Disjoint NP-Pairs

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Christian Gla?er Articles by Alan L. Selman Articles by Samik Sengupta Articles by Liyu Zhang

18th Annual IEEE Conference on Computational Complexity (CCC'03)

Disjoint NP-Pairs

Aarhus, Denmark

July 07-July 10

ISBN: 0-7695-1879-6

	ASCII Text	x
	Christian Gla?er, Alan L. Selman, Samik Sengupta, Liyu Zhang, "Disjoint NP-Pairs," Computational Complexity, Annual IEEE Conference on, pp. 313, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003.

	BibTex	x
	@article{ 10.1109/CCC.2003.1214430, author = {Christian Gla?er and Alan L. Selman and Samik Sengupta and Liyu Zhang}, title = {Disjoint NP-Pairs}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2003}, issn = {1093-0159}, pages = {313}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214430}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - Disjoint NP-Pairs SN - 1093-0159 SP EP A1 - Christian Gla?er, A1 - Alan L. Selman, A1 - Samik Sengupta, A1 - Liyu Zhang, PY - 2003 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Christian Gla?er, University at Buffalo, Buffalo, NY 14260

Alan L. Selman, University at Buffalo, Buffalo, NY 14260

Samik Sengupta, University at Buffalo, Buffalo, NY 14260

Liyu Zhang, University at Buffalo, Buffalo, NY 14260

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214430

We study the question of whether the class DisNP of disjoint pairs (A,B) of NP-sets contains a complete pair. The question relates to the question of whether optimal proof systems exist, and we relate it to the previously studied question of whether there exists a disjoint pair of NP-sets that is NP-hard. We show under reasonable hypotheses that nonsymmetric disjoint NP-pairs exist, which provides additional evidence for the existence of P-inseparable disjoint NP-pairs.

We construct an oracle relative to which the class of disjoint NP-pairs does not have a complete pair, an oracle relative to which optimal proof systems exist, hence complete pairs exist, but no pair is NP-hard, and an oracle relative to which complete pairs exist, but optimal proof systems do not exist.

Citation:

Christian Gla?er, Alan L. Selman, Samik Sengupta, Liyu Zhang, "Disjoint NP-Pairs," ccc, pp.313, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.