Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

Stewart, I. A. (2003) 'The complexity of achievement and maintenance problems in agent-based systems.', Artificial intelligence., 146 (2). pp. 175-191.

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).

Item Type:Article
Keywords:Computational complexity, Agent computing.
Full text:PDF - Accepted Version (156Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/S0004-3702(03)00014-6
Record Created:29 Jun 2009 15:35
Last Modified:10 Nov 2011 11:02

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library