Complexity Atlas
HE
Source-backed question

נזכר בדרדוקציה SAT P dHP שהראינו בכיתה. נניח שהנוסחה שבקלט יש 100 פסוקיות שכל אחת מהן מכילה 3 ליטרלים ממשתנים…

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

נוסח השאלה

נזכר בדרדוקציה SAT≤PdHPSAT \le_P dHP שהראינו בכיתה. נניח שהנוסחה שבקלט יש 100 פסוקיות שכל אחת מהן מכילה 3 ליטרלים ממשתנים שונים (אך כמובן שפסוקיות שונות עשויות להכיל ליטרלים מאותם משתנים). נניח גם שהנוסחה ספיקה במובן Not All Equal (NAE). נסמן ב- M את מספר מסלולי ההמילטון בפלט הרדוקציה. מה הטענה החזקה ביותר הידועה נכונה?

  1. אM≥2^32.
  2. בM≥2^2.
  3. גM≥2^4.
  4. דM≥2^8.
  5. הM≥2^16.
  6. וM≥2^64.

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

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

Question 12Page 11Visual reading

Byte-identical aliases: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 1.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 1.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 1.pdf

View source scan — page 11Source page 11 from נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 1.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

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