{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T23:38:17Z","timestamp":1761176297799,"version":"build-2065373602"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"value":"9781643686318","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T00:00:00Z","timestamp":1761004800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,10,21]]},"abstract":"<jats:p>We analyse the computational complexity of two types of partial satisfaction planning problems, namely, over-subscription planning and net-benefit planning. Partial satisfaction planning seeks to maximise the rewards, or net-benefit between the rewards and costs, that can be obtained by achieving a set of (candidate) goals, generally under a cost budget. In this paper, we assume that the cost budget is polynomially bounded with respect to the number of atoms. In contrast to previous works on complexity analysis, we view partial satisfaction planning as optimisation tasks instead of decision ones. Accordingly, we classify over-subscription and net-benefit planning problems in classes within the optimisation complexity framework. Let L be the size of the partial satisfaction planning instance, we first show that both optimisation problems are OptP[LO(1)]-complete. We then prove that while over-subscription planning becomes OptP[O(log L)]-complete under uniform goal rewards and uniform action costs, the complexity of net-benefit planning remains unchanged. Our results show that the relative values of rewards and costs may impact the computational complexity of partial satisfaction planning, and that an optimisation perspective can reveal differences that may otherwise be lost in their decision formulations. In addition, an optimisation complexity analysis can provide insights on approximation properties of these problems.<\/jats:p>","DOI":"10.3233\/faia251402","type":"book-chapter","created":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T10:01:21Z","timestamp":1761127281000},"source":"Crossref","is-referenced-by-count":0,"title":["On the Computational Complexity of Partial Satisfaction Planning"],"prefix":"10.3233","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-7575-2401","authenticated-orcid":false,"given":"Jiajia","family":"Song","sequence":"first","affiliation":[{"name":"The University of Melbourne"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6984-4007","authenticated-orcid":false,"given":"Seeun William","family":"Umboh","sequence":"additional","affiliation":[{"name":"The University of Melbourne"},{"name":"ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8667-3681","authenticated-orcid":false,"given":"Nir","family":"Lipovetzky","sequence":"additional","affiliation":[{"name":"The University of Melbourne"},{"name":"ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2962-0118","authenticated-orcid":false,"given":"Sebastian","family":"Sardina","sequence":"additional","affiliation":[{"name":"RMIT University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2025"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA251402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T10:01:22Z","timestamp":1761127282000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA251402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,21]]},"ISBN":["9781643686318"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia251402","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,21]]}}}