Complexity Atlas
HE
Source-backed question

1. תהא נוסחה בוליאנית מצורת 5CNF בעלת m הסגרים, שבכל אחד מהם מופיעים חמישה משתנים שונים, בחיוב או בשלילה. 1. ח…

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

נוסח השאלה

  1. תהא φ\varphi נוסחה בוליאנית מצורת 5CNF5CNF בעלת mm הסגרים, שבכל אחד מהם מופיעים חמישה משתנים שונים, בחיוב או בשלילה.
    1. חשבו את תוחלת מספר ההסגרים המסופקים בנוסחה φ\varphi על ידי השמה מקרית מהתפלגות אחידה.
    2. חשבו את תוחלת מספר ההסגרים המסופקים במובן NAENAE בנוסחה φ\varphi על ידי השמה מקרית מהתפלגות אחידה.
    3. נסחו טענות "קיום" שנובעות משני הסעיפים הקודמים ונמקו אותן.
    4. כיצד היו משתנות התשובות אם היה נתון שבכל הסגר של φ\varphi מופיעים חמישה ליטרלים שונים — אך לא בהכרח חמישה משתנים שונים — ושמספר ההסגרים שבהם מופיעים משתנה ושלילתו הוא m0m_0?
  2. יהא G=(V,E)G=(V,E) גרף פשוט. מגרילים מהתפלגות אחידה צביעה מקרית של קודקודי GG ב-1010 צבעים. מהי תוחלת מספר הקשתות בגרף GG המחברות שני קודקודים בעלי צבעים שונים לפי צביעה זו? נסחו טענת "קיום" שנובעת מהחישוב ונמקו אותה.
  3. הוכיחו כי לכל nn טבעי קיים גרף תחרות על nn קודקודים שבו לפחות n!2n−1\frac{n!}{2^{n-1}} מסלולי המילטון.

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

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

2025

2025_06_תרגיל_6.md

Question 2Page 1Human reviewed

The pages this was written from

1 page

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