Separating completely complexity classes related to polynomial size \(\Omega\)-decision trees. (English) Zbl 0756.68039

Damm, Carsten; Meinel, Christoph

Fundamentals of computation theory, Proc. Int. Conf., FCT ’89, Szeged/Hung. 1989, Lect. Notes Comput. Sci. 380, 127-136 (1989).

Summary: [For the entire collection see Zbl 0726.00019.]
In proving exponential lower and polynomial upper bounds for parity decision trees and collecting similar bounds for nondeterministic and co- nondeterministic decision trees we completely separate the complexity classes related to polynomial size deterministic, nondeterministic, co- nondeterministic, parity, and alternating decision trees.

MSC:

68Q15

Complexity classes (hierarchies, relations among complexity classes, etc.)

Keywords:

tree structured \(\Omega\)-boundary programs; separation

Citations:

Zbl 0726.00019