Robust reductions

We continue the study of robust reductions initiated by Gavalda and Balcaza r. In particular, a 1991 paper of Gavalda and Balcazar [7] claimed an optim al separation between the power of robust and nondeterministic strong reduc tions. Unfortunately, their proof is invalid. We re-establish their theorem . Generalizing robust reductions, we note that robustly strong reductions a re built from two restrictions, robust underproductivity and robust overpro ductivity, both of which have been separately studied before in other conte xts. By systematically analyzing the power of these reductions, we explore the extent to which each restriction weakens the power of reductions. We sh ow that one of these reductions yields a new, strong form of the Karp-Lipto n theorem.