email@example.com wrote: > In comp.theory Randy <firstname.lastname@example.org> wrote: > > >>To wit, the solution of 3-SAT or any X^N problem requires exponential >>runtime (right?). > > > No, we do not know that 3-SAT requires exponential runtime. > Nobody has ever found a non-exponential algorithm for 3-SAT, > but that does not mean one does not exist.
So the identification of a problem as being NP-Hard is its *absence* of a polynomial solution? If the problem is not as easy as X, then we say only that it's not as easy as other un-easy problems?
No wonder I'm confused. I've always had trouble with double negatives.
> > What do you mean by an X^N problem? Do you have an example > in mind?
AKA exponential. No doubt I've messed up that term too...