Smug Git
Arrogance Personified
Registered: Aug 2001
Location: Hilbert Space
Posts: 35656 |
quote: Originally posted by geaeslore
does the magazine to which you refer have a particular problem statement and if so would you be so kind as to post a link?
This is the central problem of complexity theory, in fact.
Problems in P are those which can be solved with a number of steps which is polynomial in the input length. NP are those problems for which possible solutions can be checked with a number of steps that is polynomial in the input length. The question is whether P=NP, ie, are there problems where you can check the solution with steps polynomial in input length but for which you can't generate solutions with steps polynomial in input length (in which case P!=NP) or is it the case that you can always solve with a number of steps polynomial in input length any problem for which you can test solutions with a number of step that is polynomial in input length (in which case P=NP).
Factorisation is a well known problem that is NP (given a large number and two prime numbers (or more) believed to be all of the factors of that large number, I can easily check whether or not they are genuine solutions. It has not been proved that there isn't an algorithm to factorise numbers, though, with a number of steps that is polynomial in input length; if it is ever proven that such an algorithm can't exist, then, indeed, P!=NP and quantum computing will be even more important to the military).
As an aside, there are a class of problems called 'NP-complete', which includes the Travelling Salesman problem (TSP) where it has been shown that if you can solve one then you can use that algorithm to solve all the rest of the NP-complete problems.
A good (but techinical) book on all of this stuff is by Papadimitriou, called something exciting like 'Complexity Theory'). I have only read a couple of chapters, but it is a good book and deals a lot with the P/NP problem, which is a real bitch of a problem.
__________________
I want to live and I want to love
I want to catch something that I might be ashamed of
Last edited by Smug Git on 04-01-2003 at 09:27 PM
Report this post to a moderator |
IP: Logged
|