Algorithmen und Datenstrukturen Notizen Siehe auch: Nichts
Confronting a tumultuous, footloose, and “headless” rural society which was hard to control and which had few political assets, the Bolsheviks, like the scientific foresters, set about redesigning their environment with a few simple goals in mind. They created, in place of what they had inherited, a new landscape of large, hierarchical, state-managed farms whose cropping patterns and procurement quotas were centrally mandated and whose population was, by law, immobile. The system thus devised served for nearly sixty years as a mechanism for procurement and control at a massive cost in stagnation, waste, demoralization, and ecological failure.
One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory—the field that studies the resources (such as time, space, and randomness) needed to solve computational problems—leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume’s problem of induction, Goodman’s grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis.