Jak udowodnić, że problem NIE jest NP-Complete?


17

Czy istnieje jakaś ogólna technika dla udowodnienia, że ​​problem NIE jest NP-Complete?

Dostałem to pytanie na egzaminie, które poprosiło mnie o wykazanie, czy jakiś problem (patrz poniżej) jest NP-Complete. Nie mogłem wymyślić żadnego prawdziwego rozwiązania, a właśnie udowodniłem, że było w P. Oczywiście nie jest to prawdziwa odpowiedź.

NP-Complete jest zdefiniowany jako zestaw problemów, które są w NP, i wszystkie problemy NP mogą być do niego zredukowane. Tak więc każdy dowód powinien być sprzeczny z przynajmniej jednym z tych dwóch warunków. Ten konkretny problem dotyczy rzeczywiście P (a zatem NP). Utknąłem więc w udowodnieniu, że w NP jest jakiś problem, którego nie można zredukować do tego problemu. Jak, u licha, można to udowodnić?

Oto konkretny problem, który dostałem na egzaminie:

Niech DNF będzie zbiorem ciągów w rozłącznej postaci normalnej . Niech DNFSAT. będzie językiem ciągów z DNfa które są zadowalające przez pewne przypisanie zmiennych. Pokaż, czy reN.faS.ZAT. jest w NP-Complete.


8
Jeśli można by udowodnić , że DNF-SAT nie jest NP-kompletny, natychmiast oznaczałoby to, że , jak wykazano. Dlatego uważam, że odpowiedź, której szukali, jest dokładnie tym, co dałeś (i prawdopodobnie miałeś domyślnie założyć, że P N P ). Jest to jednak bardzo mylące pytanie. P.N.P.P.N.P.
Shaull,

Masz rację, więc rozumiem, że ten problem jest równoważny problemowi a rozwiązanie jednego z nich rozwiązuje również drugi. P.=N.P.
Bez tytułu

Dlaczego mówisz o udowodnieniu, że DNFSAT jest w P, że „oczywiście nie jest to prawdziwa odpowiedź”?
András Salamon,

5
@ AndrásSalamon Zakłada, że , co jest niepotwierdzonym stwierdzeniem. P.N.P.
Bez tytułu

1
@ Bez tytułu: tak naprawdę nie zakłada P P NP, patrz moja odpowiedź.
András Salamon

Odpowiedzi:


8

Na podstawie komentarzy wydaje się, że chcesz bezwarunkowej odpowiedzi.

Jednak DNF-SAT znajduje się w L, przypisując zmienne do spełnienia pierwszego rozłączenia. Dlatego jeśli jest kompletny NP, to L = NP.

Z drugiej strony, jeśli L = NP, to DNF-SAT jest NP-kompletny przy ograniczeniach przestrzeni logicznej, trywialnie. (W rzeczywistości, jeśli L = NP, to każdy problem w NP jest NP-kompletny przy zmniejszeniu przestrzeni logów.)

Wynika z tego, że L = NP iff DNF-SAT jest NP-kompletny przy zmniejszeniu przestrzeni logicznej.

Dlatego nie możesz obecnie wypowiedzieć się bezwarunkowo, że DNF-SAT nie jest NP-zupełny, jak się wydaje. Nie jest konieczne założenie, że P ≠ NP, ale odpowiedź musi być uzależniona od czegoś, a L is NP jest najsłabszą możliwą hipotezą, która gwarantuje pożądany wynik.


Ciekawy. Tak więc problem ten jest równoważny z problemem . Czy możesz wyjaśnić, dlaczego uważasz, że L N P jest słabym założeniem? L.=N.P.=P.=N.P.doL.N.P.
Bez tytułu

3
Jeśli to ψ jest słabsze niż ϕ . ϕψψϕ
András Salamon

14

