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

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

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

נוסח השאלה

נגדיר את 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ב_04_תרגיל_בית_4.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 הרצה בזמן פולינומי בגודל ה…דומה בנושא — לא כפילות

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