Archive for the 'Computer Science' Category

Proof that P = NP

Published on May 6, 2008 in Computer Science. 0 Comments Tags: , , .

In computer science, the efficiency of algorithms is generally written in the form of a function indicating the maximum amount of operations that must be performed for a given input size.  For example, in the case of a linear search through a list of n items, the computational complexity would be written as O(n), meaning that for every additional item, one more operation must be performed.

However, many algorithms cannot run in O(n) time, or even close to it.  For example, take, once again, the traveling salesman problem, in which the algorithm must find the optimal route between several cities without ever visiting one more than once.  The simplest solution runs in O(n) time, while even a better solution using dynamic programming still only runs in O(n22n).  Because, as far as anyone can find, this algorithm cannot be reduced to run in polynomial time (that is, O(nsomething)), the problem is considered to be NP-complete.

Unlike the aforementioned problem, many problems have solutions that do indeed run in polynomial time, which are known as P.  However, while no one has found polynomial-time solutions to NP-complete problems, this doesn’t necessarily mean that they don’t exist.  In fact, no one has yet provided a proof that, indeed, such problems cannot have polynomial-time solutions; there’s even a $1,000,000 prize out there for the first person to provide a correct proof!  As such, I have created the following infallible proof:

P = NP
P/P = NP/P
1 = N
Therefore,
P = (1)P
P = P
By the Reflexive Property of Equality, this is always true.

QED

The Traveling Salesman Problem

Published on April 21, 2008 in Computer Science. 1 Comment Tags: , , .

imageYou may have already heard of the traveling salesman problem.  Basically, the idea is that you are an extremely obsessive traveling salesman with a map of cities connected by roads, and your job is to determine the best path that hits every city only once and leaves you back at the starting point.  Also, you’re a robot.

The easiest to write program that would solve the problem would check every possible route, and then pick the shortest one.  Of course, that’d be kind of slow.  Like, O(n!) slow.  (Meaning that, for every additional city you add, it will take the total number of cities times as long to finish.)

imageLuckily, there are a variety of better ways to do this.  However, instead of dwelling on these, let us move on to what is, ostensibly, the most important factor of all: the problem’s relevance to modern society.

Let’s face it: traveling salesmen are a thing of the past, like record players or 1972.  Therefore, I propose re-writing the narrative of the problem to the traveling terrorist problem, in which the salesman, now a multi-national terrorist organization, must strive to destroy each city as quickly as possible, without revisiting any, in an effort to avoid the authorities.  As the programmer, it’s your job to find out what route they will take BEFORE ITS TOO LATE.

Think about it: which would you rather be doing–helping some salesman peddle his low quality, probably counterfeit, goods, or FIGHTING EVIL BY PREDICTING ITS OPTIMAL ROUTE?

That’s what I thought.