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

שאלה פתוחהq-0ed4973ee74e

נוסח השאלה

הוכיחו כי בעיות ההכרעה שלהלן שייכות למחלקת הסיבוכיות $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=\left\{\left\langle x,0^{2^{|x|}}\right\rangle\ \middle|\ x\in B\right\}.$
הוכיחו כי אם $A\in L$ אז $B\in PSPACE$ .

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

נוסח מטלה שנבדק אנושית.

Exact provenance

Each card is a genuinely distinct file. Printed versions inside one PDF stay in that card and do not inflate the sitting count.

Assignment

2025_06_תרגיל_6.md

Question 3Page 1Human reviewed