Wszyscy wiemy, że pokazanie ma bariery. Wszyscy badaliśmy te bariery, ponieważ uważamy, że P ≠ N P. .
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ść P ≠ N P jest barierą i nie wiemy na pewno, że P ≠ N P jest prawdą. Nie wiemy na pewno, czy P = N P jest również prawdą, a zatem czy można udowodnić, że P = N P również jest pokonana barierą?
2
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 i P ≠ N P . Myślę, że odpowiedź brzmi: naturalne dowody wydają się nie mieć zastosowania, ale algebrizacja i relatywizacja wciąż mają zastosowanie.
—
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.
—
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