日記:言語が決定問題のインスタンスとして妥当であることの判定コストの話

計算複雑性のプロと会話する機会があったので聞いてみました。

なぜ言語がXの適切な元かどうかを多項式時間で決定できる必要があるのかは自分が当たった本には書かれていおらず、私自身も理解できていないのでもし知っていれば教えてください

yuyubu.hatenablog.com

あるバイナリがNP=(X,Y)のXの元であるかを多項式時間で検証できる必要がある→なぜ

• そんなに深い理由はない
• ただの定義

• めちゃくちゃな問題を除外するためのルール

  • ハミルトン閉路問題の問題X自体の元を「ハミルトン閉路が存在するインスタンス」としてしまえばアルゴリズムは常にトートロジーな関数を使うことで*1ハミルトン閉路問題がO(1)で解けたと言い張れてしまう。

• EXPやNEXPではこの制限は外れるか？

  • 多分外れると思う。

ズバリな理由は教えてもらえなかったが、あまり深く考える必要はないらしい。

とにかく、自分が基本的な概念の理解を根本的に誤ってるところから発生する誤解という訳ではなさそう。

• 余談:この分野の本は中身がデタラメなものが多いらしい。
  • プロの方も最初に読んだテキストがそんな感じだったらしい。
  • 「組合せ最適」は著者訳者共に安心できるらしい。

組合せ最適化 第2版 (理論とアルゴリズム)

*1:f(x)→1