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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «<b><i>P\poly </i></b><tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex> ==Альтернативное определе…»)
 
Строка 1: Строка 1:
<b><i>P\poly </i></b><tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex>
+
'''P/poly'''<tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex>
  
 
==Альтернативное определение==
 
==Альтернативное определение==
Класс <b><i>C\f</i></b> <tex> = \{L | \exists</tex> двуместная <tex> R \in C ~\exists a_1, \ldots, a_n, \ldots : |a_n| \le f(n): x \in L \Leftrightarrow R(x, a_{|x|}) = 1\}</tex><br>
+
Класс '''C/f''' <tex> = \{L | \exists</tex> двуместная <tex> R \in C ~\exists a_1, \ldots, a_n, \ldots : |a_n| \le f(n): x \in L \Leftrightarrow R(x, a_{|x|}) = 1\}</tex><br>
Тогда <b><i>P\poly </i></b><tex> = \{L | \exists R \in P ~\exists a_1, \ldots, a_n, \ldots : |a_n| \le p(n) : x \in L \Leftrightarrow R(x, a_{|x|}) = 1 \}</tex>
+
Тогда '''P/poly''' <tex> = \{L | \exists R \in P ~\exists a_1, \ldots, a_n, \ldots : |a_n| \le p(n) : x \in L \Leftrightarrow R(x, a_{|x|}) = 1 \}</tex>
  
==Некоторые факты о <b><i>P\poly</i></b>==
+
==Некоторые факты о '''P/poly'''==
* В <b><i>P\poly</i></b> входят [[Редкие языки|редкие языки]]
+
* В '''P/poly''' входят [[Редкие языки|редкие языки]]
* Если <tex>NP</tex> не входит в <b><i>P\poly</i></b>, то <tex>P \ne NP</tex>
+
* Если '''NP''' не входит в '''P/poly''', то <tex>P \ne NP</tex>
* <tex>NP \subset </tex> <b><i>P\poly</i></b> <tex>\Rightarrow \Sigma_2 = PH</tex> ([[Теорема Карпа-Липтона]])
+
* <tex>NP \subset </tex> '''P/poly''' <tex>\Rightarrow \Sigma_2 = PH</tex> ([[Теорема Карпа-Липтона]])
* <tex> BPP \subset </tex> <b><i>P\poly</i></b>
+
* <tex> BPP \subset </tex> '''P/poly'''

Версия 17:30, 5 июня 2010

P/poly[math] = \{L | L [/math] имеет схемную сложность полином[math]\}[/math]

Альтернативное определение

Класс C/f [math] = \{L | \exists[/math] двуместная [math] R \in C ~\exists a_1, \ldots, a_n, \ldots : |a_n| \le f(n): x \in L \Leftrightarrow R(x, a_{|x|}) = 1\}[/math]
Тогда P/poly [math] = \{L | \exists R \in P ~\exists a_1, \ldots, a_n, \ldots : |a_n| \le p(n) : x \in L \Leftrightarrow R(x, a_{|x|}) = 1 \}[/math]

Некоторые факты о P/poly