Near-testable sets

A new property of sets, near-testability, is introduced. A set S is near-testable (S ε NT) if the membership relation for all immediate neighbors is polynomially computable; i.e., if the function t(x) = χ_s(x) + χ_s(x - 1) (mod 2) is polynomially computable. The near-testable sets form a subclass of the class ⊗P (parity polynomial time). ⊗P has a complete set ⊗SAT that has recently been shown 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 ⊗P to a near-testable set, and it is shown that the image of ⊗SAT under this reduction (which we call NTSAT) is polynomially isomorphic to ⊗SAT. As corollaries it is shown that NTSAT is complete for both NT and for ⊗P, 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, which is shown to be closed under polynomial-time isomorphisms while remaining a subclass of ⊗P. It is conjectured that it is a proper subclass. 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.