×

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

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.)

Citations:

Zbl 0726.00019
PDFBibTeX XMLCite