Complexity Atlas
HE
Source-backed question

מי מבין המחלקות הבאות היא המחלקה הקטנה ביותר ביחס להכלה כך שידוע עוד שהמחלקה מוכלת בה DSpace(n 2)?

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

נוסח השאלה

מי מבין המחלקות הבאות היא המחלקה הקטנה ביותר ביחס להכלה כך שידוע עוד שהמחלקה מוכלת בה DSpace(n2)DSpace(n^2)?

  1. אDTime(n^{n^2}).
  2. בDTime(n^2).
  3. גDTime(2^{n^2}).
  4. דDTime(2^{n^3}).
  5. הDTime(2^{n^5}).
  6. וEXP.

תמלול ראשון מתוך עמוד המקור ב־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 13Page 7Visual 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 7Source page 7 from נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Assignmentנגדיר TISP(f,g) כמחלקת השפות הניתנות להכרעה על ידי מכונת טיורינג סטנדרטית בעלת סרט יחיד בזמן O(f(n)) ובזיכרון O(g(n)). 1. קבעו איזו מן המחלקותTopically related — not a duplicateAssignmentעבור כל אחת מן המחלקות הבאות קבעו אם היא מכילה את NP, אם היא מוכלת ב-NP, ואם היא שווה ל-NP, ככל שידוע; אחרת הוכיחו כי השאלה שקולה לשאלה פתוחה. 1. C 1:…Topically related — not a duplicateAssignmentעבור כל אחת ממחלקות הסיבוכיות שלהלן, קבעו האם היא מכילה את המחלקה NP, האם NP מוכלת בה, והאם היא שווה לה, אם ידוע. אחרת הוכיחו כי השאלה שקולה לשאלה פתו…Topically related — not a duplicateLessonii. קלט: גרף מכוון G = (V,E) ושני קודקודים s,t V. שאלה: האם קיים בגרף G מסלול מ-s ל-t ש-3 מחלק את מספר קשתותיו? נסמן את השפה ב-A. נוכיח כי A NL. נתבונ…Topically related — not a duplicateAssignmentתהי f פונקציה ניתנת לבניית זמן, ותהי g=o(f). נגדיר את שפת האלכסון המרופדתTopically related — not a duplicateAssignment1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר:Topically related — not a duplicate

Near variants — not duplicates