Złożoność obliczeniowa/Moduł Twierdzenie PCP: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Nie podano opisu zmian
 
Nie podano opisu zmian
 
Linia 1: Linia 1:
Odpowiedzialny: [[Użytkownik:Ggutowski|Grzegorz Gutowski]]
= Twierdzenie PCP =
= Twierdzenie PCP =
* systemy dowodów propabilistycznie weryfikowalnych
* systemy dowodów propabilistycznie weryfikowalnych

Aktualna wersja na dzień 21:43, 1 lip 2006

Odpowiedzialny: Grzegorz Gutowski

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=2636”