יובל רצתה להוכיח את הטענה הבאה: אם 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. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

Exact provenance

Appearances by source document

Each card is a genuinely distinct file. Printed versions inside one PDF stay in that card and do not inflate the sitting count.

Exam

2026 A · moed A

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

Question 4Page 19Visual reading

View source scan — page 19

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

Open full size

נוסח השאלה

Appearances by source document

2026 A · moed A

Related questions from another source type