ענו על שני הסעיפים הנפרדים הבאים. (א1) CIRCUIT-SAT. נתון כי במעגל הפלט שמופק על ידי הרצת רדוקציית Cook-Levin C…

ענו על שני הסעיפים הנפרדים הבאים. (א1) CIRCUIT-SAT. נתון כי במעגל הפלט שמופק על ידי הרצת רדוקציית $Cook-Levin CIRCUIT-SAT \le_P L$ מופיע תת-המעגל $g_{18,4,1/43}$ הבא, שמייצג את זכרון s = 4 בזמן t = 18: [דיאגרמה] g_{17,4,0/45} g_{17,4,1} g_{17,5,1/49} מה ניתן ללמוד מכך אודות פונקציית המעברים של המווקדא הרלוונטי של השפה L: ________________________________________ ________________________________________ (ב1) SUBSET-SUM. נתון כי הפלט של הרדוקציה הסטנדרטית $3-SAT \le_P SUBSET-SUM$ הינה בדיוק הרשימה של 14 המספרים הבאים, ובנוסף אליהם מספר היעד t. [טבלה] 1,000,001 10,100 100 1,000,010 10,010 10 100,100 1,101 10 100,001 1,010 1 100 1 רשמו את מספר היעד t ______________________________________ רשמו את סדרת הפסוקיות של הקלט ______________________________________ 4