Мы знаем, что если то весь PH разрушается. Что если полиномиальная иерархия частично разрушится? (Или как понять, что PH может рухнуть выше определенной точки, а не ниже?)
Короче говоря, каковы будут последствия и P ≠ N P ?
Мы знаем, что если то весь PH разрушается. Что если полиномиальная иерархия частично разрушится? (Или как понять, что PH может рухнуть выше определенной точки, а не ниже?)
Короче говоря, каковы будут последствия и P ≠ N P ?
Ответы:
Для меня одно из самых основных и удивительных следствий - это наличие коротких доказательств для целого ряда проблем, где очень трудно понять, почему у них должны быть короткие доказательства. (Это своего рода шаг назад от «Какие другие последствия сложности имеет этот коллапс?» К «Каковы основные, практические причины, по которым этот коллапс будет удивительным?»)NP=coNP
Например, если , то для каждого графа, который не является гамильтоновым, существует краткое доказательство этого факта. Аналогично для графиков, которые не являются 3-раскрашиваемыми. Аналогично для пар графов, которые не изоморфны. Аналогично для любой тавтологии высказываний .NP=coNP
В мире, где , трудность доказательства пропозициональной тавтологии заключается не в том, что у некоторых коротких тавтологий есть длинные доказательства - потому что в таком мире у каждой тавтологии есть полиномиально короткое доказательство, - а скорее из-за того, что есть некоторые Другая причина, по которой мы не можем найти эти доказательства эффективно.P≠NP=coNP
источник
Если мы также предположим, что , то гипотеза также вызовет коллапс рандомизированных классов:NP=RP . Хотя предполагается, что все они безоговорочно рухнут в P , все равно остается открытым, действительно ли это произойдет. В любом случае, N P = c o N P , по-видимому, не означает, что эти рандомизированные классы разрушаются.ZPP=RP=CoRP=BPP P NP=coNP
Если их нет, то есть, по крайней мере, у нас есть , то вместе с гипотезой N P = c o N P это будет иметь еще одно важное следствие:BPP≠P NP=coNP . Это следует из результата Babai, Fortnow, Нисан и Wigderson,котором говоритсячтоесли все унарные (приблизительно) языки в P H попадают в P , то B P P = P . Таким образом, если Б Р Р ≠ Р , то они не могут все попадают в P , как N P = C ö N P предположение означает P H = N P . Следовательно, в N P - P должен быть язык подсчетаE≠NE PH P BPP=P BPP≠P P NP=coNP PH=NP NP−P , И, наконец, присутствие языка в учетный хорошо известно, подразумевает E ≠ N E .NP−P E≠NE
Приведенные выше рассуждения показывают интересный эффект , что гипотеза, несмотря на то , коллапс, фактически усиливает разделяющую силу B P P ≠ P , так как последний в одиночку не известно, подразумевает E ≠ N E . Эта «аномалия» , кажется, поддерживает гипотезу B P P = P .NP=coNP BPP≠P E≠NE BPP=P
источник
источник
Ker-i Ko Показано, что существует оракул, который заставляет PH разрушаться на k-м уровне. См. «Ker-I Ko: Релятивизированные полиномиальные иерархии времени, имеющие ровно K уровней. SIAM J. Comput. 18 (2): 392-408 (1989)».
источник