VERY HARD randomized algorithm/hash function question. PLESE HELP

In summary, the speaker has been struggling for a week to solve a problem in part (vi). They have shown that a deterministic program S can be constructed from P, and it yields the same outcome as G for the same input. They now need to modify S to get Q, and a hint has been given to potentially use a hash function. They are seeking help and advice from others.
  • #1
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
 

Attachments

  • Untitled1.jpg
    Untitled1.jpg
    51.1 KB · Views: 479
  • Untitled2.jpg
    Untitled2.jpg
    33 KB · Views: 472
Mathematics news on Phys.org
  • #2
*bump* anyone know how to solve this? help...
 

1. What is a randomized algorithm/hash function?

A randomized algorithm/hash function is a computational procedure that uses a random element in its design or execution to achieve its desired goal. It is used in computer science to solve problems that require a large amount of computational power.

2. What makes a randomized algorithm/hash function "very hard"?

A randomized algorithm/hash function is considered "very hard" when it is extremely difficult to predict the output or behavior of the algorithm. This is often due to the use of random elements, making it challenging to analyze and solve the problem using traditional methods.

3. What are some common applications of randomized algorithms/hash functions?

Randomized algorithms/hash functions have a wide range of applications, including data encryption, data compression, simulation, and optimization problems. They are also used in machine learning, artificial intelligence, and cryptography.

4. How do you measure the efficiency of a randomized algorithm/hash function?

The efficiency of a randomized algorithm/hash function is typically measured by its time complexity, which is the amount of time it takes to execute on a given input. Space complexity, which measures the amount of memory required by the algorithm, is also used in some cases.

5. Are there any drawbacks to using randomized algorithms/hash functions?

While randomized algorithms/hash functions have many practical applications, they can also have some drawbacks. These include the potential for errors due to the use of random elements, the difficulty in analyzing their behavior, and the fact that they may not always produce the same output for the same input.

Similar threads

  • General Math
4
Replies
125
Views
16K
Replies
2
Views
860
  • Linear and Abstract Algebra
Replies
3
Views
908
  • Topology and Analysis
Replies
7
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
754
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Math Proof Training and Practice
4
Replies
105
Views
12K
  • Math Proof Training and Practice
2
Replies
61
Views
9K
  • Math Proof Training and Practice
5
Replies
150
Views
15K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
Back
Top