Legyen <math>X</math> az az eldöntési probléma, ahol egy irányítatlan <math>G</math> páros gráfról és egy <math>k</math> számról azt szeretnénk eldönteni, hogy van-e <math>G</math> -ben <math>k</math> élű párosítás és legyen <math>Y</math> az a kérdés, ahol egy irányítatlan <math>G</math> gráfról és egy számról azt szeretnénk eldönteni, hogy van-e <math>G</math> -ben <math>k</math> pontból álló klikk (azaz teljes gráf). (2022 jan)Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq NP</math> ?
<math>X</math> Karp-redukálható <math>Y</math> -ra, de <math>Y</math> nem Karp-redukálható <math>X</math> -re. <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.