Complexity Atlas
HE
Source-backed question

הוכיחו כי TSP, בעיית הסוכן הנוסע שהוגדרה בשיעור, שייכת ל-NP.

0Exams1Assignments0Lessons1Source documents
שאלה פתוחהq-28a0033f977d

נוסח השאלה

הוכיחו כי TSPTSP, בעיית הסוכן הנוסע שהוגדרה בשיעור, שייכת ל-NPNP.

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

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.

Assignment

2026 A

2026א_04_תרגיל_4.md

Question 4Page 1Human reviewed
Further practice

These are topic and lesson matches, not identical appearances.

Examנזכיר את בעיית הסוכן הנוסע. קלט: גרף לא מכוון שלם G = (V,E) עם משקלות w: E ℕ ומספר k ℕ. שאלה: האם קיים מעגל פשוט ב G העובר דרך כל הקודקודים ומשקלו לכל…Topically related — not a duplicateExamשמתקיים P=NP. בבעיית הספיקות (3-SAT) מציין n את מספר המשתנים, ו-m את מספר הפסוקיות. בבעיית הסוכן-הנוסע (TSP) ובבעיית הקליקה מציין n את מספר הקדקודים ב…Topically related — not a duplicateExamיגרור שמתקיים P=NP . הן בבעיית הסוכן-הנוסע (TSP) והן בבעיית הקליקה n מציין את מספר הקדקודים בגרף. .ד. שלוש התשובות (א-ג) נכונות.Topically related — not a duplicateExamאנו מעוניינים להוכיח את הטענה הבאה: טענה: אם קיים קרוב 2000 לבעיית הסוכן הנוסע (TSP) ללא אי שוויון המשולש אז P = NP. ההוכחה תהיה דומה להוכחה שראינו בכ…Topically related — not a duplicateExamנזכיר את בעיית האריזה בתאים. קלט: n-ייה של מספרים a 1, ,a n (0,1] ומספר טבעי k . שאלה: האם קיימת חלוקה של a 1,a 2, ,a n ל-k תאים כך שסכום המספרים בכל…Topically related — not a duplicateExamהיפר-גרף הוא זוג H=(V,E) כאשר V קבוצת קדקודים ו- E אוסף של תת-קבוצות של V. כל תת-קבוצה כזו נקראת קשת היפר- קשת (היפר-קשתות שונות עשויות בעלות מספר קדק…Topically related — not a duplicate