<p>As far as I know, we don't know of such languages, or if we do, there is significant controversy about the "naturalness" of them. I know this isn't really a satisfying answer, but I can say:</p>

<p>(a) If you prove an $\Omega(n^k)$ time lower bound for k-ISOLATED SAT for every $k$, then you have actually proved $P \neq NP$. </p>

<p>(b) One way you might hope to show that k-ISOLATED SAT is one of these natural problems in $NTIME[n^{k+1}] - NTIME[n^k]$ is to show that k-ISOLATED SAT problem is hard (in the usual, formal sense of having efficient reductions) for $NTIME[n^k]$. In fact this is the only way we know how to prove such results. But k-ISOLATED SAT is probably not hard in this sense, there are some very unlikely consequences.</p>

<p>The main reason is that k-ISOLATED SAT instances are solvable in $\Sigma_2 TIME[n]$, independently of $k$. You can existentially guess the isolated assignment, then universally verify (for all $O(\log (\sum_{i=1}^k {n \choose i}))$ ways to flip up to $k$ bits in the assignment) that none of the other "local" assignments work. </p>

<p>Here is the proof of part (a). Let ISOLATED SAT be the version of the problem with $k$ given as part of the input (in unary, say). Suppose we prove that ISOLATED SAT requires $\Omega(n^k)$ time for all $k$. If $P=NP$, then $\Sigma_2 TIME[n]$ is in $TIME[n^c]$ for some fixed $c$ (the proof uses an efficient version of Cook's theorem: if there is a SAT algorithm running in time $n^d$, then any $c > d^2$ suffices). But we proved that there is a language in $\Sigma_2 TIME[n]$ that is <em>not</em> in $TIME[n^k]$ for every $k$. This is a contradiction, so $P \neq NP$.</p>

<p>Here is the proof of part (b). If every $L \in NTIME[n^k]$ could be efficiently reduced to a k-ISOLATED SAT formula (e.g., all $n$ bit instances of $L$ get reduced to $k$-ISOLATED SAT formulas of at most $f(k) n^{c}$ size) then $NP=\bigcup_{k} NTIME[n^k] \subseteq \Sigma_2 TIME[n^{c+1}]$. This would immediately imply $coNP \neq NP$, but moreover it just looks very unlikely that all of $NP$ can be simulated so efficiently within the polynomial hierarchy. </p>

CC BY-SA 2.5
2010-09-03T07:40:54.073Z
Thank you for the neat argument showing k-ISOLATED SAT is not going to do the job.
András Salamon
CC BY-SA 2.5
2010-09-01T16:36:00.803Z
2010-09-01T16:36:00.803Z
Ryan Williams
<p>The original Nondeterministic Time Hierarchy Theorem is due to <a href="http://dx.doi.org/10.1016/S0022-0000%2873%2980028-5">Cook</a> (the link is to S. Cook, <em>A hierarchy for nondeterministic time complexity</em>, JCSS <strong>7</strong> 343–353, 1973).  The theorem states that for any real numbers $r_1$ and $r_2$, if $1 \le r_1 \lt r_2$ then <a href="http://en.wikipedia.org/wiki/NTIME">NTIME</a>($n^{r_1}$) is strictly contained in NTIME($n^{r_2}$).</p>

<p>One key part of the proof uses (an unspecified) diagonalization to construct a separating language from the elements of the smaller class.  Not only is this a nonconstructive argument, but languages obtained by diagonalization usually provide no insight other than the separation itself.</p>

<p>If we want to understand the structure of the NTIME hierarchy, the following question probably needs to be answered:</p>

<blockquote>
  <p>Is there a natural language in NTIME($n^{k+1}$) but not in NTIME($n^k$)?</p>
</blockquote>

<p>One candidate might be <a href="http://constraints.wordpress.com/2010/04/15/k-isolated-sat/">k-ISOLATED SAT</a>, which requires finding a solution to a CNF formula with no other solutions within Hamming distance k.  However, proving the lower bound <strike>seems</strike> <em>is</em> tricky, as usual.  It is obvious that checking a Hamming k-ball is clear of potential solutions "should" require $\Omega(n^k)$ different assignments to be checked, but this is by no means easy to <em>prove</em>.  <em>(Note: Ryan Williams points out this lower bound for $k$-ISOLATED SAT would actually prove P ≠ NP, so this problem does not seem to be the right candidate.)</em></p>

<p>Note that the theorem holds unconditionally, regardless of unproved separations such as P vs. NP.  An affirmative answer to this question would therefore not resolve P vs. NP, <em>unless it has additional properties like $k$-ISOLATED SAT above.</em>  A natural separation of NTIME would perhaps help to illuminate part of the "difficult" behaviour of NP, the part which derives its difficulty from an infinite ascending sequence of hardness.</p>

<p>Since lower bounds are hard, I will accept as an answer natural languages for which we may have a good reason to believe a lower bound, even though there may not yet be a proof.  For instance, if this question had been about DTIME, then I would have accepted $f(k)$-CLIQUE, for a non-decreasing function $f(x) \in \Theta(x)$, as a natural language that probably provides the required separations, based on Razborov's and Rossman's circuit lower bounds and the $n^{1-\epsilon}$-inapproximability of CLIQUE.</p>

<p><em>(Edited to address Kaveh's comment and Ryan's answer.)</em></p>

CC BY-SA 2.5
2010-09-01T16:39:02.060Z
that's a neat question,  András
Suresh Venkat
CC BY-SA 2.5
2010-09-01T16:55:21.030Z
Stephen Cook suggested Linear Programming as an possible separator for $k=2$.
András Salamon
CC BY-SA 2.5
2010-09-02T17:49:08.970Z
Could you please explain what do you mean by "nonconstructive argument"? A proof using diagonalization does not need to be nonconstructive.
Kaveh
<cc.complexity-theory><nondeterminism><time-hierarchy>
Are there natural separations in the nondeterministic time hierarchy?
András Salamon
# Are there natural separations in the nondeterministic time hierarchy?

(Asked by: username_0 on 2010-09-01)

The original Nondeterministic Time Hierarchy Theorem is due to [Cook](http://dx.doi.org/10.1016/S0022-0000%2873%2980028-5) (the link is to S. Cook, *A hierarchy for nondeterministic time complexity*, JCSS **7** 343–353, 1973). The theorem states that for any real numbers $r\_1$ and $r\_2$, if $1 \le r\_1 \lt r\_2$ then [NTIME](http://en.wikipedia.org/wiki/NTIME)($n^{r\_1}$) is strictly contained in NTIME($n^{r\_2}$).

One key part of the proof uses (an unspecified) diagonalization to construct a separating language from the elements of the smaller class. Not only is this a nonconstructive argument, but languages obtained by diagonalization usually provide no insight other than the separation itself.

If we want to understand the structure of the NTIME hierarchy, the following question probably needs to be answered:

> Is there a natural language in NTIME($n^{k+1}$) but not in NTIME($n^k$)?

One candidate might be [k-ISOLATED SAT](http://constraints.wordpress.com/2010/04/15/k-isolated-sat/), which requires finding a solution to a CNF formula with no other solutions within Hamming distance k. However, proving the lower bound seems *is* tricky, as usual. It is obvious that checking a Hamming k-ball is clear of potential solutions "should" require $\Omega(n^k)$ different assignments to be checked, but this is by no means easy to *prove*. *(Note: username_3 points out this lower bound for $k$-ISOLATED SAT would actually prove P ≠ NP, so this problem does not seem to be the right candidate.)*

Note that the theorem holds unconditionally, regardless of unproved separations such as P vs. NP. An affirmative answer to this question would therefore not resolve P vs. NP, *unless it has additional properties like $k$-ISOLATED SAT above.* A natural separation of NTIME would perhaps help to illuminate part of the "difficult" behaviour of NP, the part which derives its difficulty from an infinite ascending sequence of hardness.

Since lower bounds are hard, I will accept as an answer natural languages for which we may have a good reason to believe a lower bound, even though there may not yet be a proof. For instance, if this question had been about DTIME, then I would have accepted $f(k)$-CLIQUE, for a non-decreasing function $f(x) \in \Theta(x)$, as a natural language that probably provides the required separations, based on Razborov's and Rossman's circuit lower bounds and the $n^{1-\epsilon}$-inapproximability of CLIQUE.

*(Edited to address username_2's comment and Ryan's answer.)*

**Tags:** cc.complexity-theory, nondeterminism, time-hierarchy

> **Comments:**
> **username_1**: that's a neat question,  András  
> **username_0**: Stephen Cook suggested Linear Programming as an possible separator for $k=2$.  
> **username_2**: Could you please explain what do you mean by "nonconstructive argument"? A proof using diagonalization does not need to be nonconstructive.  

---

## 1 answers

### Answer by username_3 on 2010-09-01. Score: 15 | Accepted answer

As far as I know, we don't know of such languages, or if we do, there is significant controversy about the "naturalness" of them. I know this isn't really a satisfying answer, but I can say:

(a) If you prove an $\Omega(n^k)$ time lower bound for k-ISOLATED SAT for every $k$, then you have actually proved $P \neq NP$.

(b) One way you might hope to show that k-ISOLATED SAT is one of these natural problems in $NTIME[n^{k+1}] - NTIME[n^k]$ is to show that k-ISOLATED SAT problem is hard (in the usual, formal sense of having efficient reductions) for $NTIME[n^k]$. In fact this is the only way we know how to prove such results. But k-ISOLATED SAT is probably not hard in this sense, there are some very unlikely consequences.

The main reason is that k-ISOLATED SAT instances are solvable in $\Sigma\_2 TIME[n]$, independently of $k$. You can existentially guess the isolated assignment, then universally verify (for all $O(\log (\sum\_{i=1}^k {n \choose i}))$ ways to flip up to $k$ bits in the assignment) that none of the other "local" assignments work.

Here is the proof of part (a). Let ISOLATED SAT be the version of the problem with $k$ given as part of the input (in unary, say). Suppose we prove that ISOLATED SAT requires $\Omega(n^k)$ time for all $k$. If $P=NP$, then $\Sigma\_2 TIME[n]$ is in $TIME[n^c]$ for some fixed $c$ (the proof uses an efficient version of Cook's theorem: if there is a SAT algorithm running in time $n^d$, then any $c > d^2$ suffices). But we proved that there is a language in $\Sigma\_2 TIME[n]$ that is *not* in $TIME[n^k]$ for every $k$. This is a contradiction, so $P \neq NP$.

Here is the proof of part (b). If every $L \in NTIME[n^k]$ could be efficiently reduced to a k-ISOLATED SAT formula (e.g., all $n$ bit instances of $L$ get reduced to $k$-ISOLATED SAT formulas of at most $f(k) n^{c}$ size) then $NP=\bigcup\_{k} NTIME[n^k] \subseteq \Sigma\_2 TIME[n^{c+1}]$. This would immediately imply $coNP \neq NP$, but moreover it just looks very unlikely that all of $NP$ can be simulated so efficiently within the polynomial hierarchy.

> **Comments:**
> **username_0**: Thank you for the neat argument showing k-ISOLATED SAT is not going to do the job.  

---

