Your Favorite NP-Complete Cheat

blog
121

Well, that just begs the question - why the blog post in the first place? And why recommend a book that you haven’t read and/or didn’t understand? Not cheap shots here, I actually want to understand why you took that credibility risk with the people who know this stuff - which it turns out is a lot of programmers.

In all honesty, despite reading all the above comments and the wikipedia entries, I still don’t quite understand the definition of NP-complete other than as we’ll know it when lots of experts have seen it, tried, and failed.

Have you really read all of the above comments? Not just scanned over them but read them? You only know if a problem is NP-complete if the experts have seen it, tried, and proved that it’s NP-complete. There’s a precise definition and a set of criteria to demonstrate that something is NP-complete.

I’ll have a crack at some explanations, I don’t know how much help they’ll be. I’m sure the book you linked to probably explains it better.

A Turing machine is a simple model of a computer. In its usual form its only output is to accept or reject and input, so instead of asking it what a + b is, you normally ask it if a + b = c - ie it solves decision problems.

A problem is in P (Polynomial time) if for all instances of a problem with size n (n = 100 if we have 100 objects to sort, for instance) the Turing machine takes a number of steps to come to a decision that is a polynomial in n - eg there’s an uppper bound of 2 * n^5 + 4 *n + 5.

A lot of the time when we talk about the size we’re talking about the number of bits - adding n-bit numbers is in P - O(n) - and so is ultiplying n-bit n-bit numbers - O(n^2) the simple way, although FFT methods do better.

This is where I back up for a second and talk about non-determinism. A regular expression is just a non-deterministic finite automaton or state machine. It has a state, and the next state is determined by the current state and the next piece of the input which is read.

Say we’re scanning a bit string rather than a character string, and we’re after strings that have a 1 as their tenth last bit. Using a regular state machine we’re going to need about 2^10 states to handle this.

This is where we add non-determinism. We allow the machine to go to several different states based on the current state and the next piece of the input. Once we’ve read a 1 we’re in a state with two paths - one leads back to the state we’re in, and one leads to a string of ten states which all transition to each other on all inputs and end with an accepting state.

Rather than having the machine encode 2^n states we have the machine split into 2^n in different multiverses and we take a big OR of the results. The machine took n guesses that the current piece of input was the tenth last, and we were able to save some space describing the machine.

As a bonus you can easily implement a NFA engine with only a polynomial size increase in space / time for the processing over the deterministic equivalent, so they’re both in P but I digress.

So we’re processing the input of a Turing machine. Now we add non-determinism, so at every step the machine can split - so we have 2^n virtual-multiverse machines, if any of them say yes to the current decision problem then the answer is a yes. If the running time for each machine is bound above by a polynomial in n, we have a problem in NP.

That’s why there’s a polynomial size check (or certificate) of all NP problems - it’s just an encoding of the n guess that were made to get to the accepting state. You can take the original non-deterministic turing machine and at each place where you would normally guess the certificate will tell you which path to take and guide you to the accepting state. It’s like factoring the product of two large primes is hard but it’s easy to check if you have one of them already via the mod operation.

The NP-complete problems are assumed to be the hardest of the NP problems. It all starts with SAT3 - just take it as a given for now that SAT3 is the first in the list of NP-complete problems.

Take a candidate for a second NP-complete problem. Using a polynomial number of copies (A) of this candidate problem and a polynomial sized amount of Turing machine glue code (B) try to show that you can solve SAT3 (or something else on the list). If you can, the candidate problem is NP-complete and you can add it the list.

So if solving NP problems takes exponential time, we have A * an exponential in n + B, and it takes a really long time to solve SAT3 and every problem between your problem and SAT3.

But if one of them can be done in polynomial time, we have A * a polynomial in n + B, and it takes polynomial time to solve SAT3 and every problem between your problem and SAT3.

You may have spotted that so far this means solving SAT3 in polynomial time doesn’t do much for you. NPC is defined as the problems that are in NP and reduce to all other problems in NPC, and so for SAT3 to keep its crown you also build the tree in the other direction.

It becomes a crazy tangled web but it’s clear that if you can solve one of the problems in polynomial time you can solve all of them in polynomial time just by stepping through the web from the P-time problem towards the problem you’re after.

