No nontrivial lower bound for the multiplcation is known (clearly, it is $\Omega(n)$) and David Harvey himself does not know if a complexity of $O(n\log(n))$ is the best possible: in his own words: "...

Nice question! This is a very nontrivial problem involving regular languages. First of all: no, you cannot run an automaton on every substring of a string skipping other letters, you are supposed to ...

Your claim is false. Indeed, it is equivalent to prove that if a language $L$ is not regular, then also $L^2$ is not regular, but this is not true. Here Yuval Filmus gives (possibly) two examples of a ...

Maybe you're confusing two different problems. The algorithm you are describing shows that the problem of testing whether a CFG generates some string from $1^∗$ is decidable (e.g., see here at page 21)...

Just for fun, I've constructed the TM sketched by Rodion, you can simulate its behaviour here. Observe that I assume $p$ (or $m$, which is the same) strictly positive; moreover one actually has to use ...

Obviously, $f(n)+o(f(n))=\Omega(f(n))$ (clearly, I'm assuming all functions being positive), so you need only to prove that $f(n)+o(f(n))=O(f(n))$. But a function in $o(f(n))$ is definitevely smaller ...

Here the problem status is "open". The page was revised in 2006 and it seems updated to September 2017, so we can safely suppose that the problem is still open. Anyway, an algorithm that solves the ...

If I correclty understand the algorithm, your TM starts "marking" the first $a$, then it finds the first $b$ and marks it, then it comes back the the first unmarked $a$ and so on. So, ...

Unfortunately your grammar generates only $\epsilon$ (which is not in the language, since $n$ and $m$ are greater than 0), as you don't delete the $A$; moreover you don't control that the number of $A$...

There are also short sequences that satisfy your request. Consider for example the first 16 terms of the binary Van der Corput sequence $$0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.$$ In ...

Of course, we can suppose we are able to do sum and difference in linear time. Now, if we want to calculate $h\cdot k$, we can find in linear time $a$ and $b$ such that $h=a-b$ and $k=a+b$: take $a=\... View answer 1 votes As a counterexample you can take$f(n)=n$and$g(n)=\sqrt{n}$. You can think that$f(n)=O(n^2)$means that an upper bound for$f(n)$is$n^2$(of course, without considering multiplicative constant), ... View answer 1 votes I don't know if$x$,$y$, etc. can be$0$, so maybe there's something to fix (e.g., you'll need$S\rightarrow \varepsilon$etc.), but you can try something like this:$S\rightarrow 0S1 \mid 0A0 \mid ...

Unfortunately your grammar generates mixed $1$s and $2$s. You can try something like this: $S\rightarrow 0SB | S'$ $S' \rightarrow 0S'A | \varepsilon$ $A\rightarrow 1$ $B\rightarrow 2$ Notice that I ...

For sure, $T(\sqrt{n})\leq T(n)$, so $T(n)\leq 2T(n-1)+n$, but this produces an exponential upper bound, which is correct but to big to be useful. Anyway, in this case if we start from the solution of ...

The set $A$ cointains all the strings on the alphabet $\{a,b,c\}$ starting with $a$, ending with $c$ and with the same number of $b$s and $c$s. Similarly, $B$ is made by strings on the same alphabet, ...

Start from the initial state $q_0$: the current value of $(n_a(w) - n_b(w)) \pmod 3$ is 0. Next, if you read $a$ in $q_0$, then the current value of $(n_a(w) - n_b(w)) \pmod 3$, which is 0, becomes 1, ...

Be $\Sigma$ an alphabet, consider $L_1=\Sigma^*$ and $L_2$ a non-regular language, then also its complement, i.e. $L_1\setminus L_2$, is non-regular (remember that the family of regular language is ...
Yes, but the only example I know is subsumption in FL$^-$, which actually is in P. On the other hand, subsumption in full FL is co-NP hard. A standard reference is Levesque and Brachman, ...