On the proof complexity of the Nisan-Wigderson generator

Abstract

We prove the consistency of a statement generalizing Razborov''s conjecture from proof complexity with the true universal theory in the language of Cook''s theory PV.

Keywords

• proof
• complexity
• Nisan-Wigderson
• generator