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