P = NP

by Anon84 • 13 years ago

46 50 13 years ago

pfortuny• 13 years ago

I would wait until the paper has no more corrections made at least for a whole non-summer month. Well, it looks like there were no corrections in October but maybe he took his vacation then?

Give it some more time, I suggest.

robinhouston• 13 years ago

It’s fascinating how this sort of thing keeps attracting interest. Here’s a list of 100 proofs that P=NP or P≠NP, which includes this one: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

There’s nothing to make this attempt more worthy of interest than the other 99, as far as I know.

quchen2• 13 years ago

Which makes me wonder: how do you filter these? In physics it's common practice to ignore papers about Perpetuum Mobiles (excuse the probably incorrect plural), but here we have a topic that is somewhat easy to write good and bad about while still having very high relevance.

j2kun2• 13 years ago

Here's two lists of ways to filter. They're heuristics, but they work well.

One for general mathematical proofs: http://www.scottaaronson.com/blog/?p=304

One specific to P != NP: http://www.scottaaronson.com/blog/?p=458

DanWaterworth• 13 years ago

Can anyone comment on how credible this is. It seems to have been submitted many times.

this_user• 13 years ago

Every once in a while some publishes a paper that seeks to prove that N equals NP, but so far none were conclusive. Given that track record and the fact that the all existing evidence points to N unequal NP, I would be very cautious with this paper.

jessaustin3• 13 years ago

I'm not going to dig into the paper, but I note that the abstract claims a constructive proof. I sort of assume that anyone with such a proof could organize a convincing demonstration by letting a disinterested observer provide a series of random numbers while clicking a stopwatch.

petercooper• 13 years ago

But only when N is 1 or P is 0.

skykooler• 13 years ago

This was already posted here. It is fatally flawed in that, although the theoretical computing time is polynomial, the memory required grows exponentially.

topynate• 13 years ago

I'm confident that the paper is indeed flawed. However, a Turing machine can neither write to nor read from an exponential number of locations in polynomial time, so the flaw will be something else.

jmpe• 13 years ago

Memory growth is not a consideration in the academic proof, Turing machine tape is infinite in both directions.

taejo• 13 years ago

Turing machines have may have infinite memory, but they can also only write one step per cell. So a polynomial-time TM can't use superpolynomial memory.

jessaustin3• 13 years ago

In addition to what siblings said, remember that P is a subset of PSPACE.

Gurkenglas• 13 years ago

I think the statement you meant to remind us of is that NP is a subset of PSPACE.

skj• 13 years ago

This statement is not quite coherent. If there is an exponential memory growth, then there is exponential computing time because memory growth doesn't happen magically.

ronaldx2• 13 years ago

Since P refers to polynomial time, it's not clear to me that a memory requirement is relevant.

heron872• 13 years ago

A definition of P indeed does not require a restriction on memory use. But the definition implies a restriction on memory: a polynomially bounded (in time) machine cannot use exponential memory (because reading 2^n cells on a tape requires 2^n time steps).

jnazario• 13 years ago

seems like a solid argument to me for peer reviewed publications.

mion5• 13 years ago

The best intuition I've read that P = NP can't possibly turn out to be true, is that if it were, you could write a piece of music as easily as you could appreciate it.

Also, I can't imagine the answer to something as fundamental as this coming out of a hacky solution. There's probably a more elegant, natural way to prove it. And by natural I mean maybe they should start looking outside Turing's theory.

Trufa• 13 years ago

That is a brilliant way of putting it, thanks!

hansbo• 13 years ago

I've read that one too, but I don't particularly like it. P=NP implies only that all problems which can be verified in polynomial time can also be solved in polynomial time, not necessarily that it can be solved as quickly, nor that it can be solved easily.

Perhaps writing a piece of music is also done in polynomial time, but it requires more training (more advanced algorithm)? Or, perhaps, the time complexity is x^3 for writing, instead of x for appreciating.

mion5• 13 years ago

