Newsgroups: comp.theory
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 27 Nov 92 15:30:45 GMT
Subject: Re: Cryptography and P=NP

annan@vax.oxford.ac.uk writes:

On an ``algorithm'' that halts in polynomial time on accepting a
string in a language but may not halt on rejection of a string not in
the language.

>>>By usual definitions, this is NOT a polynomial time algorithm for the
>>>NP-complete language.

When I replied:

>> On the contrary, by the usual definition cited, this is a polynomial
>> time [sic] for recognizing the NP-complete language, as we were discussing.

I'm afraid I was mistaken.  I was misled by a sentence on on page 25
of Garey and Johnson (to which I was directed by John Mount's
message).  G&J show a program that does halts on acceptance and does
not halt on rejection, and say that the program recognizes the
language.  But they continue to say that the program ``does not
correspond to our notion of an algorithm.''  So there is a *program*
that recognizes the language, but not an *algorithm* that recognizes
the language.  The notion of polynomial time is indeed used to refer
to the maximum time taken over all strings over the input alphabet,
not just the strings in the recognized language.

>What definition do you use? Or are you using "recognising" to mean something
>different from "accepting"?

Somehow I had gotten the idea that G&J were using the term
``recognizing'' (a language) to refer to a process's behavior on
success, while ``deciding'' (membership in a language) referred to the
process's behavior on all strings.  A more careful reading shows that
they make this distinction between a program and an algorithm.

I deeply regret having so intemperately rejected James Annan's correct
summary of the usual terminology.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil