202
правки
Изменения
Нет описания правки
# если на вход машине <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-полной полные задачи ==Говоря про <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полноту]], мы, как правило, подразумеваем <tex>\mathrm{P}</tex>-полноту относительно <tex>\widetilde{\mathrm{L}}</tex>-сведения.<ref>[[Классы L, NL, coNL. NL-полнота задачи о достижимости]]</ref>
{{Определение
|definition=
{{Теорема
|statement =
<tex>CIRCVAL</tex> {{---}} <tex>\mathrm{P}</tex>-полная задача.<ref>[[Сведение относительно класса функцийhttp://www.math.sc.edu/~cooper/math778C/abct.pdf S. Сведение по КарпуArora, B. Трудные и полные задачи#Определения трудных и полных задач|полная]Barak, "Computational Complexity: A Modern Approach"] задача.</ref>
}}
<references/>
[[Категория: Теория Классы сложности]]
