TR10-046 | 22nd March 2010 18:50
Nisan-Wigderson generators in proof systems with forms of interpolation
TR10-046
Authors:
Ján Pich
Publication: 23rd March 2010 10:45
Downloads: 3463
Keywords:
Abstract:
We prove that the Nisan-Wigderson generators based on computationally hard functions and suitable matrices are hard for propositional proof systems that admit feasible interpolation.