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 7: | Linia 7: | ||
* MAX3SAT jest zupełny w MAXSNP w sensie L-redukcji | * MAX3SAT jest zupełny w MAXSNP w sensie L-redukcji | ||
* systemy dowodów propabilistycznie weryfikowalnych | * systemy dowodów propabilistycznie weryfikowalnych | ||
* twierdzenie <math>\mathbf{NP} = \mathbf{PCP}(log n, 1)</math> | * 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 | * MAX3SAT nie ma PTAS, problemy z MAXSNP nie mają PTAS, problem zbioru niezależnego nie ma współczynnika aproksymacji | ||
Wersja z 19:19, 1 lip 2006
- klasa SNP i MAXSNP
- 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
- MAX3SAT jest zupełny w MAXSNP w sensie L-redukcji
- systemy dowodów propabilistycznie weryfikowalnych
- twierdzenie
- MAX3SAT nie ma PTAS, problemy z MAXSNP nie mają PTAS, problem zbioru niezależnego nie ma współczynnika aproksymacji
