Сложностные классы. Вычисления с оракулом — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 15: Строка 15:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p : 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>).
+
<tex>\mathrm{DTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p такая, что 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=
 
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p : 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>).
+
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p такая, что 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>).
 
}}
 
}}
  

Версия 13:40, 3 июня 2012

Определение:
[math]\mathrm{T}(p,x)[/math] — время работы программы р на входе х.


Определение:
[math]\mathrm{S}(p,x)[/math] — объем памяти, требуемый программе р для выполнения на входе х.


Определение:
[math]\mathrm{TS}(f,g)[/math] — класс языков, для которых существует детерминированная программа, разрешающая их с данными ограничениями времени и памяти.


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


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


Вычисление с оракулом

Определение:
Оракул — программа [math]A(x)[/math], вычисляющая за [math]O(1)[/math] времени, верно ли, что [math]x \in A[/math].

Сложностный класс задач, решаемых алгоритмом из класса [math]\mathrm{C}[/math] с оракулом для языка [math]\mathrm{A}[/math], обозначают [math]\mathrm{C^A}[/math]. Если [math]\mathrm{A}[/math] — множество языков, то [math]\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}[/math].