Pytania otagowane jako np-intermediate

28
Problemy między P a NPC
Rozkładanie na czynniki i izomorfizm wykresów są problemami w NP, o których nie wiadomo, że są w P ani w NP-kompletne. Jakie są inne (wystarczająco różne) naturalne problemy, które dzielą tę właściwość? Sztuczne przykłady pochodzące bezpośrednio z dowodu twierdzenia Ladnera się nie liczą. Czy którykolwiek z tych przykładów może być …
4
Uogólnione twierdzenie Ladnera
Twierdzenie Ladnera stwierdza, że ​​jeśli P ≠ NP, to istnieje nieskończona hierarchia klas złożoności ściśle zawierających P i ściśle zawartych w NP. Dowód wykorzystuje kompletność SAT przy wielu redukcjach NP. Hierarchia zawiera klasy złożoności skonstruowane przez rodzaj diagonalizacji, z których każda zawiera pewien język, do którego języków w niższych klasach …
3
Techniki pokazujące, że problemem jest twardość „otchłani”
Biorąc pod uwagę nowy problem w którego prawdziwa złożoność jest gdzieś pomiędzy P a ukończeniem NP, istnieją dwie metody, o których wiem, że mogą być wykorzystane do udowodnienia, że ​​rozwiązanie tego jest trudne:N P.N.P.\mathsf{NP}P.P.\mathsf{P} Pokaż, że problem dotyczy GI (GI = Graph Isomorphism) Pokazują, że problem w . Według znanych …
3
Czy NPI jest zawarty w P / poly?
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} = \Sigma_2P≠NPP≠NP\mathsf{P} \ne \mathsf{NP}NPI:=NP∖(NPC∪P)≠∅NPI:=NP∖(NPC∪P)≠∅\mathsf{NPI} := \mathsf{NP} \setminus(\mathsf{NPC} \cup \mathsf{P}) \ne \emptysetP/polyP/poly\mathsf{P}/\text{poly}NPI⊂P/polyNPI⊂P/poly\mathsf{NPI} \subset \mathsf{P}/\text{poly}NP⊂NPC∪P/polyNP⊂NPC∪P/poly\mathsf{NP} \subset \mathsf{NPC} \cup \mathsf{P}/\text{poly} Zakładając, że …
2
Problemy pośrednie NP z efektywnymi rozwiązaniami kwantowymi
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 są wciąż trudne do rozwiązania na komputerach kwantowych. …
6
Czy istnieje naturalny problem w czasie quasi-wielomianowym, ale nie w czasie wielomianowym?
László Babai niedawno udowodnił, że problem z izomorfizmem grafowym występuje w quasipolomomialnym czasie . Zobacz także jego przemówienie na Uniwersytecie w Chicago, notatkę z przemówień Jeremy Kun GLL post 1 , GLL post 2 , GLL post 3 . Zgodnie z twierdzeniem LADNER, o ile P.≠NP.P≠N.P.P \neq NP , a …
1
Naturalni kandydaci do hierarchii wewnątrz NPI
Załóżmy, że . N P ja to klasa problemów w N P , które nie są ani w P ani w N P -hard. Listę problemów, które można przypuszczać, że są N P I tutaj .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}NPINPI\mathsf{NPI}NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}NPINPI\mathsf{NPI} Twierdzenie Ladnera mówi nam, że jeśli to istnieje nieskończona hierarchia problemów N …
1
Czy występują problemy z „NP-Intermediate-Complete”?
Załóżmy, że P NP.≠≠\ne Twierdzenie Ladnera mówi, że istnieją problemy pośrednie NP (problemy w NP, które nie są ani w P, ani w NP-Complete). Znalazłem w Internecie kilka zawoalowanych odniesień, które sugerują (myślę), że istnieje wiele „poziomów” wzajemnie redukowalnych języków w ramach NPI, które zdecydowanie nie wszystkie się zlewają. Mam …
1
Czy różni się od ?
Czy możemy udowodnić, że dla każdego języka który nie jest -hard (zakłada to ), ? Alternatywnie, czy można to udowodnić przy jakichkolwiek uzasadnionych założeniach?L∈NPL∈NPL\in\mathsf{NP}NPNP\mathsf{NP}P≠NPP≠NP\mathsf P \ne \mathsf{NP}PL≠PSATPL≠PSAT\mathsf{P}^L \ne \mathsf{P}^{\text{SAT}}
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.