Why don't we use larger classes to study determinism vs non-determinism?

Question

In a previous question about time hierarchy, I've learned that equalities between two classes can be propagated to more complex classes and inequalities can be propagated to less complex classes, with arguments using padding.

Therefore, a question comes to mind. Why do we study a question about different types of computation (or resources) in the smallest (closed) class possible?

Most researchers believe that $P \neq NP$. This distinction of classes wouldn't be between classes that use the same type of resource. Therefore, one might think of this inequality as a universal rule: Nondeterminism is a more powerful resource. Therefore, although an inequality, it could be propagated upwards via exploiting the different nature of the two resources.So, one could expect that $EXP \neq NEXP$ too. If one proved this relation or any other similar inequality, it would translate to $P \neq NP$.

My argument could maybe become clear in terms of physics. Newton would have a hard time understanding universal gravity by examining rocks (apples?) instead of celestial bodies. The larger object offers more details in its study, giving a more precise model of its behavior and allowing to ignore small-scale phenomena that might be irrelevant.

Of course, there is the risk that in larger objects there is a different behavior, in our case that the extra power of non-determinism wouldn't be enough in larger classes. What if after all, $P \neq NP$ is proven? Should we start working on $EXP \neq NEXP$ the next day?

Do you consider this approach problematic? Do you know of research that uses larger classes than polynomial to distinguish the two types of computation?

Answer 1

The issue may be a bit cleaner with $E=Dtime(2^{O(n)})$ and $NE=Ntime(2^{O(n)})$. The easiest way to think about these classes is that they are the same as $P$ and $NP$ but restricted to unary languages. That is, all inputs are of the form $1^k$.

That is, the language $L$ is in $E$ if and only if the language $U_L = \{ 1^x : x\in L \}$ is in $P$ (identifying strings with numbers using binary representation), and similarly $NE$ is isomorphic to unary $NP$.

So, trying to separate $NE$ from $E$ is just like trying not just to separate $P$ from $NP$, but actually do it using a unary language. No reason it should make your life even conceptually easier.

Answer 2

Why we choose to care about $P$ vs. $NP$? Actually nondeterminism as an object of study is only of secondary concern. We really care about $NP$ because of the thousands of important problems that are $NP$-complete. These are problems we want (and in real life need to) solve. We care about whether these problems can be solved efficiently, and $P$ is our theoretical model for efficient computation. Hence we are lead to the question of $P$ vs. $NP$.

Answer 3

Note that there are known separations for some unbounded complexity classes, e.g. $decidable \neq computability \ enumerable$, and also equalities like $NPSpace = PSpace$ and $primitive \ recursive = nondeterministic \ primitive \ recursive$. (It is instructive to think about why the trivial padding using them is not helpful for settling P vs NP.) We should be more careful about what we mean by a question like $P$ vs $NP$ and $EXP$ vs $NEXP$. If $P$ vs $NP$ is a padded version of it (e.g. $EXP$ vs $NEXP$ and $E$ vs $NE$) then Boaz's answer will also apply to it.

The evidence for $EXP \neq NEXP$ is much weaker than $P \neq NP$ and has less dramatic consequences, and there are people who find $EXP = NEXP$ plausible so the situation is more complicated there and we have a much weaker intuition about the expected answer. An equality will not help in practice and it is not known to have a effect on the really interesting case which is $P$ vs $NP$, and an inequality is formally and conceptually as difficult as an inequality between $P$ vs $NP$.