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

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

נוסח השאלה

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

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

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

ייחוס מדויק

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

מטלה

2026ב_02_תרגיל_בית_2.md

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