English Explanatory Dictionary

Turing reduction

English dictionary entry

Meanings

noun
  1. A reduction that solves a problem if the solution to another problem is already known, i.e. an algorithm that could be used to solve A if it had available to it a subroutine for solving B.

Word forms

Turing reduction Turing reductions

Etymology

After Alan Turing.

Related words

Cook reduction oracle machine
This entry uses open data from Wiktionary (CC BY-SA/GFDL). Word forms are used for search and are not indexed as separate pages.
Back to search All on T Russian dictionary Dahl dictionary