New answers tagged randomized-algorithms
0
If $c < 1/2$ then for any problem there is an algorithm that answers correctly with probability at least $c+1/n$, say. For small $n$, the algorithm just outputs the hardwired correct answer. When $n$ is large enough so that $c + 1/n \leq 1/2$, the algorithm just tosses a coin.
What went wrong? For BPP amplification to work, we need a gap between the ...
3
Given an instance of knapsack, multiply all values by $k+1$. Any solution satisfyign $OPT(I) - P_A(I) \leq k$ is in fact optimal, so you could use such an algorithm to solve knapsack.
Top 50 recent answers are included
