10
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ I think that the same barriers that make proving P != NP difficult make separating EXP and NEXP difficult, too. E.g., I believe there's a non-relativization result for EXP and NEXP. I'm sure people have considered separation questions regarding larger complexity classes, but I would imagine this hasn't led to any more progress than trying to separate the smaller ones. $\endgroup$ – Philip White Dec 11 '10 at 21:05
  • $\begingroup$ I just re-read your last few paragraphs; I may have misread your question. Are you asking, "why can't we separate P != NP by examining such related conjectures as EXP != NEXP?" or are you asking, "why was P ?= NP chosen instead of a different question to explore the differences between determinism and nondeterminism?" I'm assuming you are aware that P = NP --> EXPTIME = NEXPTIME. The answer to the second question, I think, is related to the fact that P is feasible, whereas EXPTIME is not. Also, NP is relevant to cryptography. I think P ?= NP just seems more "relevant." $\endgroup$ – Philip White Dec 12 '10 at 2:23
  • $\begingroup$ 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 $\endgroup$ – chazisop Dec 12 '10 at 3:02
21
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – chazisop Dec 13 '10 at 5:46
  • 2
    $\begingroup$ Yes indeed it does (for more restricted families of languages) $\endgroup$ – Boaz Barak Dec 13 '10 at 18:39
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ $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. $\endgroup$ – Mohammad Al-Turkistany Dec 14 '10 at 8:09
  • 1
    $\begingroup$ @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? $\endgroup$ – Kaveh Dec 14 '10 at 8:19
  • 1
    $\begingroup$ @Kaveh, Let me disagree. I find $EXP = NEXP$ to be very surprising result because it implies $NEXP =co-NEXP$ as I stated above. $\endgroup$ – Mohammad Al-Turkistany Dec 14 '10 at 8:33
  • 2
    $\begingroup$ @turkistany: It is clear to me that $P = NP$ would be way more surprising than $EXP=NEXP$, but sure, you can disagree with it. :) $\endgroup$ – Kaveh Dec 14 '10 at 19:30
  • $\begingroup$ How do you define non-deterministic primitive recursive? $\endgroup$ – slimton Dec 14 '10 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.