Não determinístico em tempo polinomial algoritmo versus certificado/verificador para mostrar a associação em NP

Question

Neste papel (https://arxiv.org/pdf/1706.06708.pdf) o autor provar que, de forma ideal de resolver o $n $ O Cubo de Rubik é um problema NP-completo.No processo, eles devem mostrar que o relevante problema de decisão pertence NP (seção 2.5, página 6).Para fazer isso, eles descrevem um algoritmo que nondeterministically resolve o Cubo em tempo polinomial.Parece-me que esta é mais esforço do que o necessário.

Em particular, o problema de decisão é o seguinte:O Cubo de Rubik problema tem como entrada uma permutação $t$ e um valor $k$.O objetivo é decidir se $t$ pode ser resolvido em $k$ ou menos de movimentos.Assim, em vez de construir um não determinístico em tempo polinomial algoritmo de solução, eles poderiam simplesmente dar um certificado de que um "sim" a decisão é apenas uma lista de, no máximo $k$ move-se e verificar que verificar se este está em tempo polinomial.

Então minhas perguntas são as seguintes.São duas definições abaixo, na verdade, equivalentes?

1. NP é a classe de complexidade dos problemas de decisão que podem ser resolvidos por uma máquina de Turing não determinística em tempo polinomial.
2. NP é a classe de complexidade dos problemas de decisão para os quais uma solução pode ser confirmado em tempo polinomial (determinística)?

E se eles são equivalentes, porque os autores da vinculado papel de escolher a mais difícil de método (ou estou errado sobre essa suposição)?

---

Note que estou postando esta questão em vários StackExchange websites como eu não tenho certeza de que é melhor ajuste.Se é inapropriado aqui, eu vou feliz excluí-lo.Da mesma forma, irá vincular a uma boa solução em outro site, se ele for respondida.

Answer 1

O certificado que você propõe não pode ser polinomial no tamanho da entrada.

O tamanho da entrada do problema é $O(n^3 + \log k)$, enquanto seu certificado tem tamanho $\Omega(k log n)$.Este não é o polinômio, por exemplo, para $k = 2^n$.

O certificado de trabalho se você definir, por exemplo, para uma lista vazia sempre que $k = \Omega(\frac{n^2}{\log n})$, e modificar o verificador apenas para verificar se a configuração de entrada do cubo é solução para qualquer valor de $k$ (ignorando assim o certificado).