Menu Home

The hardest problem in computer science (Part 2)

The P vs. NP problem is perhaps the biggest unsolved question in computer science – but an answer would have profound implications for mathematics, cryptography, cancer research, nurse roster scheduling, and sudoku. [2 of 2]

Welcome back! Yesterday I began an explanation of the P vs. NP problem by describing two ways to classify problems:

  • P = problem is easily solved
  • NP = problem is easily checked

Some problems, like sorting library books, are both P and NP. Some problems, like sudoku puzzles, are NP but not P… or so we think. As it turns out, there are a lot of problems of this second type.

Take scheduling a roster for a group of nurses. The roster has a set of constraints: you cannot do a morning shift immediately after a night shift; Nurse Bonnie doesn’t want to work weekends; Nurse Steve cannot work nights. It is the algorithm’s job to make sure that they all get what they want. We have yet to come up with an efficient way to solve this problem with a computer so that it scales with the number of nurses. (This problem, by the way, is called NSP, or Nurse Scheduling Problem.) Much of modern cryptographic security relies on solutions that are easy to check but cannot be solved quickly – because you want encryption to be easy to verify but not easy to crack. Researchers trying to cure cancer, Alzheimer’s disease, Huntington’s, and other ailments spend enormous amounts of computing time trying to understand how proteins fold. All of these problems cannot be solved easily and at scale.

So what? Many of these problems appear to fit in the same category as sudoku: we can check the answer very quickly and easily, even if we cannot find the answer easily. You can see at a glance that Nurse Bonnie is scheduled for a morning, afternoon, and evening shift, for example. Going back to our P and NP terminology: they are NP (easily checked) but not P (easily solved).

Or so we assume. There’s a big pile of NP but not P problems… but sometimes, just sometimes, we find that one of the problems doesn’t belong in this pile. Someone will discover an algorithm that can solve the problem quickly, making it both P and NP. This algorithmic shortcut makes the insurmountable problem solvable.

Mathematicians and computer scientists have had a few successes syncing up P and NP problems in this fashion. It is possible that algorithmic shortcuts exist for all such NP problems… and we just haven’t found them yet. Maybe every problem that is easy checked is also easily solved. Maybe P and NP are the same thing.

Here’s where it gets tricky. (“Just now?!?” I hear you ask. Sorry.) A whole host of these problems are linked together. The technical term for them is “NP-complete.” For these problems, if you found an algorithmic solution for one of them you would automatically solve all of them. We would suddenly have efficient solutions to dozens of unanswered problems in mathematics and computer science – problems like the Travelling Salesperson problem, which has plagued us for more than a century. It would be a golden bullet.

Most researchers believe that P and NP are not the same thing, and that we’ll never find efficient solutions for these tough questions. Until we prove otherwise, though, it’s always possible – and the proof continues to elude us. The P vs. NP problem is so important that the Clay Mathematics Institute will give you a million dollars if you prove it. And now that you know what it is, you can give that a try.

(End note: NP and NP-complete problems are not the most complex possible; they’re just the ones that are complex to solve but easy to verify. There’s a whole branch of problems that are complex to solve but also complex to check. These are called NP-hard. If you want to explore all of the other categories of problem I strongly recommend the YouTube video below.)

Categories: Mathematics & statistics Sciences Technology

The Generalist

I live in Auckland, New Zealand, and am curious about most things.

3 replies

  1. “These are called NP-hard.”

    Terminological nit: no, those are called “not in NP”. NP-hard is “NP-complete and harder”, so it includes problems that are poly-time checkable.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: