¡Más rápido que el navegador!
49 relaciones: Algoritmo de aproximación, Análisis de algoritmos, Cambridge University Press, Clase de complejidad, Clases de complejidad P y NP, Combinatoria, Complejidad de Kolmogórov, Computación cuántica, Computadora, Computers and Intractability: A Guide to the Theory of NP-Completeness, Cota superior asintótica, David S. Johnson, DSPACE, DTIME, EXPSPACE, EXPTIME, Heurística, Introducción a los algoritmos, Jack Edmonds, L (clase de complejidad), Leonid Levin, Máquina de Turing, Metaheurística, Michael Garey, MIT Press, Modelo de computación, NEXPTIME, NL (clase de complejidad), NP (clase de complejidad), NP-completo, NSPACE, NTIME, P (clase de complejidad), Polinomio, PP (clase de complejidad), Problema computacional, PSPACE, Reducción (complejidad), Richard Karp, Stephen Cook, Teoría de grafos, Teoría de la computabilidad, Teoría de la computación, Teorema de Cook, Teorema de la jerarquía temporal, Tesis de Church-Turing, Tiempo de ejecución, Transformación polinómica, Veintiún problemas NP-completos de Karp.
Algoritmo de aproximación
En ciencias de la computación e investigación de operaciones, un algoritmo de aproximación es un algoritmo usado para encontrar soluciones aproximadas a problemas de optimización.
¡Nuevo!!: Teoría de la complejidad computacional y Algoritmo de aproximación · Ver más »
Análisis de algoritmos
El término análisis de algoritmos fue acuñado por Donald Knuth y se refiere al proceso de encontrar la complejidad computacional de un algoritmo que resuelva un problema computacional dado, con el objetivo de proveer estimaciones teóricas de los recursos que necesita.
¡Nuevo!!: Teoría de la complejidad computacional y Análisis de algoritmos · Ver más »
Cambridge University Press
Cambridge University Press (conocida en inglés coloquialmente como CUP) es una editorial que recibió su Royal Charter de la mano de Enrique VIII en 1534, y es considerada una de las dos editoriales privilegiadas de Inglaterra (la otra es la Oxford University Press).
¡Nuevo!!: Teoría de la complejidad computacional y Cambridge University Press · Ver más »
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!!: Teoría de la complejidad computacional y Clase de complejidad · Ver más »
Clases de complejidad P y NP
La relación entre las clases de complejidad NP y P es una pregunta por primera vez formulada por el científico computacional Stephen Cook que la teoría de la complejidad computacional aún no ha podido responder.
¡Nuevo!!: Teoría de la complejidad computacional y Clases de complejidad P y NP · Ver más »
Combinatoria
La combinatoria es una rama de la matemática perteneciente al área de matemáticas discretas que estudia la enumeración, construcción y existencia de propiedades de configuraciones que satisfacen ciertas condiciones establecidas.
¡Nuevo!!: Teoría de la complejidad computacional y Combinatoria · Ver más »
Complejidad de Kolmogórov
En la teoría de la computación, la complejidad de Kolmogórov es el tamaño o cantidad de información del programa de computadora más corto que produce cierto resultado.
¡Nuevo!!: Teoría de la complejidad computacional y Complejidad de Kolmogórov · Ver más »
Computación cuántica
La computación cuántica o informática cuántica es un paradigma de computación distinto al de la informática clásica.
¡Nuevo!!: Teoría de la complejidad computacional y Computación cuántica · Ver más »
Computadora
Computadora, computador u ordenador es una máquina electrónica digital programable que ejecuta una serie de comandos para procesar los datos de entrada, obteniendo convenientemente información que posteriormente se envía a las unidades de salida.
¡Nuevo!!: Teoría de la complejidad computacional y Computadora · Ver más »
Computers and Intractability: A Guide to the Theory of NP-Completeness
En ciencias de la computación, más específicamente en el área de complejidad computacional, Computers and Intractability: A Guide to the Theory of NP-Completeness es un influyente libro de texto escrito por Michael Garey y David S. Johnson.
¡Nuevo!!: Teoría de la complejidad computacional y Computers and Intractability: A Guide to the Theory of NP-Completeness · Ver más »
Cota superior asintótica
En análisis de algoritmos, una cota superior asintótica es una función que sirve de cota superior de otra función cuando el argumento tiende a infinito.
¡Nuevo!!: Teoría de la complejidad computacional y Cota superior asintótica · Ver más »
David S. Johnson
David Stifler Johnson (Washington D.esdC., 9 de diciembre de 1945 - 8 de marzo de 2016) fue un informático teórico especialista en algoritmos y optimización.
¡Nuevo!!: Teoría de la complejidad computacional y David S. Johnson · Ver más »
DSPACE
En teoría de la complejidad computacional, la clase de complejidad DSPACE(f(n)) o SPACE(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en espacio O(f(n)) y tiempo ilimitado.
¡Nuevo!!: Teoría de la complejidad computacional y DSPACE · Ver más »
DTIME
En teoría de la complejidad computacional, la clase de complejidad DTIME(f(n)) (también llamada TIME(f(n))) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(f(n)), y espacio ilimitado.
¡Nuevo!!: Teoría de la complejidad computacional y DTIME · Ver más »
EXPSPACE
En teoría de la complejidad computacional, la clase de complejidad EXPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos con una máquina de Turing determinista en espacio O(2p(n)), donde p(n) es una función polinomial sobre n. De acuerdo con el Teorema de Savitch, esta clase es igual a la que considera máquinas de Turing no deterministas.
¡Nuevo!!: Teoría de la complejidad computacional y EXPSPACE · Ver más »
EXPTIME
En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2p(n)), donde p(n) es una función polinomial sobre n. En términos de DTIME, Se sabe que y por el teorema de la jerarquía temporal: de manera que al menos una de las inclusiones de la primera línea debe ser estricta (se piensa que todas esas inclusiones son estrictas).
¡Nuevo!!: Teoría de la complejidad computacional y EXPTIME · Ver más »
Heurística
La heurística (del griego εὑρίσκειν), que significa «hallar, inventar» (el pretérito perfecto de este verbo es eureka), aparece en más de una categoría gramatical.
¡Nuevo!!: Teoría de la complejidad computacional y Heurística · Ver más »
Introducción a los algoritmos
Introducción a los algoritmos (Introduction to Algorithms en versión original) es un libro de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein.
¡Nuevo!!: Teoría de la complejidad computacional e Introducción a los algoritmos · Ver más »
Jack Edmonds
Jack R. Edmonds (1934) es un matemático canadiense, considerado uno de los más importantes contribuyentes al campo de la optimización combinatoria y recibió en 1985 el John von Neumann Theory Prize.
¡Nuevo!!: Teoría de la complejidad computacional y Jack Edmonds · Ver más »
L (clase de complejidad)
En teoría de la complejidad computacional, la clase de complejidad L (LSPACE o espacio logarítmico determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, por una máquina de Turing determinista tal que la solución si existe es única.
¡Nuevo!!: Teoría de la complejidad computacional y L (clase de complejidad) · Ver más »
Leonid Levin
Leonid Anatólievich Levin Леонид Анатольевич Левин (nació el 2 de noviembre de 1948 en la antigua URSS).
¡Nuevo!!: Teoría de la complejidad computacional y Leonid Levin · 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!!: Teoría de la complejidad computacional y Máquina de Turing · Ver más »
Metaheurística
Una metaheurística es un método heurístico para resolver un tipo de problema computacional general, usando los parámetros dados por el usuario sobre unos procedimientos genéricos y abstractos de una manera que se espera eficiente.
¡Nuevo!!: Teoría de la complejidad computacional y Metaheurística · Ver más »
Michael Garey
Michael Randolph Garey es un informático teórico estadounidense, coautor (junto a David S. Johnson) del famoso libro de texto Computers and Intractability: A Guide to the Theory of NP-Completeness.
¡Nuevo!!: Teoría de la complejidad computacional y Michael Garey · Ver más »
MIT Press
MIT Press es una editorial universitaria afiliada a Instituto Tecnológico de Massachusetts (MIT).
¡Nuevo!!: Teoría de la complejidad computacional y MIT Press · Ver más »
Modelo de computación
En la teoría de la computabilidad y en la teoría de la complejidad computacional, un modelo de computación es la definición un conjunto de operaciones permitibles usadas en el cómputo y sus respectivos costos.
¡Nuevo!!: Teoría de la complejidad computacional y Modelo de computación · Ver más »
NEXPTIME
En teoría de la complejidad computacional, la clase de complejidad NEXPTIME es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en tiempo O(2p(n)), donde p(n) es una función polinomial sobre n. En función de NTIME, Categoría:Clases de complejidad.
¡Nuevo!!: Teoría de la complejidad computacional y NEXPTIME · Ver más »
NL (clase de complejidad)
En teoría de la complejidad computacional, la clase de complejidad NL (espacio logarítmico no determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, por una máquina de Turing no determinista tal que la solución, si existe, es única.
¡Nuevo!!: Teoría de la complejidad computacional y NL (clase de complejidad) · 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!!: Teoría de la complejidad computacional 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!!: Teoría de la complejidad computacional y NP-completo · Ver más »
NSPACE
En teoría de la complejidad computacional, la clase de complejidad NSPACE(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en espacio O(f(n)) y tiempo ilimitado.
¡Nuevo!!: Teoría de la complejidad computacional y NSPACE · Ver más »
NTIME
En teoría de la complejidad computacional, la clase de complejidad NTIME(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en tiempo O(f(n)) y espacio ilimitado.
¡Nuevo!!: Teoría de la complejidad computacional y NTIME · Ver más »
P (clase de complejidad)
En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor o igual que un cierto valor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico o polinomial P. La tesis de Cobham postula que la clase P es la que tiene los problemas tratables más grandes, es decir, los problemas de gran tamaño que se pueden calcular de forma eficiente con un ordenador.
¡Nuevo!!: Teoría de la complejidad computacional y P (clase de complejidad) · Ver más »
Polinomio
En matemáticas, polinomio (del latín: polynomium, y este del griego: πολυς, polys, ‘muchos’ y νόμος, nómos, ‘regla’, ‘prescripción’, ‘distribución’) es una expresión algebraica formada por la suma de varios monomios o términos, cada uno de los cuales es el producto de.
¡Nuevo!!: Teoría de la complejidad computacional y Polinomio · Ver más »
PP (clase de complejidad)
En teoría de la complejidad computacional PP, que quiere decir tiempo polinomial probabilístico, es una clase de problema de decisión resoluble por una máquina de Turing probabilística (diferente de la máquina de Turing general o determinista, en que las transiciones entre estados tienen la misma probabilidad de ocurrencia) con un error de probabilidad de menos de 1/2 para todas las instancias.
¡Nuevo!!: Teoría de la complejidad computacional y PP (clase de complejidad) · Ver más »
Problema computacional
En ciencia computacional teórica, un problema computacional o problema abstracto es una relación entre un conjunto de instancias y un conjunto de soluciones.
¡Nuevo!!: Teoría de la complejidad computacional y Problema computacional · Ver más »
PSPACE
En teoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio de polinomios (S(n).
¡Nuevo!!: Teoría de la complejidad computacional y PSPACE · Ver más »
Reducción (complejidad)
En teoría de la computación y teoría de la complejidad computacional, una reducción es una transformación de un problema a otro problema.
¡Nuevo!!: Teoría de la complejidad computacional y Reducción (complejidad) · Ver más »
Richard Karp
Richard Manning Karp (Boston, (Estados Unidos), 3 de enero de 1935) es un científico de la computación, conocido por su investigación en teoría de algoritmos, por lo que recibió el Premio Turing en 1985, el premio del Instituto Franklin en 2004 y el Premio Kioto en 2008.
¡Nuevo!!: Teoría de la complejidad computacional y Richard Karp · Ver más »
Stephen Cook
Stephen Arthur Cook (1939, Búfalo (Nueva York)) es un reconocido científico de la computación.
¡Nuevo!!: Teoría de la complejidad computacional y Stephen Cook · Ver más »
Teoría de grafos
La teoría de grafos, también llamada teoría de gráficas, es una rama de la matemática y las ciencias de la computación que estudia las propiedades de los grafos.
¡Nuevo!!: Teoría de la complejidad computacional y Teoría de grafos · Ver más »
Teoría de la computabilidad
La teoría de la computabilidad o teoría de la recursión es la parte de la computación que estudia los problemas de decisión que se pueden resolver con un algoritmo o equivalentemente con una máquina de Turing.
¡Nuevo!!: Teoría de la complejidad computacional y Teoría de la computabilidad · Ver más »
Teoría de la computación
La teoría de la computación o teoría de la informática es un conjunto de conocimientos racionales y sistematizados que se centran en el estudio de la abstracción de los procesos, con el fin de reproducirlos con ayuda de sistemas formales; es decir, a través de símbolos y reglas lógicas.
¡Nuevo!!: Teoría de la complejidad computacional y Teoría de la computación · Ver más »
Teorema de Cook
En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente: Cook demostró este teorema en su artículo de 1971 "The Complexity of Theorem Proving Procedures".
¡Nuevo!!: Teoría de la complejidad computacional y Teorema de Cook · Ver más »
Teorema de la jerarquía temporal
En la teoría de complejidad computacional, los teoremas de jerarquía temporal son declaraciones importantes sobre cómputo de tiempo acotado en máquinas de Turing.
¡Nuevo!!: Teoría de la complejidad computacional y Teorema de la jerarquía temporal · Ver más »
Tesis de Church-Turing
En teoría de la computabilidad, la tesis de Church-Turing formula hipotéticamente la equivalencia entre los conceptos de función computable y máquina de Turing, que expresado en lenguaje corriente vendría a ser "todo algoritmo es equivalente a una máquina de Turing".
¡Nuevo!!: Teoría de la complejidad computacional y Tesis de Church-Turing · Ver más »
Tiempo de ejecución
Se denomina tiempo de ejecución (runtime en inglés) al intervalo de tiempo en el que un programa de computadora se ejecuta en un sistema operativo.
¡Nuevo!!: Teoría de la complejidad computacional y Tiempo de ejecución · Ver más »
Transformación polinómica
En complejidad computacional, una transformación polinómica, reducción polinómica o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza inmediatamente, y a través de un tiempo polinómico, la existencia de un algoritmo que resuelve el segundo.
¡Nuevo!!: Teoría de la complejidad computacional y Transformación polinómica · Ver más »
Veintiún problemas NP-completos de Karp
En teoría de complejidad computacional, los veintiún (21) problemas NP-completos de Karp son un conjunto de problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos y que cumplen la característica en común de que todos ellos pertenecen a la clase de complejidad de los NP-completos.
¡Nuevo!!: Teoría de la complejidad computacional y Veintiún problemas NP-completos de Karp · Ver más »
Redirecciona aquí:
Complejidad Computacional, Complejidad algoritmica, Complejidad algorítmica, Complejidad computacional, Complejidad de algoritmo, Problema tratable, Problemas tratables, Teoria de la complejidad computacional, Teoría de complejidad computacional, Teoría de la complejidad informática.
