skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

Near-testable sets

GOLDSMITH, J ; HEMACHANDRA, L. A ; JOSEPHI, D ; YOUNG, P

SIAM journal on computing, 1991-06, Vol.20 (3), p.506-523 [Periódico revisado por pares]

Philadelphia, PA: Society for Industrial and Applied Mathematics

Texto completo disponível

Citações Citado por
  • Título:
    Near-testable sets
  • Autor: GOLDSMITH, J ; HEMACHANDRA, L. A ; JOSEPHI, D ; YOUNG, P
  • Assuntos: Algorithmics. Computability. Computer arithmetics ; Applied sciences ; Complexity theory ; Computer science ; Computer science; control theory; systems ; Exact sciences and technology ; Theoretical computing
  • É parte de: SIAM journal on computing, 1991-06, Vol.20 (3), p.506-523
  • Descrição: 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.
  • Editor: Philadelphia, PA: Society for Industrial and Applied Mathematics
  • Idioma: Inglês
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.