Изменения

<tex>DTIME(f(n)) = \{ L \mid \exists </tex> программа <tex>p : L(p)=L,</tex> для любого <tex>x</tex>, такого что <tex>|x| = n</tex>, где n — длина входа и <tex>Time(p,x) = O( f(n)) \}</tex>.

{{Определение|definition=Оракул — программа <tex>A(x)</tex>, вычислющая за <tex>O(1)</tex> верно ли, что <tex>x \in A</tex>.}}Сложностный класс задач, решаемых алгоритмом из класса <tex>AC</tex> с оракулом для языка <tex>BA</tex> обозначают <tex>C^A^B</tex>. Так же <tex>AC</tex> называют сложностным классом с доступом к оракулу <tex>BA</tex>.Если <tex>BA</tex> — это множество языков, то <tex>C^A^B =\bigcup\limits_{D \in BA}AC^D</tex>, где <tex>D</tex> — язык из <tex>BA</tex>.