In comp.theory Randy <email@example.com> wrote: > firstname.lastname@example.org wrote: >> In comp.theory Randy <email@example.com> 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?
No. A problem is NP-hard if every problem in NP is polynomially reducible to it. Nobody currently knows if polynomial time solutions exist for any NP-Hard problems. If you were to find a polynomial solution for an NP-Hard problem then you have proven that P=NP. If you prove that no polynomial time algorithm exists for an NP-Complete problem then you have proven that P<>NP. If you prove that no polynomial time algorithm exists for an NP-Hard problem, it may still be the case that P=NP because not all NP-Hard problems are in NP.
> 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.
> 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...
But what problem do you have in mind? Remember there is a difference between a problem and an algorithm. We do not know that 3-SAT is an exponential problem. There are very few problems that we know for a fact require exponential time. We do know that 3-SAT is NP-complete, and lots of people suspect that means that there does not exist a polynomial time algorithm for 3-SAT, but we do not actually know that.