Complexity Atlas
HE
Source-backed question

תהא A בעיית ההכרעה הבאה. קלט: גרף מכוון G ומספר k. שאלה: האם קיים ב-G מעגל באורך לפחות k. תהא B בעיית ההכרעה ה…

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

נוסח השאלה

תהא A בעיית ההכרעה הבאה. קלט: גרף מכוון G ומספר k. שאלה: האם קיים ב-G מעגל באורך לפחות k. תהא B בעיית ההכרעה הבאה. קלט: גרף מכוון G ומספר k. שאלה: האם קיים ב-G מעגל פשוט באורך לפחות k. אילו מהטענות הבאות היא התשובה החזקה ביותר הידועה כנכונה?
  1. אטענות ב' ג' נכונות.
  2. בA ∈ coNL וגם B ∈ NP.
  3. גאם B ∈ NL אז P = NP.
  4. דאם A ∈ P אז NP = P.
  5. הA ∈ NL וגם B ∈ NL.
  6. ותשובות ב' ו-ד' נכונות.

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

2025 C · moed B

shalon_131111_2025_s3_g06_moed2.pdf

Question 2Page 3Visual reading

Byte-identical aliases: נושא 131111 קבוצה 13111106 שנה 2025 סמסטר 3 מועד 2.pdf

View source scan — page 3Source page 3 from shalon_131111_2025_s3_g06_moed2.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Lesson5. הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאלה: האם קיימת קבוצה S V בגודל |S| = k עבו…Topically related — not a duplicateAssignment1. הוכיחו כי בעיות ההכרעה שלהלן שייכות למחלקת הסיבוכיות L. 1. קלט: גרף לא מכוון G=(V,E) וקבוצת קודקודים S V. שאלה: האם הקבוצה S היא כיסוי קודקודים ב-G…Topically related — not a duplicateAssignment1. יהי G=(V,E) גרף שאינו דווקא פשוט - ייתכנו בו קשתות מקבילות ולולאות - ויהי k מספר טבעי. נסמן ב-G' את הגרף הפשוט המתקבל מ-G באמצעות הוספת שני קודקודי…Topically related — not a duplicateAssignmentנקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר 1. 1. הוכיחו כי בעיית ההכרעה הבאה היא NP-שלמה: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה:…Topically related — not a duplicateAssignment1. יהי G=(V,E) גרף שאינו בהכרח פשוט — ייתכנו בו קשתות מקבילות ולולאות — ויהי k מספר טבעי. נסמן ב-G' את הגרף הפשוט המתקבל מ-G באמצעות הוספת שני קודקודי…Topically related — not a duplicateAssignment1. נגדיר את בעיית ההכרעה A כלהלן: קלט: נוסחה בוליאנית מצורת CNF ומספר טבעי k. שאלה: האם המספר המרבי של הסגרים שהשמה יכולה לספק בנוסחה הוא בדיוק k? 1.…Topically related — not a duplicate

Near variants — not duplicates