|
|
| Строка 5: |
Строка 5: |
| | <tex>\mathrm{TS(p,x)}</tex> — ограничение и по времени и по памяти. | | <tex>\mathrm{TS(p,x)}</tex> — ограничение и по времени и по памяти. |
| | }} | | }} |
| − |
| |
| − | Введём понятия <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex>, аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму, а <tex>\mathrm{N}</tex> — недетерминизму).
| |
| | | | |
| | {{Определение | | {{Определение |
Версия 11:34, 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]\mathrm{DSPACE}[/math], [math]\mathrm{DTIME}[/math], [math]\mathrm{NSPACE}[/math] и [math]\mathrm{NTIME}[/math] будет дано определение многим сложностным классам, в том числе классов P и NP.
Вычисление с оракулом
| Определение: |
| Оракул — программа [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].
