Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-26T11:22:18.626Z Has data issue: false hasContentIssue false
  • English
  • Français

Discretely ordered modules as a first-order extension of the cutting planes proof system

Published online by Cambridge University Press:  12 March 2014

Jan Krajíček
Jan Krajíček*
Affiliation:
Mathematical Institute, and Institute of Computer Science, Academy of Sciences, Prague Mathematical Institute, Oxford University, 24–29 St. Giles', Oxford, OX1 3LB, Great Britain. E-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We define a first-order extension LK(CP) of the cutting planes proof system CP as the first-order sequent calculus LK whose atomic formulas are CP-inequalities ∑i ai · xi ≥ b (xi's variables, ai's and b constants). We prove an interpolation theorem for LK(CP) yielding as a corollary a conditional lower bound for LK(CP)-proofs. For a subsystem R(CP) of LK(CP), essentially resolution working with clauses formed by CP-inequalities, we prove a monotone interpolation theorem obtaining thus an unconditional lower bound (depending on the maximum size of coefficients in proofs and on the maximum number of CP-inequalities in clauses). We also give an interpolation theorem for polynomial calculus working with sparse polynomials.

The proof relies on a universal interpolation theorem for semantic derivations [16, Theorem 5.1].

LK(CP) can be viewed as a two-sorted first-order theory of Z considered itself as a discretely ordered Z-module. One sort of variables are module elements, another sort are scalars. The quantification is allowed only over the former sort. We shall give a construction of a theory LK(M) for any discretely ordered module M (e.g., LK(Z) extends LK(CP)). The interpolation theorem generalizes to these theories obtained from discretely ordered Z-modules. We shall also discuss a connection to quantifier elimination for such theories.

We formulate a communication complexity problem whose (suitable) solution would allow to improve the monotone interpolation theorem and the lower bound for R(CP).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 63 , Issue 4 , December 1998 , pp. 1582 - 1596
Copyright
Copyright © Association for Symbolic Logic 1998

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] Alon, N. and Boppana, R., The monotone circuit complexity of Boolean functions, Combinatorica, vol. 7(1) (1987), pp. 1–22.Google Scholar
[2] Andreev, A.E., On a method for obtaining lower bounds for the complexity of individual monotone functions, Doklady AN SSSR, vol. 282(5) (1985), pp. 1033–1037.Google Scholar
[3] Babai, L., Gál, A., Kollár, J., Rónyai, L., Szabó, T., and Wigderson, A., Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs, Proceedings of the 28th annual ACM Symposium on theory of computing, 1996, pp. 603–611.Google Scholar
[4] Bonet, M.L., Pitassi, T., and Raz, R., Lower bounds for cutting planes proofs with small coefficients, Proceedings of the 27th annual ACM Symposium on theory of computing, 1995, pp. 575–589.Google Scholar
[5] Buss, S., Impagliazzo, R., Krajíček, J., Pudlák, P., Razborov, A.A., and Sgall, J., Proof complexity in algebraic systems and constant depth Frege systems with modular counting, Computational Complexity, vol. 6 (1996/1997), pp. 256–298.Google Scholar
[6] Clegg, M., Edmonds, J., and Impagliazzo, R., Using the Groebner basis algorithm to find proofs of unsatisfiability, Proceedings of the 28th annual ACM Symp. on theory of computing, ACM Press, 1996, pp. 174–183.Google Scholar
[7] Cook, S.A. and Reckhow, A.R., The relative efficiency of propositional proof systems, this Journal, vol. 44(1) (1979), pp. 36–50.Google Scholar
[8] Cook, W., Coullard, C. R., and Túrán, G., On the complexity of cutting plane proofs, Discrete Applied Mathematics, vol. 18 (1987), pp. 25–38.Google Scholar
[9] Fisher, M.J. and Rabin, M.O., Superexponential complexity of Presburger's arithmetic, SIAM-AMS Proceedings, vol. 7 (1974), pp. 27–41.Google Scholar
[10] Haken, A. and Cook, S.A., An exponential lower bound for the size of monotone real circuits, Journal of Computer and System Science (1995), to appear.Google Scholar
[11] Impagliazzo, R. and Pitassi, T., Interpolation for generalized cutting planes proof systems, a report in the CZ–US email seminar written by Pitassi, T., 1996.Google Scholar
[12] Karchmer, M. and Wigderson, A., Monotone circuits for connectivity require super-logarithmic depth, Proceedings of the 20th annual ACM Symposium on theory of computing, ACM Press, 1988, pp. 539–550.Google Scholar
[13] Krajíček, J., Lower bounds to the size of constant-depth propositionai proofs, this Journal, vol. 59(1) (1994), pp. 73–86.Google Scholar
[14] Krajíček, J., Bounded arithmetic, propositionai logic and complexity theory, Cambridge University Press, 1995.Google Scholar
[15] Krajíček, J., Interpolation by a game, Mathematical Logic Quarterly (1996), to appear.Google Scholar
[16] Krajíček, J., Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, this Journal, vol. 62(2) (1997), pp. 457–486.Google Scholar
[17] Krajíček, J. and Pudlák, P., Some consequences of cryptographical conjectures for S 2 1 and EF, Logic and computational complexity (Leivant, D., editor), Lecture Notes in Computer Science, vol. 960, Springer-Verlag, 1995, Proceedings of the meeting held in Indianapolis, 10 1994, pp. 210–220.Google Scholar
[18] Lenstra, H.W., Integer programming with a fixed number of variables, Mathematics of Operations Research, vol. 8 (1983), pp. 538–548.CrossRefGoogle Scholar
[19] Lovász, L., Algorithmic theory of numbers, graphs and convexity, CBMS–NSF Regional conferences series in applied mathematics, Society for Industrial and Applied mathematics, Philadelphia, 1986.Google Scholar
[20] Pudlák, P., Lower bounds for resolution and cutting planes proofs and monotone computations, this Journal, vol. 62 (1997), pp. 605–633.Google Scholar
[21] Pudlák, P. and Sgall, J., Algebraic models of computation, and interpolation for algebraic proof systems, Proof complexity and feasible arithmetic (Buss, S. R., editor), Lecture Notes in Computer Science, DIMACS series in Discrete Mathematics and Theoretical Computer Science, vol. 39, Springer-Verlag, 1998, pp. 279–295.Google Scholar
[22] Razborov, A.A., Lower bounds on the monotone complexity of some Boolean functions, Soviet Mathematics. Doklady, vol. 31 (1985), pp. 354–357.Google Scholar
[23] Razborov, A.A., Unprovability of lower bounds on the circuit size in certain fragments of bounded arithmetic, Izvestiya of the R.A.N., vol. 59(1) (1995), pp. 201–224.Google Scholar
[24] Rosenbloom, A., Monotone real circuits are more powerful than monotone boolean circuits, Information Processing Letters, vol. 61 (1997), pp. 161–164.Google Scholar
[25] Takeuti, G., Proof theory, North-Holland, 1975.Google Scholar
[26] van den Dries, L. and Holly, J., Quantifier elimination for modules with scalar variables, Annals of Pure and Applied Logic, vol. 57 (1992), pp. 161–179.Google Scholar