user6530
  • Member for 1 year, 9 months
  • Last seen this week
Proof that no O(n) multiplication algorithm exists
9 votes

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: "...

View answer
Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular
Accepted answer
7 votes

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 ...

View answer
Proof that L^2 is regular => L is regular
Accepted answer
5 votes

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 ...

View answer
CFG that generates $1^*$ is decidable
4 votes

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)...

View answer
Turing machine for $0^{3^k} 1^{p}$
4 votes

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 ...

View answer
Proof of $f(n) + ο(f(n)) = \Theta(f(n))$
Accepted answer
3 votes

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 ...

View answer
Is X+Y sorting problem still an open problem?
Accepted answer
3 votes

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 ...

View answer
Time complexity of $L=\{a^nb^n | n \ge 1\}$
2 votes

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, ...

View answer
Generate the context free grammar for the following language: $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$
Accepted answer
2 votes

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$...

View answer
Existence / non-existence of a sequence with short longest increasing subsequence and decreasing subsequence?
2 votes

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 ...

View answer
How does squaring time complexity imply the same time complexity for multiplying different numbers? Isn't it the other way round?
1 votes

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
Comparisons of functions, their big-oh and their implications
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
Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$
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 ...

View answer
Write a CFG for the language $\{0^n 1^a 2^b \mid n = a+b\}$
1 votes

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 ...

View answer
Recurrence relations and induction: guessing the right bound
Accepted answer
1 votes

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 ...

View answer
The intersection of 2 CFL
Accepted answer
1 votes

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, ...

View answer
Grammar for $\{ (n_a(w) - n_b(w)) mod\ 3 = 2 \} $
Accepted answer
0 votes

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, ...

View answer
Difference between a regular and a non-regular language
0 votes

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 ...

View answer
Description logics with decision problems within NP
0 votes

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, ...

View answer