33
правки
Изменения
м
<tex><x,y> \subset{L_1}</tex> означает что если Если <tex>L_1\in{} NP</tex> то <tex>L_1 \le{}_m SAT</tex> с помощью <tex>f</tex>, т.е.
Нет описания правки
----
'''Требуется доказать, что <tex>L\in \Sigma_1</tex>'''
<tex>L=\{x|\forall{y} f(<x,y>)\in{SAT}\}</tex>
'''Что такое "<tex>f(<x,y>)\subset{SAT}</tex>"?'''
<tex>f(<x,y>)\subset{SAT}</tex> <tex>-- </tex> для некоторого набора логических схем это означает выполнимость всего этого набора. Если предположить, что набор этих схем нам известен , то получится , что <tex>L=\{x|\forall{y} C_n(f(<x,y>))=1\}</tex> ,где <tex>n</tex>- длина входа <tex><x,y></tex>.
Требуется откуда то взять этот набор. Его можно угадать, используя квантор "<tex>\exists{}</tex>" снаружи.
