Изменения

Перейти к: навигация, поиск

Теорема Бейкера-Гилла-Соловэя

1 байт добавлено, 10:58, 16 июня 2010
м
Нет описания правки
1) <tex>A</tex> - <tex>PS</tex>-полный язык (разрешимый на полиномиальной памяти)
<tex>NP^A=NPS=PS=P^A</tex>
 
2) <tex>B</tex>:<tex>L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}</tex>
Diniska
33
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/1515»

Навигация