Изменения

Теорема Карпа-Липтона

5 байт добавлено, 14:47, 3 июня 2010

Нет описания правки

Требуется откуда то взять этот набор. Его можно угадать, используя квантор "<tex>\exists{}</tex>" снаружи.

<tex>C_n</tex> существует по предположению что <tex>NP \subset{P/poly}</tex> т.е.

<tex>L=\{x|\exists{C_n}: C_n</tex> решает <tex>SAT</tex> и <tex>\forall{y} C_n(f(<x,y>))=1\}</tex>

~~<tex>C_n</tex> существует по предположению что <tex>NP</tex> входит в <tex>P/poly</tex> т.е.~~

~~<tex>L=\{x|\exists{C_n}: C_n решает SAT и \forall{y} C_n(f(<x,y>))=1\}</tex>~~

'''Что такое Cn Решает SAT?'''

33

правки