Złożoność obliczeniowa/Moduł Schematy aproksymacji i klasa MAXSNP

• klasa SNP i MAXSNP
  • problem MAXSAT
  • problem zbioru niezależnego przy ograniczonym stopniu wierzchołka
  • problem maksymalnego podgrafu $k$-kolorowalnego
• L-redukcje
  • redukcja problemu zbioru niezależnego do pokrycia wierzchołkowego przy ograniczonym stopniu wierzchołka
• MAX3SAT jest zupełny w MAXSNP w sensie L-redukcji
• systemy dowodów propabilistycznie weryfikowalnych
• twierdzenie $\mathbf{𝐍}\mathbf{𝐏}=\mathbf{𝐏}\mathbf{𝐂}\mathbf{𝐏}(\log n,1)$
• MAX3SAT nie ma PTAS, problemy z MAXSNP nie mają PTAS, problem zbioru niezależnego nie ma współczynnika aproksymacji