|
gptkbp:instanceOf
|
gptkb:Complexity_class
|
|
gptkbp:abbreviation
|
gptkb:PSPACE
|
|
gptkbp:characterizedBy
|
Alternating polynomial time (AP = PSPACE)
Polynomial space Turing machine
Problems solvable with polynomial space
|
|
gptkbp:closure_property
|
gptkb:Kleene_star
gptkb:intersection
gptkb:Union
complement
|
|
gptkbp:complete_problem
|
gptkb:TQBF
|
|
gptkbp:contains
|
gptkb:IP
gptkb:MA
gptkb:AM
gptkb:QMA
gptkb:BPL
gptkb:co-NP
gptkb:PSPACE/poly
gptkb:QBF
gptkb:QIP
P
L
NL
NP
PH
PL
SL
RL
PSPACE-complete
PSPACE-hard
ZPL
NPSPACE
co-NL
PSPACE/log
QSPACE
co-L
|
|
gptkbp:definedIn
|
gptkb:Technical_Machine
|
|
gptkbp:equivalentTo
|
NPSPACE (by Savitch's theorem)
|
|
gptkbp:example
|
gptkb:QBF
gptkb:TQBF
Model checking
Games with perfect information
Generalized geography
Word problem for linear bounded automata
|
|
gptkbp:hasWikipediaPage
|
https://en.wikipedia.org/wiki/PSPACE
|
|
gptkbp:introduced
|
1970s
|
|
gptkbp:namedAfter
|
polynomial space bound
|
|
gptkbp:open_question
|
gptkb:PSPACE_vs_EXPTIME
PSPACE vs NP
|
|
gptkbp:PSPACE-complete_problem
|
gptkb:QBF
gptkb:TQBF
Model checking
Games with perfect information
Generalized geography
Quantified Boolean formula
Word problem for linear bounded automata
|
|
gptkbp:relatedTo
|
gptkb:QMA
gptkb:EXPTIME
gptkb:co-NP
gptkb:Savitch's_theorem
gptkb:QIP
P
L
NL
NP
PH
EXPSPACE
Alternating Turing machine
Interactive proof systems
QSPACE
Space hierarchy theorem
Time hierarchy theorem
|
|
gptkbp:resource_bound
|
space
|
|
gptkbp:resource_bound_type
|
gptkb:algebra
|
|
gptkbp:studiedBy
|
gptkb:theoretical_computer_science
|
|
gptkbp:bfsParent
|
gptkb:Vector_spaces
|
|
gptkbp:bfsLayer
|
8
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Polynomial space
|