Efektívne algoritmy a zložitosť - 11 - Cookova veta. Redukcie.

Zhrnutie prednášky

Prednáška po zopakovaní tried P, NP a NP-úplných problémov dokazuje Cookovu vetu, teda že problém splniteľnosti logickej formuly (SAT) je NP-ťažký, a teda NP-úplný. Ľubovoľný problém z NP sa polynomiálne zredukuje na SAT tak, že nedeterministický polynomiálny program zapísaný v assembleri podobnom modeli (registre, Accept, Reject, Choose, GoTo, aritmetika) sa spolu so vstupom premení na veľkú formulu simulujúcu jeho beh. Formula je konjunkciou pravidiel nad premennými Q(i,k) a S(i,j,k), ktoré popisujú vykonávaný riadok a hodnoty registrov v čase i. Pravidlá zabezpečujú jeden riadok a jednu hodnotu registra v každom čase, správny začiatok, dosiahnutie Accept a zmeny stavu v súlade s programom. Následne sa ukáže, ako pomocou redukcie dokazovať NP-úplnosť vlastných problémov.

• - Trieda P je podmnožinou NP; NP-úplné problémy sú najťažšie v NP.
• - Cookova veta: SAT je NP-úplný (patrí do NP a je NP-ťažký).
• - Ľubovoľný problém z NP sa zapíše ako nedeterministický polynomiálny program v jednoduchom assembleri s registrami.
• - Beh programu A na vstupe X sa kóduje do formuly F s premennými Q(i,k) (riadok k v čase i) a S(i,j,k) (hodnota registra j v čase i).
• - F je konjunkcia pravidiel: jeden riadok a jedna hodnota registra v každom čase, počiatočný stav, dosiahnutie Accept po p(n) krokoch, správny prechod stavov.
• - F je splniteľná práve vtedy, keď existuje výpočet programu končiaci v Accept.
• - Dokázaná NP-úplnosť problému znamená, že je lepšie hľadať heuristiky alebo iné formulácie než polynomiálny algoritmus.

Zhrnutie pripravené s pomocou AI z prepisu videa.