#computational_complexity #computational_models #computer_science

CO-P ו CO-NP

CO-NP

נגדיר את $C O - N P$ להיות :

C O - N P = {S | \overset{―}{S} \in N P}

דוגמה: נתבונן בבעיה

\overset{―}{S A T} = {ρ | ρ cannot be satisfied}

כיוון ש $S A T \in N P$ מתקיים ש $\overset{―}{S A T} \in C O - N P$ .

השערה- $C O - N P \neq N P$
טענה- $P \subseteq C O - N P$ . הוכחנו בעבר כי $P \subseteq N P$ בנוסף, אם $S \in P$ זה גורר ש $\overset{―}{S} \in P$ כי נוכל בקלות להחזיר תשובה הפוכה ולכן $\overset{―}{S} \in N P$ . סך הכל נקבל $\overset{―}{S} \in C O - N P$

Pasted image 20230602210735.png|400

CO-P

נגדיר את $C O - P$ להיות :

C O P = {S | \overset{―}{S} \in P}

משפט- $C O P = P$ . נוכיח על ידי הכלה דו כיוונית.
תהי $S \in C O - P$ אזי $\overset{―}{S} \in P$ . סך הכל נוכל להכריע את $S$ על ידי החזרת תשובה הפוכה מזו שיחזיר האלגוריתם שמכריע את $\overset{―}{S}$ .

מסקנה : אם $N P \neq C O N P$ אז $P \neq N P$
נב״ש $P = N P$ אזי $C O P = C O N P$ מטענה קודמת נובע ש

N P = P = C O P = C O N P

לכן $N P = C O N P$ בסתירה.

השערה

שיערנו ש $N P \neq C O - N P$ ובנוסף ראינו ש $P \subseteq N P \cap C O N P$ ולכן נניח ש $P \subset N P \cap C O N P$
כלומר:

S \in P \leftrightarrow \overset{―}{S} \in P \leftrightarrow \overset{―}{S} \in N P \leftrightarrow S \in C O N P

NP/CONP

טענה
אם קיימת $A \in N P \cap C O N P$ שהיא NP-קשה* אז $N P = C O N P$

נוכיח בהכלה דו כיוונית תחת ההנחה הנ״ל

$\subseteq$ :
ראשית , תהי $S \in C O N P$ , אזי $\overset{―}{S} \in N P$
לכן, קיימת רדוקציית קוק מ $\overset{―}{S}$ ל $A$ לפי הגדרת בעיה $N P$ -קשה* . כמו כן תמיד קיימת רידוקצית קוק מ $S$ ל $\overset{―}{S}$ .
סה״כ מטרנזיטיביות הרדוקציות נקבל שקיימת רדוקציית קוק מ $S$ ל $A$ .

כעת נוכל לבנות ל $S$ מוודא פולינומי $V_{S}$ (כדי להוכיח שהוא אכן ב $N P$ ) שאינטואיטיבית יהיה דומה לפעולת רדוקציית הקוק מבלי להחשיב את הקריאות למכונת אורקל שפותרת את $A$ , כי אין לו גישה אליה, במקום זאת, נסמלץ אותן באופן מלאכותי ובכל מקום שקראנו לאורקל והוא החזיר תשובה חיובית, כיוון ש $A \in N P$ , במקום להחזיר רק תשובה חיובית, נחזיר גם עד מתאים ובאופן דומה אם החזיר תשובה שלילית נחזיר גם עד מתאים ומובטח שהוא קיים כי $A \in C O N P$ .

אם כן, המוודא $V_{S} (x, y)$ יקבל עדות $y$ המורכבת מאוסף שלשות מהצורה

y = {(q_{1}, a_{1}, w_{1}), \dots, (q_{t}, a_{t}, w_{t})}

