P vs. NP06 May 2015
In the following post, I’ll show you how a problem in theoretical computer science relates to a cure for cancer.
About a month ago, I had the blessing to study vs. for my discrete mathematics class. While we only spent about five minutes discussing my first taste of theoretical computer science, I was desperate to have a greater understanding of the topic. While studying the topic independently, I came across this phenomenal introductory video:
While summarizing this video to everyone in the hallway of my dormitory, my good friend came back with a book on the subject: The Golden Ticket by Lance Fortnow, chair of the School of Computer Science at Georgia Tech.
If you chose not to watch the video, fear not. I’ll give you a very rudimentary understanding of the topic without getting too technical (the author of the video did it far better than me):
- is defined as the set of all problems that can be verified by a computer about as quickly as they can be solved. Examples of include practically any type of mathematical operation: addition, subtraction, multiplication, division, and even some factorization. The stands for “polynomial time”; meaning that the efficiency of the algorithm used to solve the problem is bounded by the size of the problem’s input. (For those with some discrete mathematics background, means that the number of steps required to complete the algorithm is , where is the size of the problem’s input, and is some nonnegative integer.
- is a little bit trickier: it is the set of all problems that can be quickly verified by a computer, but cannot quickly be solved. Many truly intriguing problems are NP-problems: the travelling salesperson problem, the job shop scheduling problem, finding solutions to Hamiltonian paths, and finding prime factors of huge numbers (like 232-digit numbers). stands for “nondeterministic polynomial time,” meaning that the problem can be solved by a nondeterministic Turing machine (NTM). From what I understand, problems that can be solved by a NTM can be solved by checking every single possible solution.
For simplicity, stick the definitions I provide in the first sentence of each bullet, for that is what and truly boil down to according to Cobham’s thesis. From here, we must make note of a couple important observations:
- Any problem is an problem. This is because any problem also satisfies the definition of an problem. Think about it: an is pretty broad: it is any problem that can be solved by checking every single possible solution. problems can naturally be solved this way, and so we can say that (that is, the set is a subset of the set ).
- Some problems have first been classified as , only to be discovered to actually be part of as well: finding gigantic prime numbers is the most highlighted example.
The fact that some problems are later discovered to actually be part of begs the question: does ? That is, is every problem with an easily verifiable solution also easily solvable? I’ll give you a couple of examples of -complete problems: the hardest of all problems that computers haven’t been able to solve. The nature of -complete problems is that if we can find a fast and reliable solution to one, we can theoretically find solutions to any problem. Take a look:
- The travelling salesperson problem. It asks if there is an optimal way to travel to a variable number of cities. It is easy to figure out the best (shortest) way to travel between a small number of cities, but the difficulty of the problem grows at a hyper exponential rate as the number of cities needed to travel to gets greater.
- Sudoku. Being able to check that a solution to a sudoku puzzle is correct is simple enough: all you have to do is check that each row, column, and sub-grid contain the digits from 1 to 9 once and only once. With a standard nine by nine grid, sudoku can be solved and verified by a computer with ease. But if the sudoku grid becomes 1000 by 1000, you can bet that a computer will have a tough time solving the puzzle in a reasonable amount of time.
- Tetris: you know, that game you played in middle school when you should have been perfecting your skills in typing class? As Fortnow describes in The Golden Ticket: in “traditional Tetris you don’t know what shape will come next. But even if you knew the order of the shapes ahead of time, playing Tetris optimally is…NP-complete” (63).
- Factoring large numbers. If you’re anything like me, you might have trouble realizing that . I didn’t choose this factoring problem randomly: if you noticed, both and are prime numbers. As it turns out, finding prime factors of numbers that are hundreds of digits long is difficult. So difficult, in fact, that it requires research teams multiple years to find the factors of just one astronomically large number. If it took more than a half a dozen Ph.Ds armed with computers more than two years to figure out one of these factoring problems, imagine how difficult it would be for one computer to do it by itself. (Keep in mind that it is a good thing that computers have such a difficult time doing this task. Finding the prime factors of large numbers is the basis for RSA encryption, which is the premier cryptographic method for things like online banking).
As I already mentioned, the problem regarding and is determining whether the two equal one another. If you get mesmerized by graphs, this is how and breaks down:
That’s all well and good, but I think the world-at-large would have a better understanding of the gravity of and if they understood the problem’s consequences, and that is where is Fortnow’s The Golden Ticket comes into play. Before I describe Fortnow’s interpretations of a world, consider a quote from Scott Aaronson, a theoretical computer scientist at MIT:
If , then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found.
What I like about Aaronson’s quote is that it bridges the divide between a layman’s understanding of problem solving and a theoretical computer scientist’s understanding of problem solving. There is also the incredibly powerful message that the quote delivers as well: the fact that in a world, so long as you can recognize that a solution to a problem is correct, you can also find a way to solve that problem quickly.
Fortnow, too, paints a picture of what the world would be like if . A picture so broad, in fact, that he devotes an entire chapter of The Golden Ticket to it! In particular, Fortnow applies the results of a world to a woman’s trip to the doctor’s office. In Fortnow’s story, the woman is diagnosed with pancreatic cancer through a simple blood test. The real kicker, however, comes in regards to treatment. As the doctor explains,
Much has changed in the last decade. General approaches to cancer have had limited success. We realized that one needs an individual approach. We can examine a person’s DNA as well as the mutated DNA of the cancer cells and develop proteins that will fold in just the right way to effectively starve the cancer cells without causing any problems for the normal cells. The dead cancer cells just wash out of the body (15).
Fortnow is describing what the Hackerdashery YouTube video calls “protein folding”: one of the most promising theoretical cures to cancer. A world would allow for the creation of such individualized proteins for the treatment of cancer through efficient and fast algorithms that could find just the type of protein needed for the job. Were we to prove that , we could effectively find a cure for cancer that involves protein folding. That’s how theoretical computer science relates to cancer. (See? I did what I promised!).
Don’t get your hopes up, however. The vast majority of theoretical computer scientists believe that . The overarching significance of this scenario is that computers just can’t solve everything. In a time where tech start-ups are claiming they can do just about everything for you, there is a race in academia to figure out whether they can theoretically back up that claim. That race is versus , and you now have the understanding of it to annoy others about it over a meal. Go tell your mother about it!
Better yet, go develop a proof for it. I’ll wait here patiently.