Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator

DOI10.2168/LMCS-8(3:9)2012zbMATH Open1256.68079arXiv1207.0393MaRDI QIDQ2904626

Publication date: 15 August 2012

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1207.0393

zbMATH Keywords

hard core interactive computation nonstandard model of arithmetic Nisan-Wigderson generator

Mathematics Subject Classification ID

2-person games (91A05) Applications of game theory (91A80) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonstandard models of arithmetic (03H15) Complexity of proofs (03F20)

This page was built for publication: Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904626)