Most hard problems can either be solved efficiently in average time, or an approximation can be efficiently found. Are there any natural problems for which this is not the case? In particular, is there a natural problem that can not be solved in polynomial time in the average case, even if we only demand an approximation?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Are there any natural problems for which this is not the case?
Consider the scheduling jobs with deadlines on a single machine problem. I cannot say anything about its average time but this problem has no $\rho$-approximation unless $P=NP$.
Suppose that there are $n$ jobs to be scheduled on a single machine, where the machine processes at most one job at a time. Suppose also each job $J_i$ has
- release time $r_i \geq 0$
- deadline (due time) $d_i$
Define the delay by $D_i = t_i - d_i$ if the job $J_i$ finishes at $t_i$. So, we are interested in the minimization of the maximum delay, i.e.,
$$\text{minimize: } \max\{D_i\}, i=1,\dots,n$$
Now assume we have $\rho$-approximation algorithm for this problem. This means that our algorithm would find a solution which is not more than $\rho OPT$ (where $OPT$ is the optimal value). If for any problem instance with the optimal value equal to $0$ our approximation algorithm would find the solution at most $\rho 0 = 0$ in (polynomial time) and this would imply $P=NP$.
answered Nov 30, 2017 at 6:33
$\begingroup$
$\endgroup$
Consider the 3-colouring problem. Every planar graph can be 4-coloured. Determining if it is 3-colourable is NP-complete. Finding the number of colours required with less than 14% error is NP-complete.
