Изменения

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

PCP-система

86 байт убрано, 16:46, 4 июня 2012

→‎Свойства

|statement = <tex>\mathrm{PCP}[0, poly(n)]</tex> = <tex>\mathrm{NP}</tex>.

|proof =

Очевидно следует из [[~~Недетерминированные вычисления. Классы NP и Σ₁#Классы NP и Σ₁~~Классы_NP_и_Σ₁|определения Σ₁]].

}}

Анонимный участник

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/23740»