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

LATER

LANCE: I found this cool construction of an OR gate that creates a unique coloring.

LATER

LANCE: That didn't work because you need to take an OR of three variables. OK, this isn't that easy.

LATER

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