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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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

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

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

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

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


הקשר בין חיפוש וזיהוי[עריכה]

זיהוי גורר חיפוש[עריכה]

משפט:

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

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

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

האם חיפוש גורר זיהוי?[עריכה]

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

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

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


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