2
$\begingroup$

Does space(n) have a complete language? Actually the following was in a complexity cource final exam :

if A is SPACE(n) hard then A is also PSPACE-hard

(this is supposed to be shown by padding...i don't know how exactly)

i think that it is false (if space(n) has a complete language then it is trivially false) because of the proof of TBQF being PSPACE-complete (with some minor modifications, i think that it can be shown that there is a language which is space(n) hard (not nessesarily complete) that it is decided by a O(n^k) for some small value of k). I am not sure though!!

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Under what type of reductions? $\endgroup$
    – Robin Kothari
    Commented Sep 26, 2010 at 3:47

4 Answers 4

Reset to default
2
$\begingroup$

The padding trick to show that if $A$ is DSPACE($n$)-hard then it is also PSPACE-hard is fairly standard and goes as follows. Start with an arbitrary language $B$ in PSPACE, say in DSPACE($n^k$). Let $B'$ be the "padded" version of $B$ defined as the set of words of the form $$ x01^{|x|^k} $$ for $x \in B$. Note that $B'$ is in DSPACE($n$) since we are given the space to simulate the $n^k$-space machine in the input, and that there is a trivial reduction from $B$ to $B'$: $$ x \mapsto x01^{|x|^k}. $$ Now, since $A$ is DSPACE($n$)-hard and $B'$ is in DSPACE($n$), there is a also a polynomial-time reduction from $B'$ to $A$. Composing the reductions we get the one from $B$ to $A$.

Note that this fact is not incompatible with DSPACE($n$) having a complete language (under polynomial-time reductions) and the fact that DSPACE($n$) $\not=$ PSPACE because DSPACE($n$) is not closed under polynomial-time reductions. Whether DSPACE($n$) actually has a complete language is a different story. The standard candidates (QBF, universal space bounded machine, etc.) incur $O(\log n)$ factors in the encodings to take care of unbounded alphabets or unbounded number of tapes in the machines defining DSPACE($n$), so they do not work directly. Relatively recent work by Ryan Williams where he examines the efficiency of the encodings could be relevant for this (see http://www.cs.cmu.edu/~ryanw/qbf-lower-bd.pdf).

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is meant to be a comment on Kristoffer's answer below but I don't have enough reputation to place it there. The comment is that it seems to me that the tape-compression theorem, which you invoke to turn every machine to one with a single work-tape and a fixed alphabet, works precisely by increasing the alphabet or the number of work-tapes; or does it? $\endgroup$
    – slimton
    Commented Sep 27, 2010 at 21:47
1
$\begingroup$

Thanks!!! The padding explanation was very enlighting!!!!

I also understand the part about DSPACE(n) having complete language doesn't contradict the above, but even if there is a O(n^{3}) DSPACE(n) hard language (that is what i meant when i mentioned an O(n^{k}) language for some small k) then this could lead to a contradiction (it depends on the size of the reduction...since a O(n^k) (k>>3) language could be reduced to this DSPACE(n)-hard language but the reduction could output an O(n^{k/3}) size input for the machine that decides this DSPACE(n)-hard language)..but if this is not the case that could lead to SPACE(n^{k_{1}}) = SPACE(n^{k_{2}}), with k_{1} < k_{2}.

thank you again!!!

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Hi kos, you should register an account so that your reputation will be in one place, and you can then edit, comment, and vote on other answers -- write the moderators so that they can combine your two unregistered accounts into one as well. $\endgroup$
    – j.c.
    Commented Sep 27, 2010 at 19:43
1
$\begingroup$

A canonical complete language for $LINSPACE = DSPACE(n)$ would be the following language

$L =\{ < M,x,1^s>\ :\ M\ \text{is a Turing machine that accepts}\ x\ \text{using space}\ s\}$

which is complete for $LINSPACE$ under linear time reductions, logspace reductions, as well as polynomial time reductions.

Here linear time reductions are arguably the most natural reductions, since LINSPACE is closed under linear time reductions these. As for logspace and polynomial time reductions, the language $L$ above is even hard for $PSPACE$ under these reductions.

Another thing to mention about linear space is the connection to context sensitive languages. Turing machines that operate in linear space are also known as Linear bounded automata. Through grammars one can define (somewhat more natural) complete languages for $LINSPACE$ and $NLINSPACE=NSPACE(n)$ than the canonical complete problems.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I should also clarify to address the worries expressed in the previous answer of possible large alphabets and number of tapes of the Turing machine M in the language $L$ defined above. I shall simply only allow Turing machines M over a fixed tape alphabet and with a single work-tape. This ensures that $L$ is in $LINSPACE$. Also, by tape reduction and encoding alphabets, any $O(n)$ space bounded Turing machine can be converted into this form and still be $O(n)$ space bounded. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Commented Sep 27, 2010 at 19:22
0
$\begingroup$

If we consider only log-space reductions, can it be then that L (above) is also PSPACE-hard? (doesn't the padding trick suggest that we use polynomial-space reduction?)

Improve this answer
$\endgroup$
1
  • $\begingroup$ This should really have been left as an edit to the original question. $\endgroup$
    – Yemon Choi
    Commented Sep 29, 2010 at 22:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .