Complexity Atlas
HE
Source-backed question

הוכיחו כי המחלקות הבאות סגורות תחת רדוקציות זמן פולינומי: 1. BPP; 2. RP; 3. coRP.

0Exams1Assignments0Lessons1Source documents
שאלה פתוחהq-32074ac3f7ab

נוסח השאלה

הוכיחו כי המחלקות הבאות סגורות תחת רדוקציות זמן פולינומי:

  1. BPPBPP;
  2. RPRP;
  3. coRPcoRP.

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

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 2Page 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מבין המחלקות הבאות, מה המחלקה הקטנה ביותר ביחס להכלה שידוע לגביה שהיא סגורה תחת רדוקציות זמן פולינומיאלי.Topically related — not a duplicateExamא. הוכיחו כי EXP סגורה תחת רדוקציות זמן פולינומי. ב. תהאנה A, B Σ* שפות. רדוקציית זמן מעריכי מ A ל B היא מכונת טיורינג דטרמיניסטית M המקיימת את שתי הת…Topically related — not a duplicateExamמבין המחלקות הבאות, מה המחלקה הקטנה ביותר ביחס ביחס להכלה שסגורה תחת רדוקציות פולינומיאליות.Topically related — not a duplicateExamעבור כל אחת מהטענות הבאות קבעו האם היא נכונה, שגויה או שקולה לשאלה פתוחה (במקרה זה יש לציין איזו שאלה פתוחה). הוכיחו את תשובותיכם. א. טענה 1: לכל [0,1…Topically related — not a duplicateExamנזכר בשפות הבאות: Subset-Sum= \ a 1, ,a n,s . קיימת תת קבוצה של \a 1, ,a n\ שסכומה .s \ Partition= \ a 1, ,a n . קיימת חלוקה של \a 1, ,a n\ לשתי קבוצו…Topically related — not a duplicateExamתהאנה A,B Σ* שפות. רדוקציית זמן מעריכי מ A ל B היא מכונת טיורינג דטרמיניסטית M המקיימת את שתי התכונות הבאות. ● קיים c 1 כך שלכל x Σ* מתקיים timeM(x) O…Topically related — not a duplicate

Near variants — not duplicates