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

נגדיר את מחלקת הסיבוכיות ZPP כמחלקת כל השפות A שעבורן קיימת מכונת טיורינג הסתברותית M וקיים פולינום p, כך שלכל…

0בחינות1מטלות0שיעורים1מסמכי מקור
שאלה פתוחהq-194d5a36f2fc

נוסח השאלה

נגדיר את מחלקת הסיבוכיות ZPPZPP כמחלקת כל השפות AA שעבורן קיימת מכונת טיורינג הסתברותית MM וקיים פולינום pp, כך שלכל xx מתקיים

E[timeM(x)]≤p(∣x∣).E[time_M(x)]\le p(|x|).

כלומר, תוחלת זמן הריצה של MM על xx היא פולינומית ב-∣x∣|x|, אך אין הבטחה לגבי זמן הריצה הגרוע ביותר. כמו כן, לכל xx, בכל ריצה שבה MM עוצרת על xx היא מחזירה את התשובה הנכונה.

הראו כי

ZPP=RP∩coRP.ZPP=RP\cap coRP.

נוסח מטלה שנבדק אנושית.

ייחוס מדויק

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

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

מטלה

2026 א׳

2026א_06_תרגיל_6.md

שאלה 5עמוד 1נבדק אנושית
תרגול המשך

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

בחינהנתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא כל מחלקת השפות A Σ* עבורן קיימת מכונת טיורינג M וקיים פולינום P כך שלכל x Σ*, רצה על x בזמן לכל היותר…דומה בנושא — לא כפילותבחינהעבור 0 < α < 1 נתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A ⊆ Σ * עבור קיימת מכונת טיורינג דטרמיניסטית M הרצה בזמן פולינומיאלי בא…דומה בנושא — לא כפילותבחינהעבור 1<α<0 נתונות מחלקות הסתביכויות הבאות. I. המחלקה C 1 היא כל השפות A Σ* עבורן קיימת מכונת טיורינג דטרמיניסטית M הרצה בזמן פולינומי בגודל הקלט x Σ*,…דומה בנושא — לא כפילותבחינהעבור 0< <1 נתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A * עבורן קיימת מכונת טיורינג דטרמיניסטית M וקיים פולינום p כך שלכל x *, M…דומה בנושא — לא כפילותבחינהתהא D מחלקת השפות A Σ* עבורן קיימים מכונת טיורינג M עם זמן ריצה פולינומיאלי ופולינום q כך שלכל x Σ* מתקיים: אם x A אז Pr r ~ 0,1 q(|x|)[M(x,r) = True]…דומה בנושא — לא כפילותבחינהעבור 0 < α < 1 נתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A Σ* עבורן קיימת מכונת טיורינג דטרמיניסטית M הרצה בזמן פולינומי בגודל ה…דומה בנושא — לא כפילות

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