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