A Gadget for 3-Colorings

Following up on Bill's post earlier this week on counting the number of 3-colorings, Steven Noble emailed us with some updated information. The first proof that counting 3-colorings is #P-complete is in a 1986 paper by Nati Linial. That proof uses a Turing reduction using polynomials based on posets.

Steven points to a 1994 thesis of James Annan under the direction of Dominic Welsh at Oxford that gives the gadget construction that I so tried and failed to do in Bill's post.

Think of color 0 as false and color 1 as true and use this gadget in place of the OR-gadgets in the regular NP-complete proof of 3-coloring. I checked all eight values of a, b and c and the gadget works as promised.

James Annan later became a climate scientist and co-founded Blue Skies Research in the UK. 

Steven also noted that counting 2-colorings is easy, because for each connected component, there are either 0 or 2 colorings.

Update 4/22/24: We later learned of another gadget construction by Graham Farr in a 1994 Acta Informatica paper. 

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.

Guest post by Prahalad Rajkumar: advice for grad students

I suspect that Lance and/or I have had blogs giving advice to grad students. I won't point to any particular posts since that's a hard thing to search for. However, they were all written WAY AFTER Lance and I actually were grad students. Recently a former grad student at UMCP, Prahalad Rajkumar, emailed me that he wanted to do a post about advice for grad students. Since he has graduated more recently (Master degree in CS, topic was Monte Carlo Techniques, in 2009, then a job as a programmer-analyst) his advice may be better, or at least different, than ours was.

Here is his guest post with an occasional comment by me embedded in it. 

----------------------------

 I Made this Fatal Mistake when I Joined a Graduate Program at Maryland

Getting accepted to a graduate program in a good school is an honor.

It is also an opportunity to do quality work and hone your skills. I made one fatal mistake at the start of my master’s degree at the University of Maryland which took me down a vicious rabbit hole. I believed that I was not cut out for this program.

The Only Person Who Gave an Incorrect Answer

Before the start of my graduate studies, there was an informal gathering held for newer students and some faculty members. A faculty member asked a basic algorithm question.

Everyone in the room gave one answer. I gave another answer.

This is real life and not Good Will Hunting, and of course, I was wrong. I had misunderstood the question. It would have been a simple matter to shrug and move forward. But the paternal voice in my head saw a good opportunity to continue to convince me that I was an imposter who did not belong here.

Who is Smarter than Whom?

Some of my fellow incoming graduate students, who TAed with me for Bill Gasarch’s class, played an innocent looking game.

“That guy is so smart”.

“I wish I were as smart as her”.

They couldn’t know that this would affect me. I too did not know that this could affect me. But it did. I asked myself “Am I smarter than person X?”. Each time, the paternal voice in my head was quick to answer “No”. And each time I took this “No” seriously.

NOTE FROM BILL: Professors also play who is smarter than who game and we shouldn't.

I Didn’t Choose My Classes Wisely

I made a few mistakes in choosing my classes. I chose Concrete Complexity with Bill, which I later realized I had no aptitude for. I chose an undergraduate class taught by a professor whose style did not resonate with me. Mercifully, I chose a third class that I liked and excelled in. A class which did not destroy my confidence.

In retrospect, though I chose a couple of classes that were not my cup of tea, I compounded my problems with the stories I told myself. I had several good options available to me. I could redouble my efforts in the said classes and give it my best shot. I could accept my inevitable “B” grades in these classes, and be mindful to choose better classes in the upcoming semesters.

I, however, did the one thing I should not have done: I further convinced myself that I was not cut out to be a graduate student.

NOTE FROM BILL: Some students wisely ask around to find out who is a good teacher? Prahalad points out that this is just the first question. A class may be appropriate for you or not based on many factors, not just if the instructor is a good teacher. 

I Fell Victim to Impostor Syndrome

I kept compounding my woes in my second and third semesters. Things got bad -- I took up a position as a research assistant in my third semester. My confidence was low -- and I struggled to do basic tasks that fall under my areas of competence.

In my fourth semester, I convinced myself that I could not code. In a class project where I had to do some coding as a part of a group project, I struggled to write a single line of code.