122

Dave has it almost completely right above, except for a couple of details. The NP-complete problems aren’t assumed to be the hardest problems in NP - they are proven to be, and the proof involves SAT instead of SAT3 (SAT3 is just SAT restricted to no more than 3 literals per clause).

This is what Cook’s Theorem is all about, and it’s why NP-completeness isn’t as recursive as it looks. What Cook did was to show that given any decision problem in NP, we could take a description of the non-deterministic Turing machine that solves it, and produce in polynomial time an equivalent SAT problem that had a solution if and only if the NTM returned true along one of the paths in its original computation. So if we had a hypothetical polynomial-time algorithm to solve SAT, we could use it to solve every decision problem in NP in polynomial time - just take the description of the NTM that solves the original problem, produce the equivalent SAT problem, and turn our hypothetical SAT solver loose on that.

That’s what showed that there was such a thing as NP-completeness in the first place, and showed that SAT was one such problem. All the other NP-complete problems have been shown to be NP-complete by showing that If we could solve problem X in polynomial time, then we could solve this other problem in polynomial time … and therefore, we could solve SAT in polynomial time.

Terminology note: a decision problem is one with a boolean true/false result. E.g., does the following instance of the TSP have a solution with cost = B? Technically, NP (and therefore all the NP-complete problems) consists only of decision problems (by definition). The optimization problems that we are usually really interested in solving can be NP-hard, rather than NP-complete. A problem is NP-hard if a polynomial-time solution to it would imply a polynomial-time solution to an NP-complete problem. Thus What is the lowest-cost solution to the following instance of the TSP? is NP-hard, not NP-complete, but it should be pretty obvious that if we could solve it in polynomial time, we could also answer the related decision problem, which is NP-complete.

123

I think what Jeff means is that nobody can define what makes a particular problem belong to NP, but not P.

That is what I was trying to say. Poorly, obviously. I have updated the post.

I still say the definition of NP-complete is awfully… conveniently … recursive, as T.E.D. mentioned.

