Wednesday, June 18, 2008

Indistinguishability of property testings

粗略地說,兩個 graph properties 若為 indistinguishable,則在某種程度上來講,它們是非常相似的性質 ("很難分的出來")。根據 Alon et al. 在 2000 年的一個 lemma:

If P and Q are indistinguishable graph properties, then P is testable if and only if Q is testable.

這個 lemma 的證明,大致上是利用 PQ 當中一個 property 的 tester,經過稍微修改之後,拿去測另一個性質。反正他們很「相似」,所以 testing 的效果不會差多少。

所以說,就像證明 NP-hardness 的 reduction 一樣,要證明 testability 也有所謂的 "reduction",靠的就是 indistinguishability 的推導。

No comments: