Near-Testable Sets
Judy Goldsmith, Lane A. Hemaspaandra, Deborah Joseph, Paul R. Young · SIAM Journal on Computing · 1991
In this paper a new property of sets, near-testability, is introduced. A set S is near-testable$(S \in NT)$ if the membership relation for all immediate neighbors is polynomially computable; i.e., if the function $t(x) = \chi _S (x) + \chi _S (x - 1)(\bmod 2)$ is polynomially computable. The near-testable sets form a subclass of the class $ \oplus P$ (parity polynomial time), introduced by Papadimitriou and Zachos, and Goldschlager and Parberry. $ \oplus P$ has a complete set $ \oplus SAT$ that has recently been shown by Valiant and Vazirani to be hard for $NP$ under randomized polynomial-time reductions. It is proved that there is a uniform polynomial one-one reduction that takes every set in $ \oplus P$ to a near-testable set, and it is shown that the image of $ \oplus SAT$ under this reduction (which we call $NTSAT$) is polynomially isomorphic to $ \oplus SAT$. As corollaries it is shown that $NTSAT$ is complete for both $NT$ and for $ \oplus SAT$, that $NTSAT$ is hard for $NP$ under randomized polynomial-time reductions, and that the existence of one-way functions implies the existence of sets that are near-testable but not polynomially decidable. It is then asked whether near-testability is preserved under p-isomorphisms. This leads to a generalization, $NT^ * $, of $NT$ similar to those introduced by Meyer and Paterson and by Ko for self-reducible sets. With this more general definition, $NT^ * $ is shown to be closed under polynomial-time isomorphisms while remaining a subclass of $ \oplus P$. It is conjectured that it is a proper subclass. In fact it is shown that, relative to a random oracle, the containments $P \subseteq NT \subseteq NT^ * \subseteq \oplus P$ are proper with probability one. It is also shown that, relative to a random oracle, with probability one $NT$ and $NT^ * $ are incomparable with both $NP$ and with $coNP$. Finally, the effects that the distribution and density of elements have on the complexity of near-testable sets are considered.