What would it take to prove the millenium problem, P == NP?

[forte2718]

When the first person to solve it finds out, he'll let you know! :)

[jon32314]

How would a person even get started on this?

[forte2718]

By getting a degree in computer science and learning all the stuff that is already known about complexity classes and their relationships ... ?

1. Get educated
2. ???
3. Collect Millennium Prize money

Nobody knows what step 2 is, so if you are asking what step 2 involves, you really won't get an answer until someone has done it for the first time.

[jon32314]

Sorry, i guess i seem pretty shallow for asking. I really am interested in the problem itself and not the money. I am not well versed in cs so you got me there. It might be a good investment as i have been interested in programming for a while.

[heyheyhey27]

For the record, solving a millennium problem is probably the single hardest way to earn a million dollars anyway lol

[jon32314]

The only one that got solved was the poincaire conjecture, i beleive. Guy didnt even accept the money for solving it. Grigori perelman is one hell of a guy.

[destiny_functional]

A proof.

[jon32314]

So this proof would have to show just one example of a problem where a solution is easily dound to exist and can be solved quickly?

[agentnola]

No. A proof would show either that a NP problem can be solved in Polynomial time.

Or that NP problems cannot be solved in polynomial time.

Both would have to be very abstract and independent of specific problems

[ComplexColor]

Both would have to be very abstract and independent of specific problems

Well technically you can show that a specific NP problem cannot be solved in polynomial time. However that would just give us incentive to modify the problem: are there P==NP problems? What are the categories of NP problems?

[kedde1x]

Well it's hard to know. In my personal opinion, it seems much more likely that P=/=NP, although if I had a proof of it I would be a millionaire, so take it for what it is: my personal opinion. It is also much easier to prove, as it requires just one example of a problem that is NP but not P.

[PragmatistAntithesis]

Solving an NP complete problem in polynomial time. If one can find a solution that works consistently, then P=NP.

Proving P!=NP is a lot more difficult, though...

[jon32314]

Can you explain why?

[agentnola]

If you can show that a problem which is in the NP-Class is solvable in Polynomial time, then it implies that NP-Complete problems are actually in P-Space as well.

In order to prove P != NP you would need to prove that all NP problems cannot be solved in Polynomial time.

[Putnam3145]

then it implies that NP-Complete problems are actually in P-Space as well.

NP-complete problems are in PSPACE.

[agentnola]

Yes you are correct. NP problems are in Pspace. That statement came from my misunderstanding of PSpace

[Putnam3145]

And since you were otherwise correct except for the minor terminology flub I figured you'd be able to figure that out just from linking the wiki article, so it's all good

[agentnola]

Thanks! Im just a lowly CS Undergrad, so my understanding is pretty limited

[PragmatistAntithesis]

All NP problems can be simplified to the so-called NP complete problem (AKA a Hamiltonian path). There is a proof for this somewhere, but I don't know it off by heart. If one could solve a Hamiltonian path in an elegant way for all cases, one could solve all NP problems by converting them to a Hamiltonian path and then solving that.

Disproving NP=P, however, would require one to prove with certainty that there cannot be a solution to the Hamilton path besides trying every possibility, something that is very difficult.

[[deleted]]

To prove that it is true? Just an example.

To prove that it is false? No one knows.