#computational_complexity #computational_models #computer_science

NP-completeness

NP-hardness :
עבור בעיית הכרעה $S^{'}$ , זאת תקרא $N P$ -קשה ( $N P H$ ) אם קיימת רדוקציית קארפ מכל בעייה $S \in N P$ ל $S^{'}$ .

NP-completeness :
נאמר ש $S^{'}$ היא NP-שלמה אם היא $N P$ -קשה וגם $S^{'} \in N P$ .

משפט: קיימת בעיה שהיא $N P$ -שלמה
הוכחה: נשתמש ב מכונת טיורינג אוניברסלית $u$ . נזכיר שמכונת טיורינג אוניברסלית $u (⟨ M, x ⟩)$ מקבלת כקלט תיאור של מכונת טיורינג $M$ וקלט על המכונה ומחזירה $M (x)$ .

נגדיר את בעיית ההכרעה $S_{u}$ הבאה:

\begin{matrix} S_{u} = { \\ ⟨ M, x, 1^{t} ⟩ | \exists_{y : | y | \leq t} : M (x, y) = \\ 1 \land M determine the input after at most t steps \\ } \end{matrix}

כמו כן נשים לב ש $M$ זאת מכונת טיורינג שמקבלת 2 קלטים ו $1^{t} = \underset{t times}{\underset{⏟}{1 \circ 1 \circ 1 \circ 1 \dots}}$
זאת אכן בעיית $N P$ -שלמה, נוכיח זאת.

$S_{u} \in N P$ - נוכל להגדיר מוודא פולינומי מהצורה $V_{S_{u}} (⟨ M, x, 1^{t} ⟩, y)$ כאשר $| y | \leq t and | y | \leq | ⟨ M, x, 1^{t} ⟩ |$ כלומר $y$ חסום פולינומית באורך הקלט. והמוודא יעבוד באופן הבא:
1. הרץ את $u$ על $M (x, y)$ לכל היותר $t$ צעדים.
2. אם התקבלה תשובה במהלך הריצה החזר $t r u e$ אחרת החזר $f a l s e$ .
מהגדרה מתקיים $\exists_{y : | y | \leq P (| ⟨ M, x, 1^{t} ⟩ |)} : V_{S_{u}} (⟨ M, x, 1^{t} ⟩, y) = 1 \leftrightarrow ⟨ M, x, 1^{t} ⟩ \in S_{u}$ כדרוש.
$S_{u}$ היא שלמה - נראה שלכל $S \in N P$ קיימת רדוקציית קארפ מ $S$ ל $S_{u}$ . נוכל לבנות את $f$ פונקציית המרת הקלטים באופן הבא

f (x) = ⟨ V_{S_{}}, x, 1^{P_{V_{S_{}}} (| x | + P^{*} (| x |))} ⟩

כאשר $V_{S}$ הוא המוודא הפולינומי של $S$ . הקלט ל $V_{S}$ אורכו $| x | + | y | \leq | x | + P^{*} (| x |)$ כלומר פולינומי לאורך הקלט.
יהי $P_{V_{S}}$ הפולינום החוסם את זמן הריצה של $V_{S}$ כפונקצייה של אורך הקלט שלו. כלומר

T_{V_{S}} (| x | + | y |) \leq P_{V_{S}} (| x | + | y |) \leq P_{V_{S}} (| x | + P^{*} (| x |))

כאשר $T_{V_{S}}$ זאת פונקציית זמן הריצה של $V_{S}$ על קלט באורך מסויים. אכן נקבל ש $x \in S$ אמ״מ קיים $y$ חסום פולינומית ב $P^{*}$ כך ש $V_{S} (x, y) = 1$ אמ״מ $f (x) \in S_{u}$ שכן השתמשנו באלגוריתם הוידאו כייצוג של המכונה שלנו. כדרוש.

Cook-Levin

משפט cook-levin אומר שבעית SAT היא $N P$ -שלמה.
ההוכחה שלו דורשת להסתכל על בעיה אחרת $C S A T$ - נתון מעגל בוליאני ויש להכריע האם יש לו השמה מספקת.
מעגל בוליאני - הוא גרף ללא מעגלים מכוון שקודקודיו מתחלקים ל3 סוגים

קודקודי קלט- ללא קשתות נכנסות
קודקודי פלט - ללא קשתות יוצאות, קשת נכנסת אחת
שערים- קודקודים עם $d e g_{i n} \leq 2$ ו $d e g_{o u t} \geq 1$

