Complexity Atlas
HE
Source-backed question

תהי φ נוסחה בצורת CNF בעלת 1000 פסוקיות וכך שבכל פסוקית יש בדיוק k ליטרלים ממשתנים שונים (אך כמובן שפסוקיות שו…

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירהq-46b3d725c68b

נוסח השאלה

תהי φφ נוסחה בצורת CNF בעלת 1000 פסוקיות וכך שבכל פסוקית יש בדיוק k ליטרלים ממשתנים שונים (אך כמובן שפסוקיות שונות יכולות להכיל ליטרלים מאותם המשתנים). מבין הבאים, מהו הערך המינימלי של k שמבטיח שהנוסחה ספיקה?

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

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

2025 A · moed A

נושא 131111 קבוצה 13111101 שנה 2025 סמסטר 1 מועד 1.pdf

Question 12Page 11Visual reading
View source scan — page 11Source page 11 from נושא 131111 קבוצה 13111101 שנה 2025 סמסטר 1 מועד 1.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Lesson5. הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאלה: האם קיימת קבוצה S V בגודל |S| = k עבו…Topically related — not a duplicateAssignment1. תהא נוסחה בוליאנית מצורת 5CNF בעלת m הסגרים, שבכל אחד מהם מופיעים חמישה משתנים שונים, בחיוב או בשלילה. 1. חשבו את תוחלת מספר ההסגרים המסופקים בנוסח…Topically related — not a duplicateAssignmentבכל סעיף מוצגות טענה ואלגוריתם. קבעו אם האלגוריתם מגדיר רדוקציית זמן פולינומי המוכיחה את הטענה, והוכיחו את קביעתכם. נשתמש בהגדרות: - נוסחת CNF ספיקה ב…Topically related — not a duplicateAssignmentהוכיחו שבעיות ההכרעה הבאות שייכות ל-P. 1. קלט: נוסחה בוליאנית מצורת 1CNF. שאלה: האם ספיקה? 2. קלט: נוסחה בוליאנית מצורת CNF. שאלה: האם קיימת השמה שנות…Topically related — not a duplicateAssignmentיהיו k N ו-A \0, ,k\. נגדיר את הבעיה kSAT A: קלט: נוסחה בצורת k-CNF. שאלה: האם קיימת השמה כך שבכל פסוקית מספר הליטרלים המקבלים אמת שייך ל-A? לדוגמה, ב…Topically related — not a duplicateAssignmentמולטיגרף הוא גרף לא מכוון שעשויות להיות בו קשתות מקבילות ולולאות. הקלט לבעיית Max-Cut-Multi הוא מולטיגרף G=(V,E) ומספר טבעי k, והשאלה היא האם קיים חתך…Topically related — not a duplicate

Near variants — not duplicates