באחד מהתרגילים בקורס תוארה רדוקציה מהשפה 4-NAE לשפה 3-NAE (תזכורת: 3-NAE הייא שפת הנוסחאות בצורת 3-CNF שיש להם…

באחד מהתרגילים בקורס תוארה רדוקציה מהשפה 4-NAE לשפה 3-NAE (תזכורת: 3-NAE הייא שפת הנוסחאות בצורת 3-CNF שיש להם השמה וכך שמתקיים שבכל פסוקית יש לפחות ליטרל אחד שערכו בהשמה הוא True ולפחות ליטרל אחד שערכו בהשמה הוא False. השפה 4-NAE מוגדרת בדומה אך עם נוסחאות בצורת 4-CNF). נניח שהקלט לרדוקציה זו מכיל 3 פסוקיות שכל אחת מהן מכילה 4 ליטרלים ממשתנים שונים וגם בין הפסוקיות אין ליטרלים מאותו המשתנה (כלומר הנוסחה מכילה 12 ליטרלים ממשתנים שונים). נסמן ב$- α$ את מספר המשתנים (שימו לב: משתנים ולא ליטרלים) הכולל בפלט הרדוקציה וב$- β$ את מספר הפסנעקוות הכולל בפלט הרדוקציה. מה הערכים הנכונים של $α$ ו$- β$?