Złożoność obliczeniowa/Moduł Twierdzenie PCP

Z Studia Informatyczne
< Złożoność obliczeniowa
Wersja z dnia 19:48, 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

Twierdzenie PCP

  • systemy dowodów propabilistycznie weryfikowalnych
  • 𝐍𝐏=𝐏𝐂𝐏(log⁡n,1)

Redukcje wprowadzające lukę

  • problem k-centrum
  • problem komiwojażera
  • problem MAX3SAT

Wnioski

  • 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ł_Twierdzenie_PCP&oldid=2630”