Complexity Atlas
HE
Source-backed question

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

0Exams1Assignments0Lessons1Source documents
שאלה פתוחהq-27a188eb547e

נוסח השאלה

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

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

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

2026 B

2026ב_02_תרגיל_בית_2.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ב. בעיית ההכרעה A מוגדרת כלהלן. קלט : נוסחה בוליאנית φ מצורת CNF שכל משתנה שלה מופיע בה 3 פעמים בדיוק (בצורת חיוב ו/או שלילה). שאלה : האם φ ספיקה? הוכ…Topically related — not a duplicateExamנזכר בדרדוקציה SAT P dHP שהראינו בכיתה. נניח שהנוסחה שבקלט יש 100 פסוקיות שכל אחת מהן מכילה 3 ליטרלים ממשתנים שונים (אך כמובן שפסוקיות שונות עשויות לה…Topically related — not a duplicateExamנזכיר את בעיית הסוכן הנוסע. קלט: גרף לא מכוון שלם G = (V,E) עם משקלות w: E ℕ ומספר k ℕ. שאלה: האם קיים מעגל פשוט ב G העובר דרך כל הקודקודים ומשקלו לכל…Topically related — not a duplicateExamבאחד מהתרגילים בקורס תוארה רדוקציה מהשפה 4-NAE לשפה 3-NAE (תזכורת: 3-NAE הייא שפת הנוסחאות בצורת 3-CNF שיש להם השמה וכך שמתקיים שבכל פסוקית יש לפחות ל…Topically related — not a duplicateExamנתאר להלן רדוקציה מ- 3-SAT ל- IS (תזכורת: IS היא שפת הזוגות <G,k> של גרף ומספר k כך שבגרף G יש קבוצה בלתי תלויה בגודל k). הרדוקציה: בהינתן קידוד של נו…Topically related — not a duplicateLesson5. הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאלה: האם קיימת קבוצה S V בגודל |S| = k עבו…Topically related — not a duplicate