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

Материал из Викиконспекты
Версия от 19:38, 4 сентября 2022; Maintenance script (обсуждение | вклад) (rollbackEdits.php mass rollback)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определение

Язык [math]A[/math] сводится по Куку к [math]B[/math], если существует разрешающая язык [math]A[/math] программа [math]m[/math], работающая полиномиальное время от длины входа, которая может использовать разрешающую программу [math]m_B[/math] для языка [math]B[/math] в качестве оракула. При этом время работы [math]m_B[/math] не учитывается.

Обозначается как [math]A {\le}_c B[/math].


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


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