נתבונן בשפות הבאות: A=\ G,k ב-G יש קליקה בגודל k בדיוק\ B=\ G,k ב-G יש קליקה בגודל k לפחות\ C=\ G,k k הוא גודל…

נתבונן בשפות הבאות:

$A=\{\langle G,k\rangle\mid$ ב-$G$ יש קליקה בגודל $k$ בדיוק$\}$

$B=\{\langle G,k\rangle\mid$ ב-$G$ יש קליקה בגודל $k$ לפחות$\}$

$C=\{\langle G,k\rangle\mid k$ הוא גודלה של הקליקה המקסימאלית ב-$G\}$

(כל הגרפים בשאלה אינם מכוונים).

נתונות הטענות הבאות:

i. $A\le_p B$

ii. $B\le_p C$

iii. $C\le_p A$

אילו מהטענות הנתונות שקולות לשאלה פתוחה?