שאלת רב־ברירהq-cbefc4816d5a
נוסח השאלה
יהיו A ו- B שפות. ידוע ש- A ניתנת לרדוקציית זמן פולינומיאלי ל- B וש- A שלמה ל- EXP (ביחס לרדוקציות זמן פולינומיאלי). נתבונן בטענות הבאות: (i B ∈ NL. (ii B ∈ P. (iii B ∈ NP. (iv B ∈ PSPACE. (v B ∈ EXP. עבור כמה מהטענות שלעיל ידוע שהן בהכרח אינן נכונות?
תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.
ייחוס מדויק
מופעים לפי מסמך מקור
כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.
בחינה
2025 א׳ · מועד א׳
נושא 131111 קבוצה 13111101 שנה 2025 סמסטר 1 מועד 1.pdf
שאלה 9עמוד 7קריאה חזותית
הצגת צילום המקור — עמוד 7
פתיחה בגודל מלא