מפת הסיבוכיות
EN
שאלה מבוססת מקור

א. הוכיחו כי לכל k טבעי, אם DSpace(n k) P אז DSpace(n 3k) P. ב. קבעו האם הטענה הבאה נכונה, שגויה או שקולה לשאל…

1בחינות0מטלות0שיעורים1מסמכי מקור
שאלה פתוחהq-6f7c2a18a32f

נוסח השאלה

א. הוכיחו כי לכל kk טבעי, אם DSpace(nk)⊆PDSpace(n^k)\subseteq P אז DSpace(n3k)⊆PDSpace(n^{3k})\subseteq P. ב. קבעו האם הטענה הבאה נכונה, שגויה או שקולה לשאלה פתוחה.

קיים kk טבעי כך ש-P=DSpace(nk)P=DSpace(n^k).

ניתן להשתמש בתוצאת סעיף א' גם אם לא הוכחתם אותה.

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

ייחוס מדויק

מופעים לפי מסמך מקור

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

בחינה

2026 ב׳ · מועד א׳

מ-2026 סמסטר ב מועד א (טופס נבחן)

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

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

תרגול המשך

אלו התאמות לפי נושא ושיעור — לא מופעים זהים של אותה שאלה.

מטלהעבור שתי פונקציות f,g: N N נגדיר את מחלקת הסיבוכיות TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M וקיימים קבועים c,d>0, כך ש-M מכריעה את A ו…דומה בנושא — לא כפילותמטלהיהי אלפבית, תהיינה f,g: * * פונקציות, ותהיינה M f,M g מכונות טיורינג המחשבות את f,g, בהתאמה. תהא h: * * פונקציית ההרכבהדומה בנושא — לא כפילותמטלהעבור כל אחת ממחלקות הסיבוכיות שלהלן, קבעו האם היא מכילה את המחלקה NP, האם NP מוכלת בה, והאם היא שווה לה, אם ידוע. אחרת הוכיחו כי השאלה שקולה לשאלה פתו…דומה בנושא — לא כפילותמטלהעבור מספר טבעי k ושתי פונקציות f,g, נגדיר את מחלקת הסיבוכיות TISP k(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M עם k סרטים, המכריעה את A, כך של…דומה בנושא — לא כפילותמטלה1. נניח כי DSpace(n 2) P. 1. הוכיחו כי DSpace(n k) P לכל k N, k 2. 2. הסיקו כי P=PSPACE. 2. קבעו אם הטענהדומה בנושא — לא כפילותמטלהעבור f,g: N N נגדיר את TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M בעלת אלפבית קלט וקיימים קבועים c,d>0, כך ש-M מכריעה את A ולכל x *,דומה בנושא — לא כפילות