Circuit Definitions of Nondeterministic Complexity Classes
DOI10.1137/0221040zbMATH Open0749.68039OpenAlexW2024994589MaRDI QIDQ4016401FDOQ4016401
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
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
Boolean circuitsarithmetic circuitsemi-unboundednessskew circuitsnondeterministic space and time classes
Circuits, networks (94C99) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
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
- Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
- Succinct certification of monotone circuits
- Properties that characterize LOGCFL
- 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
- Title not available (Why is that?)
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)
