New Proof: P = NP !
I don''t get it. It''s not funny.
<img src=http://webspace.utexas.edu/~mvdepala/random/resist-ignorance.png
<img src=http://webspace.utexas.edu/~mvdepala/random/resist-ignorance.png
Basically all he is saying is 1 = 0. 1 = Not 1 in boolean logic, or something is equal to its opposite. Yeah, really funny *rolls eyes*
No, the joke is at least slightly funny. P = NP is nothing like 1 = 0. The question of whether P = NP (it probably isn''t) is the most important open question in computer science and one of the top 5 most important open questions in mathematics as a whole.
P is the class of algorithmic problems that have polynomial time solutions.
Some people mistakenly think NP means "Not polynomial", and this leads to the 1 = 0 analogy. NP actually means "nondeterministic polynomial" and refers to the class of problems where you can VERIFY whether a candidate solution is correct or not in polynomial time.
So the april fool joke works, though funny is in the eye of the beholder.....
P is the class of algorithmic problems that have polynomial time solutions.
Some people mistakenly think NP means "Not polynomial", and this leads to the 1 = 0 analogy. NP actually means "nondeterministic polynomial" and refers to the class of problems where you can VERIFY whether a candidate solution is correct or not in polynomial time.
So the april fool joke works, though funny is in the eye of the beholder.....
For those who haven't had any Theory of Computation classes :
P is the set of problems that can be solved on a deterministic Turing Machine (e.g classic computer) in polynomial O(nk) time.
NP is the set of problems that can be solved on a nondeterministic Turing Machine (e.g. infinitely parallel/quantum computer) in polynomial O(nk) time.
Obviously, all problems in P are also in NP, but whether all problems in NP are in P (hence P=NP) has yet to be proved one way or the other... Whether it can be proved has yet to be proved one way or the other too.
Technically, proving that one of the NP-complete problems (like graph 3-colorability, or the traveling-salesman problem) can be solved on a deterministic TM (e.g. your average computer) in polynomial time would be one such proof.
P being equal to NP would have major repercussions. For example, decomposition in prime factors is NP. If there were a way to factorise number in polynomial time, cryptographic algorithms that rely on this problem being difficult would be invalidated.
Not that proving P=NP would provide such an algorithm, but it would be a critical step.
[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]
[edited by - Fruny on April 1, 2003 6:59:19 PM]
P is the set of problems that can be solved on a deterministic Turing Machine (e.g classic computer) in polynomial O(nk) time.
NP is the set of problems that can be solved on a nondeterministic Turing Machine (e.g. infinitely parallel/quantum computer) in polynomial O(nk) time.
Obviously, all problems in P are also in NP, but whether all problems in NP are in P (hence P=NP) has yet to be proved one way or the other... Whether it can be proved has yet to be proved one way or the other too.
Technically, proving that one of the NP-complete problems (like graph 3-colorability, or the traveling-salesman problem) can be solved on a deterministic TM (e.g. your average computer) in polynomial time would be one such proof.
P being equal to NP would have major repercussions. For example, decomposition in prime factors is NP. If there were a way to factorise number in polynomial time, cryptographic algorithms that rely on this problem being difficult would be invalidated.
Not that proving P=NP would provide such an algorithm, but it would be a critical step.
[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]
[edited by - Fruny on April 1, 2003 6:59:19 PM]
quote:Original post by gumbyNo, that would require me to have actually believed you before I read your post.
April fool!
Frunny,
Mostly nice summary.
However nondeterministic Turing Machines are not infinitely parallel, nor are they quantum. The class of problems efficiently solvable on a quantum computer (usually the class BQP is considered) is not known and probably has very little relationship with NP.
>Whether it can be proved has yet to be proved one way or the >other too.
You think it might be independent of ZFC? That would be way cool, but I fear awfully unlikely.
> P being equal to NP would have major repercussions.
It would change the whole (real) world.
quote:Original post by Fruny
For those who haven't had any Theory of Computation classes
quote:Original post by Zipster
And who hasn't, right?
I haven't, but I'm interested in that kind of stuff, and since I'm doing a B. Sc. in maths-phys, I won't learn it at school.Fruny, what kind of textbook are you using in these classes? Can you give me a few references?
Thanks,
Cédric
[edited by - cedricl on April 1, 2003 8:49:02 PM]
Uh, I haven''t. Seeing as I''m not a CS major. And even if I were, I''m only a freshman
<img src=http://webspace.utexas.edu/~mvdepala/random/resist-ignorance.png
<img src=http://webspace.utexas.edu/~mvdepala/random/resist-ignorance.png
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement