Skip to main content

Research Repository

Advanced Search

The complexity of achievement and maintenance problems in agent-based systems

Stewart, I.A.

The complexity of achievement and maintenance problems in agent-based systems Thumbnail


Authors



Abstract

We completely classify the computational complexity of the basic achievement and maintenance agent design problems in bounded environments when these problems are parameterized by the number of environment states and the number of agent actions. The different problems are P-complete, NP-complete, co-NP-complete or PSPACE-complete (when they are not trivial). We also consider alternative achievement and maintenance agent design problems by allowing longer runs in environments (that is, our environments are bounded but the bounds are more liberal than was the case previously). Again, we obtain a complete classification but so that the different problems are DEXPTIME-complete, NEXPTIME-complete, co-NEXPTIME-complete or NEXPSPACE-complete (when they are not trivial).

Citation

Stewart, I. (2003). The complexity of achievement and maintenance problems in agent-based systems. Artificial Intelligence, 146(2), 175-191. https://doi.org/10.1016/s0004-3702%2803%2900014-6

Journal Article Type Article
Publication Date Jun 1, 2003
Deposit Date Jun 29, 2009
Publicly Available Date Aug 25, 2009
Journal Artificial Intelligence
Print ISSN 0004-3702
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 146
Issue 2
Pages 175-191
DOI https://doi.org/10.1016/s0004-3702%2803%2900014-6
Keywords Computational complexity, Agent computing.
Publisher URL http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6TYF-4817DJD-2-1&_cdi=5617&_user=10&_orig=browse&_coverDate=06%2F30%2F2003&_sk=998539997&view=c&wchp=dGLzVzz-zSkzS&md5=b49aaf4ba9591799aaf734dae38e85c3&ie=/sdarticle.pdf

Files





You might also like



Downloadable Citations