# Question on randomized algorithm/hash function.

• Dec 11th 2011, 07:46 AM
complexity9
Question on randomized algorithm/hash function.
I have been trying to solve the problem in part (vi) for almost a whole week, but still not able to solve it. Please read the attachment before proceeding.

I was able to show that, using part (iii), we can construct a deterministic program S from P. Then S gives the same outcome as G for the same input. Therefore,

$F(x_1, ..., x_m) = 0 \Leftrightarrow \forall y_1, ..., y_n S(x_1, ..., x_m, y_1, ..., y_n) = 0$

and

$F(x_1, ..., x_m) = 1 \Leftrightarrow \exists y_1, ..., y_n S(x_1, ..., x_m, y_1, ..., y_n) = 1$

Now I need to find a way to modify S to get Q that satisfies the requirement in the question. They also gave a hint that I might be able to use the hash function to get the result.