EXPTIME

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,

\mbox{EXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}\left(2^{n^k}\right).

Se sabe que

PNPPSPACE ⊆ EXPTIME ⊆ EXPSPACE

y por el teorema de la jerarquía temporal:

P ⊂ EXPTIME

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).

La clase de complejidad EXPTIME-completo es el conjunto de problemas de decisión que están en EXPTIME tales que todo problema de EXPTIME tiene una transformación polinomial hacia cada uno de los problemas de EXPTIME-completo. Dicho de otra forma, existe un algoritmo que trabaja en tiempo polinómico que transforma las instancias de un problema en las instancias del otro con la misma respuesta. El conjunto EXPTIME-completo puede ser visto como el conjunto de los problemas más difíciles de EXPTIME.

Como ejemplos de problemas EXPTIME-completos están el buscar a partir de una posición (en una versión generalizada) del Ajedrez, Damas, o Go y determinar si el primer jugador tiene una secuencia de jugadas ganadora a partir de allí. Estos juegos son EXPTIME-completos dado que las secuencias de jugadas a partir de una configuración dada es exponencial sobre el tamaño del tablero. (Cuando se tiene un juego generalizado en el cual el número de jugadas a partir de una configuración es polinómico en el tamaño del tablero, el mismo problema resulta generalmente PSPACE-completo.)


EXPTIME-completo

Un problema de decisión es EXPTIME-completo si es en EXPTIME, y todos los problemas de EXPTIME tienen tiempo-polinomial, o una reducción de la misma. En otras palabras, hay un algoritmo de tiempo polinomico que transforma los casos de uno a instancias del otro con la misma respuesta. Se podria pensar que los problemas que son EXPTIME-completo son los problemas más difíciles en EXPTIME. Notese que aunque no sabemos si NP es un subconjunto de P o no, sí sabemos que los problemas EXPTIME-completo no están en P; se ha demostrado que estos problemas no pueden resolverse en tiempo polinomial.

En teoría de la computabilidad, uno de los problemas básicos no decidibles es el de decidir si una máquina de Turing determinista (DTM) se detiene(problema de la parada). Uno de los problemas más fundamentales EXPTIME-completo es una versión más sencilla de ello, que dice si un DTM detiene en a lo sumo k pasos. Es en EXPTIME porque obviamente una de simulación requiere O(k) tiempo, y la entrada k se codifica mediante O(log k) bits. Es EXPTIME-completo, ya que podemos usarlo para determinar si una máquina que resuelve un problema de EXPTIME acepta en forma exponencial el número de pasos; no va a usar más.

Otros ejemplos de problemas EXPTIME-completo incluyen el problema de evaluar una situación generalizada en el ajedrez, damas o Go (con las reglas japonesas ko). Estos juegos pueden ser EXPTIME-completo porque los juegos pueden durar de una serie de movimientos que es exponencial en el tamaño del tablero. En el ejemplo del Go, la regla japonesa del ko es lo suficientemente insoluble para implicar EXPTIME-completo, pero no se sabe si las más flexibles como las americanas o chinas son EXPTIME-completo.

Por el contrario, juegos generalizados que pueden durar una serie de movimientos que son polinomicos en el tamaño del tablero son a menudo PSPACE-completo.


Wikimedia foundation. 2010.

См. также в других словарях:

  • EXPTIME — EXP redirects here; for other uses, see exp. In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2 p ( n )) time, where p ( n… …   Wikipedia

  • EXPTIME — In der Komplexitätstheorie steht EXPTIME (manchmal auch nur EXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine in durch beschränkter Zeit entschieden werden können. ist dabei ein beliebiges… …   Deutsch Wikipedia

  • EXPTIME — Класс сложности EXPTIME В теории сложности вычислений, класс сложности EXPTIME (иногда называемый просто EXP) это множество задач, решаемых с помощью детерминированной машины Тьюринга за время O(2p(n)), где p(n) это полиномиальная функция от n.… …   Википедия

  • 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… …   Enciclopedia Universal

  • 2-EXPTIME — In computational complexity theory, the complexity class 2 EXPTIME (sometimes called 2 EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(22 p ( n )) time, where p ( n ) is a polynomial function of n .In… …   Wikipedia

  • Класс EXPTIME — В теории сложности вычислений, класс сложности EXPTIME (иногда называемый просто EXP) это множество задач, решаемых с помощью детерминированной машины Тьюринга за время O(2p(n)), где p(n) это полиномиальная функция о …   Википедия

  • Game complexity — Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state space complexity, game tree size, decision complexity, game tree complexity, and computational complexity. Contents 1 Measures of… …   Wikipedia

  • Complejidad en los juegos — Este artículo o sección sobre ocio necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 11 de junio de 2008. También puedes ayudar… …   Wikipedia Español

  • Lógica de descripción — Las lógicas de descripción, también llamadas lógicas descriptivas (DL por description logics) son una familia de lenguajes de representación del conocimiento que pueden ser usados para representar conocimiento terminológico de un dominio de… …   Wikipedia Español

  • 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. Informalmente, estos teoremas dicen que con más tiempo, una máquina de Turing puede …   Wikipedia Español


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»