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

כזכור, הגדרנו: E= d 1DTime(2 d n). נגדיר: E 2= d 1DTime(2 d n 2). 1. הוכיחו כי אם E=PSPACE, אז E 2 PSPACE. 2.…

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

נוסח השאלה

כזכור, הגדרנו:

E=⋃d≥1DTime(2d⋅n).E=\bigcup_{d\ge1}DTime(2^{d\cdot n}).

נגדיר:

E2=⋃d≥1DTime(2d⋅n2).E^2=\bigcup_{d\ge1}DTime(2^{d\cdot n^2}).
  1. הוכיחו כי אם E=PSPACEE=PSPACE, אז E2⊆PSPACEE^2\subseteq PSPACE.
  2. הסיקו כי E≠PSPACEE\ne PSPACE.

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

ייחוס מדויק

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

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

מטלה

2026 א׳

2026א_02_תרגיל_2.md

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

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

שיעור1. בפברואר 2025, פירסם ריאן ויליאמס מאוניברסיטת MIT תוצאה פורצת דרך לפיה לכל פונקציה f: ℕ ℕ המקיימת n f(n) לכל n, מתקיים DTime(f) ⊆ DSpace(√(f ⋅ log 2…דומה בנושא — לא כפילותבחינהטענה: קיימות מחלקות 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) איזו מבין הטענות שלהלן היא הטענה החזקה ביותר אשר ידוע שהיא…דומה בנושא — לא כפילותשיעורהוכחה: תהי A PSPACE. אזי קיימת מכונה M A כך שקיים פולינום p כך ש-M A מכריעה את A וגם לכל x Σ*, space M A(x) p(|x|). תהי B P A. אזי קיימת מכונה M B עם…דומה בנושא — לא כפילותשיעור4. עבור מספר טבעי k וקבוצה A 0,1,...,k נגדיר את בעיית ההכרעה kSAT A כלהלן. קלט: נוסחה בוליאנית φ מצורת kCNF. שאלה: האם קיימת השמה עבור משתני הנוסחה φ…דומה בנושא — לא כפילותבחינהנסמן: C 1= c 1 DTime (n (2 c) ), C 2= c 1 DTime (n (n c) ), C 3= c 1 DTime (n (cn) ) איזו מהטענות הבאות ידועה כנכונה?דומה בנושא — לא כפילות