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

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

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

נוסח השאלה

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

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

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

ייחוס מדויק

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

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

מטלה

2026 ב׳

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

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

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

3 עמודים

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

תרגול המשך

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

בחינהמבין המחלקות הבאות, מה המחלקה הקטנה ביותר ביחס להכלה שידוע לגביה שהיא סגורה תחת רדוקציות זמן פולינומיאלי.דומה בנושא — לא כפילותבחינהא. הוכיחו כי EXP סגורה תחת רדוקציות זמן פולינומי. ב. תהאנה A, B Σ* שפות. רדוקציית זמן מעריכי מ A ל B היא מכונת טיורינג דטרמיניסטית M המקיימת את שתי הת…דומה בנושא — לא כפילותבחינהמבין המחלקות הבאות, מה המחלקה הקטנה ביותר ביחס ביחס להכלה שסגורה תחת רדוקציות פולינומיאליות.דומה בנושא — לא כפילותבחינהעבור כל אחת מהטענות הבאות קבעו האם היא נכונה, שגויה או שקולה לשאלה פתוחה (במקרה זה יש לציין איזו שאלה פתוחה). הוכיחו את תשובותיכם. א. טענה 1: לכל [0,1…דומה בנושא — לא כפילותבחינהנזכר בשפות הבאות: Subset-Sum= \ a 1, ,a n,s . קיימת תת קבוצה של \a 1, ,a n\ שסכומה .s \ Partition= \ a 1, ,a n . קיימת חלוקה של \a 1, ,a n\ לשתי קבוצו…דומה בנושא — לא כפילותבחינהתהאנה A,B Σ* שפות. רדוקציית זמן מעריכי מ A ל B היא מכונת טיורינג דטרמיניסטית M המקיימת את שתי התכונות הבאות. ● קיים c 1 כך שלכל x Σ* מתקיים timeM(x) O…דומה בנושא — לא כפילות

וריאציות קרובות — לא כפילויות