Discussion papers

CPM-02-98 - 15 May 2002

Computational Complexity of a Constraint Model-based Proof of the Envelope of Tendencies in a MAS-based Simulation Model

Oswaldo Terán and Bruce Edmonds

To be presented as: Terán, O and Edmonds, B. (2002) Computational Complexity of a Constraint Model-based Proof of the Envelope of Tendencies in a MAS-based Simulation Model, 2nd International Workshop on Complexity in Automated Deduction (CiAD), at CADE-18, Copenhagen, Denmark, July, 2002.

Abstract

This paper determines the complexity of a constraint model-based proof of the envelope of a tendency in the dynamics of a Multi-Agent-based Simulation model. The proof is performed via a constraint model-based exploration of simulation trajectories using forward inference, by means of which a whole fragment of the simulation model theory is investigated. Such exploration allows for all simulation trajectories defined by a range of parameters of the model and a range of choices of the agents. The paper verifies that the search is coNP-complete.

Downloads