Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-22T10:00:58.289Z Has data issue: false hasContentIssue false
  • English
  • Français

The Complexity of Propositional Proofs

Published online by Cambridge University Press:  15 January 2014

Alasdair Urquhart
Alasdair Urquhart*
Affiliation:
Deaprtment of Philosophy, University of Toronto, Toronto, Ontario.E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

§1. Introduction. The classical propositional calculus has an undeserved reputation among logicians as being essentially trivial. I hope to convince the reader that it presents some of the most challenging and intriguing problems in modern logic.

Although the problem of the complexity of propositional proofs is very natural, it has been investigated systematically only since the late 1960s. Interest in the problem arose from two fields connected with computers, automated theorem proving and computational complexity theory. The earliest paper in the subject is a ground-breaking article by Tseitin [62], the published version of a talk given in 1966 at a Leningrad seminar. In the three decades since that talk, substantial progress has been made in determining the relative complexity of proof systems, and in proving strong lower bounds for some restricted proof systems. However, major problems remain to challenge researchers.

The present paper provides a survey of the field, and of some of the techniques that have proved successful in deriving lower bounds on the complexity of proofs. A major area only touched upon here is the proof theory of bounded arithmetic and its relation to the complexity of propositional proofs. The reader is referred to the book by Buss [10] for background in bounded arithmetic. The forthcoming book by Krajíček [40] also gives a good introduction to bounded arithmetic, as well as covering most of the basic results in complexity of propositional proofs.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 1 , Issue 4 , December 1995 , pp. 425 - 467
Copyright
Copyright © Association for Symbolic Logic 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Ajtai, Miklós, The complexity of the pigeonhole principle, Proceedings of the 29th Annual IEEE Symposium on the Foundations of Computer Science, 1988, pp. 346–355.Google Scholar
[2] Ajtai, Miklós, Parity and the pigeonhole principle, Feasible mathematics (Buss, Samuel R. and Scott, Philip J., editors), Birkhäuser, 1990, pp. 1–24.Google Scholar
[3] Ajtai, Miklós, The independence of the modulo p counting principles, preprint, 1993.Google Scholar
[4] Ajtai, Miklós, Symmetric systems of linear equations modulo p, preprint, 1993.Google Scholar
[5] Beame, Paul, A switching lemma primer, preprint, 1993.Google Scholar
[6] Beame, Paul, Impagliazzo, Russell, Krajíc̆ek, Jan, Pitassi, Toniann, and Pudlák, Pavel, Lower bounds on Hilbert's Nullstellensatz and propositional proofs, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1994, pp. 794–806.Google Scholar
[7] Beame, Paul, Impagliazzo, Russell, Krajíc̆ek, Jan, Pitassi, Toniann, Pudlák, Pavel, and Woods, Alan, Exponential lower bounds for the pigeonhole principle, Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, 1992, pp. 200–220.Google Scholar
[8] Beame, Paul and Pitassi, Toniann, An exponential separation between the matching principles and the pigeonhole principle, forthcoming, Annals of Pure and Applied Logic, 1993.Google Scholar
[9] Bellantoni, Stephen, Pitassi, Toniann, and Urquhart, Alasdair, Approximation and small-depth Frege proofs, SIAM Journal of Computing, vol. 21 (1992), pp. 1161–1179.Google Scholar
[10] Buss, Samuel R., Bounded arithmetic, Bibliopolis, Naples, 1986.Google Scholar
[11] Buss, Samuel R., Polynomial size proofs of the propositional pigeonhole principle, Journal of Symbolic Logic, vol. 52 (1987), pp. 916–927.Google Scholar
[12] Buss, Samuel R., On model theory for intuitionistic bounded arithmetic with applications to independence results, Feasible mathematics (Buss, Samuel R. and Scott, Philip J., editors), Birkhäuser, 1990, pp. 27–47.Google Scholar
[13] Church, Alonzo, Introduction to mathematical logic, Princeton U. P., 1956.Google Scholar
[14] Chvátal, Vašek, The tail of the hypergeometric distribution, Discrete Mathematics, vol. 25 (1979), pp. 285–287.Google Scholar
[15] Chvátal, Vašek and Szemerédi, Endre, Many hard examples for resolution, Journal of the Association for Computing Machinery, vol. 35 (1988), pp. 759–768.Google Scholar
[16] Cook, Stephen A., The complexity of theorem-proving procedures, Proceedings of the Third Annual ACM Symposium on the Theory of Computation, 1971, pp. 151–158.Google Scholar
[17] Cook, Stephen A., An exponential example for analytic tableaux, manuscript, 1973.Google Scholar
[18] Cook, Stephen A., Feasibly constructive proofs and the propositional calculus, Proceedings of the Seventh Annual ACM Symposium on the Theory of Computation, 1975, pp. 83–97.Google Scholar
[19] Cook, Stephen A. and Reckhow, Robert A., On the lengths of proofs in the propositional calculus, Proceedings of the Sixth Annual ACM Symposium on the Theory of Computing, 1974, see also corrections for above in SIGACT News, vol. 6 (1974), pp. 15–22.Google Scholar
[20] Cook, Stephen A. and Reckhow, Robert A., The relative efficiency of propositional proof systems, Journal of Symbolic Logic, vol. 44 (1979), pp. 36–50.Google Scholar
[21] Cook, Stephen A. and Urquhart, Alasdair, Functional interpretations of feasibly constructive arithmetic, Annals of Pure and Applied Logic, vol. 63 (1993), pp. 103–200.Google Scholar
[22] D'Agostino, Marcello, Are tableaux an improvement on truth-tables?, Journal of Logic, Language and Information, vol. 1 (1992), pp. 235–252.Google Scholar
[23] Davis, Martin, Logemann, G., and Loveland, D., A machine program for theorem proving, Communications ofthe Association for Computing Machinery, vol. 5 (1962), pp. 394–397, reprinted in [57], vol. 1, pp. 267–270.Google Scholar
[24] Davis, Martin and Putnam, Hilary, A computing procedure for quantification theory, Journal of the Association for Computing Machinery, vol. 7 (1960), pp. 201–215, reprinted in [57], vol. 1, pp. 125–139.Google Scholar
[25] Dowd, Martin, Propositional representation of arithmetic proofs, Ph.D. thesis, University of Toronto, 1979, Department of Computer Science, Technical Report No. 132/79.Google Scholar
[26] Dowd, Martin, Model-theoretic aspects of , unpublished MS, 1985.Google Scholar
[27] Dunne, Paul E., The complexity of Boolean networks, Academic Press, London and San Diego, 1988.Google Scholar
[28] Frege, Gottlob, Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens, Nebert, Halle, 1879.Google Scholar
[29] Furst, Merrick, Saxe, James B., and Sipser, Michael, Parity, circuits, and the polynomial-time hierarchy, Proceedings of the 22nd Annual IEEE Symposium on the Foundations ofComputer Science, 1981, pp. 260–270.Google Scholar
[30] Gabber, Ofer and Galil, Zvi, Explicit constructions of linear size superconcentrators, Proceedings 20th Annual Symposium on Foundations of Computer Science (New York), IEEE, 1979, pp. 364–370.Google Scholar
[31] Galil, Zvi, On the complexity of regular resolution and the Davis-Putnam procedure, Theoretical Computer Science, vol. 4 (1977), pp. 23–46.Google Scholar
[32] Garey, Michael R. and Johnson, David S., Computers and intractability. a guide to the theory of NP-completeness, W. H. Freeman, 1979.Google Scholar
[33] Goerdt, Andreas, Comparing the complexity of regular and unrestricted resolution, Proceedings of the 14th German Workshop on A.I., Informatik Fachberichte 251, 1990.Google Scholar
[34] Håstad, Johan T., Computational limitations of small-depth circuits, MIT Press, 1987.Google Scholar
[35] Haken, Armin, The intractability of resolution, Theoretical Computer Science, vol. 39 (1985), pp. 297–308.Google Scholar
[36] Hopcroft, John E. and Ullman, Jeffrey D., Introduction to automata theory, languages and computation, Addison-Wesley, 1979.Google Scholar
[37] Kowalski, R. and Hayes, P J., Semantic trees in automatic theorem-proving, Machine intelligence vol. 4 (Meitzer, and Michie, , editors), Edinburgh U. Press, Edinburgh, 1969, pp. 87–101.Google Scholar
[38] Krají!c̆ek, Jan, Pudlák, Pavel, and Woods, Alan, Exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle, Random Structures and Algorithms, vol. 7 (1995), pp. 15–39.Google Scholar
[39] Krajíc̆ek, Jan, Lower bounds to the size of constant-depth propositional proofs, Journal of Symbolic Logic, vol. 59 (1994), pp. 73–86.CrossRefGoogle Scholar
[40] Krajíc̆ek, Jan, Bounded arithmetic, propositional logic and complexity theory, Cambridge University Press, 1996.Google Scholar
[41] Krajíc̆ek, Jan and Pudlák, Pavel, Propositional proof systems, the consistency of first order theories and the complexity of computations, Journal of Symbolic Logic, vol. 54 (1989), pp. 1063–1079.Google Scholar
[42] Krajíc̆ek, Jan and Pudlák, Pavel, Propositional provability in models of weak arithmetic, Computer science logic (Kaiserlautern, Oct. '89) (Börger, E., Kleine-Bunning, H., and Richter, M.M., editors), Springer-Verlag, 1990, LNCS 440, pp. 193–210.Google Scholar
[43] Krajíc̆ek, Jan and Pudlák, Pavel, Quantified propositional calculi and fragments of bounded arithmetic, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 36 (1990), pp. 29–46.Google Scholar
[44] Margulis, G. A., Explicit construction of concentrators, Problems of Information Transmission, vol. 9 (1973), pp. 325–332.Google Scholar
[45] Murray, Neil V. and Rosenthal, Erik, On the computational intractability of analytic tableau methods, Bulletin of the IGPL, vol. 2 (09 1994), no. 2, pp. 205–228.Google Scholar
[46] Papadimitriou, Christos H., Computational complexity, Addison-Wesley, 1994.Google Scholar
[47] Parikh, Rohit, Existence and feasibility in arithmetic, Journal of Symbolic Logic, vol. 36 (1971), pp. 494–508.Google Scholar
[48] Paris, J. and Wilkie, A., Counting problems in bounded arithmetic, Methods in mathematical logic (Proceedings Caracas, 1983), Springer-Verlag, Berlin, 1985, Lecture Notes in Mathematics, vol. 1130, pp. 317–340.Google Scholar
[49] Pitassi, Toniann, Beame, Paul, and Impagliazzo, Russell, Exponential lower bounds for the pigeonhole principle, Computational Complexity, vol. 3 (1993), pp. 97–140.Google Scholar
[50] Razborov, Alexander A., Lower bounds on the size of bounded depth networks over a complete basis with logical addition, Matemat. Zametki, vol. 41 (1987), pp. 598–607, English translation in Mathematical Notes, vol. 41 (1987), 333–338.Google Scholar
[51] Razborov, Alexander A., Bounded arithmetic and lower bounds in Boolean complexity, Feasible mathematics II (Clote, Peter and Remmel, Jeffrey, editors), Birkhäuser, Boston, Basel, Berlin, 1995, pp. 344–386.Google Scholar
[52] Reckhow, Robert, On the lengths of proofs in the propositional calculus, Ph.D. thesis , University of Toronto, 1976.Google Scholar
[53] Riis, Søren, Independence in bounded arithmetic, D. Phil. thesis, Oxford University, 1993.Google Scholar
[54] Robinson, J. A., The generalized resolution principle, Machine intelligence, vol. 3 (Dale, and Michie, , editors), American Elsevier, New York, 1968, pp. 77–94, reprinted in [57], vol. 2, pp. 135–151.Google Scholar
[55] Shanin, N.A., Davydov, G.V., Maslov, S. Y., Mints, G.E., Orevkov, V.P., and Slisenko, A.O., An algorithm for a machine search of a natural logical deduction in a propositional calculus, Izdat. Nauka, Moscow, 1965, reprinted in [57].Google Scholar
[56] Shoenfield, Joseph, Mathematical logic, Addison-Wesley, 1967.Google Scholar
[57] Siekmann, Jörg and Wrightson, Graham (editors), Automation of reasoning, Springer-Verlag, New York, 1983.Google Scholar
[58] Smolensky, R., Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the 19th Annual ACM Symposium on the Theory of Computing, 1987, pp. 77–82.Google Scholar
[59] Smullyan, Raymond M., First-order logic, Springer-Verlag, New York, 1968, reprinted by Dover, New York, 1995.Google Scholar
[60] Spira, P. M., On time-hardware complexity tradeoffs for Boolean functions, Proceedings of the Fourth Hawaii International Symposium on System Sciences, 1971, pp. 525–527.Google Scholar
[61] Statman, Richard, Bounds for proof-search and speed-up in the predicate calculus, Annals of mathematical logic, vol. 15 (1978), pp. 225–287.Google Scholar
[62] Tseitin, G. S., On the complexity of derivation in propositional calculus, Studies in constructive mathematics and mathematical logic, part 2 (Slisenko, A. O., editor), Consultants Bureau, New York, 1970, pp. 115–125, reprinted in [57], vol. 2, pp. 466–483.Google Scholar
[63] Urquhart, Alasdair, Hard examples for resolution, Journal of the Association for Computing Machinery, vol. 34 (1987), pp. 209–219.Google Scholar
[64] Urquhart, Alasdair, The complexity of Gentzen systems for propositional logic, Theoretical Computer Science, vol. 66 (1989), pp. 87–97.Google Scholar
[65] Urquhart, Alasdair, The relative complexity of resolution and cut-free Gentzen systems, Annals of mathematics and artificial intelligence, vol. 6 (1992), pp. 157–168.Google Scholar
[66] von Neumann, John, Zur Hilbertschen Beweistheorie, Mathematische Zeitschrift, vol. 26 (1926), pp. 1–46.Google Scholar
[67] Wang, Hao, Towards mechanical mathematics, IBM Journal for Research and Development, vol. 4 (1960), pp. 2–22, reprinted in [57], vol. 1, pp. 244–264.Google Scholar
[68] Wegener, Ingo, The complexity of Boolean functions, B. G. Teubner and John Wiley, 1987.Google Scholar
[69] Whitehead, Alfred North and Russell, Bertrand, Principia mathematica, vols. 1–3, Cambridge University Press, 1910–1913, second edition, 1925.Google Scholar