References

[GiggleLiu]

• 3 SAT and independent set: https://www.cs.umd.edu/class/fall2017/cmsc451-0101/Lects/lect20-np-3sat.pdf
• QUBO problems¹ (GitHub link)
• Independent set problem on KSG and independent set² (GitHub link).

Footnotes

1. Glover, F., Kochenberger, G., Du, Y., 2019. A Tutorial on Formulating and Using QUBO Models. ↩

2. Nguyen, M.-T., Liu, J.-G., Wurtz, J., Lukin, M.D., Wang, S.-T., Pichler, H., 2023. Quantum Optimization with Arbitrary Connectivity Using Rydberg Atom Arrays. PRX Quantum 4, 010316. https://doi.org/10.1103/PRXQuantum.4.010316 ↩

[SciCodePhy]

C. Moore, S. Mertens, "The Nature of Computation", Oxford University Press, 2011.

Reduction (Related to Our Problems of Interests)

1. Witness Existence <= Circuit SAT <= 3-SAT <= NAE-4-SAT <= NAE-3-SAT <= Graph-3-Coloring <= Graph k-Coloring (k>=3) <= Planar Graph 3-Coloring <= Independent Set;
2. 3-SAT <= NAE-4-SAT <= NAE-3-SAT <= Max Cut

Problems of Interests Involved:

1. (Maximal) Independent Set;
2. Max-Cut;
3. Graph Coloring;
4. Satifiability problem