מפת הסיבוכיות
EN
פונקציית הזהות

3SAT ≤p SAT

3SAT≤pSAT\mathrm{3SAT}\le_p\mathrm{SAT}, ומכאן 3SAT∈NP\mathrm{3SAT}\in\mathrm{NP}.

הבנייה

על קלט ⟨φ⟩\langle\varphi\rangle — החזר ⟨φ⟩\langle\varphi\rangle.

זו פונקציית הזהות, וזה הכול. הרדוקציה הזאת נכללת כאן דווקא מפני שהיא נראית ריקה מתוכן: היא מדגימה שכיוון הרדוקציה הוא הטענה כולה. הכיוון הזה — מ-3SAT\mathrm{3SAT} אל SAT\mathrm{SAT} — אומר ש-SAT\mathrm{SAT} קשה לפחות כמו 3SAT\mathrm{3SAT}, וזה הכיוון ה"קל", כי כל נוסחת 3CNF היא בפרט נוסחת CNF. הכיוון המעניין הוא ההפוך, והוא דורש עבודה אמיתית.

נכונות — שני הכיוונים

3SAT ∈ ⟹ SAT ∈

נניח ⟨φ⟩∈3SAT\langle\varphi\rangle\in\mathrm{3SAT}. אזי φ\varphi היא נוסחת 3CNF ספיקה. כל נוסחת 3CNF היא בפרט נוסחת CNF, ולכן φ\varphi היא נוסחת CNF ספיקה, כלומר ⟨φ⟩∈SAT\langle\varphi\rangle\in\mathrm{SAT}.

SAT ∈ ⟹ 3SAT ∈

נניח ⟨φ⟩∈SAT\langle\varphi\rangle\in\mathrm{SAT} כאשר φ\varphi היא נוסחת 3CNF (זהו הקלט שקיבלנו). אזי φ\varphi ספיקה, ומכיוון שהיא 3CNF מתקיים ⟨φ⟩∈3SAT\langle\varphi\rangle\in\mathrm{3SAT} לפי ההגדרה.

קלט שאינו קידוד תקין של נוסחת 3CNF נדחה על ידי שתי השפות כאחת, ולכן אינו מפר את השקילות.

סיבוכיות הרדוקציה

זמןO(|φ|)
מקוםO(|φ|)
גודל הפלט|φ|

זמן ההעתקה בלבד. הפלט זהה לקלט באורכו.

מה זה קונה

יחד עם SAT∈NP\mathrm{SAT}\in\mathrm{NP} וסגירות NP\mathrm{NP} תחת ≤p\le_p מתקבל 3SAT∈NP\mathrm{3SAT}\in\mathrm{NP}.

מלכודות

  • הזהות היא רדוקציה חוקית רק כשהיא באמת משמרת את שני הכיוונים. באותו שיעור בדיוק נדחתה הזהות כרדוקציה מ-3COL\mathrm{3COL} ל-4COL\mathrm{4COL} — שם הכיוון הראשון עובד והשני קורס. ה"טריוויאליות" של הזהות אינה מבטיחה דבר.

מאיפה זה נקרא

  • שיעור 8משפט 4: 3SAT≤pSAT\mathrm{3SAT} \le_p \mathrm{SAT}, ומכאן 3SAT∈NP\mathrm{3SAT}\in\mathrm{NP}