loading...
Partial Bi-immunity and NP-Completeness
Amherst, Massachusetts June 21-June 24
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2004.131384219th Annual IEEE Conference on Comput ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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

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
Usage of this product signifies your acceptance of the Terms of Use.