カテゴリー: NP-complete

Decrypt history, Encrypt future™

3-SATとは何か|事業の制約を変数と節で構造化する

3-SAT とは、各節がちょうど3個のリテラルからなる連言標準形(CNF)の充足可能性問題である。変数に真か偽を割り当て、すべての節を同時に真にできるかを問う。形は単純だが、NP 完全問題の代表であり、多くの還元の出発点…
Read more

粗視化とは何か|巨大な状態空間を目的に合わせて圧縮する

粗視化(coarse-graining)とは、対象の状態を、目的に必要な違いだけが残るようにまとめる操作である。情報を雑に捨てることではない。何を同じとみなし、何を区別し、どの誤差まで許し、どこで計算を止めるかを、目的か…
Read more

PとNPの違い|解くことと検証することは同じか

PとNPの違いは、「解を見つけること」と「与えられた解を確かめること」が、同じくらいの手間でできるかを問う枠組みにある。ここでいう手間は、人間の感覚での速さではない。入力の大きさを n としたとき、計算に要する手順数が、…
Read more

The lower and upper bounds of computational constraints before discussing AI potential

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

NP-completeの難易度α≈4.267を活用したクリエイティブ

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

Formal definition of NP

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

Any statement that have proof have zero knowledge proof

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

NP completeは現実世界では問題ない程度に満足解を作ることができる

立体は4色以上で塗り分け可能である。一方平面は1-4色で塗り分け可能である。3 colorableの判定はNP completeであるものの、現代のコンピューターはNP completeを3-SATに変換してCDCL(c…
Read more

Orandum est ut sit mens sana in corpore sano.|DNAレベルのパージ機能と決定の質は比例する

1. DNAの「NP性」 ビジネスや人生の決断がなぜ難しいかというと、それがP問題(順番に計算すれば決定的に解ける問題)ではなく、NP困難 / 3SAT問題(選択肢の組み合わせが限りなく非決定的な有限問題)だからです。 …
Read more

Circuit Complexity

Circuit Complexity(回路計算量)とは、計算理論の一分野で、ある計算問題を解くために必要な「論理回路」のサイズや深さを研究する学問です。 通常の計算量理論(PやNPなど)が「プログラムの実行時間やメモリ使…
Read more