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

• they could simply give a certificate that a "yes" decision is just a list of at most k moves which means that the list length is at most $2^{length(k)}$, which can be exponential of the input size. That's why they use $p(n)$, polynomial bound on the number of moves. But I do agree that they could write this in 1 paragraph instead of 3.
– user114966
Jul 15, 2020 at 18:12

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).
• For the input size, I just encoded the problem by storing for each of the $n^3$ squares of a $n \times n \times n$ cube, the color of the square. This requires a constant number of bits per square. In addition you'll need to encode $k$, which requires $O(\log k)$ bits. Your certificate has size $\Omega(k \log n)$ since you'll need to write $k$ moves. If you encode a move by some sort of coordinates in the cube, you'll need $\Omega(\log n)$ bits (which are needed just for a single number between $1$ and $n$). Jul 15, 2020 at 19:49
• Finally, in the paper the authors discuss how $O(\frac{n^2}{\log n})$ moves are enough to solve any feasible $n \times \n \times n$ cube. Jul 15, 2020 at 19:51
• Okay, I think I can follow that. My knowledge of information theory is limited enough that I don't immediately recognize things like the number of bits required to encode an integer. And I was thrown off by the $n^3$ because I was expecting to see something like $n^3-(n-2)^3$, but I see that the $n^3$ dominates. Jul 15, 2020 at 19:58