8
$\begingroup$

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.

  1. 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"?
  2. 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"?
  3. ...
| cite | improve this question | |
$\endgroup$
  • 5
    $\begingroup$ As alluded to in D.W.'s answer, the problem is that there are no restrictions placed on $P$. For example, "$G$ is one of the 42 graphs that I happen to have already computed the optimal solution to" is a valid property $P$. To get anywhere in this direction, I think you would need to restrict the set of possible properties $P$ -- say, to properties expressible in some restricted form of logic. $\endgroup$ – j_random_hacker Dec 16 '16 at 2:03
17
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

In some sense, the answer to your question is affirmative, due to Levin's universal search algorithm. Consider for concreteness graph coloring, and a particular class of easy instances. As a witness that this class is easy, you have an algorithm which, given a graph in this class, produces (in polynomial time) a legal coloring together with a polynomial size proof that the coloring is optimal.

Levin's universal search algorithm runs all polynomial time algorithms on its instance (this is achieved by trying all possible polynomial time bounds for each algorithm), checking whether they provide a legal coloring together with an optimality proof. On any class of easy instances, this algorithm runs in polynomial time. Unfortunately the constants will be huge, so this algorithms isn't practical.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Note that the question only says that $\Pi$ is NP-hard, so it's not guaranteed that solutions can be verified in polynomial time. $\endgroup$ – David Richerby Dec 28 '16 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.