scientific article; zbMATH DE number 139642

MaRDI QIDQ4029623zbMATH OpenFDO

Authors R. G. Nigmatullin

Publication date 28 March 1993

zbMATH Keywords

lower boundscomplexity theoryBoolean circuitscomputational resourcescombinational complexityBoolean Function

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4208009
• scientific article; zbMATH DE number 4087011
• scientific article; zbMATH DE number 4104386
• On a hierarchy of Boolean functions hard to compute in constant depth
• Models of lower-bounds proofs

Cited in

(18)

• Lower bounds for unrestricted Boolean circuits: open problems
• On a hierarchy of Boolean functions hard to compute in constant depth
• scientific article; zbMATH DE number 981681 (Why is no real title available?)
• scientific article; zbMATH DE number 3916179 (Why is no real title available?)
• scientific article; zbMATH DE number 4087011 (Why is no real title available?)
• Diagonalization strikes back: some recent lower bounds in complexity theory
• A nonlinear lower bound on the practical combinational complexity
• A nonlinear lower bound on the practical combinational complexity
• Complexity Lower Bounds using Linear Algebra
• A Gödel Theorem on Network Complexity Lower Bounds
• scientific article; zbMATH DE number 4059378 (Why is no real title available?)
• Models of lower-bounds proofs
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Linear FPT reductions and computational lower bounds
• A uniform method for proving lower bounds on the computational complexity of logical theories
• scientific article; zbMATH DE number 4172392 (Why is no real title available?)
• scientific article; zbMATH DE number 3934407 (Why is no real title available?)
• scientific article; zbMATH DE number 3992933 (Why is no real title available?)

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 Q4029623)