Bariery, aby pokazać

Wszyscy wiemy, że pokazanie ma bariery. Wszyscy badaliśmy te bariery, ponieważ uważamy, że $P\ne NP$ $P\ne NP$ .

Załóżmy jednak, że i są mądrzy ludzie, którzy wierzą, że taka możliwość istnieje . Jeśli tak rzeczywiście jest, to sam fakt, że nie widzieliśmy żadnych dobrych algorytmów, wskazuje, że mogą istnieć bariery również w tym alternatywnym wszechświecie. Niezawodność jest barierą i nie wiemy na pewno, że jest prawdą. Nie wiemy na pewno, czy jest również prawdą, a zatem czy można udowodnić, że również jest pokonana barierą? $P=NP$ $P\ne NP$ $P\ne NP$ $P= NP$ $P=NP$

p-vs-np barriers T ....
źródło

Jak zauważył Kaveh, jeśli P = NP, bariera naturalnych dowodów wydaje się znikać. Bariery relatywizacja i algebrization już działa zarówno przed

. Myślę, że odpowiedź brzmi: naturalne dowody wydają się nie mieć zastosowania, ale algebrizacja i relatywizacja wciąż mają zastosowanie.

P = N P

$P=NP$

P \neq N P

$P\neq NP$

Joshua Grochow,

@ThomasKlimpel: Relatywizacja zdecydowanie odnosi się do P = NP: Baker-Gill-Solovay dał wyrocznię rel, dla której P = NP, i wyrocznię rel, dla której P

NP, co oznacza, że techniki relatywizacji nie mogą rozwiązać pytania P vs NP w obu kierunek . Algebrizacja została wprowadzona, ponieważ dowód, że IP = PSPACE (i powiązane rzeczy, takie jak MIP = NEXP) nie został relatywizowany.

\neq

$\neq$

Joshua Grochow

@JoshuaGrochow Co to jest technika relatywizacji służąca udowodnieniu równości? Czy dowód, że log (n) -AuxPDA jest równy P, stosuje technikę relatywizacji? Wydaje mi się, że gdzieś przeczytałem, że istnieje wyrocznia, względem której log (n) -AuxPDA! = P, ale być może jest to bardziej związane z subtelnością wyroczni dla obliczeń ograniczonych przestrzenią. Jednak w celu udowodnienia nierówności jest dość oczywiste, że większość znanych metod relatywizuje się.

Thomas Klimpel

@ThomasKlimpel: przykładem techniki algebrizing dla udowodnienia równości jest wynik IP = PSPACE. Wierzę, że NL = relatywizuje CoNL. Jestem pewien, że wynik AUC-SPACE (poli) = PSPACE relatywizuje się. W rzeczywistości trudno mi wymyślić jakikolwiek wynik równości, który ani nie relatywizuje, ani nie algebry. Odp: „a jeśli znasz ten algorytm”: jeśli P = NP, to w pewnym sensie to robimy, mianowicie uniwersalne wyszukiwanie Levina! Ale uniwersalne poszukiwanie Levina relatywizuje ...

Joshua Grochow

Nie ma prawdziwej bariery dla jakiegoś szalonego algorytmu, który zdarza się, aby rozwiązać zagadnienie logiczne. Brak takiej bariery z pewnością nie implikuje prawdy ani nawet prawdopodobieństwa.

Lance Fortnow

Bariery, aby pokazać

Odpowiedzi: