Computational Complexity of a Constraint
Model-based Proof of the Envelope of Tendencies in a MAS-based
Simulation Model
CPM Report No.: 02-98
By: Oswaldo Terán and Bruce Edmonds
Date: 15th May 2002To 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.
Accessible as: