On the proof complexity of the Nisan-Wigderson generator

Abstrakt

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.

Klíčová slova

• proof
• complexity
• Nisan-Wigderson
• generator