The Computational Complexity of Agent Verification

摘要

In this paper, we investigate the computational complexity of the agent verification problem. Informally, this problem can be understood as follows. Given representations of an agent, an environment, and a task we wish the agent to carry out in this environment, can the agent be guaranteed to carry out the task successfully? Following a formal definition of agents, environments, and tasks, we establish two results, which relate the computational complexity of the agent verification problem to the complexity of the task specification (how hard it is to decide whether or not an agent has succeeded). We first show that for tasks with specifications that are in Σ_u~p, the corresponding agent verification problem is ∏_(u+1)~p-complete; we then show that for PSPACE-complete task specifications, the corresponding verification problem is no worse ― it is also PSPACE-complete. Some variations of these problems are investigated. We then use these results to analyse the computational complexity of various common kinds of tasks, including achievement and maintenance tasks, and tasks that are specified as arbitrary Boolean combinations of achievement and maintenance tasks.