Legyen <math>X</math> a <math>2SZÍN</math> eldöntési probléma, azaz ahol egy egyszerü, irányítatlan <math>G</math> gráfról azt szeretnénk eldönteni, hogy ki lehet-e színezni a csúcsait két színnel úgy, hogy azonos színú csúcsok közőtt ne menjen él. Az <math>Y</math> eldöntési problémában pedig azt kell eldöntenünk <math>n</math> darab pozitív egész számról, hogy van-e ezeknek a számoknak egy olyan részhalmaza, hogy a részhalmazban levő számok összege megegyezik a részhalmazba be nem vett számok összegével. (2022 jun)Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq N P</math> ?
<math>X</math> nem Karp-redukálható <math>Y</math> -ra, de <math>Y</math> Karp-redukálható <math>X</math> -re. <math>X</math> Karp-redukálható <math>Y</math> -ra és <math>Y</math> is Karp-redukálható <math>X</math> -re. <math>X</math> sem Karp-redukálható <math>Y</math> -ra és <math>Y</math> sem Karp-redukálható <math>X</math> -re. <math>X</math> Karp-redukálható <math>Y</math> -ra, de <math>Y</math> nem Karp-redukálható <math>X</math> -re.