0
$\begingroup$

Disclaimer

I have no idea about complexity theory. If this question makes no sense or is wrong, mods are free to delete the question

I´ve read somewhere that the problems that can be correctly decided in $o(log\ log\ n)$ space are exactly the regular languages. I was thinking in "$promise-DSPACE(o(log\ log\ n))$" problems. Those are some problems that I have just "invented", which are problems that can be solved in $o(log\ log\ n)$ space when we pad the problem.

That is, if we have a problem $L$ not in $DSPACE(o(log\ log\ n))$, we have another problem $L'$ that is formed by taking $L$ and concatenating enough symbols to $L$ so that the new problem, with that padding, can be solved in $DSPACE(o(log\ log\ n))$

For instance the language ${a^{n}b^{n}}$ is not regular. This language can be decided in logspace because we can count the length of the input with logarithmic space.

Now, the language ${a^{n}b^{n}p^{2^{2^{|x|}}}}$ can be "solved" in $O(log\ log\ log\ n)$ space, provided that we give it always the right quantity of padding ($|x|$ is the length of the input and $p$ is a symbol used for padding). And we have $DSAPCE(O(log\ log\ log\ n)) \in DSPACE(o(log\ log\ n))$.

We define "promise-DFA" problems which are the problems that we can "solve" on a DFA.

I use solve instead of recognize because that´s the word used here in this document. Solving a language is different than recognizing a language

When we solve a language $A$ with a DFA, we say that there are two sets $A_{yes}$ and $A_{no}$ inside the language. The DFA has to accept the words that belong to $A_{yes}$ and reject the words that belong to $A_{no}$. If the input doesn´t belong to any of the two sets, the DFA can accept or reject the string, it doesn´t matter.

Now, let´s define a class of languages, $C$. A language, $L'$ in this class is formed by words that belong to a language $L$ that can´t be decided in $DSPACE(o(log\ log\ n)$ and enough padding at the end of the problem $L$ so that the new problem, $L'$, can be solved in $DSPACE(o(log\ log\ n))$.

What I want to know is if there is some language inside $C$ that can be solved, it doesn´t have to be recognized, by a DFA.

I know that there are problems in $C$ which cannot be solved by a DFA, the proof is below

There are problems in "$promise-DSPACE(o(log\ log\ n))$" that cannot be solved by a DFA

I think there are some languages in "$promise-DSPACE(o(log\ log\ n))$" that are not in "$promise-DFA$"

"Proof":

Let $L$ be an arbitrary EXPSPACE complete problem, then there is another problem $L' = {Lp^{2^{2^{2^{2^{|x|}}}}}}$ that can be solved in $DSPACE(O(log\ log\ log\ n^k)) \in DSPACE(o(log\ log\ n))$ (again, $|x|$ is the length of the input in $L$ and $p$ is a padding symbol).

Suppose that there is a DFA $y$ that correctly solves $L'$. We number the states in $y$. Lets call $z$ the number of the state the DFA will be after reading the part of the input that belongs to $L$.

I´ve seen somewhere that a DFA can be simulated by a constant space turing machine. Therefore, we have a constant space machine $M$ that simulates $y$.

Claim:

The machine $M$ with "constant advice" can solve the EXPSPACE-complete language $L$.

Proof:

We first describe the advice tape:

We have a tape with a number of symbols, the advice tape. Now, as other advice classes like $P/poly$ this advice changes only depending on the length of the input, not the content.

The advice contains a binary chain that in position $i$ has a "zero" if the DFA $y$ that is on state number $i$ ends in a non accepting state after running the DFA $y$ with the amount of padding in $L'$ (if the DFA $y$ ends in an accepting state, it has a "one" in that position). Since the amount of padding depends only on the length of the input in $L$, we have a different chain for each padding. And also the binary chain has always constant symbols, because there is always the same amount of symbols in a DFA for each size of the input.

Now the proof:

We simulate the DFA with the input that belongs to $L$. Again, $z$ is the number of the state in which the DFA is after the simulation. We store that number. It only takes constant space to do this, since there is always a limited number of states in a DFA.

Finally, we look for the symbol in position $z$ in the advice chain. We accept if there is a "one" and reject if there is a "zero".

So we can solve $L$ in constant space with constant advice as claimed.

Then, we have that constant space with constant advice is contained in $L/poly$, which in turn is contained in $P/poly$. But I´ve seen somewhere that no EXPSPACE-complete problem can be decided in $P/poly$ and so we reach a contradiction and QED.

With this, we can prove that there are some languages in "$promise-o(loglog\ n)$" that are not in "$promise-DFA$"

Now, I am a very very ignorant person about math. I don´t do proofs, so this proof is surely wrong. If that´s the case, mods are free to modify or delete the proof.

There are surely better proofs than this out there, but I like this because is mine

Things that I found looking on the internet

After coming with the previous proof, I found a document that talked about promise automatas which is something that is very similar to the things i´m talking here.

The document is this

In the document, they talk about a variant of a DFA (called a pvDFA) that can "solve" languages instead of recognizing languages as normal DFAs do. Solving means that you can correctly distinguish among two different classes of inputs, acepting those that belong to "class 1" and rejecting those that belong to "class 2". If the input doesn´t belong to any of those two classes, it can either accept or reject and it doesn´t matter.

In page 9 they show a pumping lemma that can be used to determine those languages that cannot be solved by this DFA and in page 10 they prove using the lemma that the language ${a^{n}b^{n}}$ cannot be solved by a pvDFA.

Now, I think that their proof breaks with the padded language $L = {a^{n}b^{n}1^{2^{2^{|x|}}}}$ (x is the length of the input).

We have $w = a^{p}b^{p}1^{2^{2^{2p}}}$ that belongs to $L$ and we have $C_{yes} = \{a^{n}b^{n}1^{2^{2^{2n}}}\}$ and $C_{no} = \{a^{l}b^{m}1^{2^{2^{l+m}}}| l \neq m\}$

Let $y = a^{k}$ such that $|xy| \leq p$.

We duplicate $y$ like they do in their proof and we have:

$xy^2z = a^{p+k}b^p1^{2^{2^{2p}}}$

And we can see that the word doesn´t belong to $C_{no}$. So the proof doesn´t work anymore.

I don´t know anything about automatas, apart from things that I´ve read here and there. So maybe you can patch the proof

$\endgroup$
  • 1
    $\begingroup$ That's a big post. What exactly is your question? Does it need the full proof attempt? $\endgroup$ – Raphael Jul 2 '17 at 6:34
  • $\begingroup$ The theorem states that anything solvable in $o(\log\log n)$ space is solvable in $O(1)$ space (i.e., by a DFA). In your case, you wouldn't be able to recognize that the input is formatted properly without using $\Omega(\log\log n)$ space. If you only consider inputs which are properly formatted, then the example of padded $a^nb^n$ shows that the theorem no longer holds. $\endgroup$ – Yuval Filmus Jul 2 '17 at 8:09
  • $\begingroup$ Can you give a more precise definition of the complexity class? I'm not sure exactly how to interpret ``given enough "padding"''. Also, you say "in $O(\log \log n)$", but what resource are you talking about? Space? Time? Also, I wonder if the model of computation might be important to choose here. (Single-tape Turing machines? Multiple-tape Turing machines?) Finally, it would help to clarify what your question is, and to proof-read your question to fix the typesetting. Typing text inside $...$ doesn't work very well. I don't think you're using "promise" in the standard way. $\endgroup$ – D.W. Jul 2 '17 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.