PSPACE-completo: differenze tra le versioni

Versione delle 09:44, 16 mag 2023

Versione attuale delle 01:04, 24 mag 2024

(4 versioni intermedie di 3 utenti non mostrate)

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 massimominimo una quantità di [[Memoria (informatica)|memoria]] [[Polinomio|polinomiale]] rispetto alla dimensione dell'[[input]]. PSPACE-completoe corrispondequando alla [[classe di complessità]] computazionale che rappresentatutti i problemi decisionalirisolti checon sonomemoria almenopolinomiale altrettantopossono difficiliessere dei[[Riduzione problemi(informatica)|ridotti]] piùad difficiliesso in [[PSPACE]]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]].

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>

== Definizione ==

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. 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.

==Definizione==

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

# ''A'' appartiene a PSPACE, cioè può essere risolto utilizzando una quantità di memoria polinomiale rispetto alla dimensione dell'input.

# Ogni problema ''B'' in PSPACE può essere ridotto ad ''A'' tramite una [[Riduzione (informatica)|riduzione]] in tempo polinomiale. Questo significa che esiste una funzione computabile ''f'', che può essere calcolata in tempo polinomiale, tale che per ogni input ''x'', ''B(x)'' è vero se e solo se ''A(f(x))'' è vero.<ref>Papadimitriou, C. H. (1994). ''Computational Complexity''. Addison-Wesley</ref>

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 tantotanta spaziomemoria 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 di problemi PSPACE-completicompleto è ununa sottoinsiemesottoclasse della classe PSPACE, che comprenderappresenta tutti i problemi risolvibilidecisionali inche possono essere risolti da una [[macchina di Turing]] deterministica che utilizza una quantità di spazio polinomiale rispetto alla dimensione dell'input. ComprendeI ancheproblemi PSPACE-completi comprendono alcuni dei problemi più difficili in PSPACE. SeLa undefinizione problemadi PSPACE-completo puòè esserestata risoltointrodotta in tempo polinomiale, allorada [[PStephen (complessità)|PCook]] = PSPACE.nel Tuttavia1971, la relazione tra P e PSPACEda rimaneallora apertaha eavuto nonun siruolo safondamentale senella Pteoria =della PSPACE.<ref>Fortnowcomplessità computazionale, L.in (2009).particolare nell''Theambito Statusdella ofdimostrazione thedi Plimiti Versusinferiori NPper Problem''.la Communicationscomplessità ofdei theproblemi ACM, 52(9), 78-86computazionali.</ref>

Se un problema PSPACE-completo può essere risolto in tempo polinomiale, allora [[P (complessità)|P]] = PSPACE. Tuttavia, la relazione tra P e PSPACE rimane aperta e non si sa se P = PSPACE.<ref>Fortnow, L. (2009). ''The Status of the P Versus NP Problem''. Communications of the ACM, 52(9), 78-86.</ref>

== Esempi di problemi PSPACE-completi ==

Line 22 ⟶ 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>

=== Il problema delle mosse valide nel gioco di Reversi ===

Il problema decisionale delle mosse valide in ''[[Othello (gioco)|Othello]]'' o ''Reversi'', un gioco da tavolo che coinvolge due giocatori che si alternano a posizionare dischi su una griglia, è stato dimostrato essere PSPACE-completo.<ref>Robson, J. M. (1983). ''The complexity of Go''. In IFIP Congress (pp. 413-417).</ref>

=== Sokoban ===

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 />

== Voci correlate ==

* [[NP-completo]]

* [[Classe di complessità]]

{{Classi di complessità}}