Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator
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...
| Hoofdauteur: | |
|---|---|
| Formaat: | Artikel |
| Taal: | English |
| Gepubliceerd in: |
Logical Methods in Computer Science e.V.
2012-08-01
|
| Reeks: | Logical Methods in Computer Science |
| Onderwerpen: | |
| Online toegang: | https://lmcs.episciences.org/788/pdf |