Изменения
Новая страница: «<b><i>P\poly </i></b><tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex> ==Альтернативное определе…»
<b><i>P\poly </i></b><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>
Тогда <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>
==Некоторые факты о <b><i>P\poly</i></b>==
* В <b><i>P\poly</i></b> входят [[Редкие языки|редкие языки]]
* Если <tex>NP</tex> не входит в <b><i>P\poly</i></b>, то <tex>P \ne NP</tex>
* <tex>NP \subset </tex> <b><i>P\poly</i></b> <tex>\Rightarrow \Sigma_2 = PH</tex> ([[Теорема Карпа-Липтона]])
* <tex> BPP \subset </tex> <b><i>P\poly</i></b>
==Альтернативное определение==
Класс <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>
Тогда <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>
==Некоторые факты о <b><i>P\poly</i></b>==
* В <b><i>P\poly</i></b> входят [[Редкие языки|редкие языки]]
* Если <tex>NP</tex> не входит в <b><i>P\poly</i></b>, то <tex>P \ne NP</tex>
* <tex>NP \subset </tex> <b><i>P\poly</i></b> <tex>\Rightarrow \Sigma_2 = PH</tex> ([[Теорема Карпа-Липтона]])
* <tex> BPP \subset </tex> <b><i>P\poly</i></b>
