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

Z Studia Informatyczne
< Złożoność obliczeniowa
Wersja z dnia 19:17, 1 lip 2006 autorstwa Ggutowski (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania
  • 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 𝐍𝐏=𝐏𝐂𝐏(logn,1)
  • MAX3SAT nie ma PTAS, problemy z MAXSNP nie mają PTAS, problem zbioru niezależnego nie ma współczynnika aproksymacji
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Złożoność_obliczeniowa/Moduł_Schematy_aproksymacji_i_klasa_MAXSNP&oldid=2621”