patternMinor
Can an NP-hard problem be polynomial on average?
Viewed 0 times
problemcanpolynomialhardaverage
Problem
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?
Can anyone answer or provide a reference answering either of these questions?
- 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?
Solution
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.
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.
Context
StackExchange Computer Science Q#28466, answer score: 5
Revisions (0)
No revisions yet.