principleModerate
Is detecting easy instances of NP-hard problems easy?
Viewed 0 times
instanceshardeasyproblemsdetecting
Problem
My question is the following. Assume that $\Pi$ is an NP-hard problem. Given an arbitrary instance $I$ of $\Pi$ and assume that an adversary knows that this instance is easy to solve, is it possible to find a deterministic polynomial-time algorithm to solve this particular instance $I$?
For example: Suppose that $\Pi$ is GRAPH COLORING. The adversary gives you a graph $G$ with $n$ vertices.
For example: Suppose that $\Pi$ is GRAPH COLORING. The adversary gives you a graph $G$ with $n$ vertices.
- The adversary knows that $G$ is complete but you don't. Can you find a polynomial-time algorithm that says "This graph is colorable with $\Delta +1$ colors"?
- The adversary knows that $G$ has some property $P$ but you don't. Can you find a polynomial-time algorithm that says "This graph is colorable with $b$ colors"?
- ...
Solution
The problem isn't really well-posed. For any particular instance, there is a single solution, say $S$. Consequently, we can imagine an algorithm that has the answer $S$ hardcoded in: no matter what input you give it, all it does is just print $S$. This answer counts as a deterministic polynomial-time algorithm that solves this particular instance $I$.
Therefore, the answer to your question is "Yes", but for uninteresting reasons. It's possible you might need to think more about how to formulate your question to match what you really want to know.
The final part of your question is actually a bit different. It doesn't ask about a single instance $I$. Rather, it asks about a special case of the problem, i.e., an infinite family of instances that is a proper subset of all possible instances for $\Pi$. In that case, the answer is "it depends"; some special cases might remain NP-hard, and others might be in P.
Finally, I don't know what it means to say "The adversary knows X but you don't". I'm free to write an algorithm that assumes X is true and only works when X is true. "Knowledge" is a funny thing and not well modelled by the kinds of tools you seem to be talking about; complexity theory is more about "existence" than "knowledge".
Therefore, the answer to your question is "Yes", but for uninteresting reasons. It's possible you might need to think more about how to formulate your question to match what you really want to know.
The final part of your question is actually a bit different. It doesn't ask about a single instance $I$. Rather, it asks about a special case of the problem, i.e., an infinite family of instances that is a proper subset of all possible instances for $\Pi$. In that case, the answer is "it depends"; some special cases might remain NP-hard, and others might be in P.
Finally, I don't know what it means to say "The adversary knows X but you don't". I'm free to write an algorithm that assumes X is true and only works when X is true. "Knowledge" is a funny thing and not well modelled by the kinds of tools you seem to be talking about; complexity theory is more about "existence" than "knowledge".
Context
StackExchange Computer Science Q#67480, answer score: 17
Revisions (0)
No revisions yet.