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 będzie zbiorem ciągów w rozłącznej postaci normalnej . Niech będzie językiem ciągów z które są zadowalające przez pewne przypisanie zmiennych. Pokaż, czy jest w NP-Complete.