P/poly

Материал из Викиконспекты
Версия от 22:16, 2 июня 2010; 192.168.0.2 (обсуждение) (Новая страница: «<b><i>P\poly </i></b><tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex> ==Альтернативное определе…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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