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

Relacja redukowalności wielomianowej w sensie Karpa $\leq _{P}$:

jest zwrotna Dobrze

jest porządkiem częściowym Źle

jest przechodnia Dobrze

jest preporządkiem Dobrze

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

Problem $NP$-zupełny w sensie transformacji wielomianowych:

nie należy do klasy $NP$ Źle

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

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

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

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

nie musi być jedyny Dobrze

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

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

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

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$ Dobrze

problem $SAT$ należy do klasy $NP$ Dobrze

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

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

Wybierz zdania prawdziwe z poniższej listy:

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

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

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$ Dobrze

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

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

Twierdzenie Fagina

każdemu problemowi z klasy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle NP} można przypisać odpowiadającą mu formułę z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle ESO} Dobrze

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

każdej formule z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle ESO} można przypisać odpowiadający jej problem z klasy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle NP} Dobrze