A Note on Closeness between NP-Hard Sets and C=P
刘田 · 2000
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 NPC=P.This improves the previous result and has implication in quantum computation.