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

נתונות שבע מחלקות סיבוכיות: P,quad EXP,quad DTime(2 n 6),quad c 1DTime(n 2 c),quad c 1DTime(c cn),quad c 1DTim…

0בחינות1מטלות0שיעורים1מסמכי מקור
שאלה פתוחהq-1edfed327768

נוסח השאלה

נתונות שבע מחלקות סיבוכיות:

P,quadEXP,quadDTime(2n6),quad⋃c≥1DTime(n2c),quad⋃c≥1DTime(ccn),quad⋃c≥1DTime(cnc),quad⋃c≥1DTime(nnc).P,quad EXP,quad DTime(2^{n^6}),quad \bigcup_{c\ge1}DTime(n^{2^c}),quad \bigcup_{c\ge1}DTime(c^{cn}),quad \bigcup_{c\ge1}DTime(c^{n^c}),quad \bigcup_{c\ge1}DTime(n^{n^c}).

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

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

ייחוס מדויק

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

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

מטלה

2026 ב׳

2026ב_01_תרגיל_בית_1.md

שאלה 4עמוד 1נבדק אנושית
תרגול המשך

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

שיעור1. בפברואר 2025, פירסם ריאן ויליאמס מאוניברסיטת MIT תוצאה פורצת דרך לפיה לכל פונקציה f: ℕ ℕ המקיימת n f(n) לכל n, מתקיים DTime(f) ⊆ DSpace(√(f ⋅ log 2…דומה בנושא — לא כפילותבחינהנתונות שלוש מחלקות סיבוכיות: C 1 = DSpace(n 5) , C 2 = NSpace(n 3) , C 3 = EXP. איזו מבין הטענות שלהלן היא הטענה החזקה ביותר אשר ידוע שהיא נכונה? (שימ…דומה בנושא — לא כפילותבחינהטענה: קיימות מחלקות D E כך ש- c 100 DTime(c n) D E EXP וכן שההכלה ממש ניתנת להוכחה בשיטות [לא ברור] ממשפט ההירריכיה בזמן (בנוסח שראינו). איזה מההגדים…דומה בנושא — לא כפילותבחינהנתונות שלוש מחלקות סיבוכיות: .C1 = DTime(2 n 4) , C2 = DSpace(n 3) , C3 = c>1 DTime(2 cn 4) איזו מבין הטענות שלהלן היא הטענה החזקה ביותר אשר ידוע שהיא…דומה בנושא — לא כפילותבחינהיובל רצתה להוכיח את הטענה הבאה: אם DSpace(n 10) P אז DSpace(n 50) P בעזרת טיעוני ריפוד. את ההוכחה היא התחילה כך: נניח ש-DSpace(n 10) P. תהא A DSpace(n…דומה בנושא — לא כפילותבחינהנסמן: C 1= c 1 DTime (n (2 c) ), C 2= c 1 DTime (n (n c) ), C 3= c 1 DTime (n (cn) ) איזו מהטענות הבאות ידועה כנכונה?דומה בנושא — לא כפילות

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