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

Gdybyśmy znali konkretny język obliczeniowy taki, że moglibyśmy udowodnić $L$ , spowodowałoby to, że byłoby równoważnezdaniu . Chociaż wynosi , nie wiadomo, że jest to , i jest to absolutnie nieprawda w relatywizowanym świecie (patrzhttps://cstheory.stackexchange.com/a/16644). $L\in\mathrm P\iff\mathrm P\ne\mathrm{NP}$ $\mathrm P\ne\mathrm{NP}$ $\Sigma^0_2$ $\mathrm P\ne\mathrm{NP}$ $\Pi^0_2$ $\Sigma^0_2$

— Emil Jeřábek
źródło

Powiązane: Komentarz Emila do MO

— Kaveh