ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > EXTENDED FREGE SYSTEM:
Reports tagged with Extended Frege system:
TR03-055 | 20th July 2003
Jan Krajicek

Implicit proofs

We describe a general method how to construct from a propositional proof system P a possibly much stronger proof system iP. The system iP operates with exponentially long P-proofs described ``implicitly'' by polynomial size circuits. As an example we prove that proof system iEF, implicit EF, corresponds to bounded arithmetic ... more >>>



ISSN 1433-8092 | Imprint