arXiv Open Access 2014

Approximation Resistance by Disguising Biased Distributions

Peng Cui

Lihat Sumber

Abstrak

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$.

Topik & Kata Kunci

cs.CC

Penulis (1)

Peng Cui

Format Sitasi

APA MLA BibTeX

Cui, P. (2014). Approximation Resistance by Disguising Biased Distributions. https://arxiv.org/abs/1401.6520

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2014
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