Once upon a time, there was a chocolate factory. It produced chocolate bars which were sold all over the world. The proprietor of the factory hid a handful of Golden Tickets in some of the chocolate bars. For those who were lucky to find the Golden Ticket could have a tour to the mysterious factory and a lifetime supply of confectionery.

A poor young boy, Charlie, dreamed of visiting the chocolate factory and was eager to find that Golden Ticket. The chance of him getting the ticket was slim. What should he do? He could buy up as many of the chocolate bars as he could. He could try using a magnet, but gold is not magnetic.

Veruca, a kid of a rich business man, also wanted the Golden Ticket. Her father decided to buy up all the chocolate bars that he could find. Well, having a large mound of chocolate bars didn’t make the ticket any easier to find. No matter how he tried to find that ticket, he would need a considerable amount of time, money, or luck. Maybe someday someone would develop a cheap device that would let him find that ticket quickly, or maybe such a device would never exist.

NP Problem

The problem faced by Charlie and Veruca above is an example of NP problem. NP stands for non deterministic polynomial time. It is all about the time taken to solve a problem which is non deterministic. It is about computational complexity. The solution(s) of a NP problem can be verified in polynomial time but it does not necessarily mean that the solution(s) can be found as quickly as in polynomial time. If this was the case then we have where we would be living in a beautiful world. More about this later.

There are several NP-naming conventions: NP, NP-Complete, NP-Hard with each has a different meaning.

Quoted from Wikipedia:

NP is a class of computational problems for which solutions can be computed by a non-deterministic Turing machine in polynomial time (or less). Or, equivalently, those problems for which solutions can be checked in polynomial time by a deterministic Turing machine.

NP-Complete is a class of problems which contains the hardest problems in NP. Each element of NP-complete has to be an element of NP… the most notable characteristic of NP-complete problems is that no fast solution to them is known… This means that the time required to solve even moderately sized versions of many of these problems can easily reach into the billions or trillions of years, using any amount of computing power available today.

NP-Hard is a class of problems which are at least as hard as the hardest problems in NP. Problems in NP-hard do not have to be elements of NP, indeed, they may not even be decision problems… NP-hard problems may be of any type: decision problems, search problems, or optimization problems.

The level of “hardness” (complexity) increases from NP → NP-Complete → NP-Hard. The wonderful characteristic of NP problems is that, if there existed an algorithm that could solve one of the NP problem efficiently, then the whole class of problems could also be solved efficiently.

More examples of NP problems

Here are some of the common puzzles or problems which are from NP class: large Sudoku, Minesweeper, Tetris, Candy Crush Saga, Traveling-Salesman Problem.

Sudoku

Sudoku’s solution is easy to verify. Hence, it is a NP problem. But is it easy to find a solution? For a standard 9 x 9 Sudoku, a traditional computer can solve the puzzle in a couple of seconds. How about a 25 x 25 variant, where every row, column or square must have every number from 1 to 25 exactly once? A naif computer search will take a significant amount of time. A 100 x 100 games can defeat today’s fastest machines.

Minesweeper

Minesweeper is a game that’s installed by default on most computers that come with Windows. Minesweeper is a deceptively simple test of memory and reasoning. The goal is to find the empty squares and avoid the mines. You click on a square to reveal a number that tells how many mines lay hidden in the eight surrounding squares - information you use to deduce which nearby squares are safe to click. Determining whether one can win a large Minesweeper game is NP-Complete.

Tetris

In Tetris, the player slides and rotates pieces to fill a row and once a row is filled it disappears. The goal is to play as long as possible until you run out of rows. In traditional Tetris, you don’t know what shape will come next. But even if you knew the order of shapes ahead of time, it is still a NP-Complete problem to play it optimally.

Candy Crush Saga

Candy Crush Saga is currently the most popular game on Facebook. It has been installed half a billion times on Facebook, and on iOS and Android devices. Playing Candy Crush to achieve a given score in a fixed number of swaps is NP-hard. See the prove here.

