On the Usefulness of Promises

A Boolean predicate \(A\) is defined to be promise-useful if \(\textrm{PCSP}(A,B)\) is tractable for some nontrivial Boolean predicate \(B\) and otherwise it is promise-useless. We initiate investigations of this notion and derive sufficient conditions for both promise-usefulness and promise-uselessness (assuming P \(\ne\) 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.