Изменения

<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>'''