# Can an NP-hard problem be polynomial on average?

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?

• This question popped up in CS theory a while ago, here is the link cstheory.stackexchange.com/questions/496/… – lPlant Jul 16 '14 at 18:22
• Ah, excellent! Should I close/delete this question then? – jmite Jul 16 '14 at 19:37
• @jmite: This may be useful to keep around here, so maybe post a quick (self-)answer with a reference here? – Raphael Jul 16 '14 at 23:52
• I would just like to point out that amortized is not the same as average-case running time. – gardenhead Jul 21 '14 at 22:00
• 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.) – Kaveh Sep 4 '14 at 18:28

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.