Complexity Atlas
HE
Source-backed question

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

0Exams1Assignments0Lessons1Source documents
שאלה פתוחה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.

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

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.

Assignment

2026 A

2026א_02_תרגיל_2.md

Question 2Page 1Human reviewed
Further practice

These are topic and lesson matches, not identical appearances.

Lesson1. בפברואר 2025, פירסם ריאן ויליאמס מאוניברסיטת MIT תוצאה פורצת דרך לפיה לכל פונקציה f: ℕ ℕ המקיימת n f(n) לכל n, מתקיים DTime(f) ⊆ DSpace(√(f ⋅ log 2…Topically related — not a duplicateExamטענה: קיימות מחלקות D E כך ש- c 100 DTime(c n) D E EXP וכן שההכלה ממש ניתנת להוכחה בשיטות [לא ברור] ממשפט ההירריכיה בזמן (בנוסח שראינו). איזה מההגדים…Topically related — not a duplicateExamנתונות שלוש מחלקות סיבוכיות: .C1 = DTime(2 n 4) , C2 = DSpace(n 3) , C3 = c>1 DTime(2 cn 4) איזו מבין הטענות שלהלן היא הטענה החזקה ביותר אשר ידוע שהיא…Topically related — not a duplicateLessonהוכחה: תהי A PSPACE. אזי קיימת מכונה M A כך שקיים פולינום p כך ש-M A מכריעה את A וגם לכל x Σ*, space M A(x) p(|x|). תהי B P A. אזי קיימת מכונה M B עם…Topically related — not a duplicateLesson4. עבור מספר טבעי k וקבוצה A 0,1,...,k נגדיר את בעיית ההכרעה kSAT A כלהלן. קלט: נוסחה בוליאנית φ מצורת kCNF. שאלה: האם קיימת השמה עבור משתני הנוסחה φ…Topically related — not a duplicateExamנסמן: C 1= c 1 DTime (n (2 c) ), C 2= c 1 DTime (n (n c) ), C 3= c 1 DTime (n (cn) ) איזו מהטענות הבאות ידועה כנכונה?Topically related — not a duplicate