Complexity Atlas
HE
Source-backed question

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

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

נוסח השאלה

תהא AA בעיית ההכרעה הבאה.

קלט: גרף לא מכוון GG ומספר kk.

שאלה: האם קיימים ב-GG לפחות kk קודקודים כך שבין כל שניים מהם אין מסלול.

תהא BB בעיית ההכרעה הבאה.

קלט: גרף לא מכוון GG ומספר kk.

שאלה: האם קיימים ב-GG לפחות kk קודקודים כך שבין כל שניים מהם אין קשת.

נתונות הטענות הבאות:

i. A∈PA\in P

ii. B≤pAB\le_p A

iii. B∈NPB\in NP

אילו מהטענות הנתונות ידועות כנכונות?

  1. אטענות i,iii.
  2. בטענה ii.
  3. גטענות ii,iii.
  4. דטענות i,ii.
  5. הטענה iii.
  6. וטענה i.

נוסח מטלה שנבדק אנושית.

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

2026 B · moed A

מ-2026 סמסטר ב מועד א (טופס נבחן)

Question 4Page 1Human reviewed

This question has no source scan. The only surviving copy is a marked personal exam script — it carries an identity number on every page, over a student's answers and a grader's red corrections. Only the printed question text was taken from it; the handwriting, the marks and the grades are not part of the question and are not shown.

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. יהי G=(V,E) גרף שאינו דווקא פשוט - ייתכנו בו קשתות מקבילות ולולאות - ויהי k מספר טבעי. נסמן ב-G' את הגרף הפשוט המתקבל מ-G באמצעות הוספת שני קודקודי…Topically related — not a duplicateAssignmentנקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר 1. 1. הוכיחו כי בעיית ההכרעה הבאה היא NP-שלמה: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה:…Topically related — not a duplicateAssignmentנגדיר את בעיית IS: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה: האם קיימת ב-G קבוצה בלתי תלויה בגודל לפחות k? 1. נתונה הרדוקציה הבאה מ-SAT. לכל…Topically related — not a duplicateAssignment1. יהי G=(V,E) גרף שאינו בהכרח פשוט — ייתכנו בו קשתות מקבילות ולולאות — ויהי k מספר טבעי. נסמן ב-G' את הגרף הפשוט המתקבל מ-G באמצעות הוספת שני קודקודי…Topically related — not a duplicateAssignmentקליק בגרף לא מכוון הוא קבוצת קודקודים שכל שני קודקודים שונים בה מחוברים בקשת. גרף הוא איחוד זר של קליקים אם ניתן לחלק את קודקודיו לקבוצות שכל אחת מהן…Topically related — not a duplicate

Near variants — not duplicates