Класс P — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 20: Строка 20:
  
 
==Задача равенства '''P''' и '''NP'''==
 
==Задача равенства '''P''' и '''NP'''==
Основополагающей задачей теории сложности является задача равенства классов '''P''' и [[NP]], не разрешенная по сей день. Однако легко показать, что по определению, <tex> P \subset NP</tex>, так как достаточно для любой задачи класса '''P''' привести ее решение в качестве сертификата, а значит задача по определению будет входить в класс '''NP'''
+
Одним из центральных вопросов теории сложности является вопрос о равенстве классов '''P''' и [[NP]], не разрешенный по сей день. Однако легко показать, что по определению, <tex> P \subset NP</tex>, так как достаточно для любой задачи класса '''P''' привести ее решение в качестве сертификата, а значит задача по определению будет входить в класс '''NP'''

Версия 16:53, 18 марта 2010

В теории сложности Класс P - класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть [math]P=\bigcup_{i=0}^{\infty} DTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} DTIME(in^k)[/math].

Определение

Язык L лежит в классе P тогда и только тогда, когда существует такая детерминированная машина Тьюринга m, что:

  1. m завершает свою работу за полиномиальное время на любых входных данных
  2. если на вход машине m подать слово [math]l \in L[/math], то она допустит его
  3. если на вход машине m подать слово [math]l \not\in L[/math], то она не допустит его

Свойства класса P

  1. Замкнутость относительно дополнений. [math] L \in P \Rightarrow \overline L \in P[/math]
  2. Замкнутость относительно сведения по Карпу. [math] L \in P , M \le L \Rightarrow M \in P[/math]
  3. Замкнутость относительно сведения по Куку. [math] L \in P , M {\le}_c L \Rightarrow M \in P[/math]

Примеры задач и языков из P

Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:

  • нахождение делителей числа (язык делителей числа)
  • поиск диаметра связного графа

Но, по теореме о временной иерархии существуют и задачи не из P.

Задача равенства P и NP

Одним из центральных вопросов теории сложности является вопрос о равенстве классов P и NP, не разрешенный по сей день. Однако легко показать, что по определению, [math] P \subset NP[/math], так как достаточно для любой задачи класса P привести ее решение в качестве сертификата, а значит задача по определению будет входить в класс NP