1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
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!

  1. Dec 11, 2011 #1
    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


    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!


    Attached Files:

  2. jcsd
  3. Dec 14, 2011 #2
    *bump* anyone know how to solve this? help...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook