Complexity Atlas
HE
Source-backed question

ראינו בהרצאה רדוקציה מ- 3-SAT ל- Subset Sum. בהוכחת נכונות הרדוקציה התאמנו בין השמה שמספקת לנוסחה שבקלט לבין מ…

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

נוסח השאלה

ראינו בהרצאה רדוקציה מ- 3-SAT ל- Subset Sum. בהוכחת נכונות הרדוקציה התאמנו בין השמה שמספקת לנוסחה שבקלט לבין מספרים בפלט שסכומם הוא הסכום הנדרש. נניח שהקלט לרדוקציה הוא הנוסחה (x1∨x2)∧(x1∨x3)(x1\vee x2)\wedge(x1\vee x3) ונסתכל על ההשמה המספקת שנותנת ערך True לכל שלושת המשתנים. מה מספר המספרים בפלט הרדוקציה שסכומם הוא הסכום הנדרש ושאליהם ההוכחה מתאימה את ההשמה הזו?

  1. א5.
  2. ב2.
  3. ג3.
  4. ד4.
  5. ה6.
  6. ו7.

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

2024 A · moed B

נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 2.pdf

Question 8Page 4Visual reading
View source scan — page 4Source page 4 from נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 2.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Assignmentבשאלה זו נוכיח כי בעיית Bin-Packing שראינו בשיעור היא NP-שלמה. הקלט הוא סדרת מספרים a 1,a 2, ,a n (0,1] ומספר טבעי k. השאלה היא האם ניתן לחלק את המספר…Topically related — not a duplicateAssignmentבכל סעיף מוצגות טענה ואלגוריתם. קבעו אם האלגוריתם מגדיר רדוקציית זמן פולינומי המוכיחה את הטענה, והוכיחו את קביעתכם. נשתמש בהגדרות: - נוסחת CNF ספיקה ב…Topically related — not a duplicateAssignmentיהיו k N ו-A \0, ,k\. נגדיר את הבעיה kSAT A: קלט: נוסחה בצורת k-CNF. שאלה: האם קיימת השמה כך שבכל פסוקית מספר הליטרלים המקבלים אמת שייך ל-A? לדוגמה, ב…Topically related — not a duplicateAssignmentנגדיר את בעיית IS: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה: האם קיימת ב-G קבוצה בלתי תלויה בגודל לפחות k? 1. נתונה הרדוקציה הבאה מ-SAT. לכל…Topically related — not a duplicateAssignmentמולטיגרף הוא גרף לא מכוון שעשויות להיות בו קשתות מקבילות ולולאות. הקלט לבעיית Max-Cut-Multi הוא מולטיגרף G=(V,E) ומספר טבעי k, והשאלה היא האם קיים חתך…Topically related — not a duplicateAssignmentבכל אחד מן הסעיפים הבאים מוצגות טענה ואלגוריתם. קבעו בכל סעיף האם האלגוריתם המוצג מגדיר רדוקציית זמן פולינומי המוכיחה את הטענה, והוכיחו את טענותיכם. מ…Topically related — not a duplicate

Near variants — not duplicates