kevinwang
Joined 12 years ago
Joined 12 years ago
I certainly think you could say both of those are reasoning in latent space. But of course people can have different definitions of what they consider reasoning. Maybe this is because I think it's hard to pin down what "reasoning" is so I instead alias it to "computation" which both of those examples do.
Isn't this an ironic example to use, since one of the only lower bounds we have actually found is nlogn for comparison-based sorting?
And anyways, this point seems too strong: the fact that TCS people believe NP != P is another example that we believe a lower bound exists, no? (And relatedly, the large portion of TCS that is dedicated to trying to figure out how to lower-bound anything, while admittedly not so successful yet, shows that researchers believe lower bounds exist. I mean, any complexity class non-equality hypothesis is an example of this, no?)
scientist.wang