PSPACE

I matematikk og informatikk er PSPACE ei kompleksitetsklasse. Den kan defineres som mengda av alle problemer som kan løses av ei turingmaskin med en polynomiell mengde plass.


== Relasjoner til andre kompleksitetsklasser ==
Følgende relasjoner er kjente mellom PSPACE og andre kompleksitetsklasser.  Merk at ⊊ ikke er det samme som ⊈. ⊊ er ekte delmengde relasjonen. ⊆ er delmengderelasjonen.

  
    
      
        
          
            
              
                
                  
                    N
                    L
                    ⊆
                    P
                    ⊆
                    N
                    P
                    ⊆
                    P
                    H
                    ⊆
                    P
                    S
                    P
                    A
                    C
                    E
                  
                
              
            
            
              
                
                  
                    P
                    S
                    P
                    A
                    C
                    E
                    ⊆
                    E
                    X
                    P
                    T
                    I
                    M
                    E
                    ⊆
                    E
                    X
                    P
                    S
                    P
                    A
                    C
                    E
                  
                
              
            
            
              
                
                  
                    N
                    L
                    ⊊
                    P
                    S
                    P
                    A
                    C
                    E
                    ⊊
                    E
                    X
                    P
                    S
                    P
                    A
                    C
                    E
                  
                
              
            
            
              
                
                  
                    P
                    ⊊
                    E
                    X
                    P
                    T
                    I
                    M
                    E
                  
                
              
            
          
        
      
    
    {\displaystyle {\begin{array}{l}{\mathsf {NL\subseteq P\subseteq NP\subseteq PH\subseteq PSPACE}}\\{\mathsf {PSPACE\subseteq EXPTIME\subseteq EXPSPACE}}\\{\mathsf {NL\subsetneq PSPACE\subsetneq EXPSPACE}}\\{\mathsf {P\subsetneq EXPTIME}}\end{array}}}
  
Inneholdt i PSPACE har man også PSPACE-komplette problemer som er de hardeste problemene i PSPACE. De er definert som ved andre kompleksitetsklasser.


== Egenskaper ==
PSPACE er lukka under operasjonene union, komplement og kleenestjerne.
En annen interessant egenskap er at komplementet av PSPACE er lik PSPACE selv. Med andre ord er co-PSPACE = PSPACE.


== Litteratur ==
Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), ss. 281–294.