PSPACE-completo: differenze tra le versioni

Versione delle 09:42, 16 mag 2023

Versione delle 09:42, 16 mag 2023

Riga 1:

{{Richiesta revisione bozza|ts=20230509203154|esito=|utente=}}

{{Richiesta revisione bozza|ts=20230508014205|esito=Descrizione confusa (l'incipit sembra incompleto e comunque non ha molto senso dal punto di vista matematico scritto in quel modo)|utente=Superspritz}}

{{Bozza|arg=matematica|arg2=informatica|ts=20230508013715}}

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 la [[classe di complessità]] computazionale che rappresenta i problemi decisionali che sono almeno altrettanto difficili dei problemi più difficili in [[PSPACE]].

Line 42 ⟶ 38:

{{Portale|Informatica|Matematica}}

{{Categorie bozza|

[[Categoria:Classi di complessità]]

}}