tag:blogger.com,1999:blog-3722233.post4647242799583898034..comments2020-09-20T19:47:50.963-05:00Comments on Computational Complexity: A well known theorem that has not been written down- so I wrote it down- CLIQ is #P-completeLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-82553181952850660452020-09-01T22:38:52.622-05:002020-09-01T22:38:52.622-05:00I am not surprised its well known, I am surprised ...I am not surprised its well known, I am surprised that I could not find it online. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9579880716919389542020-09-01T22:24:21.824-05:002020-09-01T22:24:21.824-05:00Your "easy" proof #3SAT to $CLIQ is defi...Your "easy" proof #3SAT to $CLIQ is definitely well-known; it is the reduction I've been teaching since mid-nineties to show Clique is NP-hard, and later when I reach counting complexity I ask the students to check back that the reduction is parsimonious. It appears in the AroraBarak text in Theorem 2.15.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41326857404814670372020-09-01T14:51:11.841-05:002020-09-01T14:51:11.841-05:00(David Eppstein's comment- he asked me to post...(David Eppstein's comment- he asked me to post it for him.)<br /><br />Counting independent sets is #P-complete, even in planar graphs:<br /><br />SIAM J. Comput., 31(2), 398–427. (30 pages)<br />The Complexity of Counting in Sparse, Regular, and Planar Graphs<br />Salil P. Vadhan<br />https://doi.org/10.1137/S0097539797321602<br /><br />So counting cliques is complete in the complement of planar graphs.<br /><br />The reduction is not parsimonious. The definition of #P-completeness does not require parsimoniousness. I think in this case it's a Turing reduction. It should be possible to prove #P-completeness of cliques under polynomial-time counting reductions (https://en.wikipedia.org/wiki/Polynomial-time_counting_reduction) but I don't know of a reference.<br />Parsimonious reductions are not possible, because every graph has at least one clique (the empty set) and not every satisfiability instance has at least one satisfying assignment.<br /><br /><br /><br /><br />gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.com