Złożoność obliczeniowa/Moduł Schematy aproksymacji i klasa MAXSNP: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| (Nie pokazano 3 pośrednich wersji utworzonych przez tego samego użytkownika) | |||
| Linia 1: | Linia 1: | ||
Odpowiedzialny: [[Użytkownik:Ggutowski|Grzegorz Gutowski]] | |||
= Schematy aproksymacyjne = | = Schematy aproksymacyjne = | ||
* PTAS i FPTAS | * PTAS i FPTAS | ||
| Linia 9: | Linia 10: | ||
* problemy silnie NP-zupełne nie mają FPTAS | * problemy silnie NP-zupełne nie mają FPTAS | ||
= klasa | = klasa MAXSNP = | ||
** problem MAXSAT | * 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 | * L-redukcje | ||
** redukcja problemu zbioru niezależnego do pokrycia wierzchołkowego przy ograniczonym stopniu wierzchołka | ** redukcja problemu zbioru niezależnego do pokrycia wierzchołkowego przy ograniczonym stopniu wierzchołka | ||
Aktualna wersja na dzień 21:42, 1 lip 2006
Odpowiedzialny: Grzegorz Gutowski
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
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 -kolorowalnego
- L-redukcje
- redukcja problemu zbioru niezależnego do pokrycia wierzchołkowego przy ograniczonym stopniu wierzchołka
