The problem comes from network coding area. A wireless server holds a set of data packets and would like to broadcast a set of coded packets to the receivers to optimize a certain performance metric, where each coded packet is a linear combination of the data packets. I have proved that it is NP-hard to find the optimal coded packets when every coded packet can be received by every receiver. My question is that, is it still NP-hard to find the optimal coded packets when the receivers may randomly miss the coded packets? It is like "If making the optimal life-changing choice is already hard when you can foresee the future, is the choice still hard to make if you cannot foresee the future?" - toss a coin is out of the scope ...