שאלת רב־ברירהq-cbefc4816d5a
נוסח השאלה
יהיו A ו- B שפות. ידוע ש- A ניתנת לרדוקציית זמן פולינומיאלי ל- B וש- A שלמה ל- EXP (ביחס לרדוקציות זמן פולינומיאלי). נתבונן בטענות הבאות: (i B ∈ NL. (ii B ∈ P. (iii B ∈ NP. (iv B ∈ PSPACE. (v B ∈ EXP. עבור כמה מהטענות שלעיל ידוע שהן בהכרח אינן נכונות?
תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.
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.
Exam
2025 A · moed A
נושא 131111 קבוצה 13111101 שנה 2025 סמסטר 1 מועד 1.pdf
Question 9Page 7Visual reading
View source scan — page 7
Open full size