Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR04-082 | 21st January 2005 00:00

Representable Disjoint NP-Pairs

RSS-Feed




Revision #1
Authors: Olaf Beyersdorff
Accepted on: 21st January 2005 00:00
Downloads: 2741
Keywords: 


Abstract:

We correct a mistake in the proof of Proposition 17 and add Corollary 20
as an immediate but interesting consequence.


Paper:

TR04-082 | 9th September 2004 00:00

Representable Disjoint NP-Pairs





TR04-082
Authors: Olaf Beyersdorff
Publication: 20th September 2004 17:08
Downloads: 3127
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint