I'm wondering if there are any $NP$-hard problems which are ``polynomial" in the average case. I think there are two ways to interpret this?

  • If $P \neq NP$, can there be an algorithm solving an $NP$-hard problem with amortized (average case) running time of $O(n^k)$ for a constant $k$?
  • Are there any problems which are $NP$-hard which are also in $BPP$, or even $PP$?

Can anyone answer or provide a reference answering either of these questions?

  • 5
    $\begingroup$ This question popped up in CS theory a while ago, here is the link cstheory.stackexchange.com/questions/496/… $\endgroup$ – lPlant Jul 16 '14 at 18:22
  • $\begingroup$ Ah, excellent! Should I close/delete this question then? $\endgroup$ – jmite Jul 16 '14 at 19:37
  • 2
    $\begingroup$ @jmite: This may be useful to keep around here, so maybe post a quick (self-)answer with a reference here? $\endgroup$ – Raphael Jul 16 '14 at 23:52
  • 1
    $\begingroup$ I would just like to point out that amortized is not the same as average-case running time. $\endgroup$ – gardenhead Jul 21 '14 at 22:00
  • $\begingroup$ If an NP-hard problem is in BPP, it means that NP is in BPP, which means that the polynomial hierarchy collapses, an outcome that is considered to be unlikely. On the other hand I don't think it is not considered very unlikely that PP contains NP since $PH \subseteq P^{PP}$. (You may want to ask about evidence for and against NP in PP on Theoretical Computer Science.) $\endgroup$ – Kaveh Sep 4 '14 at 18:28

It would seem that the question has been answered at CSTheory.SE.

Summary: it is, indeed possible.

For example, the Max 2-CSP problem is NP hard with an $O(n)$ expected time algorithm.

This makes sense, I guess. Sometimes only a small subset of instances is needed to make a problem $NP$-hard, like SAT vs 3SAT. But you can expand the problem, and as long as it still contains the hard instances, it will be NP-hard, but the probability of success with a fast algorithm will be raised.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.