מפת הסיבוכיות
EN
שאלה מבוססת מקור

הוכיחו כי השפות 3NAE ו-IS הן NP-שלמות.

0בחינות1מטלות0שיעורים1מסמכי מקור
שאלה פתוחהq-27a188eb547e

נוסח השאלה

הוכיחו כי השפות 3NAE3NAE ו-ISIS הן NPNP-שלמות.

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

ייחוס מדויק

מופעים לפי מסמך מקור

כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.

מטלה

2026 ב׳

2026ב_02_תרגיל_בית_2.md

שאלה 2עמוד 1נבדק אנושית

העמודים שמהם זה נכתב

1 עמודים

העמודים נבחרו לפי חפיפת מילים בין הטקסט כאן לתמלול העמוד — לא אומתו ידנית. הם הצעה לבדיקה, לא ציטוט.

תרגול המשך

אלו התאמות לפי נושא ושיעור — לא מופעים זהים של אותה שאלה.

בחינהב. בעיית ההכרעה A מוגדרת כלהלן. קלט : נוסחה בוליאנית φ מצורת CNF שכל משתנה שלה מופיע בה 3 פעמים בדיוק (בצורת חיוב ו/או שלילה). שאלה : האם φ ספיקה? הוכ…דומה בנושא — לא כפילותבחינהנזכר בדרדוקציה SAT P dHP שהראינו בכיתה. נניח שהנוסחה שבקלט יש 100 פסוקיות שכל אחת מהן מכילה 3 ליטרלים ממשתנים שונים (אך כמובן שפסוקיות שונות עשויות לה…דומה בנושא — לא כפילותבחינהנזכיר את בעיית הסוכן הנוסע. קלט: גרף לא מכוון שלם G = (V,E) עם משקלות w: E ℕ ומספר k ℕ. שאלה: האם קיים מעגל פשוט ב G העובר דרך כל הקודקודים ומשקלו לכל…דומה בנושא — לא כפילותבחינהבאחד מהתרגילים בקורס תוארה רדוקציה מהשפה 4-NAE לשפה 3-NAE (תזכורת: 3-NAE הייא שפת הנוסחאות בצורת 3-CNF שיש להם השמה וכך שמתקיים שבכל פסוקית יש לפחות ל…דומה בנושא — לא כפילותבחינהנתאר להלן רדוקציה מ- 3-SAT ל- IS (תזכורת: IS היא שפת הזוגות <G,k> של גרף ומספר k כך שבגרף G יש קבוצה בלתי תלויה בגודל k). הרדוקציה: בהינתן קידוד של נו…דומה בנושא — לא כפילותשיעור5. הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאלה: האם קיימת קבוצה S V בגודל |S| = k עבו…דומה בנושא — לא כפילות