カテゴリー: NP-complete

Decrypt history, Encrypt future™

ロバスト軌道問題とは何か|完全一致ではなく許容軌道で判定する

ロバスト軌道問題とは、完全一致だけを同一とみなすのではなく、許容された変換の範囲(軌道)の中に入るかを判定する、という枠組みの呼び方である。数学の定番用語として定着した名称ではなく、同一性判定を設計するときの整理用の言葉…
Read more

ダークマター判定から学ぶアノマリー検出

序章:見えないものを「ある」と知る技術 宇宙の総質量エネルギーのうち、私たちが日常的に触れ、観測できる通常の物質(バリオン物質)はわずか5%に過ぎない。残りの約27%は正体不明の「ダークマター(暗黒物質)」であり、約68…
Read more

原始重力波とは何か|未確定力学を観測する推論モデル

原始重力波は、直接実験できない初期宇宙の力学を、CMBのBモード偏光とテンソル・スカラー比 \(r\) の上限から逆算するための推論モデルである。検出そのものより、前景分離・系統誤差・ベイズ証拠によって仮説空間をどこまで…
Read more

公理とは何か|証明の前提を選ぶ操作

公理とは、絶対的な真理そのものではなく、命題を導くために置く前提の集まりである。少ない前提から、多くの命題を証明するための出発点である。どの公理を選ぶかで、展開できる理論の範囲が変わる。事業の前提にも似た役割があるが、数…
Read more

コルモゴロフ複雑性とは何か|最短記述としての既約さ

コルモゴロフ複雑性とは、ある対象を出力する最も短いプログラムの長さである。記述が短いほど、その対象は規則を持ち、圧縮しやすい。どのプログラムも十分に短くできないなら、その対象は規則に乏しく、ランダムに近い。名称は And…
Read more

coNPとは何か|Noであることの短い証拠

coNP とは、「属さない(No である)」ことを、短い証拠で多項式時間に検証できる問題のクラスである。補集合が NP に属するとき、その問題は coNP に入る。NP が Yes の短い証拠を扱うのに対し、coNP は…
Read more

2-SATとは何か|2点間の矛盾発見を多項式時間で検証する

2-SAT とは、各節が2個以下のリテラルからなる CNF の充足可能性問題である。含意グラフと強連結成分(SCC)を使えば、多項式時間で解ける。したがって 2-SAT は P に属する。節の幅を2に抑えるだけで、3-S…
Read more

Satisficingとは何か|最適解ではなく充足水準で止める

Satisficing(満足化)とは、最適解を探し続けるのではなく、あらかじめ定めた充足水準を満たした案を見つけた時点で探索を止める意思決定の枠組みである。Herbert A. Simon(1916–2001)が提唱した…
Read more

CDCLとは何か|失敗を再訪禁止の学習節へ変換する

CDCL(Conflict-Driven Clause Learning)とは、SAT を解く手続きの一つである。変数の値を仮に決め、そこから必然的に決まる割り当てを進め、矛盾が起きたら原因を短い禁止条件(学習節)にまと…
Read more

Bounded Model Checkingとは何か|探索範囲を有限に固定する

Bounded Model Checking(BMC:有界モデル検査)とは、システムの振る舞いを無限の未来まで調べるのではなく、先の k ステップまでに区切り、「まずい状態へ到達する道があるか」を調べる手法である。範囲の…
Read more