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

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 $DNF$ które są zadowalające przez pewne przypisanie zmiennych. Pokaż, czy $DNFSAT$ jest w NP-Complete.

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.

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.$\neq$$Q$$Q$
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$$\neq$

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.$\neq$$\neq$

Dzięki niedeterministycznej hierarchii czasu możesz wykazać, że problemem jest twardy; jak N P ≠ N 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 .$\mathsf {NEXP}$$\mathsf {NP} \ne \mathsf {NEXP}$$\mathsf {NP}$$\mathsf {NP}$

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 P ≠ N P .$\mathsf {NP}$ $\mathsf {NP}$$\mathsf {NP}$$\mathsf P \ne \mathsf {NP}$

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.

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!