Оракул — абстракция , вычисляющая за Будем называть '''оракулом''' для языка <tex>O(1)A</tex> времениабстрактное вычислительное устройство, верно ли, что для которого постулируется возможность решить задачу о принадлежности некоторого слова языку <tex>xA</tex> принадлежит множеству за <tex>AO(1)</tex>времени.
}}
Сложностный класс задач, решаемых алгоритмом из класса <tex>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.
