2018. 02. 28. 10:15 - 2018. 02. 28. 13:00
ELTE lágymányosi campus, déli épület (1117 Budapest, Pázmány Péter s.1/C), 3-607 terem
-
-
-
-
Esemény típusa: szeminárium
Szervezés: Külsős
-
-

Leírás

Papadimitriou 94-es cikkében számos új TFNP-beli (keresési)
bonyolultsági osztályt definiált, melyekről itt lehet olvasni:
https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#ppa

Többek között ide tartozik a SPERNER, a BORSUK-ULAM, a
NASH, eps-GCIRCUIT, NECKLACE SPLITTING és még sok
más fontos keresési probléma. Azóta fény derült pár hibára az
eredeti cikkben és született pár új pozitív eredmény is. Ezeket
fogjuk áttekinteni mindenki számára érthető módon, tehát az
alapdefinícióktól kezdve.