Computational foundations of the human world

Title: Computational Foundations of the Human World

Problem Statement
Human societies continuously transform scattered information into collective judgments and coordinated action through mechanisms such as markets, governments, and scientific communities. While theoretical computer science (TCS) offers formal tools to analyze resource requirements (time, memory, communication) for solving problems, the social sciences lack a domain focused on the intrinsic nature of computation within human social organization. Existing quantitative approaches in social science (e.g., social network science, econophysics, scaling laws) have identified statistical regularities but have failed to provide a unified framework connecting microscopic interactions to robust macroscopic behavior. The central problem addressed is the computational difficulty of collective decision-making: the time and communication required to reach solutions impose fundamental constraints on social organization, yet these constraints are rarely analyzed through the lens of computational complexity.

Methodology and Theoretical Framework
This paper proposes a perspective that applies frameworks from theoretical computer science to the study of human social systems. Rather than treating computation merely as a tool for simulating social phenomena (computational social science) or analyzing the deployment of digital algorithms in society, the authors argue that social systems themselves should be viewed as distributed computational systems.

The methodology involves:

1. Reframing Social Phenomena: Identifying core social "meta-problems" (e.g., finding, counting, coordination, prediction) and mapping them to formal problems in computer science.
2. Expanding Computational Paradigms: Moving beyond the traditional Turing Machine (TM) and worst-case complexity analysis, which are often ill-suited for the noisy, stochastic, and distributed nature of human collectives. The paper advocates for the use of:
   • Non-uniform computation: Specifically Boolean circuits and the concept of "advice," which model how social structures can vary with scale and utilize external knowledge (culture, norms) to solve problems more efficiently.
   • Distributed computing theory: Analyzing coordination under constraints of communication complexity, asynchrony, and fault tolerance (e.g., Byzantine generals problem).
   • Alternative complexity measures: Utilizing average-case complexity, approximation complexity, and parameterized complexity to better reflect the "good enough" solutions and bounded rationality found in real-world social systems.

Key Contributions
The paper outlines four core social phenomena that can be fruitfully framed as computational:

1. Distributed Consensus and Coordinated Action: The paper distinguishes between centralized computation (e.g., democratic elections, auctions) and distributed computation (e.g., market price discovery, emergence of norms). It highlights that while social optimality is often discussed in economics, the computational feasibility of reaching such optima is a critical, often overlooked constraint.
2. Hierarchical and Modular Structure: Human social systems are rarely purely centralized or fully distributed; they exhibit modularity (semi-independent components specializing in distinct domains) and hierarchy (layered interdependency). The authors suggest these structures function as mechanisms to manage the computational burden of aggregating dispersed knowledge, analogous to how Boolean circuits manage complexity through depth and size.
3. Scaling of Human Social Computation: As populations grow, coordination costs increase, potentially leading to combinatorial blowup. The paper argues that societies reorganize their institutional and communication structures (e.g., shifting from small-scale egalitarian groups to complex bureaucracies) to maintain computational tractability. This restructuring is viewed as a co-evolution of problem size and problem-solving capacity.
4. Externalized Memory Systems: Societies extend their computational capacity through external memory (writing, digital storage, AI). This allows for the accumulation and encoding of knowledge across generations, effectively providing "advice" strings that reduce the need to recompute solutions to previously solved problems.

Results and Analysis
The paper does not present new empirical data or experimental results but synthesizes existing theoretical insights to argue for a new research agenda. Key analytical points include:

• Intractability of Social Optima: Finding Nash equilibria or socially optimal allocations is often computationally intractable (NP-hard). If a solution cannot be found in reasonable time, it is implausible that a group will converge to it, suggesting that "social optima" in theory may be irrelevant in practice if computationally inaccessible.
• Efficiency of Decentralization: The paper references arguments (e.g., Hayek) that decentralized markets may achieve efficient allocations that are computationally infeasible for centralized mechanisms, particularly when dealing with combinatorial preferences where price discovery requires exponential communication.
• Robustness and Error Correction: Social systems, like distributed computing systems, must handle faults and adversarial behavior. Concepts such as Byzantine fault tolerance and self-stabilization offer frameworks for understanding how social institutions maintain resilience against misinformation or strategic manipulation.
• Approximation over Exactness: Real-world social systems often operate under severe time and resource constraints, making exact optimization impossible. The paper suggests that approximation complexity (finding "good enough" solutions) and average-case analysis are more relevant metrics for social phenomena than worst-case exact solutions.

Significance and Claims
The authors claim that this perspective offers a "computational lens" to examine social processes, potentially unifying fragmented theories in economics, sociology, and anthropology. The significance of this work lies in:

• Bridging Disciplines: It proposes a concrete intersection between computer science theory and social science, moving beyond the application of computational tools to the study of social data, toward understanding the computational nature of social systems themselves.
• Formalizing Social Constraints: It suggests that the evolution of social institutions (hierarchy, modularity, external memory) can be understood as adaptations to computational constraints (communication costs, time complexity, memory limits).
• Future Research Directions: The paper identifies specific avenues for future work, including developing complexity characterizations for price discovery in distributed systems, formulating complexity notions based on fixed constraints of time/memory/energy, and analyzing real-world coordination tasks through the lens of distributed computing theory.

The paper concludes modestly, stating it does not propose a single rigorous formalism but aims to inspire the adoption of a computational viewpoint to explain why social systems restructure with scale, why hierarchy emerges, and how external memory benefits information processing. It posits that many longstanding debates in social science could be placed on a more concrete, formal footing through this framework.