01982523

j

01982523 Bonet, Maria Luisa Galesi, Nicola Degree complexity for a modified pigeonhole principle. Arch. Math. Logic 42, No.5, 403-414 (2003). 2003 Springer-Verlag, Berlin EN F.4.1 I.2.3 modified pigeonhole principle polynomial calculus resolution resolution upper bound degree lower bound Zbl 0745.68093 Zbl 1026.03043 Zbl 0946.68129 Zbl 0938.68825

doi:10.1007/s001530200141

Summary: We consider a modification of the pigeonhole principle, MPHP, introduced by {\it A. Goerdt} [Theor. Comput. Sci. 93, 159-167 (1992; Zbl 0745.68093)]. MPHP is defined over $n$ pigeons and $\log n$ holes, and more than one pigeon can go into a hole (according to some rules). Using a technique of {\it A. Razborov} [Comput. Complex. 7, 291-324 (1998; Zbl 1026.03043), reviewed above] and simplified by {\it R. Impagliazzo, P. Pudl\'ak} and {\it J. Sgall} [ibid. 8, 127-144 (1999; Zbl 0946.68129)], we prove that any polynomial calculus refutation of a set of polynomials encoding the MPHP, requires degree $\Omega(\log n)$. We also prove a simple lemma giving a simulation of resolution by polynomial calculus. Using this lemma, and a resolution upper bound by Goerdt [loc. cit.], we obtain that the degree lower bound is tight. Our lower bound establishes the optimality of the tree-like resolution simulation by the polynomial calculus given by {\it M. Clegg, J. Edmonds} and {\it R. Impagliazzo} [Proc. 28th annual ACM Symp. on the theory of computing (STOC), 1996. New York: ACM, 174-183 (1996; Zbl 0938.68825)].