Złożoność obliczeniowa/Test 4: Redukcje i zupełność

From Studia Informatyczne

Relacja redukowalności wielomianowej w sensie Karpa \leq_P:

jest zwrotna

jest porządkiem częściowym

jest przechodnia

jest preporządkiem

jest relacją węższą od relacji redukowalności logarytmicznej


Problem NP-zupełny w sensie transformacji wielomianowych:

nie należy do klasy NP

jest równoważny w sensie relacji redukowalności wielomianowej każdemu innemu problemowi NP-zupełnemu

jest problemem NP-zupełnym w sensie transformacji wielomianowych Turinga

jest trudniejszy w sensie redukcji wielomianowych od każdego problemu z klasy P


Niech L \in NP. Świadek przynależności słowa do w języka L:

nie musi być jedyny

może mieć dowolną długość

pozwala zweryfikować przynależność w do L w czasie wielomianowo zależnym od |w|

nie może być świadkiem przynależności innego słowa do języka L


Spośród poniższych zdań wybierz zdania prawdziwe:

obliczenie prawdziwości formuły w koniunkcyjnej postaci normalnej przy ustalonym wartościowaniu jest problemem z P

problem SAT należy do klasy NP

każdy problem z klasy NP można zredukować do problemu SAT za pomocą transformacji logarytmicznej

każdy problem z klasy NP można zredukować do problemu SAT za pomocą transformacji wielomianowej


Wybierz zdania prawdziwe z poniższej listy:

spójność grafu jest własnością definiowalną przy pomocy formuł logicznych pierwszego rzędu

zaprzeczenie własności grafowej definiowalnej za pomocą formuły pierwszego rzędu jest definiowalne przez formułę pierwszego rzędu

jeżeli zaprzeczenie jakiejś własności grafowej definiowalnej za pomocą formuły z ESO nie jest definiowalne za pomocą formuły z ESO to P \neq NP

niespójność grafu jest własnością definiowalną przy pomocy formuł logicznych pierwszego rzędu

nie wiadomo, czy sprawdzanie prawdziwości ustalonej formuły pierwszego rzędu dla wejściowych grafów jest problemem z klasy NP


Twierdzenie Fagina

każdemu problemowi z klasy NP można przypisać odpowiadającą mu formułę z ESO

w dowodzie twierdzenia Fagina konstruujemy osobną formułę logiczną dla każdego słowa z rozpatrywanego języka

każdej formule z ESO można przypisać odpowiadający jej problem z klasy NP