Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-23T22:49:23.175Z Has data issue: false hasContentIssue false
  • English
  • Français

Lower bounds for cutting planes proofs with small coefficients

Published online by Cambridge University Press:  12 March 2014

Maria Bonet ,
Toniann Pitassi  and
Ran Raz
Maria Bonet
Affiliation:
Department de Lenguajes y Systemas Informaticos, Edificio e Pau Gargallo 5, 08028 Barcelona, Spain, E-mail: [email protected]
Toniann Pitassi
Affiliation:
Department of Computer Science, University of Arizona, Tucson, AZ 85721, USA, E-mail: [email protected]
Ran Raz
Affiliation:
Department of Applied Math, Weizmann Institute, Rehovat 76100, Israel, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider small-weight Cutting Planes (CP*) proofs; that is, Cutting Planes (CP) proofs with coefficients up to Poly(n). We use the well known lower bounds for monotone complexity to prove an exponential lower bound for the length of CP* proofs, for a family of tautologies based on the clique function. Because Resolution is a special case of small-weight CP, our method also gives a new and simpler exponential lower bound for Resolution.

We also prove the following two theorems: (1) Tree-like CP* proofs cannot polynomially simulate non-tree-like CP* proofs. (2) Tree-like CP* proofs and Bounded-depth-Frege proofs cannot polynomially simulate each other.

Our proofs also work for some generalizations of the CP* proof system. In particular, they work for CP* with a deduction rule, and also for any proof system that allows any formula with small communication complexity, and any set of sound rules of inference.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 62 , Issue 3 , September 1997 , pp. 708 - 728
Copyright
Copyright © Association for Symbolic Logic 1997

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, M., The complexity of the pigeonhole principle, forthcoming; preliminary version, 29th Annual Symposium on the Foundations of Computer Science, pp. 346–355, 1988.Google Scholar
[2]Alon, N. and Boppana, R., The monotone circuit complexity of Boolean functions, Combinatorica, vol. Vol 7, No. 1 (1987), pp. 1–22.CrossRefGoogle Scholar
[3]Beame, P., Impagliazzo, R., Krajíček, J., Pitassi, T., Pudlák, P., and Woods, A., Exponential lower bounds for the pigeonhole principle, Symposium on Theoretical Computer Science, 1992, pp. 200–221.Google Scholar
[4]Beame, P. and Lawry, J., Randomized versus nondeterministic communication complexity, Symposium on Theoretical Computer Science, 1992, pp. 188–199.Google Scholar
[5]Buss, S., Polynomial size proofs of the propositional pigeonhole principle, this Journal, vol. 52 (1987), pp. 916–927.Google Scholar
[6]Buss, S. and Clote, P., Cutting planes, connectivity and threshold logic, to appear in Archive for Mathematical Logic.Google Scholar
[7]Chvatal, V., Edmond polytopes and a hierarchy of combinatorial problems, Discrete Math., vol. 4 (1973), pp. 305–337.CrossRefGoogle Scholar
[8]Cook, S. and Haken, A., manuscript in preparation.Google Scholar
[9]Cook, S. and Reckhow, R., The relative efficiency of propositional proof systems, this Journal, vol. 44 (1979), pp. 36–50.Google Scholar
[10]Cook, W., Coullard, C. R., and Turan, G., On the complexity of cutting plane proofs, Discrete Applied Mathematics, vol. 18 (1987), pp. 25–38.CrossRefGoogle Scholar
[11]Goerdt, A., Cuttingplane versus Frege proof systems, Lecture Notes in Computer Science, vol. 533.Google Scholar
[12]Gomory, R. E., An algorithm for integer solutions of linear programs, Recent advances in mathematical programming, McGraw-Hill, New York, 1963, pp. 269–302.Google Scholar
[13]Haken, A., The intractability of resolution, Theoretical Computer Science, vol. 39 (1985), pp. 297–308.CrossRefGoogle Scholar
[14]Impagliazzo, R., Pitassi, T., and Urquhart, A., Upper and lower bounds for tree-like cutting planes proofs, Proceedings from Logic in Computer Science, 1994.Google Scholar
[15]Karchmer, M., Communication complexity: A new approach to circuit depth, MIT Press, 1989.CrossRefGoogle Scholar
[16]Karchmer, M. and Wigderson, A., Monotone circuits for connectivity require super-logarithmic depth, Proceedings of the 20th STOC, 1988, pp. 539–550.Google Scholar
[17]Krajíček, J., Interpolation theorems, lower bounds for proof systems and independence results for bounded arithmetic, to appear in this Journal.Google Scholar
[18]Krajíček, J., Lower bounds to the size of constant-depth propositional proofs, this Journal, vol. 59 (1994), no. 1, pp. 73–86.Google Scholar
[19]Krajíček, J. and Pudlák, P., Some consequences of cryptographical conjectures for EF, manuscript, 1995.CrossRefGoogle Scholar
[20]Kushilevitz, E. and Nisan, N., Communication complexity, to appear.Google Scholar
[21]Clote, P., Cutting planes and constant depth Frege proofs, manuscript, 1993.Google Scholar
[22]Paris, J., Wilkie, A., and Woods, A., Provability of the pigeonhole principle and the existence of infinitely many primes, this Journal, vol. 53 (1988), no. 4, pp. 1235–1244.Google Scholar
[23]Pudlák, P., manuscript in preparation.Google Scholar
[24]Raz, R., Lower bounds for probabilistic communication complexity and for the depth of monotone Boolean circuits, Ph.D. thesis, The Hebrew University, 1992, in Hebrew.Google Scholar
[25]Raz, R. and Wigderson, A., Probabilistic communication complexity of Boolean relations, Proceedings of the 30th FOCS, 1989, pp. 562–567.Google Scholar
[26]Raz, R. and Wigderson, A., Monotone circuits for matching require linear depth, ACM Symposium on Theory of Computing, 1990, pp. 287–292.Google Scholar
[27]Razborov, A., Lower bounds for the monotone complexity of some Boolean functions, Dokl. Ak. Nauk. SSSR, vol. 281 (1985), pp. 798–801, in Russian; English translation in Sov. Math. Dokl, vol. 31 (1985), pp. 354–357.Google Scholar
[28]Razborov, A., Unprovability of lower bounds on the circuit size in certain fragments of bounded arithmetic, Izvestiya of the R.A.N., vol. 59 (1995), no. 1, pp. 201–224.Google Scholar
[29]Razborov, A. and Rudich, S., Natural proofs, Proceedings from the Twenty-sixth ACM Symposium on Theoretical Computer Science, 05 1994, pp. 204–213.Google Scholar
[30]Yao, A. C.-C., Some complexity questions related to distributive computing, 11th Symposium on Theoretical Computer Science, 1979, pp. 209–213.Google Scholar