Metraipolis › archive › dc_8fe07d83642d

NEXPTIME — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/NEXPTIME
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-07T19:56:02.951Z
SHA-256 of the archived text
491db372f60970bb9df4b5328da512c14529b8737f8ffde46f5f57083041cfa9
Stable URL of this page
https://metraipolis.com/documento/dc_8fe07d83642d

How to cite

NEXPTIME — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/NEXPTIME (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_8fe07d83642d (Metraipolis archive dc_8fe07d83642d, sha256 491db372f60970bb9df4b5328da512c14529b8737f8ffde46f5f57083041cfa9)
BibTeX
@misc{dc8fe07d83642d,
  title = {NEXPTIME — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/NEXPTIME},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_8fe07d83642d; sha256 491db372f60970bb9df4b5328da512c14529b8737f8ffde46f5f57083041cfa9},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/NEXPTIME. 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à NEXPTIME (a volte detta NEXP) è l'insieme dei problemi decisionali risolvibili da una macchina di Turing non deterministica in tempo O(2p(n)), dove p(n) è una funzione polinomiale. In termini di NTIME, 𝖭𝖤𝖷𝖯𝖳𝖨𝖬𝖤=⋃k∈ℕ𝖭𝖳𝖨𝖬𝖤(2nk). Sappiamo che 𝖯⊆𝖭𝖯⊆𝖤𝖷𝖯𝖳𝖨𝖬𝖤⊆𝖭𝖤𝖷𝖯𝖳𝖨𝖬𝖤 e, per il teorema della gerarchia temporale, che 𝖭𝖯⊊𝖭𝖤𝖷𝖯𝖳𝖨𝖬𝖤. Se P = NP, allora NEXPTIME = EXPTIME (ragionamento di padding); più precisamente, E ≠ NE se e solo se esistono linguaggi sparsi in NP che non sono in P.

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 «NEXPTIME» — https://it.wikipedia.org/wiki/NEXPTIME
Wikidata Q1575791: «classe di complessità» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1575791
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/NEXPTIME?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 146625551, consultata il 2026-11-07T19:52:30.082Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 3c7ba9538edacf88586fbd78c24332847b6e0e4efdff287fbd8261b5dbf8e0a7