En la teoría de la complejidad computacional , un lenguaje disperso es un lenguaje formal (un conjunto de cadenas ) tal que la función de complejidad , contando el número de cadenas de longitud n en el lenguaje, está limitada por una función polinómica de n . Se utilizan principalmente en el estudio de la relación de la clase de complejidad NP con otras clases. La clase de complejidad de todos los lenguajes dispersos se llama SPARSE .
Los lenguajes dispersos se denominan dispersos porque hay un total de 2 n cadenas de longitud n , y si una lengua solo contiene polinomialmente muchas de estas, entonces la proporción de cadenas de longitud n que contiene pasa rápidamente a cero a medida que n crece. Todos los lenguajes unarios son escasos. Un ejemplo de un lenguaje disperso no trivial es el conjunto de cadenas binarias que contienen exactamente k 1 bits para algunos k fijos ; para cada n , solo haycadenas en el idioma, que está delimitado por n k .
Relaciones con otras clases de complejidad
SPARSE contiene TALLY , la clase de lenguajes unarios , ya que estos tienen como máximo una cadena de cualquier longitud. Aunque no todos los lenguajes en P / poly son escasos, existe una reducción de Turing en tiempo polinomial de cualquier lenguaje en P / poly a un lenguaje esparcido. [1] Fortune demostró en 1979 que si alguna lengua escasa es co-NP -completa , entonces P = NP ; [2] Mahaney usó esto para mostrar en 1982 que si cualquier lenguaje disperso es NP -completo , entonces P = NP (este es el teorema de Mahaney ). [3] Ogihara y Watanabe dieron una prueba más simple de esto basada en conjuntos izquierdos en 1991. [4] El argumento de Mahaney en realidad no requiere que el lenguaje disperso esté en NP, por lo que hay un conjunto NP escaso- difícil si y solo si P = NP . [5] Además, E ≠ NE si y sólo si existen lenguas dispersas en NP que no están en P . [6] Hay una reducción de Turing (a diferencia de la reducción de Karp del teorema de Mahaney) de un lenguaje NP -completo a un lenguaje disperso si y solo si. En 1999, Jin-Yi Cai y D. Sivakumar, basándose en el trabajo por Ogihara, mostró que si existe una escasa P -Complete problema, entonces L = P . [7]
Referencias
- ^ Jin-Yi Cai. Clase 11: P = poli, Conjuntos dispersos y Teorema de Mahaney. CS 810: Introducción a la teoría de la complejidad. La Universidad de Wisconsin – Madison. 18 de septiembre de 2003 (PDF)
- ^ S. Fortune. Una nota sobre los conjuntos completos dispersos. SIAM Journal on Computing , volumen 8, número 3, págs. 431–433. 1979.
- ^ SR Mahaney. Conjuntos completos dispersos para NP: Solución de una conjetura de Berman y Hartmanis. Revista de Ciencias de la Computación y Sistemas 25: 130–143. mil novecientos ochenta y dos.
- ^ M. Ogiwara y O. Watanabe. En polinomios, la reducibilidad de la tabla de verdad limitada en el tiempo de los conjuntos NP a conjuntos dispersos. SIAM Journal on Computing, volumen 20, págs. 471–483. 1991.
- ^ Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (1990). Complejidad estructural II . Springer . págs. 130-131. ISBN 3-540-52079-1.
- ^ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Conjuntos dispersos en NP-P: EXPTIME versus NEXPTIME. Información y control , volumen 65, número 2/3, págs. 158–181. 1985. En ACM Digital Library
- ^ Jin-Yi Cai y D. Sivakumar. Conjuntos duros dispersos para P: resolución de una conjetura de Hartmanis. Journal of Computer and System Sciences , volumen 58, número 2, págs. 280–296. 1999. ISSN 0022-0000 . En Citeseer
enlaces externos
- Lance Fortnow . Teoremas favoritos: conjuntos pequeños . 18 de abril de 2006.
- William Gasarch . Conjuntos dispersos (tributo a Mahaney) . 29 de junio de 2007.
- Complejidad Zoo : SPARSE