Efektívne algoritmy a zložitosť - 10 - Triedy P a NP

Zhrnutie prednášky

Prednáška motivuje teóriu NP-úplnosti na probléme obchodného cestujúceho (TSP), pre ktorý nie je známy polynomiálny algoritmus ani dôkaz jeho neexistencie. Ak sa pre vlastný problém nedá nájsť efektívne riešenie, najlepším argumentom je ukázať, že je NP-ťažký alebo NP-úplný, a teda jeho vyriešenie by vyriešilo aj všetky notoricky ťažké problémy. Teória je definovaná pre rozhodovacie problémy s odpoveďou áno/nie, preto sa ku každému optimalizačnému problému zavádza jeho rozhodovacia verzia (napr. existuje okružná cesta s dĺžkou najviac B). Obe verzie sú v podstate rovnako ťažké: optimalizačný problém rieši rozhodovací priamo a rozhodovací zasa optimalizačný pomocou binárneho vyhľadávania a postupného odoberania hrán. Na záver sa zavádzajú nedeterministické výpočty v pseudokóde cez konštrukty accept, reject a choose.

• - TSP hľadá najkratšiu okružnú cestu v ohodnotenom neorientovanom grafe, ale nie je preň známy polynomiálny algoritmus.
• - Najlepší argument o ťažkosti vlastného problému je dôkaz jeho NP-ťažkosti alebo NP-úplnosti.
• - Ak sa vyrieši ľubovoľný NP-úplný problém v polynomiálnom čase, vyriešia sa tak všetky problémy v NP.
• - Teória sa definuje pre rozhodovacie problémy, ktorých výstupom je jeden bit (áno/nie).
• - Rozhodovacia verzia TSP sa pýta, či existuje okružná cesta s dĺžkou najviac B.
• - Optimalizačný a rozhodovací problém sú polynomiálne ekvivalentné: binárne vyhľadávanie hranice B a vynechávanie hrán umožnia nájsť dĺžku aj samotnú cestu.
• - Nedeterministický pseudokód rozširuje deterministický o konštrukty accept, reject a choose.

Zhrnutie pripravené s pomocou AI z prepisu videa.