Pasted image 20230411185319.png|300

נשים לב ש $C S A T \in N P$ - בהינתן השמה בוליאנית אפשר בזמן פולינומי באורך ייצוג המעגל לבדוק שהיא אכן מתקבלת על ידי המעגל. כלומר שהמעגל מחזיר עליה $t r u e$ .

CSAT היא NP-שלמה

השלב הראשון של ההוכחה אם כן היא להראות שלכל $S \in N P$ קיימת $f$ חשיבה פולינומית כך ש $x \in S \leftrightarrow f (x) = C_{x} \in S_{C S A T}$ כאשר

S_{C S A T} = {C | C is a boolean circle graph that can be saturated}

תהי $S \in N P$ , אזי ל $S$ ישנו מוודא פולינומי $V_{S}$ כך ש $\exists_{y : | y | \leq P^{*} (| x |)} : V_{S} (x, y) = 1 \leftrightarrow x \in S$ וזמן הריצה של $V_{S}$ חסום על ידי $P_{V_{S}} (| x | + | y |) \leq P_{V_{S}} (| x | + P^{*} (| x |)) = t$ .

נבנה טבלה שמייצגת ריצה של מכונת טיורינג על הקלט $(x, y)$ לפי הריצה של $V_{S}$ (אפשר לעשות זאת כי הראנו שכל בעיה ב $N P$ אפשר ״להמיר״ לבעיית NP-שלמה שהקלט שלה הוא מכונת טיורינג)
פונקציית המעברים הינה

Σ \times Q \to Σ \times Q \times {+ 1, - 1, 0}

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

Pasted image 20230412121928.png|400

נתבונן בטבלת ריצת המוודא $V_{S}$ (המכונה הדו מימדית) על קלט $(x, y)$ נרצה להמיר את טבלת הריצה למעגל לוגי $C_{x}$ כך ש $C_{x} (y) = V_{S} (x, y)$ ואז יתקיים

\exists_{y} : C_{x} (y) = 1 \leftrightarrow \exists_{y} : V_{S} (x, y) = 1 \leftrightarrow x \in S

נשים לב שטבלת ריצת המוודא היא בגודל $t \times t$ לכל היותר כאשר בשורה הראשונה רשום הקלט ובשורה האחרונה נמצא הפלט. המכונה תעשה לכל היותר $t$ צעדים כי כל צעד של הראש נרד שורה בטבלה.

בשורה הראשונה בכל תא רשומים שני ערכים, הערך הראשון הוא ביט של אינפורמציה מתוך הקלט והערך השני הוא ״-״ או תיאור מצב המכונה. לכל התאים פרט לתא בו נמצא הראש של המכונה יהיה ״-״ בערך השני של התא ורק בתא בו נמצא הראש יהיה ערך השני התואם למצב המכונה. כמו כן, כל צד של טבלת החישוב (מתוך $t$ צעדים) מחושב על פי טבלת הצעדים של המכונה (פונקציית המצבים המוגדרת למעלה).

ערך כל תא בטבלת החישוב נקבע רק על-פי שלושת התאים שמעליו. לכן ניתן לבנות מעגל קטן בגודל קבוע שלא תלוי בגודל הקלט אך תלוי בטבלת המצבים של המכונה, הקובע ערך התא על פי שלושת ערכי התאים מעליו.

כעת משהבנו איך תיאור המכונה יעבוד ונראה על הטבלה הנ״ל נוכל לנצל זאת כדי לבנות את המעגל $C_{x}$ . ניקח את הטבלה ונבנה ממנה מעגל בגודל $t \times t$ המורכב מאיחוד של המעגלים הקטנים יותר שקובעים את הערך של כל תא בשורה מסויימת, המשתנים של המעגל יהיו $x, y$ שנמצאים בשורה הראשונה לאחר ההשמה. תוצאת הפלט תהיה accept או true אמ״מ $V_{S} (x, y) = 1$ כלומר המכונה מכריעה את הקלט. במצב שבוא $V_{S} (x, y) = 0$ נקבל שגם המעגל שלנו לא ספיק ולכן

\exists_{y} : C_{x} (y) = 1 \leftrightarrow \exists_{y} : V_{S} (x, y) = 1 \leftrightarrow x \in S

כדרוש.

