Complexity Atlas
HE
Source-backed question

אנו מעוניינים להוכיח את הטענה הבאה: טענה: אם קיים קרוב 2000 לבעיית הסוכן הנוסע (TSP) ללא אי שוויון המשולש אז P…

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

נוסח השאלה

אנו מעוניינים להוכיח את הטענה הבאה: טענה: אם קיים קרוב 2000 לבעיית הסוכן הנוסע (TSP) ללא אי שוויון המשולש אז P = NP. ההוכחה תהיה דומה להוכחה שראינו בכיתה (עבור קרוב 2024) אך כשנבנה את הגרף השלם מגרף הקלט ניתן לכל קשת בגרף השלם שלא קיימת בגרף הקלט משקל αα במקום המשקל שנתנו בכיתה (כאשר αα עשוי להיות תלוי במספר קדקודי גרף הקלט שנסמנו ב- N). מבין הערכים הבאים, מה ערך αα המינימלי שיאפשר להוכיח את הטענה?

  1. אα = 1999N + 2.
  2. בα = 1999N.
  3. גα = 1999N + 1.
  4. דα = 2000N.
  5. הα = 2000N + 1.
  6. וα = 2000N + 2.

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

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

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

These are topic and lesson matches, not identical appearances.

Assignmentהיפרגרף 3-אחיד הוא זוג H=(V,E), כאשר V קבוצת קודקודים ו-E אוסף תת־קבוצות של V, כל אחת בגודל 3. כל קבוצה כזו היא היפר־קשת. כיסוי קודקודים של H הוא S V…Topically related — not a duplicateAssignmentנסמן ב-TSP-TI את תת־הקבוצה של TSP, גרסת ההכרעה של בעיית הסוכן הנוסע, שמכילה אך ורק גרפים המקיימים את אי־שוויון המשולש (*Triangle Inequality*). הוכיחו…Topically related — not a duplicateAssignmentהוכיחו כי TSP, בעיית הסוכן הנוסע שהוגדרה בשיעור, שייכת ל-NP.Topically related — not a duplicateAssignmentנקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר 1. 1. הוכיחו כי בעיית ההכרעה הבאה היא NP-שלמה: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה:…Topically related — not a duplicateAssignmentקליק בגרף לא מכוון הוא קבוצת קודקודים שכל שני קודקודים שונים בה מחוברים בקשת. גרף הוא איחוד זר של קליקים אם ניתן לחלק את קודקודיו לקבוצות שכל אחת מהן…Topically related — not a duplicateAssignmentקלט: קבוצה U, אוסף \F 1, ,F m\ של m תתי-קבוצות של U, שכל אחת מהן בגודל 3, ומספר טבעי k. שאלה: האם קיימת קבוצה S U, בגודל |S|=k, המקיימתTopically related — not a duplicate