algorithm - NP クラス : なぜ多項式の長さが出力されるのですか?

Question

NP クラスに該当する問題の場合:

1. 問題の解には、多項式出力の長さがなければならず、
2. 解は多項式時間で検証可能でなければなりません。

多項式出力の長さの意味は何ですか?

PS：多項式出力の長さは、出力が多項式時間で検証可能であるために必要な前提条件だと思います。(しかし、解は多項式時間で検証できると言うだけで十分です。)

Answer 1

多項式の長さの賦課は、マシンをユニバーサル チューリング マシンとしてモデル化しているためです。

この場合、出力「テープ」は多項式の長さでなければなりません。

これは、最新の言語を使用していて多項式の長さの結果を期待しているからではありません。