Изменения

Перейти к: навигация, поиск

Класс P

771 байт добавлено, 16:02, 14 ноября 2018
Нет описания правки
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.
 
== Устойчивость класса P к изменению модели вычислений ==
Машина Тьюринга может симулировать другие модели вычислений (например, языки программирования) с не более чем полиномиальным замедлением. Благодаря этому, класс <tex>\mathrm{P}</tex> на этих моделях не становится шире.
 
Согласно [http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%B7%D0%B8%D1%81_%D0%A7%D1%91%D1%80%D1%87%D0%B0_%E2%80%94_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 тезису Чёрча-Тьюринга], любой физически реализуемый алгоритм можно реализовать на машине Тьюринга. Так что класс <tex>\mathrm{P}</tex> устойчив и в обратном преобразовании модели вычислений.
== Свойства класса P ==
== P-полные задачи ==
{{Определение|definition=Язык <tex>X</tex> является Говоря про <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полнымполноту]], если:# мы, как правило, подразумеваем <tex>X \in \mathrm{P}</tex>;# -полноту относительно <tex>\forall Y \in widetilde{\mathrm{PL}} \Rightarrow Y \leq_L X</tex> (то есть любой язык из класса -сведения.<tex>\mathrm{P}</texref> [[Сведение относительно класса функцийКлассы L, NL, coNL. Сведение по Карпу. Трудные и полные NL-полнота задачи|сводитсяо достижимости]] к <tex>X</tex> с использованием <tex>O(log(n))</texref> памяти).}}
{{Определение
<references/>
[[Категория: Теория Классы сложности]]
Infovarius
202
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/23788...66961»

Навигация