Redukcja karp jest wielomianową obliczalną w czasie wielokrotnością redukcji między dwoma problemami obliczeniowymi. Wiele redukcji Karp jest w rzeczywistości funkcjami jeden-jeden. Rodzi to pytanie, czy każda redukcja Karp jest iniekcyjna (funkcja jeden do jednego).
Czy istnieje naturalny problem z całkowitym którym wiadomo, że jest całkowity tylko przy zmniejszeniu Karp o wiele jeden, a nie jest znany jako całkowity po wstrzyknięciu zmniejszającym Karp? Co zyskujemy (i tracimy), jeśli zdefiniujemy kompletność za pomocą iniekcyjnej redukcji Karp?
Jednym oczywistym zyskiem jest to, że rzadkie zestawy nie mogą być kompletne przy iniekcyjnych redukcjach Karp.