Pytania oznaczone «p-hardness»

128
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...

55
Dlaczego 2SAT w P?

Natknąłem się na algorytm wielomianowy, który rozwiązuje 2SAT. Uważam za zaskakujące, że 2SAT znajduje się w P, gdzie wszystkie (lub wiele innych) instancji SAT są NP-Complete. Co wyróżnia ten problem? Co sprawia, że ​​jest to takie proste (NL-Complete - nawet łatwiejsze niż...

47
Trudne problemy z NP na drzewach

Kilka problemów optymalizacyjnych, o których wiadomo, że są trudne do NP na grafach ogólnych, można w prosty sposób rozwiązać w czasie wielomianowym (niektóre nawet w czasie liniowym), gdy grafem wejściowym jest drzewo. Przykłady obejmują minimalną osłonę wierzchołków, maksymalny niezależny zestaw,...

45
Kompletny wariant faktoringu NP.

Książka Arory i Baraka przedstawia faktoring jako następujący problem: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\} Dodają, w dalszej części...

34
Codzienne problemy z NP-zupełnymi problemami

Mark Dominus zebrał kilka przykładów redukcji czasu wielomianowego od różnych trudnych problemów NP do dopasowania „wyrażenia regularnego” . Wyobrażanie sobie weryfikacji w czasie wielomianowym nie jest ogromnym skokiem. Jak zilustrujesz klasę NP-zupełną studentom lub przyjaciołom z innych...

33
Odniesienie do twardości NP 3-zabarwienia?

Mam pytanie historyczne. Próbuję ustalić odniesienie dla faktu, że 3-kolorowalność grafów (alternatywnie, kolorowalność dla danego k ≥ 3 ) jest NP-trudna.kkkk ≥ 3k≥3k\geq 3 Kuszącą odpowiedzią jest „oryginał Karpa”, ale to nieprawda. Oto skan: Reducibility Among Combinatorial Problems, Karp...