About: Polynomial-time counting reduction

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

In the computational complexity theory of counting problems, a polynomial-time counting reduction is a type of reduction (a transformation from one problem to another) used to define the notion of completeness for the complexity class ♯P. These reductions may also be called polynomial many-one counting reductions or weakly parsimonious reductions; they are analogous to many-one reductions for decision problems and they generalize the parsimonious reductions.

Property Value
dbo:abstract
  • In the computational complexity theory of counting problems, a polynomial-time counting reduction is a type of reduction (a transformation from one problem to another) used to define the notion of completeness for the complexity class ♯P. These reductions may also be called polynomial many-one counting reductions or weakly parsimonious reductions; they are analogous to many-one reductions for decision problems and they generalize the parsimonious reductions. (en)
dbo:wikiPageID
  • 59141049 (xsd:integer)
dbo:wikiPageLength
  • 6037 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1071444636 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • In the computational complexity theory of counting problems, a polynomial-time counting reduction is a type of reduction (a transformation from one problem to another) used to define the notion of completeness for the complexity class ♯P. These reductions may also be called polynomial many-one counting reductions or weakly parsimonious reductions; they are analogous to many-one reductions for decision problems and they generalize the parsimonious reductions. (en)
rdfs:label
  • Polynomial-time counting reduction (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License