Circuit Definitions of Nondeterministic Complexity Classes
From MaRDI portal
Publication:4016401
DOI10.1137/0221040zbMath0749.68039OpenAlexW2024994589MaRDI QIDQ4016401
Publication date: 14 December 1992
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0221040
arithmetic circuitBoolean circuitssemi-unboundednessskew circuitsnondeterministic space and time classes
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Circuits, networks (94C99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Skew circuits of small width, Computing the best-case energy complexity of satisfying assignments in monotone circuits, Positive and negative proofs for circuits and branching programs, The computational complexity of generating random fractals, Small space analogues of Valiant's classes and the limitations of skew formulas, Succinct certification of monotone circuits, Characterizing Valiant's algebraic complexity classes, A model-theoretic characterization of constant-depth arithmetic circuits, Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae, Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes, Algebraic Complexity Classes, Non-commutative arithmetic circuits: depth reduction and size lower bounds, A lower bound for monotone arithmetic circuits computing \(0-1\) permanent, Non-cancellative Boolean circuits: A generalization of monotone boolean circuits, On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits, The computational complexity of the Lorentz lattice gas
