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