[Solved]: Can an NP-hard problem be polynomial on average?

Problem Detail: 

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?

Asked By : jmite

Answered By : jmite

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28466

3.2K people like this

 Download Related Notes/Documents