1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dmitry Jul 15 at 18:12
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you elaborate on how you got these sizes? I can see how I'm oversimplifying the problem, assuming these are correct. $\endgroup$ – Atsina Jul 15 at 18:28
  • $\begingroup$ 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$). $\endgroup$ – Steven Jul 15 at 19:49
  • $\begingroup$ 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. $\endgroup$ – Steven Jul 15 at 19:51
  • $\begingroup$ 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. $\endgroup$ – Atsina Jul 15 at 19:58

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.