#computational_complexity #computational_models #computer_science

רדוקצייה

נאמר כי קיימת רדוקציה מבעיה $A$ לבעיה $B$ אם אפשר לפתור את $A$ על ידי גישה לאלגוריתם שפותר את $B$ .

רדוקציית קארפ

תהיינה $S_{1}, S_{2}$ בעיות הכרעה. רדוקציית קארפ מ $S_{1}$ ל $S_{2}$ הינה פונקצייה $f$ שניתנת לחישוב בזמן פולינומי ומקיימת

\forall_{x} : x \in S_{1} \leftrightarrow f (x) \in S_{2}

Pasted image 20230325150519.png|300

טרנזיטיביות של רדוקציות קארפ

רידוקציות בין 3 בעיות $A, B, C$ הן טרנזיטיביות כלומר אם קיימת רידוקציית קארפ מ $A \to B$ וריקודציית קארפ מ $B \to C$ אז קיימת רידוקציית קארפ $A \to C$

הערה

אם יש רדוקציית קארפ מ $S_{1}$ ל $S_{2}$ יש גם רדוקציית קוק מ $S_{1}$ ל $S_{2}$ שכן נוכל לכל $x$ לחשב $f (x)$ ולבדוק האם $f (x) \in S_{2}$

משפט: אם $S_{2} \in P$ וכן יש רדוקציית קארפ מ $S_{1}$ ל $S_{2}$ אזי $S_{1} \in P$ .
הוכחה: נבנה את האלגוריתם ל $S_{1}$ בהינתן קלט $x$

חשב $f (x)$
החזר $f (x) \in S_{2}$

IS ו 3-SAT

נבנה רידוקצייה קארפ מבעיות ההכרעה של 3-SAT ל IS כלומר

\begin{matrix} S_{3 S A T} = {ρ | ρ is a CNF formula that can be saturated} \\ S_{I S} = {(G, k) | G is a graph with an independent set of size k} \end{matrix}

כדי להוכיח שקיימת רידוקצייה כזאת נרצה למצוא פונקצייה $f$ חשיבה פולינומית שתקיים

f (ρ) = (G, k) \in S_{I S} \leftrightarrow ρ \in S_{3 S A T}

נתאר את הרידוקצייה באמצעות דוגמה על הנוסחה

ρ = (x_{1} \lor \overset{―}{x_{2}} \lor x_{3}) \land (\overset{―}{x_{1}} \lor \overset{―}{x_{3}} \lor x_{4}) \land (\overset{―}{x_{1}} \lor \overset{―}{x_{4}} \lor x_{3})

נבנה את $G_{ρ}$ באופן הבא:

כל שלישייה תהווה שלושה קודקודים שכולם מחוברים אחד לשני עם קשת.
בין כל ליטרל נעביר קשת לשלישה שלו אם קיימת כזאת.

כך למשל עבור הנוסחה הנ״ל נקבל

Pasted image 20230325152832.png|500

וניתן לראות שקיימת השמה מספקת מהצורה $x_{1}, x_{4}, x_{3}$ שזאת גם קבוצה $k = 3$ בלתי תלויה של קודקודים.

תיאור הרידוקציה (קלט: $ρ$ ב $3 C N F$ )
נבנה גרף $G$ ומספר $k$ באופן הבא:
כל מופע של ליטרל ב $ρ$ יהיה קודקוד ולכן מספר הקודקודים ב $G$ הוא מספר הפסוקיות כפול $3$ .
הקשתות ב $G$ יהיו בין כל הליטרלים תחת אותה הפסוקית ובין כל ליטרל ושלילתו.
$k$ מהווה את מספר הפסוקיות ב $ρ$

הוכחה נכונות:
נרצה להוכיח שאם $ρ$ ספיקה אז $f (ρ) \in S_{I S}$ ובנוסף נוכיח את הcp של הכיוון השני כלומר $ρ$ לא ספיקה אז. $f (ρ) \notin S_{I S}$ .

$\leftarrow$ יהי $ρ$ ספיקה אז נוכיח שבגרף שאנחנו בונים יש $I S$ בגודל $k$ .
אם היא ספיקה אז בכל פסוקית יש לפחות ליטרל אחד שמקבל $T$ בכל פסוקית. נוכל לבחור ליטרל אחד בידיוק מכל פסוקית שקיבל $T$ והקודקודים שנבחרו מהווים קבוצה בת״ל בגודל מספר הפסוקיות. הקבוצה הזאת היא בת״ל כי לא ייתכן שבכל פסוקית ליטרל ושלילתו יהיו $T$ ולכן מאיך שבנינו את הגרף בין כל הקודקודים האחרים כשכל אחד מפסוקית אחרת לא תהיה קשת.

$\to$ אם $G$ מכילה קבוצה בת״ל בגודל $k$ קבוצה זאת חייבת לקחת בידיוק קודקוד אחד מכל עמודה (שקול לפסוקית) וכל שנשאר לעשות זה להציב True עבור הליטרלים שבחרנו.

כמעט קליקה

נאמר שקבוצת קודקודים $S$ בגרף $G = (V, E)$ היא כמעט קליקה אם יש קשתות בין כל זוג קודקודים ב $S$ למעט אחד.

