De Wikipedia, la enciclopedia libre
Ir a navegaciónSaltar a buscar

En la teoría de la complejidad computacional , un lenguaje unario o lenguaje de conteo es un lenguaje formal (un conjunto de cadenas ) donde todas las cadenas tienen la forma 1 k , donde "1" puede ser cualquier símbolo fijo. Por ejemplo, el idioma {1, 111, 1111} es unario, al igual que el idioma {1 k  | k es primo }. La clase de complejidad de todos estos lenguajes a veces se denomina TALLY .

El nombre "unario" proviene del hecho de que un lenguaje unario es la codificación de un conjunto de números naturales en el sistema de numeración unario . Dado que el universo de cadenas sobre cualquier alfabeto finito es un conjunto contable , cada idioma puede asignarse a un conjunto A único de números naturales; así, cada lengua tiene una versión unaria {1 k  |  k en A}. A la inversa, cada lenguaje unario tiene una versión binaria más compacta, el conjunto de codificaciones binarias de números naturales k tal que 1 k está en el lenguaje.

Dado que la complejidad generalmente se mide en términos de la longitud de la cadena de entrada, la versión unaria de un idioma puede ser "más fácil" que el idioma original. Por ejemplo, si una lengua puede reconocerse en O (2 n ) tiempo, su versión unaria puede reconocerse en O ( n ) tiempo, porque n se ha vuelto exponencialmente más grande. De manera más general, si una lengua puede reconocerse en O (f ( n )) tiempo y O (g ( n )) espacio, su versión unaria puede reconocerse en O ( n + f (log n )) tiempo y O (g (log n )) espacio (requerimos O ( n ) tiempo solo para leer la cadena de entrada). Sin embargo, si la pertenencia a un idioma es indecidible, entonces la pertenencia a su versión unaria también es indecidible.

Relaciones con otras clases de complejidad

TALLY está contenido en P / poly , la clase de lenguajes que pueden reconocerse en tiempo polinomial dada una función de aviso que depende únicamente de la longitud de entrada. En este caso, la función de aviso requerida es muy simple: devuelve un solo bit por cada longitud de entrada k especificando si 1 k está en el idioma o no.

Un lenguaje unario es necesariamente un lenguaje disperso , ya que para cada n contiene como máximo un valor de longitud n y como máximo n valores de longitud como máximo n , pero no todos los lenguajes dispersos son unarios; por lo tanto, TALLY está contenido en SPARSE .

Se cree que no existen lenguajes unarios NP-duros : si existe un lenguaje unario que es NP-completo , entonces P = NP . [1]

Este resultado se puede extender a idiomas dispersos. [2]

Si L es un lenguaje unario, entonces L * (la estrella de Kleene de L ) es un lenguaje regular . [3]

Clases de conteo

La clase de complejidad P 1 es la clase de los lenguajes unarios que pueden ser reconocidos por una máquina de Turing de tiempo polinómico (dada su entrada escrita en unario); que es el análogo de la clase P . El análogo de NP en el entorno unario es NP 1 . También se conoce una clase de conteo #P 1 , el análogo de #P . [4]

Referencias

Notas

  1. ^ Piotr Berman. Relación entre densidad y complejidad determinista de lenguajes NP-completos. En Actas de la 5ª Conferencia sobre Autómatas, Lenguajes y Programación , págs. 63–71. Springer-Verlag. Notas de la conferencia en Ciencias de la Computación # 62 . 1978.
  2. ^ 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.
  3. ^ -, Patrick. "La estrella de Kleene de un lenguaje unario infinito siempre produce un lenguaje regular" . Intercambio de pilas de informática . Consultado el 19 de octubre de 2014 .CS1 maint: nombres numéricos: lista de autores ( enlace )
  4. ^ Leslie Valiant , La complejidad de los problemas de enumeración y confiabilidad , [1] acceso cerrado

Referencias generales