Complexity Atlas
HE
Source-backed question

נתבונן בשפות הבאות: A=\ G,k ב-G יש קליקה בגודל k בדיוק\ B=\ G,k ב-G יש קליקה בגודל k לפחות\ C=\ G,k k הוא גודל…

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

נוסח השאלה

נתבונן בשפות הבאות:

A={⟨G,k⟩∣A=\{\langle G,k\rangle\mid ב-GG יש קליקה בגודל kk בדיוק}\}

B={⟨G,k⟩∣B=\{\langle G,k\rangle\mid ב-GG יש קליקה בגודל kk לפחות}\}

C={⟨G,k⟩∣kC=\{\langle G,k\rangle\mid k הוא גודלה של הקליקה המקסימאלית ב-G}G\}

(כל הגרפים בשאלה אינם מכוונים).

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

i. A≤pBA\le_p B

ii. B≤pCB\le_p C

iii. C≤pAC\le_p A

אילו מהטענות הנתונות שקולות לשאלה פתוחה?

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

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

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 5Page 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.

Assignmentבכל אחד מן הסעיפים הבאים מוצגות טענה ואלגוריתם. קבעו בכל סעיף האם האלגוריתם המוצג מגדיר רדוקציית זמן פולינומי המוכיחה את הטענה, והוכיחו את טענותיכם. מ…Topically related — not a duplicateAssignmentבשאלה זו נעסוק בבעיות מעגל ומסלול המילטון בגרפים מכוונים ולא מכוונים. 1. נציע את הרדוקציה הבאה מן הבעיה DHC לבעיה UHC. בהינתן גרף מכוון G=(V,E) נבנה ג…Topically related — not a duplicateAssignment1. נוסחה בוליאנית מצורת kCNF היא ספיקה במובן NAE ‏(Not\ All\ Equal) אם קיימת השמה שעבורה בכל פסוקית יש ליטרל שערכו True וליטרל שערכו False. תהא kNAE ש…Topically related — not a duplicateAssignmentבכל סעיף מוצגות טענה ואלגוריתם. קבעו אם האלגוריתם מגדיר רדוקציית זמן פולינומי המוכיחה את הטענה, והוכיחו את קביעתכם. נשתמש בהגדרות: - נוסחת CNF ספיקה ב…Topically related — not a duplicateAssignmentנגדיר את בעיית IS: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה: האם קיימת ב-G קבוצה בלתי תלויה בגודל לפחות k? 1. נתונה הרדוקציה הבאה מ-SAT. לכל…Topically related — not a duplicateAssignment1. תהא נוסחה בוליאנית מצורת 5CNF בעלת m הסגרים, שבכל אחד מהם מופיעים חמישה משתנים שונים, בחיוב או בשלילה. 1. חשבו את תוחלת מספר ההסגרים המסופקים בנוסח…Topically related — not a duplicate

Near variants — not duplicates