scientific article; zbMATH DE number 4090800

MaRDI QIDQ3817611zbMATH OpenFDO

Authors H. Venkateswaran

Publication date 1988

zbMATH Keywords

complexity classesBoolean circuitscircuit complexitynondeterministic space and time classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Circuit Definitions of Nondeterministic Complexity Classes
• 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

(4)

• Arithmetization: A new method in structural complexity theory
• Circuit Definitions of Nondeterministic Complexity Classes
• Nonuniform complexity classes specified by lower and upper bounds
• Properties that characterize LOGCFL

This page was built for publication:

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