PSPACE-completo: differenze tra le versioni

Versione delle 10:03, 16 mag 2023

Versione delle 01:02, 15 feb 2024

Riga 1:

{{W|informatica|maggio 2023|mancano i template di citazione, con una nota inserita semplicemente come url, e le formule matematiche (al momento la notazione è inserita con il corsivo)}}

InNella [[teoria della complessità computazionale]], un problema decisionale è detto '''PSPACE-completo''' quando gli [[Algoritmo|algoritmi]] che lo risolvono richiedono al minimo una quantità di [[Memoria (informatica)|memoria]] [[Polinomio|polinomiale]] rispetto alla dimensione dell'[[input]] e quando tutti i problemi risolti con memoria polinomiale possono essere [[Riduzione (informatica)|ridotti]] ad esso in tempo polinomiale.

PSPACE-completo corrisponde alla [[classe di complessità]] computazionale che rappresenta i problemi decisionali che sono almeno altrettanto difficili dei problemi più difficili in [[PSPACE]].

== Definizione ==

Un problema decisionale ''A'' è definito PSPACE-completo se:

Riga 12:

Un problema è quindi 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 tanta memoria 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>.

== Proprietà ==

La classe PSPACE-completo è una sottoclasse della classe PSPACE, che rappresenta tutti i problemi decisionali che possono essere risolti da una [[macchina di Turing]] deterministica che utilizza una quantità di spazio polinomiale rispetto alla dimensione dell'input. I problemi PSPACE-completi comprendono alcuni dei problemi più difficili in PSPACE. La definizione di PSPACE-completo è stata introdotta da [[Stephen Cook]] nel 1971, e da allora ha avuto un ruolo fondamentale nella teoria della complessità computazionale, in particolare nell'ambito della dimostrazione di limiti inferiori per la complessità dei problemi computazionali.

Riga 24:

Il problema QBF è un'estensione del problema della [[soddisfacibilità booleana]] (SAT). Mentre SAT chiede se esiste un assegnamento di valori di verità per le variabili booleane che rende vera una formula booleana, QBF generalizza questo problema aggiungendo [[Quantificatore|quantificatori]] universali ed esistenziali alle variabili booleane. Si è dimostrato che QBF è PSPACE-completo.<ref>Stockmeyer, L., & Meyer, A. (1973). ''Word problems requiring exponential time'' (Technical Report). MIT.</ref>

=== Il gioco di Hex ===

''[[Hex (gioco)|Hex]]'' è un gioco di strategia su una griglia esagonale che è stato dimostrato essere PSPACE-completo. Il problema decisionale associato è determinare se il giocatore che muove per primo ha una strategia vincente.<ref>Reisch, S. (1981). ''Hex ist PSPACE-vollständig''. Acta Informatica, 15(2), 167-191.</ref>

Riga 35:

Il gioco ''[[Sokoban]]'', in cui un omino deve spostare casse verso una posizione indicata, è PSPACE-completo.<ref>https://www.semanticscholar.org/paper/Sokoban-is-PSPACE-complete-Culberson/7a73f74c2943e5aafef364735302a36ee2f17b26</ref>

== Note ==

<references />