The Complexity of Very Simple Boolean Formulas with Applications

DOI10.1137/0219003zbMath0696.68060OpenAlexW1968653910MaRDI QIDQ3474280

Richard E. Stearns, Harry B. III Hunt

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/e303887a120f7faad696ebc41e512deefda60363

zbMATH Keywords

complexityfault detectionfinite fieldsdecision problemsNP-completenessbinary decision diagramsmodular arithmeticBoolean formulasprogram schemesfinite and distributive latticesSAT-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Algebraic logic (03G99) Lattices (06B99) Distributive lattices (06D99)

Related Items

On symmetric signatures in holographic algorithms, Power indices and easier hard problems, Decision lists and related Boolean functions, Sorting, linear time and the satisfiability problem, Double Horn functions, The complexity of equivalence for commutative rings