Property testing とは

コンピュータサイエンスでは、決定問題のプロパティテストアルゴリズムは、入力に対するクエリの複雑さが問題のインスタンスサイズよりもはるかに小さいアルゴリズムです。一般に、プロパティテストアルゴリズムは、いくつかの数学的オブジェクト(グラフやブール関数など)が「グローバル」プロパティを持つか、このプロパティを持つのが「遠い」かを決定するために使用されます。オブジェクト。
例えば、次の約束問題は、(任意の定数ε> 0に対して)クエリの複雑さがインスタンスサイズに依存しないアルゴリズムを認めています。
「n個の頂点にグラフGを与え、Gが二分木であるかどうかを決定するか、あるいはGを最大でも ϵ ( n 2 ) {\displaystyle \epsilon {\tbinom {n}{2}}} 個の辺の任意の部分集合を削除しても二分木にすることはできません。
プロパティテストアルゴリズムは、確率論的にチェック可能なプルーフの定義の中心であり、確率論的にチェック可能なプルーフは本質的に、プロパティテストアルゴリズムによって検証できる証明です。