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?