P vs NP Problem has us wondering if there is a way to determine whether we can solve problems quickly in polynomial time. Why? Because solving problems in exponential time isn’t doesn’t always allow us to solve these problems due to the explosive growth when the input starts getting large.

For example, the Traveling Salesman is an NP Complete problem. Given a list of cities and their distances between them, the task is to find the shortest possible tour in which each city is visited exactly once. Sure, heuristics have been made to solve sets of these problems, but a single algorithm to solve these problems in polynomial time hasn’t.

Solving the following P ?= NP question would determine if it would be possible to find if these NP problems could be solved in linear time. So yes, solving this problem is kind of a big deal. It may be regarded as one of the top (or the top) question in Computer Science. It also is a Millennium Prize Problem so whoever solves it is awarded 1M dollars.

For now, all we can do is wait and determine if the paper forwarded from Vinay Deolalikar proves that P != NP. The paper is over 100 pages and is quite a read. So if ever thought reading publications in the science field was tough, get prepared.

This was first uncoverd by Greg Baker at his blog.

Sources:
P vs NP
Traveling salesman problem