Complexity Atlas
HE
Source-backed question

שמתקיים P=NP. בבעיית הספיקות (3-SAT) מציין n את מספר המשתנים, ו-m את מספר הפסוקיות. בבעיית הסוכן-הנוסע (TSP) ו…

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

נוסח השאלה

שמתקיים P=NP. בבעיית הספיקות (3-SAT) מציין n את מספר המשתנים, ו-m את מספר הפסוקיות. בבעיית הסוכן-הנוסע (TSP) ובבעיית הקליקה מציין n את מספר הקדקודים בגרף.
  1. אפקטור n^{-(2/3)} עבור בעיית הקליקה.
  2. דאף תשובה מבין (א-ג) אינה נכונה.
  3. בפקטור 2^n עבור הסוכן הנוסע.
  4. השלוש התשובות (א-ג) נכונות.
  5. גפקטור 6/7 עבור 3-SAT.
  6. ושתיים מהתשובות (א-ג) נכונות.

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

2023 C · moed A

נושא 131111 קבוצה 13111106 שנה 2023 סמסטר 3 מועד 1.pdf

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

These are topic and lesson matches, not identical appearances.

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