I also agree with this particular sentence in the Wikipedia (http://en.wikipedia.org/wiki/NP-hard) article: The NP-family naming system is confusing.

And how.

124

I actually want to understand why you took that credibility risk with the people who know this stuff - which it turns out is a lot of programmers

I wrote about it for the same reason I write about anything, I’m trying to understand it. Sometimes you’re successful, other times not so much. Life is a credibility risk; what are you gonna do? Not say anything until you’re guaranteed to be perfectly right every time?

It becomes a crazy tangled web

Well, that part is clear.

125

@T.E.D.:

The definition on Wikipedia is not recursive. I think the confusion may arise because NP and NP-Complete mean different things, and the definition of NP-Complete depends on the definition of NP.

A problem is NP if (roughly speaking) it’s quick to check whether a proposed solution is correct. Note that this includes both easy and hard problems.

This definition of NP is not recursive. You can decide whether a problem is NP independent of other problems.

A problem is NP-Complete if it’s both NP and if finding an easy algorithm to solve it would automatically give you an easy algorithm to all NP problems.

This definition of NP-Complete depends on the definition of NP, but it does not depend on itself.

126

Another reason it sounds recursive is that generally the way you prove a problem is NP-Complete is by showing that it’s NP and then reducing another NP-Complete problem to it. So how do you prove that anything is NP-Complete in the first place? The answer is that this is only the easy way. The hard way is to prove that every problem in NP can be reduced to your problem. That’s what the Cook-Levin theorem did for the SAT problem. Once you know one NP-Complete problem, it becomes easier to prove other problems are NP-Complete.

http://en.wikipedia.org/wiki/Cook–Levin_theorem

127

A problem is NP-complete if it is both [quick to check whether a proposed solution is correct] and finding an [efficient] algorithm to solve it would automatically give you an [efficent] algorithm to solve all [quick to check whether a proposed solution is correct] problems.

Isn’t this… er… still… partically recursive? We know it because solving one would solve all the others, which in turn solves the others, which in turn solves the others… ad infinitum?

I have to say I find this topic incredibly confusing, even after reading all the above comments (many of which were quite helpful, thank you) and the relevant wikipedia articles.

128

Isn’t this… er… still… partically recursive?

The definition involves infinite stuff (the set of all NP problems), but it is not recursive. The definition of NP stands alone, and the definition of NP-Complete depends only on the definition of NP.

The presence of infinite stuff isn’t as big a deal as you’d think. You can prove that adding together any two odd numbers will give you an even number, even though there are an infinite number of odd numbers. I don’t really understand the Cook-Levin theorem myself, but I’m happy to know that it shows that all of the infinite possible problems (including all the ones nobody has thought of yet) in NP can be converted to an instance of the SAT problem. That might seem surprising, but it’s not all that different to proving something about all the infinite possible odd numbers. Then, with that in hand, you can go on to show that other stuff is NP-Complete, because if you can convert SAT to your problem, you know you can convert any problem in NP to SAT and then convert it to your problem.

129

@Jeff

You’ve mentioned the explorative nature of your posts before and it just slipped my mind - sorry about that.

The blog post does read like you’re telling people about something that you’re pretty familiar with, which might be why the people familiar with NP / NPC are exploding on here.

For instance, I read the expert programmer line like you were in the pool of people who understood NP / NPC and were asking the other folk to jump in and test the water. Could just be me though.

I guess it’s not about credibility, it’s about being able to tell when you’re expounding and when you’re exploring. And I guess that’s really a problem occurring in the space between you and readers - lots of stuff is missing when you’re communicating digitally. Maybe throw in a hint next time to make it clear to those of us that are struggling to tell the two apart? :slight_smile:

Good luck with the exploration :slight_smile:

@Dave W - you’re spot on.

Although I didn’t meant that it is assumed, I was just asking Jeff to trust me on it since it was already an overlong post :slight_smile: It took enough restraint to avoid mentioning the different kinds of reductions.

Of course, now that you’ve mentioned it I’m kicking myself for not just saying you can emulate a NTM with a carefully configured instance of SAT.

130

Ok, not enough time to read all the comments that don’t have the answer to the question, what’s your favorite cheat? Mine: refactoring a hard problem such that I can avoid the part I want to avoid as much as possible. I imagine that there is a CS term for it, but I majored in English :slight_smile: Clearly a lot of the commenters are smart–probably smarter and certainly more educated (in this field, anyway) than I; how does the flamage help anyone get things done?

131

@Henry: great explanation. Rather than repeating the self-referential jargon that other explanations used, you did a pretty good job of demonstrating what the concepts mean. If you could have avoided the terms ‘Turing machine’ and ‘polynomial’, it might have been better, but I (and presumably most) knew those anyway.

132

Im sorry Jeff but your update is still somewhat wrong. You should abandon the thought NP-complete == hard-problem . It should be more like NP-comple = we think it’s a hard problem.

I’ll try to give an understandable and maybe partly informal definition of NP-complete below, bear with me (or ignore it, if you think it’s not interesting).

NP-completeness is defined by two criteria:

  1. The problem is in NP (aka the problem can be solved in polynomial time by a non-deterministic Turing machine. (Before I get flamed for mentioning Turing Machines: Regarding some previous posts by Jeff I think he knows what I’m talking about.)
    Note this is trivially true for all problems in P (those which can be solved in polynomial time by a deterministic Turing machine). So P is a part of NP.

  2. The problem L is one of the hardest problems in NP.
    Let’s say we have some magic box, which accepts the input for our problem L and gives us the correct output, taking only a fixed amount of time, independent of the input. Now to prove, that our problem L is the hardest, we have to show that we can solve all other problems in NP in polynomial time using our magic box (This is known as Reduction).
    We do this by giving an algorithm, which transforms the input for other problems into input for our problem. Now showing something for ALL problems sounds difficult, but it can be done. (If you want to know how look up the Cook-Levin Theorem).

If we have one problem L’, which is known to be the hardest it is enough to show that our problem L is equally hard. This means we only have to give an algorithm which solves L in polynomial time using a magic box which solves L’.

So, the Cook-Levin Theorem shows that we can transform every problem in NP into SAT. Going on from there we show that we can transform SAT into other problems, like Traveling Salesman, Bin Packing, etc. take your pick.

We think that we can’t solve this problems in polynomial time on a non-deterministic Turing Machine (or on your average computer), but we can’t proof that and if someone would come up with a way to solve one of these problems in polynomial time, we could solve all of them in polynomial time (we could just apply the algorithms, that we defined when we proved their NP-completeness).

However, even if someone comes up with such a solution (which is highly unlikely) the definition of NP-complete I gave above still applies to all of the problems, so they remain NP-complete. We only revise the deduction NP = difficult.

133

Wow. Jeff Atwood, master troll!

I think I’m going to add Jeff’s explanation of NP-complete to Conservapedia. http://www.conservapedia.com/Public-key_encryption

It’s a pretty good imitation of a pop science explanation of CS terms, but with glaring errors that stand out to anyone with an undergrad CS education. (Nobody really knows what NP-completeness means… Problems are only NP-complete because we can’t prove they aren’t.)

Maybe Jeff can explain one-way hash functions next. (A one-way hash function is a way of implementing a read-only hash table, similar to Ada’s ‘const final’ attributes.) Or branch prediction. (Branch prediction is the ability of a programming language to conditionalize certain instructions on flags in the hardware’s ISR register.) Or garbage collection. (Languages such as Java are only considered garbage-collected because we can’t prove they aren’t.)

134

(BTW, please don’t fix the Conservapedia articles. The errors are intentional parody.)

135

Okay, Jeff; I admit I haven’t read all of these posts. But I’m going to try and clear up some of your confusion without using too many words. I aimed for 200, but I’m afraid I ended up needing 300:

We need to separate algorithms and problems. We write algorithms to solve problems, and they scale in a certain way. Although this is a simplification, let’s label an algorithm with a ‘P’ if the scaling is good enough, and ‘NP’ if it isn’t.

It’s helpful to know things about the problems we’re trying to solve, rather than the algorithms we use to solve them. So we’ll say that all the problems which have a well-scaling algorithm are in P. And the ones which have a poor-scaling algorithm are in NP.

That means that lots of simple problems are in NP too, because we can write bad algorithms to solve easy problems. It would be good to know which problems in NP are the really tricky ones, but we don’t just want to say it’s the ones we haven’t found a good algorithm for. After all, I could come up with a problem (call it X) that I think needs a super-amazing algorithm. I tell the world that the best algorithm I could come up with to solve X scales badly, and so I think that X is a really tough problem. But tomorrow, maybe somebody cleverer than me invents an algorithm which solves X and is in P. So this isn’t a very good definition of hard problems.

All the same, there are lots of problems in NP that nobody knows a good algorithm for. So if I could prove that X is a certain sort of problem: one where a good algorithm to solve X could also be used, in some roundabout way, to give a good algorithm for every other problem in NP. Well now people might be a bit more convinced that X is a genuinely tricky problem. And in this case we call X NP-Complete.

136

porges and Delmania: no, the existence of reductions from any NP-complete problem to any other doesn’t mean that if one has good approximations then they all do. It can happen that there’s a polynomial-time reduction from problem A to problem B but that it doesn’t give you a good approximation for problem A even if problem B has one. (Crudely: suppose you’ve got something that turns solutions to B into solutions to A, but that turns almost-solutions with error x to B into almost-solutions with error rapidly_growing_function(x) to A. Then approximate solutions don’t turn into approximate solutions even though exact solutions turn into exact solutions.)

It would be nice if people didn’t use NP to mean hard, just like it would be nice if people didn’t use exponential to mean big, but it probably isn’t going to happen any time soon.

137

Hi Jeff,

Please let me try a real simple explanation of the difference between P and NP… I hope I’m not repeating anyone, I haven’t read all the posts. I won’t bother repeating definitions I already saw above, just explain the difference (and why it isn’t a recursive definition)

For a problem, M:

M is in P if, and only if, there exists an algorithm that solves M in polynomial time. In all cases, that means we know the algorithm and prove it’s polynomial.

M is NOT in P if we have proven, absolutely proven, that there is NO algorithm for it that runs in polynomial time. This is, of course, much harder to prove, since you can’t do with with an example - you have to prove it for all possible algorithms.

That would seem to cover all problems, but for quite a few problems, the answer is ‘we don’t know’. That’s because there’s no known polynomial algorithm for them, but also, there’s no proof that there one doesn’t exist.

This annoys computer scientists to no end.

In studying these problems which are unknown, it turns out that for a lot of them, you can devise a simple algorithm to tests a given solution, but not one to find a solution. The formal definition for them, given above in a lot of posts, is NP problems. Due to its definition, NP problems also include all P problems.

To complete things, it also turns out that quite a few of those NP problems are NP-HARD, which means that if you solve them in polynomial time, you can also solve all the rest in polynomial time.

A problem that is both NP-HARD and in NP is called NP complete.

So there you have it, a non-recursive and hopefully simple explanation.

Or

138

I have never commented before and most probably will not again. There are two serious problems with the post, one of which has been fixed partly. But the second one hasn’t.

  1. Nobody can define what makes a problem NP-complete, exactly …

It has an exact and precise definition, as pointed before. In your redaction you link to a poll about P != NP amongst computer scientists. How can this imply there is a confusion regarding the definition of NPC? Please take down the link as it is very misleading.

  1. Your recommendation of Garey-Johnson - this book has a timeless quality. Have you read the book? Clearly you haven’t. Otherwise you wouldn’t be confused by the definition of NPC. It is obvious, you are strongly recommending a book you haven’t read at all. This completely destroys you credibility as an author. You must preface the recommendation with the text - Disclaimer: I HAVE NOT READ THIS BOOK.

Since, you have claimed in your comments to still be confused by the definition of NPC, I will try and explain it in my own words, because it is quite simple.

Let U = set of problems.
Let P = set of problems that can be solved in polytime wrt size of the input
Let NP = set of problems whose solution can be verified in polytime wrt size of the input

Obviously P = NP = U

For example sorting an array of numbers

  1. belongs to U
  2. belongs to P, we can do this in nlogn
  3. belongs to NP, given a array, we can check if it is sorted in polytime. In other words, Given an unsorted array, we sort it using a black box routine and verify if it is sorted in polytime. Let us say we do not know of any algo to sort numbers in polytime. This does not prevent the problem for belonging in NP. The problem may or may not belong to P. We don’t know.

Another example, determine if a number is Prime
Before 2002

  1. Belongs to U
  2. Dont know if it belongs to P. No algo known
  3. Dont know if it belongs to NP (I think). Simply stating that a number is prime, isn’t enough, we need a proof of the fact, that can be verified in polytime. For a sorted array, it is simply the array laid out in sorted fashion.

After 2002 AKS polytime primality test, we KNOW that it belongs to P and hence NP.

Another example, does a graph have a Hamiltonian cycle (Google this).

  1. Belongs to U
  2. Don’t know if it belongs to P
  3. Belongs to NP. Given a cycle in the graph, we can verify if it covers all vertices of the graph.

Cooks theorem showed that if the 3-SAT problem, which belongs to NP also belongs to P, then ALL OF NP BELONGS TO P i.e. P == NP. Note that he did not prove that 3-SAT is in P. Just that if it were then, P == NP. Now many CS scientists are busy trying to prove that this implies a contradiction, i.e. P != NP, with noone succeeding so far. That’s where the cartoon comes from.

Now we get to the definition of NPC - NP Complete.
After Cooks paper, Richard Karp proved that 21 problems that belong to NP are atleast as hard as 3-SAT, including the Hamiltonian cycle problem.

at least as hard means

  1. Suppose you have a polytime solution for the Hamiltonian cycle. Then you can easily (in polytime) transform the 3-SAT problem into a Hamiltonian cycle problem. In other words, if you solve the Hamiltonian problem in polytime, you would have solved the 3-SAT problem in polytime as well. Like, if you can multiply complex numbers, you can also multiply real numbers.

Hence a polytime solution for Hamiltonian = polytime solution for 3-SAT = P == NP

Now, NP-Complete problems are those problems in NP that are at least as hard as 3-SAT, i.e. if even one of these problems were to belong to P, it would imply that all of P == NP. Starting with Karp’s 21 problems, thousands of such problems are now known.

However note that the definition of NPC depends on convertibility of 3-SAT to it, and no-where on P == NP. A problem is NPC if the 3-SAT problem can be transformed into it in polytime.

139

Lastly

P = NP = NPC U

140

Please scratch the previous post, I meant

NPC lt;= NP lt; U

P lt;= NP lt; U