¡Más rápido que el navegador!
11 relaciones: Clase de complejidad, Conjunto recursivamente enumerable, Función recursiva, Máquina de Turing, NP (clase de complejidad), NP-completo, NP-hard, Problema de decisión, Problema de la parada, R (clase de complejidad), Teoría de la complejidad computacional.
Clase de complejidad
En teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada.
¡Nuevo!!: RE (clase de complejidad) y Clase de complejidad · Ver más »
Conjunto recursivamente enumerable
En teoría de la computabilidad, un conjunto S de números naturales se denomina computablemente enumerable (ce), recursivamente enumerable (re), semidecidible, parcialmente decidible, enumerable, demostrable o Turing-reconocible si.
¡Nuevo!!: RE (clase de complejidad) y Conjunto recursivamente enumerable · Ver más »
Función recursiva
En lógica matemática y computación, las funciones recursivas o también conocidas como funciones recursivas-μ son una clase de funciones de los números naturales en los números naturales que son «computables» en un sentido intuitivo.
¡Nuevo!!: RE (clase de complejidad) y Función recursiva · Ver más »
Máquina de Turing
Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas.
¡Nuevo!!: RE (clase de complejidad) y Máquina de Turing · Ver más »
NP (clase de complejidad)
En teoría de la complejidad computacional, NP es el acrónimo en inglés de nondeterministic polynomial time ("tiempo polinomial no determinista").
¡Nuevo!!: RE (clase de complejidad) y NP (clase de complejidad) · Ver más »
NP-completo
En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo.
¡Nuevo!!: RE (clase de complejidad) y NP-completo · Ver más »
NP-hard
En teoría de la complejidad computacional, la clase de complejidad NP-hard (o NP-complejo, o NP-difícil) es el conjunto de los problemas de decisión que contiene los problemas H tales que todo problema L en NP puede ser transformado polinomialmente en H. Esta clase puede ser descrita como aquella que contiene a los problemas de decisión que son como mínimo tan difíciles como un problema de NP.
¡Nuevo!!: RE (clase de complejidad) y NP-hard · Ver más »
Problema de decisión
En teoría de la computación, un problema es un conjunto de frases de longitud finita que tienen asociadas frases resultantes también de longitud finita.
¡Nuevo!!: RE (clase de complejidad) y Problema de decisión · Ver más »
Problema de la parada
El problema de la parada o problema de la detención para máquinas de Turing consiste en lo siguiente: dada una Máquina de Turing M y una palabra w, determinar si M terminará en un número finito de pasos cuando es ejecutada usando w como dato de entrada.
¡Nuevo!!: RE (clase de complejidad) y Problema de la parada · Ver más »
R (clase de complejidad)
En complejidad computacional, R es la clase conformada por los problemas de decisión resolubles por una máquina de Turing, vale decir, el conjunto de todos los lenguajes recursivos.
¡Nuevo!!: RE (clase de complejidad) y R (clase de complejidad) · Ver más »
Teoría de la complejidad computacional
La teoría de la complejidad computacional o teoría de la complejidad informática es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clases de complejidad.
¡Nuevo!!: RE (clase de complejidad) y Teoría de la complejidad computacional · Ver más »
