計算可能性と計算の複雑さ入門:1.問題とアルゴリズム
- 作者: 渡辺治
- 出版社/メーカー: 近代科学社
- 発売日: 1992/10
- メディア: 単行本
- クリック: 1回
- この商品を含むブログ (6件) を見る
読み始めた。
- 「手に負えない問題」
- その問題を解くプログラムが存在しない(計算不可能)
- 多項式時間内に解くプログラムが存在しない(NP問題)
その他記号のセットアップと命題論理式について
- 命題論理式
- 命題変数と論理記号(∧、∨、¬)からなる式
-
- F(X_1,X_2)=[X_1∧X_2]∧¬X_1
- 真偽値の組から真偽値の組への関数
- 拡張命題論理式
- →←などをつかえるようにする
- 普通の命題論理式に直せる
- P→Qは¬P∨Qと同値
プログラムから名に変えられるのは、正しく停止したときのみと限定
