Some properties are not even partially testable

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

For a property $P$ and a sub-property $P^{\prime }$, we say that $P$ is $P^{\prime }$-partially testable with $q$ queries if there exists an algorithm that distinguishes, with high probability, inpu…