P/poly - История изменений

Andrey Danilchenko: переименовал «P by poly» в «P/poly»

2010-06-05T14:30:29Z

переименовал «P by poly» в «P/poly»

Andrey Danilchenko в 14:30, 5 июня 2010

2010-06-05T14:30:14Z

192.168.0.2: Новая страница: «P\poly = \{L | L имеет схемную сложность полином\} ==Альтернативное определе…»

2010-06-02T19:16:17Z

Новая страница: «P\poly <tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex> ==Альтернативное определе…»

Новая страница

P\poly <tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex>

==Альтернативное определение==
Класс 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> 
Тогда 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>

==Некоторые факты о P\poly==
* В P\poly входят [[Редкие языки|редкие языки]]
* Если <tex>NP</tex> не входит в P\poly, то <tex>P \ne NP</tex>
* <tex>NP \subset </tex> P\poly <tex>\Rightarrow \Sigma_2 = PH</tex> ([[Теорема Карпа-Липтона]])
* <tex> BPP \subset </tex> P\poly

@@ Строка 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'''

← Предыдущая	Версия 14:30, 5 июня 2010
(нет различий)