Many-one reduction (original) (raw)
多対一還元（たたいいちかんげん、many-one reduction）とは、計算理論と計算量理論におけるある種の操作の名前。何らかの決定問題を他の決定問題に変換する働きを持つ。 多対一還元はチューリング還元の特殊ケースであり、チューリング還元よりも弱い（多対一還元可能であるという主張はチューリング還元可能よりも強い）。多対一還元においては、オラクルの使用（神託機械参照）は一度だけ、そして最後にだけ許される。 多対一還元は1944年、エミール・ポストによって初めて導入された。1956年、Norman Shapiro は同じ概念を strong reducibility という名前で適用した。
| Property | Value |
|---|---|
| dbo: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) |
| dbo:wikiPageID | 362983 (xsd:integer) |
| dbo:wikiPageLength | 9408 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1099548749 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Power_set dbr:Preorder dbr:NP_(complexity) dbr:Total_computable_function dbr:Algorithm dbc:Reduction_(complexity) dbr:Relation_(mathematics) dbr:Decidability_(logic) dbr:Decision_problem dbr:Computability_theory dbr:Co-NP dbr:NL_(complexity) dbr:L_(complexity) dbr:Alphabet_(computer_science) dbr:Computational_complexity_theory dbr:P_(complexity) dbr:Transitive_relation dbr:Log-space_reduction dbr:Polynomial-time_reduction dbr:Norman_Shapiro dbr:PSPACE dbr:Formal_language dbr:Recursively_enumerable dbr:Reduction_(complexity) dbr:Halting_problem dbr:If_and_only_if dbr:Iff dbr:Reflexive_relation dbr:Universal_Turing_machine dbr:Turing_reduction dbr:Injective dbr:Powerset dbr:Richard_Karp dbr:Emil_Post dbr:EXP |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Reduction_(complexity) |
| gold:hypernym | dbr:Reduction |
| rdf:type | dbo:Album |
| 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) |
| rdfs:label | Many-one reduction (en) 多対一還元 (ja) Redução por mapeamento (pt) Багатозначна зводимість (uk) |
| owl:sameAs | freebase:Many-one reduction wikidata:Many-one reduction dbpedia-ja:Many-one reduction dbpedia-pt:Many-one reduction dbpedia-uk:Many-one reduction https://global.dbpedia.org/id/33FAE |
| prov:wasDerivedFrom | wikipedia-en:Many-one_reduction?oldid=1099548749&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Many-one_reduction |
| is dbo:wikiPageRedirects of | dbr:Many-one_reducible dbr:Many-one dbr:Many-to-one_reduction dbr:Mapping_reducibility dbr:Mapping_reduction dbr:M-complete |
| is dbo:wikiPageWikiLink of | dbr:Preorder dbr:Enumeration_reducibility dbr:Myhill_isomorphism_theorem dbr:NE_(complexity) dbr:Parsimonious_reduction dbr:Decidability_(logic) dbr:Decision_problem dbr:Index_set_(computability) dbr:PSPACE-complete dbr:Computability_theory dbr:SL_(complexity) dbr:NP-easy dbr:Clique_problem dbr:Emil_Leon_Post dbr:Creative_and_productive_sets dbr:Arithmetical_hierarchy dbr:Berman–Hartmanis_conjecture dbr:Complement_(complexity) dbr:Computability_logic dbr:Computable_isomorphism dbr:PR_(complexity) dbr:Gadget_(computer_science) dbr:Karp's_21_NP-complete_problems dbr:Log-space_reduction dbr:Polynomial-time_reduction dbr:Norman_Shapiro dbr:Goishi_Hiroi dbr:RE_(complexity) dbr:Reduction_(complexity) dbr:Back-and-forth_method dbr:Counting_problem_(complexity) dbr:Hyperarithmetical_theory dbr:Holographic_algorithm dbr:Reduction_(computability_theory) dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:NP-completeness dbr:NP-hardness dbr:Post's_theorem dbr:Many-one_reducible dbr:PolyL dbr:Polynomial-time_counting_reduction dbr:Polynomial_creativity dbr:Turing_reduction dbr:Simple_set dbr:Turing_degree dbr:Many-one dbr:Many-to-one_reduction dbr:Mapping_reducibility dbr:Mapping_reduction dbr:M-complete |
| is foaf:primaryTopic of | wikipedia-en:Many-one_reduction |