Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Many-one_reduction> ?p ?o. }
Showing items 1 to 17 of
17
with 100 items per page.
- Many-one_reduction abstract "In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one reductions are a special case and stronger form of Turing reductions. With many-one reductions the oracle can be invoked only once at the end and the answer cannot be modified.Many-one reductions were first used by Emil Post in a paper published in 1944. Later Norman Shapiro used the same concept in 1956 under the name strong reducibility.".
- Many-one_reduction wikiPageID "362983".
- Many-one_reduction wikiPageRevisionID "595497830".
- Many-one_reduction hasPhotoCollection Many-one_reduction.
- Many-one_reduction subject Category:Computability_theory.
- Many-one_reduction subject Category:Computational_complexity_theory.
- Many-one_reduction comment "In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one reductions are a special case and stronger form of Turing reductions.".
- Many-one_reduction label "Many-one reduction".
- Many-one_reduction label "Redução por mapeamento".
- Many-one_reduction label "多対一還元".
- Many-one_reduction sameAs 多対一還元.
- Many-one_reduction sameAs Redução_por_mapeamento.
- Many-one_reduction sameAs m.01_ngp.
- Many-one_reduction sameAs Q3300648.
- Many-one_reduction sameAs Q3300648.
- Many-one_reduction wasDerivedFrom Many-one_reduction?oldid=595497830.
- Many-one_reduction isPrimaryTopicOf Many-one_reduction.