שאלות פתוחות ממבחן cc08a-b-ans
Yossi
2. בהינתן שפה L' נגדיר גרף G(L',n) G = על 2 בחזקת n צמתים באופן הבא:
שני צמתים u ו- v מחוברים אם ורק אם הקידוד הבינארי של uv (באורך 2n)
שייך ל- L' . נשים לב שכל שפה מגדירה גרף שונה לכל מספר טבעי n. בשאלה זו
נעסוק בסיבוכיות של שתי שפות, בהינתן מכונה שעוצרת תמיד ומשתמשת בזיכרון
פולינומיאלי. הקלט הוא מהצורה (M,1^n), כלומר קידוד המכונה ולאחריו n
פעמים '1'.
א. הוכח שבעיית ההכרעה בה מתקבל קלט M כנ"ל ויש להכריע האם הגרף ( GL(M,n
הוא דו צדדי היא ב- PSPACE.
ב. הראה שהבעייה מ- א' היא PSPACE שלמה.
בקשר לא': לא הצלחתי לחשוב על האלגוריתם הבא: ננחש מעגל אי-זוגי בגרף. אם
קיים, נחזיר F.
אבל - זה מצריך עד באורך 2 בחזקת n, שאינו פולי' ביחס לקלט, אז אני לא
מאמין שזה יעבוד.
בקשר לב' אין לי מושג
kiri...@gmail.com
התחלה ולנחש מעגל, כלומר בכל צעד לוודא שלא הגעת לנקודת ההתחלה.
כל הזיכרון שאתה צריך בשביל זה הוא מונה למספר הקודקודים שעברת בגרף
ומונה המחזיק את צומת ההתחלה.
בקשר ל-ב' אם תנפח את הבעיה, תקבל בעיה שהיא
NL
לאורך הקלט.
קודם כל הבעיה של מציאת מעגל באורך אי זוגי היא שלמה ב-
NL.
אפשר להראות בקלות ע"י רדוקציה מ-
CONN
(אם תסתבך שאל אותי כיצד(
בנוסף קל להראות רדוקציה מהבעיה של מציאת מעגל באורך אי זוגי לבעיה שיש
לנו בשאלה לאחר שניפחנו אותה.
לכן הבעיה החדשה היא NL שלמה.
עכשיו אתה גם יכול לקחת כל בעיה ב-PSPACE, לנפח אותה, להפוך אותה ל-NL
ולהראות רדוקצית מקום לוגריתמית לבעיה המנופחת שלנו.
אם תוריד את הניפוח תקבל רדוקצית מקום פול', מה שבהחלט מספק אותנו מאחר
ואנחנו רוצים להוכיח שלמות ב-PSPACE
מקווה שהייתי ברור,
ולעזאזל עם העברית ההפוכה הזאת!
kiri...@gmail.com
לוגריתמית ולא פולינומיאלית.
odedr
Here are my thoughts on this:
A.
One way to solve it is to show that it in NPSPACE (i.e.,
nondeterministic machine with polynomial space) and
then use Savitch theorem (which implies NPSPACE=PSPACE)
to conclude that it is in PSPACE.
In order to show that it is in NPSPACE, you construct a
machine that tries to guess an odd cycle in the graph
(since existence of odd cycle is equivalent to not being bipartite).
The 'witness' here (i.e., the sequence of nondeterministic
choices) is of exponential length, but this is not a problem:
the definition of NPSPACE allows this (the only requirement
is on the size of the storage space).
Notice that this shows that "not bipartite" is in PSPACE.
But since PSPACE is trivially closed under complement,
we also get that "bipartite" is in PSPACE.
(I think this is what Kiril was trying to say, but I'm not sure;
his answer was too sketchy this time)
B.
Here I think Kiril's answer is wrong (but I might be mistaken).
I don't see how to prove PSPACE completeness using
padding.
The solution, I think, is much simpler:
Because the machine M is allowed to do any poly-space computations,
we can use it to solve our input problem. Let me explain how:
We want to show that our problem is PSPACE-hard (under poly-time
Karp reductions, as usual). So let L be an arbitrary language in
PSPACE
and let M be a poly-space machine that solves L. The reduction takes
an input x to L and outputs the pair (M',1^n) where n is the length of
x and
M' is the following machine: it simply outputs the negation of M(x).
Correctness:
If M(x) is true, then the graph described by M' is the empty graph
(no edges anywhere). If M(x) is false, then the graph described
by M' is the complete graph (edges between any two vertices).
Notice that the empty graph is bipartite, and that the complete
graph is not bipartite. So if M(x)=T, we end up with an instance
in our language, and similarly if M(x)=F we end up with an
instance not in our language.
Running time:
The reduction is in polynomial time. All it does is take an input
x and output the pair (M',1^n) where M' is the code of an algorithm
that can be easily created from the code of M.
-- Oded
