ECCC-Report TR06-142https://eccc.weizmann.ac.il/report/2006/142Comments and Revisions published for TR06-142en-usThu, 23 Nov 2006 09:47:15 +0200
Paper TR06-142
| On the Deduction Theorem and Complete Disjoint NP-Pairs |
Olaf Beyersdorff
https://eccc.weizmann.ac.il/report/2006/142 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.
Thu, 23 Nov 2006 09:47:15 +0200https://eccc.weizmann.ac.il/report/2006/142