1
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.