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