Złożoność obliczeniowa/Test 9: Twierdzenie PCP i nieaproksymowalność

$(\log n,1)$-ograniczony weryfikator

niekoniecznie ma własność stopu Źle

odczytuje co najwyżej jeden bit świadka Źle

odczytuje dowolną liczbę bitów świadka Źle

wykorzystuje co najwyżej $\log n$ bitów losowych Dobrze

żadna z pozostałych odpowiedzi nie jest poprawna Źle

Twierdzenie PCP ma postać

$NP=PCP(0,poly(n))$ Źle

$NP=PCP(poly(n),\log n)$ Źle

$NP=PCP(\log n,1)$ Dobrze

$NP=PCP(\log n,\log n)$ Źle

żadna z pozostałych odpowiedzi nie jest poprawna Źle

Przy założeniu, że $P\neq NP$, problem MAX3SAT

nie posiada PTAS, co dowodzimy korzystając z tego że jest MAXSNP-zupełny Źle

posiada PTAS, co wynika z twierdzenia PCP Źle

nie posiada PTAS, co wykazujemy L-redukując MAXkFSAT do MAX3SAT Źle

żadna z pozostałych odpowiedzi nie jest poprawna Dobrze

Ekspander to graf o jednakowym stopniu wszystkich wierzchołków, który

jest dwudzielny Źle

posiada doskonałe skojarzenie Źle

dla każdego zbioru wierzchołków posiada odpowiednio dużą liczbę krawędzi opuszczających ten zbiór Dobrze

żadna z pozostałych odpowiedzi nie jest poprawna Źle

Problem 3OCCUR MAX3SAT jest

NP-zupełny Dobrze

MAXSNP-zupełny Dobrze

w $MAXSNP_{0}$ Dobrze

często stosowany w dowodach MAXSNP-zupełności Dobrze

Jeśli $G$ jest grafem o $n$ wierzchołkach i $m$ krawędziach, to $G^{2}$ ma wierzchołków i krawędzi odpowiednio

$n^{2}$ i $mn^{2}$ Dobrze

$n^{2}$ i $m^{2}$ Źle

$mn$ i $m^{2}n$ Źle

$n^{2}$ i $mn$ Źle

$mn$ i $mn$ Źle

Najsilniejszy znany rezultat o nieaproksymowalności problemu zbioru niezależnego mówi, że przy założeniu $P\neq NP$

nie istnieje aproksymacja z żadna stałą Źle

nie istnieje PTAS Źle

nie istnieje $\alpha (n)$-aproksymacja, gdzie $\alpha (n)=1/n^{\epsilon }$, dla pewnego $\epsilon$ Dobrze

nie istnieje $\alpha (n)$-aproksymacja, gdzie $\alpha (n)=1/n^{\epsilon }$, dla każdego $\epsilon$ Źle