הוכיחו כי DTime(n 10) אינה סגורה לרדוקציות זמן פולינומי. **רמז:** השתמשו במשפט ההיררכיה בז…

שאלה פתוחהq-dc042c2a2efe

נוסח השאלה

הוכיחו כי $DTime(n^{10})$ אינה סגורה לרדוקציות זמן פולינומי.

רמז: השתמשו במשפט ההיררכיה בזמן ובמשפט: לכל שתי שפות $A,B$ , אם $B\in P$ וגם $A$ אינה טריוויאלית, אז $B\le_p A$ .

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

Exact provenance

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ב_02_תרגיל_בית_2.md

Question 5Page 1Human reviewed