数理論理学に出てくる用語のまとめ - 大人になってからの再学習
参考： これだけは知っておきたい数学ビギナーズマニュアル 作者: 佐藤文広出版社/メーカー: 日本評論社発売日: 1994/06メディア: 単行本購入: 4人 クリック: 21回この商品を含むブログ (16件) を見る ■公理：Axiom 理論の土台となる約束事。前提事項。 （証明の必要は無い。） ■定義：Definition 新しく導入する述語や単語の正確な意味を定めること 以降の「定理」・「命題」・「系」・「補題」はいずれも定義・公理に基づく厳密な推論により証明された主張。 違いは、理論の中で果たしている「役割」であって、厳密な区別は無い。 最も一般的なものは「命題」で、他の定理、系、補題も命題の一種と言うことができる。 ■定理：Theorem 成り立つことが証明済みの命題で、特に重要であるもの。 （公理から真であることが導き出される） ■命題：Proposition 定理と呼ぶほどで
PとNPとNP完全とNP困難 - 大人になってからの再学習
計算複雑性の話の中で、P、NP、NP完全、NP困難というキーワードが登場する。 それぞれの違いを、字面だけから判断するのは、少し無理そう。 それで、詳しい説明を Wikipedia に求めると・・・。 ・P（Wikipedai） ・NP（Wikipedai） ・NP完全（Wikipedai） ・NP困難（Wikipedai） 大学などで正確な定義を学習していない場合には、軽く絶望することになる。 そこで、厳密ではないことをあらかじめ断ったうえで、これらを簡単に説明してみる。 （証明されていないが、前提としてNP≠P とする。これが証明できたら100万ドルもらえる。） まず、それぞれの関係は下図のように表すことができる。 図では、上のものほど難しい問題で「P≦NP≦NP完全≦NP困難」と言うことができる。 さらに次のことが言える。 ・ P は現実的な時間で解を求めることができる問題。 ・ N
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
