In this paper we study the issue of characterizing the complexity of air traffic to support Air Traffic Management (ATM) operations. We discuss, in particular, the features of a complexity metric that are relevant for application to future ATM systems where part of the responsibility for separation assurance and trajectory management operations is distributed on board of the aircraft. We then describe a probabilistic complexity metric that meets all those features and is amenable for supporting onboard conflict detection and resolution and trajectory management operations. A numerical example illustrates its possible use in a fully automated self-separation context.