RE (מחלקת סיבוכיות)

בתורת החישוביות והסיבוכיות, המחלקה RE (מאנגלית: Recursively Enumerable) היא מחלקה אשר מכילה את כל בעיות ההכרעה שעל התשובה "כן" קיימת מכונת טיורינג היכולה לוודא זאת בזמן סופי. באופן לא פורמלי, הכוונה שאם התשובה לבעיה נתונה היא "כן", אזי קיים תהליך כלשהו שיכול לוודא זאת בזמן סופי, ותהליך זה לעולם לא יפלוט "כן" אם התשובה האמיתית היא "לא". אף על פי כן, אם התשובה האמיתית היא "לא", התהליך לא מחויב לעצור ואף יכול להיכנס ללולאה אינסופית בחלק מהמקרים. תהליך כזה נקרא לעיתים דמוי-אלגוריתם או אלגוריתם למחצה, על מנת להבדיל מאלגוריתם אשר נועד לחשב תשובה עבור בעיית הכרעה.

באופן דומה, ניתן להגדיר את המחלקה המשלימה, coRE, בתור מחלקת כלל השפות הפורמליות שהמשלימה שלהן נמצאת ב-RE, דהי, המחלקה מכילה את כלל השפות הפורמליות שניתן לשלול שייכות בזמן סופי, אך הוכחת שייכות יכולה לקחת זמן אינסופי.

הגדרה שקולה

באופן שקול, ניתן להגדיר את המחלקה RE בתור מחלקת כלל בעיות ההכרעה כך שקיימת מכונת טיורינג היכולה למנות את כל מופעי ה-"כן", זו אחר זו (מכאן המשמעות של "ניתנת למנייה"). כל איבר במחלקה היא קבוצה ניתנת למנייה רקורסיבית ולכן מהווה קבוצה דיופנטית.

על מנת להראות שקילות זו, נשים לב שאם קיימת מכונה $E$ כך שהיא מונה את כל הקלטים שמתקבלים, מכונה אחרת שמקבלת מחרוזת כקלט יכולה להריץ את $E$ ולקבל (כלומר לענות כן) אם המחרוזת ניתנת למנייה. באופן הפוך, אם מכונה $M$ מקבלת (עונה כן) כאשר הקלט הוא שפה פורמלית, מכונה אחרת יכולה למנות את כל המחרוזות שנמצאות בשפה על ידי הרצת $M$ באיטרציות על כל קלט ולפלוט את כל הפלטים ש-$M$ מקבלת.

יחסים בין המחלקה למחלקות אחרות

מחלקת השפות הרקורסיביות (R) היא תת-קבוצה של RE ו-coRE ולמעשה, R מהווה את החיתוך בין שתי המחלקות, שכן אנו יכולים להכריע כל בעיה שקיימת לה מכונת טיורינג המקבלת אותה וקיימת לה מכונת טיורינג הדוחה אותה על ידי הרצה לסירוגין של שתי המכונות עד שאחת מהן עוצרת ופולטת תשובה. לכן:

${\mbox{R}}={\mbox{RE}}\cap {\mbox{coRE}}$.

באופן הפוך, הקבוצה של כלל השפות הפורמליות שאינן ב-RE ואינן ב-coRE נקראת NRNC. זוהי מחלקת כלל השפות הפורמליות שלא קיימת להן מכונת טיורינג היכולה להוכיח או להפריך שייכות אליהן בזמן סופי, כלומר:

${\mbox{NRNC}}={\mbox{ALL}}-({\mbox{RE}}\cup {\mbox{coRE}})$.

לא רק שבעיות כאלו אינן כריעות, גם הן וגם המשלימות שלהן אינן ניתנות למנייה רקורסיבית.

בעיות שלמות ב-RE

המחלקה RE-Complete היא תת-קבוצה של המחלקה RE המכילה את כל בעיות ההכרעה שהן שלמות ב-RE. ניתן לומר כי הן הבעיות "הכי" קשות הניתנות למנייה רקורסיבית. באופן כללי, אין הגבלות על הרדוקציות פרט לכך שהן אמורות להיות פונקציות מלאות המוגדרות לכל קלט ותקפות.

דוגמאות לבעיות שהן שלמות ב-RE:

1. בעיית העצירה: בהינתן תוכנית מחשב וקלט, האם התוכנית תסיים את פעולתה בשלב כלשהו עבור קלט זה.
2. משפט רייס אומר כי הכרעה של שייכות עבור כל תת-קבוצה לא טרוויאלית של קבוצת פונקציות רקורסיביות היא RE-קשה. היא תהיה שלמה אם הקבוצה היא ניתנת למנייה רקורסיבית.
3. ג'ון מייהיל (1955) הוכיח כי כל הקבוצות היצירתיות הן RE-שלמות.
4. בעיית המילה היוניפורמית עבור חבורות וחבורות למחצה.
5. קביעת שייכות עבור דקדוק בלתי-מוגבל כללי (טיפוס 0 בהיררכיית חומסקי).
6. בעיית התקפות עבור תחשיב פרדיקטים מסדר ראשון.
7. בעיית ההתאמה של פוסט
8. קביעה אם למשוואה דיופנטית יש פתרונות בשלמים.

בעיות שלמות ב-coRE

המחלקה coRE-Complete היא תת-קבוצה של המחלקה coRE המכילה את כל בעיות ההכרעה שהן שלמות ב-coRE.

דוגמאות לבעיות שהן שלמות ב-coRE:

1. בעיית הדומינו באריחי ואנג.
2. בעיית הספיקות עבור תחשיב פרדיקטים מסדר ראשון.

קישורים חיצוניים

• סקוט אהרונסון, Class RE, באתר Complexity Zoo (באנגלית)
• סקוט אהרונסון, Class coRE, באתר Complexity Zoo (באנגלית)