An exponential separation between the parity principle and the pigeonhole principle. (English) Zbl 0866.03029
Summary: The combinatorial parity principle states that there is no perfect matching on an odd number of vertices. This principle generalizes the pigeonhole principle, which states that for a fixed bipartition of the vertices, there is no perfect matching between them. Therefore, it follows from recent lower bounds for the pigeonhole principle that the parity principle requires exponential-size bounded-depth Frege proofs. M. Ajtai [Feasible mathematics, Proc. Math. Sci. Inst. Workshop, Ithaka/NY (USA) 1989, Prog. Comput. Sci. Appl. Log. 9, 1-24 (1990; Zbl 0781.03045)] previously showed that the parity principle does not have polynomial-size bounded-depth Frege proofs even with the pigeonhole principle as an axiom schema. His proof utilizes nonstandard model theory and is nonconstructive. We improve Ajtai’s lower bound from barely superpolynomial to exponential and eliminate the nonstandard model theory. Our lower bound is also related to the inherent complexity of particular search classes [C. H. Papadimitriou, Combinatorics, graphs and complexity, Proc. 4th Czech. Symp., Prachatice/Czech. 1990, Ann. Discrete Math. 51, 245-250 (1992; Zbl 0798.68058)]. In particular, oracle separations between the complexity classes PPA and PPAD, and between PPA and PPP also follow from our techniques [the authors et al., “The complexity of NP search problems”, Proc. 27th Ann. ACM Symp. Theory of Computing, Las Vegas/NV (USA), 303-314 (1995)].
MSC:
| 03F20 | Complexity of proofs |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
combinatorial parity principle; perfect matching; pigeonhole principle; Frege proofs; lower bound; search classes; oracle separationsReferences:
| [1] | Ajtai, M., The complexity of the pigeonhole principle, (Proc. 29th Ann. Symp. on Foundations of Computer Science. Proc. 29th Ann. Symp. on Foundations of Computer Science, White Plains, New York (1988), IEEE Press: IEEE Press New York), 346-355 · Zbl 0811.03042 |
| [2] | Ajtai, M., Parity and the pigeonhole principle, (Buss, S. R.; Scott, P. J., Feasible Mathematics, A Mathematical Sciences Institute Workshop. Feasible Mathematics, A Mathematical Sciences Institute Workshop, Ithaca, New York (1990), Birkhäuser: Birkhäuser Basel), 1-24 · Zbl 0781.03045 |
| [3] | Beame; Cook; Edmonds; Impagliazzo; Patalsi, The complexity of NP search porblems, (Proc. 27th Ann. ACM Symp. on Theory of Computing. Proc. 27th Ann. ACM Symp. on Theory of Computing, Las Vegas, NV, USA (1995)), 303-314 · Zbl 0978.68526 |
| [4] | Beame, P. W.; Håstad, J., Optimal bounds for decision problems on the CRCW PRAM, J. ACM, 36, 643-670 (1989) · Zbl 0825.68378 |
| [5] | Beame, P. W.; Impagliazzo, R.; Krajíček, J.; Pitassi, T.; Pudlák, P.; Woods, A., Exponential lower bounds for the pigeonhole principle, (Proc. 24th Ann. ACM Symp. on Theory of Computing. Proc. 24th Ann. ACM Symp. on Theory of Computing, Victoria, BC, Canada (1992)), 200-220 |
| [6] | Beame, P.; Pitassi, T., An exponential separation between the matching principle and the pigeonhole principle, (Proc. 8th Ann. IEEE Symp. on Logic in Computer Science. Proc. 8th Ann. IEEE Symp. on Logic in Computer Science, Montreal, Quebec (1993)) · Zbl 0866.03029 |
| [7] | Bellantoni, S.; Pitassi, T.; Urquhart, A., Approximation and small depth Frege proofs, (Proc. Structure in Complexity Theory, 6th Ann. Conf.. Proc. Structure in Complexity Theory, 6th Ann. Conf., Chicago, IL (1991), IEEE Press: IEEE Press New York), 367-391 |
| [8] | Buss, S. R., Studies in Proof Theory, (Bounded Arithmetic, Vol. 3 (1986), Bibliopolis: Bibliopolis Napoli) · Zbl 0649.03042 |
| [9] | Buss, S. R., Polynomial size proofs of the pigeonhole principle, J. Symbolic Logic, 57, 916-927 (1987) · Zbl 0636.03053 |
| [10] | Cook, S. A.; Reckhow, R. A., The relative efficiency of propositional proof systems, J. Symbolic Logic, 44, 36-50 (1977) · Zbl 0408.03044 |
| [11] | Haken, A., The intractability of resolution, Theoret. Comput. Sci., 39, 297-305 (1985) · Zbl 0586.03010 |
| [12] | Håstad, J., ACM Doctoral Dissertation Award Series (1986) |
| [13] | Krajíček, J.; Pudlák, P.; Woods, A., Exponential lower bounds to the size of bounded-depth Frege proofs of the pigeonhole principle, Random Structures and Algorithms, 7, 15-39 (1995) · Zbl 0843.03032 |
| [14] | Papadimitriou, C. H., On inefficient proofs of existence and complexity classes, (Proc. 4th Czechoslovakian Symp. on Combinatorics (1991)) · Zbl 0798.68058 |
| [15] | Pitassi, T., The power of weak formal systems, (Ph.D. Thesis (August 1992), University of Toronto) |
| [16] | Pitassi, T.; Beame, P.; Impagliazzo, R., Exponential lower bounds for the pigeonhole principle, Comput. Complexity, 3, 97-140 (1993) · Zbl 0784.03034 |
| [17] | Paris, J.; Wilkie, A., Counting problems in bounded arithmetic, (Methods in Mathematical Logic: Proc. 6th Latin American Symposium on Mathematical Logic. Methods in Mathematical Logic: Proc. 6th Latin American Symposium on Mathematical Logic, 1983. Methods in Mathematical Logic: Proc. 6th Latin American Symposium on Mathematical Logic. Methods in Mathematical Logic: Proc. 6th Latin American Symposium on Mathematical Logic, 1983, Lecture Notes in Mathematics, Vol. 1130 (1985), Springer: Springer Berlin), 317-340 · Zbl 0572.03034 |
| [18] | Urquhart, A., Hard examples for resolution, J. ACM, 34, 209-219 (1987) · Zbl 0639.68093 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
