Complexity Atlas
HE
Source-backed question

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

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

נוסח השאלה

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

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

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

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

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

These are topic and lesson matches, not identical appearances.

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

Near variants — not duplicates