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

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

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 {\mathrm{\Sigma }}^{\ast }\}\cup \{(⟨M⟩,1)\mid ⟨M⟩\in L_{\mathrm{\varnothing }}\}$

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

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

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

-