Traveling Salesman Problem

This is a classic example of NP problem. Given a certain number of cities, determine the shortest distance to cover all the cities at least once. The number of possible solutions for this problem is with the number of cities.

Given 10 cities, there will be 1814400 possible solutions. Finding the shortest distance among 1814400 is still within today’s computer capacity. With 20 cities, there will be 1.216451e+18 possible solutions (1 with 18 zeros). Still manageable. What about 30 cities?  There will be 1.3262643e+32 possible solutions to scan through. The number of possible solutions increases exponentially.

The Beautiful World

If , which means the NP problems can be solved quickly just like the time it takes to verify the solution, then we would be living in a beautiful world as described in The Golden Ticket: P, NP, and the Search for the Impossible.

If there is an algorithm that can solve NP problem quickly and efficiently, we would be living in a fantasy world. The algorithm could be used to decode the DNA and make cancer detection in seconds, make better weather prediction a year ahead of time, schedule a perfect game play in sports, track down the criminal suspects using DNA alone to predict not only physical features such as height, eye, and skin color but also personality traits and likely careers… There would be tremendous progress made in technology.

However, there is dark side of the beautiful world. The encryption technology used to send credit card number securely to companies over Internet would break down. The privacy of every human being would be compromised since not only can innocuous video cameras immediately recognize people and track them, algorithms can accurately predict the trips you take, the music you listen to, the movies you watch, and the products you purchase. The computers know more than you do.

Sound hard to believe that a single algorithm can change everything? That everything we can recognize we can find quickly? That we can learn everything quickly? In fact, the P versus NP problem (proving  or ) is a major unsolved problem in computer science.

Snippet

I suspect that the ComBUStion puzzle is NP-Hard. It involves scheduling optimally the resources (in this case the drivers) while satisfying the constraints to obtain a maximum score.

The search of the missing MH370 is definitely an example of NP problem. The search space is so large that no human being can effectively tell how and when the missing plane will be found.

Knowing the optimal solution for one instance of a specific NP problem won’t increase the efficiency of the next search by large degree. You need to start all over again. Just take the missing MH370 case as a reference, do you think that after finding the missing MH370 aircraft, we would know better where to search if in the future there is another flight incident happen in the Pacific ocean?

Writing this article optimally is NP-hard. There are just infinitely many ways to structure an articles, choose which examples to use, which words for best conveying the meaning, etc. There are problems that are harder than NP-hard.

Life puzzle

Life is more than NP-hard. There are problems that are not following any algebraic structure, hence impossible to evaluate even the number of possible solutions. We can count the number of possible solutions for the traveling salesman problem given any number of cities. But how do you count the number of possible ways to transform raw ingredients into products for example. There is an unlimited ways to do things and there are even more ways to do things that you don’t even know you could. Think about the unknown’s unknown.

It is unwise to find an optimal way to do everything since it is nearly impossible based on current technology. At least you won’t be able to find that optimal solution during your lifetime unless you are LUCKY that you happen to find the golden ticket.

Success is luck (most of the time). Since almost every decision is sub-optimal (we know that getting to an optimal decision is nearly impossible), people can be successful with sub-optimal solution by the natural selection which is random. Life is therefore 99% determined by luck and 1% by effort since the search space is incredibly large that you could not possibly explore more than 1% of it during your lifetime. Well, I think 1% is way over estimated of our capability.

Finally a (pseudo-)proof that luck matters a lot in life. 🙂

How to improve your chance of success

Search harder. Just like scientists who use more powerful machines can reach the solution quicker. Same for highly motivated human who keeps learning and experimenting to find the golden ticket.

Or use heuristic, which refers to experience-based techniques for problem solving, learning, and discovery that gives a solution. It is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. It is closer to practical life but it won’t guarantee an optimal solution.