<p>Any problem has such a version, just PAD it! E.g. the language that consists of a true 3CNF of length m followed by m^2 0's is in DSPACE(sqrt(n)).</p>

CC BY-SA 3.0
2012-05-05T12:46:33.820Z
Thank you! Do you have any idea about poly-logarithmic space?
Abuzer Yakaryilmaz
CC BY-SA 3.0
2012-05-06T00:38:55.123Z
just pad a 3CNF with $2^{\sqrt{n}}$ zeros?
Sasho Nikolov
CC BY-SA 3.0
2012-05-06T06:36:42.153Z
@Sasho: Then the problem would stop being NP-complete, you can only PAD with a poly number of zeros.
domotorp
CC BY-SA 3.0
2012-05-06T06:39:53.353Z
@Abuzer: I think poly-log space would imply that NP is a part of DTIME[$2^{poly-log}$]. This is open and unlikely.
domotorp
CC BY-SA 3.0
2012-05-06T08:19:25.937Z
@domotorp: Yes, you are right! Thank you!
Abuzer Yakaryilmaz
CC BY-SA 3.0
2012-05-07T03:24:50.760Z
yes I know, but it will still be outside $\mathsf{P}$ (assuming $\mathsf{P} \neq \mathsf{NP}$)?
Sasho Nikolov
CC BY-SA 3.0
2012-05-07T03:30:55.230Z
maybe i mean assuming ETH. sorry, no time to think this through. basically, you should be able to pad just enough to make a problem solvable in poly-log nondeterministic space (and quasipoly time), but still keep it outside P
Sasho Nikolov
CC BY-SA 3.0
2012-05-05T11:21:41.357Z
2012-05-05T11:21:41.357Z
domotorp
<p>For any language in $\mathsf{NP}$ there exists a proof that can be verified using $O(\log n)$ working space. One just needs to use the same ideas used to prove SAT is $\mathsf{NP}$-complete. By definition, given an $\mathsf{NP}$ language $L$, we know that there exists a turing machine $M$ such that for any $x \in L$ there exists a $y$ such that $M(x, y)$ accepts. We can construct a logspace verifiable proof for $x$ by writing down $y$ and the computation tableau of $M$ on input $x, y$. It is easy to verify in logspace that the tableau describes a valid accepting computation of $M$. Similarly, for any $x \not \in L$ and any $y$, no valid computation of $M(x, y)$ accepts, so the logspace verifier won't accept any tableau.</p>

<p>Of course this does <strong>not</strong> show that $\mathsf{NP} = \mathsf{NL}$ (because that would imply $\mathsf{NP} = \mathsf{P}$). The reason is that the verifier has two-way access to the proof (can go back and forth). The proof-verifier definition of $\mathsf{NL}$ gives the the logspace verifier only one-way access to the proof (once a bit of the proof is read and the head moves right it cannot move left). </p>

CC BY-SA 3.0
2012-05-05T18:01:37.013Z
I do not get the idea! Do you mean probabilistic verification? If so, actually constant-space is sufficient for any language in NP since $ DSPACE(2^n) \subseteq IP(1) $. Or, do you mean log-space reduction of any language in NP to SAT? I am really confused!
Abuzer Yakaryilmaz
CC BY-SA 3.0
2012-05-05T22:58:07.027Z
Let me try another way: one standard way to define $\mathsf{NP}$ is as the class of languages that have deterministic polytime verifiers. I am saying that an equivalent definition is to define $\mathsf{NP}$ as the class of languages that have deterministic logspace verifiers with multiple-read access to the proof. no randomness is necessary.
Sasho Nikolov
CC BY-SA 3.0
2012-05-06T08:38:34.883Z
Thank you. Actually I knew that :) The log-space nondeterministic class based on your explanation is denoted $ \mathsf{NSPACE_{off\mbox{-}line}(log)} $, and yes, $ \mathsf{NP} = \mathsf{NSPACE_{off\mbox{-}line}(log)} $. Moreover, $ \mathsf{NL} = \mathsf{NSPACE_{on\mbox{-}line}(log)} $. The notion "off-line" and "on-line", as you pointed out, represent the access types to the given proof. REF: Section 5.3.1 of Computational Complexity by Oded Goldreich (2008).
Abuzer Yakaryilmaz
CC BY-SA 3.0
2012-05-05T16:42:05.427Z
2012-05-05T23:02:21.827Z
2012-05-05T23:02:21.827Z
Sasho Nikolov
<p>The planar version of many NP-complete problems belong to $NTISP(n,n^q)$ for some $q&lt;1$</p>

<p>See for example "<a href="http://arxiv.org/abs/cs/0606058">Lower Bounds and Complete Problems in Nondeterministic Linear Time and
Sublinear Space Complexity Classes</a>" by P. Chapdelaine and E. Grandjean (2006)</p>

