Circuit Definitions of Nondeterministic Complexity Classes

DOI10.1137/0221040MaRDI QIDQ4016401zbMATH OpenOpenAlexFDO

Authors H. Venkateswaran

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

zbMATH Keywords

Boolean circuitsarithmetic circuitsemi-unboundednessskew circuitsnondeterministic space and time classes

Mathematics Subject Classification ID

Circuits, networks (94C99) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 4090800
• On the (non) NP-hardness of computing circuit complexity
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• Nondeterministics circuits, space complexity and quasigroups
• Lower bounds for the size of nondeterministic circuits
• scientific article; zbMATH DE number 1256716
• Completeness for nondeterministic complexity classes
• On the complexity of circuit satisfiability
• Mathematical Foundations of Computer Science 2003
• Separation of deterministic, nondeterministic and alternating complexity classes

Cited in

(19)

• Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits
• Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• Small space analogues of Valiant's classes and the limitations of skew formulas
• The computational complexity of generating random fractals
• Properties that characterize LOGCFL
• Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
• Succinct certification of monotone circuits
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Positive and negative proofs for circuits and branching programs
• A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
• Skew circuits of small width
• Computing the best-case energy complexity of satisfying assignments in monotone circuits
• The computational complexity of the Lorentz lattice gas
• Characterizing Valiant's algebraic complexity classes
• Algebraic complexity classes
• Nonuniform complexity classes specified by lower and upper bounds
• Succinct algebraic branching programs characterizing non-uniform complexity classes
• scientific article; zbMATH DE number 4090800 (Why is no real title available?)

This page was built for publication: Circuit Definitions of Nondeterministic Complexity Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4016401)