Approximation Resistance by Disguising Biased Distributions
Peng Cui
所有作者
Peng Cui
文献摘要
In this short note, the author shows that the gap problem of some 3-XOR is
NP-hard and can be solved by running Charikar&Wirth’s SDP algorithm for two
rounds. To conclude, the author proves that P=NP.