If you were famous....
04-23-2013, 11:08 AM
Post: #1
|
|||
|
|||
If you were famous....
If you were famous, what would you be famous for?
GC: TheGreatAnt |
|||
04-23-2013, 01:05 PM
(This post was last modified: 04-23-2013 01:05 PM by TheGreatErenan.)
Post: #2
|
|||
|
|||
RE: If you were famous....
Things I would really like to be famous for some day:
Things I wish I could be famous for some day but which are extremely unlikely:
|
|||
04-23-2013, 02:01 PM
Post: #3
|
|||
|
|||
RE: If you were famous....
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.
|
|||
04-23-2013, 02:15 PM
Post: #4
|
|||
|
|||
RE: If you were famous....
Someone please explain P/NP to me.
It'll be GG when you're up against GG of GG. |
|||
04-23-2013, 02:30 PM
(This post was last modified: 04-23-2013 02:34 PM by TheGreatErenan.)
Post: #5
|
|||
|
|||
RE: If you were famous....
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. |
|||
04-23-2013, 02:32 PM
(This post was last modified: 04-23-2013 02:33 PM by awpertunity.)
Post: #6
|
|||
|
|||
RE: If you were famous....
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... |
|||
04-23-2013, 02:33 PM
(This post was last modified: 04-23-2013 02:35 PM by TheGreatErenan.)
Post: #7
|
|||
|
|||
RE: If you were famous....
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 |
|||
04-24-2013, 02:42 AM
Post: #8
|
|||
|
|||
RE: If you were famous....
My head asplode.
It'll be GG when you're up against GG of GG. |
|||
04-24-2013, 02:51 AM
Post: #9
|
|||
|
|||
RE: If you were famous....
(04-24-2013 02:42 AM)GreatGonzales Wrote: My head asplode. This. I already am famous, so this question is irrelevant for me. You can ask a... (drawing by Chemoeum) |
|||
04-24-2013, 04:26 AM
(This post was last modified: 04-24-2013 04:26 AM by TheGreatErenan.)
Post: #10
|
|||
|
|||
RE: If you were famous....
(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? |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread:
16 Guest(s)
16 Guest(s)
Return to TopReturn to Content