Complexity Atlas
HE
Source-backed question

נסמן C 1 = c 1 DTime(n (n c)) , C 2 = c 1 DTime(n (2 cn)) , C 3 = c 1 DTime(n (n cn)) איזו מהטענות הבאות היא ה…

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירהq-917dc8f32132

נוסח השאלה

נסמן C1=⋃c≥1DTime(n(nc)),C2=⋃c≥1DTime(n(2cn)),C3=⋃c≥1DTime(n(ncn))C_1 = \bigcup_{c\ge1} DTime(n^{(n^c)}) , C_2 = \bigcup_{c\ge1} DTime(n^{(2^{cn})}) , C_3 = \bigcup_{c\ge1} DTime(n^{(n^{cn})}) איזו מהטענות הבאות היא התוזקה היותר הידועה כנכונה.

  1. אC_1 = EXP ⊂ C_2 ⊂ C_3
  2. בC_1 = EXP ⊆ C_2 = C_3
  3. גC_1 ⊆ C_2 ⊆ C_3 ⊆ EXP
  4. דC_1 ⊂ C_2 = EXP ⊆ C_3
  5. הC_1 ⊂ C_2 ⊂ EXP ⊂ C_3
  6. וC_1 = EXP ⊂ C_2 = C_3

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

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

Question 7Page 11Visual reading
View source scan — page 11Source page 11 from מ-נושא 131111 סיבוכיות מועד 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 duplicateAssignment1. הוכיחו כי המחלקות הבאות סגורות לרדוקציות זמן פולינומיאלי: 1. PSPACE. 2. c 1DTime(n n c). 2. תהא B=\0\ שפה המכילה מחרוזת אחת בלבד. 1. הוכיחו כי לכל…Topically related — not a duplicateAssignmentכזכור, הגדרנו: E= d 1DTime(2 d n). נגדיר: E 2= d 1DTime(2 d n 2). 1. הוכיחו כי אם E=PSPACE, אז E 2 PSPACE. 2. הסיקו כי E PSPACE.Topically related — not a duplicateAssignmentעבור f,g: N N נגדיר את TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M בעלת אלפבית קלט וקיימים קבועים c,d>0, כך ש-M מכריעה את A ולכל x *,Topically related — not a duplicate

Near variants — not duplicates