קיימת רידוקציית קארפ מ CSAT ל SAT

כעת הוכחנו שבעיית $C S A T$ היא $N P$ -שלמה, כל שנשאר לעשות הוא לבנות רידוקציית קארפ ממנה ל $S A T$ . מטרנזיטיביות הרידוקציית יתקיים שגם היא שלמה. נרצה שבהינתן מעגל בוליאני $C$ בנות נוסחה $Φ$ בצורת $C N F$ כך ש $C \in C S A T \leftrightarrow Φ \in S A T$ .

באופן נאיבי היינו יכולים לבנות טבלת אמת למעגל ולבנות ממנה נוסחה בצורת $C N F$ אך הפתרון הזה אינו פולינומי כי עבור $n$ משתנים טבלת האמת תכיל $2^{n}$ תוצאות בטבלת האמת.
נשים לב להבחנה שאם מספר המשתנים היה קבוע היינו יכולים ב $O (1)$ להמיר אותו לנוסחה מהצורה של $C N F$ .

אם כן, האינטואיצייה תהיה ״לפצל״ את המעגל לכמה מעגלים קטנים, מכל אחד נבנה נוסחה בצורת $C N F$ ולבסוף נחזיר נוסחה שתהיה מורכבת מכל הנוסחאות הקטנות.
נסמן את קודקודי הקלט ב $x_{1} \dots, x_{n}$ ואת השערים ב $g_{1}, \dots, g_{m}$ ונגדיר נוסחה עם $n + m$ משתנים כנגד קודקוד הפלט והשערים ב $C$ . למשל עבור המעגל
Pasted image 20230412141128.png|300
נקבל נוסחה מהצורה
Pasted image 20230412141152.png|350
נשים לב שהוספנו פרדיקט של EQ שהמטרה שלו היא לבדוק שיוויון בין $g_{i}$ המשתנה לנוסחה שממנה הוא מורכב במעגל. באופן הזה הגרף מבטיח שהפרקדיט EQ יחזיר $t r u e$ רק אם המשתנה ב״גרף״ החדש שבנינו יקבל ערך ששקול לערך שהוא מקבל במעגל $C$ . תחת ההבנה הזאת נוכל לקחת כל פרדיקט EQ ולבנות טבלת אמת בין שני הגורמים שמרכיבים אותו. אלו יהיו תמיד על מספר משתנים בגודל קבוע כי מתחילים מהנעלמים ומתקדמים לכיוון הפלט. לאחר שנמיר את ה״גרף״ לפסוקיות בצורה $C N F$ נשים $\land$ בין כולם ונגיע לתוצאה הרצויה (כמעט).

לכל שער $i$ במעגל $C$ נגדיר נוסחה בצורת $C N F$ נסמנה $Φ_{i}$ שתהיה מסופקת אמ״מ הערך שמקבל המשתנה $g_{i}$ עקבי עם הערך שמקבל השער $g_{i}$ במעגל $C$ . לדוגמה עבור

g_{1} = x_{1} \land x_{2}

$x_{1}$	$x_{2}$	$g_{1}$	$g_{1} = x_{1} \land x_{2}$
T	T	T	T
T	T	F	F
T	F	T	F
T	F	F	T
F	T	T	F
F	T	F	T
F	F	T	F
F	F	F	T

נזכיר שכדי להמיר את הפסוקית לצורת $C N F$ לוקחים את כל הפסוקיות שמחזירות $f a l s e$ ומפעילים not כל כולם ולכן

\begin{matrix} (g_{1} = x_{1} \land x_{2}) \equiv \overset{―}{(x_{1} \land x_{2} \land \overset{―}{g_{1}})} \land \overset{―}{(x_{1} \land \overset{―}{x_{2}} \land g_{1})} \land \overset{―}{(\overset{―}{x_{1}} \land x_{2} \land g_{1})} \land \overset{―}{(\overset{―}{x_{1}} \land \overset{―}{x_{2}} \land g_{1})} \\ \equiv (\overset{―}{x_{1}} \lor \overset{―}{x_{2}} \lor g_{1}) \land (\overset{―}{x_{1}} \lor x_{2} \lor \overset{―}{g_{1}}) \land (x_{1} \lor \overset{―}{x_{2}} \lor \overset{―}{g_{1}}) \land (x_{1} \lor x_{2} \lor \overset{―}{g_{1}}) \end{matrix}

