Complexity Atlas
HE
Source-backed question

1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר:

0Exams1Assignments0Lessons1Source documents
שאלה פתוחהq-094cda9f7820

נוסח השאלה

  1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא ff פונקציה ישימה בזמן. נגדיר:

    Tf={⟨M⟩#n | ⟨M⟩#n הוא קידוד חוקי, n טבעי,M דוחה את ⟨M⟩#n,timeM(⟨M⟩#n)≤1∣⟨M⟩∣ f(∣⟨M⟩#n∣)}.T_f= \left\{ \langle M\rangle\#^n \ \middle|\ \begin{array}{l} \langle M\rangle\#^n\text{ הוא קידוד חוקי},\ n\text{ טבעי},\\ M\text{ דוחה את }\langle M\rangle\#^n,\\ time_M(\langle M\rangle\#^n)\le \dfrac{1}{|\langle M\rangle|}\,f(|\langle M\rangle\#^n|) \end{array} \right\}.

    הסימון ⟨M⟩#n\langle M\rangle\#^n מבטא קידוד של מכונת טיורינג MM ולאחריו nn מופעים של התו #\#.

    תהא gg פונקציה המקיימת g=o(f)g=o(f).

    1. הוכיחו כי Tf∈DTime(f2)T_f\in DTime(f^2).
    2. הוכיחו כי Tf∉DTime(g)T_f\notin DTime(g). הסבירו היכן נעשה שימוש בתוספת #n\#^n לייצוג המכונה.
    3. הסיקו את משפט היררכיית הזמן.

  2. תנו דוגמה לשפה אשר שייכת ל-DTime(n2024)DTime(n^{2024}), אך אינה שייכת ל-DTime(n1011)DTime(n^{1011}).

  3. נתונות שש מחלקות הסיבוכיות:

    P,EXP,DTime(2n5),⋃c≥1DTime(nlog⁡cn),⋃c≥1DTime(cn),⋃c≥1DTime(2clog⁡2n).P,\quad EXP,\quad DTime(2^{n^5}),\quad \bigcup_{c\ge1}DTime(n^{\log^c n}),\quad \bigcup_{c\ge1}DTime(c^n),\quad \bigcup_{c\ge1}DTime(2^{c\log^2 n}).

    סדרו את המחלקות בשורה כך שכל מחלקה מכילה את קודמתה. לגבי כל אחת מחמש ההכלות המתקבלות, קבעו אם מדובר בשוויון או בהכלה ממש. הוכיחו את כל טענותיכם.

  4. הוכיחו את הטענות הבאות, תוך שימוש בהגדרה משאלה 2:

    1. TISP3(2n5,n7)⊊DTime(2n6)TISP^3(2^{n^5},n^7)\subsetneq DTime(2^{n^6}).
    2. TISP3(2n8,n4)⊈DTime(2n6)TISP^3(2^{n^8},n^4)\nsubseteq DTime(2^{n^6}).

נוסח מטלה שנבדק אנושית.

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.

Assignment

2024

2024_01_תרגיל_1.md

Question 4Page 1Human reviewed

The pages this was written from

1 page

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.

Examשפה A ניתנת להכרעה ע"י מכונת טיורינג דטרמיניסטית שמשתמשת במקום O(n 2) לקלט באורך n. שפה B ניתנת לרדוקציה לשפה A ע"י מ"ט דטרמיניסטית בזמן O(n 3) לקלט ב…Topically related — not a duplicateExamנתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A Σ* עבור קיימת מכונת טיורינג אי-דטרמיניסטית M וקיימים c 1 כך שלכל x Σ*, אם x A אז קיי…Topically related — not a duplicateExamנתונות מחלקות הסתביכויות הבאות. I. המחלקה C 1 היא כל השפות A Σ* עבורן קיימת מכונת טיורינג אי-דטרמיניסטית M וקיים c 1 כך שלכל x Σ*, אם x A אז כל ריצה ש…Topically related — not a duplicateExamמטל"ד M , שצורכת זיכרון עבודה "סביר" (S Ω(log(n))) (space constructible), ועלינו להוכיח, שקיימת מכונה דטרמיניסטית מתאימה M' , שמכריעה את L . קבעו אילו…Topically related — not a duplicateExamלפניכם 2 מחלקות סיבוכיות: • C 1 – מחלקת השפות A * עבורן קיים c 1 כך שקיימת מכונת טיורינג אי-דטרמיניסטית M, כך שלכל x * מתקיים: אם x A אז קיימת ריצה של…Topically related — not a duplicateExamתהא D מחלקת השפות A Σ* עבורן קיימים מכונת טיורינג M עם זמן ריצה פולינומיאלי ופולינום q כך שלכל x Σ* מתקיים: אם x A אז Pr r ~ 0,1 q(|x|)[M(x,r) = True]…Topically related — not a duplicate