שאלות 7, 8 מהמבחן מועד א
arisha84
(השאלות על המ"ט הסתברותית, והמ"ט הדטרמניסטית)
eviatark
המחלקות האפשריות שונות, PSPACE זוהי האפשרות היחידה.
לגבי המכונה ההסתברותית, אני לא בטוח, אבל נראה לי שהמכונה יכולה לקבל עד
שיהיה "ההגרלה" עבורה M דוחה, ולכן לא יכולה לקבל בהסתברות 1.
Oren Z
I sent you some explanation which I think might be the answer, but it
was by mistake... I wanted to post it here so anyone can see and
comment - I clicked "reply to author" instead of "reply" by mistake.
Can you please post the message I sent to you?
Oren Z
כמו אל "מבלי לעזוב את t התאים הראשונים" (התבלבלתי עם השאלה הקודמת). אם
אפשר לקבל את הפתרון ששלחתי לך בבקשה אני אולי אוכל לעבור עליו ולתקן
אותו.
arisha84
Regarding the question with the probabilistic TM, the problem is in
coNP.
I think that I have a proof as to why it's in coNP so I'll post it
here, if there is anything wrong with it please correct me.
As to why it's not in NL I don't have a proof but when I was thinking
about this question I tried different things and it seemed pretty
clear that it cannot be in NL (and thus not in L either - of course).
So why it is in coNP? Suppose that with have some input to our problem
<M, x, 1^t> which does NOT belong to the language/problem we are
dealing with, so it means that either M(x, r) passes beyond t cells or
M(x, r) = 0 for some random string r (if I'm not mistaken :P).
Now, first thing we do is take M's code and modify it like this:
We add a counter which will tell us where M's reader/writer head is
located at any moment at time, to do so we change the "function" which
moves the reader/writer head so it updates our counter appropriately -
can be done in poly' time with respect to M's size and that's also
poly' with respect to our input size since our input is: <M, x, 1^t>.
So we tweaked M's code and now we have a counter, right after where we
added the procedure which updates the counter we need to add a
condition like this:
if (counter > t) return 0;
(the above can also be done while still maintaining poly' time of
course)
The result is that each time the head moves, the counter is updated
and then it's value is checked against t - if it's larger than t, then
M' (our modified version for M) returns 0.
Reminder: if <M, x, 1^t> does not belong to our problem then either M
(x, r) passes beyond t cells or M(x, r) = 0 for some random string r.
Now we can finally describe our verifier and the witness which show
that <M, x, 1^t> does not belong to the language/problem we are
dealing with:
The witness: r - the random string for which either M(x, r) passes
beyond t cells or M(x, r) = 0
The verifier: simply take M', run it with input (x, r) and return the
opposite of what it gives you.
Explanation: if <M, x, 1^t> does not belong to our problem then either
M(x, r) passes beyond t cells or M(x, r) = 0 for some random string r:
If it the reason for not being in the language is because M passes
beyond t cells, then M' will return 0 since that's how we constructed
M' and thus our verifier returns 1.
If it the reason for not being in the language is because M(x, r) = 0
then M' also returns 0 and thus our verifier returns 1.
Ok now, that was pretty long and I'm not even sure all of this (or any
of this :P) is correct LOL, if someone think/know something is wrong
then let me know. If it's correct, also let me know.
Oren Z
previous one (with question 3 from the test's first version).
Here is a correction, please let me know if now it makes sense:
Instead of our counter, M' will use a stepper function (like we did in
Modelim) and after each step, we'll check that we didn't make more
than t steps so far - if everything is fine and no more than t steps
had been done so far - we continue, otherwise M' stops and returns 0.
What I'm not sure about is that we can modify M in order to get
M' (which is M with a stepper) in poly' time... any ideas?