Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP

Question

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.

Answer 1

The certificate you propose might not be polynomial in the size of the input.

The input size of the problem is $O(n^3 + \log k)$, while your certificate has size $\Omega(k \log n)$. This is not polynomial, e.g., for $k = 2^n$.

Your certificate would work if you set it, e.g., to an empty list whenever $k = \Omega(\frac{n^2}{\log n})$, and modify the verifier to just check whether the input configuration of the cube is solvable for any such value of $k$ (thus ignoring the certificate).