Assignments 6 and 7: tips, pitfalls, random comments

There's nothing terrible critical that I have to say about these, but I figured I might as well (belatedly) run through the minor points.

Hw #6, problem 2 (Clustering)

Parameterized proofs

First, a lot of people described a reduction in terms of the parameter b, but didn't give a value for it (e.g. "d(u,v)=b+1 if there's an edge from u to v, otherwise d(u,b)=b-1"). This is fine, but makes us wonder about whether we could in fact pick a value of b (in this case, we obviously can, though).

It seems to me that the simplest thing is just to pick a value of b (say 1), and work from there. There's no need to create a parameterized proof in which the reader can select a value of b and obtain a unique proof. Picking a specific value makes things more explicit and obvious - and generally that describes the charateristics of an optimal proof.

k-Color vs. 3-Color

The other thing, also minor, is for those who reduced from k-Color. Once again, this is totally acceptable. It's also kind of cool because you can easily show that k-Color and Clustering are essentially the same problem in disguise.

However, the proof is probably a bit easier reducing from 3-Color, and making things easy is a good thing (of course, I realize it's often hard enough to come up with a proof at all, let alone the optimally simplest one over such a minor point.)

Zasha's philosophy of life, umm, NP-completeness in the real world

I just thought I'd share my personal view on issues in determining if problems are NP-complete in the real world (i.e. problems that may come up in your research). Once I win a Turing Award, these will be rules supported by my prestige and other accomplishments. Until then, it's just my take.

First, of course, there's always the wimpy, but practical strategies of (1) collaborating with someone who's more experienced at NP-completeness type stuff, or (2) figuring it's not that important and just coming up with a heuristic alg that seems to work pretty well (#2 makes a lot of sense if the problem is very gnarly, & in fact I've done it). Also, I think the discussion from the midterm about P!=Practical and NP!=Not Practical is relevant in the real world.

But suppose you decide to not wimp out. Well, Garey & Johnson (Computers & Intractability) has a good section on practical tips - despite being written in 1979. I won't repeat them here.

One issue that I was reminded by the assignment is that of picking a good problem to reduce from. This issue was made artificially easier in hw #6 (not that it was actually easy, just easier) by the fact that we've only studied about 5-10 NP-complete problems, and you could presume that one of them was good.

In reality, Garey & Johnson (again, from 1979) has ~300 problems, and I'd guess there are several thousand known NP-complete problems out there. So, how to choose? I think there's two extreme strategies:

Pore through all known NP-complete problems looking for the perfect one to reduce from, and then do that reduction. Lots of up-front work, relatively easy reduction.
Use only one problem always, and bash out the reduction from it. No up-front work, but potentially horrendous reduction.

I actually favor the latter approach (and like 3-SAT, which I feel I understand well). More typically, people seem to have a list of maybe 10 popular problems to consider, mostly the original problems from Karp's 1972 paper which popularized NP-hardness proofs using reductions. Of course, probably Richard (Ladner or Karp) & others have more maturity in this issue...

Hw #7, problem 1: intuition gone wrong

Some people made the following statement in reasoning about the relative complexities of A and A': "Checking for membership in A' takes more time than checking for membership in A'. Therefore, since A' is in NP, so is A." It's true that if A' is in NP then so is A, but this is not a sound argument for why.

Remember that although checking for membership in A' takes longer, A' itself is also longer. When you get to the shorter A, the complexity could indeed be decreased because members of A are shorter. But, it could also be increased, because the complexity is relative to the smaller input size. In fact, this is what happens, since A' is in linear space, but A is only in quadratic space. A correct argument is essentially to show that A is poly-time reducible to A' (and careful about the direction...), in which case it follows that since A' is in NP, A is also in NP.