Vybrané kapitoly z výpočetní složitosti I

Michal Koucký
<koucky@iuuk.mff.cuni.cz>

NTIN085 - 2/1 Z, Zk

Přednáška 5.11. se nekoná - děkansky den.

Čas konání: Út. 9:00-10:30
Místo konání: S321, tedy chodba 3. patro, Malá Strana.

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován tzv. zjemnělé složitosti (fine-grained complexity). Zjemnělá složitost je oblast, která vznikla a pozoruhodně se rozvinula během posledních patnácti let. Snaží se odpovědět na otázku, proč nejlepší známé algoritmy například pro hledání nejdelší společné podposloupnosti mají kvadratickou časovou složitost a pro jiné problémy mají všechny známé algoritmy zase složitost kubickou. Dává to do souvislosti s exponenciálními algoritmy pro řešení splnitelnosti (SAT).

Přednáška je určena především studentům vyšších ročníků studia a doktorandům. Přednáška předpokládá základní znalosti z výpočetní složitosti, pravděpodobnosti a diskrétní matematiky. Přednášku je možné si zapsat opakovaně.

Předběžný plán přednášky

• ETH, SETH, Orthogonal Vectors Problem (OV) vs SETH (Notes)
• Algorithms for SAT
• Strong Exponential Time Hypothesis (SETH) and sparsification (Notes)
• Algoritmus pro OVP
• Nejdelší společná podposloupnost (LCS) vs SETH, algoritmy
• Nejkratší cesty v grafu (APSP)
• 3SUM a její redukce
• Edit distance vs LCS, algoritmy
• Hledání kliky a související domněnky
• Nedeterministická SETH, Merlin-Arthur SETH a spol.
• Jemné aproximace

Literatura:

• Akualizované poznámky k přednášce.
• Virginia Vassilevska Williams and Ryan Williams. Fine-Grained Algorithms and Complexity. 2020. Lecture notes.
• Karl Bringmann and Marvin Künnemann. Fine-Grained Complexity Theory. 2017. Lecture notes.

Domácí úkoly