多対一還元
1. Many-one reductionIn 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.
Read “Many-one reduction” on English Wikipedia
Read “多対一還元” on Japanese Wikipedia
Read “Many-one reduction” on DBpedia
Read “Many-one reduction” on English Wikipedia
Read “多対一還元” on Japanese Wikipedia
Read “Many-one reduction” on DBpedia
Discussions
Log in to talk about this word.