Czy powinniśmy uznać

Wielu ekspertów uważa, że hipoteza jest prawdziwa i wykorzystuje ją w swoich wynikach. Obawiam się, że złożoność silnie zależy od hipotezy .$\mathsf{P} \neq \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Więc moje pytanie brzmi:

Dopóki hipoteza nie zostanie udowodniona, czy można / należy uznać ją za prawo natury, jak wskazano w cytacie ze Strassen? Czy też powinniśmy traktować to jako matematyczne przypuszczenie, które może kiedyś udowodnić lub obalić?$\mathsf{P}\neq\mathsf{NP}$

Zacytować:

„Dowody na korzyść hipotez Cooka i Valianta są tak przytłaczające, a konsekwencje ich niepowodzenia są tak groteskowe, że ich status można porównać do praw fizycznych, a nie zwykłych matematycznych przypuszczeń”.

[Volker Strassena laudation zwycięzcy Nevanlinna nagroda, Leslie G. Valarów w 1986]

Zadaję to pytanie podczas czytania postu Wyniki fizyki w TCS? . Być może warto zauważyć, że złożoność obliczeniowa ma pewne podobieństwa do (teoretycznej) fizyki: wiele ważnych wyników złożoności zostało udowodnionych przy założeniu , podczas gdy w teoretycznych wynikach fizyki udowodniono, zakładając pewne prawa fizyczne$\mathsf{P} \neq \mathsf{NP}$ . W tym sensie można uznać za coś w rodzaju . Powrót do wyników z fizyki w TCS? :$\mathsf{P} \neq \mathsf{NP}$$E = mc^2$

Czy (część) TCS może być gałęzią nauk przyrodniczych?

Wyjaśnienie:

(por. odpowiedź Suresha poniżej)

Czy uzasadnione jest stwierdzenie, że hipoteza w teorii złożoności jest tak fundamentalna jak prawa fizyczne w fizyce teoretycznej (jak powiedział Strassen)?$\mathsf{P}\neq\mathsf{NP}$

Oświadczenie Strassena należy umieścić w kontekście. To był adres do publiczności matematyków w 1986 roku, kiedy wielu matematyków nie miało wysokiej opinii na temat informatyki teoretycznej. Kompletne zestawienie to

Dla niektórych z was może się wydawać, że omawiane tutaj teorie opierają się na słabych podstawach. Oni nie. Dowody na korzyść hipotez Cooka i Valianta są tak przytłaczające, a konsekwencje ich niepowodzenia są tak groteskowe, że ich status może być może porównywany do statusu praw fizycznych, a nie zwykłych matematycznych przypuszczeń.

Jestem pewien, że Strassen rozmawiał z czystymi matematykami, którzy powiedzieli coś podobnego

„Opierasz całą teorię złożoności na domku z kart. Co jeśli P = NP? Wówczas wszystkie twoje twierdzenia będą bez znaczenia. Dlaczego po prostu nie włożysz trochę wysiłku i nie udowodnisz, że P NP, a nie budujcie teorię na tak słabych podstawach ”.$\neq$

W 2013 r., Kiedy P NP od kilkunastu lat stanowi problem z nagrodą gliny, może wydawać się trudne do uwierzenia, że ​​jakikolwiek matematyk rzeczywiście miał takie podejście; Mogę jednak osobiście ręczyć, że niektórzy to zrobili.$\neq$

Strassen kontynuuje, mówiąc, że nie powinniśmy rezygnować z szukania dowodu P NP (co pośrednio sugeruje, że jest to rzeczywiście przypuszczenie matematyczne):$\neq$

Niemniej jednak tradycyjny dowód byłby bardzo interesujący i wydaje mi się, że hipotezę Valianta można łatwiej potwierdzić niż hipotezę Cooka ...

więc może nazwałbym to „hipotezą roboczą”, a nie „prawem fizycznym”.

Na koniec zauważę, że matematycy również stosują takie działające hipotezy. Istnieje wiele artykułów matematycznych potwierdzających twierdzenia, których twierdzenia brzmią: „Zakładając, że hipoteza Riemanna jest prawdziwa, to ...”.

Widzę trzy powiązane sposoby zrozumienia pytania:

1) Czy możemy uznać za podstawową zasadę teorii złożoności obliczeniowej, nawet zanim będziemy w stanie to udowodnić?$NP \ne P$

2) Czy zasada wykracza poza jej wąskie znaczenie matematyczne?$NP \ne P$

3) Czy zasadę można uznać za prawo fizyczne.$NP \ne P$

Myślę, że istnieją dobre powody, aby odpowiedzieć „tak” lub „kwalifikowane tak” na wszystkie te trzy pytania.

Nie jestem pewien, czy rozumiem. Prawo fizyczne (wskazane przez ciebie) jest matematycznym wyrażeniem modelu (w tym przykładzie względności), który twierdzi, że oddaje rzeczywistość. Prawo fizyczne może zostać udowodnione jako błędne, jeśli podstawowa matematyka jest niepoprawna, ale może być również błędne, jeśli zmieni się podstawowy model (na przykład mechanika newtonowska). P vs NP to specyficzne matematyczne przypuszczenie, które jest prawdziwe lub fałszywe (i może być możliwe do udowodnienia lub nie)

Aby odpowiedzieć na pierwotne pytanie:

Tak, przynajmniej Scott Aaronson w to wierzy $P \ne NP$jest prawem natury. Zaproponował następujące sformułowanie

„Założenie o twardości NP ?: Nie ma fizycznych możliwości rozwiązania kompletnych problemów NP w czasie wielomianowym”.

Wygłosił miłą rozmowę na Uniwersytecie w Waterloo, zatytułowaną Nieprzerwalność obliczeniowa jako prawo fizyki

First of all is the known weaker result $NL\neq PSPACE$ or the stronger conjecture $NP\neq coNP$ possible laws of nature? Then we can ask questions about if $P\neq NP$ is a law of nature.

The statement P≠NP can encoded as a statement $\phi$ about natural numbers. Since $\phi$ is either true or false about the naturals, the answer to the question is a purely mathematical one. This is definitely not a physical law which is subject to the nature of the physical world that we live in.

You can do a lots of experiments on speeds and velocities, and you will obtain overwhelming evidence to validate Newton's laws. Of course, you will see some very strange things in very particular experiments, like the speed of light in moving water, or some astronomical events. But your overwhelming pieces of evidence will say to you : Newton is right and those laws are what you need

Of course, Newton "is not right", and Einstein came after him.

For P=NP, we can see a lots of example where it seems P≠NP. But in some particular cases, we have strange things. If P≠NP, there are an infinite number of classes between them, so we should find some problems in NP that are not in P, but are not NP-complete. We don't know any of them, and most candidates were proven to be in P.

What you think about this problem depends on where you want to look at. I would not be surprised if P=NP.