בהוכחת משפט קוק-לוין יצאנו משפה B NP והראינו שהיא ניתנת לרדוקציית זמן פולינומיאלי ל- SAT. לשם כך, עבור קלט x ל…

בהוכחת משפט קוק-לוין יצאנו משפה $B \in NP$ והראינו שהיא ניתנת לרדוקציית זמן פולינומיאלי ל- SAT. לשם כך, עבור קלט x לשפה B נעזרנו בטבלה ריבועית $T_{M,x}$ בגודל q(|x|) × q(|x|) (כאשר M ו- q הוצגו בהוכחה) ובנינו טבלת אמת לכל אחד מ$- q^2(|x|)$ תאי הטבלה. נסמן ב- r את מספר השורות הכולל בטבלאות האמת בכל $q^2(|x|)$ תאי הטבלה יחד. מבין הטענות הבאות, מה הטענה החזקה ביותר הנכונה לגבי r? (תזכורת: בטבלת אמת בעלת m משתנים יש $2^m$ שורות.)