Problem NP-zupełny wtedy, gdy jest NP- trudne i w NP. Oznacza to, że musisz obalić jeden z tych dwóch.Q

  1. Przy założeniu, że P NP, można dać czas rozwiązywania algorytm wielomian Q . Rzadziej, przy założeniu, że izomorfizm grafów nie jest NP-trudny, możesz wykazać, że Q jest czasem polimetycznym redukowalnym do izomorfizmu grafów.QQ
  2. Pokazujesz, że nie ma w NP. Jest to trudniejsze i zwykle musisz użyć innych założeń, takich jak brak załamania hierarchii wielomianowej, że NP coNP lub pokazać, że jest to trudne dla innej klasy wyższej niż NP, np. Pokazując, że jest trudne NEXPTIME.Q

Zwykle odpowiedzią jest podanie algorytmu wielomianowego czasu, który byłby najprostszy dla DNF-SAT, ale opiera się on na hipotezie, że P NP. Jednak udowodnienie, że DNF-SAT nie jest NP-kompletne bez żadnych założeń, jak wskazuje Shaull, dowodzi, że P NP, więc jest to nieco trudniejsze.


1
Obie podane przez ciebie techniki opierają się na pewnym nieudowodnionym założeniu. Czy sądzisz, że może istnieć konkretny sposób (bez założeń) rozwiązania tego rodzaju problemu?
Bez tytułu

Aha, i nie miałem na myśli tego konkretnego problemu, ponieważ, jak stwierdził Shaull, problem ten jest nadal otwarty. Miałem ogólnie na myśli wykazanie kompletności coNP.
Bez tytułu

2
@Untitled Prawdopodobnie nie miałeś na myśli kompletności coNP. Jednym ze sposobów wykazania tego jest mój punkt (2), dowodzący, że problem jest NEXPTIME trudny. Wiemy, że NP NEXPTIME, więc to by to udowodniło. Udowodnienie, że problem Q jest trudny NEXPTIME, oznaczałoby zatem, że Q nie może być w NP, a zatem nie może być NP-zupełny. QQ
Pål GD

10

Dzięki niedeterministycznej hierarchii czasu możesz wykazać, że problemem jest twardy; jak N PN E X, P , to jest możliwe, w celu zmniejszenia tego problemu w wielomian czasie do problemów w N P , więc problem nie będzie N P .NEXPNPNEXPNPNP

Jednakże, jeśli problem nie jest aż takie trudne, może być do muru, aby udowodnić, że nie jest w ; a jeśli jest w N P , będziesz do muru, aby pokazać, że N P nie jest Karp-sprowadzić do problemu bez zakładając, że PN P .NP NPNPPNP


0

Podobnie jak w przypadku wszystkich dowodów, nie ma formuły na potwierdzenie oświadczenia, musisz wykonać pewne inteligentne domysły, próby i błędy i mam nadzieję, że będziesz w stanie udowodnić to, co próbujesz udowodnić. Aby udowodnić, że problem NIE JEST kompletny z NP, zaneguj definicję (prawo DeMorgrana), to znaczy udowodnij problem NIE z NP lub udowodnij, że problem NIE jest NP-trudny.


0

Wierzę, że tak naprawdę wykładowca chce, abyś mógł odróżnić problemy występujące w P od problemów, które są NP-zupełne w znaczeniu danego języka. Czy możesz zbudować wydajny algorytm? jeśli tak, to podejrzewa się, że nie jest NP-kompletny, ponieważ nie uważamy, że języki w P są NP-kompletne! w przeciwnym razie nadal musisz udowodnić, że problem jest trudny NP!

zauważmy, że istnieją pewne problemy, których statusu nie znamy, takie jak izomorfizm grafów, faktoring podanej liczby, ... uważamy, że problemy te nie są NP-kompletne, ale nikt nie może tego udowodnić! konkretnie mamy dowody, że izomorfizm grafów nie jest NP-zupełny! innym problemem jest unikalna koniunktura w grze, która, jak podejrzewamy, jest wyjątkowa dla NP, ale nie istnieje żaden dowód! więc podejście, które opisałeś, nie jest pomocne!

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.