When I confessed this to one of my group members, he got me out of my head. He got me to code my part more than capably. I’ve written about this experience here.

 It Does Not Matter in the Slightest

I wish I could tell the 2007 version of myself the following: It doesn’t matter who is smarter than whom. In any way whatsoever. We are on our individual journeys. In graduate school. In life.

Comparing myself with another person is as productive as playing several hours of angry birds.

 The Admission Committee Believed in Me.

There was one good reason I should have rejected the thought that I did not belong in the program. The admission committee believed that I belonged here. Consisting of several brilliant minds. If they thought I should be here, why should I second guess them?

NOTE FROM BILL: While the Admissions committee DID believe in Prahalad and was CORRECT in this, I would not call the committee brilliant. As is well known, the IQ of a committee is the IQ of its dumbest member divided by the number of people on the committee. 

Bill Gasarch’s Secret Sauce

Since I took a class with Bill and TAed for him, I had occasion to spend a lot of time with Bill.

In one conversation, Bill told me something profound. He told me the secret sauce behind his accomplishments. No, it was not talent. It was his willingness to work as hard as it takes.

And working hard is a superpower which is available to anyone who is inclined to invoke it. I wish I had.

BILL COMMENT: The notion that hard work is important is of course old. I wonder how old. One of the best expressions of this that I read was in a book Myths of Innovation which said (a) Great ideas are over rated, (b) hard work and follow through are underrated. There are more sources on this notion in the next part of Prahalad's post. (Side Note- I got the book at the Borders Books Going Out of Business Sale. Maybe they should have read it.) 

Talent is Overrated.

I read a few books in the last couple of years that discussed the subject of mastery: Mastery by Robert Greene, Peak by Anders Ericsson, Talent is Overrated by Geoff Colvin, The Talent Code by Daniel Coyle, Grit by Angela Duckworth, Mindset by Carol Dweck

There was one point that all of these books made: talent is not the factor which determines a person’s success. Their work ethic, their willingness to do what it takes, and several hours of deliberate practice is the secret of success. Of course, talent plays a part -- you can’t be 5’1 and hope to be better than Michael Jordan. But in the graduate school setting, where a majority are competent, it really is a matter of putting in the effort.

 Follow the Process

Bill Walsh signed up as the coach of the languishing 49ers football team. The title of his bestselling book describes his coaching philosophy: The Score Takes Care of Itself. He established processes. Focusing on the smallest of details. Walsh made everyone in the football team and in the administrative departments follow their respective processes. Long story short: the score took care of itself. The 49ers won 3 super bowls among other impressive performances.

If I had to do it all again: I would get out of my head. And keep going with a disciplined work ethic. Establish a process. Follow the process. And let the results take care of themselves.

All’s Well That Ends Well

I grinded and hustled and successfully completed my Masters degree. However, instead of making the journey a joyride, I got in my own way and complicated things for no good reason.

 Final Thoughts

As William James said, a person can change his life by changing his attitude. All I needed to do was change my thinking -- work hard -- and the “score would have taken care of itself”.

I thought I was alone. But I found out in other spheres that a non-negligent percentage of people fall prey to the impostor syndrome. I wanted to write this to help any student who may be going through the problem that I did. If you are going through self-doubt, my message to you is to get out of the head, believe that you are capable (and make no mistake, you certainly are), do the work diligently,

follow the process, and let the score take care of itself.

I am surprised that the Shortest Vector Problem is not known to be NP-hard, but perhaps I am wrong

A lattice L in R^n is a discrete subgroup of R^n. 

Let p IN [1,infinty)

The p-norm of a vector x=(x_1,...,x_n) IN R^n is

                                          ||x||_p=(|x_1|^p + ... + |x_n|^p)^{1/p}.

Note that p=2 yields the standard Euclidean distance.

If p=infinity  then ||x||_p=max_{1 LE  i LE n} |x_i|.

Let p IN [1,infinity]

The Shortest Vector Problem in norm p (SVP_p) is as follows:

INPUT A lattice L specified by a basis.

