Complexity Atlas
HE
Source-backed question

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

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

נוסח השאלה

מבין המחלקות הבאות, מה המחלקה הקטנה ביותר ביחס להכלה שידוע לגביה שהיא סגורה תחת רדוקציות זמן פולינומיאלי.
  1. אNP.
  2. בPSPACE.
  3. גL.
  4. דNL.
  5. הDSpace(log^2 n).
  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 B

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

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

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.

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לכל טענה קבעו האם היא נכונה, אינה נכונה, או שקולה לשאלה פתוחה, והוכיחו את קביעתכם. השפה SAT-UNSAT היא שפת הזוגות ( 1, 2) של נוסחאות בוליאניות מצורת CN…Topically related — not a duplicateAssignment1. הוכיחו כי RP NP. 2. הוכיחו כי BPP PSPACE. 3. הוכיחו כי מחלקת הסיבוכיות RP סגורה לחיתוך, כלומר שאם A,B RP אז A B RP. 4. זהו את מחלקות הסיבוכיות שלהל…Topically related — not a duplicateAssignmentעבור כל אחת מן המחלקות הבאות קבעו אם היא מכילה את NP, אם היא מוכלת ב-NP, ואם היא שווה ל-NP, ככל שידוע; אחרת הוכיחו כי השאלה שקולה לשאלה פתוחה. 1. C 1:…Topically related — not a duplicateAssignment1. הוכיחו כי רדוקציות זמן פולינומי מקיימות טרנזיטיביות. כלומר, לכל A,B,C *, אם A p B וגם B p C, אז A p C. 2. הוכיחו כי EXP סגורה לרדוקציות זמן פולינומ…Topically related — not a duplicate

Near variants — not duplicates