Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

gumby

New Proof: P = NP !

This topic is 5737 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
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*

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.....

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Uh, I haven''t. Seeing as I''m not a CS major. And even if I were, I''m only a freshman

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!