OUTPUT Output the shortest vector in that basis using the p-norm.

I was looking at lower bounds on approximating this problem and just assumed the original problem was NP-hard. Much to my surprise either (a) its not known, or (b) it is known and I missed in in my lit search. I am hoping that comments on this post will either verify (a) or tell me (b) with refs. 

Here is what I found:

Peter van Emde Boas in 1979  showed that SVP_infinity  is NP-hard.   

(See here for a page that has a link to the paper.  I was unable to post the link directly. Its where it says I found the original paper.) He conjectured that for all p GE 1 the problem is NP-hard. 

Miklos Ajtai in 1998 showed that SVP_2 is NP-hard under randomized reductions.  (See here)

There are other results by Subhash Khot in 2005  (see here)  and Divesh Aggarwal et al. in 2021 (see here)  (Also see the references in those two papers.)  about lower bounds on approximation using a variety of assumptions. Aggarwal's paper in unusual in that it shows hardness results for all p except p even; however, this is likely a function of the proof techniques and not of reality. Likely these problems are hard for all p.

But even after all of those great papers it seems that the  the statement:

                For all p IN [1,infinity] SVP_p is NP-hard

is a conjecture, not a theorem. I wonder if van Emde Boas would be surprised. If he reads this blog, maybe I'll find out. If you know him then ask him to comment, or comment yourself. 

SO is that still a conjecture OR have I missed something?

(Oddly enough, my own blog post here (item 5)  indicates SVP_p  is NP-hard; however, 

I have not been able to track down the reference.)

Does the Social Media Law in Texas affect theory bloggers?

A new law in Texas states that any social media sites that has at least 50 million subscribers a month cannot ban anyone (its more nuanced than that, but that's the drift). 

(I wrote this before the Supreme courts blocked the law, which you can read about here. This is a temporary block so the issue is not settled.) 

Here is an article about the law: here

My random thoughts

1) How can any internet law be local to Texas or to any state? I wonder the same thing about the EU's law about right-to-be-forgotten and other restrictions. 

2) Does the law apply to blogs? If Scott had over 50 million readers... Hold that thought. Imagine if that many people cared about quantum computing, complexity theory,  the Busy Beaver function,  and Scott's political and social views. That would be an awesome world! However, back to the point- if he did have that many readers would he not be allowed to ban anyone?

3) If Lance and I had over 50 million readers... Hold that thought. Imagine if that many people cared about Complexity Theory, Ramsey Theory, Betty White and Bill and Lance's political and social views. Would that be an awesome world? I leave that as an open question. However, back to the point- would they be able to block posts like: 

                      Great Post. Good point about SAT. Click here for a good deal on tuxedos. 

Either the poster thinks that Lance will win a Turing award and wants him to look good for the ceremony, or its a bot. 

4) If Lipton and Regan's GLL blog had over 50 million readers.... Hold that thought. Imagine if that many people cared about Complexity theory, open-mindedness towards P=NP, catching people who cheat at chess, nice things about everyone they mention, and their political and social views. That would be a very polite world! However, back to the point- would they be able to block posts? Block people? 

5) arxiv recently rejected a paper by Doron Zeilberger. This rejection was idiotic, though Doron can argue the case better than I can, so see here for his version of events (one sign  that he can argue better than I can: he does not use any negative terms like idiot.)  Under the moronic Texas law, can arxiv ban Doron for life? (of course, the question arises, do they have at least 50 million subscribers?)

6) Given who is proposing the law its intent is things like you can't kick Donald Trump off Twitter. I  wonder if Parler or 8-chan or Truth-Social which claim to be free-speech sites, but whose origins are on the right, would block  liberals. Or block anyone? I DO NOT KNOW if they do, but I am curious. If anyone knows please post- no speculation or rumor, I only want solid information. 

7) Republicans default position is to not regulate industry. It is not necessarily  a contradiction to support a regulation; however, they would need  a strong argument why this particular case needs regulation when other issues do not. I have not seen such an argument; however, if you have one then leave a comment. (The argument they are doing it  to please their base is not what I mean- I want a fair objective argument.)