We investigate solutions to problems of air traffic control subject to real-world limitations on the computational/communication cost of finding that solution. The approach involves direct quantification of controllability of the system via establishing a set of comprehensive physical constraints on trajectory calculations. We develop practical and quantifiable measures of controllability and complexity to facilitate provability of system safety and inform the needs of functional allocation. Controlling air traffic on all temporal and spatial scales – from a single aircraft to the entire airspace – can be formally stated as a dynamic, high-dimensional optimization problem with many objectives and constraints based on physics, economics, information, and other considerations. Especially in the future NAS, attempting to find the optimal solution to such problems as they arise during operations would often violate practical constraints such as computation time and/or communication resources. The issue is how to find the best solution subject to such constraints on the solution-finding algorithm. We propose to approach this as a multilevel optimization problem, where a complexity measure F maps the combination of s and an algorithm alpha (e.g., an algorithm that searches over a specified class of fine-grained traffic flows all having a given large-scale flow) to whether applying alpha to s would violate the practical constraints. Given F, the higher level optimization problem identifies the member of a set A of candidate algorithms that has best likely value of the objective functions, subject to provided practical constraints on the algorithm. A lower level optimizer then runs that algorithm and by construction is likely to do so within the given practical constraints. The technical approach will use mathematical programming, Probability Collectives (PC), and Machine Learning (ML), among other areas. The ultimate goal is a methodology and tools for use both in research and as a decision-making aid for all system participants, including aircraft pilots and automatic systems, air traffic controllers, and airlines.