Complexity Atlas
HE
Source-backed question

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

0Exams1Assignments0Lessons1Source documents
שאלה פתוחה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.

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

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.

Assignment

2026 A

2026א_06_תרגיל_6.md

Question 5Page 1Human reviewed
Further practice

These are topic and lesson matches, not identical appearances.

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

Near variants — not duplicates