Сведение по Куку — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
м (rollbackEdits.php mass rollback)
 
(не показана 1 промежуточная версия 1 участника)
(нет различий)

Текущая версия на 19:38, 4 сентября 2022

Определение

Язык [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].


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