כאשר $q_{i}$ היא שאלה מספר $i$ שמכונת הרדוקצייה מ $S$ ל $A$ הפעילה לאורקל.
$a_{i} \in {0, 1}$ היא תשובה לשאלה $q_{i}$
$w_{i}$ היא עדות פולינומית לכל ש $a_{i}$ היא אכן תשובת המכונה ל $q_{i}$ .
כלומר אם $a_{i} = 1$ אז $w_{i}$ תהיה עדות לכל ש $q_{i} \in A$ ואם $a_{i} = 0$ אז $w_{i}$ תהיה עדות לכך ש $q_{i} \notin A$

תיאור המוודא:
$V_{s} (x, y)$ יריץ את מכונת האורקל מ $S$ ל $A$ ( $M^{A}$ ) , אך יחליף כל פנייה ל $A$ בשימוש בתשובה $a_{i}$ שהתקבלה בעדות, וכן בעדות $w_{i}$ שהתקבלה שמוכיחה שהתשובה שהאורקל החזיר אכן נכונה. כלומר, לפני שימוש בתשובה $a_{i}$ להמשך הביצוע, המוודא יוודא כי התשובה אכן נכונה ועל כן יריץ בצורה נכונה את לוגיקת הרידוקציה אך ללא פנייה ל אורקל של $A$ .
אם כן, מתקיים ש אם $x \in S$ אז יש עדות $y$ שניתן לתת ל $V_{S}$ שמתאים לריצת הרדוקצייה. ואם $x \notin S$ המוודא יחזיר $0$ לכל ריצה על הרדוקצייה שבנינו.

$\supseteq$ :
נב״ש כי $N P ⊈ C O N P$ , אזי קיימת $S^{'} \in N P / C O N P$ , ולכן $S^{'} \in N P$ וגם $S^{'} \notin C O N P$ . כלומר $\overset{―}{S^{'}} \in C O N P$ ומכיוון ש $C O N P \subseteq N P$ אזי $\overset{―}{S^{'}} \in N P$ ולכן $S^{'} \in C O N P$ בסתירה לכך ש $N P ⊈ C O N P$ .

טענה
אם $C O N P$ מכילה בעיה $N P H$ אז $N P = C O N P$
כדי להוכיח את הטענה, ראשית נשים לב כי אם $C O N P \subseteq N P$ אז גם $N P \subseteq C O N P$ כיוון ש

S \in N P \to \overset{―}{S} \in C O N P \to \overset{―}{S} \in N P \to S \in C O N P

ולכן מספיק להראות שאם $C O N P$ מכילה בעיה $N P H$ כלומר $S \in C O N P \cap N P H$ אזי $C O N P \subseteq N P$

Pasted image 20230701003002.png

טענת עזר אם יש רדוקציית קארפ מ $S^{'}$ ל $S$ אז יש רדוקציית קארפ מ $\overset{―}{S^{'}}$
ל $\overset{―}{S}$ .

Pasted image 20230701121436.png

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

