# VERY HARD randomized algorithm/hash function question. PLESE HELP!

1. Dec 11, 2011

### complexity9

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 if and only if \forall y_1, ..., y_n S(x_1, ..., x_m, y_1, ..., y_n) = 0

and

F(x_1, ..., x_m) = 1 if and only if \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.

-Peter

#### Attached Files:

File size:
51.1 KB
Views:
132
• ###### Untitled2.jpg
File size:
33 KB
Views:
145
2. Dec 14, 2011

### complexity9

*bump* anyone know how to solve this? help...