Просмотр исходного текста страницы Сложностные классы. Вычисления с оракулом

{{Определение
|definition=
<tex>\mathrm{T}(p,x)</tex> — время работы программы р на входе х.
}}
{{Определение
|definition=
<tex>\mathrm{S}(p,x)</tex> — объем памяти, требуемый программе р для выполнения на входе х.
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков, для которых существует детерминированная программа, разрешающая их с данными ограничениями времени и памяти.
}}

{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> - мощность <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> - мощность <tex>x</tex>).
}}

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

[[Категория: Теория сложности]]