Complexity Atlas
HE
Source-backed question

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

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

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

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 B

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

Question 1Page 1Human reviewed

The pages this was written from

3 pages

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