Entscheidbarkeit 90

	Wortproblem	Leerheitsproblem	Äquivalenzproblem	Schnittproblem
Typ 3	ja mit $O\left(n\right)$	ja	ja	ja
Det. kf.	ja mit $O\left(n\right)$	ja	ja	nein
Typ 2	ja mit $O\left(n^{3}\right)$	ja	nein	nein
Typ 1	ja mit $O\left(c^{n}\right)$	nein	nein	nein
Typ 0	nein	nein	nein	nein