מפת הסיבוכיות
EN
שאלה מבוססת מקור

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

1בחינות0מטלות0שיעורים1מסמכי מקור
שאלת רב־ברירה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. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

ייחוס מדויק

מופעים לפי מסמך מקור

כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.

בחינה

2023 ב׳ · מועד ב׳

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

שאלה 13עמוד 7קריאה חזותית

עותקים זהים של אותו מסמך: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 2.pdf

הצגת צילום המקור — עמוד 7עמוד מקור 7 מתוך נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf פתיחה בגודל מלא
תרגול המשך

אלו התאמות לפי נושא ושיעור — לא מופעים זהים של אותה שאלה.

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

וריאציות קרובות — לא כפילויות