In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem into instances of a second decision problem where the instance reduced to is in the language if the initial instance was in its language and is not in the language if the initial instance was not in its language . Thus if we can decide whether instances are in the language , we can decide whether instances are in its language by applying the reduction and solving . Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that reduces to if, in layman's terms is harder to solve than . That is to say, any algorithm that solves can also be used as part of a (
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Many-one reduction (en)
- 多対一還元 (ja)
- Redução por mapeamento (pt)
- Багатозначна зводимість (uk)
|
| rdfs:comment
| - 多対一還元（たたいいちかんげん、many-one reduction）とは、計算理論と計算量理論におけるある種の操作の名前。何らかの決定問題を他の決定問題に変換する働きを持つ。 多対一還元はチューリング還元の特殊ケースであり、チューリング還元よりも弱い（多対一還元可能であるという主張はチューリング還元可能よりも強い）。多対一還元においては、オラクルの使用（神託機械参照）は一度だけ、そして最後にだけ許される。 多対一還元は1944年、エミール・ポストによって初めて導入された。1956年、Norman Shapiro は同じ概念を strong reducibility という名前で適用した。 (ja)
- Na teoria da computabilidade e teoria da complexidade computacional, uma redução por mapeamento é uma redução que converte instâncias de um problema de decisão em instâncias de um outro problema de decisão. Reduções são, portanto, usado para medir a relativa dificuldade computacional de dois problemas. Reduções por mapeamento são um caso especial e uma forma mais forte de redução. Reduções por mapeamento foram utilizados pela primeira vez por Emil Post em 1944. Mais tarde, em 1956, usou este mesmo conceito sob a redutibilidade. (pt)
- In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem into instances of a second decision problem where the instance reduced to is in the language if the initial instance was in its language and is not in the language if the initial instance was not in its language . Thus if we can decide whether instances are in the language , we can decide whether instances are in its language by applying the reduction and solving . Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that reduces to if, in layman's terms is harder to solve than . That is to say, any algorithm that solves can also be used as part of a ( (en)
- У теорії обчислюваності та теорії обчислювальної складності, багатозначна зводимість являє собою , що перетворює приклади одної у приклади другої задачі розпізнавання. Зводимості, таким чином, використовуються для вимірювання відносної обчислювальної важкості двох задач. Багатозначні зводимості є частинним випадком та посиленою формою . Для багатозначних зводимостей оракул може бути викликаний тільки одного разу наприкінці і відповідь не може бути змінена. (uk)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem into instances of a second decision problem where the instance reduced to is in the language if the initial instance was in its language and is not in the language if the initial instance was not in its language . Thus if we can decide whether instances are in the language , we can decide whether instances are in its language by applying the reduction and solving . Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that reduces to if, in layman's terms is harder to solve than . That is to say, any algorithm that solves can also be used as part of a (otherwise relatively simple) program that solves . Many-one reductions are a special case and stronger form of Turing reductions. With many-one reductions, the oracle (that is, our solution for B) can be invoked only once at the end, and the answer cannot be modified. This means that if we want to show that problem A can be reduced to problem B, we can use our solution for B only once in our solution for A, unlike in Turing reduction, where we can use our solution for B as many times as needed while solving A. This means that many-one reductions map instances of one problem to instances of another, while Turing reductions compute the solution to one problem, assuming the other problem is easy to solve. The many-one reduction is more effective at separating problems into distinct complexity classes. However, the increased restrictions on many-one reductions make them more difficult to find. 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. (en)
- 多対一還元（たたいいちかんげん、many-one reduction）とは、計算理論と計算量理論におけるある種の操作の名前。何らかの決定問題を他の決定問題に変換する働きを持つ。 多対一還元はチューリング還元の特殊ケースであり、チューリング還元よりも弱い（多対一還元可能であるという主張はチューリング還元可能よりも強い）。多対一還元においては、オラクルの使用（神託機械参照）は一度だけ、そして最後にだけ許される。 多対一還元は1944年、エミール・ポストによって初めて導入された。1956年、Norman Shapiro は同じ概念を strong reducibility という名前で適用した。 (ja)
- Na teoria da computabilidade e teoria da complexidade computacional, uma redução por mapeamento é uma redução que converte instâncias de um problema de decisão em instâncias de um outro problema de decisão. Reduções são, portanto, usado para medir a relativa dificuldade computacional de dois problemas. Reduções por mapeamento são um caso especial e uma forma mais forte de redução. Reduções por mapeamento foram utilizados pela primeira vez por Emil Post em 1944. Mais tarde, em 1956, usou este mesmo conceito sob a redutibilidade. (pt)
- У теорії обчислюваності та теорії обчислювальної складності, багатозначна зводимість являє собою , що перетворює приклади одної у приклади другої задачі розпізнавання. Зводимості, таким чином, використовуються для вимірювання відносної обчислювальної важкості двох задач. Багатозначні зводимості є частинним випадком та посиленою формою . Для багатозначних зводимостей оракул може бути викликаний тільки одного разу наприкінці і відповідь не може бути змінена. Багатозначні зводимості були вперше використані Емілем Постом у 1944 році. Пізніше використав ідентичне поняття у 1956 році під назвою сильна зводимість. (uk)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)