Cosmological lower bound on the circuit complexity of a small problem in logic
From MaRDI portal
Publication:3455548
DOI10.1145/602220.602223zbMath1326.68153OpenAlexW2165587117MaRDI QIDQ3455548
Albert R. Meyer, Larry J. Stockmeyer
Publication date: 7 December 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/602220.602223
computational complexitylower boundcircuit complexitylogicdecision problemWS1Spractical undecidability
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (7)
Verification of agent navigation in partially-known environments ⋮ A GLNPSO for multi-level capacitated lot-sizing and scheduling problem in the poultry industry ⋮ On the model-checking of monadic second-order formulas with edge set quantifications ⋮ On algebraic array theories ⋮ Automata for the verification of monadic second-order graph properties ⋮ A note on dimensions of polynomial size circuits ⋮ Unnamed Item
This page was built for publication: Cosmological lower bound on the circuit complexity of a small problem in logic
