# Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP In this paper (https://arxiv.org/pdf/1706.06708.pdf) the authors prove that optimally solving the $$n\times n\times n$$ Rubik’s Cube is an NP-complete problem. In the process, they must show that the relevant decision problem belongs in NP (section 2.5 on page 6). To do this, they describe an algorithm that nondeterministically solves the Cube in polynomial time. It seems to me that this is more effort than necessary.

In particular, the relevant decision problem is as follows: The Rubik’s Cube problem has as input a permutation $$t$$ and a value $$k$$. The goal is to decide whether $$t$$ can be solved in $$k$$ or fewer moves. So rather than constructing a nondeterministic polynomial time solution algorithm, they could simply give a certificate that a "yes" decision is just a list of at most $$k$$ moves and verify that checking this is polynomial time.

So my questions are as follows. Are the two definitions below actually equivalent?

1. NP is the complexity class of decision problems that are solvable by a nondeterministic Turing machine in polynomial time.
2. NP is the complexity class of decision problems for which a solution can be confirmed in polynomial time (deterministically)?

And if they are equivalent, why would the authors of the linked paper choose the more difficult method (or am I wrong about this assumption)?

Note that I am posting this question on multiple StackExchange websites as I’m not sure where it’s best fit. If it is inappropriate here, I’ll happily delete it. Similarly, I’ll link to a good solution on another site if it gets answered there. Posted on Categories proxies