Abstract : The Extended ATC Planning (EAP) function aims at bridging the gap between Air Traffic Flow & Capacity Management (ATFCM) and Air Traffic Control (ATC) by predicting air traffic congested areas tens of minutes before their formation, and by suggesting real-time and fine-tuning measures to alleviate airspace "complexity". Current Air Traffic Flow Prediction methods focus on crude aircraft count in a sector, and hence are unable to distinguish between low and high complexity situations for a similar aircraft count. Complexity indicators, on the other hand, aggregate air traffic measurements and workload to describe the perceived complexity. However, the evaluation of workload is a long-debated issue and an inherently ill-posed problem. In this work, we present an intrinsic complexity metric, independent of any traffic control system, and address the prediction task of the EAP function using a novel Encoder-Decoder Long Short-Term Memory (LSTM) neural network. The complexity is measured by the eigenvalues of a linear dynamical system fitted to the aircraft's speed vectors. The Encoder-Decoder LSTM network uses a sequence of (discrete) aircraft states to predict the complexity of the air traffic in all areas of an airspace, in a time horizon of 40 minutes. Simulated traffic corresponding to one day of traffic over the French airspace is used to train and validate the model. Our experiments show that the proposed model achieves a Mean Absolute Error of 0.08 in predicting the normalized complexity value 40 minutes in the future.