PSPACE-completo: differenze tra le versioni

Versione delle 09:42, 16 mag 2023

Versione delle 09:44, 16 mag 2023

Riga 1:

In [[teoria della complessità computazionale]], un problema decisionale è detto '''PSPACE-completo''' quando gli [[Algoritmo|algoritmi]] che lo risolvono richiedono al massimo una quantità di [[Memoria (informatica)|memoria]] [[Polinomio|polinomiale]] rispetto alla dimensione dell'[[input]]. Si chiama PSPACE-completo lacorrisponde alla [[classe di complessità]] computazionale che rappresenta i problemi decisionali che sono almeno altrettanto difficili dei problemi più difficili in [[PSPACE]].

Un problema è quindi definito PSPACE-completo se appartiene a PSPACE e se ogni problema in PSPACE si riduce ad esso in tempo polinomiale. Questo significa che risolvere un problema PSPACE-completo richiede almeno tanto spazio quanto risolvere qualsiasi altro problema in PSPACE, e la sua difficoltà computazionale è tale da poter essere utilizzato per risolvere qualsiasi altro problema in PSPACE attraverso una trasformazione in tempo polinomiale.<ref>Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). ''Introduction to Automata Theory, Languages, and Computation'' (3rd ed.). Addison-Wesley.</ref>