Lenguaje unario

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 lenguaje {1, 111, 1111} es unario, al igual que el lenguaje {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 numérico unario . Dado que el universo de cadenas sobre cualquier alfabeto finito es un conjunto numerable , todo lenguaje puede asignarse a un conjunto único A de números naturales; por lo tanto, todo lenguaje tiene una versión unaria {1 ^k  | k ∈ A}. A la inversa, todo lenguaje unario tiene una versión binaria más compacta, el conjunto de codificaciones binarias de números naturales k tales que 1 ^k pertenece al lenguaje. 

Dado que la complejidad se suele medir en función de la longitud de la cadena de entrada, la versión unaria de un lenguaje puede ser más sencilla que el lenguaje original. Por ejemplo, si un lenguaje se puede reconocer en tiempo O(2n ⁾ , su versión unaria se puede reconocer en tiempo O( n ), porque n ha aumentado exponencialmente. De forma más general, si un lenguaje se puede reconocer en tiempo O(f( n )) y espacio O(g( n )), su versión unaria se puede reconocer en tiempo O( n + f(log n )) y espacio O(g(log n )) (solo leer la cadena de entrada requiere tiempo O( n )). Sin embargo, si la pertenencia a un lenguaje es indecidible , entonces la pertenencia a su versión unaria también lo es.

TALLY pertenece a P/poly , la clase de lenguajes que pueden reconocerse en tiempo polinomial a partir de una función de asesoramiento que depende únicamente de la longitud de la entrada. En este caso, la función de asesoramiento requerida es muy simple: devuelve un bit para cada longitud de entrada k, indicando si 1 ^k pertenece al lenguaje o no.

Un lenguaje unario es necesariamente un lenguaje disperso , puesto 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-difíciles . El teorema de Berman (1978) establece que si un lenguaje unario es NP-difícil, entonces P = NP . ^{[ 1 ] [ 2 ]} Esto puede demostrarse considerando un algoritmo de tiempo polinomial para 3-SAT.

Este resultado puede extenderse a lenguajes dispersos. ^{[ 3 ] [ 4 ]}

Si L es un lenguaje unario, entonces L* (la estrella de Kleene de L ) es un lenguaje regular . ^{[ 5 ]}

La clase de complejidad P ₁ es la clase de lenguajes unarios que puede ser reconocida por una máquina de Turing de tiempo polinomial (dada su entrada escrita en unario); es el análogo de la clase P . El análogo de NP en el contexto unario es NP ₁ . También se conoce una clase de conteo #P ₁ , el análogo de #P . ^{[ 6 ]}