# How to design an unbounded Monte Carlo algorithm for SAT(Boolean Satisfiability Problem) problem?

I want the algorithm to be in polynomial time and the correct answer rate is 0.5 or more. (True / false judgment is polynomial time)

All the methods I think of take exponential time(2^n).

Can anyone help me?

• What if you flip a coin for each variable & apply linearity of expectation?
– Juho
Jul 22 at 9:46
• @Juho Maybe I'm missing something, but this would give you a correct answer rate of $0.5^n$ , wouldn't it? Jul 22 at 10:18
• Such an algorithm would show that SAT belongs to RP. Jul 23 at 12:09