In computational complexity theory, a fine-grained reduction is a transformation from one computational problem to another, used to relate the difficulty of improving the time bounds for the two problems.Intuitively, it provides a method for solving one problem efficiently by using the solution to the other problem as a subroutine.If problem can be solved in time and problem can be solved in time , then the existence of an -reduction from problem to problem implies that any significant speedup for problem would also lead to a speedup for problem .
Property | Value |
---|---|
dbo:abstract |
|
dbo:wikiPageID |
|
dbo:wikiPageLength |
|
dbo:wikiPageRevisionID |
|
dbo:wikiPageWikiLink |
|
dbp:wikiPageUsesTemplate | |
dcterms:subject | |
rdfs:comment |
|
rdfs:label |
|
owl:sameAs | |
prov:wasDerivedFrom | |
foaf:isPrimaryTopicOf | |
is dbo:knownFor of | |
is dbo:wikiPageWikiLink of | |
is foaf:primaryTopic of |