Dlaczego informatycy w ogóle pracują przy założeniu, że P ≠ NP?


12

Jadąc od tła matematyki, wydaje mi się, że interesujący na całego komputera naukowcy mają tendencję do pracy przy założeniu, że PNP . Chociaż nie ma żadnego dowodu w obu przypadkach, chyba że coś może być szczególnie niepotwierdzone zarówno w matematyce, jak i nauce, jest podejmowane z dużą ilością siły. Wydaje mi się, że przez lata ludzie próbowali obalić P=NP , fakt, że nie znaleziono jeszcze żadnego dowodu, przynajmniej doprowadziłby niektórych informatyków do pracy w zakresie parametrów oglądania P=NPjak prawdopodobnie prawda. Jednak często widzę, że ludzie pracujący w ramach tego nie są prawdą i zastanawiałem się, dlaczego? Bardziej konserwatywne wydaje się założenie, że P=NP w wielu dziedzinach. Czytałem niezliczone artykuły na temat tego, ile dziedzin informatyki i pól przyległych do CS musiałoby zmienić wiele ze swojej obecnej metodologii, gdyby P=NP okazało się prawdą, więc dlaczego tego nie założono? Chociaż jest mało prawdopodobne, aby w jakikolwiek sposób zostało to udowodnione w najbliższym czasie, wydaje się to dość dziwne polegać tak mocno na takiej hipotezie. Wydaje się, że niemal najważniejsze jest założenie, że domysł Goldbacha jest nieważny, ponieważ nie ma na to dowodów.


8
Hipoteza Goldbacha nie jest poprawną analogią. Dlaczego teoretycy liczb działają przy założeniu, że hipoteza Riemanna jest prawdziwa?
Peter Shor

2
Nie są to przypadkowe opinie oparte wyłącznie na fakcie, że nikt niczego nie obalił; są świadomymi opiniami. Nikt nie obalił istnienia rzutowej płaszczyzny rzędu 12, ale prawie wszyscy myślą, że ona nie istnieje.
Peter Shor,

6
@AJ „jeśli kłócisz się inaczej, zostaniesz nazwany szalonym” ... jeśli miałbyś interesujący argument, to moim zdaniem nie byłoby to szalone. To byłoby bardzo ważne. W kilku przypadkach, w których badacze przyjęli coś podobnego do P = NP, byliśmy w stanie wyciągnąć sprzeczność. Np. Kompromisy czasoprzestrzenne dla SAT. (Uwaga: obecne pytanie, o którym mowa, nie jest ciekawym argumentem. Twierdzi, że P = NP jest bardziej konserwatywnym założeniem, bez podania powodów.)
Ryan Williams

3
W pewnym sensie, jeśli założymy, że P = NP, to duża część pola byłaby właśnie zamknięta. Nigdy więcej twardości aproksymacji, jednoznacznych konstrukcji, niektórych prymitywów kryptograficznych. Gdyby to była prawda, jakie inne interesujące pytania moglibyśmy zadać?
Igor Shinkar

11
Nie sądzę, żeby OP poważnie odrobił pracę domową w tym pytaniu. Jest to omówione w wielu miejscach . Zobacz na przykład rjlipton.wordpress.com/2009/09/18/… , scottaaronson.com/blog/?p=1720 , linki, które podał Domotor, dowolną książkę na temat teorii złożoności ..
Sasho Nikolov

Odpowiedzi:


13

Zasadniczo w przypadku każdego nierozwiązanego problemu ludzie mają skłonność do domniemania zdania rozpoczynającego się od uniwersalnego kwantyfikatora - ponieważ jeśli zacznie się od kwantyfikatora egzystencjalnego, można oczekiwać znalezienia rozwiązania. Poza tym ten temat był omawiany w kilku innych miejscach, patrz https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP lub https://rjlipton.wordpress.com/conventional-wisdom -i-pnp / .

Aktualizacja: lub najnowszy rozdział 3 tutaj: http://www.scottaaronson.com/papers/pnp.pdf


P=NPLLPLNPAAAwwSATLLPLP

@Mikhail: Rzeczywiście! Nie jestem pewien, jak można sformalizować, którą opcję wybrać.
domotorp

1
LAA

3
Istnieje wiele wyjątków. Zanim udowodniono istnienie grupy potworów, była to hipoteza, która rozpoczęła się od egzystencjalnego kwantyfikatora. W przypadku jednego z problemów Gliny (Yang-Millsa) przypuszczalny wynik zaczyna się od egzystencjalnego kwantyfikatora.
Peter Shor


0

PNPPNPP=NP

P=NPP=BPPPNPP=NP

Sprawdź także status światów Impagliazzo?

Russel wygłosił przemówienie na warsztatach IAS na temat swoich światów w 2009 r. ( Wideo ).


-1

Zasadniczo w przypadku każdego nierozwiązanego problemu ludzie mają skłonność do domniemania zdania rozpoczynającego się od uniwersalnego kwantyfikatora - ponieważ jeśli zacznie się od kwantyfikatora egzystencjalnego, można oczekiwać znalezienia rozwiązania.

Π10Π20PNPP=NPF(NPcoNP)PNP

Czytałem niezliczone artykuły na temat tego, ile dziedzin informatyki i pól sąsiadujących z CS musiałoby wiele zmienić w swojej obecnej metodologii, gdyby P = NP okazało się prawdą, więc dlaczego tego nie założono?

P=NPP=NPPNP

f(n)=O(g(n))f(n)g(n)limnf(n)g(n)=1f(n)g(n)lim supnf(n)g(n)1twierdzenie główne sformułowane jest w kategoriach i nie jest jasne, jak skomplikowane byłyby w kategoriach (lub czy takie sformułowanie byłoby w ogóle przydatne).f(n)=O(g(n))f(n)g(n)


1
Jednym z uzasadnień notacji wielkiej oh w wielu jednolitych modelach maszyn jest to, że stałe nie są odporne na model. Na przykład zobacz twierdzenie o przyspieszeniu liniowym. (A potem myślę, że nadal używamy big-oh w modelach niejednorodnych, ponieważ faktycznie używamy ich, aby zrozumieć modele jednolite ...)
Joshua Grochow

@JoshuaGrochow Nawet tak duża notacja może zapraszać do niewłaściwego użycia , nie sądzę, że wymaga to wiele uzasadnienia. Często zwięźle wyraża dokładnie to, co chcemy powiedzieć. Właśnie próbowałem znaleźć podobnie zwięzłe oznaczenia dla sytuacji, w których moglibyśmy być bardziej jednoznaczni. (Gdy odnosimy się do dowodu zamiast twierdzenia, to jest to typowa sytuacja, w której prawdopodobnie powinniśmy być bardziej jednoznaczni. Wynika to z wyjaśnień, w jaki sposób konstruktywna / intuicyjna logika może być pomocna.)
Thomas Klimpel
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.