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

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

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

נוסח השאלה

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

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

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

ייחוס מדויק

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

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

מטלה

2026 א׳

2026א_06_תרגיל_6.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…דומה בנושא — לא כפילות

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