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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Правки Ulyantsev (обсуждение) откачены к версии 192.168.0.2)
Строка 1: Строка 1:
В теории сложности '''Класс P''' —  класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть  
+
В теории сложности '''Класс''' <tex>P</tex> &mdash;  класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть  
  
'''P'''=<tex>\bigcup_{i=0}^{\infty}</tex>'''[[DTIME]]'''<tex>(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty}</tex>'''DTIME'''<tex>(in^k)</tex>.  
+
<tex>P=\bigcup_{i=0}^{\infty} DTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} DTIME(in^k)</tex>.  
  
 
==Определение==
 
==Определение==
Язык <tex>L</tex> лежит в классе '''P''' тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:
+
Язык L лежит в классе <tex>P</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;
+
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных  
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;
+
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.
+
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его
  
==Свойства класса P==
+
==Свойства класса <tex>P</tex>==
# Замкнутость относительно дополнений. <tex> L </tex> ∈ '''P''' <tex>\Rightarrow \overline L </tex> ∈ '''P'''
+
# Замкнутость относительно дополнений. <tex> L \in P \Rightarrow \overline L \in P</tex>
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex>L</tex> ∈ '''P''' , <tex>M \le L \Rightarrow M</tex> ∈ '''P'''
+
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Карпу|сведения по Куку]]. <tex>L</tex> ⊂ '''P''' <tex>\Rightarrow</tex> '''P'''='''P'''<sup><math>L</math></sup>.
+
# Замкнутость относительно [[Сведение по Карпу|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.
  
==Примеры задач и языков из P==
+
==Примеры задач и языков из <tex>P</tex>==
 
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
 
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
 
* определение связности графов;
 
* определение связности графов;
Строка 21: Строка 21:
  
  
Но, по [[теорема о временной иерархии|теореме о временной иерархии]] существуют и задачи не из '''P'''.
+
Но, по [[теорема о временной иерархии|теореме о временной иерархии]] существуют и задачи не из <tex>P</tex>.
  
==Задача равенства классов P и NP==
+
==Задача равенства <tex>P</tex> и <tex>NP</tex>==
Одним из центральных вопросов теории сложности является вопрос о равенстве классов '''P''' и '''[[NP]]''', не разрешенный по сей день.  
+
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и [[NP]], не разрешенный по сей день.  
  
Легко показать, что, по определению, '''P''' ⊂ '''NP''', так как для любой задачи класса '''P''' существует соответствующая ДМТ, которая является частным случаем НМТ, а значит задача, по определению, будет входить в класс '''NP'''.
+
Легко показать, что, по определению, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая ДМТ, которая является частным случаем НМТ, а значит задача, по определению, будет входить в класс <tex>NP</tex>.
  
 
==Ссылки==
 
==Ссылки==
 
<references/>
 
<references/>

Версия 20:45, 9 апреля 2012

В теории сложности Класс [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 \subset P \Rightarrow P=P^L[/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].

Ссылки