תהא Φ נוסחה בוליאנית מצורת CNF עם n משתנים ופחות מ- n logn פסוקיות. בכל פסוקית יש בדיוק m ליטרלים ממשתנים שוני…

תהא $Φ$ נוסחה בוליאנית מצורת CNF עם n משתנים ופחות מ$- n^{logn}$ פסוקיות. בכל פסוקית יש בדיוק m ליטרלים ממשתנים שונים (אך כמובן שבין פסוקיות שונות המשתנים אינם המשתנים בהכרח שונים). מבין ערכי m הבאים, מהו ה- m המינימלי שיבטיח שהנוסחה $Φ$ תהיה בוודאות ספיקה? (רמז: חישבו על השמה אקראית).