0
$\begingroup$

Given an optimization problem $P$, if we know that this optimization problem is NP-hard, is it necessary to check the complexity of the corresponding feasibility problem, i.e. the complexity of checking if the problem admits a feasible solution? Because in the case of $P$ the problem is not always feasible.

$\endgroup$

1 Answer 1

1
$\begingroup$

The problem of checking whether $P$ admits a feasible solution might or might not be NP-hard (both cases are possible).

For example, if $P$ it the problem of finding a vertex cover and the goal is to minimize the number of selected vertices then $P$ is NP-hard but a feasible solutions is trivial (just select all vertices).

On the other hand, if $P$ is the problem of finding a satisfying truth assignment for a $3$-SAT formula and the goal is that of minimizing the number of asserted variables, then both $P$ and the problem of checking whether a feasible solution exists are NP-hard.

$\endgroup$
1
  • $\begingroup$ so if the feasibility problem is NP-hard this implies that the optimization problem is also NP-hard $\endgroup$
    – Farah Mind
    Aug 15, 2022 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.