#computational_complexity #computational_models #computer_science

בעיות חיפוש והכרעה

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

נתעסק בשתי סוגי בעיות

בעיות חיפוש - מבקשות פתרון כלשהו (יכול להיות כמה פתרונות תקינים אבל צריך להחזיר רק אחד)
בעיות הכרעה - מספקות פתרון חד משמעי - true/false

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

בעיות קנוניות

בעיות חיפוש מפורסמות שילוו אותנו כאשר נרצה למדל בעיות חיפוש נוספות.

3-COL

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

Pasted image 20230318173512.png|300
למשל זה גרף שלא ניתן לצבוע כל קשת באופן הנ״ל

3-SAT

נתונה נוסחה בוליאנית בצורה $3 C N F$ נסמנה $ρ$ והמכילה ${X_{i}}$ משתנים בוליאנים. נרצה למצוא השמה למשתנים שנותנת השמה מספקת כלומר המחזירה $t r u e$
נזכיר שנוסחה בצורה $3 C N F$ היא נוסחה מהצורה

(X_{1} \lor X_{2} \lor X_{3}) \land (X_{4} \lor X_{5} \lor X_{6}) \land \dots

כלומר נוסחה שעוטפת 3 משתנים בוליאניים בפסוקיות או וכל קבוצה של 3 או פחות מחוברת לקבוצה אחרת עם וגם. (נשים לב ש $X_{i}$ יכול להיות גם מהצורה $\overset{―}{X_{i}}$ כלומר המשלים)

נשים לב שאם נסמן פסוקית בודדת שמכילה 3 משתנים $ρ_{i}$ אז נוכל למצוא פסוקית שלא ניתן לספק אותה על ידי

ρ_{i} \overset{―}{ρ_{i}}

מציאת מסלול בגרף

עבור גרף $G = (V, E)$ וזוג קודקודים $u, v \in E$ נרצה לדעת האם קיים בינהם מסלול.

Independent Set

בהינתן גרף לא מכוון ומספר $k$ נרצה לבדוק האם יש בגרף $k$ קודקודים ללא אף קשת בינהם (קבוצה בלתי תלויה)

Pasted image 20230325151424.png|300

מידול בעיות חיפוש

נתאר בעית חיפוש על ידי יחסים
יחס הוא אוסף של זוגות

R = {(x, y) | (x, y) \in R}

כאשר

R \subseteq {0, 1}^{*} \times {0, 1}^{*}

ו $x$ מייצג בעיה כלשהי ו $y$ הוא הפתרון עבורה.

למשל עבור בעיית ה 3col

R_{3 c o l} = {(G, I)}

$I$ היא צביעה חוקית של $G$

סימון: $R (x)$ יהווה את קבוצת אוסף הפתרונות של $x$ קלט כלשהו כלומר

R (x) = {y | (x, y) \in R}

אלגוריתם לפתרון בעיית חיפוש

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

כלומר לפתור בעיית חיפוש זה כמו להגיד שלכל $x \in {0, 1}^{*}$

אם $R (x) \neq \emptyset$ אז $A (x) \in R (x)$
אם $R (x) = \emptyset$ אז נסמן $A (x) =⊥$ סימון שמעיד שאין פתרון.

בעיות הכרעה

בעיות שהתשובה עליהן היא true/false ואותם ממדלים על ידי קבוצות.

\begin{matrix} S \subseteq {0, 1}^{*} \\ S = {x | x has a certain property} \end{matrix}

כלומר קבוצת כל הקלטים שמחזירים true עבור הבעיה שלנו.

למשל

S_{3 c o l} = {G | G has a legit coloring}

אלגוריתם $A$ פותר בעית הכרעה $S$ :

A (x) = 1 \leftrightarrow x \in S

סיבוכיות זמן

עבור מכונת טיורינג $M$ בעלת סרט בודד נסמן $S_{M} (x)$ - מספר הצעדים ש $M$ רצה על קלט $x$ עד שעוצרת (אם לא עוצרת אז $S_{M} (x) = \infty$ ) .
כדי למדוד יעילות וסיבוכיות נגדיר עבור אלגוריתם $M$

T_{M} : N \to N

פונקציית זמן הריצה של $M$ שמקיימת

T_{M} (n) = max_{| x | = n} {S_{M} (x)}

כלומר הזמן המקסימלי הדרוש כדי להריץ את את האלגוריתם $M$ על קלט באורך $n$ .

מה ייחשב יעיל?
״פולינומי״ - החישוב של $M$ יקרא ״יעיל״ אם קיים פולינום $P (.)$ כלשהו כך שלכל $n$ מתקיים