נגדיר את בעיית ההכרעה

A l m o s t - C l i q u e = {(G, k) | G has an almost k size clique}

נרצה לבנות רידוקצייה קארפ מ Clique ל Almost-Clique באופן הבא:
בהנתן גרף $(G, k)$ נבנה $(G^{'}, k^{'})$ כך ש

(G, k) \in C l i q u e \leftrightarrow (G^{'}, k^{'}) \in A l m o s t - c l i q u e

נבנה זאת על ידי

V^{'} = V \cup {u^{'}, u^{''}}

E^{'} = E \cup {(v, u^{'}), (v, u^{''}) | v \in V}

ויתקיים $k^{'} = k + 2$

כלומר הוספנו שתי קודקודים וחיברנו אותם עם כל הקודקודים בגרף הישן.
נוכיח שאם אחד הוא קליקה אז השני הוא כמעט קליקה.

נניח ש $(G, k)$ הוא קליקה ונסמן ב $S$ את הקליקה ב $G$ . לפי הבנייה ברור כי $S \cup {u^{'}, u^{''}}$ הוא כמעט קליקה בגודל $k + 2$ שכן אין קשת בין הקודקודים שהוספנו.

כעת נניח ש $(G^{'}, k^{'})$ היא כמעט קליקה ולכן קיימת כמעט קליקה $S^{'}$ בגודל $k^{'}$ .
אם שתי הקודקודים שהוספנו שייכים ל $S^{'}$ אז הקשת החסרה היא בהכרח $(u^{'}, u^{''})$ ולכן כשנוריד את הקודקודים האלו נקבל $S$ קליקה בגודל $k^{'} - 2$ ב $G$ .
אם זה לא המצב, קיימים שני קודקודים אחרים $u, v \in S^{'}$ שאין בינהם קשת ולכן נוכל פשוט להוריד את את אחד מהם ביחד עם הקודוקדים שהוספנו אם צריך ונקבל שוב קליקה.

הבחנה

לכל בעיית הכרעה $S$ יש רדוקציית קוק ל $\overset{―}{S}$
לא לכל בעיית הכרעה $S$ יש רדוקציית קארפ ל $\overset{―}{S}$ למשל אם $S$ היא קבוצת כל הקלטים ו $\overset{―}{S} = \emptyset$

קליקה ו IS

נבנה רידוקציית קארפ מ $I S$ ל $c l i q u e$ באופן הבא:
בהינתן $(G, k)$ קלט ל $I S$ נבנה $(G^{'}, k^{'})$ קלט ל $c l i q u e$ כך של

G = (V, E) \to G^{'} = (V, \overset{―}{E}), k^{'} = k

באופן הזה מתקיים ש $(G, k) \in I S \to (G, k^{'}) \in c l i q u e$ כי קיימת קבוצה בת״ל $S$ בגודל $k$ ולכן

u, v \in S \to (u, v) \notin E \to (u, v) \in \overset{―}{E}

ולכן בהכרח קיימת קליקה בגודל $k$ ב $G^{'}$ .
הכיוון השני זהה לחלוטין.

סגירות לרדוקציית קארפ

טענה:
המחלקה $P$ סגורה לרדוקציית קארפ (כלומר אם $S \in P$ ויש רדוקציית קארפ מ $S^{'}$ ל $S$ אז גם $S^{'} \in P$ ) והמחלקה $N P C$ לא סגורה לרדוקציית קארפ.

מסקנה: אם $P \neq N P$ אזי $P \cap N P C = \emptyset$ .

טענה:
המחלקה $N P$ סגורה לרדוקציית קארפ.

Pasted image 20230630235359.png
יהי $S \in N P$ לכן קיים מוודא $V$ ופולינום $P$ כך ש:

\begin{matrix} x \in S \leftrightarrow \exists_{y : | y | < P (| x |)} : V (x, y) = 1 \\ x \notin S \leftrightarrow \forall_{y : | y | < P (| x |)} : V (x, y) = 0 \end{matrix}

נניח כי יש רדוקציית קארפ מ $S^{'}$ ל $S$ כלומר קיימת פונקציה $f$ שניתנת לחישוב בזמן פולינומי ומקיימת

x \in S^{'} \leftrightarrow f (x) \in S

נגדיר מוודא $V^{'}$ עבור $S^{'}$ אשר מקבל זוג $(x, y)$ מחשב את $f (x)$ מחזיר את תשובת המוודא $V$ על $(f (x), y)$ .

האלגוריתם של $V^{'}$ הינו פולינומי כי $V$ ו $f$ רצים בזמן פולינומי , נסמן את הפולינום החוסם את $| f (x) |$ כ $g (x)$ ויתקיים

x \in S^{'} \to f (x) \in S \to \exists_{y} : V (f (x), y) = 1 \to \exists_{y : | y | \leq P (g (x))} : V^{'} (x, y) = 1

באותו אופן

x \notin S^{'} \to f (x) \notin S \to \forall_{y} : V (f (x), y) = 0 \to \forall_{y} : V^{'} (x, y) = 0