Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DEDUCTION THEOREM:
Reports tagged with Deduction Theorem:
TR06-142 | 26th October 2006
Olaf Beyersdorff

On the Deduction Theorem and Complete Disjoint NP-Pairs

In this paper we ask the question whether the extended Frege proof
system EF satisfies a weak version of the deduction theorem. We
prove that if this is the case, then complete disjoint NP-pairs
exist. On the other hand, if EF is an optimal proof system, ... more >>>




ISSN 1433-8092 | Imprint