P, NP And Decision Problems (Really, It’s Not that Bad)
After a relatively lengthy hiatus from this series, I’m going to bring back the Practical Math series, but with two changes. First, in spite of my rather intense predilection for symmetry and order, I’m going to dispense with the stock set of headers to fill out and get a little more free form with these. And secondly, I’m going to expand it to kind of be “Practical Math for Programmers but also Practical Computer Science and all of the Discrete-Mathy things in between.” With the former concession, my aim is to remove my own blockage from writing these posts — the template is good for consistency, but it sort of sucked the fun out of it and I’d stare at the headers and think, “ugh, okay, that’s a lot to do.” With the latter concession, I mean to acknowledge that computer science and a lot of the algorithms involved are fundamentally “mathy” and that’s okay. We’ll work together to make this thing approchable.
One of the coolest concepts that I ever encountered as a student or in life was NP Complete problems. It’s a rather mind blowing subject and it’s simultaneously philosophically complex and simple to approach. I’d also like to offer the caveat here that I’m a long, long way removed from formal study of this topic, so what I’m posting here is my recollection of the topic combined with a hodgepodge of visits to various .edu sites to refresh my memory on some of the finer points. The intention here is to give an approachable introduction to those programmers who’ve never really had formal CS backgrounds and not to defend a PhD thesis. I’ve made a good faith effort to keep things accurate, but let no one confuse this with a textbook.
Now, lest I scare anyone off too quickly with that disclaimer, let’s do some grade school math. What are the prime factors of 12,317? You’ve got 20 seconds. Ready, set, go!!!
(In my best Alex Trebeck voice) Oh, no, sorry — you’re out of time. Let’s try a different one. How about 109 x 113? Bet you can hammer that one out in 20 seconds either by firing up Calc.exe or just doing it longhand. Well, look at that, 12,317. Whaddya know? And both of those are prime factors, so you now have the answer to the last question too. But… why is it so much harder to reduce a composite number to prime factors than to do multiplication. I mean, 5 x 5 isn’t a whole lot harder than 25/5. Why is factoring so much harder than multiplying? Kind of interesting to think about, huh? And just like that, you’ve dipped your toe into the waters of pretty heavy discrete math and computer science theory.
See, it’s not that bad. Let’s consider some concepts now before we give them names. I think the names get pretty weird pretty fast if you don’t first understand the concepts. Thinking about the idea of factoring versus multiplication and contemplating the nature of the uneven difficulty level, you might think as follows. Multiplication is a problem that you can solve pretty easily. Prime factoring is a problem that you can solve, but not as easily. However, given a number and a candidate prime factor, what you can do is check really easily. In other words, when you were trying to find the prime factors of 12,317, you were doing something like, “let’s see, is it divisible by 2… no… 3… nope… 5… etc.” But if someone came along and said, “is 109 a factor of 12,317,” you would say, “wow, it sure is, and now I’ve also found the only other prime factor to boot. Thanks man!” So we can differentiate between whether a problem can be solved easily (e.g. multiplication but not factoring) and whether a prospective solution for a problem can be checked easily (e.g. both factoring and multiplication). And we can also phrase our approaches to these problems in yes or no forms, requiring a decision to be rendered: “Is 109 a factor of 12,317 — yes or no?” or perhaps, “do any smaller prime factors of 12,317 exist?”
With me so far? Good. Let’s not confuse things any more quite yet, opting instead to give voice to the reasonable question, “alright, whatever, but who cares?” Well, for starters, the NSA and cares and so should you’re concerned about the degree to which they trample on your various rights. The reason for this is that the imbalance between time required to solve multiplication and factoring plays a crucial role in a number of public key encryption schemes. If you want to go beyond the realm of encryption and civil liberties, consider the implications of the discovery of a fast, polynomial time solution to NP Complete problems: you’d basically solve all of mankind’s problems. Aside from personal glory and every conceivable medal/prize under the sun, you’d be able to answer the question, “how do I build the fastest possible fighter jet” in relatively short order, especially when compared to the way we’d currently need to approach the problem, which would be to build every possible fighter jet and see which one is best (perhaps applying some limited heuristics).
If this sounds comically grandiose, it sort of is, but also, it’s sort of not. It’s unknown whether this unicorn solution (fast polynomial time algorithm for NP Complete problems) is even theoretically possible, but if it is and then it were solved, it would probably be the most ground breaking mathematical discovery in the history of mathematics. But if you’re the sort who likes practical answers to “why should I care?” then consider the ability to recognize problems NP problems as a sort of “road closed” sign when looking for algorithmic efficiency. If you realize that a problem is NP Complete, you can give up on finding a slick way to do it and realize that it’s either time to go with brute force or time to seriously reconsider what you’re doing.
So what is this P and NP and NP Complete and all that? Well before we go back to some of the discoverable concepts from the factoring example and before things get all formal, let’s consider an example of an NP Complete problem. Things are always easier by example than by mathematical definition, so let’s talk about a salesman and his travels.
Let’s say that there are a bunch of cities that are on a salesman’s route, and that the salesman has to visit each city exactly once. Obviously, there is a mileage distance associated with each trip between cities, and let’s say that our salesman can only fly on one particular airline and that it’s not a given that there are flights between any two cities. So, to review, one airline, all cities visited exactly once (which theoretically may or may not actually be possible, depending on the cities involved), mileage tabulated along the way. The question that is then NP Complete is, “is there an itinerary for the salesman that results in him traveling less than X miles?”
I like this because it’s pretty simple to understand what’s being asked, as far as examples of heady discrete math concepts go. And, it’s also possible to understand where the subtle complexity creeps in. Can you think of a way to solve this other than brute force through all possible routes and then checking to see if a given one is less than X? (If you can, email me your solution and tell no one about this! I’ll see that it winds up in good hands.) Can you also see that, while answering the question is a matter of brute force, checking the answer is a simple, polynomial time proposition (walk the given path adding up the miles and then see if the total is less than X)?
Okay, so let’s finally get to some definitions, but I’m going to keep them colloquial rather than mathematically rigorous, given the theme of this series. First off, as touched on earlier, there is the concept of a decision problem. A decision problem is simply a problem in which an algorithm is applied to some set of inputs and will produce an answer of “yes” or no.” Examples include “do any smaller prime factors of 12,317 exist?” and “is there any sales route to be traveled where the salesman can fly less than 120,000 miles?”
Now to spice things up a bit. P problems are a class of decision problems where the decision can be rendered in a time that is polynomial in relation to the input. This means that in O notation terms, you’d be talking about things like O(n), O(n^3), O(n^20), etc. The time might be awful, but it wouldn’t be exponential like O(2^n) or combinatorial like O(n!). NP problems are a class of decision problems where a proposed solution can be verified in time that is polynomial in relation to the input. Conceptually, P problems are a subset of NP problems, which makes sense. After all, if you can answer whether or not there’s any path that the salesman can travel in short order, you can certainly check one particular path in pretty short order too (and, conceptually, if you can enumerate all of them in polynomial time, you could simply solve the verification problem by just paying attention when you happened to get to the proposed solution).
Now, at this point you might wonder whether P is more than a subset of NP, but actually the same as NP. This puts you in good company with the entirety of those who study theoretical computer science. This is one of the most important problems in the field in need of a solution. Okay, so what’s NP Complete, exactly, since we’ve been talking about it? To answer that, I’m going to reach back to an old post where I talked about this concept obliquely.
I don’t have a fast (polynomial time) solution for the traveling salesman problem, but let’s say that I did. Let’s say that I had some magical oracle that solved this in short order. Since the traveling salesman problem is NP Complete and I have an oracle that can solve it quickly, it means that I can use my oracle to solve any other NP problem quickly (polynomial) as well. To be a little more rigorous, I could, in polynomial time, transform my oracle into a solution for any other NP problem, in polynomial time. So NP Complete problems are those where if you find such an oracle, you win life. If a problem is not in NP complete, your oracle is a bronze medal.
There is a lot more that could be covered, but I think this is probably a good stopping point on the subject. For more reading, here are some interesting links:
[…] P, NP And Decision Problems (Really, It’s Not that Bad) – Erik Dietrich resumes an old series on practical maths, and expands its scope to include everything up to and including computer science, taking a look at some common classes of problems in computing […]
[…] >> P, NP And Decision Problems (Really, It’s Not that Bad) […]
Nice article 🙂
I have to comments:
1. Integer factorization is known to be in NP, but not known to be NP-complete. Rather it’s even assumed to be *not* NP-complete, see http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity
2. There are several algorithms for the traveling salesperson problem that do not actually use brute-force (but still require exponential time).
Thanks for pointing that out — especially (1). I just read back through the post and see that I was never clear on that point. I used factoring because it’s easy to understand the “find a solution versus verify a solution” concept, but it appears I segued to NP Complete without the distinction.
There are plenty of approximate solutions to the travelling salesman problem that do not use brute force and that also run in polynomial time.