הרדוקציה שמוכיחה שהשפה TQBF הינה קשה ביחוס למחלקה PSPACE, מקבלת כקלט מכונת טיורינג M יחד ע…

שאלת רב־ברירהq-4c0dc5038251

נוסח השאלה

הרדוקציה שמוכיחה שהשפה TQBF הינה קשה ביחוס למחלקה PSPACE, מקבלת כקלט מכונת טיורינג M יחד עם קלט x. הרדוקציה מניבה כפלט פסוק $φ = φ(C_1,C_2,T)$ שפרושו "יש חישוב של M על x שעובר מקונפיגורציה $C_1$ לקונפיגורציה $C_2$ תוך לכל היותר T צעדים."

א(40%) רשמו בצורה רקורסיבית את הפסוק φ(C_1,C_2,T)
ב(30%) נתחו את אורך הפסוק φ(C_1,C_2,T)
ג(30%), הסבירו האם זמן החישוב של הרדוקציה מקיים Time(φ) ≥ 2^{Θ(S×S)} במקרה הרע.

תמלול ראשון מתוך עמוד המקור ב־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

2024 C · moed A

נושא 131111 קבוצה 13111106 שנה 2024 סמסטר 3 מועד 1.pdf

Question 1Page 7Visual reading

View source scan — page 7

Source page 7 from נושא 131111 קבוצה 13111106 שנה 2024 סמסטר 3 מועד 1.pdf

Open full size

נוסח השאלה

Appearances by source document

2024 C · moed A

Related questions from another source type