A note on £2p-completeness of a robust binary linear program with binary uncertainty set

We show that the robust binary linear program with uncertain objective function and binary uncertainty set defined by linear constraints is £2p-complete. This result is then extended to the K-adaptability version of the problem, where one of K pre-calculated solutions can be chosen after the uncertain parameter is revealed.