1. הוכיחו כי בעיות ההכרעה שלהלן שייכות למחלקת הסיבוכיות L. 1. קלט: גרף לא מכוון G=(V,E) וקבוצת קודקודים S V. ש…

הוכיחו כי בעיות ההכרעה שלהלן שייכות למחלקת הסיבוכיות $L$.

1. קלט: גרף לא מכוון $G=(V,E)$ וקבוצת קודקודים $S\subseteq V$.
   שאלה: האם הקבוצה $S$ היא כיסוי קודקודים ב-$G$?
2. קלט: גרף מכוון $G$ שדרגת היציאה של כל קודקוד בו היא לכל היותר $1$.
   שאלה: האם קיים ב-$G$ מעגל?

הוכיחו כי בעיות ההכרעה שלהלן הן $NL$-שלמות.

1. קלט: גרף מכוון $G=(V,E)$ ושני קודקודים $s,t\in V$.
   שאלה: האם קיימים בגרף $G$ שני מסלולים שונים מ-$s$ ל-$t$?
2. קלט: גרף מכוון $G=(V,E)$ ושני קודקודים $s,t\in V$.
   שאלה: האם קיים בגרף $G$ מסלול מ-$s$ ל-$t$ ש-$3$ מחלק את מספר קשתותיו?
3. קלט: גרף מכוון $G=(V,E)$.
   שאלה: האם קיימת קבוצת קודקודים $S\subseteq V$ בגודל $|S|=|V|-100$ שבין כל שניים מהם קיים מסלול ב-$G$, בשני הכיוונים?

תהא $B$ שפה, ותהא

הוכיחו כי אם $A\in L$ אז $B\in PSPACE$.

שימו לב לא לחרוג ממגבלת סיבוכיות המקום!