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.(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

Loading...

Similar Threads - VERY HARD randomized | Date |
---|---|

B Complex Numbers in a Simple Example that I am Very Confused | Jan 23, 2017 |

Very hard problems about work | May 24, 2015 |

Having a very hard time in my PRECALC CLASS | Jan 17, 2013 |

Very HARD maths question | Mar 13, 2005 |

IQ of 110+ This is very hard, Question 1 | Jun 10, 2004 |

**Physics Forums - The Fusion of Science and Community**