Do you enjoy solving puzzles and brain teasers? If so, you may be familiar with the concept of computational complexity. It’s an intriguing field of computer science and mathematics that studies how efficiently a problem can be solved using algorithms and computers.
For me, one of the most fascinating problems in computational complexity theory is the P vs. NP enigma. Why is it so crucial? And what does it have to do with popular games like Tetris, Sudoku, and Super Mario? Let me break it down for you.
The spectrum of problem-solving
Since the dawn of time, people have been solving problems. But not every problem is as difficult as the next. In fact, some problems are much easier to solve with computers than others. We can visualize that by looking at computational difficulty as something that increases as you move along a line like this:
P: predictable problems
On this line, something on the left is easier than something on the right. Sorting a list of names alphabetically is — unsurprisingly — an easy problem to solve. But sorting is boring, simply because it’s so easy. These easy (boring) problems are all in a set we will call P. The easiest problems we know are problems in the P set.
NP: challenging, but solvable problems
There are other — more interesting (read: more difficult) — problems like Tetris, or (generalized) Sudoku, or even Super Mario Bros. Let’s put these difficult problems in another set, namely NP. What’s so special about the problems in NP? Well, if you propose a solution to a problem in NP, a computer can easily check whether it is valid.
For example, in Tetris: if I’m given a series of blocks to position in a particular way in a given situation, then a computer can easily check whether I’ll ‘survive’ (assuming my fingers are quick enough to get the blocks right, but for a computer that’s clearly not a problem). Or in Sudoku, if I put a particular number in a particular square, the computer can easily check whether the proposed solution is sure to be correct (meaning that there can be no other number in that same square). And in Super Mario Bros, I can easily carry out the list of suggested moves to see if it gets Mario from A to B.
Of course, that means that every problem in P is also in NP. Let’s update our line with the new set NP:
What’s the fundamental difference between P and NP problems? The answer is complexity. It’s much more difficult to quickly find a solution to an NP problem than a P problem. Computers can easily check solutions to NP problems, but devising an algorithm that can propose solutions to NP problems in a reasonable time is much more difficult. That’s what makes NP more interesting!
NP-hard: bad boy problems
It turns out that there are some problems we don’t even know how to solve quickly with our current knowledge. We call this set of problems NP-hard, defined as all problems that are at least as hard as the hardest NP problem. This means that some of them are in NP, but some of them are outside NP. Here’s our updated line:
Some of these NP-hard problems are so tricky it’s not just difficult to find solutions, but it’s difficult even to check them! These are what I like to call the ‘bad boy’ problems, a subset of NP-hard.
NP-complete: the key to solving NP-problems
And let’s now also introduce the NP-complete subset for those NP-hard problems where solutions can be checked easily.
NP-complete problems are therefore problems that are in both NP and NP-hard. They’re really on the border between NP and the bad boys. And here’s a fundamental characteristic: if you can solve an NP-complete problem quickly, that means you can solve all the hardest problems in NP quickly and, therefore, you can solve them all quickly. So, solving an NP-complete problem quickly is like finding a master key. So, now the complete line looks like this.
Oh, and how about Tetris and the other examples I gave? Well, Tetris is not a bad boy problem but an NP-complete problem, meaning that solutions can be checked easily but we don’t know yet how to solve the problem quickly. Similarly, Sudoku and Super Mario Bros are also NP-complete problems. So, let’s add these to our line:
The enigma of P vs. NP: Is there a shortcut to solving hard problems?
Now that you understand all of this, I can clarify the P vs. NP problem, one of the biggest mysteries in computer science and mathematics. So, the big question is: can we find a shortcut to solving complex problems? The thing is,we haven't been able to find an NP-complete problem that's also in P, which would mean that all NP problems could be solved quickly and easily.
Computer scientists have been trying to solve this problem for decades, but we still don't have a definite answer. In fact, theClay Mathematics Instituteis offeringa $1 million prize to anyone who can prove that P = NP. Or, if you’re not of good faith, and you find a solution without telling anyone, you could even make much more money than that!
Most (sane) people in the field believe that P and NP are different, meaning that there will always be problems where the proposed solutions can be checked easily but not produced easily. But no one knows for sure.
Creative ways to solve supply chain planning problems
When it comes to supply chain planning, some problems are straightforward, but most are challenging.In fact, many of the problems that arise fall into the category of NP-hard, such as sourcing and distribution, campaign and cycle planning, product mix optimization, allocation and sequencing, cutting, and blending. Unfortunately, the P vs. NP enigma means there is no master key to solve these problems.
At OMP, we know that we need the brightest minds to help us solve these problems. We believe thatcreative thinking is essential, and that there's no one-size-fits-all solution. Instead, we rely on innovative, tailored approaches to tackle each issue head on. Being part of the OMP solver team means constantly pushing myself to find new and better ways to tackle the toughest supply chain problems. It's not easy, but that's why I love what we do!
If you enjoy solving complex problems, then the OMP might be the perfect fit for you. We are always looking for talented individuals who share our passion and are willing to think outside the box. So, why not explore our opportunities today and see if we click?
