P != NP (awaiting peer-review)

[Dintiradan]

Not many of you will care, but for those who do:

 

http://www.scribd.com/doc/35539144/pnp12pt

 

Welp, there goes the rest of my evening as I try to comprehend part of this. Hopes of this being error-free are low right now, but still...

[Lilith]

this is p cool

[Dintiradan]

Bah. This jumps between disciplines far too much for my puny mind to comprehend. I grok some of this simpler complexity theory and statistics concepts, but the rest... I'll wait until this passes peer review before I dive into the main parts of the paper.

 

Still, not every day that a solution to the biggest open question in your field is proposed. I'm excited, even if no one else is.

 

EDIT: It's got Stephen Cook's attention, so it must be somewhat legit.

[The Mystic]

In the meantime, this is way beyond me.

[Dantius]

Originally Posted By: Dintiradan

Not many of you will care, but for those who do:

http://www.scribd.com/doc/35539144/pnp12pt

Welp, there goes the rest of my evening as I try to comprehend part of this. Hopes of this being error-free are low right now, but still...

So he's a millionaire now? Or was that prize offered for some different mathematical proof?

[Lilith]

It's one of the seven Millennium Prize problems, yeah. The solution will have to be verified before the prize is awarded, of course.

[Skomer]

Originally Posted By: Lilith

It's one of the seven Millennium Prize problems

I read that wikipedia article and thought "hang on a minute". Last night I started reading a book about prime numbers and the Riemann Hypothesis. The first few pages are the story of the physicist who finally cracked it in 1997, and the mathematician Bombieri who publicised it. Surprising, then, to see it on the list of Millennium problems.

But today I reached page 12, where it turns out that Bombieri made up the whole thing.

[Aran]

As long as it is not explained why his proof that 3-SAT (NP-complete) is not in P doesn't apply to the 2-SAT and XOR-SAT problems as well (which would be incorrect, since 2-SAT and XOR-SAT are both in P), it's probably broken.

 

The summary of the issue goes like this, basically (for everyone too lazy to read Wikipedia or too intimidated by its terminology):

 

There are some problems computers can solve fairly fast, like searching an unsorted list (n), comparing every pair of elements in a list to each other (n²), etc. Importantly, "fairly fast" just means "polynomial" - n^5 or n^10 are actually very slow algorithms, but they still count as polynomial. The set of these problems is called "P".

 

Then there are some problems where a given solution can be checked quickly, but where an unknown solution can (so far as we know) only be found by brute-force checking of every possible solution. Since all possible solutions are usually permutations or combinations, that means there is an exponential number of them. For example, there are 52^10 possible mixed-case passwords with ten letters, or 10!=10*9*8*7*6*5*4*3*2 possible ways to arrange ten different given letters. Since exponential functions grow faster than polynomial ones, that means such a problem takes much longer to solve. The set of problems that are easy to verify, are called "NP", for "non-deterministic polynomial", the problems that are hard to solve are "NP-hard", and the problems that are both are called "NP-complete".

 

The important part is that since "NP" is an upper bound on difficulty, all "P" problems are contained in "NP". The question everyone has been trying to answer is whether the reverse is also true: That is, whether there is some magical algorithm that can solve NP-complete problems in polynomial time as well. This is almost certain to be false, but there is no proof for that yet.

 

As it applies to this proof: The proof appears to focus on proving a well-known NP-complete problem to be actually unsolvable in P time. One important thing about NP-completeness is that all such problems are interchangeable: solve one problem in P-time, and they're all solved; prove one unsolveable in P, and they all are.

 

The NP-complete problem he chose is called 3-SAT. The input is a Boolean formula like (x OR !y OR z) AND (y OR k OR !x), consisting of a number of bracketed parts connected by AND, each of which contains 3 variables (possibly negated) connected by OR. The solution (if it exists) is a combination of values for the variables (for example: x = y = z = TRUE, k = FALSE) that make the whole formula TRUE.

 

This is an interesting one because there are slight variants that are far easier to solve (ie. in P), which are called 2-SAT (the same problem, but only 2 variables per clause) and XOR-SAT (the same problem, but only requiring that an odd number of parts must be true, rather than all of them). From the comments I've read so far, the prover hasn't been able to adequately explain why the proof doesn't apply to these variants as well. If it did, then it would have to be wrong.

[Student of Trinity]

Ha! Thanks very much, Aran, for a lucid explanation.

 

I don't actually use algorithms directly much in my work, or in my life for that matter, though of course they are running unbeknownst to me all the time. But I have the idea that this part of computer science is actually a very fundamental part of philosophy, saying something about how things really are. In this sense, this P != NP issue is something that should interest everybody.

[Slawbug]

What does it say about how things really are?

 

It sounds like it says something about how certain types of patterns really work, but is that the same thing?

[Student of Trinity]

To me, yes. One of the basic questions I have is, What is the difference between reality and fiction? Since I take a kind of Platonic-idealist view of physics, this is a real question in my mind. Insofar as current physics is correct, the bottom line deal with the universe is a vector in a really large Hilbert space. That's just a pattern of numbers.

 

What's the difference between that pattern, and the pattern I make by typing this post? I too can say, "Let there be light!" But it doesn't seem to work when I do it. Why not? What's God got, that I ain't got?

 

The idea that some patterns are qualitatively more complex than others is important. It's not at all clear to me that the line between NP and P in particular is philosophically significant, but I think that lines of this general kind are.

[Dantius]

Originally Posted By: Student of Trinity

I too can say, "Let there be light!" But it doesn't seem to work when I do it. Why not? What's God got, that I ain't got?

You mean aside from being omnipotent, omniscient, omnipresent, and omnibenevolent?

[Student of Trinity]

Well, exactly. But what do those things actually mean? To say that God creates light by speaking the words and I don't, because God is omnipotent and I'm not, is just a reiteration, not an explanation.

 

Some people would argue that we are to God as the characters in a novel are to the novel's author. Others would say that we are to God as a semicolon is to the author. I say that we are to God as a semicolon is to God.

 

We are just patterns. Hence my interest in classes of patterns.

[Dantius]

Originally Posted By: Student of Trinity

Well, exactly. But what do those things actually mean? To say that God creates light by speaking the words and I don't, because God is omnipotent and I'm not, is just a reiteration, not an explanation.

Some people would argue that we are to God as the characters in a novel are to the novel's author. Others would say that we are to God as a semicolon is to the author. I say that we are to God as a semicolon is to God.

We are just patterns. Hence my interest in classes of patterns.

This sound suspiciously like what a witch would say!

Do you weigh more than a duck? Just asking...

[Student of Trinity]

No, no I don't.

[Slawbug]

superb answer. the first one.

[Sticky]

Bump - but I've spent a lot of time over the past month trying to optimize the selection of acceptable solutions to something like the example problem, and I was amazed to find something on the subject here! I hadn't even realized that it was a studied subject.

[Alorael at Large]

It turns out the proof contained a number of errors. P has gone back to being sort of but not exactly kind of somehow related to NP or maybe not.

 

—Alorael, who wishes you luck with solving NP-complete problems.