NP oznacza niedeterministyczny czas wielomianowy.
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...
Interesuje mnie naturalne uogólnienie słynnej 15-puzzli , w których musisz przesuwać bloki, dopóki nie posortujesz wszystkich podanych liczb (zwykle jest przerwa 1 blok). Teraz uogólnieniem byłoby zwiększenie rozmiaru układanki z 15 do , gdzie jedno pole jest wolne. Stworzyłem małą ilustrację...
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} =...
Pytanie dotyczące teorii „ Co to jest NP ograniczony do świadków wielkości liniowej? ” Dotyczy klasy NP ograniczonej do świadków wielkości liniowej , aleO ( n )O(n)O(n) Czy istnieją naturalne problemy NP-zupełne, w których (tak) przypadki wielkości wymagają świadków o rozmiarze większym niż n...
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 =
Edycja : Jak Ravi Boppana słusznie wskazał w swojej odpowiedzi, a Scott Aaronson dodał również inny przykład w swojej odpowiedzi , odpowiedź na to pytanie okazała się „tak” w sposób, którego w ogóle się nie spodziewałam. Najpierw pomyślałem, że nie odpowiedzieli na pytanie, które chciałem zadać,...
Peter Shor pokazał, że dwa z najważniejszych problemów pośrednich NP, faktoring i dyskretny log, są w BQP. Natomiast najbardziej znany algorytm kwantowy dla SAT (poszukiwanie Grovera) zapewnia jedynie kwadratową poprawę w porównaniu z klasycznym algorytmem, co sugeruje, że problemy z całkowitą NP...
To pytanie zostało przeniesione z Computer Science Stack Exchange, ponieważ można na nie odpowiedzieć na Theoretical Computer Science Stack Exchange. Migrował 6 lat temu . Wydaje się, że wiele osób uważa, że , po części dlatego, że wierzą, że faktoring nie jest możliwy do...
Czy jest przykładem języka, który jest w NPNPNP , ale gdzie nie możemy udowodnić ten fakt bezpośrednio poprzez pokazanie, że istnieje wielomian świadka do członkostwa w tym języku? Zamiast tego fakt, że język znajduje się w NPNPNP , można udowodnić, redukując go do innego języka w NPNPNP , gdzie...
Czy występują jakieś naturalne problemy w , które nie są (wiadomo, że są / sądzi się, że są) w U P ∩ c o U P ?N.P.∩ c o NP.NP∩coNPNP \cap coNPUP.∩ c o UP.UP∩coUPUP \cap coUP Oczywiście wielki każdy wie o w jest wersja decyzja faktoringu (czy n mają współczynnik wielkości co najwyżej k), ale to...
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...
Czy istnieje (najlepiej naturalny) NP-pełny język L⊆{0,1}∗L⊆{0,1}∗L\subseteq \{0,1\}^* , taki, że dla każdego n≥1n≥1n\geq 1 |L∩{0,1}n|=2n−1|L∩{0,1}n|=2n−1|L\cap \{0,1\}^n|=2^{n-1} trzyma? Innymi słowy, LLL zawiera dokładnie połowę wszystkich nnn bitowych...
Jest to związane z pytaniem Czy rozmiar członkostwa świadka dla każdego języka NP jest już znany? Niektóre naturalne problemy (-kompletne) mają świadków o długości liniowej: zadowalające przypisanie dla , ciąg wierzchołków dla itp.NPNP\mathsf{NP}SATSATSATHAMPATHHAMPATHHAMPATH Rozważ klasę...
Dostęp do wyroczni zapewniłby duże, super-wielomianowe przyspieszenie wszystkiego w N P - P (zakładając, że zestaw nie jest pusty). Nie jest jednak jasne, ile P skorzystałby z tego dostępu do wyroczni. Oczywiście przyspieszenie w P nie może być wielomianowe, ale nadal może być wielomianowe. Na...
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...