1
$\begingroup$

Suppose, for the sake of argument, that it was proved that $P \not= NP$. Then, this would imply that for every $NP$-complete problem, there is a "hardest instance" of the problem that cannot be solved in polynomiall time. Then, if $P$ were to not equal $NP$, what properties would be known about the hardest instances of $NP$-complete problems?

In particular, my question is:

If $H$ is the set of all hardest instances of some $NP$-complete problem (take subset-sum for instance), thereby not solvable in polynomial time, then do we know if $H$ would contain both "yes" and "no" instances of the problem, or only "yes" or only "no" instances? (By "yes" instance I mean the answer to the decision problem is "yes"; i.e., "yes, there is a subset of some integer set that sums to a target value").

My gut tells me the set of all hardest instances of a problem must contain at least one "yes" instance, and not necessarily a "no" instance, but I do not have a proof and am wondering if someone has one.

My general thought for a proof of why there must be "yes" instances in the hardest set is as follows:

Suppose, for the sake of contradiction, that the set of problems that no algorithm could solve in polynomial time are all "no" instances. Then this implies there is an algorithm that can solve all "yes" instances in polynomial time, and hence for parameter $n$ is gauranteed to halt after $n^d$ iterations, where $d$ is a fixed positive integer. But then this implies that if the algorithm does not return "yes" after $n^d$ iterations, then it knows it must be a "no" instance, and hence returns "no" in polynomial time ($n^d$ iterations). But then this is an algorithm solving all instances of the problem in polynomial time, a contradiction.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ For any particular instance of an NP problem, there is an algorithm solving that instance in polynomial time: just have the certificate for that instance hard-coded. $\endgroup$
    – Tassle
    Commented Jul 27, 2022 at 20:31
  • $\begingroup$ @Tassle yes, but my point is that in order to get that certificate in the first place there must have been an algorithm that solved the problem, and this could not have run in polynomial time (if it was a hardest instance). My question is what those hardest instances look like: i.e. are they all "yes" or "no" or a mixture of both? I added my idea for a proof which may help elucidate things. $\endgroup$
    – user918212
    Commented Jul 27, 2022 at 20:44

1 Answer 1

Reset to default
9
$\begingroup$

This would imply that for every NP-complete problem, there is a "hardest instance" of the problem that cannot be solved in polynomiall time.

No. This is incorrect. For every single instance, there is a polynomial-time algorithm that solves that instance correctly. The algorithm can hardcode a check to check for that one instance and output a hardcoded answer (the correct solution).

As this also shows, the notion of "hardest instance" is not well-defined. So, your proposal that we define $H$ to be the set of hardest instances is not well-defined. The set $H$ is not well-defined, because there is no sensible definition of what it means for a single instance to be a hardest instance.

This means that your question is not answerable because it is not meaningful/well-posed.

For any set of instances, if the set contains only "yes" instances it can be solved in polynomial time (simply use an algorithm that ignores its input and always outputs "yes"). Similarly, any set that contains only "no" instances can be solved in polynomial time. So, if you have a set that is not solvable in polynomial time, then it must contain both yes instances and no instances. In fact, it must contain infinitely many yes instances and infinitely many no instances.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I see. In that case, can you say what a good definition of "hardest instance" is? My thinking goes to the fact that $P\not= NP$ does not imply that NP-complete problems are hard to solve on average, but are hard to solve in the worst case. I suppose I am trying to classify what the "worst case" instances look like. $\endgroup$
    – user918212
    Commented Jul 28, 2022 at 2:05
  • $\begingroup$ That is, is it not so that $P\not= NP$ implies that NP-complete problems require at least exponential time to solve in the worst case, hence implying that there are instances of the problem that lie in this "worst case" (hardest instance as I am describing in the question)? $\endgroup$
    – user918212
    Commented Jul 28, 2022 at 2:59
  • 1
    $\begingroup$ @Generic, as I already wrote, the notion of "hardest instance" is not well-defined. Unfortunately, there is no meaningful notion of "hardest instance" and no way to define it in any meaningful way. You can only talk about hardness of languages (i.e., sets of instances), not hardness of an individual instance. I explained why in the first paragraph of my answer. $\endgroup$
    – D.W. ♦
    Commented Jul 28, 2022 at 4:36
  • $\begingroup$ @user20574, thank you! Good catch. Fixed. $\endgroup$
    – D.W. ♦
    Commented Aug 21 at 4:23

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.