Question

pspace

נגדיר את מחלקת השפות P\oplus P:

שפה LL נמצאת ב-P\oplus P אם קיימת מ"ט א"ד פולינומית MM כך ש:

  • לכלxLx \in L מספר המסלולים המקבלים של MM הוא אי זוגי.
  • לכלxLx \notin L מספר המסלולים המקבלים של MM הוא זוגי.

ענו בקצרה על הסעיפים הבאים:

  • הוכיחו/הפריכו: PPSPACE\oplus P \subseteq \text{PSPACE}.
  • הוכיחו/הפריכו: אם L1,L2PL_1,L_2 \in \oplus P אז L1L2PL_1 \cap L_2 \in \oplus P.
1

Answers

1. נכון, אם LPL \in \oplus P אז קיימת לה מ"ט א"ד, MM, כמתואר. נראה שקיימת מ"ט עם זיכרון פולינומי, MM', שמכריעה את LL.

המ"ט MM' על קלט ww מסמלצת את MM ובנוסף זוכרת ביט בודד שמסמל אם MM קיבלה במספר זוגי או אי-זוגי של מסלולים' MM' מקבלת בהתאם. קל לראות שניתן לעשות זאת בזיכרון פולינומי וש-MM' מקבלת אמ"מ MM מקבלת.

2. נכון, נניח ש-L1,L2PL_1, L_2 \in \oplus P אז קיימות M1M_1 ו-M2M_2 כמתואר בהתאמה.

נתאר מ"ט א"ד, M12M_{12} כך שאם wL1L2w \in L_1 \cap L_2 אז M12M_{12} מספר המסלולים המקבלים ב-M12M_{12} הוא זוגי ואחרת מספר המסלולים המקבלים אי-זוגי.

המ"ט M12M_{12} על קלט ww תתנהג כשרשור של המכונות M1M_1 ו-M2M_2.

נשים לב שאם wL1L2w \in L_1 \cap L_2 נשים לב שמספר המסלולים המקבלים של M12M_12 הוא מכפלת מספר המסלולים המקבלים של M1M_1 ו-M2M_2 ומספר זה עונה לתנאים.

1
Feedback