Complexity Atlas
HE
Source-backed question

טענה: קיימות מחלקות D E כך ש- c 100 DTime(c n) D E EXP וכן שההכלה ממש ניתנת להוכחה בשיטות [לא ברור] ממשפט ההיר…

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירהq-5ae8684c66ef

נוסח השאלה

טענה: קיימות מחלקות D⊂ED\subset E כך ש−⋃c≥100DTime(cn)⊆D⊂E⊆EXP- \bigcup_{c\ge100} DTime(c^n)\subseteq D\subset E\subseteq EXP וכן שההכלה ממש ניתנת להוכחה בשיטות [לא ברור] ממשפט ההירריכיה בזמן (בנוסח שראינו). איזה מההגדים הבאים לגבי הטענה הוא החזקה ביותר ידוע כנכון?

  1. אהטענה נכונה ו- D -י E יכולים להיות DTime(2^{n^2}) ו- DTime(2^{3n^2}), בהתאמה.
  2. בהטענה אינה נכונה.
  3. גהטענה נכונה ו- D -י E יכולים להיות DTime(2^{n^2}) ו- DTime(2^{2n^2}), בהתאמה.
  4. דהטענה נכונה ו- D -י E יכולים להיות DTime(2^{n^2}) ו- ⋃_{c≥1} DTime(2^{cn^2}), בהתאמה.
  5. ההטענה נכונה ו- D -י E יכולים להיות DTime(2^{n^2}) ו- ⋃_{c≥100} DTime(2^{cn^2}), בהתאמה.
  6. והטענה נכונה יותר מאחד מהגדים א' ג' ד' ה' נכון.

תמלול ראשון מתוך עמוד המקור ב־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

2023 B · moed B

נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf

Question 9Page 5Visual reading

Byte-identical aliases: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 2.pdf

View source scan — page 5Source page 5 from נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Assignment1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר: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 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 duplicateLesson1. בפברואר 2025, פירסם ריאן ויליאמס מאוניברסיטת MIT תוצאה פורצת דרך לפיה לכל פונקציה f: ℕ ℕ המקיימת n f(n) לכל n, מתקיים DTime(f) ⊆ DSpace(√(f ⋅ log 2…Topically related — not a duplicateAssignmentתהי f פונקציה ניתנת לבניית זמן, ותהי g=o(f). נגדיר את שפת האלכסון המרופדתTopically related — not a duplicateAssignmentעבור שתי פונקציות f,g: N N נגדיר את מחלקת הסיבוכיות TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M וקיימים קבועים c,d>0, כך ש-M מכריעה את A ו…Topically related — not a duplicate