Nisan-Wigderson generators in proof systems with forms of interpolation
Ján Pich · Mathematical logic quarterly · 2011
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. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim