> I am still puzzled why computer scientist consider computational complexity something metaphysical. In what sense do you mean "metaphysical"? Personally, I

> I am still puzzled why computer scientist consider computational complexity something metaphysical. In what sense do you mean "metaphysical"? Personally, I would say computational complexity is both "physical", in the sense that it gives fundamental limits to what can/cannot be done in the physical world using some amount of resources (say, anything obeying Blum's axioms). I would say it's also "metaphysical", in the sense that those limits are derived purely mathematically, and are "imposed on" the physical world; rather than, for example, by observing the physical world and imposing consistency with those observations on some mathematical model. I think of these computational "laws of nature" in a similar way to the "law of nature" that e^(i*pi) + 1 = 0. In other words, we can imagine (AKA develop a consistent mathematical model of) a world operating by Newtonian physics; we can do the same for a world operating by special or general relativity; and for the standard model; we can do it for worlds with N dimensions; with Euclidean, hyperbolic or spherical geometry; and so on. All of these "make sense", in a self-consistent way, and it's up to physicists to figure out which of those models best describes our physical world. On the other hand, there don't seem to be self-consistent models of universal systems which can solve their own halting problem, or models which don't posess the hierarchical complexity classes we've found (although, of course, the machine models may differ, we may introduce hierarchies of halting oracles, etc.). In that sense, these seem to be "laws of nature" which are intrinsic to our models, by virtue of their mathematical definition, rather than being imposed from the outside in order to agree with observations.