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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

-ograniczony weryfikator

niekoniecznie ma własność stopu

odczytuje co najwyżej jeden bit świadka

odczytuje dowolną liczbę bitów świadka

wykorzystuje co najwyżej bitów losowych

żadna z pozostałych odpowiedzi nie jest poprawna


Twierdzenie PCP ma postać

żadna z pozostałych odpowiedzi nie jest poprawna


Przy założeniu, że , 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

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


Jeśli jest grafem o wierzchołkach i krawędziach, to ma wierzchołków i krawędzi odpowiednio

i

i

i

i

i


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

nie istnieje aproksymacja z żadna stałą

nie istnieje PTAS

nie istnieje -aproksymacja, gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \alpha(n)=1/n^\epsilon }} , dla pewnego

nie istnieje -aproksymacja, gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \alpha(n)=1/n^\epsilon }} , dla każdego