NL-Integridad y PSPACE-Integridad

Para resolver problemas complejos necesitamos un algoritmo eficiente. Nos enfrentamos a tantos problemas y algunos de ellos se pueden resolver mediante el uso de un algoritmo y cada algoritmo requiere algo de espacio y tiempo. Para un mejor rendimiento del programa, necesitamos reducir la complejidad espacial y temporal del algoritmo.

En este artículo discutiremos brevemente sobre NL-completitud, PSPACE-Completitud con algunas definiciones básicas.

Ejemplos que requerirán más memoria: el gráfico web, los genomas, etc.

Queremos un algoritmo que use una pequeña cantidad de memoria, de modo que se pueda manipular una gran cantidad de datos sin almacenar todos los datos en el disco duro de la computadora a la vez. Un algoritmo toma un espacio sublineal porque la entrada de n bits toma un espacio lineal. 

Aquí se utiliza la máquina de Turing de dos cintas.

1. Cinta de solo lectura que contiene entrada
2. Cinta de trabajo que se puede utilizar libremente

El espacio adquirido por la cinta de trabajo contribuye a la complejidad del espacio. 

Tenemos,

 L = SPACE ( log n ) , and  
 NL = NSPACE ( log n ) 

COMPLEJIDAD ESPACIAL:
Se define como la cantidad de espacio de memoria de la computadora requerida para resolver cualquier problema computacional dado en función de la entrada o podemos decir que es la cantidad de memoria que necesita un algoritmo, hasta que se completa su ejecución. Un algoritmo se llama completo si termina y si existe su solución.

NL-Completitud:
NL contiene un problema de decisión y se resuelve mediante una máquina de Turing no determinista. Antes de comprender la completitud de NL, primero entendemos la reducibilidad del espacio logarítmico.

Reducibilidad del espacio logarítmico:
A es el espacio logarítmico reducible a B, si para todas las funciones f :

 {0, 1}* → {0, 1}* such that x ∈ A if f (x) ∈ B for every x ∈ {0, 1}* 

Para definir la completitud de NL, requerimos una reducción adecuada. Si L = NL es la cuestión teórica de la complejidad. Por lo tanto, la reducción es una reducción del espacio logarítmico, es decir, dada una string de entrada x, tenemos una función f(x) tal que f(x) es calculable por DTM utilizando como máximo celdas O(log |x|) en la cinta de trabajo.

Un idioma «A» es NL-completo si cumple las dos condiciones a continuación:

1. «A» está en NL. (A ∈ NL)
2. El idioma que pertenece a NL puede ser un espacio de registro reducible a «A»

 (para todo B en NL, existe B ≤L A).

Aplicaciones:

• Conectividad ST
• Lógica proposicional
• 2-satisfacibilidad

PSPACE-completitud:
todos los problemas de decisión que se pueden resolver en longitud de entrada polinomial, y si todos los demás problemas resueltos en espacio polinomial se pueden convertir a tiempo polinomial. El «problema verbal» para gramáticas deterministas sensibles al contexto fue el primer problema completo de PSPACE. 

Un idioma «A» es PSPACE-completo si cumple las dos condiciones a continuación

1. “A” está en PSPACE. (A ∈ PESPACIO)
2. El lenguaje perteneciente a PSPACE puede ser tiempo polinomial reducible a «A»

(para todo B en PSPACE, existe B ≤L A).

Tenga en cuenta que si «A» sigue solo la segunda condición, decimos que es PSPACE-hard.

Aplicaciones:

• Hexadecimal (juego de mesa).
• Lógica de igualdad de primer orden
• Teoría de primer orden de conjuntos bien ordenados
• cálculo lambda, etc.

¿Por qué se usa la reducción del espacio de registro para la completitud de NL mientras que la reducción de PSPACE no se usa para la completitud de PSPACE? 
Como L ⊆ NL ⊆ PAGS . por lo tanto, no tiene sentido usar la reducción de tiempo polinomial para la completitud de NL, ya que la reducción de tiempo polinómico es más poderosa que la clase L. Por lo tanto, usamos la reducción de espacio logarítmico para la completitud de NL.

Los resultados de integridad son más impresionantes con una reducción más débil, ya que la reducción puede hacer menos trabajo, por lo tanto, la reducción en realidad está haciendo todo el trabajo, por lo tanto, usamos la reducción de tiempo polinomial en lugar de la reducción de espacio polinomial.