#computational_complexity #computational_models #computer_science

רדוקציית קוק

תהיינה $A, B$ שתי בעיות חישוב , נגדיר רדוקציית קוק מ $A$ ל $B$ על ידי אלגוריתם פולינומי שפותר את $A$ בעזרת גישה ל ״אורקל״ שפותר את $B$ .
למשל - נזכר בבעיית k-clique

R_{k C l i q u e} = {((G, k), S) | S is a clique with size at lest k in G}

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

S_{c l i q u e} = c l i q u e = {(G, k) | exists a k clique in G}

נבצע רידוקציית קוק בין $R_{c l i q u e}$ ל $c l i q u e$ , על ידי בניית אלגוריתם פולינומי שמקבל $(G, k)$ ומחזיר קליקה בגודל $k$ או $⊥$ אם אין כזאת באמצעות גישה לבעיית ההכרעה המתאימה.

$A (G, k)$

אם $(G, k) \notin c l i q u e$ אז החזר $⊥$
אחרת, לכל קודקוד $u$ ב $G$ :
- הסר מ $G$ את $u$ והקשתות הנוגעות בו. נסמן את הגרף החדש $G^{'}$
- בדוק האם $(G^{'}, k) \in c l i q u e$
  - אם בגרף החדש יש קליקה ממשיכים על $G^{'}$ אחרת, ממשיכים על $G$
החזר את קבוצת הקודקודים שנותרה ב $G$ .

הסבר: האלגוריתם מסיר מהגרף את כל הקודקודים בלעדיהם יש קליקה בגודל $k$ ולבסור מחזיר קליקה בגודל $k$ בזמן $O (| V |)$ .

מכונת טיורינג בעלת גישת אורקל

נסמן את $M^{A}$ מכונת טיורינג רגילה בתוספת האפשרות לבצע שאילתות לבעיית הכרעה $A$ בעלות של צעד בודד. מכונה שכזו תקרא מכונת טיורינג בעלת גישת אורקל.

רידוקצייה עצמית

יחס $R \in P C$ ניתן לרידקוצייה עצמית אם אפשר לפתור את $R$ על ידי מספר גישות פולינומי לבעיית ההכרעה $S_{R}$ .

טענה: אם $R \in P C$ המקיים ש $S_{R} \in N P C$ אזי $R$ ניתן לרדוקצייה עצמית.
בהוכחת המשפט $P C \subseteq P F \leftrightarrow N P \subseteq P$ ראינו רדוקציית קוק מ $R$ ל $S_{R^{'}}$ בעיית התחיליות.
כיוון שנתון ש $S_{R}$ היא NP שלמה אזי ישנה רידוקציית קארפ מ $S_{R^{'}}$ ל $S_{R}$ ומטרנזיטיביות הרידוקציות נקבל רדוקציית קוק מ $R$ ל $S_{R}$ .

טענה: לכל יחס $R \notin P F$ כך ש $S_{R} \in P$ אין רדוקצייה עצמית.
נניח בשלילה שיש ל $R$ רדוקצייה עצמית אז ניתן לפתור את $R$ בזמן פולינומי ללא גישת אורקל על ידי החלפת כל גישת אורקל באלגוריתם פולינומי שמכריע את $S_{R}$ ולכן $R \in P F$ בסתירה.

דוגמה:
בעיה לדוגמה שמשערים שאין לה רדוקצייה עצמית היא

R_{f a c t o r i n g} = {(n, k) | n \in N, k | n}

כאשר $k$ מחלק לא טריוויאלי.

משערים שבעיה זו אינה ב $P F$ אבל יודעים להכריע בזמן פולינומי האם מספר הוא ראשוני או לא כלומר $S_{R} \in P$ ולכן ל $R_{f a c t o r i n g}$ אין רדוקצייה עצמית.

הבחנה

המחלקה $N P$ אינה סגורה לרדוקציית קוק, רק לרדוקציית קארפ

NP-קשה*

משפט- לכל $S \subseteq {0, 1}^{*}$ קיימת רדוקציית קוק מ $S$ ל $\overset{―}{S}$ . נוכל להוכיח זאת על ידי כך שלכל קלט $x$ נריץ את האורקל המכריע את $\overset{―}{S}$ ונחזיר תשובה הפוכה..

הבחנה

בניגוד לרידוקציית קארפ שבה לא תמיד יש רידוקצייה מבעיה למשלים שלה, ברידוקציית קוק הדבר תמיד מתקיים למשל מ $\overset{―}{S A T}$ ל $S A T$ למרות שהראשונה לא שייכת כנראה ל $N P$ . המסקנה המתבקשת היא ש $N P$ ככל הנראה אינה סגורה לרדוקציית קוק

הגדרה בעיה $S$ נקראת $N P$ -קשה* אם היא קשה יחסית לרדוקציית קוק. כלומר, קיימת רדוקציית קוק מכל $S^{'} \in N P$ ל $S$ .

נשים לב

ב $N P C$ של $A$ דרשנו רדוקציית קארפ מכל $B \in N P$ ל $A$ . בעיות $N P$ קשות הן יותר קלות מבעיות $N P C$ , כי בעיות שלמות כ״כ קשות שבקלות אפשר לעבור אליהן ע״י רדוקציית קארפ, לעומת זאת במקרה הזה צריך לעבוד קשה יותר כדי לעשות את המעבר כי הבעיה יותר קלה..

משפט Lander

קיימות בעיות הכרעה שהן ב $N P$ ואינן $N P C$ , כך שאם $P \neq N P$ אז הן אינן ב $P$ . לדוגמה: בעיית $F a c t o r i n g$ (פירוק לגורמים ראשוניים) היא כזו.