מפת הסיבוכיות
EN
שאלה מבוססת מקור

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

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

ייחוס מדויק

מופעים לפי מסמך מקור

כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.

בחינה

2025 ג׳ · מועד ב׳

shalon_131111_2025_s3_g06_moed2.pdf

שאלה 1עמוד 3קריאה חזותית

עותקים זהים של אותו מסמך: נושא 131111 קבוצה 13111106 שנה 2025 סמסטר 3 מועד 2.pdf

הצגת צילום המקור — עמוד 3עמוד מקור 3 מתוך shalon_131111_2025_s3_g06_moed2.pdf פתיחה בגודל מלא
תרגול המשך

אלו התאמות לפי נושא ושיעור — לא מופעים זהים של אותה שאלה.

מטלה1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר:דומה בנושא — לא כפילותמטלהעבור שתי פונקציות f,g: N N נגדיר את מחלקת הסיבוכיות TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M וקיימים קבועים c,d>0, כך ש-M מכריעה את A ו…דומה בנושא — לא כפילותמטלהנתונות שבע מחלקות סיבוכיות: 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). סדרו אותן…דומה בנושא — לא כפילותמטלה1. הוכיחו כי המחלקות הבאות סגורות לרדוקציות זמן פולינומיאלי: 1. PSPACE. 2. c 1DTime(n n c). 2. תהא B=\0\ שפה המכילה מחרוזת אחת בלבד. 1. הוכיחו כי לכל…דומה בנושא — לא כפילותמטלהכזכור, הגדרנו: E= d 1DTime(2 d n). נגדיר: E 2= d 1DTime(2 d n 2). 1. הוכיחו כי אם E=PSPACE, אז E 2 PSPACE. 2. הסיקו כי E PSPACE.דומה בנושא — לא כפילותמטלהעבור f,g: N N נגדיר את TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M בעלת אלפבית קלט וקיימים קבועים c,d>0, כך ש-M מכריעה את A ולכל x *,דומה בנושא — לא כפילות

וריאציות קרובות — לא כפילויות