P vs. NP problem and understanding "worst case complexity"

Question

Suppose that $P \not= NP$. Then my understanding is not all instances of NP-complete problems can be solved in polynomial time. That is for every NP-complete problem, there are a colleciton of instances of that problem where the solution (correct certificate) cannot be determined in polynomial time (I do not mean that there is no algorithm that solves it in polynomial time, like the algorithm that just hard codes the instance and knows the correct certificate).

Is what I have said here correct? If not, what exactly does "worst case complexity" when $P \not= NP$ mean, if it does not mean there are instances of NP-complete problems that no algorithm can find a solution (correct certificate to) in polynomial time?

Answer 1

What you wrote isn't clear. This is a problem with using English to try to summarize mathematics: it is easy to write an English sentence that is ambiguous.

If you mean "there is a set of instances, such that there is no single algorithm that solves every instance in that set correctly", then the answer is: correct. The language itself (i.e., the set of all instances of the problem) is such a set.

If you mean "there is a set of instances, such that for every instance in that set, there is no algorithm that solves that instance correctly", then the answer is: incorrect. For every instance, there exists an algorithm that solves that one instance correctly.

---

You appear to be trying to draw some distinction between "can be determined in polynomial time" and "there is an algorithm that solves it in polynomial time", but there is no such distinction. The notion of "can be determined in polynomial time" is vague, but to the extent that it has any precise meaning, the only meaning I can imagine is that there exists an algorithm that can solve it in polynomial time.

---

Consider the following analogy. For every number, there exists a larger number. But there is no largest number (there is no number, such that every number is larger than it). The order of quantifiers matters.

---

May I suggest some quality time with a complexity theory textbook, and perhaps on discrete math and proofs?