T_{M} (n) \leq P (n)

מצב זה נקרא סיבוכיות זמן פולינומית

אלגוריתם לא יהיה יעיל אם לא קיים פולינום כזה למשל עבור סיבוכיות מעריכית כמו $2^{n}$ .

הבחנה

אלגוריתם יעיל הוא אלגוריתם שרץ בזמן פולינומי לאורך הקלט שלו למשל אם הקלט הוא $x, y$ אז האלגוריתם צריך לרוץ בזמן $P (x + y)$

מחלקות של בעיות חיפוש

נרצה בתוך עולם של בעיות החיפוש למצוא את קבוצת בעיות החיפוש שיש להן אלגוריתם יעיל שמוצא פתרון. נסמן את קבוצה זאת כ $P F$ - polynomial find. יתקיים עבורו ש

$R \in P F$ (R זאת בעיית חיפוש) אם:

$R$ חסום פולינומית כלומר

\forall_{(x, y) \in R} : | y | \leq P_{R} (| x |)

כלומר אורך הפולט הוא פולינומי לאורך הקלט.

קיים אלגוריתם פולינומי $A$ שפותר את $R$

הבחנה

זה תנאי הכרחי אבל לא מספיק כלומר לא כל יחס שהפתרונות שלו הם קצרים יהיה ב $P F$ למשל $R_{3 c o l}$ חסום פולינומית אבל לא ידוע אם הוא ב $P F$ כי לא מכירים אלגוריתם שפותר אותה ביעילות. מה שכן אנחנו יכולים לעשות זה לוודא שפתרון כלשהו הוא תקין כלומר בהינתן שיש פתרון נוכל לוודא אותו ביעילות.

מחלקה חשובה נוספת של בעיות חיפוש נקראת $P C$ שמתארת בעיות שוידוא פתרון ניתן לעשות ביעילות. polynomial check. במקרה זה, $R_{3 c o l} \in P C$ . באופן פורמלי יותר $R \in P C$ אם $R$ חסום פולינומית וקיים אלגוריתם פולינומי $A$ כך שלכל זוג איברים $(x, y)$ יתקיים $A (x, y) = 1 \leftrightarrow (x, y) \in R$ .

שאלה: האם $P F \subseteq P C$ ?
אינטואיטיבית נראה שכן אבל בפועל זה לא המצב.
אם כן , ישנו $R \in P F$ ושמקיים $R \notin P C$ ולכן אין הכלה. ההסבר ללמה זה נכון היא שבאלגוריתם וידוא פתרון לפעמים לאמת פתרון קשה מאוד יהיה יותר מורכב מלמצוא אותו. לדוגמה :

\begin{matrix} R = {(⟨ m, x ⟩, 0) | x \in {0, 1}^{*}, m is turing machine} \\ \cup \\ {(⟨ m, x ⟩, 1) | x \in {0, 1}^{*}, m is turing machine that accept x} \end{matrix}

$R \in P F$ עבור $⟨ m, x ⟩$ תמיד $0$ היא תשובה נכונה כי זה איחוד של כל הקלטים עם 0 וקלטים תקינים עם 1.

$R \notin P C$ היא בעצם בעיה הדורשת מאיתנו לבדוק האם $m$ עוצרת על $x$ שזאת בעיה לא כריעה.

הבחנה

לא ידוע האם $P C \subseteq P F$

מחלקות של בעיות הכרעה

מהן המקבילות של $P C, P F$ בעולם של בעיות הכרעה?

המקבילה ל $P F$ נקראת $P$ והיא מייצגת את אוסף בעיות ההכרעה שיש להן אלגוריתם פולינומי כלומר קיים להן אלגוריתם מכריע $A$ . למשל- $S_{2 c o l} \in P$
המקבילה של $P C$ היא קבוצת אלגוריתמים שכל אחד מהם הוא מוודא או באופן פורמלי אלגוריתם $V$ עבור בעיית הכרעה $S$ כלשהי שמקיים 2 תנאים
- אי שלמות- לכל $x \in S$ קיים $y$ כך ש $V (x, y) = 1$
- נאותות- אם $x \notin S$ אזי לכל $y$ מתקיים $V (x, y) = 0$

כלומר

