  Our definition of reduction above lacked precision, just saying that the mapping \(\tau\) must by easy-to-compute.  The reductions that Karp used were polynomial-time reductions, i.e., \(\tau\) is computable in polynomial time.   Since then, many researchers have observed that natural problems remain complete for natural complexity classes under surprisingly weak reductions including logspace reductions [Jones, 1973], first-order reductions [Immerman, 1999], projections [Valiant, 1982], and first-order projections [Immerman, 1999]. 