Results 1 to 1 of 1

Math Help - Question on randomized algorithm/hash function.

  1. #1
    Newbie
    Joined
    Dec 2011
    Posts
    16

    Question on randomized algorithm/hash function.

    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
    Attached Thumbnails Attached Thumbnails Question on randomized algorithm/hash function.-untitled1.jpg   Question on randomized algorithm/hash function.-untitled2.jpg  
    Last edited by mr fantastic; December 11th 2011 at 12:15 PM. Reason: Title.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hash functions.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 7th 2011, 11:27 AM
  2. Randomized Convergence
    Posted in the Advanced Statistics Forum
    Replies: 8
    Last Post: December 29th 2010, 12:21 PM
  3. why should a hash table be prime number length?
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: May 7th 2010, 05:30 PM
  4. a strongly universal (p,p)-hash family
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 3rd 2009, 03:47 PM
  5. completey randomized ANOVA
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: June 18th 2006, 12:18 AM

Search Tags


/mathhelpforum @mathhelpforum