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

הוכיחו את הטענות הבאות: 1. BPP PSPACE. 2. RP סגורה לאיחוד. 3. BPP סגורה לחיתוך. 4. RP NP BPP. 5. BPP=BPP(5/6,5…

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

נוסח השאלה

הוכיחו את הטענות הבאות:

  1. BPP⊆PSPACEBPP\subseteq PSPACE.
  2. RPRP סגורה לאיחוד.
  3. BPPBPP סגורה לחיתוך.
  4. RP⊆NP∩BPPRP\subseteq NP\cap BPP.
  5. BPP=BPP(5/6,5/6)BPP=BPP(5/6,5/6).

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

ייחוס מדויק

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

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

מטלה

2026 א׳

2026א_06_תרגיל_6.md

שאלה 1עמוד 1נבדק אנושית

העמודים שמהם זה נכתב

1 עמודים

העמודים נבחרו לפי חפיפת מילים בין הטקסט כאן לתמלול העמוד — לא אומתו ידנית. הם הצעה לבדיקה, לא ציטוט.

תרגול המשך

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

בחינהנתונות 4 טענות הבאות. A. NP BPP(1/n,1). B. NP BPP(1-1/n,1). C. NP=BPP(1/n,1). D. NP=BPP(1-1/n,1). אם ידוע כי NP BPP, אילו מהטענות A,B,C,D שהובאו לעיל…דומה בנושא — לא כפילותבחינהנתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא כל מחלקת השפות A Σ* עבורן קיימת מכונת טיורינג M וקיים פולינום P כך שלכל x Σ*, רצה על x בזמן לכל היותר…דומה בנושא — לא כפילותבחינהאיזו מבין הטענות הבאות ידועה כנכונה ?דומה בנושא — לא כפילותבחינהתהאענה A,B Σ* כך ש- A,B RP. אילו מהטענות הבאות היא החזקה ביותר הידועה כנכונה?דומה בנושא — לא כפילותבחינהתהא D מחלקת השפות A Σ* עבורן קיימים מכונת טיורינג M עם זמן ריצה פולינומיאלי ופולינום q כך שלכל x Σ* מתקיים: אם x A אז Pr r ~ 0,1 q(|x|)[M(x,r) = True]…דומה בנושא — לא כפילותבחינהתהא Φ נוסחה בוליאנית מצורת CNF עם n משתנים ופחות מ- n logn פסוקיות. בכל פסוקית יש בדיוק m ליטרלים ממשתנים שונים (אך כמובן שבין פסוקיות שונות המשתנים א…דומה בנושא — לא כפילות