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

הרדוקציה שמוכיחה שהשפה TQBF הינה קשה ביחוס למחלקה PSPACE, מקבלת כקלט מכונת טיורינג M יחד עם קלט x. הרדוקציה מנ…

1בחינות0מטלות0שיעורים1מסמכי מקור
שאלת רב־ברירהq-4c0dc5038251

נוסח השאלה

הרדוקציה שמוכיחה שהשפה TQBF הינה קשה ביחוס למחלקה PSPACE, מקבלת כקלט מכונת טיורינג M יחד עם קלט x. הרדוקציה מניבה כפלט פסוק φ=φ(C1,C2,T)φ = φ(C_1,C_2,T) שפרושו "יש חישוב של M על x שעובר מקונפיגורציה C1C_1 לקונפיגורציה C2C_2 תוך לכל היותר T צעדים."

  1. א(40%) רשמו בצורה רקורסיבית את הפסוק φ(C_1,C_2,T)
  2. ב(30%) נתחו את אורך הפסוק φ(C_1,C_2,T)
  3. ג(30%), הסבירו האם זמן החישוב של הרדוקציה מקיים Time(φ) ≥ 2^{Θ(S×S)} במקרה הרע.

תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

ייחוס מדויק

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

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

בחינה

2024 ג׳ · מועד א׳

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

שאלה 1עמוד 7קריאה חזותית
הצגת צילום המקור — עמוד 7עמוד מקור 7 מתוך נושא 131111 קבוצה 13111106 שנה 2024 סמסטר 3 מועד 1.pdf פתיחה בגודל מלא
תרגול המשך

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

מטלהתהיינה A,B שפות. רדוקציית זמן מעריכי מ-A ל-B היא מכונת טיורינג M המקיימת: - קיים c 1 כך שלכל x *,דומה בנושא — לא כפילותמטלהתהיינה A,B שפות. רדוקציית זמן מעריכי מ-A ל-B היא מכונת טיורינג M המקיימת: 1. קיים c 1 כך שלכל x *,דומה בנושא — לא כפילותמטלהעבור כל אחת ממחלקות הסיבוכיות שלהלן, קבעו האם היא מכילה את המחלקה NP, האם NP מוכלת בה, והאם היא שווה לה, אם ידוע. אחרת הוכיחו כי השאלה שקולה לשאלה פתו…דומה בנושא — לא כפילותמטלהעבור f,g: N N נגדיר את TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M בעלת אלפבית קלט וקיימים קבועים c,d>0, כך ש-M מכריעה את A ולכל x *,דומה בנושא — לא כפילותמטלהעבור כל אחת ממחלקות הסיבוכיות הבאות, קבעו אם היא מכילה את NP, מוכלת ב-NP, ושווה ל-NP - אם הדבר ידוע. הוכיחו את קביעותיכם. כאשר קובעים ששתי מחלקות שוות…דומה בנושא — לא כפילותמטלהעבור שתי פונקציות f,g: N N נגדיר את מחלקת הסיבוכיות TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M וקיימים קבועים c,d>0, כך ש-M מכריעה את A ו…דומה בנושא — לא כפילות