Matches in DBpedia 2014 for { <http://dbpedia.org/resource/P-complete> ?p ?o. }
Showing items 1 to 24 of
24
with 100 items per page.
- P-complete abstract "In complexity theory, the notion of P-complete decision problems is useful in the analysis of both: which problems are difficult to parallelize effectively, and; which problems are difficult to solve in limited space.Formally, a decision problem is P-complete (complete for the complexity class P) if it is in P and that every problem in P can be reduced to it by using an appropriate reduction.The specific type of reduction used varies and may affect the exact set of problems. If we use NC reductions, that is, reductions which can operate in polylogarithmic time on a parallel computer with a polynomial number of processors, then all P-complete problems lie outside NC and so cannot be effectively parallelized, under the unproven assumption that NC ≠ P. If we use the weaker log-space reduction, this remains true, but additionally we learn that all P-complete problems lie outside L under the weaker unproven assumption that L ≠ P. In this latter case the set P-complete may be smaller.".
- P-complete wikiPageID "54683".
- P-complete wikiPageRevisionID "600534949".
- P-complete hasPhotoCollection P-complete.
- P-complete subject Category:Complexity_classes.
- P-complete type Abstraction100002137.
- P-complete type Class107997703.
- P-complete type Collection107951464.
- P-complete type ComplexityClasses.
- P-complete type Group100031264.
- P-complete comment "In complexity theory, the notion of P-complete decision problems is useful in the analysis of both: which problems are difficult to parallelize effectively, and; which problems are difficult to solve in limited space.Formally, a decision problem is P-complete (complete for the complexity class P) if it is in P and that every problem in P can be reduced to it by using an appropriate reduction.The specific type of reduction used varies and may affect the exact set of problems.".
- P-complete label "P-complete".
- P-complete label "P-completo".
- P-complete label "P-completo".
- P-complete label "P-完全".
- P-complete sameAs P-completo.
- P-complete sameAs P-완전.
- P-complete sameAs P-completo.
- P-complete sameAs m.0f87m.
- P-complete sameAs Q905789.
- P-complete sameAs Q905789.
- P-complete sameAs P-complete.
- P-complete wasDerivedFrom P-complete?oldid=600534949.
- P-complete isPrimaryTopicOf P-complete.