Complexity Atlas
HE
Source-backed question

נגדיר את בעיית ההכרעה הבאה, MIN − VC קלט: גרף G ומספר טבעי k. שאלה: האם הגודל המינימלי של כיסוי בקודקודים\בצמת…

1Exams0Assignments0Lessons1Source documents
שאלה פתוחהq-ecfd882e356f

נוסח השאלה

נגדיר את בעיית ההכרעה הבאה,MIN−VC, MIN − VC קלט: גרף G ומספר טבעי k. שאלה: האם הגודל המינימלי של כיסוי בקודקודים\בצמתים ב G הוא k. עבור כל אחת מהטענות הבאות קבעו האם היא נכונה, שגויה או שקולה לשאלה פתוחה. א.MIN−VC. MIN − VC היא NP-קשה. (רמז: הזכרו ברדוקציה מ IS ל VC) (12 נק') ב.MIN−VC. MIN − VC היא NP-שלמה. (13 נק')

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

shalon_131111_2025_s3_g06_moed2.pdf

Question 1Page 13, 15Visual reading

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

View source scan — page 13Source page 13 from shalon_131111_2025_s3_g06_moed2.pdf Open full size
View source scan — page 15Source page 15 from shalon_131111_2025_s3_g06_moed2.pdf Open full size

The pages this was written from

1 page

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Further practice

These are topic and lesson matches, not identical appearances.

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