Polynomielle Reduktion

Ein Entscheidungsproblem P ist polynomiell reduzierbar auf ein Entscheidungsproblem Q, wenn jede Instanz von P in polynomieller Zeit in eine Instanz von Q transformiert werden kann.