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

From Studia Informatyczne

(\log n,1)-ograniczony weryfikator

niekoniecznie ma własność stopu

odczytuje co najwyżej jeden bit świadka

odczytuje dowolną liczbę bitów świadka

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

żadna z pozostałych odpowiedzi nie jest poprawna


Twierdzenie PCP ma postać

NP=PCP(0,poly(n))

NP=PCP(poly(n),\log n)

NP=PCP(\log n, 1)

NP=PCP(\log n, \log n)

żadna z pozostałych odpowiedzi nie jest poprawna


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

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

posiada PTAS, co wynika z twierdzenia PCP

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

żadna z pozostałych odpowiedzi nie jest poprawna


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

jest dwudzielny

posiada doskonałe skojarzenie

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

żadna z pozostałych odpowiedzi nie jest poprawna


Problem 3OCCUR MAX3SAT jest

NP-zupełny

MAXSNP-zupełny

w MAXSNP_0

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


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

n^2 i m^2

mn i m^2n

n^2 i mn

mn i mn


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łą

nie istnieje PTAS

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

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