Complexity Atlas
HE
Source-backed question

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

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

נוסח השאלה

נתבונן בשפות הבאות: A={⟨G,k⟩∣A=\left\{\langle G,k\rangle \mid\right. ב-GG יש קליקה בגודל kk בדיוק }\left.\right\} B={⟨G,k⟩∣B=\left\{\langle G,k\rangle \mid\right. ב-GG יש קליקה בגודל kk לפחות }\left.\right\} C={⟨G,k⟩∣C=\left\{\langle G,k\rangle \mid\right. גודלה של קליקה מקסימלית ב-GG הוא k}\left.k\right\} ניזכר בסימון הבא: תהאנה A,BA,B שפות. A≡pBA\equiv_p B אם ורק אם (A≤pBA\le_p B וגם B≤pAB\le_p A). בחרו את הטענה המדויקת ביותר הידועה כנכונה:

  1. א

    A≡pCA\equiv_p C

  2. ב

    A≡pCA\equiv_p C אם ורק אם P=NPP=NP

  3. ג

    A≡pBA\equiv_p B

  4. ד

    A≡pB≡pCA\equiv_p B\equiv_p C

  5. ה

    A≤pBA\le_p B אבל לא קיימת רדוקציית זמן פולינומית מ-BB ל-AA.

  6. ואף אחת מהתשובות א'-ה' אינה נכונה.

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

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 A · moed B

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

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

Near variants — not duplicates