Pytania dotyczące lub związane z P vs. NP
To moje pierwsze pytanie na tej stronie. Biorę kurs magisterski z teorii obliczeń. Jak wytłumaczysz problem P = NP 10-letniemu dziecku i dlaczego ma on taką nagrodę pieniężną? Twoje zdanie? Zaktualizuję pytanie, gdy moja głowa się o tym
Czasami twierdzi się, że teoria złożoności geometrycznej Ketana Mulmuleya jest jedynym wiarygodnym programem do rozstrzygania otwartych pytań teorii złożoności, takich jak pytanie P vs. NP. Było wiele pozytywnych komentarzy od słynnych teoretyków złożoności na temat programu. Według Mulmuleya...
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 .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}P≠NPP≠NP\mathsf{P} \neq \mathsf{NP} Więc moje pytanie brzmi: Dopóki hipoteza nie zostanie udowodniona, czy można /...
Twierdzenie Ladnera dobrze wie, że jeśli , wówczas istnieje nieskończenie wiele pośrednich ( ). Istnieją również naturalni kandydaci do tego statusu, tacy jak Graph Isomorphism i wiele innych, patrz Problemy między P i NPC . Niemniej jednak ogromna większość w tłumie znanych jest znana z lub ....
Przypuszcza się, że ponieważ odwrotność oznaczałaby . Twierdzenie Ladnera stwierdza, że jeśli a następnie . Wydaje się jednak, że dowód nie uogólnia na więc możliwość ie wydaje się otwarty.NP⊈P/polyNP⊈P/poly\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}PH=Σ2PH=Σ2\mathsf{PH} =...
Czy są jakieś przykłady zabawek, które zapewniają „niezbędny” wgląd w trzy znane bariery dla problemu - relatywizacja, dowody naturalne i algebryzacja?P=NPP=NPP =
Ta odpowiedź na główne nierozwiązane problemy w informatyce teoretycznej? pytanie stwierdza, że jest otwarte, jeśli określony problem w NP wymaga czasu .Ω ( n2))Ω(n2)\Omega(n^2) Patrząc na komentarze pod odpowiedzią, zastanawiałem się: Oprócz paddingu i podobnych sztuczek, jaka jest...
Powszechnie wiadomo, że każdy dowód rozwiązujący pytanie P vs NP musi pokonać relatywizację , dowody naturalne i bariery algebrizacyjne . Poniższy schemat dzieli „przestrzeń próbną” na różne regiony. Na przykład RNRNRN odpowiada zestawowi dowodów relatywizujących i naturalizujących. GCTGCTGCT...
To jest pytanie otwarte, za co z góry przepraszam. Czy istnieją przykłady zdań, które (pozornie) nie mają nic wspólnego ze złożonością lub maszynami Turinga, ale odpowiedź na które sugerowałaby ?P≠NPP≠NP\mathbf{P}\neq
Czytałem „ Czy P w porównaniu z NP jest formalnie niezależny? ”, Ale mnie to zaskoczyło. Uważa się, że w teorii złożoności . Moje pytanie dotyczy tego, co jeśli nie da się tego udowodnić (powiedzmy w Z F C ). (Załóżmy, że dowiadujemy się tylko, że P ≠ N P jest niezależny od Z F C, ale nie ma...
Czy istnieje znany, wyraźny przykład algorytmu o takiej właściwości, że jeśli to ten algorytm nie działa w czasie wielomianowym, a jeśli to działa w czasie wielomianowym?P≠NPP≠NPP\neq
Słynny Izomorfizm Conjecture od Bermana i Hartmanis mówi, że wszystkie językach -Complete są wielomian czas izomorficzne (p-izomorficzny) do siebie. Kluczem znaczenie przypuszczeniem jest, że implikuje P ≠ N P . Została opublikowana w 1977 roku, a kawałek dowody potwierdzające, że wszystkie N P...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
Interesuje mnie nauka powiązań między „chaosem”, a szerzej, systemami dynamicznymi, a pytaniem . Oto przykład rodzaju literatury, której szukam:P.= NP.P.=N.P.P{=}NP Ercsey-Ravasz, Mária i Zoltán Toroczkai. „Twardość optymalizacji jako przejściowy chaos w analogicznym podejściu do satysfakcji z...
Myślę, że dobrym pomysłem byłoby sporządzenie listy twierdzeń stwierdzających, że P nie jest równe NP wtedy i tylko wtedy, gdy takie i takie wyjścia, pewna klasa złożoności jest zawarta w innej klasie złożoności i tak dalej.
Gowers przedstawił ostatnio problem, który nazywa „dyskretną determinacją Borela”, którego rozwiązanie dotyczy dolnych granic obwodu dowodzenia. Czy możesz podać podsumowanie podejścia, które jest dostosowane do grupy teoretyków złożoności? Co potrzeba, aby to podejście wykazało cokolwiek , w tym...
Wszyscy wiemy, że pokazanie ma bariery. Wszyscy badaliśmy te bariery, ponieważ uważamy, że P ≠ N P.P≠NPP≠NPP\ne NPP≠NPP≠NPP\ne NP . 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...
Jak rozumiem, dowód, że P = NP lub P ≠ NP musiałby być nierelatywny (jak w wyroczniach teorii rekurencji). Praktycznie wszystkie dowody wydają się być relatywne. Jakie są dobre przykłady spoza relativizable dowodów, w tym rodzaju, że P = NP / P ≠ NP dowód musiałby być, że nie są błahe albo...
w 1979 r. Hopcroft / Ullman napisał, że L ⊆ P ⊆ NP ⊆ PSpace jest znany, ale L ⊊ PSpace jest jedynym właściwym (i trywialnym) zabezpieczeniem znanym, chociaż wszystkie są przypuszczane, że są odpowiednimi zabezpieczeniami i „tam, gdzie rzeczy nadal istnieją” ~ 4 dekady później . od tego czasu...
W poniższym pytaniu wykorzystano pomysły z kryptografii zastosowane w teorii złożoności. To powiedziawszy, jest to pytanie teoretycznie złożone, i aby odpowiedzieć na to pytanie, nie jest wymagana żadna wiedza kryptograficzna. Celowo piszę to pytanie bardzo nieformalnie. Brakuje szczegółów,...