{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:11Z","timestamp":1781078291229,"version":"3.54.1"},"reference-count":24,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Math. Log."],"published-print":{"date-parts":[[2011,6]]},"abstract":"<jats:p> Let g be a map defined as the Nisan\u2013Wigderson generator but based on an NP \u2229 coNP -function f. Any string b outside the range of g determines a propositional tautology \u03c4(g)<jats:sub>b<\/jats:sub> expressing this fact. Razborov [27] has conjectured that if f is hard on average for P\/poly then these tautologies have no polynomial size proofs in the Extended Frege system EF. <\/jats:p><jats:p> We consider a more general Statement (S) that the tautologies have no polynomial size proofs in any propositional proof system. This is equivalent to the statement that the complement of the range of g contains no infinite NP set. <\/jats:p><jats:p> We prove that Statement (S) is consistent with Cook' s theory PV and, in fact, with the true universal theory T<jats:sub> PV <\/jats:sub> in the language of PV. If PV in this consistency statement could be extended to \"a bit\" stronger theory (properly included in Buss's theory [Formula: see text]) then Razborov's conjecture would follow, and if T<jats:sub>PV<\/jats:sub> could be added too then Statement (S) would follow. <\/jats:p><jats:p> We discuss this problem in some detail, pointing out a certain form of reflection principle for propositional logic, and we introduce a related feasible disjunction property of proof systems. <\/jats:p>","DOI":"10.1142\/s0219061311000979","type":"journal-article","created":{"date-parts":[[2011,9,12]],"date-time":"2011-09-12T13:56:16Z","timestamp":1315835776000},"page":"11-27","source":"Crossref","is-referenced-by-count":14,"title":["ON THE PROOF COMPLEXITY OF THE NISAN\u2013WIGDERSON GENERATOR BASED ON A HARD <font>NP<\/font> \u2229 <font>coNP<\/font> FUNCTION"],"prefix":"10.1142","volume":"11","author":[{"given":"JAN","family":"KRAJ\u00cd\u010cEK","sequence":"first","affiliation":[{"name":"Department of Algebra, Faculty of Mathematics and Physics, Charles University, Sokolovsk\u00e1 83, Prague 8, CZ \u2013 186 75, The Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"rf4","volume-title":"Bounded Arithmetic","author":"Buss S. R.","year":"1986"},{"key":"rf5","unstructured":"A.\u00a0Cobham, Proc. Logic, Methodology and Philosophy of Science, ed. Y.\u00a0Bar-Hillel (North-Holland, 1965)\u00a0pp. 24\u201330."},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511676277"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"rf9","volume":"7","author":"Cook S. A","journal-title":"ACM Trans. Comput. Log."},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891"},{"key":"rf11","unstructured":"J.\u00a0Hastad, Randomness and Computation, Advances in Computing Research\u00a05, ed. S.\u00a0Micali (JAI Press, 1989)\u00a0pp. 143\u2013170."},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.12.003"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.4064\/fm170-1-8"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.2307\/2687774"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1080938841"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.4064\/fm182-2-7"},{"key":"rf18","series-title":"London Mathematical Society Lecture Notes Series","volume-title":"Forcing with Random Variables in Bounded Arithmetic, and proof Complexity","volume":"382","author":"Kraj\u00ed\u010dek J.","year":"2011"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.2307\/2274765"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2674"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029595"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90043-L"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1002\/malq.201010012"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(98)80023-2"},{"key":"rf26","first-page":"598","volume":"41","author":"Razborov A. A.","journal-title":"Mat. Z."},{"key":"rf30","volume":"40","author":"Viola E.","journal-title":"ACM SIGACT News"}],"container-title":["Journal of Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219061311000979","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:31:42Z","timestamp":1565094702000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219061311000979"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6]]},"references-count":24,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2011,6]]}},"alternative-id":["10.1142\/S0219061311000979"],"URL":"https:\/\/doi.org\/10.1142\/s0219061311000979","relation":{},"ISSN":["0219-0613","1793-6691"],"issn-type":[{"value":"0219-0613","type":"print"},{"value":"1793-6691","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6]]}}}