Sunday, June 26, 2022

Counting the Number of 3-colorings of a graph is Sharp-P complete. This should be better known.

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

1 comment:

  1. This paper, joint with Samir Khuller, has another complexity-theoretic anomaly of the graph coloring problem.

    ReplyDelete