(ADDED LATER- Lance and I were emailed more information on the topic of this post, and that was made into a post by Lance which is here.)
BILL: Lance, is #3COL #P complete? (#3COL is: Given a graph G, return the number of different 3-colorings it has.)
LANCE: Surely you know that for all natural A, #A is #P complete.
BILL: There is no rigorous way to define natural. (I have several blog posts on this.)
LANCE: Surely then for all the NP-complete problems in Garey & Johson.
BILL: I know that. But is there a proof that 3COL is #P Complete? I saw a paper that claimed the standard proof that 3-COL is NPC works, but alas, it does not. And stop calling me Shirley.
LANCE: I found this cool construction of an OR gate that creates a unique coloring.
LANCE: That didn't work because you need to take an OR of three variables. OK, this isn't that easy.
LANCE: I found an unpublished paper (its not even in DBLP) that shows #3-COL is #P complete using a reduction from NAE-3SAT, see here. The proof was harder than I thought it would be.
BILL: Great! I'll post about it and give the link, since this should be better known. The link is here.
This leads to a question I asked about 2 years ago on the blog (see here) so I will be brief and urge you to read that post.
a) Is every natural NPC problem also #P-complete. Surely yes though this statement is impossible to make rigorous.
b) Is there some well defined class LANCE of LOTS of NPC problems and a theorem saying that for every A in LANCE, #A is #P complete? The last time I blogged about this (see above pointer) a comment pointed me to a cs stack exchange here that pointed to an article by Noam Levine, here which has a theorem which is not quite what I want but is interesting. Applying it to 3COL it says that there is a NTM poly time M that accepts 3COL and #M is #P-complete.
Not just 3COL but many problems.
c) Is there some reasonable hardness assumption H such that from H one can show there is a set A that is NP-complete that is NOT #P-complete? (The set A will be contrived.)
ADDED LATER: Is #2-COL known to be #P-complete? This really could go either way (P or #P-complete) since some problems in P have their #-version in P, and some have their #-version be #P-complete.
This paper, joint with Samir Khuller, has another complexity-theoretic anomaly of the graph coloring problem.ReplyDelete