カテゴリー: computability

Bounded Model Checking（BMC／有界モデル検査）とは、未来を無限に調べるのではなく、先の k ステップまでに区切って、『まずい状態にたどり着く道があるか』を調べる手法である。全部の未来について安全だ…
Read more

3-SATとは、各節がちょうど3個のリテラルからなる連言標準形（CNF／Conjunctive Normal Form）の充足可能性問題である。与えられた論理式を真にする真偽割当が存在するかを問う。CNFは「節（OR）の…
Read more

粗視化（coarse-graining）とは、世界のすべてを同じ細かさで扱うのではなく、目的に必要な違いだけを残して状態をまとめることである。経営へ応用するなら、追跡する状態変数を目的に合わせて間引く手続である。 情報を…
Read more

PとNPの違いを一言で表すと、Pは効率よく解ける問題のクラス、NPは正解の候補を受け取れば効率よく検証できる問題のクラスである。 ここでいう「効率よく」とは、人間の感覚で速いという意味ではない。入力の大きさを \(n\)…
Read more

言語で喋るから合成数が増えて既約性を失い、決定、判断ができなくなる。自然言語は補助として、記号とステップに置き換えて既約性を検証すれば素数性判定ができる。 口論で混乱する人がいるのは相手の言葉をそのまま処理するからである…
Read more

The Codified Preamble: Computational and Structural Tractability of AI When discussing Artificial Intelligence…
Read more

ハードウェアの物理的な限界（エンジニアリング）から、計算理論による下界の特定について 並列計算と計算複雑性理論の系譜（1967〜1995） 1. 黎明期：物理リソースの限界と「直列の壁」 📌 アムダールの法則（Amdah…
Read more

ヒットソングが飽きないのは、過去に確率的に生き残ったヒットソングの情報を網の目に組み合わせているからと言える。そうすると、論文も、過去の確率的に生き残ったロングセラーをつぎはぎに高次論理で繋ぎ合わせれば次のヒット論文を作…
Read more

It is traditional to view NP as the class of languages whose elements posses short proofs of membership. A “pr…
Read more

あらゆる言語による論理は記号に置き換えることができる。あるstatement(宣言)がyes or noで判断できる記号形式を取る時、それをproposition(命題)と呼ぶ。propositionがtrueであること…
Read more