Your Favorite NP-Complete Cheat

For those who try to defend the author, we are not blaming him because he is being brief. We are blaming him because he is WRONG.

NP Completeness is a term that can be easily defined, but he is taking a wrong approach. NP is NOT about a problem being hard. It is about the fast verification of a given solution. So in short, NP completeness only has two aspects:

  1. fast verification of a given solution
  2. If you can solve one NPC problem quickly, you can solve them all quickly.

I don’t think this is that much more complicated that what the author said, but this is the correct explanation.

Also, saying that NPC problems can be spotted by expert programmer is completely and utterly false. One excellent example is primality check. For many many years people believe that to test whether a given integer is prime is NPC, WRONG. With the discovery of AKS primality check in 2002, we know that actually primality check is actually in P. Even the best mathematicans/ programmers wouldn’t have known before that.

That might be what Jeff wanted to say, however there is a strong definition of NP-completeness (a language L is part of NP and all other languages in NP are polynomial time reducible to L). As all problems in P are part of NP, this remains the same even if P=NP. In that case it won’t be very interesting, as all problems in P, except always accepting and never accepting are P-complete, but it is still a valid definition.

Strilanc,
if you start with Jeff not mentioning that he talks about decision problems, you might as well mention that he didn’t state what type of reduction he is talking about.

@dan:
I’ve set it before. Jeff’s MO is the google expert MO (he calls it just-in-time learning). It may be fine if you’re just trying to solve this or that problem and get on with your work. But if you’re gonna talk about something, you had better do the research. And Jeff seldom does.

Obviously Jeff puts in considerable time in writing his blog posts. I appreciate that. Is it that hard to spend more minutes for researching them?
Or here’s an idea! Don’t talk about things that you clearly DON’T know about. Reading Wikipedia does not make one a domain expert, and is definitely not enough to start explaining this to others.

Every single time Jeff talks about something I know about, he make many small but not insignificant errors, betraying his ignorance on the subjects. Sometimes Jeff makes gross errors. The kind of errors that anyone who has a little bit of knowledge in that area would know.
It makes me wonder how much of what Jeff says about stuff I don’t know about, is a mistake.

Also, trivializing the work of hundreds of computer scientists is extremely condescending. I actually avoided calling it what it is, in my previous post.
How can Jeff, with his 30 minutes of reading Wikipedia, claim that no one can define what makes a problem NP-complete?
And calling something ‘fancy computer science jargon shorthand for incredibly hard’ is not only condescending, it’s down right insulting, when it comes from someone who very obviously don’t know what their talking about.

My point? Such articles (read back a bit, this is not an isoladed incident) are superficial and shallow, poorly researched pieces.
I don’t think it was Jeff’s intention, but they promote and ENCOURAGE the notion that programmers don’t need to study CS at all, that it’s just a bunch of B.S.
I mean, why study intractable problems when we can cheat?

And like I said, it’s insulting. I don’t insult Jeff’s work as a web programmer. I know NOTHING about web programming. I don’t write about web programming in such manner.

Dan, We don’t have an a priori way to tell which problems are going to be NP Complete, though we can recognize when a specific problem is
That’s a great sentence. Very clear. But that’s totally not what Jeff said. Again, I encourage you to read back through the archives, on posts dealing with subjects bordering on CS. Jeff is often wrong on the basic details, and you can read the comments and see him being corrected time and again.

Wow, these comments have gotten pretty nasty.

I think what’s coming out more than anything is evidence of the growing animosity between computer science (theory) and software development (practice).

@M: It’s insulting? How many computer scientists have I heard in the past week imply this analogy:
computer science : mechanical engineer :: programmer : auto mechanic
I’ve known brilliant head-in-the-clouds computer scientists (PhDs and all) that write code at a rate of 5 lines per month (with comments).

Until both sides start respecting each other as completely distinct yet dependent professions, this kind of thing will be par for the course.

This is my first post to this discussion, since I just saw the post. Well, I am really curious why people are ‘defending’ Jeff.

Nobody here is trying to show off.

