Partial Bi-immunity and NP-Completeness

	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 John M. Hitchcock Articles by A. Pavan Articles by N. V. Vinodchandran

19th Annual IEEE Conference on Computational Complexity (CCC'04)

Amherst, Massachusetts

June 21-June 24

ISBN: 0-7695-2120-7

	ASCII Text	x
	John M. Hitchcock, A. Pavan, N. V. Vinodchandran, "Partial Bi-immunity and NP-Completeness," Computational Complexity, Annual IEEE Conference on, pp. 198-203, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004.

	BibTex	x
	@article{ 10.1109/CCC.2004.1313842, author = {John M. Hitchcock and A. Pavan and N. V. Vinodchandran}, title = {Partial Bi-immunity and NP-Completeness}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2004}, issn = {1093-0159}, pages = {198-203}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313842}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - Partial Bi-immunity and NP-Completeness SN - 1093-0159 SP198 EP203 A1 - John M. Hitchcock, A1 - A. Pavan, A1 - N. V. Vinodchandran, PY - 2004 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

John M. Hitchcock, University of Wyoming

A. Pavan, Iowa State University

N. V. Vinodchandran, University of Nebraska-Lincoln

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

The Turing and many-one completeness notions for NP have been previously separated under measure, genericity, and bi-immunity hypotheses on NP. The proofs of all these results rely on the existence of a language in NP with almost everywhere hardness.

In this paper we separate the same NP-completeness notions under a partial bi-immunity hypothesis that is weaker and only yields a language in NP that is hard to solve on most strings. This improves the results of Lutz and Mayordomo [15], Ambos-Spies and Bentzien [1], and Pavan and Selman [18]. The proof of this result is a significant departure from previous work.

Citation:

John M. Hitchcock, A. Pavan, N. V. Vinodchandran, "Partial Bi-immunity and NP-Completeness," ccc, pp.198-203, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004

Peer Review Notice | Give Us Feedback

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