Třídy složitosti

Třídy složitosti problému teoretické informatiky

Znění: Patří věta w do jazyka L(G) generovaného zadanou gramatikou G?

typ jazyka	rozhodnutelný?	třída složitosti
typ 0	nerozhodnutelný [1]	–
typ 1	rozhodnutelný [1]	–
typ 2	rozhodnutelný	polynomiální, O(n^3) (CYK algoritmus [2], [3])
typ 3	rozhodnutelný	lineární časová složitost (O(n))

Q?: rozdíl mezi fixed a general membership problem?

[1] Chomsky 1963, Harrison 1978, Hopcroft and Ulman 1979
[2] http://en.wikipedia.org/wiki/CYK_algorithm
[3] http://www.cs.ucr.edu/~jiang/cs215/tao-new.pdf - včetně příkladu a nástinu důkazu

Teoretická informatika - KNOW HOW last edited on 30 August 2005 at 4:48 pm by 215.59.vivo.cz