<p>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 <em>problems</em> that are $NP$-complete. These are problems we want (and in real life <em>need to</em>) 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$.</p>

CC BY-SA 2.5
2010-12-13T20:57:03.827Z
2010-12-13T20:57:03.827Z
Kristoffer Arnsfelt Hansen
<p>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.</p>

<p>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 <em>the really interesting</em> case which is $P$ vs $NP$, and an inequality is formally and conceptually as difficult as an inequality between $P$ vs $NP$.</p>

CC BY-SA 2.5
2010-12-14T08:09:17.713Z
$EXP \ne NEXP$ implies $P \ne NP$, So I don't understand your claim that the evidence for $EXP \ne NEXP$ is much weaker. Notice that $EXP = NEXP$ implies tht $NEXP = co-NEXP$ which is very surprising result.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-14T08:19:55.053Z
@turkistany: Thanks for the comment (though I don't find it a good reason for down voting). I thought that it was clear, $EXP \neq NEXP$ implies $P \neq NP$ but not vice versa, therefore an evidence for $P \neq NP$ does not seem to be an evidence for $EXP \neq NEXP$. In any case $EXP=NEXP$ would be much less surprising than $P=NP$, don't you agree?
Kaveh
CC BY-SA 2.5
2010-12-14T08:33:22.670Z
@Kaveh, Let me disagree. I find $EXP = NEXP$ to be very surprising result because it implies $NEXP =co-NEXP$ as I stated above.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-14T19:30:58.117Z
@turkistany: It is clear to me that $P = NP$ would be way more surprising than $EXP=NEXP$, but sure, you can disagree with it. :)
Kaveh
CC BY-SA 2.5
2010-12-14T23:46:36.480Z
How do you define non-deterministic primitive recursive?
slimton
CC BY-SA 2.5
2010-12-15T04:25:25.800Z
@slimton: one way is a certificate definition where the length of the certificate is bounded by a primitive recursive function and the verifier is primitive recursive.
Kaveh
CC BY-SA 2.5
2010-12-13T21:46:31.963Z
2010-12-13T21:46:31.963Z
Kaveh
<p>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 <i>unary</i> languages. That is, all inputs are of the form $1^k$. </p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 2.5
2010-12-13T05:46:33.177Z
This seems to clarify the situation. So one could say that $P \neq NP$ implies there is no general algorithm that allows a polynomial simulation of a NTM by a DTM, while similar statements for larger classes imply the same statement but for more specific languages?
chazisop
CC BY-SA 2.5
2010-12-13T18:39:38.233Z
Yes indeed it does (for more restricted families of languages)
Boaz Barak
CC BY-SA 2.5
2010-12-13T03:11:19.830Z
2010-12-13T18:38:53.930Z
2010-12-13T18:38:53.930Z
Boaz Barak
<p>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.</p>

<p>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? </p>

<p>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$. </p>

<p>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. </p>

<p>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?</p>

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

CC BY-SA 2.5
2010-12-12T03:02:06.223Z
The second question is my main question. However, the first question is related too : Can we separate nondeterminism from determinism once and for all or are we doomed to trying to solve infinite P != NP questions, every time with larger classes? I am also arguing that although P and NP are relevant to our "human" problems, perhaps larger classes that are infeasible are needed to understand the power of nondeterminism
chazisop
<cc.complexity-theory><big-picture>
Why don't we use larger classes to study determinism vs non-determinism?
chazisop
# Why don't we use larger classes to study determinism vs non-determinism?

(Asked by: username_0 on 2010-12-11)

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?

**Tags:** cc.complexity-theory, big-picture

> **Comments:**
> **username_0**: The second question is my main question. However, the first question is related too : Can we separate nondeterminism from determinism once and for all or are we doomed to trying to solve infinite P != NP questions, every time with larger classes? I am also arguing that although P and NP are relevant to our "human" problems, perhaps larger classes that are infeasible are needed to understand the power of nondeterminism  

---

## 3 answers

### Answer by username_5 on 2010-12-13. Score: 20 | Accepted answer

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.

> **Comments:**
> **username_0**: This seems to clarify the situation. So one could say that $P \neq NP$ implies there is no general algorithm that allows a polynomial simulation of a NTM by a DTM, while similar statements for larger classes imply the same statement but for more specific languages?  
> **username_5**: Yes indeed it does (for more restricted families of languages)  

---

### Answer by username_1 on 2010-12-13. Score: 4

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 by username_2 on 2010-12-13. Score: 1

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$.

> **Comments:**
> **username_3**: $EXP \ne NEXP$ implies $P \ne NP$, So I don't understand your claim that the evidence for $EXP \ne NEXP$ is much weaker. Notice that $EXP = NEXP$ implies tht $NEXP = co-NEXP$ which is very surprising result.  
> **username_2**: @turkistany: Thanks for the comment (though I don't find it a good reason for down voting). I thought that it was clear, $EXP \neq NEXP$ implies $P \neq NP$ but not vice versa, therefore an evidence for $P \neq NP$ does not seem to be an evidence for $EXP \neq NEXP$. In any case $EXP=NEXP$ would be much less surprising than $P=NP$, don't you agree?  
> **username_3**: @username_2, Let me disagree. I find $EXP = NEXP$ to be very surprising result because it implies $NEXP =co-NEXP$ as I stated above.  
> **username_2**: @turkistany: It is clear to me that $P = NP$ would be way more surprising than $EXP=NEXP$, but sure, you can disagree with it. :)  
> **username_4**: How do you define non-deterministic primitive recursive?  
> **username_2**: @username_4: one way is a certificate definition where the length of the certificate is bounded by a primitive recursive function and the verifier is primitive recursive.  

---