CC BY-SA 3.0
2012-05-05T12:48:51.027Z
Thank you! Do you have any idea about poly-logarithmic space?
Abuzer Yakaryilmaz
CC BY-SA 3.0
2012-05-05T11:16:09.297Z
2012-05-05T11:16:09.297Z
Marzio De Biasi
<p>There are some NP-Complete problems ($ \mathsf{SAT} $, $ \mathsf{SUBSETSUM} $, etc.) known to be in $ \mathsf{DSPACE(n)} $. What about the sub-linear spaces?</p>

<blockquote>
  <p>Is there any known NP-Complete (or NP-Intermediate) problem in <strong>sublinear nondeterministic</strong> space?</p>
</blockquote>

<cc.complexity-theory><np-hardness><nondeterminism><np-intermediate>
Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?
Abuzer Yakaryilmaz
# Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?

(Asked by: username_0 on 2012-05-05)

There are some NP-Complete problems ($ \mathsf{SAT} $, $ \mathsf{SUBSETSUM} $, etc.) known to be in $ \mathsf{DSPACE(n)} $. What about the sub-linear spaces?

> Is there any known NP-Complete (or NP-Intermediate) problem in **sublinear nondeterministic** space?

**Tags:** cc.complexity-theory, np-hardness, nondeterminism, np-intermediate

---

## 3 answers

### Answer by username_3 on 2012-05-05. Score: 14 | Accepted answer

The planar version of many NP-complete problems belong to $NTISP(n,n^q)$ for some $q<1$

See for example "[Lower Bounds and Complete Problems in Nondeterministic Linear Time and
Sublinear Space Complexity Classes](http://arxiv.org/abs/cs/0606058)" by P. Chapdelaine and E. Grandjean (2006)

> **Comments:**
> **username_0**: Thank you! Do you have any idea about poly-logarithmic space?  

---

### Answer by username_1 on 2012-05-05. Score: 14

Any problem has such a version, just PAD it! E.g. the language that consists of a true 3CNF of length m followed by m^2 0's is in DSPACE(sqrt(n)).

> **Comments:**
> **username_0**: Thank you! Do you have any idea about poly-logarithmic space?  
> **username_2**: just pad a 3CNF with $2^{\sqrt{n}}$ zeros?  
> **username_1**: @Sasho: Then the problem would stop being NP-complete, you can only PAD with a poly number of zeros.  
> **username_1**: @Abuzer: I think poly-log space would imply that NP is a part of DTIME[$2^{poly-log}$]. This is open and unlikely.  
> **username_0**: @domotorp: Yes, you are right! Thank you!  
> **username_2**: yes I know, but it will still be outside $\mathsf{P}$ (assuming $\mathsf{P} \neq \mathsf{NP}$)?  
> **username_2**: maybe i mean assuming ETH. sorry, no time to think this through. basically, you should be able to pad just enough to make a problem solvable in poly-log nondeterministic space (and quasipoly time), but still keep it outside P  

---

### Answer by username_2 on 2012-05-05. Score: 11

For any language in $\mathsf{NP}$ there exists a proof that can be verified using $O(\log n)$ working space. One just needs to use the same ideas used to prove SAT is $\mathsf{NP}$-complete. By definition, given an $\mathsf{NP}$ language $L$, we know that there exists a turing machine $M$ such that for any $x \in L$ there exists a $y$ such that $M(x, y)$ accepts. We can construct a logspace verifiable proof for $x$ by writing down $y$ and the computation tableau of $M$ on input $x, y$. It is easy to verify in logspace that the tableau describes a valid accepting computation of $M$. Similarly, for any $x \not \in L$ and any $y$, no valid computation of $M(x, y)$ accepts, so the logspace verifier won't accept any tableau.

Of course this does **not** show that $\mathsf{NP} = \mathsf{NL}$ (because that would imply $\mathsf{NP} = \mathsf{P}$). The reason is that the verifier has two-way access to the proof (can go back and forth). The proof-verifier definition of $\mathsf{NL}$ gives the the logspace verifier only one-way access to the proof (once a bit of the proof is read and the head moves right it cannot move left).

> **Comments:**
> **username_0**: I do not get the idea! Do you mean probabilistic verification? If so, actually constant-space is sufficient for any language in NP since $ DSPACE(2^n) \subseteq IP(1) $. Or, do you mean log-space reduction of any language in NP to SAT? I am really confused!  
> **username_2**: Let me try another way: one standard way to define $\mathsf{NP}$ is as the class of languages that have deterministic polytime verifiers. I am saying that an equivalent definition is to define $\mathsf{NP}$ as the class of languages that have deterministic logspace verifiers with multiple-read access to the proof. no randomness is necessary.  
> **username_0**: Thank you. Actually I knew that :) The log-space nondeterministic class based on your explanation is denoted $ \mathsf{NSPACE_{off\mbox{-}line}(log)} $, and yes, $ \mathsf{NP} = \mathsf{NSPACE_{off\mbox{-}line}(log)} $. Moreover, $ \mathsf{NL} = \mathsf{NSPACE_{on\mbox{-}line}(log)} $. The notion "off-line" and "on-line", as you pointed out, represent the access types to the given proof. REF: Section 5.3.1 of Computational Complexity by Oded Goldreich (2008).  

---

