Question on randomized algorithm/hash function.

**complexity9** · December 11th 2011, 07:46 AM

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.

Please help anyone! Some advice would also be useful even if you can't completely solve it. Please! Thanks you!

-Peter

Thread: Question on randomized algorithm/hash function.

LinkBack

Thread Tools

Display

Question on randomized algorithm/hash function.

Similar Math Help Forum Discussions

Hash functions.

Randomized Convergence

why should a hash table be prime number length?

a strongly universal (p,p)-hash family

completey randomized ANOVA

Search Tags