I am struggling to understand why can't such a language exist(a P-Complete language in log-logarithmic space), according to the question details:
Defining a new kind of reduction: a reduction in log-logarithmic space. For this purpose, we define a log-logarithmic transformer that is identical to a logarithmic transformer, but its working tape can hold $O(log(logn) $symbols and not $O(logn)$ symbols.
We'll say a language A can be reduced in a log-logarithmic space to language B and denote $A ≤_{LL}B$, if exists a transformer with log-logarithmic space that applies a mapping reduction between A to B.
Now, Language C will be called P-complete in regards to reduction in log-logarithmic space if:
- C belongs to class P
- For every language A in P exists a reduction in log-logarithmic space to C(meaning $A ≤_{LL} C$).
I am quite lost and all of the hierarchies involved and I cannot understand why this P-complete language cannot exist in log-logarithmic space. Would be very glad if you could help me understand it and elaborate so it will be clear.
EDIT: adding my attempt:
since $n^{logn}=(2^{logn})^{logn}=2^{log^2n}$, so $2^{log^2n}=o(2^n)$, and at most $O(logn)$ steps. now, if a language $C \in P$, it means that it can be solved by a deterministic turing machine in polynomial time. assume for contradiction, that C is also P-complete in regards to reduction in log-logarithmic space, meaning there exists a reduction in log logarithmic space for every language $A \in P$ to $C$. so, by time hierarchy, we get that if $t:N->N$ is time constructible, then there exists a language $A\in TIME(t(n))$ so that $A \not \in TIME(s(n))$ for every $s(n)=\frac{o(t(n))}{logt(n)}$, meaning that the hierarchies show that $TIME(s(n)) \not \subseteq TIME(t(n))$, so if t is time constructible, and C does at most $O(logn)$ steps, and since $TIME(n) \neq TIME(logn)$, we get a contradiction, meaning that there cannot exist a P-complete in regards to reduction in log-logarithmic space.
Not sure my proof is full or correct, would really appreciate seeing how to do it fully and coherently
Thank you very much for your much appreciated help.
Hint: A TM that always stops, and uses $O(\log\log(n))$ space, does at most $O(2^{\log\log(n)})=O(\log(n))$ steps.
Another hint: We know there are languages in $\text{DTIME}-O(n)$, but not in $\text{DTIME}-O(\log(n))$.
The point is, given an input of length $n$, denote by $x$, any reduction that uses at most $O(\log(\log(n)))$ space, will be able to read only a prefix of $x$ of length $O(\log(n))=O(2^{\log(\log(n)})$.
Take the language $$\text{Majority}:=\{x\in\{0,1\}^*\mid\text{There are at least as many $1$'s in $x$ as $0$'s }\}$$
It is obviously in $\text{P}$, a reduction under $O(\log(\log(n)))$ could cause you to lose information, and therefore $\text{P}$ is not closed under $\text{LL-reduction}$.
for example, if $x = 0^k1^k1$, the reduction can't process the last character of $x$ (because this takes $O(\log(n))$ space), and therefore
$$x\in \text{Majority} \iff \varphi(x)\in L$$
where $\varphi$ is the reduction, and $L$ is some language in $\text{P}$ will not be true.