この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年8月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合、あるいはの部分集合からへの写像である。
たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。
決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。
optimization problem）は特定の集合上で定義された実数値関数または整数値関数についてその値が最小（もしくは最大）となる状態を解析する問題である。数理計画問題（すうりけいかくもんだい、（英: mathematical programming problem）、エネルギー最小化問題（エネルギーさいしょうかもんだい）とも。
関数問題（かんすうもんだい、function problem）とは、計算量理論において、各入力に対してある出力を返す形式の問題をいう。評価問題とも呼ばれる。文字列上の写像 Σ ∗ → Σ ∗ {\displaystyle \Sigma ^{*}\to \Sigma ^{*}} で表される。主に判定問題（関数問題のうち出力が
assumption ナップサック問題 en:knapsack problem 部分和問題 en:subset sum problem ラティス問題 SVP / CVP 巡回セールスマン問題 en:traveling salesman problem 証明に関する手法 / 仮定 / モデル 確率的証明 probabilistically
the problem of Plateau”. Trans. Amer. Math. Soc. 33 (1): 263–321. doi:10.2307/1989472. JSTOR 1989472. Douglas, Jesse (1939). “Green's function and the
imbedding problem for Riemannian manifolds"（1956年、数学雑誌Annals of Mathematicsにて発表） "Analyticity of the solutions of implicit function problem with analytic
a Frobenius-type theorem for function spaces”. Acta Arithmetica 24: pp. 507–528. ^ Babenko, K.I. (1978). “On a problem of Gauss”. Soviet Math. Dokl.
function MakeSet(x) x.parent := x function Find(x) if x.parent == x return x else return Find(x.parent) function Union(x, y) xRoot :=
問題解決（もんだいかいけつ、英: problem solving）とは、問題を解決する、すなわち解を発見することであり、思考の一部分である。すべての知的な機能の中で最も複雑な思考であり、高次元の要求の認識と定義されている。それには、より筋道の立った手順及び基礎的な知識の操作、調節が必要となる。
