Complexity Atlas
HE
Source-backed question

שפה A ניתנת להכרעה ע"י מכונת טיורינג דטרמיניסטית שמשתמשת במקום O(n 2) לקלט באורך n. שפה B ניתנת לרדוקציה לשפה…

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

נוסח השאלה

שפה A ניתנת להכרעה ע"י מכונת טיורינג דטרמיניסטית שמשתמשת במקום O(n2)O(n^2) לקלט באורך n. שפה B ניתנת לרדוקציה לשפה A ע"י מ"ט דטרמיניסטית בזמן O(n3)O(n^3) לקלט באורך n. מהי המחלקה הקטנה ביותר ביחס להכלה שאליה ידוע שהכלה שאלייה שייכת שייכת?

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

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

2024 A · moed A

נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 1.pdf

Question 2Page 3Visual reading
View source scan — page 3Source page 3 from נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 1.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Assignment1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר:Topically related — not a duplicateAssignmentיהי אלפבית, תהיינה f,g: * * פונקציות, ותהיינה M f,M g מכונות טיורינג המחשבות את f,g, בהתאמה. תהא h: * * פונקציית ההרכבהTopically related — not a duplicateAssignmentעבור כל אחת ממחלקות הסיבוכיות שלהלן, קבעו האם היא מכילה את המחלקה NP, האם NP מוכלת בה, והאם היא שווה לה, אם ידוע. אחרת הוכיחו כי השאלה שקולה לשאלה פתו…Topically related — not a duplicateAssignmentתהיינה M f,M g מכונות טיורינג אשר מחשבות את הפונקציותTopically related — not a duplicateAssignmentנגדיר TISP(f,g) כמחלקת השפות הניתנות להכרעה על ידי מכונת טיורינג סטנדרטית בעלת סרט יחיד בזמן O(f(n)) ובזיכרון O(g(n)). 1. קבעו איזו מן המחלקותTopically related — not a duplicateAssignmentחזרו על הוכחת משפט היררכיית המקום שהוצגה בהרצאה, וודאו שהיא מובנת במלואה. השתמשו בה כדי להוכיח באופן מלא את משפט היררכיית הזמן. תהיינה f,g: N N. נניח…Topically related — not a duplicate

Near variants — not duplicates