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

הוכיחו את הטענות הבאות: 1. BPP PSPACE. 2. לכל A,B RP מתקיים A B RP. 3. לכל A,B BPP מתקיים A B BPP. 4. RP NP BP…

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

נוסח השאלה

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

  1. BPP⊆PSPACEBPP\subseteq PSPACE.
  2. לכל A,B∈RPA,B\in RP מתקיים A∪B∈RPA\cup B\in RP.
  3. לכל A,B∈BPPA,B\in BPP מתקיים A∩B∈BPPA\cap B\in BPP.
  4. RP⊆NP∩BPPRP\subseteq NP\cap BPP.

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

ייחוס מדויק

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

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

מטלה

2026 ב׳

2026ב_04_תרגיל_בית_4.md

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

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

3 עמודים

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

תרגול המשך

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

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