Skip to content

Intractability

May 4, 2013

An intractable problem is defined as a problem where no algorithm is known that can run in any polynomial time. Cobham’s thesis says that non-polynomial problems can not be computed feasibly by any physical computational devices. An interesting example of this fact, is the brute force Traveling Salesman Problem O(N!) for 1000 cities would take an unimaginable time to process.

NP-Complete problems are the hardest of the NP problem space, and there are a lot of them. NP literally stands for “nondeterministic polynomial time“. Some interesting call outs of NP problems are: Integer programming, satisfiability, and the Steiner tree problem.

What if P=NP? What if these NP-Complete problems could be solved in polynomial time? That is the P=NP problem and it’s an open problem. P=NP is a Millenium Prize problem worth $1 million dollars. Although, P=NP would be terrific as it would open up feasible solutions to currently intractable problems. However, there are a few benefits of intractability, like security and encryption. If P was equal to NP, then our encryption techniques would be crackable in short time frames.

Intractability is the final section of Coursera/Princeton’s Algorithm 2 course, and ended with this clever song: Longest Path

Advertisements

From → Algorithms

Leave a Comment

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: