2025/11/26 by Austrin, Per, Håstad, Johan, Martinsson, Björn
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2511.21450
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 promise-uselessness (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.