Algoritmo temporale polinomiale non deterministico rispetto al certificato/verificatore per mostrare l'appartenenza a NP

Question

In questo documento (https://arxiv.org/pdf/1706.06708.pdf) gli autori dimostrano che risolvendo in modo ottimale il $n\volte n\volte n$ Il cubo di Rubik è un problema NP-completo.Nel processo, devono dimostrare che il problema decisionale rilevante appartiene a NP (sezione 2.5 a pagina 6).Per fare ciò, descrivono un algoritmo che risolve in modo non deterministico il Cubo in tempo polinomiale.Mi sembra che questo sia uno sforzo maggiore del necessario.

In particolare, il problema decisionale rilevante è il seguente:Il problema del Cubo di Rubik ha come input una permutazione $t$ e un valore $k$.L'obiettivo è decidere se $t$ può essere risolto in $k$ o meno mosse.Quindi, invece di costruire un algoritmo di soluzione temporale polinomiale non deterministico, potrebbero semplicemente fornire un certificato che una decisione "sì" è solo un elenco di al massimo $k$ si muove e verifica che il controllo di questo sia un tempo polinomiale.

Quindi le mie domande sono le seguenti.Le due definizioni seguenti sono effettivamente equivalenti?

1. NP è la classe di complessità dei problemi decisionali risolvibili da una macchina di Turing non deterministica in tempo polinomiale.
2. NP è la classe di complessità dei problemi decisionali per i quali una soluzione può essere confermata in tempo polinomiale (deterministicamente)?

E se sono equivalenti, perché gli autori dell'articolo collegato dovrebbero scegliere il metodo più difficile (o mi sbaglio su questo presupposto)?

---

Tieni presente che sto pubblicando questa domanda su più siti Web StackExchange poiché non sono sicuro di dove sia più adatta.Se è inappropriato qui, lo cancellerò volentieri.Allo stesso modo, mi collegherò a una buona soluzione su un altro sito se riceverà risposta lì.

Answer 1

Il certificato che proponi potrebbe non essere polinomiale nella dimensione dell'input.

La dimensione di input del problema è $O(n^3 + \log k)$, mentre il tuo certificato ha size $\Omega(k \log n)$.Questo non è un polinomio, ad esempio, for $k = 2^n$.

Il tuo certificato funzionerebbe se lo imposti, ad esempio, su un elenco vuoto ogni volta $k = \Omega(\frac{n^2}{\log n})$, e modificare il verificatore per verificare semplicemente se la configurazione di input del cubo è risolvibile per qualsiasi valore di questo tipo $k$ (ignorando così il certificato).