\begin{matrix} x \in S^{'} \leftrightarrow f (x) \in S \\ ↓ \\ x \notin S^{'} \leftrightarrow f (x) \notin S \\ ↓ \\ x \in \overset{―}{S^{'}} \leftrightarrow f (x) \in \overset{―}{S} \end{matrix}

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

כעת, נחזור ל $S \in C O N P \cap N P H$ וניקח בעיה $S^{'} \in C O N P$ . מתקיים ש
$\overset{―}{S^{'}} \in N P$ . ישנן מספר רדוקציות קארפ שאנחנו יודעים שישנן:

מ $\overset{―}{S^{'}}$ ל $S$ כי $S$ היא $N P H$
מטענת העזר יש מ $S^{'}$ ל $\overset{―}{S}$ רדוקציית קארפ.

$S \in C O N P$ ולכן $\overset{―}{S} \in N P$ . מטענת סגירות לרדוקציית קארפ מתקיים ש $S^{'} \in N P$ ולכן הראנו שאם הנ״ל מתקיים כל בעיה שנמצאת ב $C O N P$ נמצאת גם ב $N P$ ולכן

C O N P \subseteq N P

כלומר: $N P = C O N P$

משפט :
בהנחה ש $P \neq N P \cap C O N P$ אז קיימת בעיית חיפוש $R \in P C$ שאין לה רדוקצייה עצמית.

Screenshot 2023-07-01 at 17.12.20.png

הוכחה:
תהי $S \in N P \cap C O N P / P$ כלומר $S, \overset{―}{S} \in N P$ .
נסמן ב $V_{S}, V_{\overset{―}{S}}, P_{S}, P_{\overset{―}{S}}$ את הפולינומים והמוודאים של $S, \overset{―}{S}$ .
נגדיר את בעיות החיפוש הבאות:

\begin{matrix} R_{S} = {(x, y) | | y | \leq P_{S} (| x |), V_{S} (x, y) = 1} \\ R_{\overset{―}{S}} = {(x, y) | | y | \leq P_{\overset{―}{S}} (| x |), V_{\overset{―}{S}} (x, y) = 1} \end{matrix}

מאיך שהגדרנו את בעיות החיפוש שלנו מתקיים

x \in S \leftrightarrow \exists_{y | y | \leq P_{S} (| x |)} : (x, y) \in R_{S}, \forall_{y} : (x, y) \notin R_{\overset{―}{S}}

x \in \overset{―}{S} \leftrightarrow \exists_{y | y | \leq P_{\overset{―}{S}} (| x |)} : (x, y) \in R_{\overset{―}{S}}, \forall_{y} : (x, y) \notin R_{S}

נגדיר כעת $R = R_{S} \cup R_{\overset{―}{S}}$ ונראה כי $R$ היא בעיית חיפוש ב $P C$ שאין לה רדוקצייה עצמית.

$R \in P C$ : בהנתן $(x, y)$ נריץ את שתי המוודאים ואם לפחות אחד מהם החזיר $1$ נחזיר $1$ אחרת נחזיר $0$ .

נרצה כעת להראות של $R$ אין רדוקצייה עצמית, נראה כי $R \notin P F$ ו $S_{R} \in P$ ומטענה קודמת נקבל את הדרוש.

נשים לב ש

S_{R} = S \cup \overset{―}{S} = {0, 1}^{*} \in P

נראה אם כן ש $R \notin P F$ על ידי הנחה בשלילה שהיא כן ב $P F$ .
אם $R \in P F$ אז ישנו אלגוריתם פולינומי $A$ שפותר אותה כלומר בהינתן $x$ יחזור $y$ אם $(x, y) \in R$ . בעצם מתקיים ש $x \in S \leftrightarrow (x, A (x)) \in R$ . נבנה אלגוריתם $D$ המכריע את $S$

בהנתן קלט $x$ נריץ את $A (x)$ ונבדוק האם $(x, A (x)) \in R_{S}$ , נוכל לעשות זאת בזמן פולינומי :

אם $A (x)$ החזיר $⊥$ אז אנחנו יודעים שהוא לא ב $R_{S}$ כי הוא לא ב $R$ .
אם $A (x)$ החזיר $y$ כלשהו פשוט נריץ את המוודא $V_{S} (x, y)$ ונבדוק את התוצאה.

$D$ אם כן, אלגוריתם פולינומי המקיים

x \in S \leftrightarrow (x, A (x)) \in R_{S} \leftrightarrow D (x) = 1

סה״כ הראנו כי $R \in P C$ ואין לו רדוקצייה עצמית.

הגדרה שקולה ל $C O N P$

$S \in C O N P$ אם קיים פולינום $P$ ומוודא פולינומי $V$ כך ש

x \in S \leftrightarrow \forall_{y : | y | \leq P (| x |)} : V (x, y) = 1

למשל עבור $\overset{―}{S A T}$ המוודא יקבל נוסחה והשמה ויחזיר $1$ אמ״מ ההשמה לא מספקת.