8
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

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)

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

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

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

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Abuzer Yakaryilmaz May 5 '12 at 18:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov May 5 '12 at 22:58
  • 3
    $\begingroup$ 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). $\endgroup$ – Abuzer Yakaryilmaz May 6 '12 at 8:38

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.