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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 14: Строка 14:
 
<tex>\mathrm{DSPACE(f(n))} = \{ L \mid \exists </tex> программа <tex>p : L(p)=L</tex> и для <tex>\forall x</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>\mathrm{S(p,x)} = O(f(n)) \}</tex>.
 
<tex>\mathrm{DSPACE(f(n))} = \{ L \mid \exists </tex> программа <tex>p : L(p)=L</tex> и для <tex>\forall x</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>\mathrm{S(p,x)} = O(f(n)) \}</tex>.
 
}}
 
}}
 
Через понятия классов <tex>\mathrm{DSPACE}</tex>, <tex>\mathrm{DTIME}</tex>, <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> будет дано определение многим сложностным классам, в том числе классов [[Класс P|P]] и [[Недетерминированные вычисления. Классы NP и Σ₁|NP]].
 
  
 
== Вычисление с оракулом ==
 
== Вычисление с оракулом ==

Версия 11:36, 2 июня 2012

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

[math]\mathrm{S(p,x)}[/math] — ограничение по памяти.

[math]\mathrm{TS(p,x)}[/math] — ограничение и по времени и по памяти.


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


Определение:
[math]\mathrm{DSPACE(f(n))} = \{ L \mid \exists [/math] программа [math]p : L(p)=L[/math] и для [math]\forall x[/math], такого что [math]|x| = n[/math] (здесь [math]n[/math] — длина входа), [math]\mathrm{S(p,x)} = O(f(n)) \}[/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].