означает , что, в свою очередь, имеет интересные последствия, такие как коллапс полиномиальной иерархии.
Есть ли интересные последствия для ?
означает , что, в свою очередь, имеет интересные последствия, такие как коллапс полиномиальной иерархии.
Есть ли интересные последствия для ?
Ответы:
Комментарий Эмиля Йержабека отвечает на вопрос:
Обратите внимание на следствие
Доказательство следствия:
Доказательство комментария Эмиля: Достаточно показать, что NP P / poly подразумевает P / poly NP / poly.⊆ =
Все вышеприведенные доказательства релятивизируются, потому что существование NP-полных задач также верно в релятивизированных мирах. Это говорит о том, что бесполезно искать доказательство того, что P / poly NP / poly. Однако давайте подведем итоги удаленного мотивационного раздела≠ от вопроса как «Строка совета может быть формальной аксиоматической системой (автоматически гарантируемой последовательностью, злой усмешкой), сила которой быстро увеличивается с увеличением длины ввода, и NP чрезвычайно хорош в использовании этого совета». Если не очень внимательно относиться к тому, что «существование последовательности укусов рекомендаций» имеет только «формальное» значение по отношению к фиксированной формальной системе, такая установка, вероятно, позволит построить очевидные парадоксы. Но построение таких парадоксов, тем не менее, может быть забавным, и, возможно, они могут даже предложить способы построения доказательств независимости (для достаточно слабых формальных систем).
источник