On the Usefulness of Promises

A Boolean predicate A is defined to be promise-useful if PCSP(A, B) is tractable for some non-trivial B and otherwise it is promise-useless. We initiate investigations of this notion and derive sufficient conditions for both promise-usefulness and promiseuselessness (assuming P ̸ = NP). While we do not obtain a complete characterization, our conditions are sufficient to classify all predicates of arity at most 4 and almost all predicates of arity 5. We also derive asymptotic results to show that for large arities a vast majority of all predicates are promise-useless.

Our results are primarily obtained by a thorough study of the "Promise-SAT" problem, in which we are given a k-SAT instance with the promise that there is a satisfying assignment for which the literal values of each clause satisfy some additional constraint.

The algorithmic results are based on the basic LP + affine IP algorithm of Brakensiek et al. (SICOMP, 2020) while we use a number of novel criteria to establish NP-hardness.