Metraipolis › archive › dc_67f182c49d89

EXPTIME — Wikipedia (es)

Source
Wikipedia (es)
Original
https://es.wikipedia.org/wiki/EXPTIME
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-06T07:22:25.317Z
SHA-256 of the archived text
1bd62091162cbdacc700cce5eff0dc0a5c378e93238441dff0de0779fc054200
Stable URL of this page
https://metraipolis.com/documento/dc_67f182c49d89

How to cite

EXPTIME — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/EXPTIME (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_67f182c49d89 (Metraipolis archive dc_67f182c49d89, sha256 1bd62091162cbdacc700cce5eff0dc0a5c378e93238441dff0de0779fc054200)
BibTeX
@misc{dc67f182c49d89,
  title = {EXPTIME — Wikipedia (es)},
  howpublished = {Wikipedia (es)},
  url = {https://es.wikipedia.org/wiki/EXPTIME},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_67f182c49d89; sha256 1bd62091162cbdacc700cce5eff0dc0a5c378e93238441dff0de0779fc054200},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/EXPTIME. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

En teoría de la complejidad computacional, la clase de complejidad EXPTIME, también denotada como EXP, incluye el conjunto de problemas de decisión que pueden resolverse mediante una máquina de Turing determinista en un tiempo acotado por una función exponencial. Específicamente, un problema pertenece a EXPTIME si existe un algoritmo que lo resuelve en tiempo O(2p(n)), donde p(n) es una función polinomial del tamaño de la entrada n. Esta clase contiene problemas que requieren una cantidad de tiempo exponencial en el peor caso, lo que los hace computacionalmente intratables para entradas grandes. EXPTIME incluye a clases como P y NP, aunque no se ha demostrado formalmente si estas inclusiones son estrictas. También se sabe que EXPTIME está contenida en EXPSPACE, y que contiene a PSPACE, es decir: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE Un ejemplo clásico de problema que pertenece a EXPTIME es el problema del juego generalizado del ajedrez, que se ha demostrado ser EXPTIME-completo bajo ciertas condiciones. EXPTIME es fundamental para el estudio de los límites de lo computacionalmente factible, especialmente en el diseño y análisis de algoritmos para problemas complejos o con alta carga combinatoria. En términos de DTIME, EXPTIME = ⋃ k ∈ N DTIME ( 2 n k ) . {\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{n^{k}}\right).} Se sabe que P ⊆ NP ⊆ PSPACE ⊆ 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.)

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in spagnolo, in ordine alfabetico).
Fonte: Wikipedia in spagnolo, voce «EXPTIME» — https://es.wikipedia.org/wiki/EXPTIME
Wikidata Q1276570: «insieme di problemi decisionali» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1276570
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/EXPTIME?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 170207469, consultata il 2026-11-06T04:37:11.311Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 133b5d8ab03f86256d38ac30603afa10bd6bdf1c72af0429876030cc10a5b0d6