Metraipolis › archive › dc_0648b7aea583

PSPACE — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/PSPACE
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-08T04:38:41.917Z
SHA-256 of the archived text
8c27f23001910f1c74e3d0a237e429631dcccb146497883e4cd9da04d8d55cf8
Stable URL of this page
https://metraipolis.com/documento/dc_0648b7aea583

How to cite

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

Archived text

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

Nella teoria della complessità computazionale, la classe di problemi PSPACE, che sta per polynomial space, è l'insieme di tutti i problemi che possono essere risolti da una macchina di Turing deterministica usando una quantità di memoria di O(nk), dove n è la dimensione dei dati di input e k è un qualsiasi valore finito. In altre parole, PSPACE include quei problemi che possono essere risolti da un algoritmo che utilizzi uno spazio di memoria la cui dimensione sia al più funzione polinomiale della dimensione dell'input.

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 «PSPACE» — https://it.wikipedia.org/wiki/PSPACE
Wikidata Q500716: «classe di complessità» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q500716
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/PSPACE?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 144340676, consultata il 2026-11-08T04:35:01.986Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 0beb5de565da86e4f2773358517038bf065489037368534e94b8950b1d7c9620