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.
- 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"?
- ...