Agreed, it is bit sensationalist. But what if someone proves it and then we realize that even though it can be done in polynomial time, there's some other constraint (like "x^N but N has to be super big") that renders the result impractical?

I think once someone proves it, it will be obvious in hindsight as a lot of people are just ignoring the isomorphisms in nature.

tetha• 13 years ago

Yup, doing a big of handwavy math also demonstrates this: You are comparing something like x^N - x^M with 2^x - x^M. The second will always grow big rapidly, while the first could stay small, but it can also grow arbitrarily large. In fact, it is bound to do so for N > M and it will do so quite rapidly if N >> M.

Tmmrn• 13 years ago

if it were, you could write a piece of music as easily as you could appreciate it.

Yea, but maybe it would still be exactly 1.000.000 times as hard.

mion5• 13 years ago

Meaning you wasted a shit ton of time trying to prove something obvious :)

biofox• 13 years ago

When I'm drifting off to sleep, I frequently hallucinate polyphonic songs. Real time composition. P=NP? :)

Houshalter2• 13 years ago

The best intuition I've read that P = NP can't possibly turn out to be true, is that if it were, you could write a piece of music as easily as you could appreciate it.

Your intuition isn't always correct, there is algorithmic music that can sort of do this already. And just because it seems weird doesn't mean it's impossible, just that no one has figured it out yet.

mion5• 13 years ago

This is why I said intuition. What I meant is that N = NP would suggest, for instance, that the amount of effort needed to appreciate a brilliant piece of music (e.g. Mozart, not any music) is in the same "space" of the amount of effort needed to create it.

You can find many examples of things in nature that are "hard to solve" yet "easy to verify".

j2kun2• 13 years ago

This is also a bad analogy because human beings tend to be extremely good at solving, or at least approximating close solutions to, NP-complete problems (on small instances).

Aardwolf• 13 years ago

A proof that P=NP without an accompanying program that solves SAT or another NP problem in polynomial time does not count to me :)

raverbashing3• 13 years ago

I agree

And let me say, I don't even care about a paper. Sure, it's useful, but it shouldn't be the focus.

A simple implementation that solves any of the NP problems in polynomial time is a much better proof than any article.

(of course, those that prove P != NP can't do that, still)

aeurielesn• 13 years ago

I beg to disagree with both of you.

You are kinda disrespecting the important of theoretic research, and a big part of any field of interest on research.

quchen2• 13 years ago

A simple implementation that solves any of the NP problems in polynomial time is a much better proof than any article.

That completely misses the point of P vs. NP, which is not about programmability but a problem entirely of theoretical nature (and interest).

- O(n^<Graham's number>) is in P. (If you can solve TSM in that time, you've proven P = NP.)

- Cracking AES-256 is even easier than P: it's O(1).

dllthomas4• 13 years ago

A program isn't a proof. It's perfectly possible to solve restricted cases of an NP-problem in polynomial time. Doing so in enough of the test cases people throw at it to fool people for a while would itself be a huge accomplishment, but it would still be entirely possible that P != NP while I'm holding a program that has solved every NP problem I have thrown at it in P time (especially if that P is large).

elwell2• 13 years ago

You would benefit from both, or you might have doubts the NP problem that was solved was ever actually NP.

Sniffnoy2• 13 years ago

He does give pseudocode in the paper for transforming an NP problem M<NP> into a P problem. It should be straightforward to apply this with M<NP>=SAT. (Whether it actually works is another matter...)

doughj3• 13 years ago

How did this go from being #3 on the front page of Hacker News to non-existent even two or three pages back?

elwell2• 13 years ago

Moderation

simgidacav• 13 years ago

Even if this content is quite old, the idea of linking it here in those days is quite clever. Just tell me how many of you did not immediately think "Oh crap, my RSA is doomed!".

Houshalter2• 13 years ago

Cryptography? Really? Wouldn't this mean you could create absurdly intelligent AIs and solve pretty much any optimization problem?

P = NP

Related Stories