Изменения

Перейти к: навигация, поиск

Сведение по Куку

164 байта добавлено, 14:04, 19 марта 2010
Определение
----
Класс <tex>P</tex> замкнут относительно сведения по Куку. Если язык <tex>A \in P</tex>, то использование <tex>A</tex> в качестве оракула ничего не дает, т.к. и без обращения к оракулу программа можно решить задачу <tex>A</tex> за полиномиальное время. Т.о. <tex>mP = P ^ A</tex> может разрешить сводимый язык.
Если A \in P то P = P ^ A---- См. также [[сведение по Карпу]].
51
правка

Навигация