PSPACEvolledig

PSPACEvolledig (PSPACE-complete in het Engels) is een classificatie voor beslissingsproblemen in de theoretische computerwetenschap. Een probleem is PSPACEvolledig als het twee hoofdkenmerken heeft: het ligt in de klasse PSPACE en het is PSPACE-hard. Een probleem ligt in PSPACE als er een procedure bestaat die in polynomiale ruimte kan bepalen of een invoer ja of nee is, los van de tijdsduur. Een probleem is PSPACE-hard als elk probleem in PSPACE polynomiale tijd kan worden gereduceerd tot het probleem via polynomiale-tijds reducties. Samengevat: PSPACEvolledig betekent dat het probleem de “zwaarste” problemen in PSPACE vertegenwoordigt.

Het canonieke PSPACEvolledige probleem is QBF (Quantified Boolean Formula). Dit betreft de evaluatie van voor alle en er bestaan-kwantoren in Booleaanse formules en is beslissingsproblematiek: of een gegeven kwantificatie-formule waar is. Naast QBF bestaan er andere PSPACEvolledige problemen, zoals Generalized Geography, en bepaalde beslissingsproblemen uit planning en combinatorische spellen. Dergelijke problemen demonstreren hoe PSPACEvolledige problemen vaak logica- of spelmechanismen modelleren waarbij het oplossingsproces lang kan doorgaan met beperkte geheugenruimte.

Relaties met andere klassen: PSPACE bevat P en NP, maar de exacte scheiding tussen deze klassen is onbekend. Volgens de standaard-relaties geldt P ⊆ NP ⊆ PSPACE ⊆ EXPTIME. Volgens Savitch’s theorem vallen NPSPACE en PSPACE samen, wat betekent dat niet-deterministische en deterministische polyruimtecomputers evenveel kunnen verwerken in termen van geheugen. Het concept van PSPACEvolledigheid is daarmee een centrale maatstaf voor de moeilijkheidsgraad binnen PSPACE en dient als referentiepunt bij het vergelijken van problemen in de complexiteitstheorie.