{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T21:06:46Z","timestamp":1725656806928},"reference-count":0,"publisher":"EasyChair","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Motivated by satisfiability of constraints with function symbols, we consider numerical inequalities on non-negative integers. The constraints we address are a conjunction of a linear system Ax = b and an arbitrary number of (reverse) convex constraints of the form xi \u2265 xdj (xi \u2264 xdj ). We show that the satisfiability of these constraints is NP-complete even if the solution to the linear part is given explicitly. As a consequence, we obtain NP- completeness for an extension of certain quantifier-free constraints on sets with cardinalities and function images.<\/jats:p>","DOI":"10.29007\/wdd7","type":"proceedings-article","created":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T22:10:10Z","timestamp":1685830210000},"page":"350-330","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of Convex and Reverse Convex Prequadratic Constraints"],"prefix":"10.29007","volume":"94","author":[{"given":"Rodrigo","family":"Raya","sequence":"first","affiliation":[]},{"given":"Jad","family":"Hamza","sequence":"additional","affiliation":[]},{"given":"Viktor","family":"Kuncak","sequence":"additional","affiliation":[]}],"member":"11545","event":{"name":"Proceedings of 24th International Conference on Logic for Programming, Artificial Intelligence and Reasoning"},"container-title":["EPiC Series in Computing"],"original-title":[],"deposited":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T22:10:22Z","timestamp":1685830222000},"score":1,"resource":{"primary":{"URL":"https:\/\/easychair.org\/publications\/paper\/T6kG"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":0,"URL":"https:\/\/doi.org\/10.29007\/wdd7","relation":{},"ISSN":["2398-7340"],"issn-type":[{"type":"print","value":"2398-7340"}],"subject":[]}}