Nisan-Wigderson generatos in proof systems with forms of interpolation

Abstrakt

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.

Klíčová slova

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