Why Philosophers Should Care About Computational Complexity
Open the pdf of the full paper [55 pg]
I'll spoil the end, by posting the excerpt below
12.2Future Directions
Even if the various criticisms of complexity theory don't negate its relevance, it would be great to address those criticisms head-on-and more generally, to get a clearer understanding of the relationship between complexity theory and the real-world phenomena that it tries to explain.
Toward that end, I think the following questions would all benefit from careful philosophical analysis:
• What is the empirical status of asymptotic claims? What sense can we give to an asymp-totic statement "making predictions," or being supported or ruled out by a finite number of observations?
• How can we explain the empirical facts on which complexity theory relies: for example, that we rarely see n10000 or 1.0000001n algorithms, or that the computational problems humans care about tend to organize themselves into a relatively-small number of equivalence classes?
• Short of proof, how do people form intuitions about the truth or falsehood of mathematical conjectures? What are those intuitions, in cases such as P = NP?
• Do the conceptual conclusions that people sometimes want to draw from conjectures such asP = NP or BPP = BQP-for example, about the nature of mathematical creativity or the interpretation of quantum mechanics-actually depend on those conjectures being true? Arethere easier-to-prove statements that would arguably support the same conclusions?
• If P = NP, then how have humans managed to make such enormous mathematical progress,even in the face of the general intractability of theorem-proving? Is there a "selection effect,"by which mathematicians favor problems with special structure that makes them easier tosolve than arbitrary problems? If so, then what does this structure consist of?
In short, I see plenty of scope for the converse essay to this one: "Why Computational Com-plexity Theorists Should Care About Philosophy."
Why Philosophers Should Care About Computational Complexity
Re: Why Philosophers Should Care About Computational Complexity
