תורת החישוביות/בעיות זיהוי ובעיות חיפוש

יהי $S\subseteq \Sigma ^{*}\times \Sigma ^{*}$ יחס דו־מקומי

1. בעיית החיפוש של S היא: בהנתן x מצא y כך ש־$(x,y)\in S$

נאמר שהיחס S ניתן לחיפוש אם קיימת מ״ט שעל כל קלט x מוצאת ערך y כך ש־$(x,y)\in S$ (לפחות אחד, אם קיימים יותר), ואם אין y כנ״ל, המכונה אינה עוצרת.

2. בעיית הזיהוי של S היא: בהנתן זוג $(x,y)$ האם $(x,y)\in S$?

נאמר שהיחס S ניתן לזיהוי אם קיימת מ״ט שמקבלת את הקלט $(x,y)$ אם הוא שייך ליחס S, ודוחה אחרת. זו היא בעצם בעיית ההכרעה של השפה

$L_{S}=\{(x,y)\mid (x,y)\in S\}$

הקשר בין חיפוש וזיהוי

זיהוי גורר חיפוש

משפט: אם $L_{S}\in RE$ אז היחס S ניתן לחיפוש     (כלומר: זיהוי גורר חיפוש)

הוכחה: אם $L_{S}\in RE$ אז קיימת מ״ט שמקבלת את $L_{S}$, שנסמנה ב־$M$. בהנתן קלט x נמצא בעזרת הרצה מבוקרת של M ערך y כך ש־$(x,y)\in S$ אם אין ערך y כנ״ל, המכונה לא תעצור.

שיטת ההרצה המבוקרת הוצגה בפרק תורת החישוביות/מודל לבעיות הכרעה

האם חיפוש גורר זיהוי?

התשובה היא לא! ייתכן שלכל x קיימים מספר ערכי y, אחד מהם קל למצוא (ומ״ט של החיפוש תחזיר אותו שוב ושוב), ולאו דווקא נוכל למצוא את ערך ה־y שניתן כקלט.

להוכחת טענה זו נביט ביחס הבא:

$S=\{(x,0)\mid x\in \Sigma ^{*}\}\;\cup \;\{(\langle M\rangle ,1)\mid \langle M\rangle \in L_{\emptyset }\}$

בעיית החיפוש ניתנת לפתרון בקלות: לכל קלט x נוציא כפלט את המחרוזת "0". לעומת זאת, בעיית הזיהוי, עבור קלט מהצורה $(x,1)$ הוא בלתי־אפשרי. פורמלית, ניתן להראות שהשפה $L_{S}\notin RE$ ע״י הרדוקציה $L_{\emptyset }\leq L_{S}$, והידיעה ש־$L_{\emptyset }\notin RE$ לפי משפט רייס המורחב.

הפרק הקודם: הסתברות אוניברסאלית

בעיות זיהוי ובעיות חיפוש

-