Hispanopedia Wiki
Articulo de referencia

Lenguaje escaso

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 , que cuenta el número de c...

Hispanopedia WikiContenido en espanolLectura gratuita

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 , que cuenta el número de cadenas de longitud n en el lenguaje, está acotada 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 denomina SPARSE .

Obviamente, todos los lenguajes unarios son dispersos. Por consiguiente, el concepto de lenguaje disperso se suele utilizar únicamente para lenguajes con al menos dos letras.

Los lenguajes dispersos se llaman así porque sobre algún alfabeto finitoΣ{\displaystyle \Sigma }hay|Σ|norte{\displaystyle {|\Sigma |}^{n}}cadenas de longitud n . Por lo tanto, cuando el lenguaje no es unario, la probabilidad de que una cadena de longitud n muestreada uniformemente al azar pertenezca al lenguaje converge exponencialmente a 0.

Ejemplos

Para cualquier entero fijo k , considere el conjunto de cadenas binarias que contienen exactamente k repeticiones del bit1{\displaystyle 1}. Para cada n , solo hay(nortek)≲nortek{\displaystyle {\binom {n}{k}}\lesssim n^{k}}cadenas en el lenguaje. Por lo tanto, es disperso.

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.
  • E ≠ NE si y solo si existen lenguajes dispersos en NP que no están en P. [ 1 ]
  • Si algún lenguaje disperso es NP-difícil con respecto a las reducciones de Turing , entonces PH colapsa aΔ2PAG{\displaystyle \Delta _ {2}^{P}}Esto es una consecuencia del teorema de Karp-Lipton . [ 2 ] Este resultado se mejoró en 2005, mostrando que PH colapsa más allá deΔ2PAG{\displaystyle \Delta _ {2}^{P}}. [ 3 ]

Teorema de Mahaney

(Fortune, 1979) demostró que si cualquier lenguaje disperso es co-NP -completo , entonces P = NP . [ 4 ] (Mahaney, 1982) utilizó esto para demostrar el teorema de Mahaney que establece que si cualquier lenguaje disperso es NP -completo , entonces P = NP . [ 5 ] El argumento de Mahaney en realidad no requiere que el lenguaje disperso esté en NP (porque la existencia de un conjunto disperso NP-difícil implica la existencia de un conjunto disperso NP-completo), por lo que existe un conjunto disperso NP -difícil si y solo si P = NP . [ 6 ]

(Ogihara y Watanabe, 1991) ofrece una demostración simplificada del teorema de Mahaney basada en conjuntos izquierdos. [ 7 ]

(Jin-Yi Cai y D. Sivakumar, 1999), basándose en el trabajo de Ogihara, demostraron que, si existe un lenguaje disperso que es P -completo bajo reducción logspace (muchos a uno) , entonces L = P. [ 8 ]

P/poliéster

Aunque no todos los lenguajes en P /poly son dispersos, existe una reducción de Turing en tiempo polinomial desde cualquier lenguaje en P /poly a un lenguaje disperso. [ 9 ]

Existe 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 sinotario público⊆PAG/escuela politécnica{\displaystyle {\textbf {NP}}\subseteq {\textbf {P}}/{\text{poly}}}.

Referencias

  1. ↑ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Conjuntos dispersos en NP-P: EXPTIME versus NEXPTIME. Information and Control , volumen 65, número 2/3, págs. 158-181. 1985. En la Biblioteca Digital de la ACM.
  2. ↑ Karp, Richard M.; Lipton , Richard J. (1980). "Algunas conexiones entre clases de complejidad uniformes y no uniformes". En Miller, Raymond E.; Ginsburg, Seymour; Burkhard, Walter A.; Lipton, Richard J. (eds.). Actas del 12.º Simposio Anual de la ACM sobre Teoría de la Computación, 28-30 de abril de 1980, Los Ángeles, California, EE. UU . ACM. págs. 302–309 . doi : 10.1145/800141.804678 . 
  3. ^ Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori (2003). Alt, Helmut; Habib, Michel (eds.). "Los probadores competidores obtienen resultados mejorados del colapso de Karp-Lipton" . STACS 2003 . Berlín, Heidelberg: Springer: 535– 546. doi : 10.1007/3-540-36494-3_47 . ISBN 978-3-540-36494-8.
  4. ↑ S. Fortune. Una nota sobre conjuntos completos dispersos. SIAM Journal on Computing , volumen 8, número 3, págs. 431–433. 1979.
  5. ↑ SR Mahaney. Conjuntos completos dispersos para NP: Solución de una conjetura de Berman y Hartmanis. Journal of Computer and System Sciences 25:130–143. 1982.
  6. ↑ Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (1990). Complejidad Estructural II . Saltador . págs. 130-131 . ISBN  3-540-52079-1.
  7. ↑ Ogiwara, Mitsunori; Watanabe, Osamu (1991). "Sobre la reducibilidad de tablas de verdad acotadas en tiempo polinomial de conjuntos NP a conjuntos dispersos". SIAM Journal on Computing . 20 (3): 471– 483. doi : 10.1137/0220030 . MR 1094526 . 
  8. ↑ Cai, Jin-Yi; Sivakumar, D. (1999-04-01). "Sparse Hard Sets for P" . J. Comput. Syst. Sci . 58 (2): 280– 296. doi : 10.1006/jcss.1998.1615 . ISSN 0022-0000 . 
  9. ↑ Jin-Yi Cai. Lección 11: P=poly, conjuntos dispersos y el teorema de Mahaney. CS 810: Introducción a la teoría de la complejidad. Universidad de Wisconsin-Madison. 18 de septiembre de 2003 (PDF)
Obtenido de " https://en.wikipedia.org/w/index.php?title=Sparse_language&oldid=1351301397 "