At 11:02 AM 11/4/00 -0600, Jim Choate wrote:
On Sat, 4 Nov 2000, Declan McCullagh wrote:
"NP" problems, on the other hand, are those that can be solved in nondeterministic polynomial time (think only by guessing). NP includes P.
Actualy any time that can't be described using a polynomial (i.e. a0 + a1x + a2x^2 + ...) is NP. For example something that executes in factorial or exponential time is NP.
If it is found that all NP can be reduced to P then I'd expect to see somebody be able to express a factorial (for example) as a polynomial. I ain't holding my breath.
The 'nondeterministic' part simply means it's unknown if the problem can be reduced to a polynomial representation.
As to 'guessing', some processes are polynomial and some aren't.
Jim, you're misunderstanding the class NP, though you're correct in not holding your breath. It's not "all problems that can't be solved in polynomial time." It's "all problems that can be solved in polynomial time by a non-deterministic Turing machine." A non-deterministic Turing machine is allowed to guess answers (or at least, to guess a polynomial number of answers). Answers to NP problems can be verified in polynomial time - the hypothetical machine guesses the answer, and verifies it in a polynomially bounded time. There are lots of problems that are outside of NP - they're known to take exponential amounts of time to solve, regardless of whether you've got a NTM which can pull correct bits out of /dev/oracle. There are also lots of problems for which the complexity is unknown, such as factoring. Until ~20 years ago, linear programming was believed to be part of NP, but Karmarkar's algorithm (which I think was based on Shor's work?) demonstrated a way to solve it in polynomial time, though with an annoyingly large polynomial. NP-complete problems are a certain set of problems for which it can be proven that if you can solve one problem in that set in polynomial time, you can use only polynomially more work to solve any other problem in that set. Usually people reduce things to the Satisfiability problem, though sometimes others are more convenient. When I was studying complexity theory from Karp back in grad school, one thing I didn't understand was the issue of whether there might be other sets of problems that are similarly hard but not reducable to each other, e.g. a set NP1 of hard problems including satistiability, Hamiltonian paths, etc., a set NP2 of hard problems including Foo and Bar that are reducable to each other but haven't been proven to solve or be solved by NP1 (or at least not both.) Perhaps it's a definitional thing, or perhaps there are proofs that were beyond the scope of a first-year grad course, or perhaps the problems that appear to be that hard just keep turning out to be members of the well-known NP-complete set, or perhaps there was something obvious I was just missing... Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639