Posts Tagged ‘complexity theory’
“Life is a Zen koan, that is, an unsolvable riddle. But the contemplation of that riddle – even though it cannot be solved – is, in itself, transformative.”*…
How hard is it to prove that problems are hard to solve? Meta-complexity theorists have been asking questions like this for decades. And as Ben Brubaker explains, a string of recent results has started to deliver answers…
… Even seasoned researchers find understanding in short supply when they confront the central open question in theoretical computer science, known as the P versus NP problem. In essence, that question asks whether many computational problems long considered extremely difficult can actually be solved easily (via a secret shortcut we haven’t discovered yet), or whether, as most researchers suspect, they truly are hard. At stake is nothing less than the nature of what’s knowable.
Despite decades of effort by researchers in the field of computational complexity theory — the study of such questions about the intrinsic difficulty of different problems — a resolution to the P versus NP question has remained elusive. And it’s not even clear where a would-be proof should start.
“There’s no road map,” said Michael Sipser, a veteran complexity theorist at the Massachusetts Institute of Technology who spent years grappling with the problem in the 1980s. “It’s like you’re going into the wilderness.”
It seems that proving that computational problems are hard to solve is itself a hard task. But why is it so hard? And just how hard is it? Carmosino and other researchers in the subfield of meta-complexity reformulate questions like this as computational problems, propelling the field forward by turning the lens of complexity theory back on itself.
“You might think, ‘OK, that’s kind of cool. Maybe the complexity theorists have gone crazy,’” said Rahul Ilango, a graduate student at MIT who has produced some of the most exciting recent results in the field.
By studying these inward-looking questions, researchers have learned that the hardness of proving computational hardness is intimately tied to fundamental questions that may at first seem unrelated. How hard is it to spot hidden patterns in apparently random data? And if truly hard problems do exist, how often are they hard?
“It’s become clear that meta-complexity is close to the heart of things,” said Scott Aaronson, a complexity theorist at the University of Texas, Austin.
This is the story of the long and winding trail that led researchers from the P versus NP problem to meta-complexity. It hasn’t been an easy journey — the path is littered with false turns and roadblocks, and it loops back on itself again and again. Yet for meta-complexity researchers, that journey into an uncharted landscape is its own reward. Start asking seemingly simple questions, said Valentine Kabanets, a complexity theorist at Simon Fraser University in Canada, and “you have no idea where you’re going to go.”…
Complexity theorists are confronting their most puzzling problem yet– complexity theory itself: “Complexity Theory’s 50-Year Journey to the Limits of Knowledge,” from @benbenbrubaker in @QuantaMagazine.
* Tom Robbins
###
As we limn limits, we might send thoroughly cooked birthday greetings to Denis Papin; he was born on this date in 1647. A mathematician and physicist who worked with Christiaan Huygens and Gottfried Leibniz, Papin is better remembered as the inventor of the steam digester, the forerunner of the pressure cooker and of the steam engine.
“Our civilization is flinging itself to pieces. Stand back from the centrifuge.”*…
From ancient empires to the industrialized nation-states of our globally-interconnected world, complexity theory offers a fresh perspective on the past and possible futures of human societies. Dries Daems explains…
… Civilizations rise and fall, sometimes at the stroke of a sword. Myriad explanations have been posited as to why this happens. Often, hypotheses of collapse say more about the preoccupations of contemporary society than they do about the past. It is no coincidence that Edward Gibbon’s The History of the Decline and Fall of the Roman Empire (01776), written during the anticlerical Age of Reason, blamed Christianity for Rome’s downfall, just as it is no coincidence that recent popular accounts of civilizational collapse such as Jared Diamond’s Collapse: How Societies Choose to Fail or Succeed (02005) point toward environmental damage and climate change as the main culprits.
I’ve been fascinated by the oscillations of human societies ever since the early days of my research for my Ph.D. in archaeology. Over the last 12,000 years, we’ve gone from small hunter-gatherer groups to highly urbanized communities and industrialized nation-states in a globally interconnected world. As societies grow, they expand in territory, produce economic growth, technological innovation, and social stratification. How does this happen, and why? And is collapse inevitable? The answers provided by archeology were unsatisfying. So I looked elsewhere.
Ultimately, I settled on a radically different framework to explore these questions: the field of complexity theory. Emerging from profound cross-disciplinary frustrations with reductionism, complexity theory aims to understand the properties and behavior of complex systems (including the human brain, ecosystems, cities and societies) through the exploration of their generative patterns, dynamics, and interactions.
In what follows, I’ll share some thoughts about what social complexity is, how it develops, and why it provides a more comprehensive account of societal change than the traditional evolutionary approaches that permeate archeology. By recasting the rise and fall of civilizations in terms of social complexity, we can better understand not only the past of human societies, but their possible futures as well…
Fascinating– and arresting: “Reimagining the Rise and Fall of Civilizations,” from @DriesDaems at @longnow.
See also Nick Brysiewicz‘s “Creative Technology at the Timescale of Civilization” @nicholaspaul26 for @_baukunst.
* Ray Bradbury, Fahrenheit 451
###
As we contemplate change, we might recall that it was on this date in 1644 that the Qing dynasty‘s Manchu forces, led by the Shunzhi Emperor, took Beijing– sealing the collapse of the Ming dynasty, which had ruled since 1368.
“Several thousand years from now, nothing about you as an individual will matter. But what you did will have huge consequences.”*…
In 2013, a philosopher and ecologist named Timothy Morton proposed that humanity had entered a new phase. What had changed was our relationship to the nonhuman. For the first time, Morton wrote, we had become aware that “nonhuman beings” were “responsible for the next moment of human history and thinking.” The nonhuman beings Morton had in mind weren’t computers or space aliens but a particular group of objects that were “massively distributed in time and space.” Morton called them “hyperobjects”: all the nuclear material on earth, for example, or all the plastic in the sea. “Everyone must reckon with the power of rising waves and ultraviolet light,” Morton wrote, in “Hyperobjects: Philosophy and Ecology After the End of the World.” Those rising waves were being created by a hyperobject: all the carbon in the atmosphere.
Hyperobjects are real, they exist in our world, but they are also beyond us. We know a piece of Styrofoam when we see it—it’s white, spongy, light as air—and yet fourteen million tons of Styrofoam are produced every year; chunks of it break down into particles that enter other objects, including animals. Although Styrofoam is everywhere, one can never point to all the Styrofoam in the world and say, “There it is.” Ultimately, Morton writes, whatever bit of Styrofoam you may be interacting with at any particular moment is only a “local manifestation” of a larger whole that exists in other places and will exist on this planet millennia after you are dead. Relative to human beings, therefore, Styrofoam is “hyper” in terms of both space and time. It’s not implausible to say that our planet is a place for Styrofoam more than it is a place for people.
When “Hyperobjects” was published, philosophers largely ignored it. But Morton, who uses the pronouns “they” and “them,” quickly found a following among artists, science-fiction writers, pop stars, and high-school students. The international curator and art-world impresario Hans Ulrich Obrist began citing Morton’s ideas; Morton collaborated on a talk with Laurie Anderson and helped inspire “Reality Machines,” an installation by the Icelandic-Danish artist Olafur Eliasson. Kim Stanley Robinson and Jeff VanderMeer—prominent sci-fi writers who also deal with ecological themes—have engaged with Morton’s work; Björk blurbed Morton’s book “Being Ecological,” writing, “I have been reading Tim Morton’s books for a while and I like them a lot.”
…
The problem with hyperobjects is that you cannot experience one, not completely. You also can’t not experience one. They bump into you, or you bump into them; they bug you, but they are also so massive and complex that you can never fully comprehend what’s bugging you. This oscillation between experiencing and not experiencing cannot be resolved. It’s just the way hyperobjects are.
Take oil: nature at its most elemental; black ooze from the depths of the earth. And yet oil is also the stuff of cars, plastic, the Industrial Revolution; it collapses any distinction between nature and not-nature. Driving to the port, we were surrounded by oil and its byproducts—the ooze itself, and the infrastructure that transports it, refines it, holds it, and consumes it—and yet, Morton said, we could never really see the hyperobject of capital-“O” Oil: it shapes our lives but is too big to see.
…
Since around 2010, Morton has become associated with a philosophical movement known as object-oriented ontology, or O.O.O. The point of O.O.O. is that there is a vast cosmos out there in which weird and interesting shit is happening to all sorts of objects, all the time. In a 1999 lecture, “Object-Oriented Philosophy,” Graham Harman, the movement’s central figure, explained the core idea:
The arena of the world is packed with diverse objects, their forces unleashed and mostly unloved. Red billiard ball smacks green billiard ball. Snowflakes glitter in the light that cruelly annihilates them, while damaged submarines rust along the ocean floor. As flour emerges from mills and blocks of limestone are compressed by earthquakes, gigantic mushrooms spread in the Michigan forest. While human philosophers bludgeon each other over the very possibility of “access” to the world, sharks bludgeon tuna fish and icebergs smash into coastlines…
We are not, as many of the most influential twentieth-century philosophers would have it, trapped within language or mind or culture or anything else. Reality is real, and right there to experience—but it also escapes complete knowability. One must confront reality with the full realization that you’ll always be missing something in the confrontation. Objects are always revealing something, and always concealing something, simply because they are Other. The ethics implied by such a strangely strange world hold that every single object everywhere is real in its own way. This realness cannot be avoided or backed away from. There is no “outside”—just the entire universe of entities constantly interacting, and you are one of them.
… “[Covid-19 is] the ultimate hyperobject,” Morton said. “The hyperobject of our age. It’s literally inside us.” We talked for a bit about fear of the virus—Morton has asthma, and suffers from sleep apnea. “I feel bad for subtitling the hyperobjects book ‘Philosophy and Ecology After the End of the World,’ ” Morton said. “That idea scares people. I don’t mean ‘end of the world’ the way they think I mean it. But why do that to people? Why scare them?”
What Morton means by “the end of the world” is that a world view is passing away. The passing of this world view means that there is no “world” anymore. There’s just an infinite expanse of objects, which have as much power to determine us as we have to determine them. Part of the work of confronting strange strangeness is therefore grappling with fear, sadness, powerlessness, grief, despair. “Somewhere, a bird is singing and clouds pass overhead,” Morton writes, in “Being Ecological,” from 2018. “You stop reading this book and look around you. You don’t have to be ecological. Because you are ecological.” It’s a winsome and terrifying idea. Learning to see oneself as an object among objects is destabilizing—like learning “to navigate through a bad dream.” In many ways, Morton’s project is not philosophical but therapeutic. They have been trying to prepare themselves for the seismic shifts that are coming as the world we thought we knew transforms.
…
For the philosopher of “hyperobjects”—vast, unknowable things that are bigger than ourselves—the coronavirus is further proof that we live in a dark ecology: “Timothy Morton’s Hyper-Pandemic.”
* “Several thousand years from now, nothing about you as an individual will matter. But what you did will have huge consequences. This is the paradox of the ecological age. And it is why action to change global warming must be massive and collective.” – Timothy Morton, Being Ecological
###
As we find our place, we might send classical birthday greetings to James Clerk Maxwell; he was born on this date in 1831. A mathematician and and physicist, he calculated (circa 1862) that the speed of propagation of an electromagnetic field is approximately that of the speed of light– kicking off his work in uniting electricity, magnetism, and light… that’s to say, formulating the classical theory of electromagnetic radiation, which is considered the “second great unification in physics” (after the first, realized by Isaac Newton). Though he was the apotheosis of classical (Newtonian) physics, Maxwell laid the foundation for modern physics, starting the search for radio waves and paving the way for such fields as special relativity and quantum mechanics. In the Millennium Poll – a survey of the 100 most prominent physicists at the turn of the 21st century – Maxwell was voted the third greatest physicist of all time, behind only Newton and Einstein.
“Life is really simple, but we insist on making it complicated”*…
One of the dominant themes of the last few years is that nothing makes sense. Donald Trump is president, QAnon has mainstreamed fringe conspiracy theories, and hundreds of thousands are dead from a pandemic and climate change while many Americans do not believe that the pandemic or climate change are deadly. It’s incomprehensible.
I am here to tell you the the reason that so much of the world seems incomprehensible is that it is incomprehensible. From social media to the global economy to supply chains, our lives rest precariously on systems that have become so complex, and we have yielded so much of it to technologies and autonomous actors that no one totally comprehends it all.
In other words: No one’s driving. And if we hope to retake the wheel, we’re going to have to understand, intimately, all of the ways we’ve lost control…
The internet might be the system that we interact with in the most direct and intimate ways, but most of us have little comprehension of what lies behind our finger-smudged touchscreens, truly understood by few. Made up of data centers, internet exchanges, huge corporations, tiny startups, investors, social media platforms, datasets, adtech companies, and billions of users and their connected devices, it’s a vast network dedicated to mining, creating, and moving data on scales we can’t comprehend. YouTube users upload more than 500 hours of video every minute — which works out as 82.2 yearsof video uploaded to YouTube every day. As of June 30, 2020, there are over 2.7 billion monthly active Facebook users, with 1.79 billion people on average logging on daily. Each day, 500 million tweets are sent— or 6,000 tweets every second, with a day’s worth of tweets filling a 10-million-page book. Every day, 65 billion messages are sent on WhatsApp. By 2025, it’s estimated that 463 million terabytes of data will be created each day — the equivalent of 212,765,957 DVDs…
What we’ve ended up with is a civilization built on the constant flow of physical goods, capital, and data, and the networks we’ve built to manage those flows in the most efficient ways have become so vast and complex that they’re now beyond the scale of any single (and, arguably, any group or team of) human understanding them. It’s tempting to think of these networks as huge organisms, with tentacles spanning the globe that touch everything and interlink with one another, but I’m not sure the metaphor is apt. An organism suggests some form of centralized intelligence, a nervous system with a brain at its center, processing data through feedback loops and making decisions. But the reality with these networks is much closer to the concept of distributed intelligence or distributed knowledge, where many different agents with limited information beyond their immediate environment interact in ways that lead to decision-making, often without them even knowing that’s what they’re doing…
Ceding control to vast unaccountable networks not only risks those networks going off the rails, it also threatens democracy itself. If we are struggling to understand or influence anything more than very small parts of them, this is also increasingly true for politicians and world leaders. Like the captain of the container ship, politicians and voters have less and less control over how any of these networks run. Instead they find themselves merely managing very small parts of them — they certainly don’t seem to be able to make drastic changes to those networks (which are mainly owned by private corporate industries anyway) even though they have a very direct impact on their nations’ economies, policies, and populations. To paraphrase the filmmaker Adam Curtis, instead of electing visionary leaders, we are in fact just voting for middle managers in a complex, global system that nobody fully controls.
The result of this feels increasingly like a democratic vacuum. We live in an era where voters have record levels of distrust for politicians, partly because they can feel this disconnect — they see from everyday reality that, despite their claims, politicians can’t effect change. Not really. They might not understand why, exactly, but there’s this increasing sense that leaders have lost the ability to make fundamental changes to our economic and social realities. The result is a large body of mainstream voters that wants to burn down the status quo. They want change, but don’t see politicians being able to deliver it. It feels like they’re trapped in a car accelerating at full throttle, but no one is driving.
They may not be able to do much about it, but there are mainstream politicians and elected leaders who see this vacuum for what it is — and see how it provides them with a political opportunity. Figures like Donald Trump and Boris Johnson certainly don’t believe in patching up the failures of this system — if anything, they believe in accelerating the process, deregulating, handing more power to the networks. No, for them this is a political vacuum that can be filled with blame. With finger-pointing and scapegoating. It is an opportunity to make themselves look powerful by pandering to fears, by evoking nationalism, racism, and fascism.
Donald Trump has still not conceded the 2020 election despite Joe Biden’s clear victory, and is leaning in part on the fact that the United States has a complex and sometimes opaque voting system that most of the public doesn’t understand to spread conspiracy theories about glitchy or malfeasant voting machines switching or deleting millions of votes. It’s perhaps no coincidence that some of the highest-profile figures on the right — like ex-Trump-adviser Steve Bannon or Brexit Party leader Nigel Farage — have backgrounds in the financial industry. These are political players who have seen how complicated things have become and can sense the gap in public comprehension but want to fill it with chaos and conspiracies rather than explanations…
As Tim Maughan (@TimMaughan) explains, vast systems, from automated supply chains to high-frequency trading, now undergird our daily lives — and we’re losing control of all of them: “The Modern World Has Finally Become Too Complex for Any of Us to Understand” (the first of a series of monthly columns that will “locate ways that we can try to increase our knowledge of the seemingly unknowable, as well as find strategies to counter the powerlessness and anxiety the system produces”).
* Confucius
###
As we contemplate complexity, we might send emergent birthday greetings to Per Bak; he was born on this date in 1948. A theoretical physicist, he is credited with developing the concept (and coining the name) of “self-organized criticality,” an explanation of how very complex phenomena (like consciousness) emerge from the interaction of simple components.
“Fools ignore complexity. Pragmatists suffer it… Geniuses remove it.”*…
World War II bomber planes returned from their missions riddled with bullet holes. The first response was, not surprisingly, to add armor to those areas most heavily damaged. However, the statistician Abraham Wald made what seemed like the counterintuitive recommendation to add armor to those parts with no damage. Wald had uniquely understood that the planes that had been shot where no bullet holes were seen were the planes that never made it back. That’s, of course, where the real problem was. Armor was added to the seemingly undamaged places, and losses decreased dramatically.
The visible bullet holes of this pandemic are the virus and its transmission. Understandably, a near-universal response to the COVID-19 pandemic has been to double down on those disciplines where we already possess deep and powerful knowledge: immunology and epidemiology. Massive resources have been directed at combating the virus by providing fast grants for disciplinary work on vaccines. Federal agencies have called for even more rapid response from the scientific community. This is a natural reaction to the immediate short-term crisis.
The damage we are not attending to is the deeper nature of the crisis—the collapse of multiple coupled complex systems.
Societies the world over are experiencing what might be called the first complexity crisis in history. We should not have been surprised that a random mutation of a virus in a far-off city in China could lead in just a few short months to the crash of financial markets worldwide, the end of football in Spain, a shortage of flour in the United Kingdom, the bankruptcy of Hertz and Niemann-Marcus in the United States, the collapse of travel, and to so much more.
As scientists who study complex systems, we conceive of a complexity crisis as a twofold event. First, it is the failure of multiple coupled systems—our physical bodies, cities, societies, economies, and ecosystems. Second, it involves solutions, such as social distancing, that involve unavoidable tradeoffs, some of which amplify the primary failures. In other words, the way we respond to failing systems can accelerate their decline.
We and our colleagues in the Santa Fe Institute Transmission Project believe there are some non-obvious insights and solutions to this crisis that can be gleaned from studying complex systems and their universal properties…
The more complicated and efficient a system gets, the more likely it is to collapse altogether. Scientists who study complex systems offer solutions to the pandemic: “The Damage We’re Not Attending To.”
See also: “Complex Systems Theory Explains Why Covid Crushed the World.”
###
As we think systemically, we might recall that it was on this date in 1835 that the New York Sun began a series of six articles detailing the discovery of civilized life on the moon. Now known as “The Great Moon Hoax,” the articles attributed the “discovery” to Sir John Herschel, the greatest living astronmer of the day. Herschel was initially amused, wryly noting that his own real observations could never be as exciting. But ultimately he tired of having to answer questioners who believed the story. The series was not discovered to be a hoax for several weeks after its publication and, even then, the newspaper did not issue a retraction.
The “ruby amphitheater” on the Moon, per the New York Sun (source)
You must be logged in to post a comment.