Mr. May:
<x-flowed>At 2:20 PM -0500 11/4/00, dmolnar wrote:
On Sat, 4 Nov 2000, 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.
I'm sorry - by the definitions I know, Declan has it closer. I'm not sure what you're getting at with "any time that can't be described..." or "something that executes in factorial or exponential time." As far as I know, NP is a class of *problems*, not a class of running times or even a class of algorithms.
And I'm going to give a completely informal, but I hope useful, introduction. Though formalism is very important, and jargon is useful, I suspect that all the talk of "succinct certificates," "oracles," "reducibility," "nondeterministic polynomial time," "Co-NP," etc., isn't very useful to someone just coming to this stuff for the first time. <snip>
I confess that I only skimmed the sections on "Presburger arithmetic" and why it is "beyond NP" in some weird sense.
Have fun,
Thank you. -- A quote from Petro's Archives: ********************************************** "Despite almost every experience I've ever had with federal authority, I keep imagining its competence." John Perry Barlow