1. נניח כי DSpace(n 2) P. 1. הוכיחו כי DSpace(n k) P לכל k N, k 2. 2. הסיקו כי P=PSPACE. 2…

שאלה פתוחהq-9b0eda45cfa6

נוסח השאלה

נניח כי $DSpace(n^2)\subseteq P$ $D S p a ce (n^{2}) \subseteq P$ .
1. הוכיחו כי $DSpace(n^k)\subseteq P$ לכל $k\in\mathbb N$ , $k\ge2$ .
2. הסיקו כי $P=PSPACE$ .
קבעו אם הטענה $P=DSpace(n^2)$ נכונה, שגויה, או שקולה לבעיה פתוחה. הוכיחו את קביעתכם.
הוכיחו שאם $NTime(n^5)\subseteq TISP(n^8,n^3),$ אז $NTime(2^{5n})\subseteq TISP(2^{8n},2^{3n}).$

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

ייחוס מדויק

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

מטלה

2025_02_תרגיל_2.md

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

1 עמודים

העמודים נבחרו לפי חפיפת מילים בין הטקסט כאן לתמלול העמוד — לא אומתו ידנית. הם הצעה לבדיקה, לא ציטוט.

שיעור 25 · עמוד 1תרגילים
מילים משותפותקבעו · קביעתכם · שקולה · פתוחה · נכונה