NPのメンバーシップを表示するための証明書/検証者の非決定的多項式時間アルゴリズム

Question

（ https://arxiv.org/pdf/1706.06708.pdf この著者らは、 $ n \ times n \ whe $ Rubik's CubeがNP完全な問題であることを証明しています。このプロセスでは、関連する決定問題がNPに属することを示す必要があります（6ページの2.5項）。これを行うために、それらは、多項式時にキューブを不定に解決するアルゴリズムを説明します。これは必要以上に努力しているようです。

関連する決定問題は次のとおりです。ルービックのキューブの問題は、入力としてのaperait $ t $ 、および値 $ t $ で解決できるかどうかを決定することです。 $ k $ 、またはより少ない移動で解決できます。したがって、不定的な多項式タイムソリューションアルゴリズムを構築するのではなく、単に「はい」の決定がほとんど $ k $ の単なるリストであるという証明書を単に与えることができます。これをチェックすることは多項式の時間です。

だから私の質問は次のとおりです。以下の2つの定義は実際には同等のものですか？

1. NPは、多項式時刻における非決定的チューリング機によって解決可能な決定問題の複雑さクラスです。
2. NPは、多項式時刻（決定論的に）で解決策を確認できる決定問題の複雑さクラスですか？

そしてそれらが同等であれば、リンクされた紙の作者はより困難な方法を選択するのでしょうか（またはこの仮定については間違っています）？

---

私はそれが最良の場所であるとわからないので、私はこの質問を複数のStackexChange Webサイトに投稿しています。ここで不適切であれば、私は喜んで削除します。同様に、それがそこに答えられるならば、私は別のサイトの良い解決策にリンクします。

Answer 1

入力のサイズでは、提案した証明書が多項式ではない可能性があります。

問題の入力サイズは $ o（n ^ 3 + \ log k）$ ですが、証明書のサイズ $ \ omomega（k \ log n）$ 。これは多項式ではありません。例えば、 $ k= 2 ^ n $ 。

$ k=omega（\ frac {n ^ 2} {\ log n}）$ <}/ span>を変更して、キューブの入力構成がそのような $ k $ の値に対して解決可能かどうかをチェックするだけで検証者を変更します（したがって、証明書を無視します）。