Is there any space(n) complete language? 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!!
 A: 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).
A: 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!!!
A: 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.
A: 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?) 
