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 |
||
| Linia 9: | Linia 9: | ||
* problemy silnie NP-zupełne nie mają FPTAS | * problemy silnie NP-zupełne nie mają FPTAS | ||
= klasa | = klasa MAXSNP = | ||
* twierdzenie Fagina i definicja SNP | |||
* problem MAXSAT | * problem MAXSAT | ||
* problem zbioru niezależnego przy ograniczonym stopniu wierzchołka | * problem zbioru niezależnego przy ograniczonym stopniu wierzchołka | ||
Wersja z 19:34, 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
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
