The World’s Toughest Problems
A recent issue of Technology Review (October 2021) features an article, “The problem to end all problems,” by Siobhan Roberts. This article addresses the treasured problem of “P versus NP,” the holy grail of theoretical computer science and mathematics. Can particular problems by solved in polynomial time (nx) or non-polynomial time (en), where n is the number of nodes in a network representation of the problem?
Typical problems of interest include the knapsack problem (seeking the optimal way to pack a constrained space with the most valuable items), the traveling salesman problem (finding the shortest possible route that visits each city once and returns to the city of origin), and the Steiner tree problem (seeking to optimally connect a set of points with line segments of minimum total length). These problems are particularly difficult when the traveling salesman wants to visit one million cities.
Of course, these three classic problems are just placeholders for a wide range of other important optimization problems. I do not doubt the importance of these problems, but are they really the world’s toughest problems? They assume a fixed, albeit very large, network structure with known, and non-varying, links among nodes in this structure. These classic problems are completely deterministic. The central difficulty is the large numbers of nodes.
What if the number of nodes is not known, the relationships among nodes is uncertain, and may vary in time, and the behaviors of nodes may change in reaction to social situations, economic policies, political conflicts, and climate challenges? What types of problems can be characterized in these ways? How might they be more difficult than the complexity theorists’ world’s toughest problems?
Consider the nature of the US economy in health, education, energy, and security sectors. In healthcare delivery, there are 295,000 primary care professionals, including 209,000 physicians, 552,000 specialty physicians, 6,100 hospitals and 1,200 clinics, and 330 million patients. Higher education in the US includes 14,000 public school districts, 131,000 schools, 3.6 million teachers, and 51 million students.
The electric energy industry in the US includes 3,300 electric utilities, generating electricity via 1.5 million solar panels, 57,000 wind turbines, 1,500 hydro power plants, 7 million workers across the energy industry, and 330 million consumers. National security in the US employs almost 3 million people, deployed in roughly 500 military installations in US in every state, and roughly 100 installations internationally, with millions of weapon systems deployed.
Each of these four ecosystems would easily be considered complex networks by researchers in computer science and mathematics – indeed, everyone would see these ecosystems as complex. With significant difficulty, we could define each node in these networks of millions of nodes and, with even more difficulty, we might be able to define relationships among nodes, not just in specifications of connections, but in terms what information, resources, and services flow among nodes.
What would we like to compute and what value could be associated with the results of these computations? It seems to me that the optimal, e.g., shortest, route among all these nodes would not be very interesting. The most effective ways to communicate with and convince the network to adopt some particular behaviors, e.g., getting vaccinated or adopting green energy practices, would likely be valuable. Unfortunately, knowledge that two nodes are connected is not sufficient to enable these behaviors.
We need much deeper understanding of the behavioral and social sciences phenomena underlying nodes and relationships among nodes. Understanding the physics of what is connected to what is necessary but far from sufficient. Similarly, knowing the street map for a city provides a minimal starting point for predicting how the city will innovate in the arts, science, and business.
My sense is that Roberts’ “world’s toughest problems” characterize solutions to large, static, deterministic problems where the network of interest is fixed and unchanging. This is not a good characterization of much of the panoply of problems the world faces. Perhaps rephrasing as “mathematics toughest problems” might be a better characterization, but my guess is that there are tougher mathematical problems in game theory and stochastic processes.
Of course, claiming that something is toughest, easiest, best or worst is always readily open to criticism. This is exacerbated when the problem definition is a substantial abstraction of real problems of interest. Solutions of abstractions can be very useful, but translations to reality can be immensely difficult and highly worthy of their own accolades and approbations.
