性質検査

Last updated Unknown Edit Source

• 普通のアルゴリズム: 入力を全て読んで問題を解く

• 性質検査: 入力の一部（微小な部分）だけを読んで解く

• ε-farnessという概念

  • ε: 閾値の定数
  • ある性質を持っていそうか、全く持っていない（性質からε-farである）かを、ある確率で判定するのが性質検査?

• なぜ性質検査をする?

  • データーが巨大になった時は多項式時間でも遅い
    • 性質検査なら、線形時間どころか定数時間でやることもできる
  • 問題がNP困難な場合にも、性質検査はできる可能性がある
  • 厳密に問題を解く前の枝刈り（可能性のないものをリジェクト）に使える

• 他分野との関連

  • 近似アルゴリズム
    • 近似アルゴリズムは、大体「$0.878n$」みたいな掛け算による保証をする
    • 性質検査は保証のしかたがちょっと違う
      • ただ、性質検査の技法を応用できることがある
  • 分散アルゴリズム
    • 分散アルゴリズムはランダムにグラフ等の一部をみて出力を決める?
    • 考え方が性質検査と近い?

• 性質検査の良いところ

  • アルゴリズムは簡単、より大変なのは解析
    • そこは専門家が頑張ればいい
  • 大域的/マクロな構造と局所的/ミクロな構造の関係を明らかにする

• いろいろな対象で性質検査は研究されている

  • 単調性の性質検査
  • グラフの性質検査
  • ゴール: 定数時間で解ける性質の必要十分条件を得る
    • いくつかの研究では成功している（すごい）
    • ただ当然そもそも全ての入力は読めないから、情報理論的な手法を使っている
•