The power of polynomial size Ω-branching programs

This publication has 9 references indexed in Scilit:

• Nondeterministic space is closed under complementation
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1988
• Exponential lower bounds for real-time branching programs
  Published by Springer Nature ,1987
• Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹
  Published by Association for Computing Machinery (ACM) ,1986
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
  Information and Control, 1984
• Alternation
  Journal of the ACM, 1981
• A time-space tradeoff for sorting on a general sequential model of computation
  Published by Association for Computing Machinery (ACM) ,1980
• Some connections between nonuniform and uniform complexity classes
  Published by Association for Computing Machinery (ACM) ,1980
• The recognition problem for the set of perfect squares
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1966
• Introduction to a General Theory of Elementary Propositions
  American Journal of Mathematics, 1921