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

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

נוסח השאלה

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

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

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

ייחוס מדויק

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

מטלה

2026א_03_תרגיל_3.md

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