Complexity Atlas
HE
Source-backed question

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

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

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

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 1Page 1Human reviewed

The pages this was written from

1 page

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Further practice

These are topic and lesson matches, not identical appearances.

Examנתונות 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 שהובאו לעיל…Topically related — not a duplicateExamנתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא כל מחלקת השפות A Σ* עבורן קיימת מכונת טיורינג M וקיים פולינום P כך שלכל x Σ*, רצה על x בזמן לכל היותר…Topically related — not a duplicateExamאיזו מבין הטענות הבאות ידועה כנכונה ?Topically related — not a duplicateExamתהאענה A,B Σ* כך ש- A,B RP. אילו מהטענות הבאות היא החזקה ביותר הידועה כנכונה?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תהא Φ נוסחה בוליאנית מצורת CNF עם n משתנים ופחות מ- n logn פסוקיות. בכל פסוקית יש בדיוק m ליטרלים ממשתנים שונים (אך כמובן שבין פסוקיות שונות המשתנים א…Topically related — not a duplicate