PSPACE-completo: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
←Nuova pagina: {{Bozza}} Il '''PSPACE-completo''' è una classe di complessità computazionale che rappresenta i problemi decisionali che richiedono al massimo una quantità di memoria polinomiale rispetto alla dimensione dell'input e che sono almeno altrettanto difficili, dal punto di vista della complessità computazionale, dei problemi più difficili in PSPACE. Un problema è definito PSPACE-completo se appartiene a PSPACE e se ogni problema in PSPACE si riduce ad ess... |
m Bot: sistemo template bozza |
||
Riga 1:
{{Bozza|arg=|arg2=|ts=20230508013715}}
Il '''PSPACE-completo''' è una [[classe di complessità]] computazionale che rappresenta i problemi decisionali che richiedono al massimo una quantità di memoria polinomiale rispetto alla dimensione dell'input e che sono almeno altrettanto difficili, dal punto di vista della complessità computazionale, dei problemi più difficili in [[PSPACE]]. Un problema è definito PSPACE-completo se appartiene a PSPACE e se ogni problema in PSPACE si riduce ad esso in tempo polinomiale. Questa classe è una sottoclasse della classe PSPACE.<ref>Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). ''Introduction to Automata Theory, Languages, and Computation'' (3rd ed.). Addison-Wesley.</ref>
| |||