Complexity Atlas
HE
Source-backed question

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

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

נוסח השאלה

תהא 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 A

shalon_131111_2025_s3_g06_moed1.pdf

Question 5Page 5Visual reading

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

View source scan — page 5Source page 5 from shalon_131111_2025_s3_g06_moed1.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