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

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?

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" by P. Chapdelaine and E. Grandjean (2006)

• Thank you! Do you have any idea about poly-logarithmic space? – Abuzer Yakaryilmaz May 5 '12 at 12:48

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

• Thank you! Do you have any idea about poly-logarithmic space? – Abuzer Yakaryilmaz May 5 '12 at 12:46
• just pad a 3CNF with $2^{\sqrt{n}}$ zeros? – Sasho Nikolov May 6 '12 at 0:38
• @Sasho: Then the problem would stop being NP-complete, you can only PAD with a poly number of zeros. – domotorp May 6 '12 at 6:36
• @Abuzer: I think poly-log space would imply that NP is a part of DTIME[$2^{poly-log}$]. This is open and unlikely. – domotorp May 6 '12 at 6:39
• @domotorp: Yes, you are right! Thank you! – Abuzer Yakaryilmaz May 6 '12 at 8:19

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

• 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 May 5 '12 at 18:01
• 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 May 5 '12 at 22:58
• 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 May 6 '12 at 8:38