Complexity Atlas
HE
Source-backed question

הוכיחו כי אם קיים אלגוריתם פולינומי בעל יחס קירוב 1.49 ל-Bin-Packing, אז P=NP.

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

נוסח השאלה

הוכיחו כי אם קיים אלגוריתם פולינומי בעל יחס קירוב 1.491.49 ל-Bin-PackingBin\text{-}Packing, אז P=NPP=NP.

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

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 B

2026ב_03_תרגיל_בית_3.md

Question 7Page 1Human reviewed

The pages this was written from

2 pages

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.

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

Near variants — not duplicates