Complexity Atlas
HE
Source-backed question

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

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירהq-24c82b25b81b

נוסח השאלה

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

  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 ⊆ C_2 = EXP ⊆ 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

2025 C · moed B

shalon_131111_2025_s3_g06_moed2.pdf

Question 1Page 3Visual reading

Byte-identical aliases: נושא 131111 קבוצה 13111106 שנה 2025 סמסטר 3 מועד 2.pdf

View source scan — page 3Source page 3 from shalon_131111_2025_s3_g06_moed2.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