A problem X {\displaystyle \scriptstyle X} is polynomial-time Turing-reducible to a problem Y {\displaystyle \scriptstyle Y} if, given a subroutine that solves Y {\displaystyle \scriptstyle Y} in polynomial time, one could write a program that calls this subroutine and solves X {\displaystyle \scriptstyle X} in polynomial time.
O problemă X {\displaystyle \scriptstyle X} este Turing-reductibilă în timp polinomial la o problemă Y {\displaystyle \scriptstyle Y} dacă, având o subrutină care rezolvă Y {\displaystyle \scriptstyle Y} în timp polinomial, s-ar putea scrie un program care apelează această subrutină și rezolvă X {\displaystyle \scriptstyle X} în timp polinomial.