Membresía parcial

En matemáticas e informática teórica , el problema de la semipertenencia a un conjunto consiste en decidir cuál de dos elementos posibles tiene más probabilidades lógicas de pertenecer a ese conjunto; o bien, dados dos elementos, de los cuales al menos uno está en el conjunto, distinguir al miembro del no miembro.

El problema de la semipertenencia puede ser significativamente más sencillo que el problema de la pertenencia. Por ejemplo, consideremos el conjunto S ( x ) de cadenas binarias de longitud finita que representan los racionales diádicos menores que un número real fijo x . El problema de la semipertenencia para un par de cadenas se resuelve tomando la cadena que representa el racional diádico menor, ya que si exactamente una de las cadenas es un elemento, debe ser la menor, independientemente del valor de x . Sin embargo, el lenguaje S ( x ) puede que ni siquiera sea un lenguaje recursivo , puesto que existen incontables valores de x , pero solo contables lenguajes recursivos.

Una función f sobre pares ordenados ( x , y ) es un selector para un conjunto S si f ( x , y ) es igual a x o a y, y si f ( x , y ) está en S siempre que al menos uno de x o y esté en S. Un conjunto es semirrecursivo si tiene un selector recursivo , y es P-selectivo o semifactible si es semirrecursivo con un selector de tiempo polinomial .

Los conjuntos semifactibles tienen circuitos pequeños ; están en la jerarquía baja extendida ; y no pueden ser NP-completos a menos que P=NP .

• Derek Denny-Brown, "Algoritmos de semi-pertenencia: algunos avances recientes", Informe técnico , Departamento de Ciencias de la Computación de la Universidad de Rochester, 1994.
• Lane A. Hemaspaandra, Mitsunori Ogihara, «The complexity theory companion», Texts in theoretical computer science , EATCS series, Springer, 2002, ISBN 3-540-67419-5, página 294
• Lane A. Hemaspaandra, Leen Torenvliet, «Teoría de algoritmos semifactibles», Monografías en informática teórica , Springer, 2003, ISBN 3-540-42200-5, página 1
• Ker-I Ko, «Aplicación de técnicas de la teoría de la complejidad discreta a la computación numérica» en Ronald V. Book (ed.), «Estudios en teoría de la complejidad», Notas de investigación en ciencias de la computación teórica , Pitman, 1986, ISBN 0-470-20293-9pág.  40
• C. Jockusch jr (1968). "Conjuntos semirrecursivos y reducibilidad positiva" (PDF) . Trans. Amer. Math. Soc. 137 (2): 420– 436. doi : 10.1090/S0002-9947-1968-0220595-7 .