Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-142 | 26th October 2006 00:00

On the Deduction Theorem and Complete Disjoint NP-Pairs

RSS-Feed




TR06-142
Authors: Olaf Beyersdorff
Publication: 23rd November 2006 09:47
Downloads: 1725
Keywords: 


Abstract:

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, then
the weak deduction theorem holds for EF.
Hence the weak deduction property for EF is a natural intermediate
condition between the optimality of EF and the completeness of its
canonical pair.
We also exhibit two conditions that imply the completeness of the
canonical pair of Frege systems.



ISSN 1433-8092 | Imprint