מפת הסיבוכיות
EN
שאלה מבוססת מקור

1. בפברואר 2025, פירסם ריאן ויליאמס מאוניברסיטת MIT תוצאה פורצת דרך לפיה לכל פונקציה f: ℕ ℕ המקיימת n f(n) לכל…

0בחינות0מטלות1שיעורים1מסמכי מקור
שאלה פתוחהq-f17e0ed1a19d

נוסח השאלה

  1. בפברואר 2025, פירסם ריאן ויליאמס מאוניברסיטת MIT תוצאה פורצת דרך לפיה לכל פונקציה f:N→Nf: ℕ\to ℕ המקיימת n≤f(n)n \le f(n) לכל n, מתקיים DTime(f) ⊆ DSpace(√(f ⋅ log_2 f)). (א) השתמשו בתוצאה שלעיל על מנת להוכיח כי DTime(2n)⊊DSpace(20.51n)DTime(2^n) \subsetneq DSpace(2^{0.51n}). לפי הנתון, כיוון ש−2n≥n- 2^n \ge n לכל n∈IN,DTime(2n)⊆DSpace((2nlog2n))=DSpace(2n/2⋅n)n=o(20.01n)n\in IN, DTime(2^n) \subseteq DSpace(\sqrt(2^n log 2^n)) = DSpace(2^{n/2}\cdot\sqrt n) \sqrt n = o(2^{0.01n}) כמו כן,20.01n, 2^{0.01n} סופר-לינארית וישימה במקום. לכן DSpace(2n/2⋅n)⊂DSpace(20.51n)DSpace(2^{n/2}\cdot\sqrt n) \subset DSpace(2^{0.51n}) לפי משפט ההיררכיה במקום. מכאן, DTime(2^n) ⊂ (2^{0.51n}) (ב) התוצאה שלעיל מעלה את השאלה האם ניתן לשפר את ה"שורש" שמופיע בפונקציית המקום לחזקה P⊆PSPACEP \subseteq PSPACE קטנה כרצוננו, כלומר האם לכל קבוע 0<ε0 < ε ולכל פונקציה f:N→Nf: ℕ\to ℕ המקיימת n≤f(n)n \le f(n) לכל n, מתקיים DTime(f) ⊆ DSpace(f^ε). הוכיחו כי אם טענה זו אכן מתקיימת אז P≠PSPACEP \ne PSPACE. צ"ל:P⊂PSPACE: P \subset PSPACE יהי c≥1c \ge 1. נבחר ε=1/c.ncε = 1/c. n^c סופר-לינארית, לכן DTime(n^c) ⊆ DSpace((n^c)^ε) = DSpace(n) לכן P=⋃c≥1DTime(nc)⊆DSpace(n)n=O(n2),n2P = \bigcup_{c\ge1} DTime(n^c) \subseteq DSpace(n) n = O(n^2), n^2 סופר-לינארית וישימה במקום, לכן DSpace(n)⊂DSpace(n2)DSpace(n2)⊆PSPACEDSpace(n) \subset DSpace(n^2) DSpace(n^2) \subseteq PSPACE לכן,P⊂PSPACE, P \subset PSPACE.

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

ייחוס מדויק

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

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

שיעור

שיעור 26-תרגילים.pdf

שיעור 26-תרגילים.pdf

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

העמודים שמהם זה נכתב

2 עמודים

העמודים נבחרו לפי חפיפת מילים בין הטקסט כאן לתמלול העמוד — לא אומתו ידנית. הם הצעה לבדיקה, לא ציטוט.

תרגול המשך

אלו התאמות לפי נושא ושיעור — לא מופעים זהים של אותה שאלה.

מטלה1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר:דומה בנושא — לא כפילותמטלה1. הוכיחו כי המחלקות הבאות סגורות לרדוקציות זמן פולינומיאלי: 1. PSPACE. 2. c 1DTime(n n c). 2. תהא B=\0\ שפה המכילה מחרוזת אחת בלבד. 1. הוכיחו כי לכל…דומה בנושא — לא כפילותמטלהחזרו על הוכחת משפט היררכיית המקום שהוצגה בהרצאה, וודאו שהיא מובנת במלואה. השתמשו בה כדי להוכיח באופן מלא את משפט היררכיית הזמן. תהיינה f,g: N N. נניח…דומה בנושא — לא כפילותמטלהחזרו על הוכחת משפט היררכיית המקום שהוצגה בהרצאה, וודאו שההוכחה מובנת לכם במלואה. השתמשו בכך כדי להוכיח באופן מלא את משפט היררכיית הזמן. **משפט:** תהיי…דומה בנושא — לא כפילותמטלההוכיחו כי מחלקת הסיבוכיות DTime(n 10) אינה סגורה לרדוקציות זמן פולינומי. **רמז:** השתמשו במשפט ההיררכיה בזמן ובמשפט הבא שהוכחנו בשיעור: לכל שתי שפות A…דומה בנושא — לא כפילותמטלההוכיחו כי DTime(n 10) אינה סגורה לרדוקציות זמן פולינומי. **רמז:** השתמשו במשפט ההיררכיה בזמן ובמשפט: לכל שתי שפות A,B, אם B P וגם A אינה טריוויאלית, א…דומה בנושא — לא כפילות