Problem występuje w P tylko wtedy, gdy P! = NP

Czy są jakieś problemy, które można rozwiązać w czasie wielomianowym tylko wtedy, gdy P! = NP, a w innym przypadku rozwiązać (powiedzmy) ? $O(2^n)$

Prostym przykładem byłoby: Jeśli P! = NP, oblicz test pierwszeństwa dla losowej liczby n-bitowej, w przeciwnym razie oceń losową pozycję najgorszego przypadku w uogólnionych szachach planszy nxn z 2n częściami po każdej stronie. To wydaje się trochę hacking. Czy są jakieś naturalne przykłady?

cc.complexity-theory reference-request Phylliida
źródło

Nie do końca to, o co pytasz, ale istnieją połączenia między dolnymi granicami obwodu (np. SAT wymaga obwodów wielobiegunowych, co oznacza w szczególności, że P! = NP) i derandomizacji (np. BPP = P, w szczególności niektóre nowe problemy byłyby znany jako P). Ale jestem prawie pewien, że P! = NP nie jest wystarczająco silnym założeniem dla takiego wyniku.

usul

Jeśli jest możliwe do udowodnienia w ZFC (problem otwarty), wówczas algorytmem może być: na wejściu , jeśli

nie koduje prawidłowego dowodu

wówczas wyjście

przeciwnym razie symulacja maszyny Turinga

na pustej taśmie dla

kroki i wyjście

jeśli odrzuca lub nie zatrzymuje się,

przeciwnym razie.

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$

Marzio De Biasi,

Co powiesz na to, czy można to udowodnić w HoTT, ale nie w ZFC?

Chad Brewbaker,

@MarzioDeBiasi To prawda, dziękuję, a tak naprawdę, jak zauważył Chad, można użyć dowolnego zestawu aksjomatów zamiast ZFC, miejmy nadzieję, stosując spójny, który może w znaczący sposób udowodnić, że P! = NP. To wciąż wydaje się dość hackerskie, mam na myśli, że w moim przykładzie moglibyśmy łatwo zastąpić

o dowolnej innej złożoności czasowej (w tym, powiedzmy, rozwiązaniu problemu zatrzymania).

2^{[} | x |]

$2^[|x|]$

Phylliida

Możliwe, że nie ma naturalnie wyglądających przykładów typu, o który proszę, ale wydaje się, że formalne definicje „naturalnego” (powiedzmy, dużego prawdopodobieństwa wybrania tego problemu, biorąc pod uwagę przypadkowy problem we wszystkich problemach w EXP), trochę tracą na niektóre znaczenie, więc próba udowodnienia tego może nie być tak znacząca, nie jestem pewien.

Phylliida

Problem występuje w P tylko wtedy, gdy P! = NP

Odpowiedzi: