世界大百科事典（旧版）内の決定問題の言及
【アルゴリズム】より
…しかし理論的には次のような興味がある。非決定性アルゴリズムを〈ハミルトン閉路が存在するか否か〉，一般に〈イエスかノーか〉を問ういわゆる〈決定問題〉に適用したとき，次の評価基準を採用する。(1)答がノーの場合の計算量は問わない。…
【計算可能性】より
…さらに計算可能部分関数fに自然数mが対応することをf⇔mで表し，このときm[n]はf(n)を表すとする。 自然数をパラメーターとする命題P(n)の真偽を決定するアルゴリズムを求める問題を決定問題という。命題が真であることを1，偽であることを0で表せば，P(n)は自然数の上の関数になる。…
※「決定問題」について言及している用語解説の一部を掲載しています。
出典｜株式会社平凡社「世界大百科事典（旧版）」
Sponsored by 