P = NP?

The prevailing opinion among academics is "P is probably != NP. But it'd sure be nice if it were."

I'm just waiting for someone to finally prove that P != NP. Then I can finally stop having to hear about it in lectures - Result!!

I think that P=NP because I'm a contrarian :-)

I was reading on sci.logic or comp.theory (one of the two) that any proof would not be able to use diagonalisation, so the question has become even harder.

There's an interesting short story by Charles Stross called 'Antibodies' about what the ramifications would be if NP complete problems were ever proven to lie in P.

I like to think that it's undecidable.

Quote:

Original post by Sharlin I like to think that it's undecidable.

It's not undecideable. NP is a subset of decideable problems. There is a solution to the problem. What is unknown is whether there is a deterministic way to find the solution or is the best we can do is just try every possiblity.

When he says undecidable, he's talking about whether P = NP. It may very well be that with the currently accepted axioms, you can't prove or disprove this.

Hypothetically, quantum computers will be able to solve several NP problems in polynomial time because they can perform all possible execution paths simultaneously using a superposition of all possible inputs. The problem is the answer will be a superposition of all possible answers. I don't exactly understand how anyone plans to extract the result, but in situations where the answer is simple, like a true or false, the true results and the false results will collapse together, simplifying the data to two states. No, I don't understand it either.

- Evan

I don't think so evan, do you know Aaronson's NP Hardness Assumption? (NPHA) It states that NP-hard problems cannot be solved with polynomial resources in the physical world.

Of course, Aaronson doesn't have to be right, but it's very unlikely that a supercomputer will be able to solve NP-problems within P-time. Several attempts have been made, but all have failed. Finding P = NP is the holy grail in mathematics but I fear that it's either impossible or too hard for us to find out.

Quote:

Original post by basananas ... Finding P = NP is the holy grail in mathematics but I fear that it's either impossible or too hard for us to find out.

Don't loose hope... people used to say the same thing about Fermat's last theorem, except for the holy grail stuff, until someone (a few centuries later, i'm afraid) stepped on the solution.

I kind of have the same opinion as Puzzler183... a piece of the puzzle might be missing. Some theorem waiting to be discovered and someone to link it up to np theory.

Quote:

until someone (a few centuries later, i'm afraid) stepped on the solution

"stepped" on the solution? There were, IIRC, two principals, and a large number of grad students/postdocs that participated in the proof. It took them years. It used advanced higher-order algebra. It was pretty clearly not the proof that Fermat scribbled about in the margin: "the proof is surprisingly simple"...

Quote:

"stepped" on the solution? There were, IIRC, two principals, and a large number of grad students/postdocs that participated in the proof. It took them years. It used advanced higher-order algebra. It was pretty clearly not the proof that Fermat scribbled about in the margin: "the proof is surprisingly simple"...

Cm'on... cool off. I was not trying to take anyones' due credit nor trying to say it was easy. We can only imagine how hard those things can be. Perhaps the word "stepped" was not very well used i recognize, but it was ment to compare the time the theorem was labeled "unsolvable" with the time it took someone to solve it (a few centuries versus a few years) and not to imply it was a easy thing to do. I recognize it was a huge work, although the press usually gives credit to only one person. And some people still have their little pet wars discussing wether Fermat had a different proof.

By the way, if i'm not mistaken, wasn't Fermat's last theorem a corolary of something they discovered? Something on the lines of "we discovered this and this and this.... oh, by the way, as a corolary, we have Fermat's last theorem".

Back to np's, just like the proof of Fermats theorem used some recently discovered theory (advanced higher-order algebra), i think it will be something like that with nps... someone discovers A, someone gets to B and someone joins A and B and has the proof that "P=NP" or "P!=NP".

Quote:

Original post by basananas I don't think so evan, do you know Aaronson's NP Hardness Assumption? (NPHA) It states that NP-hard problems cannot be solved with polynomial resources in the physical world.

There are physical processes that solve NP problems in P time though: http://www.arxiv.org/PS_cache/cs/pdf/0406/0406056.pdf.

I personally don't know what to make of it all (I don't have the formal training) but they definitely exist...

Quote:

Original post by Puzzler183 Quote: Original post by basananas I don't think so evan, do you know Aaronson's NP Hardness Assumption? (NPHA) It states that NP-hard problems cannot be solved with polynomial resources in the physical world. There are physical processes that solve NP problems in P time though: http://www.arxiv.org/PS_cache/cs/pdf/0406/0406056.pdf. I personally don't know what to make of it all (I don't have the formal training) but they definitely exist...

I think this unpublished manuscript (see prof. Bringsjord's site for an updated version) is highly mistaken, because physical systems are at best an approximation of abstract algorithms and because assuming that not only such a system can be simulated, but that the simulation can be done in polynomial time, is mere wishful thinking.
I wrote Bringsjord about that and I'm waiting for an answer.

Since quantum computers can solve NP problems in expected (but not guaranteed) polynomial time, it seems to me that NP problems are effectively P if not actually so, in the same way that many undecidable problems are solveable in most interesting cases if a few allowances are made.

Things don't need to be guarantteed solveable in the general case to have helpful results. Of course general solutions are nicer for mathematicians, but engineers get by with approximations all the time =-)

I personally think that a solution will arise by.

a) Abstracting "problem". This will help to uncover the core structure underneath problems like cnf, clique, etc. And what it means to "search" for a solution as opposed to "witness" a solution.

= or =

b) Looking closer at asymptotic complexity. At what k does n^k become worse than 2^n? Theoretically never of course, but if you look at the limits as k->infty then n^k is much bigger than 2^n..hmmm.

