Pytania otagowane jako np-hardness

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

2
Hamiltoniczność wykresów k-regularnych
Wiadomo, że NP-kompletne jest sprawdzenie, czy cykl hamiltonowski istnieje na 3-regularnym wykresie, nawet jeśli jest on płaski (Garey, Johnson i Tarjan, SIAM J. Comput. 1976) lub dwustronny (Akiyama, Nishizeki, i Saito, J. Inform. Proc. 1980) lub w celu przetestowania, czy cykl hamiltonowski istnieje na wykresie 4-regularnym, nawet jeśli jest to …
6
Czy występują problemy NP-zupełne z rozwiązaniami wielomianowego oczekiwanego czasu?
Czy są jakieś problemy z NP-zupełnością, dla których znany jest algorytm, że oczekiwany czas działania jest wielomianowy (dla pewnego rozsądnego rozkładu między instancjami)? Jeśli nie, to czy istnieją problemy, dla których ustalono istnienie takiego algorytmu? Czy istnienie takiego algorytmu sugeruje istnienie deterministycznego wielomianowego algorytmu czasu?
1
Czy nadal jest możliwe określenie złożoności obliczania szerokości wykresów płaskich?
Dla stałej można określić w czasie liniowym, biorąc pod uwagę wykres wejściowy G , czy jego szerokość wynosi ≤ k . Jednakże, gdy zarówno k jak i G są podane jako dane wejściowe, problem jest trudny NP. ( Źródło ).k∈Nk∈Nk \in \mathbb{N}GGG≤k≤k\leq kkkkGGG Jednak gdy wykres wejściowy jest płaski , …
1
Chcę, aby prosty gadżet udowodnił, że cyklarny plan Hamiltonian NP-Complete (od cyklu Hamiltonian)
Wiadomo, że cykl hamiltonowski (w skrócie szynka) jest zakończony NP, a cykl szynki Planar jest zakończony NP. Dowód na cykl szynkowy nie pochodzi z cyklu szynkowego. Czy jest fajny gadżet, który, biorąc pod uwagę wykres G, zastąpi wszystkie skrzyżowania jakimś płaskim gadżetem, dzięki czemu masz płaski wykres G 'taki, że …
2
Naturalna redukcja CLIQUE do k-Color
Widoczna jest redukcja z CLIQUE na k-Color, ponieważ oba są NP-Complete. W rzeczywistości mogę go zbudować, tworząc redukcję z CLIQUE do 3-SAT z redukcją z 3-SAT do k-Color. Zastanawiam się, czy istnieje rozsądna bezpośrednia redukcja między tymi problemami. Powiedzmy, redukcję, którą mógłbym wyjaśnić przyjacielowi dość krótko, bez potrzeby opisywania języka …
5
Pakowanie prostokątów w wypukłe wielokąty, ale bez rotacji
Interesuje mnie problem pakowania identycznych kopii (2-wymiarowych) prostokątów w wypukły (2-wymiarowy) wielokąt bez nakładania się. W moim problemie nie wolno obracać prostokątów i można założyć, że są one ustawione równolegle do osi. Właśnie podano wymiary prostokąta i wierzchołki wielokąta i zapytano, ile identycznych kopii prostokąta można upakować w wielokącie. Uważam, …
2
Testowanie, czy litery można zaplanować, aby uzyskać słowo w zwykłym języku
I ustalić język regularny na alfabetem , i rozważmy następujący problem, który ja nazywam się harmonogram dla . Nieoficjalnie, dane wejściowe dają mi liter i odstępy dla każdej litery (tj. Minimalną i maksymalną pozycję), a moim celem jest umieszczenie każdej litery w tym przedziale, tak aby żadne dwie litery nie …
1
Tardos Funkcja kontrprzykład do Bluma
W tym wątku próba próby Norbet Bluma jest zwięźle obalona przez odnotowanie, że funkcja Tardos jest przeciwne do Twierdzenia 6.P.≠ N.P.P≠NPP \neq NP Twierdzenie 6 : Niech będzie dowolną monotoniczną funkcją boolowską. Załóżmy, że istnieje aproksymator A CNF-DNF, którego można użyć do udowodnienia dolnej granicy C m ( f ) …
10
Problemy łatwe w przypadku wykresów nieważonych, ale trudne w przypadku wykresów ważonych
Wiele problemów związanych z grafem algorytmicznym można rozwiązać w czasie wielomianowym zarówno na wykresach nieważonych, jak i ważonych. Niektóre przykłady to najkrótsza ścieżka, min. Drzewo rozpinające, najdłuższa ścieżka (w ukierunkowanych grafach acyklicznych), maksymalny przepływ, min. Cięcie, maks. Dopasowanie, optymalne arborescencje, niektóre najgęstsze problemy z podgrafami, maks. Rozłączne nacięcia ukierunkowane, maks. …
1
Czy istnieje problem, który jest łatwy w przypadku wykresu sześciennego, ale trudny w przypadku wykresów o maksymalnym stopniu 3?
Wykresy sześcienne to wykresy, w których każdy wierzchołek ma stopień 3. Zostały one szeroko zbadane i jestem świadomy, że kilka problemów trudnych dla NP pozostaje trudnych dla NP nawet ograniczonych do podklas grafów sześciennych, ale niektóre inne stają się łatwiejsze. Nadklasą wykresów sześciennych jest klasa grafów o maksymalnym stopniu .Æ …
2
Zależność między trudnością rozpoznawania klasy grafowej a zakazaną charakterystyką subgrafu
Rozważam klasy grafów, które można scharakteryzować za pomocą zabronionych subgrafów. Jeśli klasa grafów ma skończony zestaw zabronionych podgraphów, wówczas istnieje trywialny algorytm wielomianowego rozpoznawania czasu (można po prostu użyć brutalnej siły). Ale nieskończona rodzina zakazanych subgraphów nie oznacza twardości: istnieją pewne klasy z nieskończoną listą zakazanych subgrafów, tak że rozpoznanie …
1
Czy twardość NP oznacza twardość P?
Jeśli problem jest trudny dla NP (przy użyciu wielomianowych redukcji czasu), czy to oznacza, że ​​jest trudny dla P (przy użyciu przestrzeni dziennika lub redukcji NC)? Wydaje się intuicyjne, że jeśli jest tak trudny jak jakikolwiek problem w NP, powinien być tak trudny jak jakikolwiek problem w P, ale nie …
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.