Don't all of you talk at once! Anyway, if you solve the problem you win a MIILION DOLLARS (seriously), so maybe that will raise interest. I'll explain the problem.
P is the set containing all polynomial-time deterministic problems that have solutions. NP is the set containing all polynomial-time nondeterministic problems that have solutions. You win the million dollars if you can prove that set P is equal to set NP, or if you can prove set P is not equal to set NP. The problem is so hard that nobody knows whether we live in a world where there are polonomial-time solutions to problems we would normally have to guess at. Let me explain further...
A problem in NP is a problem that a nondeterministic Turing machine can solve in polynomial time. This is just a fancy way of saying that a problem in NP is a problem requiring a guess at some point in time of what to do next before we can solve the problem. If the problem can be solved by guessing the "right" thing to do every time, then it is in NP.
A problem is in P if it can be solved by an algorithm in polynomial time. The algorithm is always performing what it was designed to do, and never makes a guess as to what it does next.
Here is where it gets interesting. It has been proven that all problems in NP can be transformed to a certain type of problem that is said to be NP-complete. An NP-complete problem is said to be hard - so hard that if we can solve it we can solve any other problem in NP. This is incredibly useful to someone who wishes to prove P=NP. If there exists a deterministic solution to an NP-complete problem, then we would know that P=NP.
In 1971 the satisfiability problem was proven to be NP-complete. The satisfiability problem is as follows. Given a Boolean expression with N variables, does there exist an assignment of truth-values to those N variables such that the expression as a whole is true? Clearly this problem can be satisfied in polynomial time by a nondeterministic Turing machine. By guessing the "right" values for every variable, we arrive at the conclusion that the Boolean expression is either true (satisfiable) or false (contradictory).
Currently the satisfiability problem can be solved deterministically, but not in polynomial time. For a Boolean expression of N variables there exists 2^N possible combinations of these variables. We can deterministically solve the satisfiability problem by testing every possible truth-value for the variables, but the universe is not capable of providing answers to problems that are large in scale. The exponential growth of our current deterministic solution to satisfiability is simply not applicable. Let me put this into perspective.
A simple Boolean expression, expressed in modern English, would be something like "I went to the store and I had fun". There are two Boolean variables in this expression:
1) I went to the store.
2) I had fun.
Because this expression has two variables, and knowing it has 2^N possible solutions (where N is the # of variables), this expression has 4 possible scenarios to test for satisfiability. If I didn't go to the store today, then what I said was false regardless of whether or not I had fun. If I didn't have fun, then what I said was false regardless of whether I went to the store. The only way we could "satisfy" what I said would be if "I went to the store" is true and "I had fun" is true.
Now, wasn't it easy to prove that sentence was satisfiable? This was because it only had two variables totaling 4 scenarios to test for satisfiability. Now suppose we created a sentence containing a thousand variables. “I went to the store today and I had fun and I ate dinner and I didn't meet Wonda, or I did meet Wanda and didn't go to the store and...” At first you may think 1000 variables wouldn't be too much trouble. Computers can handle billions of operations a second, and can hold billions of bytes of data. But, as I said before, our universe can't provide solutions to large exponential problems. The number of scenarios we would have to test in order to know for sure whether a 1000-variable Boolean expression is satisfiable is a number larger than 1 followed by 300 zeros. There are not even this many atoms in the entire universe.
Why is a polynomial-time deterministic algorithm that can solve satisfiablity important? Well, for starters it proves P=NP and you win a million-dollar prize for solving one of the 7 millennium-prize problems. But despite the money, if you find such an algorithm you will have created an automatic theorem-prover that could solve large logical problems within the time and space bounds of our universe. Such an invention would change life as we know it.
The bad news is most modern thinkers believe P is not equal to NP, there is no such polynomial-time deterministic solution to satisfiability, and the unniverse is a chaotic environment requiring a lot of guessing and checking. They have no proof, though, and claim what they do simply because they can't imagine a world where P=NP. I choose to believe P does in fact equal NP, and will continue to look for a way to prove it. Just by witnessing the speed and accuracy by which our brains solve highly complex logical problems, I have led myself to assume our brains have some sort of finely-tuned deterministic theorem prover.
Anyone up for further discussion?
http://www.claymath.org) is proof that you get a million dollars simply for solving one problem! I find the problem very intriguing, and mainly wrote about it because it is part of the material I am studying for my final in gasp two days.
------------------
And there he is. The reigning champion of the Boonta Classic, and the crowd favorite-TheAhnFahn
[This message has been edited by theahnfahn (edited May 09, 2001).]