Two simple randomized algorithms

In this article, I introduced Two simple randomized algorithms.
one is called matrix verfication algorithm which is very powerful and remarkable.

Go back to Main page Notes for Complexity theory

The other is so called 3 cnf formula.

3 cnf is Np complete. One need brute force (2^n) to find the such solution. But if we only care about satisfy maximum number of clauses. One could use the randomized algorithm. One can satisfy 87.5% of all clauses .