Pytania otagowane jako np-hardness

Pytania dotyczące twardości NP i kompletności NP.

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
Języki kompletne i wrażliwe na kontekst.
Interesują mnie dwa pytania dotyczące języków kontekstowych (CSL) i kompletności: Czy istnieje pojęcie kompletności CSL i które języki są kompletne? Czy istnieją naturalne CSL, które są NP-kompletne? W przypadku 2. z pewnością mogę myśleć o naturalnych językach NP-zupełnych, które są CSL (ponieważ CSL jest równy NSPACE [nnn ], SAT to …
1
Ważność potęgowania w wielomianowym skrócie czasu
Zadałem to pytanie 10 dni temu na cs.stackexchange tutaj, ale nie miałem żadnej odpowiedzi. W bardzo słynnego papieru (w środowisku sieciowym), Wang i Crowcroft przedstawić kilka -completeness wyniki obliczeń ścieżki pod kilkoma dodatkami / multyplikatywnych ograniczeń. Pierwszy problem jest następujący:NPNP\mathsf{NP} Biorąc pod uwagę ukierunkowany wykres i dwie miary wagi w …
1
Ranking trudności trudnych problemów NP w praktyce
To pytanie jest ściśle związane z innym postem: Przejścia fazowe w trudnych problemach NP, ale jest nieco inne. Chociaż pytanie dotyczy twardości poszczególnych przypadków trudnych problemów NP, chodzi o uszeregowanie trudności tych samych przypadków. Istnieje wiele bibliografii na temat efektu znanego jako Przejście Fazowe . W szczególności w przypadku losowych …
3
Wyprzedaż Boba (zmiana kolejności par z ograniczeniami w celu zminimalizowania sumy produktów)
Jakiś czas temu zadałem to pytanie na temat Przepełnienia stosu: Problem: sprzedaż Boba . Ktoś zasugerował także opublikowanie pytania tutaj. Ktoś już zadał tutaj pytanie związane z tym problemem - minimalna waga lasów danej liczności - ale o ile rozumiem, nie pomaga mi to z moim problemem. Warto również przyjrzeć …
3
Złożoność kolorowania krawędzi na wykresach płaskich
3 krawędzi barwienia wykresów sześcienny -Complete. Twierdzenie o czterech kolorach jest równoważne z tym, że „Każdy sześcienny płaski wykres bez mostka ma 3 krawędzie do pokolorowania”.N.P.N.P.NP Jaka jest złożoność 3-krawędziowego kolorowania sześciennych wykresów płaskich? Ponadto, przypuszcza się, że -edge barwiący N P -hard dla płaskich wykresów z maksymalnym stopniu hemibursztynianu …
2
Trudne problemy NP na grafach ekspanderów?
W prezentacji z 2006 r. Zatytułowanej WYKRESY EKSPANDERA - CZY POZOSTAJĄ ŻADNE TAJEMNICE? Nati Linial postawił następujący otwarty problem: Które -hard obliczeniowa problemu na wykresie pozostają trudne, gdy ogranicza się do wykresów ekspandera?NPNPNP Od tego czasu postęp poczyniono udowodnić taki wynik dla -hard problemu?NPNPNP
1
NP-Kompletne problemy, które dopuszczają wydajny algorytm pod obietnicą unikalnego rozwiązania
Niedawno czytałem bardzo fajny artykuł Valianta i Vazirani, który pokazuje, że jeśli , to nie może być skutecznego algorytmu do rozwiązania SAT, nawet pod obietnicą, że jest albo niezadowalający, albo ma unikalne rozwiązanie. W ten sposób pokazując, że SAT nie dopuszcza wydajnego algorytmu nawet pod obietnicą istnienia co najwyżej jednego …
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.