0
$\begingroup$

If an optimization problem A is NP-hard and P≠NP, then does there exist an instance x of A such that no polynomial algorithm provides an optimal solution for x?

$\endgroup$
1
  • $\begingroup$ can you define what is an instance x of a problem A? $\endgroup$ Jul 4, 2023 at 13:10

1 Answer 1

1
$\begingroup$

I assume in this answer that $A$ is NP-complete, since otherwise it is possible that $A$ is unsolvable, or that the output size is super polynomial in $n$.

Assuming $A$ is NP-complete, let $x$ be some instance, and let $s$ be the optimal output for $x$. Let $\mathcal{A}$ be an algorithm that solves $A$ in (possibly exponential) deterministic time. Let $\mathcal{A}^s_x$ be the algorithm that given $x$ it outputs $s$, and otherwise it simulates $\mathcal{A}$.

Then this algorithm has linear running time in $|x|+|s|$ which is polynomial in $|x|$ (which is constant), an solves $A$ correctly in general.

Intuitively, when you fix an instance, then a solution already exists, and both the instance and the solution have constant size, we just do not know how the solution looks like, and hence, we don't know how the algorithm $\mathcal{A}_x$ looks like, but it exists!

$\endgroup$

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.