Separating complexity classes related to Ω-decision trees

By proving exponential lower and polynomial upper bounds for parity decision trees and collecting similar bounds for nondeterministic and co-nondeterministic decision trees, the complexity classes related to polynomial-size deterministic, nondeterministic, co-nondeterministic, parity, and alternating decision trees are completely separated. Considering alternating decision trees, it is shown that the number of alternations between, say, ⋎-nodes and ⋏-nodes strongly influences their computational power.

Authors

• Carsten Damm
• Christoph Meinel

Keywords

No keywords are indexed for this paper.