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

יהי יחס דו־מקומי

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

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

2. בעיית הזיהוי של S היא: בהנתן זוג האם ?

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


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

עריכה

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

עריכה

משפט:

אם   אז היחס S ניתן לחיפוש    
(כלומר: זיהוי גורר חיפוש)

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

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

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

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

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

 

בעיית החיפוש ניתנת לפתרון בקלות: לכל קלט x נוציא כפלט את המחרוזת "0". לעומת זאת, בעיית הזיהוי, עבור קלט מהצורה   הוא בלתי־אפשרי. פורמלית, ניתן להראות שהשפה   ע״י הרדוקציה  , והידיעה ש־  לפי משפט רייס המורחב.


הפרק הקודם:
הסתברות אוניברסאלית
בעיות זיהוי ובעיות חיפוש -