לאחר שיש לנו את כל הפסוקיות $Φ_{1} \dots Φ_{m}$ נרצה לבנות פסוקית נוספת מהקודקוד שנכנס לקודקוד הפלט. כלומר כרגע יש לנו את התוצאה של

⋀_{i = 1}^{m} Φ_{i}

נרצה לוודא בנוסף שגם הקודקוד שנכנס לקודקוד הפלט הוא $t r u e$ ולכן נוסיף פסוקית נוספת $Φ_{m + 1} = g_{m}$ במקרה הנ״ל $Φ_{5} = g_{4}$ . לבסוף נחזיר

⋀_{i = 1}^{m + 1} Φ_{i}

Pasted image 20230412150140.png|400
זמן בנייה מספר השערים ב $C$ חסום ליניארית באורך הקלט. עבור כל שער ביצענו $O (1)$ צעדים (כיוון שמשתמשים לכל היותר ב 3 קודקודים) כדי לבנות נוסחה $Φ_{i}$ .

כעת נרצה להוכיח ש $C \in C S A T \leftrightarrow Φ \in S A T$ :
$\to$ נניח $C \in C S A T$ לכן קיימת השמה $z = z_{1} \dots z_{n}$ עבור קודקודי הקלט במעגל שתספק אותו. נסתכל על ההשמה לנוסחה בה כל משתנה $x_{i}$ מקבל את הערך $z_{i}$ וכל משתנה $g_{i}$ מקבל את הערך של השער $g_{i}$ במעגל ל $C$ .
לפי הבנייה כל $Φ_{i}$ מסופקת וכן הפסוקית $Φ_{m + 1}$ מסופקת כי $C (z) = T$ .

$\leftarrow$ נניח $Φ \in S A T$ לכן קיימת השמה $z = z_{1}, \dots, z_{n}$ למשתנים ב $Φ$ שמספקת אותה. נשים לב שההצבה הנ״ל מספקת את המעגל מהבנייה של $Φ$ .

הבחנה

3SAT היא גם כן $N P$ -שלמה כי ראינו עכשיו שברידוקצייה מ $C S A T$ ל $S A T$ בכל פסוקית יש לכל היותר 3 ליטרלים

הבחנה

ראינו ש $S A T$ היא $N P C$ וראינו רדוקציית קארפ מ $S A T$ ל $I S$ ולכן היא גם כן שייכת ל $N P C$

תזכורת

אם יש רידוקציית קארפ מ $A$ ל $B$ כך ש $B \in N P$ אזי $A \in N P$

Vertex Cover

נתון גרף $G = (V, E)$ ונתון מספר $k$ . נרצה לדעת האם גרף $G$ ישנם $k$ קודקודים שמכסים את כל הקשתות.

Pasted image 20230602191430.png

נרצה להראות שזאת אכן בעיה $N P$ שלמה.
ראשית קל להראות שהיא ב $N P$ כי תמיד אפשר לבדוק בזמן פולינומי שאוסף קודקודים שניתן כעדות, אכן מכסה את הקשתות.

כעת, נראה רדוקציית קארפ מ $I S$ ל $V C$ .
לשם הרידקוצייה נוכיח את טענת העזר הבאה:
עבור $G = (V, E)$ ו $S \subseteq V$ קבוצה בת״ל המקיימת $| S | = k$ . אזי, $V - S = \overset{―}{S}$ היא קבוצה המקיימת $V C$ . יותר מזה,

S is independent \leftrightarrow \overset{―}{S} is vertex cover

הסבר:
אם $S$ בלתי תלוי אזי לכל קשת $(u, v) \in E$ מתקיים ש $u \notin S$ או ש $v \notin S$ כי אחרת שניהם ב $S$ וזו סתירה לכך ש $S$ בת״ל. כלומר בהכרח מתקיים שאחד מהם נמצא ב $\overset{―}{S}$ ולכן זאת תכסה את כל הקשתות.
מצד שני, אם $\overset{―}{S}$ היא ב $V C$ אזי $S$ היא בת״ל תחת אותו הסבר, לא ייתכן שישנה קשת $(u, v)$ ששני קצותיה נמצאים בתוך $S$ .

מטענת העזר נוכל לבנות רידוקציית קארפ מ $I S$ ל $V C$ על ידי

f(G,k)= (G, |V(G)|-k)

הנכונות נובעת ישירות מטענת העזרת.