About: PSPACE-complete

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Complexity class

Property	Value
dbo:description	clase de complejidad (es) classe de complexitat (ca) classe di complessità (it) complexity class (en) classe de complexité (fr) třída složitosti (cs) 複雜度等級 (zh)
dbo:wikiPageExternalLink	https://archive.org/details/introductiontoth00sips/page/283
dbo:wikiPageWikiLink	dbr:NC_(complexity) dbr:Polynomial-time_reduction dbr:Lookup_table dbr:Logarithm dbr:NP_(complexity) dbr:PSPACE dbr:Parallel_algorithm dbr:Many-one_reduction dbr:Berman–Hartmanis_conjecture dbr:Chess dbr:Combinatorial_game_theory dbr:Mahjong_solitaire dbr:Savitch's_theorem dbr:Regular_expression dbr:Computational_complexity_theory dbr:Atomix_(computer_game) dbr:EXPTIME-complete dbr:Boolean_satisfiability_problem dbr:Context-sensitive_grammar dbr:Space_hierarchy_theorem dbr:Sokoban dbr:Reversi dbr:Hex_(board_game) dbr:P_(complexity) dbr:Turing_reduction dbr:Bijection dbr:Orientation_(graph_theory) dbc:Complexity_classes dbr:Mechanical_computer dbr:English_draughts dbr:Decision_problem dbr:Generalized_game dbr:Nondeterministic_constraint_logic dbr:Reconfiguration dbr:Turing_Tumble dbr:State_space dbr:Word_problem_(computability) dbr:Linear_space dbr:Rush_Hour_(board_game) dbr:Deterministic_computation dbr:Go_(board_game) dbr:Quantified_Boolean_formula_problem
dbp:wikiPageUsesTemplate	dbt:Main dbt:Reflist dbt:ComplexityClasses dbt:For dbt:R dbt:Citation dbt:Harvtxt dbt:Short_description
dct:subject	dbc:Complexity_classes
gold:hypernym	dbr:PSPACE-complete
rdfs:label	PSPACE-complete (en) مسائل PSPACE كاملة (ar) PSPACE-complet (ca) PSPACE-completo (es) PSPACE-완전 (ko) PSPACE-completude (pt)
owl:sameAs	freebase:PSPACE-complete yago-res:PSPACE-complete wikidata:PSPACE-complete dbpedia-pt:PSPACE-complete dbpedia-es:PSPACE-complete dbpedia-ko:PSPACE-complete dbpedia-ca:PSPACE-complete dbpedia-ar:PSPACE-complete dbpedia-global:PSPACE-complete
prov:wasDerivedFrom	wikipedia-en:PSPACE-complete?oldid=1256071823&ns=0
foaf:isPrimaryTopicOf	wikipedia-en:PSPACE-complete
is dbo:wikiPageRedirects of	dbr:PSPACE-Complete dbr:PSPACE_complete dbr:Pspace-Complete dbr:Pspace-complete
is dbo:wikiPageWikiLink of	dbr:Index_of_computing_articles dbr:Online_algorithm dbr:Polynomial-time_reduction dbr:True_quantified_Boolean_formula dbr:Kayles dbr:Type_inhabitation dbr:Cook–Levin_theorem dbr:Game_of_the_Amazons dbr:PSPACE dbr:TwixT dbr:Polynomial_hierarchy dbr:Heyting_algebra dbr:EXPTIME dbr:Emptiness_problem dbr:Alternating_finite_automaton dbr:Formula_game dbr:Modal_μ-calculus dbr:Game_complexity dbr:Computation_tree_logic dbr:Rush_Hour_(puzzle) dbr:Strategy-stealing_argument dbr:Atomix_(video_game) dbr:Solved_game dbr:Mahjong_solitaire dbr:Linear_logic dbr:Security_of_cryptographic_hash_functions dbr:Rado_graph dbr:Col_(game) dbr:Timed_automaton dbr:Havannah dbr:Boolean_satisfiability_problem dbr:Simplex_algorithm dbr:Context-sensitive_grammar dbr:Context-sensitive_language dbr:Gomoku dbr:List_of_complexity_classes dbr:Transdichotomous_model dbr:Sokoban dbr:Regular_language dbr:Reversi dbr:Hex_(board_game) dbr:Lemmings_(video_game) dbr:Distributed_computing dbr:Referential_integrity dbr:Finite_model_theory dbr:List_of_PSPACE-complete_problems dbr:Lemke–Howson_algorithm dbr:Linear_temporal_logic dbr:Canadian_traveller_problem dbr:Poset_game dbr:Richard_Statman dbr:Dynamic_epistemic_logic dbr:Japaridze's_polymodal_logic dbr:Hypercomputation dbr:Kōnane dbr:Real_RAM dbr:Logic_of_graphs dbr:Online_optimization dbr:Generalized_game dbr:Generalized_geography dbr:Kosaburo_Hashiguchi dbr:Quantum_mechanics_of_time_travel dbr:NFA_minimization dbr:Nondeterministic_constraint_logic dbr:Reconfiguration dbr:Turing_Tumble dbr:Word_chain dbr:Equivalence_problem dbr:Metric_interval_temporal_logic dbr:Games,_Puzzles,_and_Computation dbr:Intersection_non-emptiness_problem dbr:Instant_Insanity dbr:Metric_temporal_logic dbr:Size-change_termination_principle dbr:PSPACE-Complete dbr:PSPACE_complete dbr:Pspace-Complete dbr:Pspace-complete
is gold:hypernym of	dbr:PSPACE-complete dbr:List_of_PSPACE-complete_problems
is foaf:primaryTopic of	wikipedia-en:PSPACE-complete