Air Traffic Management (ATM) is formally defined as the dynamic, integrated management of air traffic and airspace safely, economically and efficiently, through the provision of facilities and seamless services in collaboration with all parties and involving airborne and ground-based functions. This implies a complex socio-technical system with several layers and sub-systems. The performance of these layers is measured through various Key Performance Areas (KPAs), of which some of the most important are safety, capacity, cost-efficiency and the environmental impact. Although part of ATM structure, each of the layers have different objectives which in practice compete to maximize their own goals. A similar situation can be expected for Unmanned Aerial Systems (UAS), where the development of different UAS traffic management systems is being guided with a similar approach to that of ATM. In this thesis, we envision air traffic complexity to be the framework through which a common understanding among stakeholders making decisions at the different ATM layers is enhanced. Furthermore, we focus on automated Conflict Detection and Resolution (CD&R) to investigate how Multi-Agent Reinforcement Learning (MARL) can facilitate the progress to autonomous ATM and UAS traffic management systems. To achieve these goals, we first define air traffic complexity in such a way that provides elaborate information efficiently to different stakeholders. As an initial step, we provide a generic definition of pairwise interdependencies between aircraft, which is based on the distance at a time step and is adaptive to the use-case and context. We use graph theory to model air traffic as a dynamic graph and define four complexity indicators that combine different topological information and the severity of the interdependencies to give a detailed and nuanced evolution of traffic complexity in a certain airspace. These indicators are extended to introduce the concept of single aircraft complexity, through which complex spatio-temporal areas in a given airspace are identified. Moreover, we investigate the effectiveness of these complexity indicators in the domain of UAS, to show how the same definition of air traffic complexity can be used in different domains. Focusing on CD&R, we approach this problem through MARL, which is a paradigm of Machine Learning (ML) where multiple agents interact with an environment and themselves to maximize some notion of accumulated reward. We first extend existing work by proposing a model that not only solves conflicts but also show that it is possible to consider several other factors that affect efficiency and the environmental impact. This approach is further enhanced by the use of Graph Neural Networks (GNNs), which facilitate cooperation and communication. We show that through cooperation it is possible for autonomous agents to learn resolution strategies that are similar to known strategies by human controllers, which existing work using GNNs has not been able to achieve. While these two goals might seem separate, in this thesis we argue that a unified air traffic complexity management system with the application of AI can move aviation further to its quest for autonomy. This thesis is concluded with a vision for AI in aviation that considers meaningful human control and value alignment as the most imperative directions for future research.