Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2000, Vol. 15 Issue (2) :194-195    DOI:
Articles Current Issue | Archive | Adv Search << Previous Articles | Next Articles >>
A Note on Closeness between NP-Hard Sets and C=P
LIU Tian;
Department of Computer Science and Technology; Peking University; Beijing 100871; P.R. China;

Abstract
Reference
Related Articles
Download: [PDF 88KB]     Export: BibTeX or EndNote (RIS)  
Abstract Two sets are close if their symmetric difference is a sparse set. It is shown that NP-hard sets are not C=P-close unless NP C=C=P. This improves the previous result and has implication in quantum compulation.
Articles by authors
LIU Tian
KeywordsNP-hard   exact counting   closeness   quantum computation     
Revised 2000-03-10
Cite this article:   
LIU Tian;.A Note on Closeness between NP-Hard Sets and C=P[J]  Journal of Computer Science and Technology, 2000,V15(2): 194-195
URL:  
http://jcst.ict.ac.cn:8080/jcst/EN/
Copyright 2010 by Journal of Computer Science and Technology