Abstract
UML is the de-facto standard formalism for software design and analysis. One of the most important components of UML are class diagrams, which model the information on the domain of interest in terms of objects organized in classes and relationships between them. To support the design of large-scale industrial applications, CASE tools should be equipped with automated reasoning capabilities in order to detect relevant formal properties of UML diagrams, such as inconsistencies or redundancies. However, reasoning on UML class diagrams is fairly complex: in this paper we show that it is EXPTIME-hard.