Archived

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

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.

Recommended Posts

April fool!

Share on other sites
I don''t get it. It''s not funny.

Share on other sites
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 on other sites
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 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 on other sites
quote:
Original post by gumby
April fool!
No, that would require me to have actually believed you before I read your post.

Share on other sites

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 on other sites
quote:
For those who haven''t had any Theory of Computation classes

And who hasn''t, right?

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

1. 1
2. 2
Rutin
18
3. 3
khawk
15
4. 4
A4L
14
5. 5

• 10
• 13
• 26
• 10
• 11
• Forum Statistics

• Total Topics
633744
• Total Posts
3013666
×