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

@article{citeulike:5069969, 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).}, author = {Stewart, I.}, citeulike-article-id = {5069969}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0004-3702(03)00014-6}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0004-3702(03)00014-6}, comment = {Two flavours of complexity collide - big O, and multi-agent - in particular, looking at the big O complexity of the management of various simulations using agents}, doi = {10.1016/S0004-3702(03)00014-6}, issn = {00043702}, journal = {Artificial Intelligence}, keywords = {agents, complexity, compsci, simulation}, month = {June}, number = {2}, pages = {175--191}, posted-at = {2009-07-06 01:52:19}, priority = {4}, title = {The complexity of achievement and maintenance problems in agent-based systems}, url = {http://dx.doi.org/10.1016/S0004-3702(03)00014-6}, volume = {146}, year = {2003} }

TY - JOUR ID - citeulike:5069969 L3 - citeulike-article-id:5069969 N2 - 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). IS - 2 JF - Artificial Intelligence SN - 00043702 EP - 191 TI - The complexity of achievement and maintenance problems in agent-based systems VL - 146 SP - 175 KW - agents KW - complexity KW - compsci KW - simulation N1 - Two flavours of complexity collide - big O, and multi-agent - in particular, looking at the big O complexity of the management of various simulations using agents AU - Stewart, I PY - 2003/06// UR - http://dx.doi.org/10.1016/S0004-3702(03)00014-6 ER -