{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:35:57Z","timestamp":1753889757058,"version":"3.41.2"},"reference-count":11,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,8,13]],"date-time":"2012-08-13T00:00:00Z","timestamp":1344816000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>For an NP intersect coNP function g of the Nisan-Wigderson type and a string b outside its range we consider a two player game on a common input a to the function. One player, a computationally limited Student, tries to find a bit of g(a) that differs from the corresponding bit of b. He can query a computationally unlimited Teacher for the witnesses of the values of constantly many bits of g(a). The Student computes the queries from a and from Teacher's answers to his previous queries. It was proved by Krajicek (2011) that if g is based on a hard bit of a one-way permutation then no Student computed by a polynomial size circuit can succeed on all a. In this paper we give a lower bound on the number of inputs a any such Student must fail on. Using that we show that there is a pseudo-finite set of hard instances on which all uniform students must fail. The hard-core set is defined in a non-standard model of true arithmetic and has applications in a forcing construction relevant to proof complexity.<\/jats:p>","DOI":"10.2168\/lmcs-8(3:9)2012","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T08:17:46Z","timestamp":1385713066000},"source":"Crossref","is-referenced-by-count":2,"title":["Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator"],"prefix":"10.46298","volume":"Volume 8, Issue 3","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2012,8,13]]},"reference":[{"key":"10.2168\/LMCS-8(3:9)2012_Boo","unstructured":"G. Boole.The mathematical analysis of logic. Barclay and Macmillan, Cambridge, 1847."},{"key":"10.2168\/LMCS-8(3:9)2012_Imp","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo. Hard-Core Distributions for Somewhat Hard Problems. 36th Annual Symp. on Foundations of Computer Science, Milwaukee, Wisconsin, 23-25 October 1995, IEEE Computer Society, 538-545, 1995.","DOI":"10.1109\/SFCS.1995.492584"},{"key":"10.2168\/LMCS-8(3:9)2012_kniha","doi-asserted-by":"crossref","unstructured":"J. Kraj\u00edcek.Bounded arithmetic, propositional logic, and complexity theory. Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Vol.60, 1995.","DOI":"10.1017\/CBO9780511529948"},{"key":"10.2168\/LMCS-8(3:9)2012_k2","unstructured":"J. Kraj\u00edcek.Forcing with random variables and proof complexity. London Mathematical Society Lecture Notes Series, Cambridge University Press, Vol.382, 2011."},{"key":"10.2168\/LMCS-8(3:9)2012_Kra-nwg","doi-asserted-by":"crossref","unstructured":"J. Kraj\u00edcek. On the proof complexity of the Nisan-Wigderson generator based on a hardpcofunction.J. Mathematical Logic, 11(1): 11-27, 2011.","DOI":"10.1142\/S0219061311000979"},{"key":"10.2168\/LMCS-8(3:9)2012_Kra-satur","doi-asserted-by":"crossref","unstructured":"J. Kraj\u00edcek. A saturation property of structures obtained by forcing with a compact family of random variables. submitted preprint, 2012.","DOI":"10.1007\/s00153-012-0304-9"},{"key":"10.2168\/LMCS-8(3:9)2012_KPS","unstructured":"J. Kraj\u00edcek, P. Pudl\u00e1k, and J. Sgall. Interactive Computations of Optimal Solutions. in: B. Rovan (ed.):Mathematical Foundations of Computer Science(B. Bystrica, August '90), Lecture Notes in Computer Science, Springer-Verlag, 452:48-60, 1990."},{"key":"10.2168\/LMCS-8(3:9)2012_NW","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan and A. Wigderson","year":"1994","journal-title":"J. Comput. System Sci."},{"key":"10.2168\/LMCS-8(3:9)2012_RS1","doi-asserted-by":"crossref","first-page":"62","DOI":"10.4064\/fm-40-1-62-95","volume":"40","author":"H. Rasiowa and R. Sikorski","year":"1953","journal-title":"Fundamenta Mathematicae"},{"key":"10.2168\/LMCS-8(3:9)2012_Raz03","unstructured":"A. A. Razborov. Pseudorandom generators hard fork-DNF resolution and polynomial calculus resolution. unpublished preprint, 2003."},{"key":"10.2168\/LMCS-8(3:9)2012_Rud","unstructured":"S. Rudich. Super-bits, demi-bits, and~NP\/qpoly-natural proofs. in:Proc. of the 1st Int.Symp. on Randomization and Approximation Techniques in Computer Science, LN in Comp.Sci., Springer-Verlag, 1269:85-93, 1997."}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/788\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/788\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T00:26:22Z","timestamp":1746059182000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/788"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,13]]},"references-count":11,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(3:9)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1207.0393","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1207.0393","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,8,13]]},"article-number":"788"}}