Complexity Atlas
HE
Source-backed question

תהא A בעיית ההכרעה הבאה. קלט: גרף מכוון G=(V,E) וקודקוד v V. שאלה: האם קיימים ב-G לפחות 3 מעגלים (מכוונים) העו…

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

נוסח השאלה

תהא A בעיית ההכרעה הבאה. קלט: גרף מכוון G=(V,E) וקודקוד v∈Vv\in V. שאלה: האם קיימים ב-G לפחות 3 מעגלים (מכוונים) העוברים דרך v. תהא B בעיית ההכרעה הבאה. קלט: גרף מכוון G=(V,E) וקודקוד v∈Vv\in V. שאלה: האם קיימים ב-G בדיוק 3 מעגלים העוברים דרך v. אילו מהטענות הבאות היא החזקה ביותר הידועה כנכונה?

  1. אA∈NL וגם B∈NL.
  2. בA∈coNL וגם B∈P.
  3. גA∈P וגם B∈P.
  4. דA∈DSpace(log^2n) וגם B∈NL.
  5. הA∈L וגם B∈NL.
  6. וA∈NL וגם B∈DSpace(log^2n).

תמלול ראשון מתוך עמוד המקור ב־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

2023 B · moed A

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

Question 2Page 3Visual reading

Byte-identical aliases: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 1.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 1.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 1.pdf

View source scan — page 3Source page 3 from נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 1.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Assignment1. הוכיחו כי בעיות ההכרעה שלהלן שייכות למחלקת הסיבוכיות L. 1. קלט: גרף לא מכוון G=(V,E) וקבוצת קודקודים S V. שאלה: האם הקבוצה S היא כיסוי קודקודים ב-G…Topically related — not a duplicateLessonii. קלט: גרף מכוון G = (V,E) ושני קודקודים s,t V. שאלה: האם קיים בגרף G מסלול מ-s ל-t ש-3 מחלק את מספר קשתותיו? נסמן את השפה ב-A. נוכיח כי A NL. נתבונ…Topically related — not a duplicateAssignment1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר:Topically related — not a duplicateLesson5. הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאלה: האם קיימת קבוצה S V בגודל |S| = k עבו…Topically related — not a duplicateAssignmentחזרו על הוכחת משפט היררכיית המקום שהוצגה בהרצאה, וודאו שההוכחה מובנת לכם במלואה. השתמשו בכך כדי להוכיח באופן מלא את משפט היררכיית הזמן. **משפט:** תהיי…Topically related — not a duplicateAssignmentנסתכל על בעיית כיסוי הקודקודים VC: קלט: גרף לא מכוון G=(V,E) ומספר טבעי k. שאלה: האם קיים בגרף G כיסוי קודקודים בגודל k? 1. הוכיחו כי קיים אלגוריתם לב…Topically related — not a duplicate

Near variants — not duplicates