Stewart, I. A. (2003) 'The complexity of achievement and maintenance problems in agent-based systems.', Artificial intelligence., 146 (2). pp. 175-191.
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).
|Keywords:||Computational complexity, Agent computing.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (156Kb)
|Publisher Web site:||http://dx.doi.org/10.1016/S0004-3702(03)00014-6|
|Date accepted:||No date available|
|Date deposited:||25 August 2009|
|Date of first online publication:||June 2003|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|