Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

New answers tagged


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 ...


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