CDR: Re: An Introduction to Complexity, Hamiltonian Cycles, and Zero Knowledge Proofs--Part 1

[petro]

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