TY - JOUR
T1 - Near-testable sets
AU - Goldsmith, Judy
AU - Hemachandra, Lane A.
AU - Joseph, Deborah
AU - Young, Paul
PY - 1991
Y1 - 1991
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0026171047&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026171047&partnerID=8YFLogxK
U2 - 10.1137/0220033
DO - 10.1137/0220033
M3 - Article
AN - SCOPUS:0026171047
SN - 0097-5397
VL - 20
SP - 506
EP - 523
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 3
ER -