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}).$

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

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.

Assignment

2025

2025_02_תרגיל_2.md

Question 3Page 1Human reviewed

The pages this was written from

1 page

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Lecture 25 · page 1תרגילים
Shared wordsקבעו · קביעתכם · שקולה · פתוחה · נכונה

נוסח השאלה

Appearances by source document

2025

The pages this was written from

Related questions from another source type