A linear-time algorithm for testing the truth of certain quantified Boolean formulas. (English) Zbl 0398.68042


68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
03G05 Logical aspects of Boolean algebras
Full Text: DOI


[1] Aho, A.V.; Hopcroft, I.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0326.68005
[2] Cook, S.A., The complexity of theorem proving procedures, Proc. 3rd ann. ACM symp. theory comput., 151-158, (1971)
[3] Even, S.; Itai, A.; Shamir, A., On the complexity of timetable and multi-commodity flow problems, SIAM J. comput., 5, 4, 691-703, (1976) · Zbl 0358.90021
[4] Reingold, E.M.; Nievergelt, J.; Deo, N., Combinatorial algorithms: theory and practice, (1977), Prentice-Hall Englewood Cliffs, NJ · Zbl 0367.68032
[5] Schaefer, T.J., The complexity of satisfiability problems, Proc. 10th ann. ACM symp. theory comput., 216-226, (1978) · Zbl 1282.68143
[6] Stockmeyer, L.J.; Meyer, A.R., Word problems requiring exponential time, Proc. 5th ann. ACM symp. theory comput., 1-9, (1973) · Zbl 0359.68050
[7] Tarjan, R.E., Depth first search and linear graph algorithms, SIAM J. comput., 1, 2, 146-160, (1972) · Zbl 0251.05107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.