性質検査
普通のアルゴリズム: 入力を全て読んで問題を解く
性質検査: 入力の一部（微小な部分）だけを読んで解く
ε: 閾値の定数
ある性質を持っていそうか、全く持っていない（性質からε-farである）かを、ある確率で判定するのが性質検査?
なぜ性質検査をする?
性質検査なら、線形時間どころか定数時間でやることもできる
問題がNP困難な場合にも、性質検査はできる可能性がある 厳密に問題を解く前の枝刈り（可能性のないものをリジェクト）に使える
他分野との関連
近似アルゴリズムは、大体「$ 0.878n」みたいな掛け算による保証をする
性質検査は保証のしかたがちょっと違う
ただ、性質検査の技法を応用できることがある
分散アルゴリズムはランダムにグラフ等の一部をみて出力を決める? 考え方が性質検査と近い?
性質検査の良いところ
そこは専門家が頑張ればいい
大域的/マクロな構造と局所的/ミクロな構造の関係を明らかにする いろいろな対象で性質検査は研究されている
いくつかの研究では成功している（すごい）
ただ当然そもそも全ての入力は読めないから、情報理論的な手法を使っている 情報科学の達人.icon