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