Øv med flashcards — Problemer, instanser og reduksjoner

Problem $A$ reduseres polynomielt til $B$ dersom en polynomiell transformasjon gjør hver $A$-instans om til en $B$-instans med samme ja/nei-svar. Da er $B$ minst like hardt som $A$.