The Complexity of Very Simple Boolean Formulas with Applications
From MaRDI portal
Publication:3474280
DOI10.1137/0219003zbMath0696.68060MaRDI QIDQ3474280
Harry B. III Hunt, Richard E. Stearns
Publication date: 1990
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/e303887a120f7faad696ebc41e512deefda60363
complexity; fault detection; finite fields; decision problems; NP-completeness; binary decision diagrams; modular arithmetic; Boolean formulas; program schemes; finite and distributive lattices; SAT-completeness
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
03G99: Algebraic logic
06B99: Lattices
06D99: Distributive lattices
Related Items
Power indices and easier hard problems, Decision lists and related Boolean functions, The complexity of equivalence for commutative rings, On symmetric signatures in holographic algorithms, Double Horn functions, Sorting, linear time and the satisfiability problem