Structured Pigeonhole Principle, Search Problems and Hard Tautologies
Journal of Symbolic Logic 70 (2):619 - 630 (2005)
| Abstract | We consider exponentially large finite relational structures (with the universe {0.1}ⁿ) whose basic relations are computed by polynomial size (nO(1)) circuits. We study behaviour of such structures when pulled back by P/poly maps to a bigger or to a smaller universe. In particular, we prove that: 1. If there exists a P/poly map g: {0.1} → {0.1}m, n < m, iterable for a proof system then a tautology (independent of g) expressing that a particular size n set is dominating in a size 2ⁿ tournament is hard for the proof system. 2. The search problem WPHP, decoding RSA or finding a collision in a hashing function can be reduced to finding a size m homogeneous subgraph in a size 22m graph. Further we reduce the proof complexity of a concrete tautology (expressing a Ramsey property of a graph) in strong systems to the complexity of implicit proofs of implicit formulas in weak proof systems | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,664 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesJan Krajíček (2004). Dual Weak Pigeonhole Principle, Pseudo-Surjective Functions, and Provability of Circuit Lower Bounds. Journal of Symbolic Logic 69 (1):265 - 286.
Samuel R. Buss (1987). Polynomial Size Proofs of the Propositional Pigeonhole Principle. Journal of Symbolic Logic 52 (4):916-927.
Jan Krajíček (2004). Implicit Proofs. Journal of Symbolic Logic 69 (2):387 - 397.
Jan Krajiček (1994). Lower Bounds to the Size of Constant-Depth Propositional Proofs. Journal of Symbolic Logic 59 (1):73-86.
Jan Krajíček (1995). Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press.
Jan Krajíček (1997). Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic. Journal of Symbolic Logic 62 (2):457-486.
Pavel Hrubeš (2007). Lower Bounds for Modal Logics. Journal of Symbolic Logic 72 (3):941-958.
Mario Chiari & Jan Krajíček (1998). Witnessing Functions in Bounded Arithmetic and Search Problems. Journal of Symbolic Logic 63 (3):1095-1115.
A. Carbone (2002). The Cost of a Cycle is a Square. Journal of Symbolic Logic 67 (1):35-60.
Marcin Mostowski & Jakub Szymanik (2007). Computational Complexity of Some Ramsey Quantifiers in Finite Models. The Bulletin of Symbolic Logic 13:281--282.
Juris Steprāns (2005). Geometric Cardinal Invariants, Maximal Functions and a Measure Theoretic Pigeonhole Principle. Bulletin of Symbolic Logic 11 (4):517-525.
Michael Alekhnovich, Sam Buss, Shlomo Moran & Toniann Pitassi (2001). Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. Journal of Symbolic Logic 66 (1):171-191.
Andreas Blass (1995). An Induction Principle and Pigeonhole Principles for K-Finite Sets. Journal of Symbolic Logic 60 (4):1186-1193.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2010-08-24Total downloads1 ( #274,602 of 549,007 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
