If you were famous....

[TheGreatAnt]

If you were famous, what would you be famous for?

[TheGreatErenan]

Things I would really like to be famous for some day:

• Writing and producing music
• Designing and developing video games
• Writing novels
• Writing and/or directing films
• Being #1 on the Outwitters 1v1 Top 200 list
  

Things I wish I could be famous for some day but which are extremely unlikely:

• Proving the Riemann Hypothesis
• Proving that P=NP or that P!=NP, whichever turns out to be true
• Casting magic spells that allow me to fly or use telekinesis
  

[awpertunity]

Wow I never realized the question about P/NP was a millennium problem... I always assume P was a strict subset of NP, and the more I think about it the more convinced I am of it haha.

[GreatGonzales]

Someone please explain P/NP to me.

[TheGreatErenan]

For some problems, correct solutions can be algorithmically verified as correct in polynomial time. These problems are in the set NP. Some problems can also be solved algorithmically in polynomial time. These problems are in the set P. Some problems are in both P and NP. However, some NP problems do not have a known algorithm to solve them in polynomial time and the answer to the question of whether they are in P or not is not known.

In short, the P/NP problem is to determine whether all problems that are algorithmically verifiable in polynomial time are also algorithmically solvable in polynomial time.

There's a bit more to it than that, but that's the main idea.

I've always felt that P=NP but that the universal method for reducing an NP-complete problem to a known P problem would come at such a high computational cost as to make it practically worthless. In other words, it can theoretically be done, but it would take a hundred thousand years for our computers to do it.

[awpertunity]

They are used to classify how "difficult" a problem is, where checking all possible answers for a solution is not feasible.

A P problem is a problem that can be solved using a computer/algorithm in polynomial time.
An NP problem is a problem whose solution can be checked in polynomial time.

So here's a problem example: if I give you a finite set of numbers {-10, -5, 2, 4, 9, 19}, can you find a subset of them that sum to 0?

This problem is clearly NP because if I give you a solution (or possible solution), it is very easy to check if that solution satisfies the condition. i.e., {-10, -5, 2, 4, 9} is a solution and can be checked by simply seeing -10 - 5 + 2 + 4 + 9 = 0. Similarly you can check any possible solution, for instance, {-10, 19} is not a solution by seeing -10 + 19 =/= 0.

So the question is, does P = NP, meaning if a problem is NP, is it P? So if there is a way to check a solution in polynomial time, is there a way to actually find a solution in polynomial time. Checking every possible combination is clearly a way to find a solution, but cannot be done in polynomial time. As the size of the set I give you grows, the number of combinations you need to check grows exponentially rather than polynomially. But if P=NP there would mean there is some smarter algorithm that would be able to find a solution in polynomial time.

Here's the $1,000,000 question at hand http://www.claymath.org/millennium/P_vs_NP/ as well as the 6 other millennium problems if you're feeling ambitious

I believe the Poincare conjecture has already been solved...

[TheGreatErenan]

Yes, Grigori Perlman solved the Poincare conjecture and rejected the million dollar prize, IIRC.

Also, my favorite attempted proof:

Proof by contradiction. Assume P = NP. Let y be a proof that P = NP. The proof y can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since P = NP, the proof y can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer scientists to produce a proof), we have a contradiction.

- Hubie Chen, Cornell University

[GreatGonzales]

My head asplode.

[Mag!cGuy]

(04-24-2013 02:42 AM)GreatGonzales Wrote:  My head asplode.

This.

I already am famous, so this question is irrelevant for me.

[TheGreatErenan]

(04-24-2013 02:51 AM)Mag!cGuy Wrote:  I already am famous, so this question is irrelevant for me.

Well then... what are you currently famous for?