Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q905967> ?p ?o }
Showing triples 1 to 41 of
41
with 100 triples per page.
- Q905967 subject Q7298553.
- Q905967 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.".
- Q905967 wikiPageExternalLink 6007.
- Q905967 wikiPageWikiLink Q1087987.
- Q905967 wikiPageWikiLink Q11197.
- Q905967 wikiPageWikiLink Q11413.
- Q905967 wikiPageWikiLink Q1141840.
- Q905967 wikiPageWikiLink Q1154605.
- Q905967 wikiPageWikiLink Q125977.
- Q905967 wikiPageWikiLink Q1276570.
- Q905967 wikiPageWikiLink Q1350285.
- Q905967 wikiPageWikiLink Q1756295.
- Q905967 wikiPageWikiLink Q185521.
- Q905967 wikiPageWikiLink Q185612.
- Q905967 wikiPageWikiLink Q205084.
- Q905967 wikiPageWikiLink Q2103034.
- Q905967 wikiPageWikiLink Q215206.
- Q905967 wikiPageWikiLink Q2180601.
- Q905967 wikiPageWikiLink Q2316017.
- Q905967 wikiPageWikiLink Q3262192.
- Q905967 wikiPageWikiLink Q500716.
- Q905967 wikiPageWikiLink Q5265707.
- Q905967 wikiPageWikiLink Q5532477.
- Q905967 wikiPageWikiLink Q605445.
- Q905967 wikiPageWikiLink Q628036.
- Q905967 wikiPageWikiLink Q6593263.
- Q905967 wikiPageWikiLink Q690265.
- Q905967 wikiPageWikiLink Q718.
- Q905967 wikiPageWikiLink Q7298553.
- Q905967 wikiPageWikiLink Q748139.
- Q905967 wikiPageWikiLink Q7572588.
- Q905967 wikiPageWikiLink Q844874.
- Q905967 wikiPageWikiLink Q846354.
- Q905967 wikiPageWikiLink Q875276.
- Q905967 wikiPageWikiLink Q903738.
- Q905967 wikiPageWikiLink Q908674.
- Q905967 wikiPageWikiLink Q938821.
- Q905967 wikiPageWikiLink Q953673.
- Q905967 wikiPageWikiLink Q954210.
- Q905967 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.".
- Q905967 label "PSPACE-complete".