The suitcase lock

Question

I guess there is no polynomial algorithm for opening a code lock with n dials on a suitcase. However, to verify an existing solution is easy, it consists simply of opening the suitcase. So the problem is in NP, but not in P.

Obviously I am mistaken. Where am I wrong?

Answer 1

I agree with zmbd's answer.

I would like to expand it a little bit. Deterministic problems shouldn't have hidden numbers to be guessed; the entire problem to be solved should be clear. Deterministic problems are more like chess than like poker: the entire problem statement should be accessible to the algorithm.

However, Computer Science often studies complexity classes with "oracles". An oracle is more or less a black box that has some hidden from the algorithm criteria for answering "yes/no" questions. Your suitcase problem essentially includes an oracle that allows you to open the suitcase if and only if the lock coincide with the hidden number. With the help of that oracle your implied question can be made rigorous:

Given an oracle A that has a hidden combination of locks the problem of opening the suitcase is clearly in NP^A, but not in P^A. Does that prove that P != NP?

The answer to the above question is no: it turns out that there exists an oracle A for which P^A != NP^A, and also exists an oracle B for which P^B == NP^B. Therefore your perfectly correct observation that opening the suitcase is in NP relative to the hidden number oracle, but not in P relative to the same hidden number oracle does not prove that P != NP.

Here's the original paper about that:

T. P. Baker, J. Gill, and R. Solovay, "Relativizations of the P =? NP Question"