Złożoność obliczeniowa/Moduł Twierdzenie PCP

Odpowiedzialny: Grzegorz Gutowski

Twierdzenie PCP

• systemy dowodów propabilistycznie weryfikowalnych
• $\mathbf{𝐍}\mathbf{𝐏}=\mathbf{𝐏}\mathbf{𝐂}\mathbf{𝐏}(\log n,1)$

Redukcje wprowadzające lukę

• problem $k$-centrum
• problem komiwojażera
• problem MAX3SAT

Wnioski

• MAX3SAT nie ma PTAS
• problemy z MAXSNP nie mają PTAS, problem zbioru niezależnego nie ma współczynnika aproksymacji