P vs. NP

Emily · 07-05-2005, 10:46 PM

Anyone know anything about this problem? (I'm not asking for anything in particular, I'm just looking for some people to discuss it with.)

Iron_Cross · 07-06-2005, 09:35 AM

What's there to discuss? I guess you could just post your opinion of the whole "p vs np" problem. From the little bit I've heard about it, I don't really have an opinion yet, because it seems to be way to circumstancial.

Emily · 07-09-2005, 01:05 AM

Have you read Cook's paper?

fitzjj · 07-09-2005, 07:07 AM

Yeah covered this in lectures last semester, really dull (mainly because i have no interest in the maths side of computer science), perhaps if i understood it more - because some of the implications of P=NP are pretty interesting (plus there is quite a large sum of money sitting there for whoever proves that P=NP, or presumably whoever proves P!=NP too)...

P is the set of all decision problems solvable in time less than or equal to some polynomial p(n) by a deterministic machine.

NP is the set of all decision problems solvable in polynomial time by a non-deterministic machine.

And there is this big question of is P=NP. if it is then you can solve lots of problems in polynomial time (i.e. a **** of a lot faster than they can be solved now) which aside from saving a lot of time has implications in terms of security - if you can break encryption faster clearly that is not good!!!

Most people believe that (and it is probably the case that) P is not equal to NP.

Can i ask why you have an interest in this area?

Emily · 07-09-2005, 12:45 PM

Quote:

Originally posted by fitzjj
Can i ask why you have an interest in this area?

No reason in particular... it just interests me.

I guess I'm kind of the opposite of you, I really like the math side of computer science. It also caught my eye I guess because it's so different than the rest of the Millenium Problems, it's so easy to understand but it's just as hard as the rest of them to solve.

TheHeadFL · 07-14-2005, 08:30 AM

I think the coolest feature of problems in NP is that while there are as yet no known polynomial time *solutions* for the problems on a deterministic machine, we can *verify* the solutions in polynomial time.

This is why encryption algorithms are so fascinating to me. To go one way, the math is trivial. To go the other way, the math is staggering.

I also have a lot of interest in the related idea of computability. Like for instance, how trivial the shortest path algorithm is, but how the longest path algorithm is noncomputable, in general.

fitzjj · 07-14-2005, 01:18 PM

I have to agree with you guys to a point, the ideas behind it are pretty interesting and the consequences if P = NP. it is just when all the maths and proofs get going that i switch off!

TheHeadFL - Have you looked at busy beaver functions. These are functions that grow faster than the largest function and so are non computable. i personally found it kind of hard to get my head round to start with.

KornNut · 07-14-2005, 02:41 PM

Quote:

Originally posted by TheHeadFL

This is why encryption algorithms are so fascinating to me. To go one way, the math is trivial. To go the other way, the math is staggering.

Yeah... The most popular encryptions, those that involve Public and Private Key encryption (such as RSA), are really based on the algorithm of finding out if a number is prime or not (NP complete problem). Have you read "Digital Fortress" by Dan Brown?

TheHeadFL · 07-14-2005, 06:43 PM

No I've never heard of busy beaver functions.. I'll have to look into them. Most of this stuff I learned during my various Discrete Mathematics courses here at UCF. I enjoyed the class about turing machines and noncomputability immensely. I think I will be taking a class in encryption soon.

KornNut- Yes, I have read Digital Fortress by Dan Brown, good book. Its interesting that you mention NP completeness, since that is also really interesting. If they could prove that prime number factorization was a problem that was in P, then thousands of other problems associated with it would be in P as well. Just imagine if they could prove the halting problem was in P!

KornNut · 07-18-2005, 08:59 AM

Quote:

Originally posted by TheHeadFL

KornNut- Yes, I have read Digital Fortress by Dan Brown, good book. Its interesting that you mention NP completeness, since that is also really interesting. If they could prove that prime number factorization was a problem that was in P, then thousands of other problems associated with it would be in P as well. Just imagine if they could prove the halting problem was in P!

IF some one actually found a good algorithm, I would hope they would be honest, otherwise they can rape every one's credit card online.

Member Login