The information presented in the blog post is plain wrong, and therefore misleading. I am not going to discuss the relevant topics here (i.e., NP-completeness and approximation algorithms - called 'cheat’s in the blog post). This is not a matter of attack or defense, but maybe an opportunity for Jeff to do some self-criticism.

At various posts, I disagree with Jeff, but most of the posts are on very subjective topics, and since there is no objective metric, argument is time spent for nothing. But disagreement is not bad, I am sure in some of the topics Jeff’s are more accurate than my thoughts, and in some vice versa.

The worrying part about the post is not only its inaccuracy, but its reflection on the credibility of the author himself. At most times, when I am ignorant on a topic he posts on such as 3D cards, I took what he said for granted - not totally granted, but with high confidence I should say. This is not true from today on, because today he posted on a topic that I am very knowledgeable about, and the information is wrong, which forces me automatically to degrade his credibility on the other posts from today on.

But I hope that the comments on this blog post will at least force Jeff to reconsider his posting strategy.

Jeff: I think you are a good writer, and I don’t have to tell you this, because you make your life from blogging which says enough. In any case, I think you should stick to the following basic principles:

  • Do not post about something you don’t know as if you have an idea about it: Posting about something you don’t know is fine unless you make it absolutely clear you don’t know it, want to learn more about it, or asking the reader’s for assistance and comments.

  • Do not give references to text you haven’t read unless you make it clear you haven’t read them: If you had read the first 2 chapters of Garey Johnson, you’d not have written this post.

I suggest that you retract this post, or the misinformation propagated will be your fault. I think one of the readers can make a guest post about the topic, which will be informative to the people who don’t know the topic.

To all of the current posts detractors, if you dislike this site so much, why on earth do you even bother to read it? Does it make you feel superior to tear down and trash someone elses observations and comments?

On a somewhat unrelated note, I consider the orange CAPTCHA system that Jeff setup was brilliant, especially after reading his explanation of it.

I feel there is an IQ test somewhere regarding peoples complaints against it…

How much wood would a woodchuck chuck, if a…

Nobody can define what makes a problem NP-complete, exactly, but you’ll know it when you see it.

Is this a joke?

Accusing Atwood of not explaining NP-completeness well enough here is like expecting your friendly college science professor to explain the mathematical and cosmological underpinnings of E=MC2 in 1000 words or less.

Or when the kindergarten teacher doesn’t explain the Greco-Roman-Arabic derivation of the letters of the alphabet to his four-year-olds, do you start ranting and raving in his face, spittle flying, cursing his stupidity?

The piece was (obviously) an attempt to take a very difficult subject and make it palatable. I’d say it succeeded. It’s a pale and weak sort of ego that would find anything offensive here.

Just my .02.

I was wondering about the not having approximations for all NP-complete problems. The thing that is getting me is I thought that part of the definition of being in the NP-complete set is that a problem in the set is isomorphic with every other problem in the set. ( That is why proving that p=np or the inverse for one problem proves it for all of the problems. ) Given that why is it that we can not us a approximation for one on any of the others? Am I really confused about something here?

-Jonathan

a href=http://en.wikipedia.org/wiki/Graph_theoryhttp://en.wikipedia.org/wiki/Graph_theory/a

My favorite NP-Complete problem is bin-packing. Maybe shape separability.

Why do you make some many laymen sort of posts about how we should all be learning more about computer science (when many of probably have CS degrees and have known about this since sophomore year of undergrad days) but you think learning C is useless?

Just wondering.

To Jon who is railing about more well rounded people in this industry: You realize this is a technical blog right? Sure there may be non-technical project managers reading this but its kind of pointless to have a laymen sort of discussion with a manager of a K-Mart about Approximation Algorithms. Why would you even do that? You’re just showing your ignorance by perpetuating some stereotype about technical people going back to their caves.

Genetic algorithm. It has worked well for TSP, thus I’ve always kept a good GA library (with some timeout stoppers for example no improvement in solution during X seconds, or no exceeding X seconds of total computation ) in order to solve NP-Probs when they have arisen.

Why can’t I vote-up these answers? :stuck_out_tongue:

When reading this post, it surprised me how it depends on the circumstances when you’re first heard the term NP-complete. Jeff calls it a shorthand for incredibly hard, but I always remembered it as easy. How come?
At university, I wondered whether I should study computational linguistics and attended a first lecture about syntax theories to get a glance about what that subject is like. The problem is to syntactically parse a sentence in natural language using a computer. In that lecture, if a syntax theory is NP-complete, that meant good, quickly solvable in polynomial time. Not NP-complete meant bad, takes exponential time to solve. But the worst case (in that lecture some version of a Chomsky syntax theory) was plainly unimplementable.
My interest for computational linguistics originated in my enthusiasm for text adventures (today called interactive fiction) many years before (on a Commodore 128), so I’d call well written textadventures with bewitching graphics (Magnetic Scrolls) as my favorite NP-complete cheat.

NP = Not Possible [in linear time]

BTW, Jeff, I don’t know if you would read my comment, but since your captcha is always orange, and I never see any spam in any of your blog, how did you manage that?

@Steve,

You asked:

Can someone solve this?

a=b
so, a^2 = ab
so, a^2 - b^2 = (a
b) - b^2
factor: (a+b)(a-b) = b*(a-b)
cancel: (a+b) = b
so, 2b = b
so, 2 = 1

There are many variations to this type of puzzles. I knew or rather learned from 7th grade that all of them either involve (1) dividing by 0 or (2) Take a square root and ignore the fact the it’s rather the absolute values that are equal.