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?
Can an NP-hard problem be polynomial on average?
complexity theory;reference request;np complete;probabilistic algorithms;amortized analysis
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.