Abstract
We refine and significantly extend the known results on the complexities of the Satisfiability, Tautology, Equivalence, and ≤-Problems for classes of Boolean formulas. Results are presented on the relationships between the number of repetitions of variables occurring in formulas and the complexities of decision problems for the formulas. Results are also presented on the complexities of very simple monotone Boolean formulas and of implication.
A variety of applications of these results are presented to a number of logics studied in the literature, to computational probability and counting, to algebraic structures, and to program schemes and Binary Decision Diagrams.
Assuming P ↮ NP, a number of the results are “best” possible or are close to “best” possible.
(Research supported in part by NSF Grants No. DCR 84-03014 and DCR 83-03932.)
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
4. References
J.C. Abbott, Sets, Lattices, and Boolean Algebras, Allyn and Bacon, Boston, Mass., 1969.
S.B. Akers, Binary decision diagrams, IEEE Trans. on Computers, vol. C-27, 1978, pp. 509–516.
S.B. Akers, A procedure for functional design verification, Digest of 10-th International Symp. on Fault Tolerant Computing, 1980, pp. 65–67.
D.N. Arden, S. Chakravarty, H.B. Hunt III, and R.M. Murray, Computational probability with application to fault detection, Technical Report 84-17, Department of Computer Science, SUNY Albany, Albany, New York, 1984.
G. Birkhoff, Lattice Theory, (3rd Edition), Am. Math. Soc., Providence, R.I., 1967.
M. Blum, A.K. Chandra, and M.N. Wegman, Equivalence of free Boolean graphs can be decided probabilistically in polynomial time, Information Processing Letters 10, 1980, pp. 80–82.
P.A. Bloniarz, H.B. Hunt III, and D.J. Rosenkrantz, Algebraic structures with hard equivalence and minimization problems, J. ACM, 31, 1984, pp. 879–904.
S.K. Chakravarti and H.B. Hunt III, Binary decision diagrams, unpublished manuscript.
R.L. Constable, H.B. Hunt III, and S. Sahni, On the computational complexity of scheme equivalence, Proc. 8-th Annual Princeton Conference of Information Sciences and Systems, Princeton, N.J., 1974. Also appears as — H.B.Hunt III, R.L. Constable, and S. Sahni, On the computational complexity of program scheme equivalence, SICOMP 9, 1980, pp. 349–416.
S.A. Cook, The complexity of theorem-proving procedures, Proc. Third Annual ACM Symp. on Theory of Computing, 1971, pp. 151–158.
W. Feller, An Introduction to Probability Theory and its Applications Vol. 1 (3rd Edition), John Wiley and Sons, New York, 1968.
S. Fortune, J. Hopcroft, and E.M. Schmidt, The complexity of equivalence and containment for free single variable program schemes, Technical Report TR 77-310, Department of Computer Science, Cornell University, Ithaca, New York, 1977.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, Ca., 1979.
E.M. Gold, Complexity of automaton identification from given data, Inf. and Control 37, 1978, pp. 302–320.
A. Heyting, Intuitionism, North-Holland, Amsterdam, 1959.
D. Hibert and P. Bernays, Grundlagen der Mathematik, vol. 1, Springer, Berlin, 1934.
H.B. Hunt III and R.E. Stearns, Distributive lattices, and the complexity of logics and probability, submitted for publication.
H.B. Hunt III and R.E. Stearns, Nonlinear algebra for rings is “hard”, submitted for publication.
O.H. Ibarra and S. Moran, Probabilistic algorithms for deciding equivalence of straight-line programs, JACM 30, 1983, pp. 217–228.
S.C. Kleene, Introduction to Metamathematics, D. VanNostrand Co., Inc., Princeton, N.J., 1950.
C.I. Lewis and C.H. Langford, Symbolic Logic, New York, 1932.
S. MacLane and G. Birkhoff, Algebra, MacMillan, New York, 1967.
Z. Manna, Mathematical Theory of Computation, McGraw-Hill, New York, 1974.
E. Mendelson, Introduction to Mathematical Logic (2nd edition), D. VanNostrand, New York, 1979.
B.M.E. Moret, Decision trees and diagrams, Computing Surveys 14, 1982, pp. 593–623.
K.P. Parker and E.J. McCluskey, Probabilistic treatment of general combinational networks, IEEE Trans. on Computers, 24, 1975, pp. 668–670.
E.L. Post, Introduction to a general theory of elementary propositions, Amer. J. Math., 43, 1921, pp. 165–185.
H. Rasiowa, An Algebraic Approach to Non-Classical Logics, North-Holland, Amsterdam, 1974.
H. Rasiowa and R. Sikorski, The Mathematics of Meta-mathematics, Panstwowe Wydawnictwo Naukowe, Warzawa, 1963.
C.A. Tovey, A simplified NP-complete satisfiability problem, Discrete Applied Mathematics 8, 1984, pp. 85–89.
L.G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8, 1979, pp. 410–421.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1985 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hunt, H.B., Stearns, R.E. (1985). Monotone boolean formulas, distributive lattices, and the complexities of logics, algebraic structures, and computation structures (preliminary report). In: Monien, B., Vidal-Naquet, G. (eds) STACS 86. STACS 1986. Lecture Notes in Computer Science, vol 210. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-16078-7_83
Download citation
DOI: https://doi.org/10.1007/3-540-16078-7_83
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-16078-6
Online ISBN: 978-3-540-39758-8
eBook Packages: Springer Book Archive