Проблема, которая есть в P, только если P! = NP

Существуют ли проблемы, которые разрешимы за полиномиальное время, только если P! = NP, и иначе разрешимы за (скажем) времени? $O(2^n)$

Простым примером может быть: Если P! = NP, вычислите тест на простоту для случайного n-разрядного числа, в противном случае оцените случайную позицию наихудшего случая в обобщенных шахматах доски nxn с 2n фигурами на каждой стороне. Это кажется немного хакерским. Есть ли еще естественные примеры?

cc.complexity-theory reference-request Phylliida
источник

Не совсем то, о чем вы спрашиваете, но есть связи между нижними границами цепей (например, SAT требует цепей суперполиномиального размера, подразумевающих, в частности, что P! = NP) и дерандомизацией (например, BPP = P, в частности, возникнут некоторые новые проблемы). известно, что в P). Но я уверен, что P! = NP не является достаточно сильным допущением для любого такого результата.

Усул

Если

доказуемо в ZFC (открытая задача), то алгоритм может быть таким: на входе

, если

не кодирует действительное доказательство

тогда вывод

противном случае имитирует машину Тьюринга

на пустой ленте для

шаги и вывод

если он отклоняет или не останавливается,

противном случае.

P \neq N P

$P\neq NP$

x

$x$

x

$x$

P \neq N P

$P\neq NP$

0

$0$

x

$x$

2^{| x |}

$2^{|x|}$

0

$0$

1

$1$

Марцио Де Биаси,

Как насчет того, если это доказуемо в HoTT, но не в ZFC?

Чад Brewbaker

2^{[} | x |]

$2^[|x|]$

Возможно, не существует естественно выглядящих примеров того типа, который я запрашиваю, но похоже, что формальные определения «естественного» (скажем, высокой вероятности выбора этой проблемы при случайной проблеме во всех задачах в EXP) теряются на некоторые значения, так что, возможно, не имеет смысла пытаться доказать это, я не уверен.

Филиллида

Проблема, которая есть в P, только если P! = NP

Ответы: