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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
В теории сложности '''Класс''' <tex>P</tex> - класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть  
+
В теории сложности '''Класс''' <tex>P</tex> &mdash; класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть  
  
 
<tex>P=\bigcup_{i=0}^{\infty} DTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} DTIME(in^k)</tex>.  
 
<tex>P=\bigcup_{i=0}^{\infty} DTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} DTIME(in^k)</tex>.  
Строка 13: Строка 13:
 
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
 
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
 
# Замкнутость относительно [[Сведение по Карпу|сведения по Куку]]. <tex> L \in P , M {\le}_c L \Rightarrow M \in P</tex>
 
# Замкнутость относительно [[Сведение по Карпу|сведения по Куку]]. <tex> L \in P , M {\le}_c L \Rightarrow M \in P</tex>
# <tex>L \subset P \Rightarrow P=P^L</tex>, где <tex>C^D</tex> &mdash  
+
# <tex>L \subset P \Rightarrow P=P^L</tex>, где <tex>C^D</tex> &mdash; множество языков, разрешимых с органичением C с помощью оракула из D (C и D &mdash; сложностные классы).
  
 
==Примеры задач и языков из <tex>P</tex>==
 
==Примеры задач и языков из <tex>P</tex>==

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

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

[math]P=\bigcup_{i=0}^{\infty} DTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{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 \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]
  4. [math]L \subset P \Rightarrow P=P^L[/math], где [math]C^D[/math] — множество языков, разрешимых с органичением C с помощью оракула из D (C и D — сложностные классы).

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

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

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

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

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

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