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 .
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ć?
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 . W tym sensie można uznać za coś w rodzaju . Powrót do wyników z fizyki w TCS? :
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)?
Odpowiedzi:
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
Jestem pewien, że Strassen rozmawiał z czystymi matematykami, którzy powiedzieli coś podobnego
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.≠
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):≠
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 ...”.
źródło
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≠P
2) Czy zasada wykracza poza jej wąskie znaczenie matematyczne?NP≠P
3) Czy zasadę można uznać za prawo fizyczne.NP≠P
Myślę, że istnieją dobre powody, aby odpowiedzieć „tak” lub „kwalifikowane tak” na wszystkie te trzy pytania.
źródło
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)
źródło
Aby odpowiedzieć na pierwotne pytanie:
Tak, przynajmniej Scott Aaronson w to wierzyP.≠ N.P. 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
źródło
First of all is the known weaker resultNL≠PSPACE or the stronger conjecture NP≠coNP possible laws of nature? Then we can ask questions about if P≠NP is a law of nature.
źródło
The statement P≠NP can encoded as a statementϕ about natural numbers. Since ϕ 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.
źródło
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.
źródło