Semi-adesão - Semi-membership

Em matemática e ciência da computação teórica , o problema de semi-pertinência para um conjunto é o problema de decidir qual dos dois elementos possíveis é logicamente mais provável de pertencer a esse conjunto; alternativamente, dados dois elementos dos quais pelo menos um está no conjunto, para distinguir o membro do não membro.

O problema de semi-adesão pode ser significativamente mais fácil do que o problema de adesão. Por exemplo, considere o conjunto S ( x ) de cadeias binárias de comprimento finito que representam os racionais diádicos menores do que algum número real fixo x . O problema de semi-pertinência para um par de strings é resolvido tomando-se a string que representa o racional diádico menor, pois se exatamente uma das strings for um elemento, deve ser a menor, independentemente do valor de x . No entanto, a linguagem S ( x ) pode nem mesmo ser uma linguagem recursiva , uma vez que existem incontáveis ​​muitas dessas x , mas apenas contáveis ​​muitas linguagens recursivas.

Uma função f em pares ordenados ( x , y ) é um seletor para um conjunto S se f ( x , y ) for igual a x ou y e se f ( x , y ) estiver em S sempre que pelo menos um de x , Y é em S . Um conjunto é semi-recursivo se tiver um seletor recursivo , e é P-seletivo ou semi-viável se for semi-recursivo com um seletor de tempo polinomial .

Os conjuntos semi-viáveis ​​têm pequenos circuitos ; eles estão na hierarquia baixa estendida ; e não pode ser NP-completo a menos que P = NP .

Referências

  • Derek Denny-Brown, "Semi-Membership algoritms: some recent advance", Technical report , University of Rochester Dept. of Computer Science, 1994
  • Lane A. Hemaspaandra, Mitsunori Ogihara, "The complex theory companion", Textos em ciência da computação teórica , série EATCS, Springer, 2002, ISBN   3-540-67419-5 , página 294
  • Lane A. Hemaspaandra, Leen Torenvliet, "Teoria dos algoritmos semi-factíveis", Monografias em ciência da computação teórica , Springer, 2003, ISBN   3-540-42200-5 , página 1
  • Ker-I Ko, "Aplicando técnicas de teoria da complexidade discreta à computação numérica" em Ronald V. Livro (ed.), "Estudos em teoria da complexidade", Notas de pesquisa em ciência da computação teórica , Pitman, 1986, ISBN   0-470-20293 -9 , p.40
  • C. Jockusch Jr (1968). "Conjuntos semirecursivos e redutibilidade positiva" (PDF) . Trans. Amer. Matemática. Soc. 137 : 420–436.