Metraipolis › archive › dc_e1b5ffeb6702
EXPTIME — Wikipedia
- Source
- Wikipedia (it)
- Original
- https://it.wikipedia.org/wiki/EXPTIME
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-03T13:55:02.789Z
- SHA-256 of the archived text
1ab8dbe51b0274a1707be5e7f015c368fa5c7e9a6af664ecc7c0f7a0bb893a75- Stable URL of this page
https://metraipolis.com/documento/dc_e1b5ffeb6702
How to cite
EXPTIME — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/EXPTIME (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_e1b5ffeb6702 (Metraipolis archive dc_e1b5ffeb6702, sha256 1ab8dbe51b0274a1707be5e7f015c368fa5c7e9a6af664ecc7c0f7a0bb893a75)
BibTeX
@misc{dce1b5ffeb6702,
title = {EXPTIME — Wikipedia},
howpublished = {Wikipedia (it)},
url = {https://it.wikipedia.org/wiki/EXPTIME},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_e1b5ffeb6702; sha256 1ab8dbe51b0274a1707be5e7f015c368fa5c7e9a6af664ecc7c0f7a0bb893a75},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/EXPTIME. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Nella teoria della complessità computazionale la classe di complessità EXPTIME (a volte chiamata EXP, da Exponential Time, "tempo esponenziale"), è l'insieme di tutti i problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(2p(n)), dove p(n) è una funzione polinomiale di n. In termini di DTIME, EXPTIME=⋃k∈ℕ DTIME (2nk). Sappiamo che P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE e inoltre, dal teorema della gerarchia temporale e dal teorema della gerarchia spaziale, che P ⊊ EXPTIME e NP ⊊ NEXPTIME e PSPACE ⊊ EXPSPACE così almeno una delle prime tre inclusioni e almeno una delle ultime tre inclusioni deve essere corretta, ma non si sa quali sono, anche se la maggior parte degli esperti crede che tutte le inclusioni siano corrette. Si sa anche che se P = NP, allora EXPTIME = NEXPTIME, la classe dei problemi risolvibili nel tempo esponenziale da una macchina di Turing non deterministica. Più precisamente, EXPTIME ≠ NEXPTIME se e solo se esistono linguaggi sparsi in NP che non sono in P. EXPTIME può anche essere riformulato come la classe di spazio APSPACE, i problemi che possono essere risolti da una macchina di Turing alternante nello spazio polinomiale. Questo è un modo di vedere che PSPACE ⊆ EXPTIME, poiché una macchina di Turing alternante è potente almeno quanto una macchina di Turing deterministica. EXPTIME è una classe in una gerarchia esponenziale di classi di complessità con limiti temporali sempre più alti. La classe 2-EXPTIME è definita similmente a EXPTIME, ma con un limite temporale doppiamente esponenziale 22n. Questo può essere generalizzato a limiti temporali sempre più alti. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico). Fonte: Wikipedia in italiano, voce «EXPTIME» — https://it.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://it.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 151593709, consultata il 2026-11-03T13:46:48.993Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: b0a467bd8c5588b02d1188b8ad0d6ee93c5e3362031ce7fb00f168dcb5474b62