Aktualna wersja na dzień 21:42, 1 lip 2006

Schematy aproksymacyjne

PTAS i FPTAS
PTAS i FPTAS dla plecaka
asymptotyczny PTAS dla pakowania
problem zbioru niezależnego albo posiada PTAS, albo nie posiada współczynnika aproksymacji

twierdzenie Fagina i definicja SNP
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

@@ Linia 1: / Linia 1: @@
-* klasa SNP i MAXSNP
+Odpowiedzialny: [[Użytkownik:Ggutowski|Grzegorz Gutowski]]
-** problem MAXSAT
+= Schematy aproksymacyjne =
-** problem zbioru niezależnego przy ograniczonym stopniu wierzchołka
+* PTAS i FPTAS
-** problem maksymalnego podgrafu <math>k</math>-kolorowalnego
+* PTAS i FPTAS dla plecaka
+* asymptotyczny PTAS dla pakowania
+* problem zbioru niezależnego albo posiada PTAS, albo nie posiada współczynnika aproksymacji
+= silna NP-zupełność =
+* przykłady
+* problemy silnie NP-zupełne nie mają FPTAS
+= klasa MAXSNP =
+* twierdzenie Fagina i definicja SNP
+* problem MAXSAT
+* problem zbioru niezależnego przy ograniczonym stopniu wierzchołka
+* problem maksymalnego podgrafu <math>k</math>-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 <math>\mathbf{NP} = \mathbf{PCP}(log n, 1)</math>
-* MAX3SAT nie ma PTAS, problemy z MAXSNP nie mają PTAS, problem zbioru niezależnego nie ma współczynnika aproksymacji