complexity9
- 14
- 0
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.
Please help anyone! Some advice would also be useful even if you can't completely solve it. Please! Thanks you!
-Peter
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.
Please help anyone! Some advice would also be useful even if you can't completely solve it. Please! Thanks you!
-Peter
