¡Más rápido que el navegador!
23 relaciones: Argumento de la diagonal de Cantor, Christos Papadimitriou, Clase de complejidad, Clases de complejidad P y NP, Cota superior asintótica, DTIME, EXPTIME, Función (matemática), Función computable, Juris Hartmanis, Máquina de Turing, Modelado numérico, NEXPTIME, NP (clase de complejidad), NTIME, P (clase de complejidad), Polinomio, Problema de decisión, PSPACE, Richard Stearns, Stephen Cook, Teoría de la complejidad computacional, Tesis de Cobham.
Argumento de la diagonal de Cantor
El argumento de la diagonal de Cantor, también conocido como método de la diagonal, es una argumentación o demostración matemática vislumbrada por Georg Cantor hacia 1891 para demostrar que el conjunto de los números reales no es numerable.
¡Nuevo!!: Teorema de la jerarquía temporal y Argumento de la diagonal de Cantor · Ver más »
Christos Papadimitriou
Christos Papadimitriou es un profesor de la división de ciencias de la computación en la Universidad de California, Berkeley.
¡Nuevo!!: Teorema de la jerarquía temporal y Christos Papadimitriou · 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!!: Teorema de la jerarquía temporal 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!!: Teorema de la jerarquía temporal y Clases de complejidad P y NP · 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!!: Teorema de la jerarquía temporal y Cota superior asintótica · 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!!: Teorema de la jerarquía temporal y DTIME · 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!!: Teorema de la jerarquía temporal y EXPTIME · Ver más »
Función (matemática)
En matemática, se dice que una magnitud es función de otra si el valor de la primera depende del valor de la segunda.
¡Nuevo!!: Teorema de la jerarquía temporal y Función (matemática) · Ver más »
Función computable
Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y son, específicamente, las funciones que pueden ser calculadas por una máquina de Turing.
¡Nuevo!!: Teorema de la jerarquía temporal y Función computable · Ver más »
Juris Hartmanis
Juris Hartmanis (Riga, 5 de julio de 1928-29 de julio de 2022) fue un prominente científico de la computación letón.
¡Nuevo!!: Teorema de la jerarquía temporal y Juris Hartmanis · 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!!: Teorema de la jerarquía temporal y Máquina de Turing · Ver más »
Modelado numérico
El modelado numérico (a veces llamado modelización numérica) es una técnica basada en el cálculo numérico, utilizada en muchos campos de estudio (ingeniería, ciencia, etc.) desde los años 60 para validar o refutar modelos conceptuales propuestos a partir de observaciones o derivados de teorías anteriores.
¡Nuevo!!: Teorema de la jerarquía temporal y Modelado numérico · 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!!: Teorema de la jerarquía temporal y NEXPTIME · 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!!: Teorema de la jerarquía temporal y NP (clase de complejidad) · 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!!: Teorema de la jerarquía temporal 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!!: Teorema de la jerarquía temporal 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!!: Teorema de la jerarquía temporal y Polinomio · 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!!: Teorema de la jerarquía temporal y Problema de decisión · 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!!: Teorema de la jerarquía temporal y PSPACE · Ver más »
Richard Stearns
Richard Edwin Stearns, nacido el 5 de julio de 1936, es un prominente científico de la computación.
¡Nuevo!!: Teorema de la jerarquía temporal y Richard Stearns · Ver más »
Stephen Cook
Stephen Arthur Cook (1939, Búfalo (Nueva York)) es un reconocido científico de la computación.
¡Nuevo!!: Teorema de la jerarquía temporal y Stephen Cook · 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!!: Teorema de la jerarquía temporal y Teoría de la complejidad computacional · Ver más »
Tesis de Cobham
En ciencias de la computación, la tesis de Cobham, también conocida como la tesis de Cobham-Edmonds (llamada así por Alan Cobham y Jack Edmonds) afirma que los problemas tratables o "fácilmente computables" son los problemas computables en tiempo polinómico.
¡Nuevo!!: Teorema de la jerarquía temporal y Tesis de Cobham · Ver más »
Redirecciona aquí:
Teorema de la jerarquia temporal.
