If you were famous....
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. |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread:
2 Guest(s)
2 Guest(s)
Return to TopReturn to Content