Lower Bounds for Polynomial Calculus: Nonbinomial Case

M. V. Alekhnovich ; A. A. Razborov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Mathematical logic and algebra, Tome 242 (2003), pp. 23-43.

Résumé

We generalize recent linear lower bounds for Polynomial Calculus based on binomial ideals. We produce a general hardness criterion (that we call immunity), which is satisfied by a random function, and prove linear lower bounds on the degree of PC refutations for a wide class of tautologies based on immune functions. As applications of our techniques, we introduce mod$_p$. Tseitin tautologies in the Boolean case (e.g. in the presence of axioms $x_i^2=x_i$), prove that they are hard for PC over fields with characteristic different from $p$, and generalize them to the flow tautologies that are based on the majority function and are proved to be hard over any field. We also prove the $\Omega(n)$ lower bound for random $k$-CNFs over fields of characteristic 2.

Bibliographie

[1] Alekhnovich M., Ben-Sasson E., Razborov A., Wigderson A., “Space complexity in propositional calculus”, SIAM J. Comput., 31:4 (2002), 1184–1211 | DOI | MR | Zbl

[2] Alekhnovich M., Ben-Sasson E., Razborov A., Wigderson A., “Pseudorandom generators in propositional complexity”, Proc. 41st IEEE Symp. on Foundations of Computer Science (2000. Los Alamitos, CA), IEEE Comput. Soc. Press, 2000, 43–53 ; SIAM J. Comput. (to appear) | MR

[3] Alon N., “Spectral techniques in graph algorithms”, LATIN '98. Theoretical Informatics, Proc. 3rd Latin Amer. Symp. (Brazil, 1998), Lect. Notes Comput. Sci., 1380, eds. C. L. Lucchesi, A. V. Moura, Springer, Berlin, 1998, 206–215 | MR | Zbl

[4] Aspnes J., Beigel R., Furst M., Rudich S., “The expressive power of voting polynomials”, Combinatorica, 14:2 (1994), 1–14 | DOI | MR

[5] Beame P., Impagliazzo R., Krajíček J., Pitassi T., Pudlák P., “Lower bounds on Hilbert's Nullstellensatz and propositional proofs”, Proc. London Math. Soc., 73 (1996), 1–26 | DOI | MR | Zbl

[6] Beame P., Karp R., Pitassi T., Saks M., “On the complexity of unsatisfiability of random $k$-cnf formulas”, Proc. 30th ACM Symp. on Theory of Computing, 1998, ACM, New York, 1998, 561–571 | MR | Zbl

[7] Beame P., Pitassi T., “Simplified and improved resolution lower bounds” (1996, Los Alamitos, CA), Proc. 37th IEEE Symp. on Foundations of Computer Science, 1996, 274–282, IEEE Comput. Soc. Press | MR

[8] Beame P., Pitassi T., “Propositional proof complexity: Past, present and future”, Tech. Rept. TR98-067, El. Colloq. Comput. Complex., 1998, Bull. Eur. Assoc. Theor. Comput. Sci., 1998, no. 65, 66–89 | MR | Zbl

[9] Ben-Sasson E., Impagliazzo R., “Random CNF's are hard for the polynomial calculus”, Proc. 40th IEEE Symp. on Foundations of Computer Science (1999, Los Alamitos, CA), IEEE Comput. Soc. Press, 1999, 415–421 | MR

[10] Ben-Sasson E., Wigderson A., “Short proofs are narrow—resolution made simple”, Proc. 31st ACM Symp. on Theory of Computing (1999), ACM, New York, 1999, 517–526 | MR

[11] Buss S., Grigoriev D., Impagliazzo R., Pitassi T., “Linear gaps between degrees for the polynomial calculus modulo distinct primes”, Proc. 31st ACM Symp. on Theory of Computing (1999), ACM, New York, 1999, 547–556 | MR

[12] Buss S., Impagliazzo R., Krajíček J., Pudlák P., Razborov A., Sgall J., “Proof complexity in algebraic systems and bounded depth Frege systems with modular counting”, Comput. Complex., 6:3 (1996/1997), 256–298 | DOI | MR

[13] Bussemaker F. C., Cvetković D. M., Seidel J. J., “Graphs related to exceptional root systems”, Combinatorics, Colloq. Math. Soc. J. Bolyai, 18, eds. A. Hajnal, V. T. Sós, North-Holland, Amsterdam, 1978, 185–191 | MR

[14] Chvátal V., Szemerédi E., “Many hard examples for resolution”, J. Assoc. Comput. Mach., 35:4 (1988), 759–768 | MR | Zbl

[15] Clegg M., Edmonds J., Impagliazzo R., “Using the Groebner basis algorithm to find proofs of unsatisfiability”, Proc. 28th ACM Symp. on Theory of Computing (1996), ACM, New York, 1996, 174–183 | MR | Zbl

[16] Green F., “A complex-number Fourier technique for lower bounds on the MOD-$m$ degree”, Comput. Complex., 9:1 (2000), 16–38 | DOI | MR | Zbl

[17] Grigoriev D., “Nullstellensatz lower bounds for Tseitin tautologies”, Proc. 39th IEEE Symp. on Foundations of Computer Science (1998, Los Alamitos, CA), IEEE Comput. Soc. Press, 1998, 648–652

[18] Grigoriev D., “Linear lower bounds on degrees of Postivestellensatz calculus proofs for the parity”, Theor. Comput. Sci., 259 (2001), 613–622 | DOI | MR | Zbl

[19] Impagliazzo R., Pudlák P., Sgall J., “Lower bounds for the polynomial calculus and the Groebner basis algorithm”, Comput. Complex., 8:2 (1999), 127–144 | DOI | MR | Zbl

[20] Krajíček J., “On the degree of ideal membership proofs from uniform families of polynomials over a finite field”, Ill. J. Math., 45:1 (2001), 41–73 | MR | Zbl

[21] Lubotzky A., Phillips R., Sarnak P., “Ramanujan graphs”, Combinatorica, 8 (1988), 261–277 | DOI | MR | Zbl

[22] Margulis G. A., “Yavnye teoretiko-gruppovye konstruktsii kombinatornykh skhem i ikh primeneniya v postroenii rasshiritelei i kontsentratorov”, Problemy peredachi informatsii, 24 (1988), 51–60 | MR | Zbl

[23] Razborov A., “Lower bounds for propositional proofs and independence results in bounded arithmetic”, Proc. 23rd ICALP, Lect. Notes Comput. Sci., 1099, Springer, New York, Berlin, 1996, 48–62 | MR | Zbl

[24] Razborov A., “Lower bounds for the polynomial calculus”, Comput. Complex., 7 (1998), 291–324 | DOI | MR | Zbl

[25] Razborov A., Rudich S., “Natural proofs”, J. Comput. and Syst. Sci., 55:1 (1997), 24–35 | DOI | MR | Zbl

[26] Tsai S.-C., “Lower bounds on representing Boolean functions as polynomials in $\mathbb{Z}_m$”, SIAM J. Discr. Math., 9 (1996), 55–62 | DOI | MR | Zbl

[27] Tseitin G. S., “O slozhnosti vyvoda v ischislenii vyskazyvanii”, Zap. nauch. seminarov LOMI, 8, 1968, 234–259