Question

proof
p_np
r_re

שפה LL תקרא שלמה ביחס למחלקת שפות SS אם:

  • מתקיים ש-LSL \in S
  • לכל LS{Σ,}L' \in S \setminus \{\Sigma^*, \emptyset\} מתקיים LpLL' \leq_{p} L.

לכל אחת ממחלקות השפות הבאות, קבעו האם יש שפה שלמה ביחס אליה. הוכיחו את תשובתכם.

  • NP
  • P
  • RE \cup coRE
  • קבוצת כל השפות מעל האלפבית {0,1}\{0,1\}
1

Answers

א. קיימות שפות שלמות, למשל SAT.

ב. כל שפה ב-P ניתן להכריע בזמן פולינומי ולכן ניתן לייצר רדוקציה מכל שפה לא טרוויאלית לכל שפה לא טרוויאלית.

ג. נניח בשלילה שקיימת שפה שלמה, LL, ב-RE, עבור שפה LcoRERL' \in \text{coRE} \setminus \text{R} נבנה מ"ט שמכריעה אותה:

  • על קלט ww חשב את w=f(w)w' = f(w), כאשר ff היא הרדוקציה הפולינומית המובטחת.
  • הרץ במקביל את MLM_L על ww' ואת MM על ww כאשר MLM_L מ"ט שמקבלת את LL ו-MM מ"ט שמקבלת את L\overline{L'}.
  • ענה כמו MLM_L או הפוך מ-MM מי שעוצרת ראשונה.

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

באופן דומה, אם קיימת שפה שלמה ב-coRE אז ניתן להכריע כל שפה ב-RE - סתירה.

ד. נפעיל שיקולי ספירה: מספר הרדוקציות הפולינומיות קטן שווה למספר המ"ט והוא בן מנייה. מצד שני מספר השפות אינו בן מנייה. נשים לב שלכל שתי שפות לא טריוויאליות שונות דרושות שתי רדוקציות שונות ולכן לא קיימת שפה שלמה כזו.

1
Feedback