Последствия

12

Мы знаем, что если то весь PH разрушается. Что если полиномиальная иерархия частично разрушится? (Или как понять, что PH может рухнуть выше определенной точки, а не ниже?)P=NP

Короче говоря, каковы будут последствия и P N P ?NP=coNPPNP

Ксавье Лабуз
источник
3
В этом случае PH все еще разрушается (до 1-го, а не 0-го уровня).
Гек Беннетт
Первое предложение, кажется, выражает, что «у нас проблемы, если P = NP не потому, что иерархия рушится», что является неправильным (оставляя в стороне, возможно, спорный вопрос о том, является ли P = NP проблемной ситуацией или нет).
Каве
2
@ Хак, я думаю, что ОП может пытаться спросить, каковы последствия провала PH на 1-й уровень. Какие крутые проблемы мы сможем решить тогда?
Артем Казнатчеев
@Xavier: Почему вы говорите "... и у нас проблемы" . P = NP, и , как следствие , крах PH, будет просто фантастическим ;-)
Giorgio Camerani
@ArtemKaznatcheev: спасибо вашему пониманию
Ксавье Лабуз

Ответы:

17

Для меня одно из самых основных и удивительных следствий - это наличие коротких доказательств для целого ряда проблем, где очень трудно понять, почему у них должны быть короткие доказательства. (Это своего рода шаг назад от «Какие другие последствия сложности имеет этот коллапс?» К «Каковы основные, практические причины, по которым этот коллапс будет удивительным?»)NP=coNP

Например, если , то для каждого графа, который не является гамильтоновым, существует краткое доказательство этого факта. Аналогично для графиков, которые не являются 3-раскрашиваемыми. Аналогично для пар графов, которые не изоморфны. Аналогично для любой тавтологии высказываний .NP=coNP

В мире, где , трудность доказательства пропозициональной тавтологии заключается не в том, что у некоторых коротких тавтологий есть длинные доказательства - потому что в таком мире у каждой тавтологии есть полиномиально короткое доказательство, - а скорее из-за того, что есть некоторые Другая причина, по которой мы не можем найти эти доказательства эффективно.PNP=coNP

Джошуа Грохов
источник
Мне нравится этот ответ! +1
Тайфун Пей
Ткс за ваш ответ, подчеркнутое следствие довольно удивительно. Интересно, какая другая причина не может найти эти доказательства эффективно. Любая идея ?
Ксавье Лабуз
12

Если мы также предположим, что , то гипотеза также вызовет коллапс рандомизированных классов:NP=RP . Хотя предполагается, что все они безоговорочно рухнут в P , все равно остается открытым, действительно ли это произойдет. В любом случае, N P = c o N P , по-видимому, не означает, что эти рандомизированные классы разрушаются.ZPP=RP=CoRP=BPPPNP=coNP

Если их нет, то есть, по крайней мере, у нас есть , то вместе с гипотезой N P = c o N P это будет иметь еще одно важное следствие:BPPPNP=coNP . Это следует из результата Babai, Fortnow, Нисан и Wigderson,котором говоритсячтоесли все унарные (приблизительно) языки в P H попадают в P , то B P P = P . Таким образом, если Б Р РР , то они не могут все попадают в P , как N P = C ö N P предположение означает P H = N P . Следовательно, в N P - P должен быть язык подсчетаENEPHPBPP=PBPPPPNP=coNPPH=NPNPP, И, наконец, присутствие языка в учетный хорошо известно, подразумевает EN E .NPPENE

Приведенные выше рассуждения показывают интересный эффект , что гипотеза, несмотря на то , коллапс, фактически усиливает разделяющую силу B P PP , так как последний в одиночку не известно, подразумевает EN E . Эта «аномалия» , кажется, поддерживает гипотезу B P P = P .NP=coNPBPPPENEBPP=P

Андрас Фараго
источник
1
Может быть, я здесь медленный, но как NP = coNP подразумевает ZPP = RP = coRP = BPP?
Джошуа Грохов
@JoshuaGrochow Я тоже застрял в этом.
Tayfun Pay
Спасибо, я действительно пропустил условие. Я исправил ответ.
Андрас Фараго
@AndrasFarago хорошо! +1 :)
Tayfun Pay
@AndrasFarago Tks за ваш ответ!
Ксавье Лабуз
7

#P

ValiantsDefinition:_C#C=AC(#P)A(#PA)A

#NP=#CoNP

TodasDefinition:_C#.CfCRpxf(x)=||{y|p(|x|)=|y|R(x,y)}||

#.NP=#.CoNPNP=CoNP

PNPFP#P

Тайфун Пей
источник
Это счетная версия NP.
Тайфун Pay
На что указывает период в "# .NP"?
Тимоти Сан
4
Есть два типа, если считать подсчеты иерахиев. Один от Valiant в 1979 году, и он использует обозначения #P, # NP, # Co-NP ... Где # NP = Co-NP. С другой стороны, Тода определил другую иерархию. И запись для этого использует точки. И # .NP! = #. Co-NP, если только NP = Co-NP
Tayfun Pay
2

Ker-i Ko Показано, что существует оракул, который заставляет PH разрушаться на k-м уровне. См. «Ker-I Ko: Релятивизированные полиномиальные иерархии времени, имеющие ровно K уровней. SIAM J. Comput. 18 (2): 392-408 (1989)».

Бин фу
источник
Можете ли вы связать нас с газетой?
Tayfun Pay
@ BinFu Tks - я думал, что PH рухнет на первый уровень ...
Ксавье Лабуз
1
Для случая k = 1 это случай этой проблемы. Полиномиальное время действительно падает до NP при условии NP = coNP. Существование оракула для k-го уровня в статье Ко означает барьер любого релятивизированного метода для решения проблемы коллапса PH.
Бин Фу
1
@BinFu: ваши замечания не описывают никаких последствий PNP = coNP . Вопрос заключался не в том, как показать коллапс на первом уровне или о результатах, которые также описывают коллапс на первом уровне, а в том, что будет известно как следствие коллапса на первый уровень. Я не понимаю, как ваш ответ на это вообще.
Ниль де Бёдрап
1
Каждая выполнимая логическая формула имеет полиномиальное доказательство времени и длины, которое является истинным назначением, чтобы сделать формулу истинной. Условие NP = coNP заставляет каждую неудовлетворительную булеву формулу иметь полиномиальное доказательство времени и длины. Если P не равно NP, а NP = coNP, то не существует алгоритма полиномиального времени, чтобы найти доказательство длины полинома для булевой формулы для ее выполнимости или неудовлетворенности. Точно так же у нас будут аналогичные выводы для всех проблем в NP.
Бин Фу