2014/01/25 by Peng Cui, Cui, Peng · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #F.1.3 #F.2.2 #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.CC
paper · pdf · doi:10.48550/arxiv.1401.6520
6 pages, short note
openalex publication_date 2014/01/25 · arxiv created 2015/11/09 · arxiv updated 2015/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.