Paper accepted at ECAI25: “On the Computational Complexity of Partial Satisfaction Planning” with Jiajia Song, Nir Lipovetzky and Sebastian Sardina.