np-complete but not "hard" [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 12 years ago.

Is there some language that is NP-complete but for which we know some "quick"开发者_StackOverflow 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.

---

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.

---

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.