Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.21450 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912730663878656 |
|---|---|
| author | Austrin, Per Håstad, Johan Martinsson, Björn |
| author_facet | Austrin, Per Håstad, Johan Martinsson, Björn |
| contents | A Boolean predicate $A$ is defined to be promise-useful if $\operatorname{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 $\text{P} \ne \text{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_21450 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Usefulness of Promises Austrin, Per Håstad, Johan Martinsson, Björn Computational Complexity A Boolean predicate $A$ is defined to be promise-useful if $\operatorname{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 $\text{P} \ne \text{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. |
| title | On the Usefulness of Promises |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2511.21450 |