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

Материал из Викиконспекты
Перейти к: навигация, поиск
(1.1.1.2 поправлен tex на переменных)
м (rollbackEdits.php mass rollback)
 
(не показано 20 промежуточных версий 6 участников)
Строка 1: Строка 1:
 +
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
 +
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Классы NP и Σ₁|NP]] и т.д.
 +
 
== Определения ==
 
== Определения ==
  
Строка 4: Строка 7:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>\mathrm{T}(p,x)</tex> — время работы программы <tex>р</tex> на входе <tex>х</tex>.
+
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>\mathrm{S}(p,x)</tex> — объем памяти, требуемый программе <tex>р</tex> для выполнения на входе <tex>х</tex>.
+
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
 
}}
 
}}
  
Строка 14: Строка 17:
 
{{Определение
 
{{Определение
 
|definition=
 
|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>).<br>
+
<tex>\mathrm{DTIME}(f(n))</tex> {{---}} класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> выполнено <tex>\mathrm{T}(m,x) \leqslant f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
 
}}
 
}}
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|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>).
+
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
 
}}
 
}}
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>\mathrm{TS}(f,g)</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>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
+
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>n</tex> — длина входа.
 
}}
 
}}
  
Строка 28: Строка 33:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
+
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, в которой существует пара "ленточный символ - состояние", для которой существует 2 и более команд.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>\mathrm{NTIME}(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>).<br>
+
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>\mathrm{NSPACE}(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>).
+
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
 
}}
 
}}
  
[[Категория: Теория сложности]]
+
== См. также ==
 +
* [[Класс P]]
 +
* [[Классы NP и Σ₁]]
 +
 
 +
== Источники информации ==
 +
* [http://ru.wikipedia.org/wiki/Класс_сложности Википедия | Класс сложности]
 +
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.
 +
 
 +
[[Категория:Теория сложности|*]]
 +
[[Категория:Детерминированные и недетерминированные вычисления, сложность по памяти и времени|*]]
 +
[[Категория:Базовые определения|*]]
 +
[[Категория:Классы сложности|*]]

Текущая версия на 19:03, 4 сентября 2022

В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время? Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы P, NP и т.д.

Определения

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.

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


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


Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как [math]\mathrm{DTIME}[/math] и [math]\mathrm{DSPACE}[/math] (префикс [math]\mathrm{D}[/math] соответствует детерминизму).

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


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


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


Аналогичным образом определяются классы [math]\mathrm{NSPACE}[/math] и [math]\mathrm{NTIME}[/math] (префикс [math]\mathrm{N}[/math] соответствует недетерминизму).

Определение:
Недетерминированная машина Тьюринга (НМТ) — машина Тьюринга, в которой существует пара "ленточный символ - состояние", для которой существует 2 и более команд.


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


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


См. также

Источники информации

  • Википедия | Класс сложности
  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.