Complexity Atlas
HE
Source-backed question

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

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירהq-6d663e73b92f

נוסח השאלה

מבין המחלקות הבאות, מה המחלקה הקטנה ביותר ביחס ביחס להכלה שסגורה תחת רדוקציות פולינומיאליות.
  1. אPSPACE.
  2. בDTime(n^{20}).
  3. גDSpace(n^{20}).
  4. דDTime(2^{n^{20}}).
  5. הDSpace(2^{n^{20}}).
  6. וEXP.

תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

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.

Exam

2024 A · moed A

נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 1.pdf

Question 4Page 5Visual reading
View source scan — page 5Source page 5 from נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 1.pdf Open full size

The pages this was written from

2 pages

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.

Further practice

These are topic and lesson matches, not identical appearances.

Assignment1. הוכיחו כי PSPACE סגורה תחת רדוקציות פולינומיות. 2. הוכיחו בשתי דרכים כי NP PSPACE: פעם אחת באמצעות ההגדרה הסטנדרטית ופעם אחת באמצעות הגדרת המוודא.…Topically related — not a duplicateAssignment1. הוכיחו כי המחלקות הבאות סגורות לרדוקציות זמן פולינומיאלי: 1. PSPACE. 2. c 1DTime(n n c). 2. תהא B=\0\ שפה המכילה מחרוזת אחת בלבד. 1. הוכיחו כי לכל…Topically related — not a duplicateAssignmentהוכיחו כי מחלקת הסיבוכיות DTime(n 10) אינה סגורה לרדוקציות זמן פולינומי. **רמז:** השתמשו במשפט ההיררכיה בזמן ובמשפט הבא שהוכחנו בשיעור: לכל שתי שפות A…Topically related — not a duplicateAssignmentהוכיחו כי DTime(n 10) אינה סגורה לרדוקציות זמן פולינומי. **רמז:** השתמשו במשפט ההיררכיה בזמן ובמשפט: לכל שתי שפות A,B, אם B P וגם A אינה טריוויאלית, א…Topically related — not a duplicateAssignmentהוכיחו כי המחלקות הבאות סגורות תחת רדוקציות זמן פולינומי: 1. BPP; 2. RP; 3. coRP.Topically related — not a duplicateLessonii. קלט: גרף מכוון G = (V,E) ושני קודקודים s,t V. שאלה: האם קיים בגרף G מסלול מ-s ל-t ש-3 מחלק את מספר קשתותיו? נסמן את השפה ב-A. נוכיח כי A NL. נתבונ…Topically related — not a duplicate

Near variants — not duplicates