computation Definition Karp Reduction A many-one reduction with a reduction f is called Karp reduction if f is computable in polynomial time.