22 relaciones: Ajedrez, Algoritmo, Clase de complejidad, Cota superior asintótica, Damas, DTIME, EXPSPACE, Go, Juego generalizado, Máquina de Turing, NP (clase de complejidad), P (clase de complejidad), Problema de decisión, Problema de la parada, PSPACE, PSPACE-completo, Solubilidad, Subconjunto, Teoría de la complejidad computacional, Teoría de la computabilidad, Teorema de la jerarquía temporal, Transformación polinómica.
Ajedrez
El ajedrez es un juego de tablero entre dos contrincantes en el que cada uno dispone al inicio de dieciséis piezas móviles, desiguales en importancia y valor, que se desplazan sobre un tablero capturando piezas del jugador contrario, según ciertas reglas.
¡Nuevo!!: EXPTIME y Ajedrez · Ver más »
Algoritmo
En matemáticas, lógica, ciencias de la computación y disciplinas relacionadas, un algoritmo (probablemente del latín tardío algorithmus, y este del árabe clásico ḥisābu lḡubār, que significa «cálculo mediante cifras arábigas») es un conjunto de instrucciones o reglas definidas y no-ambiguas, ordenadas y finitas que permite, típicamente, solucionar un problema, realizar un cómputo, procesar datos y llevar a cabo otras tareas o actividades.
¡Nuevo!!: EXPTIME y Algoritmo · 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!!: EXPTIME y Clase de complejidad · 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!!: EXPTIME y Cota superior asintótica · Ver más »
Damas
Las damas es un juego de mesa para dos jugadores.
¡Nuevo!!: EXPTIME y Damas · 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!!: EXPTIME 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!!: EXPTIME y EXPSPACE · Ver más »
Go
El go (围棋 —wéiqí— en chino) (囲碁 —igo— en japonés) (바둑 —baduk— en coreano) (cờ vây en vietnamita) es un juego de tablero de estrategia para dos personas.
¡Nuevo!!: EXPTIME y Go · Ver más »
Juego generalizado
En la teoría de la complejidad computacional, un juego generalizado es un juego o rompecabezas que se ha generalizado para que se pueda jugar en un tablero o cuadrícula de cualquier tamaño.
¡Nuevo!!: EXPTIME y Juego generalizado · 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!!: EXPTIME 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!!: EXPTIME y NP (clase de complejidad) · 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!!: EXPTIME y P (clase de complejidad) · 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!!: EXPTIME 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!!: EXPTIME y Problema de la parada · 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!!: EXPTIME y PSPACE · Ver más »
PSPACE-completo
En teoría de la complejidad computacional, la clase de complejidad PSPACE-completo (PSPACE-complete en inglés) es el subconjunto de los problemas de decisión en PSPACE y todo problema en PSPACE puede ser reducido a él en tiempo polinomial.
¡Nuevo!!: EXPTIME y PSPACE-completo · Ver más »
Solubilidad
La solubilidad es la capacidad de una sustancia de disolverse en otra llamada disolvente.
¡Nuevo!!: EXPTIME y Solubilidad · Ver más »
Subconjunto
es subconjunto de otro conjunto si todos los elementos de pertenecen también a. Decimos entonces que «está contenido» dentro de.
¡Nuevo!!: EXPTIME y Subconjunto · 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!!: EXPTIME y Teoría de la complejidad computacional · 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!!: EXPTIME y Teoría de la computabilidad · 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!!: EXPTIME y Teorema de la jerarquía temporal · 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!!: EXPTIME y Transformación polinómica · Ver más »