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

arithmetic circuitBoolean circuitsnondeterministic space and time classessemi-unboundednessskew circuits

Mathematics Subject Classification ID

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

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

(22)

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

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)