Complexity Atlas
HE
Source-backed question

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

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

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.

Lesson

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

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

Question 1Page 1Visual reading

The pages this was written from

2 pages

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Further practice

These are topic and lesson matches, not identical appearances.

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