English Explanatory Dictionary

Karp reduction

English dictionary entry

Meanings

noun
  1. A polynomial-time algorithm for transforming inputs to one problem into inputs to another problem, such that the transformed problem has the same output as the original.

Word forms

Karp reduction Karp reductions

Etymology

Named after Richard Karp.

Related words

Karp-reducible Karp-reducibility
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 K Russian dictionary Dahl dictionary