Sten-Ake Tarnlund claims to have proved that P != NP, the most famous conjecture in theoretical computer science. Here’s the paper on arXiv. Since proposed proofs of famous theorems usually turn out to be incorrect, it’s too early to get excited.
The paper claims that “SAT,” the Boolean satisfiability problem, is not in “P,” the set of problems that can be solved in time equal to a polynomial function of the problem size. Since the SAT problem is NP-complete, showing that SAT is not in P would show that NP does not equal P.
{ 1 comment… read it below or add one }
sohail 11.01.08 at 11:00
When I was in school, a professor said that we would be millionaires if we solved the P!=NP problem. Then he laughed.