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?
3
-
What if you flip a coin for each variable & apply linearity of expectation? – Juho 2 days ago
-
@Juho Maybe I'm missing something, but this would give you a correct answer rate of , wouldn't it? – idmean 2 days ago
-
Such an algorithm would show that SAT belongs to RP. – Steven yesterday
Add a comment
|
