Nisan-Wigderson generatos in proof systems with forms of interpolation

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.

Keywords

• Nisan-Wigderson
• generatos
• proof
• systems
• with
• forms
• interpolation