Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/PSPACE-complete> ?p ?o }
Showing triples 1 to 64 of
64
with 100 triples per page.
- PSPACE-complete abstract "In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.The PSPACE-complete problems are widely suspected to be outside the more famous complexity classes P and NP, but that is not known. It is known that they lie outside of the class NC (a class of problems with highly efficient parallel algorithms), because problems in NC can be solved in an amount of space polynomial in the logarithm of the input size, and the class of problems solvable in such a small amount of space is strictly contained in PSPACE by the space hierarchy theorem.".
- PSPACE-complete wikiPageExternalLink 6007.
- PSPACE-complete wikiPageID "54685".
- PSPACE-complete wikiPageLength "7591".
- PSPACE-complete wikiPageOutDegree "39".
- PSPACE-complete wikiPageRevisionID "705092691".
- PSPACE-complete wikiPageWikiLink Atomix_(video_game).
- PSPACE-complete wikiPageWikiLink Boolean_satisfiability_problem.
- PSPACE-complete wikiPageWikiLink Category:Complexity_classes.
- PSPACE-complete wikiPageWikiLink Chess.
- PSPACE-complete wikiPageWikiLink Computational_complexity_theory.
- PSPACE-complete wikiPageWikiLink Computers_and_Intractability.
- PSPACE-complete wikiPageWikiLink Context-sensitive_grammar.
- PSPACE-complete wikiPageWikiLink Decision_problem.
- PSPACE-complete wikiPageWikiLink Deterministic_automaton.
- PSPACE-complete wikiPageWikiLink EXPTIME.
- PSPACE-complete wikiPageWikiLink English_draughts.
- PSPACE-complete wikiPageWikiLink Game_complexity.
- PSPACE-complete wikiPageWikiLink Generalized_game.
- PSPACE-complete wikiPageWikiLink Go_(game).
- PSPACE-complete wikiPageWikiLink Hex_(board_game).
- PSPACE-complete wikiPageWikiLink List_of_PSPACE-complete_problems.
- PSPACE-complete wikiPageWikiLink Logarithm.
- PSPACE-complete wikiPageWikiLink Lookup_table.
- PSPACE-complete wikiPageWikiLink Mahjong_solitaire.
- PSPACE-complete wikiPageWikiLink NC_(complexity).
- PSPACE-complete wikiPageWikiLink NP-completeness.
- PSPACE-complete wikiPageWikiLink NP_(complexity).
- PSPACE-complete wikiPageWikiLink NSPACE.
- PSPACE-complete wikiPageWikiLink PSPACE.
- PSPACE-complete wikiPageWikiLink P_(complexity).
- PSPACE-complete wikiPageWikiLink Parallel_algorithm.
- PSPACE-complete wikiPageWikiLink Polynomial-time_reduction.
- PSPACE-complete wikiPageWikiLink Regular_expression.
- PSPACE-complete wikiPageWikiLink Reversi.
- PSPACE-complete wikiPageWikiLink Rush_Hour_(board_game).
- PSPACE-complete wikiPageWikiLink Savitchs_theorem.
- PSPACE-complete wikiPageWikiLink Sokoban.
- PSPACE-complete wikiPageWikiLink Space_hierarchy_theorem.
- PSPACE-complete wikiPageWikiLink True_quantified_Boolean_formula.
- PSPACE-complete wikiPageWikiLink Truth_value.
- PSPACE-complete wikiPageWikiLink Vector_space.
- PSPACE-complete wikiPageWikiLinkText "'''PSPACE'''-complete".
- PSPACE-complete wikiPageWikiLinkText "PSPACE-complete".
- PSPACE-complete wikiPageUsesTemplate Template:Citation.
- PSPACE-complete wikiPageUsesTemplate Template:ComplexityClasses.
- PSPACE-complete wikiPageUsesTemplate Template:Harvtxt.
- PSPACE-complete wikiPageUsesTemplate Template:Reflist.
- PSPACE-complete wikiPageUsesTemplate Template:Sfnp.
- PSPACE-complete subject Category:Complexity_classes.
- PSPACE-complete hypernym PSPACE-complete.
- PSPACE-complete type Class.
- PSPACE-complete type Redirect.
- PSPACE-complete comment "In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time.".
- PSPACE-complete label "PSPACE-complete".
- PSPACE-complete sameAs Q905967.
- PSPACE-complete sameAs مسائل_PSPACE_كاملة.
- PSPACE-complete sameAs PSPACE-completo.
- PSPACE-complete sameAs PSPACE-완전.
- PSPACE-complete sameAs PSPACE-completude.
- PSPACE-complete sameAs m.0f88g.
- PSPACE-complete sameAs Q905967.
- PSPACE-complete wasDerivedFrom PSPACE-complete?oldid=705092691.
- PSPACE-complete isPrimaryTopicOf PSPACE-complete.