Czy powinniśmy uznać

30

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 .PNPPNP

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ć?PNP

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 fizycznePNP . W tym sensie można uznać za coś w rodzaju . Powrót do wyników z fizyki w TCS? :PNPE=mc2

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)?PNP

vb le
źródło
10
Witryna cstheory.stackexchange.com nie jest odpowiednim miejscem do dyskusji. Proszę sprawdzić „Jakich pytań mam nie pytać tutaj?” W FAQ .
Tsuyoshi Ito
11
Mam nadzieję, że ktoś może mieć właściwą odpowiedź na moje pytanie. Uważam, że punkt widzenia Strassena jest dość interesujący i, co zabawne, nie rozmawialiśmy o tym. Sprawdzę teraz FAQ ...
vb le
8
Pytasz ludzi o zdanie, a nie o fakty, więc moim zdaniem to pytanie jest zdecydowanie nieodpowiednie. Nie musicie się zgodzić, ale mam nadzieję, że moje stanowisko w tej sprawie jest jasne.
Tsuyoshi Ito
30
Myślę, że to pytanie jest dość ważne i że w tym przypadku możemy zrobić wyjątek dla tendencji do unikania dyskusji.
Gil Kalai
3
@Gil Kalai: Jest wiele ważnych rzeczy do omówienia na tym świecie, ale cstheory.stackexchange.com nie jest dla nich właściwym miejscem. Omów je gdzie indziej.
Tsuyoshi Ito

Odpowiedzi:

57

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 ”.

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):

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 ...”.

Peter Shor
źródło
1
„dlaczego nie można po prostu wysunąć trochę wysiłku i udowodnić, że P NP ...” - ale prawdopodobnie ogromny wysiłek został zostały umieszczone fwd odkąd początku przypuszczeń ....
vzn
7
@vzn: właśnie dlatego matematycy, którzy mówili takie rzeczy, byli tak denerwujący.
Peter Shor,
ok, tak, zgodzili się, że matematycy, może nieco niesprawiedliwie, nie rozpoznali P NP jako znaczące matematycznie, a może nawet fundamentalne, do ewentualnych dziesięcioleci później, a nagroda Clay prawdopodobnie miała wiele wspólnego z tym. Interesującym studium przypadku tego jest opisany przez gowersa [medalistę pola ] dowód na monotoniczny obwód razborova . i oczywiście hipoteza riemanna to kolejny problem matematyczny z glinką ... wraz z innymi, głównie matematycznymi ...=?
od
20

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ć?NPP

2) Czy zasada wykracza poza jej wąskie znaczenie matematyczne?NPP

3) Czy zasadę można uznać za prawo fizyczne.NPP

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

Gil Kalai
źródło
11

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)

Suresh Venkat
źródło
Wiem, że przesadzam z cytatem ze Strassen. Obawiam się, że złożoność silnie zależy od pytania P vs NP, podobnie jak fizyka od jego praw (jak wyjaśniłeś). Pytanie brzmi zatem: dopóki hipoteza P vs. NP nie zostanie udowodniona, czy można / należy uznać ją za prawo fizyczne, jak wskazano w Strassen?
wb.
7

Aby odpowiedzieć na pierwotne pytanie:

Tak, przynajmniej Scott Aaronson w to wierzy P.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

Mohammad Al-Turkistany
źródło
13
This is different from the PNP conjecture, although it does imply it.
Peter Shor
7
+1. From one of the conversations i had with a friend , i ended up believeing that the universe would have no reason to exist if P = NP.
labotsirc
2
@labotsirc could you give your reasons?
T....
5

First of all is the known weaker result NLPSPACE or the stronger conjecture NPcoNP possible laws of nature? Then we can ask questions about if PNP is a law of nature.

T....
źródło
From mathematical point your answer makes sense, but the question is not mathematical. I think P vs. NP is a more natural and intuitive question so it is not unreasonable to think that P vs. NP is more suitable as the starting point. At the core I think the issue is not mathematics but how the mathematical models of computation that we have built correspond to the real world and what can be done in it.
Kaveh
1
@Kaveh Why NPcoNP is not more natural? To me this seems to be profoundly as important or even more important than PNP.
T....
1

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.

Thinniyam Srinivasan Ramanatha
źródło
8
Except that we know that if physical laws didn't prevent Blum–Shub–Smale machines from being created in our universe, P and NP would be equivalent. So the question is related to the physical world in that sense.
Kyle Jones
@KyleJones Sorry, I don't understand what you are saying (probably because I don't know enough about BSS model). Could you give me a reference which explains this in more detail?
Thinniyam Srinivasan Ramanatha
I meant that if a mathematical proof of the statement is produced, no evidence from the physical world can disprove it.
Thinniyam Srinivasan Ramanatha
-4

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.

Xoff
źródło
7
Actually, there are still lots of candidates for NP-intermediate problems, whose exact complexity remains unresolved: cstheory.stackexchange.com/questions/79/…
Joshua Grochow
this list is good to know, thanks for this comment !
Xoff