יובל רצתה להוכיח את הטענה הבאה: אם DSpace(n 10) P אז DSpace(n 50) P בעזרת טיעוני ריפוד. את…

שאלת רב־ברירהq-af4874687e1a

נוסח השאלה

יובל רצתה להוכיח את הטענה הבאה: אם $DSpace(n^{10}) \subseteq P$ אז $DSpace(n^{50}) \subseteq P$ בעזרת טיעוני ריפוד. את ההוכחה היא התחילה כך: נניח ש- $DSpace(n^{10}) \subseteq P$ . תהא $A \in DSpace(n^{50})$ . נגדיר את הבעיה $B$ הבאה: $B =$ ??? ( $B$ היא למעשה הבעיה $A$ ה"מרופדת"). עזרו ליובל לבחור את הבעיה B המתאימה להמשך ההוכחה. איזו בעיה תתאים כאן ?

א
$B = \left\{ x \#^{|x|^{5}} \mid x \in A \right\}$
ב
$B = \left\{ x \#^{|x|^{10}} \mid x \in A \right\}$
ג
$B = \left\{ x \#^{|x|^{2}} \mid x \in A \right\}$
דתשובות א ', ב ' נכונות.
התשובות ב ', ג ' נכונות.
ואף אחת מהתשובות אינה נכונה.

תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

ייחוס מדויק

מופעים לפי מסמך מקור

כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.

בחינה

2026 א׳ · מועד א׳

מ-נושא 131111 סיבוכיות מועד 1.pdf

שאלה 4עמוד 19קריאה חזותית

הצגת צילום המקור — עמוד 19

עמוד מקור 19 מתוך מ-נושא 131111 סיבוכיות מועד 1.pdf

פתיחה בגודל מלא

נוסח השאלה

מופעים לפי מסמך מקור

2026 א׳ · מועד א׳

שאלות קשורות ממקור מסוג אחר