Thread: P vs. NP
View Single Post
Old 07-09-2005, 07:07 AM   #4 (permalink)
fitzjj
 
Ultra Techie

Join Date: Oct 2003

Posts: 544

fitzjj

Default

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?
fitzjj is offline