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

LIU Tian. A Note on Closeness between NP-Hard Sets and C=P[J]. Journal of Computer Science and Technology, 2000, 15(2): 194-195.

Citation:

LIU Tian. A Note on Closeness between NP-Hard Sets and C=P[J]. Journal of Computer Science and Technology, 2000, 15(2): 194-195.

Citation:

LIU Tian. A Note on Closeness between NP-Hard Sets and C=P[J]. Journal of Computer Science and Technology, 2000, 15(2): 194-195.

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.

FullText(HTML)

Export File