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

Определение

Язык [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]m[/math] может разрешить сводимый язык.

Если A \in P то P = P ^ A