The term “promise problem” refers to computational problems for which a solution must be found only on certain inputs (that is, on inputs for which the “promise” holds). Promise problems arise, among other places, in the study of cryptographic systems, where the problem of decoding a message is important only for those inputs that satisfy the promise that they are, in fact, encrypted messages. In general, not much is known about the relationship between the complexity of a problem and the complexity of solving various promise versions of that problem.
In this well-written paper, the authors focus on one particular type of promise problem: given a set A, let PP-A be the problem of taking two inputs x and y, and determining whether x is in A, under the promise that exactly one of x and y is in A. (This promise problem arises naturally from the study of p-selective sets, which have been studied extensively by Selman and others.) The main result of the paper is that if A is NP-hard, then all solutions of PP-A are “nearly” NP-hard. (More precisely, all such solutions are generalized high2.) Along the way, some intermediate results are proven, which can in turn be used to give simpler proofs of previously known results concerning sparse and p-selective sets.
