{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T11:31:30Z","timestamp":1777548690247,"version":"3.51.4"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3206,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider exponentially large finite relational structures (with the universe {0, 1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>) whose basic relations are computed by polynomial size (<jats:italic>n<\/jats:italic><jats:sup><jats:italic>O<\/jats:italic>(1)<\/jats:sup>) circuits. We study behaviour of such structures when pulled back by <jats:italic>P\/poly<\/jats:italic> maps to a bigger or to a smaller universe. In particular, we prove that:<\/jats:p><jats:p>1. If there exists a <jats:italic>P\/poly<\/jats:italic> map <jats:italic>g<\/jats:italic>: {0, 1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> \u2192 {0, 1}<jats:sup><jats:italic>m<\/jats:italic><\/jats:sup>, <jats:italic>n<\/jats:italic> &lt; <jats:italic>m<\/jats:italic>, iterable for a proof system then a tautology (independent of <jats:italic>g<\/jats:italic>) expressing that a particular size n set is dominating in a size 2<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> tournament is hard for the proof system.<\/jats:p><jats:p>2. The search problem WPHP. decoding RSA or finding a collision in a hashing function can be reduced to finding a size <jats:italic>m<\/jats:italic> homogeneous subgraph in a size 2<jats:sup>2<jats:italic>m<\/jats:italic><\/jats:sup> graph.<\/jats:p><jats:p>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.<\/jats:p>","DOI":"10.2178\/jsl\/1120224731","type":"journal-article","created":{"date-parts":[[2005,7,1]],"date-time":"2005-07-01T15:05:58Z","timestamp":1120230358000},"page":"619-630","source":"Crossref","is-referenced-by-count":8,"title":["Structured pigeonhole principle, search problems and hard tautologies"],"prefix":"10.1017","volume":"70","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007106_ref020","first-page":"553","volume-title":"Proceedings of the 34th STOC","author":"Raz","year":"2002"},{"key":"S0022481200007106_ref025","volume-title":"Cryptography: theory and practice","author":"Stinson","year":"1995"},{"key":"S0022481200007106_ref021","first-page":"149","article-title":"Formulas of bounded depth in the basis (and,\u2295) andsome combinatorial problems","volume":"134","author":"Razborov","year":"1988","journal-title":"Voprosy Kibemetiki"},{"key":"S0022481200007106_ref017","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2674"},{"key":"S0022481200007106_ref024","unstructured":"Razborov A. A. , Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution, preprint, May 2003."},{"key":"S0022481200007106_ref016","first-page":"1063","volume":"54","author":"Kraj\u00cd\u010cek","year":"1989","journal-title":"Propositional proof systems, the consistency of first order theories and the complexity of computations"},{"key":"S0022481200007106_ref011","doi-asserted-by":"publisher","DOI":"10.4064\/fm170-1-8"},{"key":"S0022481200007106_ref007","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08785-1"},{"key":"S0022481200007106_ref005","first-page":"83","volume-title":"Proceedings 7th Annual ACM Symposium on Theory of Computing","author":"Cook","year":"1975"},{"key":"S0022481200007106_ref001","article-title":"Pseudorandom generators in propositional proof complexity","volume":"23","author":"Alekhnovich","year":"2000","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"S0022481200007106_ref022","first-page":"201","article-title":"Unprovability of lower bounds on the circuit size in certain fragments of bounded arithmetic","volume":"59","author":"Razborov","year":"1995","journal-title":"Rossi\u012dskaya Akademiya Nauk. Izvestiya. Seriya Matematicheskaya"},{"key":"S0022481200007106_ref003","first-page":"1095","volume":"63","author":"Chiari","year":"1998","journal-title":"Witnessing functions in hounded arithmetic and search problems"},{"key":"S0022481200007106_ref014","first-page":"265","volume":"69","author":"Kraj\u00cd\u010cek","year":"2004","journal-title":"Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds"},{"key":"S0022481200007106_ref009","doi-asserted-by":"crossref","unstructured":"Hanika J. , Search problems and bounded arithmetic, Ph.D. thesis, Charles University, 2004.","DOI":"10.1002\/malq.200410005"},{"key":"S0022481200007106_ref002","first-page":"303","article-title":"The relative complexity of NP search problems","author":"Beame","year":"1995","journal-title":"Proceedings 27th Annual ACM Symposium on the Theory of Computing"},{"key":"S0022481200007106_ref012","doi-asserted-by":"publisher","DOI":"10.2307\/2687774"},{"key":"S0022481200007106_ref013","doi-asserted-by":"publisher","DOI":"10.4064\/fm182-2-7"},{"key":"S0022481200007106_ref010","volume-title":"Encyclopedia of mathematics and its applications","volume":"60","author":"Kraj\u00cd\u010cek","year":"1995"},{"key":"S0022481200007106_ref018","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1830"},{"key":"S0022481200007106_ref004","doi-asserted-by":"publisher","DOI":"10.1007\/s001530050118"},{"key":"S0022481200007106_ref006","first-page":"36","volume":"44","author":"Cook","year":"1979","journal-title":"The relative efficiency of propositional proof systems"},{"key":"S0022481200007106_ref008","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200410005"},{"key":"S0022481200007106_ref023","first-page":"29","volume-title":"Proceedings of the 17th IEEE conference on computational complexity","author":"Razborov","year":"2002"},{"key":"S0022481200007106_ref015","first-page":"387","volume":"69","author":"Kraj\u00cd\u010cek","year":"2004","journal-title":"Implicit proofs"},{"key":"S0022481200007106_ref019","first-page":"1235","volume":"53","author":"Paris","year":"1988","journal-title":"Provability of the pigeonhole principle and the existence of infinitely many primes"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T20:50:18Z","timestamp":1556916618000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007106\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["S0022481200007106"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1120224731","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]}}}