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

(整期优先)网络出版时间:2000-02-12
/ 1
Twosetsarecloseiftheirsymmetricdifferenceisasparseset.ItisshownthatNP-hardsetsarenotC=P-closeunlessNPC=P.Thisimprovesthepreviousresultandhasimplicationinquantumcomputation.