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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Relacja redukowalności wielomianowej w sensie Karpa :

jest zwrotna

jest porządkiem częściowym

jest przechodnia

jest preporządkiem

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


Problem -zupełny w sensie transformacji wielomianowych:

nie należy do klasy

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

jest problemem -zupełnym w sensie transformacji wielomianowych Turinga

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


Niech . Świadek przynależności słowa do języka :

nie musi być jedyny

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

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

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


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

problem należy do klasy

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

każdy problem z klasy można zredukować do problemu 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 nie jest definiowalne za pomocą formuły z to

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


Twierdzenie Fagina

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

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

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