A Note on Closeness between NP-Hard Sets and C=P  

作　　者：刘田 

出　　处：《Journal of Computer Science & Technology》2000年第2期194-195,共2页计算机科学技术学报（英文版）

基　　金：the National Key Project of China!98-780-01-05

摘　　要：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.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.

关 键 词：NP-HARD exact counting CLOSENESS quantum computation 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]