Lenguaje de hojas

El lenguaje hoja es un método en la teoría de la complejidad computacional para caracterizar una clase de complejidad formalizando lo que significa para una máquina "aceptar" una entrada. ^{[ 1 ]}

Las clases de complejidad se definen típicamente en términos de una máquina de Turing no determinista (MNT) de tiempo polinomial . Estas máquinas poseen múltiples rutas computacionales, y los resultados de estas rutas determinan si una entrada es aceptada o rechazada. ^{[ 1 ]} Tradicionalmente, una MNT acepta una entrada si al menos una ruta la acepta, y la rechaza solo si todas las rutas la rechazan. En cambio, una máquina de Turing no determinista conjunta (co-MNT) acepta una entrada solo si todas las rutas la aceptan, y la rechaza si alguna ruta la rechaza. Además, también se pueden definir nociones de aceptación más complejas.

Para formalizar la caracterización de una clase de complejidad, se puede examinar el lenguaje formal asociado a cada condición de aceptación. Esto implica asumir un árbol ordenado y leer las cadenas aceptadas/rechazadas de las hojas del árbol de computación . Las NTM aceptarán si la cadena de la hoja está en el lenguaje 0*1{0, 1}* y rechazarán si la cadena de la hoja está en el lenguaje 0* . ^{[ 2 ]}