83
правки
Изменения
базовые сведения. парочка примеров задач из P
В теории сложности '''Класс P''' - класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть <tex>P=\bigcup_{i=0}^{\infty} DTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} DTIME(in^k)</tex>.
==Определение==
Язык L лежит в классе '''P''' тогда и только тогда, когда существует такая детерминированная машина Тьюринга ''m'', что:
# ''m'' завершает свою работу за полиномиальное время на любых входных данных
# если на вход машине ''m'' подать слово <tex>l \in L</tex>, то она допустит его
# если на вход машине ''m'' подать слово <tex>l \not\in L</tex>, то она не допустит его
==Свойства класса '''P'''==
# Замкнутость относительно дополнений. <tex> L \in P \Rightarrow \overline L \in P</tex>
# Замкнутость относительно сведения по Карпу. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно сведения по Куку. <tex> L \in P , M {\le}_с L \Rightarrow M \in P</tex>
==Примеры задач и языков из '''P'''==
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
* нахождение делителей числа (язык делителей числа)
* поиск диаметра связного графа
Но существуют и задачи не из '''P''', по [[теорема о временной иерархии|теореме о временной иерархии]], существуют задачи, работающие за более чем <tex>p(x) \in Poly</tex>, а значит не входящие в объединение <tex>\bigcup_{i=0}^{\infty} DTIME(in^i)</tex>, что и требовалось показать.
==Задача равенства '''P''' и '''NP'''==
Основополагающей задачей теории сложности является задача равенства классов '''P''' и [[NP]], не разрешенная по сей день. Однако легко показать, что по определению, <tex> P \subset NP</tex>, так как достаточно для любой задачи класса '''P''' привести ее решение в качестве сертификата, а значит задача по определению будет входить в класс '''NP'''
==Определение==
Язык L лежит в классе '''P''' тогда и только тогда, когда существует такая детерминированная машина Тьюринга ''m'', что:
# ''m'' завершает свою работу за полиномиальное время на любых входных данных
# если на вход машине ''m'' подать слово <tex>l \in L</tex>, то она допустит его
# если на вход машине ''m'' подать слово <tex>l \not\in L</tex>, то она не допустит его
==Свойства класса '''P'''==
# Замкнутость относительно дополнений. <tex> L \in P \Rightarrow \overline L \in P</tex>
# Замкнутость относительно сведения по Карпу. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно сведения по Куку. <tex> L \in P , M {\le}_с L \Rightarrow M \in P</tex>
==Примеры задач и языков из '''P'''==
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
* нахождение делителей числа (язык делителей числа)
* поиск диаметра связного графа
Но существуют и задачи не из '''P''', по [[теорема о временной иерархии|теореме о временной иерархии]], существуют задачи, работающие за более чем <tex>p(x) \in Poly</tex>, а значит не входящие в объединение <tex>\bigcup_{i=0}^{\infty} DTIME(in^i)</tex>, что и требовалось показать.
==Задача равенства '''P''' и '''NP'''==
Основополагающей задачей теории сложности является задача равенства классов '''P''' и [[NP]], не разрешенная по сей день. Однако легко показать, что по определению, <tex> P \subset NP</tex>, так как достаточно для любой задачи класса '''P''' привести ее решение в качестве сертификата, а значит задача по определению будет входить в класс '''NP'''
