ECCC-Report TR04-082https://eccc.weizmann.ac.il/report/2004/082Comments and Revisions published for TR04-082en-usFri, 21 Jan 2005 00:00:00 +0200
Revision 1
| Representable Disjoint NP-Pairs |
Olaf Beyersdorff
https://eccc.weizmann.ac.il/report/2004/082#revision1We correct a mistake in the proof of Proposition 17 and add Corollary 20
as an immediate but interesting consequence.
Fri, 21 Jan 2005 00:00:00 +0200https://eccc.weizmann.ac.il/report/2004/082#revision1
Paper TR04-082
| Representable Disjoint NP-Pairs |
Olaf Beyersdorff
https://eccc.weizmann.ac.il/report/2004/082We investigate the class of disjoint NP-pairs under different reductions.
The structure of this class is intimately linked to the simulation order
of propositional proof systems, and we make use of the relationship between
propositional proof systems and theories of bounded arithmetic as the main
tool of our analysis.
Specifically we exhibit a pair which is complete under strong reductions
for all disjoint NP-pairs representable in a theory. We use these pairs
to explain the simulation order of NP-pairs under these reductions.
Mon, 20 Sep 2004 17:08:28 +0300https://eccc.weizmann.ac.il/report/2004/082