Also, there is a general lack of knowledge in the area of lower bounds.

It's such an interesting question though - I'm suprised it isn't more popular in the non-computer science crowd. Sure, it arose from complexity theory but at its core it is just a simply stated problem about _problem solving_.

.ben

Quote:

Original post by hplus0603 "stepped" on the solution? There were, IIRC, two principals, and a large number of grad students/postdocs that participated in the proof. It took them years. It used advanced higher-order algebra. It was pretty clearly not the proof that Fermat scribbled about in the margin: "the proof is surprisingly simple"...

In this case you do not remember correctly. Fermats last theorem was proven by two men, most of it done by prof Andrew Wiles with some help of his former student Richard Talyor. However you are correct that it took them years (about 7) and involves about every mathematics that have ever been used ;) (The proof is 200 pages long, and saying it is complicated is next to an understatement;)

The NP = P problem is one of the millenium prize problems, so if you solve it $1M is waiting for you ;) MPP

-M

Quote:

Original post by Extrarius Since quantum computers can solve NP problems in expected (but not guaranteed) polynomial time, it seems to me that NP problems are effectively P if not actually so,

P refers to Turing machines, not quantum computers. This is just changing the definition of the problem rather than finding the solution.

Quote:

Original post by thebolt00 Quote: Original post by hplus0603 "stepped" on the solution? There were, IIRC, two principals, and a large number of grad students/postdocs that participated in the proof. It took them years. It used advanced higher-order algebra. It was pretty clearly not the proof that Fermat scribbled about in the margin: "the proof is surprisingly simple"... In this case you do not remember correctly. Fermats last theorem was proven by two men, most of it done by prof Andrew Wiles with some help of his former student Richard Talyor. However you are correct that it took them years (about 7) and involves about every mathematics that have ever been used ;) (The proof is 200 pages long, and saying it is complicated is next to an understatement;) The NP = P problem is one of the millenium prize problems, so if you solve it $1M is waiting for you ;) MPP -M

For anyone interested, here (very large PDF) is the proof. Quite interesting that the first sentence would leave most people clueless, yet the problem itself is seemingly so simple.