Parametryczna złożoność obliczeniowa

Okazuje się że można (i warto) mierzyć trudność problemow obliczeniowych subtelniej niż przy pomocy klas P, NP, PSPACE itd. Otoż złozoność niektorych problemow zależy nie tylko od ARGUMENTU ale i od PARAMETRU. Ta obserwacja doprowadziła, w latach 90, do odkrycia klas złożoności parametrycznej, rownie naturalnych jak klasyczne klasy zlozoności. Teoria zlozoności parametrycznej stała się w ciągu kilku lat dorosłą dziedziną podstaw informatyki. Najwyższy czas się jej nauczyć (i opowiedzieć studentom).

Wymagania: JFiZO