Complexity Atlas
HE
Source-backed question

נתונות שלוש מחלקות סיבוכיות: C 1 = DSpace(n 5) , C 2 = NSpace(n 3) , C 3 = EXP. איזו מבין הטענות שלהלן היא הטע…

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

נוסח השאלה

נתונות שלוש מחלקות סיבוכיות:C1=DSpace(n5),C2=NSpace(n3),C3=EXP: C_1 = DSpace(n^5) , C_2 = NSpace(n^3) , C_3 = EXP. איזו מבין הטענות שלהלן היא הטענה החזקה ביותר אשר ידוע שהיא נכונה? (שימו לב להבדל בין הכלה ⊆\subseteq להכלה ממש ⊂ ).

  1. אאף אחת מבין התשובות ב ג ד ה ו אינה ידועה נכונה.
  2. בC_1 ⊆ C_2 ⊆ C_3.
  3. גC_1 ⊆ C_2 ⊂ C_3.
  4. דC_2 ⊆ C_1 ⊆ C_3.
  5. הC_2 ⊆ C_1 ⊂ C_3.
  6. וC_1 ⊂ C_2 ⊂ C_3.

תמלול ראשון מתוך עמוד המקור ב־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 13Page 11Visual reading
View source scan — page 11Source page 11 from נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 1.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Assignment1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר:Topically related — not a duplicateAssignmentנתונות שבע מחלקות סיבוכיות: P,quad EXP,quad DTime(2 n 6),quad c 1DTime(n 2 c),quad c 1DTime(c cn),quad c 1DTime(c n c),quad c 1DTime(n n c). סדרו אותן…Topically related — not a duplicateAssignmentעבור f,g: N N נגדיר את TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M בעלת אלפבית קלט וקיימים קבועים c,d>0, כך ש-M מכריעה את A ולכל x *,Topically related — not a duplicateAssignmentעבור כל אחת ממחלקות הסיבוכיות הבאות, קבעו אם היא מכילה את NP, מוכלת ב-NP, ושווה ל-NP - אם הדבר ידוע. הוכיחו את קביעותיכם. כאשר קובעים ששתי מחלקות שוות…Topically related — not a duplicateAssignmentעבור שתי פונקציות f,g: N N נגדיר את מחלקת הסיבוכיות TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M וקיימים קבועים c,d>0, כך ש-M מכריעה את A ו…Topically related — not a duplicateAssignment1. הוכיחו כי בעיות ההכרעה שלהלן שייכות למחלקת הסיבוכיות L. 1. קלט: גרף לא מכוון G=(V,E) וקבוצת קודקודים S V. שאלה: האם הקבוצה S היא כיסוי קודקודים ב-G…Topically related — not a duplicate

Near variants — not duplicates