Complexity Atlas
HE
Source-backed question

נתונות שלוש מחלקות סיבוכיות: .C1 = DTime(2 n 4) , C2 = DSpace(n 3) , C3 = c>1 DTime(2 cn 4) איזו מבין הטענות ש…

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירהq-7ffd3ed9ca82

נוסח השאלה

נתונות שלוש מחלקות סיבוכיות:.C1=DTime(2n4),C2=DSpace(n3),C3=⋃c>1DTime(2cn4): .C1 = DTime(2^{n^4}) , C2 = DSpace(n^3) , C3 = \bigcup_{c>1} DTime(2^{cn^4}) איזו מבין הטענות שלהלן היא הטענה החזקה ביותר אשר ידוע שהיא נכונה (שימו לב להבדל בין הכלה ⊆\subseteq להכלה ממש ⊂).

  1. אC2 ⊂ C1 ⊂ C3.
  2. באף אחת מבין התשובות א' ד' ה' ו' אינה ידועה כנכונה.
  3. גאף אחת מבין התשובות א' ד' ה' ו' אינה ידועה כנכונה וגם אם היינו משנים את C1 ל- C1 = DTime(2^n) אז היינו
  4. דC2 ⊂ C1 ⊆ C3.
  5. הC1 ⊆ C2 ⊆ C3.
  6. וC1 ⊂ C2 ⊂ C3.

תמלול ראשון מתוך עמוד המקור ב־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

2024 A · moed B

נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 2.pdf

Question 13Page 6Visual reading
View source scan — page 6Source page 6 from נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 2.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Assignment1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר:Topically related — not a duplicateAssignmentעבור שתי פונקציות f,g: N N נגדיר את מחלקת הסיבוכיות TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M וקיימים קבועים c,d>0, כך ש-M מכריעה את A ו…Topically related — not a duplicateAssignmentנתונות שבע מחלקות סיבוכיות: P,quad EXP,quad DTime(2 n 6),quad c 1DTime(n 2 c),quad c 1DTime(c cn),quad c 1DTime(c n c),quad c 1DTime(n n c). סדרו אותן…Topically related — not a duplicateAssignmentעבור f,g: N N נגדיר את TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M בעלת אלפבית קלט וקיימים קבועים c,d>0, כך ש-M מכריעה את A ולכל x *,Topically related — not a duplicateAssignmentנתונות שבע מחלקות הסיבוכיות: P,quad EXP,quad DTime(2 n 6),quad c 1DTime(n 2 c),quad c 1DTime(c cn),quad c 1DTime(c n c),quad c 1DTime(n n c). סדרו את…Topically related — not a duplicateAssignmentעבור כל אחת ממחלקות הסיבוכיות הבאות, קבעו אם היא מכילה את NP, מוכלת ב-NP, ושווה ל-NP - אם הדבר ידוע. הוכיחו את קביעותיכם. כאשר קובעים ששתי מחלקות שוות…Topically related — not a duplicate

Near variants — not duplicates