Класс P

Материал из Викиконспекты
Версия от 21:28, 16 апреля 2012; Tsar (обсуждение | вклад) (+ ещё теоремка)
Перейти к: навигация, поиск

Класс [math]P[/math] — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть

[math]P=\bigcup\limits_{i=0}^{\infty} DTIME(in^i)=\bigcup\limits_{i=0}^{\infty}\bigcup\limits_{k=0}^{\infty} DTIME(in^k)[/math].

Определение

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

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

Свойства класса [math]P[/math]

  1. Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если [math]L_1, L_2 \in P[/math], то: [math]L1 \cup L2 \in P[/math], [math]L1 \cap L2 \in P[/math], [math]L1L2 \in P[/math], [math]L1^* \in P[/math] и [math]\overline{L1} \in P[/math].
  2. Замкнутость относительно сведения по Карпу. [math] L \in P , M \le L \Rightarrow M \in P[/math]
  3. Замкнутость относительно сведения по Куку. [math]L \subset P \Rightarrow P=P^L[/math].

Соотношение классов [math]Reg[/math] и [math]P[/math]

Теорема:
Класс регулярных языков входит в класс [math]P[/math], то есть: [math]Reg \subset P[/math]
Доказательство:
[math]\triangleright[/math]

[math]Reg \subset TS(n, 1) \subset P[/math]

Замечание. [math]TS[/math] — ограничение и по времени и по памяти.
[math]\triangleleft[/math]

Соотношение классов [math]CFL[/math] и [math]P[/math]

Теорема:
Класс контекстно-свободных языков входит в класс [math]P[/math], то есть: [math]CFL \subset P[/math]
Доказательство:
[math]\triangleright[/math]

[math]CFL \subset TS(n^3, n^2) \subset P[/math]

Первое включение выполняется благодаря существованию алгоритма Эрли.
[math]\triangleleft[/math]

Примеры задач и языков из [math]P[/math]

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

  • определение связности графов;
  • вычисление наибольшего общего делителя.
  • проверка простоты числа.[1]


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

Задача равенства [math]P[/math] и [math]NP[/math]

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

Легко показать, что, по определению, [math] P \subset NP[/math], так как для любой задачи класса [math]P[/math] существует соответствующая ДМТ, которая является частным случаем НМТ, а значит задача, по определению, будет входить в класс [math]NP[/math].

Ссылки