V = {\begin{cases} \exists_{y \in {0, 1}^{*}} : V (x, y) = 1 \leftrightarrow x \in S \\ \forall_{y \in {0, 1}^{*}} : V (x, y) = 0 \leftrightarrow x \notin S \end{cases}

סך הכל, נגדיר מחלקה של בעיות הכרעה שניתנות לווידוא כ $N P$ ויתקיים $S \in N P$ אם קיים ל $S$ מוודא פולינומי מסוג $N P$ :
כלומר אם קיים מוודא $V_{S} (\cdot)$ ופולינום $P_{S} (\cdot)$ כך ש

\begin{matrix} x \in S \to \exists_{| y | \leq P_{S} (| x |)} : V_{S} (x, y) = 1 \\ x \notin S \to \forall_{| y | \leq P_{S} (| x |)} : V_{S} (x, y) = 0 \end{matrix}

ו $V_{S}$ הינו אלגוריתם שזמן ריצתו הוא פולינומי ב $| x |$ .

נשים לב

אומנם אמרנו ש $P C$ היא המקבילה של $N P$ ומתקיים $P F ⊄ P C$ אבל יתקיים ש $P \subseteq N P$ בגלל ה עד הריק, לכל $S \in P$ יש אלגוריתם פולינומי $A_{S}$ שמכריע את $S$ ויתקיים ש $S$ כזו היא ב $N P$ כי נוכל להגדיר מוודא פולינומי באופן הבא $V_{S} (x, y) = A_{S} (x)$ כלומר הוא מתעלם מהעד ומכריע רק לפי הקלט.

משפט: לכל בעית חיפוש $R$ ניתן להגדיר בעית הכרעה מתאימה $S_{R} = {x | \exists_{y} : (x, y) \in R}$ ובפרט מתקיים $R \in P F \to S_{R} \in P$ .

בעיית קליקה

יהי $G = (V, E)$ גרף לא מכוון.
קבוצת קודקודים $S \subseteq V$ נקראת ״קליקה״ אם לכל $u, v \in S$ יש קשת בין $u$ ל $v$

Pasted image 20230319193616.png|300

נגדיר את בעיית החיפוש הבאה

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

נרצה להראות ש $R_{4 C} \in P F$ . כלומר לבנות אלגוריתם שמוצא פתרון בזמן פולינומי לגודל של $S$ . ראשית נשים לב שהיחס עצמו חסום פולינומית כי לכל $(G, S)$ ביחס מתקיים $| S | \leq | G |$ . כעת נוכל לבנות את האלגוריתם

A(G):
	create S with 4 vertex
	for all u,v in S 
		if (u,v) not in E
			return NULL
		return S

זה האלגוריתם הנאיבי ביותר ולכן ברור שהוא פותר את הבעיה. הוא גם פולינומי כי מספר תתי הקבוצות בגודל 4 הוא $(\binom{| V |}{4}) \leq | V |^{4}$ .

נרחיב את הבעיה לבעיה כללית יותר

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

כעת נרצה לבדוק האם היחס הזה גם שייך ל $P F$ . במקרה הזה מתקיים שהאלגוריתם מהתרגיל הקודם אינו פולינומי כי נקבל שנרצה לבנות את תתי הקבוצות בגודל $k$ הינו

(\binom{| V |}{k}) \geq {(\frac{| V |}{k})}^{k}

שבהתאם ל $k$ יכול להיות אקספוננציאלי לגודל הקלט למשל אם $k = \frac{| V |}{2}$ נקבל שזמן הריצה יהיה גדול או שווה ל $2^{\frac{| V |}{2}}$ .

{(\frac{| V |}{\frac{| V |}{2}})}^{\frac{| V |}{2}} = 2^{\frac{| V |}{2}}

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

האם $R_{k C} \in P C$ ? כן
בהינתן $((G, k), S)$ האלגוריתם יבדוק אם $| S | \geq k$ ושלכל $u, v \in S$ מתקיים ${u, v} \in E$ אם הבדיקות עברו בהצלחה יחזיר $1$ אחרת $0$ . כעת יותר קל לאמת כי אנחנו מביאים איזשהו ״עד״ כמו שאמרנו. זמן הריצה יהיה חסום על ידי

(\binom{| S |}{2}) \leq | S |^{2} \leq | G |^{2}

בעיית composite

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

composite = {n \in N | n is not prime}

נרצה להראות שהבעייה שייכת ל $N P$ . אכן נגדיר

V(n,k)
	if 1<k<n AND n mod k == 0 
		return 1
	return 0

האלגוריתם אכן מקיים אי שלמות ונאותות עבור composite :

\forall_{n \in c o m p o s i t e} \exists_{2 \leq k \leq n - 1} : V (n, k) = 1

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

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

סיכום: סוגי מחלקות

חיפוש :

מציאה $P F$ קבוצה של יחסים $R$ חסומים פולינומית כך שלכל $R$ קיים אלגוריתם פולינומי שמוצא פתרון כלשהו
ווידוא $P C$ קבוצה של יחסים $R$ חסומים פולינומית כך שלכל $R$ קיים אלגוריתם פולינומי שמקבל $(x, y)$ ומוודא שהוא אכן שייך ל $R$
הכרעה :
מציאה $P$ קבוצה של $S$ בעיות כך שלכל בעיה קיים אלגוריתם פולינומי שמכריע אותה כלומר האם איבר שייך לקבוצה או לא.
ווידוא $N P$ קבוצה של $S$ כך שלכל בעיה קיים מוודא פולינומי $V_{S}$

הכלה של המחלקות

הראנו אם כן ש $P F ⊈ P C$ וש $P \subseteq N P$ .
מה לגבי: $P C \subseteq P F$ ו $N P \subseteq P$ ?

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

P C \subseteq P F \leftrightarrow N P \subseteq P

הוכחה:
$\leftarrow$ : נניח $P C \subseteq P F$ ונרצה להראות ש $N P \subseteq P$ .
תהי $S \in N P$ כלומר קיים $V_{S}$ פולינומי כך ש

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

נגדיר

R_{S} = {(x, y) | V_{S} (x, y) = 1}

$R_{S}$ אכן חסום פולינומית כי מוגדר לפי הזוגות שהמוודא מקבל ולפי הגדרה $y$ חסום פולינומית ל $x$ המתאים לו. כמו כן $V_{S}$ הוא אלגוריתם פולינומי ולכן $R_{S} \in P C$ .

מההנחה ש $P C \subseteq P F$ מתקיים $R_{S} \in P F$ ולכן קיים אלגוריתם פולינומי $A_{R_{S}}$ שמקיים

A_{R_{S}} (x) \neq⊥\leftrightarrow R_{S} (x) \neq \emptyset \leftrightarrow \exists_{y : | y | \leq P (| x |)} : V_{S} (x, y) = 1 \leftrightarrow x \in S

לכן נוכל להגדיר $A_{S} (x)$ אלגוריתם פולינומי ל $S$ על ידי

A_{S} (x) = {\begin{cases} 1 & A_{R_{S}} (x) \neq⊥ \\ 0 & A_{R_{S}} (x) =⊥ \end{cases}

ומתקיים ש $S \in P$ כדרוש.

$\to$ : נניח $N P \subseteq P$ וצריך להראות ש $P C \subseteq P F$ .
יהי $R \in P C$ נרצה להראות שהוא גם ב $P F$
אם כן, עבור $R$ מתקיים שישנו אלגוריתם פולינומי $A_{R}$ כך ש

(x, y) \in R \leftrightarrow A_{R} (x, y) = 1

אם כן, נגדיר

S_{R} = {x | \exists_{y : | y | \leq P (| x |)} : (x, y) \in R}

מתקיים $S_{R} \in N P$ כי אפשר להשתמש ב $A_{R}$ בתור המוודא הפולינומי ל $S_{R}$ כי מהגדרתו נובע ש $x \in S_{R}$ אמ״מ $A_{R} (x, y) = 1$ כאשר קיים $y$ שכזה חסום פולינומי באורכו של $x$ .

מההנחה מתקיים ש $S_{R} \in P$ כלומר קיים $A_{S_{R}}$ אלגוריתם שמכריע את $S_{R}$

A_{S_{R}} (x) = 1 \leftrightarrow x \in S_{R}

כעת , נגדיר בעיה שקולה ל $S_{R}$ :

S_{R}^{'} = {[x, y^{o}] | \exists_{y^{'}} : (x, y^{o} \circ y^{'}) \in R}

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

[x, y] \in S_{R}^{'} \leftrightarrow \exists_{y^{'}} : A (x, y \circ y^{'}) = 1

זה עדיין פולינומי כי מציאת $y^{'}$ שכזה היא עדיין פולינומית ולכן $S_{R}^{'} \in N P$ , מההנחה מתקיים גם ש $S_{R}^{'} \in P$ ולכן קיים לו אלגוריתם $A_{S_{R}^{'}}$ שמכריע כל קלט מהצורה $[x, y]$ .

אלגוריתם פולינומי למציאת פתרון של $R$ (קלט: $x$ )

בדוק האם $x \in S_{R}$
- אם התשובה היא false החזר $⊥$ .

אחרת, הגדר '' = y .
כל עוד $(x, y) \notin R$ (ניתן לוודא באמצעות $A_{R}$ )
- בדוק האם $[x, y \circ 0] \in S_{R}^{'}$
- אם כן, $y = y \circ 0$
- אחרת $y = y \circ 1$
החזר $y$

כדרוש.