9
$\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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
14
$\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)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! Do you have any idea about poly-logarithmic space? $\endgroup$
    – Abuzer Yakaryilmaz
    May 5, 2012 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)).

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you! Do you have any idea about poly-logarithmic space? $\endgroup$
    – Abuzer Yakaryilmaz
    May 5, 2012 at 12:46
  • 1
    $\begingroup$ just pad a 3CNF with $2^{\sqrt{n}}$ zeros? $\endgroup$
    – Sasho Nikolov
    May 6, 2012 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, 2012 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, 2012 at 6:39
  • $\begingroup$ @domotorp: Yes, you are right! Thank you! $\endgroup$
    – Abuzer Yakaryilmaz
    May 6, 2012 at 8:19
11
$\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).

Improve this answer
$\endgroup$
3
  • $\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, 2012 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, 2012 at 22:58
  • 4
    $\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, 2012 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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