np-complete but not "hard"

Question

Is there some language that is NP-complete but for which we know some "quick" algorithm? I don't mean like the ones for knapsack where we can do well on average, I mean that even in the worst case the runtime is something like 2^n^epsilon, where the result holds for any epsilon>0 and so we can allow it to get arbitrarily close to 0.

Answer 1

According to Wikipedia, "There are also decision problems that are NP-hard but not NP-complete, for example the halting problem."

There are no languages that are NP complete where we know a "quick" algorithm; otherwise, it wouldn't be NP-complete.

Answer 2

If you do find a "quick" algorithm to this np-complete problem, you just solved that P=NP, and as you know, that is still an open question.