Matches in DBpedia 2014 for { <http://dbpedia.org/resource/PSPACE-complete> ?p ?o. }
Showing items 1 to 25 of
25
with 100 items 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 of 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 wikiPageRevisionID "572374863".
- PSPACE-complete hasPhotoCollection PSPACE-complete.
- PSPACE-complete subject Category:Complexity_classes.
- PSPACE-complete type Abstraction100002137.
- PSPACE-complete type Class107997703.
- PSPACE-complete type Collection107951464.
- PSPACE-complete type ComplexityClasses.
- PSPACE-complete type Group100031264.
- 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 label "PSPACE-completo".
- PSPACE-complete label "PSPACE-completude".
- PSPACE-complete label "مسائل 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 sameAs Q905967.
- PSPACE-complete sameAs PSPACE-complete.
- PSPACE-complete wasDerivedFrom PSPACE-complete?oldid=572374863.
- PSPACE-complete isPrimaryTopicOf PSPACE-complete.