Hispanopedia Wiki
Articulo de referencia

Reducción de primer orden

En informática , una reducción de primer orden es un tipo de reducción muy fuerte entre dos problemas computacionales en la teoría de la complejidad computacional . Una reducció...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , una reducción de primer orden es un tipo de reducción muy fuerte entre dos problemas computacionales en la teoría de la complejidad computacional . Una reducción de primer orden es una reducción donde cada componente está restringido a pertenecer a la clase FO de problemas calculables en lógica de primer orden .

Dado que tenemosFO⊊L{\displaystyle {\mbox{FO}}\subsetneq {\mbox{L}}}Las reducciones de primer orden son reducciones más fuertes que las reducciones de espacio logarítmico .

Muchas clases de complejidad importantes son cerradas bajo reducciones de primer orden, y muchos de los problemas completos tradicionales también lo son (Immerman 1999, págs. 49-50). Por ejemplo, la conectividad ST es FO-completa para NL , y NL es cerrada bajo reducciones FO (Immerman 1999, pág. 51) (al igual que P , NP y la mayoría de las demás clases "bien comportadas").

Referencias

Lecturas relacionadas
6 articulos
Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...Reducción (complejidad)Reducción (complejidad)En la teoría de la computabilidad y la teoría de la complejidad computacional , una reducción es un algoritmo para transformar un problema en otro....Problema computacionalProblema computacionalEn informática teórica , un problema es aquel que pide una solución en términos de un algoritmo . Por ejemplo, el problema de factorizarTeoría de la complejidad computacionalEn la informática teórica y las matemáticas, la teoría de la complejidad computacional se centra en la clasificación de los problemas computacional...{\displaystyle E(x,y)}Teoría de la complejidad descriptivaLa complejidad descriptiva es una rama de la teoría de la complejidad computacional y de la teoría de modelos finitos que caracteriza las clases de...Lógica de primer ordenLa lógica de primer orden —también llamada lógica de predicados , cálculo de predicados , lógica cuantificacional— es una colección de sistemas for...