Есть ли у P / poly NP / poly какие-либо интересные последствия?

12

P/poly=NP/poly означает , что, в свою очередь, имеет интересные последствия, такие как коллапс полиномиальной иерархии.NPP/poly

Есть ли интересные последствия для ?P/polyNP/poly

Томас Климпел
источник
6
Н РР / р ö л уP/poly=NP/poly является эквивалентом к . NPP/poly
Эмиль Йержабек
1
@ EmilJeřábek Итак, вы говорите, что P / poly NP / poly подразумевает NP P / poly. У вас есть какие-либо ссылки на это, или вы можете объяснить мне, как это увидеть? Если да, то это определенно квалифицируется как ответ.
Томас Климпел
5
@Kaveh: удаление мотивации действительно то, что мы должны делать? Это познакомило меня с вещами, с которыми я раньше не сталкивался, и не похоже, чтобы их не отрубили. Это не Твиттер.
Андрас Саламон
4
@ EmilJeřábek Думаю, я понял это сейчас. NP P / poly подразумевает P / poly = NP / poly, потому что детерминированный алгоритм может получить как свою собственную строку рекомендаций для того, чтобы стать таким же мощным, как NP, так и строку рекомендаций для языка из NP / poly, и это достаточно, чтобы решить этот язык.
Томас Климпел
2
@ThomasKlimpel: Да, именно так.
Эмиль Йержабек

Ответы:

10

Комментарий Эмиля Йержабека отвечает на вопрос:

P / poly NP / poly эквивалентно NP P / poly=

Обратите внимание на следствие

P / poly NP / poly подразумевает P NP.

Доказательство следствия:

  1. P / poly NP / poly эквивалентен NP P / poly (комментарий Эмиля)= 
  2. NP P / poly подразумевает P / poly NP / poly (подразумевается 1.)= 
  3. P / poly NP / poly подразумевает NP P / poly (эквивалент 2.) 
  4. NP P / poly подразумевает P NP (P P / poly) 
  5. P / poly NP / poly подразумевает P NP (подразумевается под 3. и 4.) 

Доказательство комментария Эмиля: Достаточно показать, что NP P / poly подразумевает P / poly NP / poly.=

  1. Итак, давайте предположим, что NP P / poly.
  2. Поскольку SAT NP существует и последовательность строк с , детерминированный алгоритм, который может решить экземпляры SAT размера во времени , если у него есть доступ к . WLOG, этот алгоритм может также определять экземпляры SAT размера , потому что мы можем определить измененную последовательность с , где все предыдущие строки рекомендаций включены в .pSATkSAT>0sn|sn|nkSATnnpSATsnnsn=sn1sn|sn|nkSAT+1sn
  3. Теперь пусть NP / poly - произвольный язык, для которого нам нужно показать P / poly. Существует и последовательность строк с и недетерминированный алгоритм, который может определять экземпляров размера во времени , если у него есть доступ к .LLpLkL>0ln|ln|nkLLnnpLln
  4. Для каждого с , экземпляр СБ размера может быть вычислен (во время ) , что выполнимо точно , если .w|w|=ncnpLO(npL)wL
  5. Таким образом, для последовательности рекомендательных строк с , комбинация детерминированных алгоритмов из 2. и 4. дает детерминированный алгоритм, который может определять экземпляров размера за время , если он имеет доступ к .tn=lnscnpL|tn|nkL+(cnpL)kSATLnO((cnpL)pSAT)tn
  6. Поскольку NP / poly был произвольным языком, это показывает NP / poly P / poly, в предположении, что NP P / poly.L

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

оборота Томас Климпел
источник