211
правок
Изменения
м
→Вычисление с оракулом
Оракул — программа <tex>A(x)</tex>, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x \in A</tex>.
}}
Сложностный класс задач, решаемых алгоритмом из класса <tex>C</tex> с оракулом для языка <tex>A</tex>, обозначают <tex>C^A</tex>. Так же <tex>C</tex> называют сложностным классом с доступом к оракулу <tex>A</tex>.Если <tex>A</tex> — множество языков, то <tex>C^A =\bigcup\limits_{D \in A}C^D</tex>, где <tex>D</tex> — язык из <tex>A</tex>.
[[Категория: Теория сложности]]
