性質検査

Last updated Unknown Edit Source

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

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

• ε-farnessという概念

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

• なぜ性質検査をする?

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

• 他分野との関連

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

      グラフ

      プロットするグラフと、のグラフの二つの意味がある このscrapboxでは、のグラフを指す 使用頻度/リンクされる価値はこっちの方が高いかなーと プロットするグラフは、とかの言葉を使う https://ja.wikipedia.org/wiki/グラフ理論 種類 密vs疎 ...

      1/3/2023

      等の一部をみて出力を決める?
    • 考え方が性質検査と近い?

• 性質検査の良いところ

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

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

  • 単調性の性質検査

    単調性の性質検査

    = されている配列 全部読むわけではないので、たぶんXXという回答になる この場合のの定義 ε: 閾値の定数$0 ...

    1/3/2023

  • グラフの性質検査

    グラフの性質検査

    な: のある左から全ての右、ある右から全ての左に繋がってる （イメージ: の二層をグラフにしたみたいなものはbiclique） 違反枝、違反非枝の個数を用いる #性質検査 ...

    1/3/2023

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