email@example.com wrote: > In comp.theory Randy <firstname.lastname@example.org> wrote: > >>email@example.com wrote: ... >>If the problem is not as easy as X, then we say >>only that it's not as easy as other un-easy problems? > > > Currently all we can say for the most part is how hard certain problems > are relative to each other. We know of a whole bunch of problems > that are all just as hard as each other in the sense that > if a polynomial time solution existed for any of them one would > exist for all of them. However we do not know if those polynomial > solutions exist or not. It seems doubtful that they do, but > who knows what some clever person down the road may think of.
Understood. That does help.
... > > But what problem do you have in mind? Remember there is > a difference between a problem and an algorithm.
I think I just realized that. It does clarify a few things. Thanks,