Изменения

Класс <tex>P</tex> замкнут относительно сведения по Куку. Если язык <tex>A \in P</tex>, то использование <tex>A</tex> в качестве оракула ничего не дает, т.к. так как можно решить задачу <tex>A</tex> за полиномиальное время. Полиномиальное количество обращений к такому "оракулу" выполняется опять же за полиномиальное время. Т.о. Таким образом, <tex>P = P ^ A</tex>.

См. Смотрите также [[сведение по Карпу]].