title: Unique tilings of squares

text:
# Question
Title: Unique tilings of squares
We want to tile $m\times m$-square using two types of tiles: $1 \times 1$-square tile and $2 \times 2$-square tile such that every underlying square is covered without overlapping. Let us define a function $f(n)$ that gives the size of largest uniquely tillable square using $n$ $1\times 1$-squares and any number of $2 \times 2$-squares.

Is this function computable? What is the algorithm?

EDIT1: Based on Steven's answer, unique tiling means that there is one way to place the $2 \times 2$-squares inside the $m \times m$-square with a unique configuration for the positions of the $n$ $1 \times 1$-squares inside the $m \times m$-square.

# Answer
Here's an argument to prove my speculation in comments that no such unique tilings exist for any non-square $n\gt 5$. Firstly, as noted by Sasho in comments, $n$ must be restricted, because no such tilings exist if $n\equiv2$ or $3\pmod 4$. If $n$ is a perfect square $n=k^2$ then obviously the $k\times k$ square is uniquely tileable, so $f(n)$ is clearly defined and non-zero in these cases. To complete the argument, it just remains to show that no tiling involving $1$ or more $2\times 2$ tiles can be unique.

First, consider the case $n\equiv 0\pmod 4$, say $n=4k$. If we have a tiling of an $m\times m$ square using $n\ 1\times 1$ tiles, obviously $m$ must be even, say $m=2j$; then we can construct tilings by building a $j\times j$ tiling of $2\times2$ tiles and then replacing $k$ of these by 'blocks' of four $1\times 1$ tiles. It's clear that different replacements can always lead to distinct tilings except in the cases $m=4, n=12$ or $m=4, n=4$ where there's either a single $2\times 2$ tile or a single 'block of four' left over; in these cases, though, there's a different inequivalent tiling, one which puts a $2\times 2$ tile in the middle of an edge rather than in a corner.

Finally, suppose $n\equiv 1\pmod 4$, in particular presume $n=4t+1$ (and with $t\gt 1$ to prevent a slightly trivial case where there's simply 'not enough room' in the square for the following argument to go through). Then no square of size $(2t+1)^2$ or smaller can be uniquely tileable: consider a tiling with $1\times 1$ tiles across the top of the square and down the right of the square (with any extra $1\times 1$ tiles just tucked onto the right side — they can't affect the argument). Now the $2\times 3$ 'block' in the top-left of the square (consisting of the two $1\times 1$ tiles on the top and the $2\times 2$ tile beneath them) can be 'flipped' to produce a tiling that will necessarily be different from the tiling we've constructed. Finally, no square of size larger than $(2t+1)^2$ can be tileable at all: suppose we're trying to tile a square of size $(2s+1)^2$ for $s\gt t$; then by the pigeonhole principle we can't fit any more than $s^2\ 2\times 2$ tiles onto the square, which means that there are $(2s+1)^2-4s^2 = 4s^2+4s+1-4s^2=4s+1$ squares left over - but since $s\gt t$, $4s+1\gt 4t+1=n$, the number of $1\times 1$ tiles we have available.

Thus, the only unique tilings that exist for $n\gt 5$ are those that use no $2\times 2$ tiles at all, and $f(n)$ is only non-zero when $n$ is a square (in which case it equals $\sqrt{n}$).
> 7 votes

---
Tags: computability, combinatorics
---


# Question
Title: Does $\mathsf{NSPACE}( f (n)) = \mathsf{coNSPACE}( f (n))$ hold for $ f(n) < \log (n) $?
It's known that for $f(n) \geq \log n$, $\mathsf{NSPACE}(f(n)) = \mathsf{coNSPACE}(f(n))$.

What if $f(n)\<\log n$? Are they also equal?

# Answer
> 8 votes
Immerman–Szelepcsényi theorem works under logarithmic reductions. Sublogarithmic space classes have different reductions. The TMs working within **sublogarithmic space cannot even record the the length of the input**. It has been shown that the space hierarchy for any sublogarithmic bound in **Ω(log log n)-- o(log n)** is inﬁnite. You can find it in following references:

V. Geffert. **Sublogarithmic σ2-space is not closed under complement and other separation results**. Theoretical Informatics and Applications, 27:349–366, 1993.

M. Liśkiewicz and R. Reischuk. **Separating the lower levels of the sublogarithmic space hierarchy**. In Proceedings of the Symposium on Theoretical Aspects of Computer Science, pages 6–27, 1993.

B. von Braunmuhl "**Alternation for two-way machines with sublogarithmic space**". In Proceedings of the Symposium on Theoretical Aspects of Computer Science, pages 5–15, 1993.

The paper **The complexity world below logarithmic space** by M. Liśkiewicz and R. Reischuk contains an excellent wrap up of the sublogarithmic space.

---
Tags: complexity-theory, space-complexity
---


title: Star operation in CS theory

text:
# Question
Title: Star operation in CS theory
I have a question about the regular operation 'star' in computational theory.

IF $A$ is $\\{ good , bad \\}$ then

$A^\* = \\{ \varepsilon , good, bad , goodgood, goodbad, badgood , \dots \\}$

What is the exact "regular operation" mean then ?

Can we use $^\*$ operation only for regular language ? I don't think so.

$L = \\{0^n1^n \mid n \ge 0 \\}$ is a famous example of a non-regular language, but it seems we can create $L^\*$?

# Answer
> 8 votes
The $^\*$ is an operator that takes a language (not only regular languages) $L$ and produces a new language $L^\*$ called the Kleene closure of $L$. A language is a set of strings over a finite alphabet (alphabets are commonly denoted by $\Sigma$).

# Definition of $L^\*$

$$L^\*=\bigcup\_{i\in \mathbb{N}\_0}L^i=L^0\cup L^1\cup L^2\dots$$

Where, $L^0=\\{\epsilon\\}$ and $L^n=LL^{n-1}$ for $n\gt0$

# Example

Let $\Sigma=\\{0,1\\}$.

$\Sigma^0=\\{\epsilon\\}$

$\Sigma^1=\Sigma\Sigma^0=\\{0,1\\}$

$\Sigma^2=\Sigma\Sigma^1=\\{00,01,10,11\\}$

$\dots$

$\Sigma^\*=\\{\epsilon,0,1,00,01,10,11,\dots\\}$

In other words, $\Sigma^\*$ is the set of all finite-length binary strings.

# Answer
> 1 votes
The operation you refer to (Kleene star) is an operation on *languages* (sets of strings). The language doesn't have to be regular at all to apply it. It's relation to regular languages is that it is one of the operations (with concatenatin and union) that define regular languages starting from the empty language, the language containing only the empty string, and the languages made of the strings of length one.

# Answer
> 1 votes
You can certainly apply the *Kleene star* operation on any set, however the *regular languages* are *closed* under taking the Kleene star. This means that if a language $L$ is regular, so is $L^\*$.

---
Tags: formal-languages
---


title: Quick union and heuristic by size

text:
# Question
Title: Quick union and heuristic by size
Studying Quick-Find and Quick-Union heuristic I've found clear that:

* with quick find trees and a union based on the size of the trees we can make a union in $T\_{am}(n)=O(\log(n))$
* with quick find trees and a union based on the height of the trees we can make a find in $T(n)=O(\log(n))$

But I read that using quick union trees and an union based on the size of the trees we can also have a find in $T(n)=O(\log(n))$, so my question is how can this be demonstrated? What relationship is there between height and size?

For example knowing that $\text{size}(A)=4$ I could have both:

```
        A                A
      / | \              |
     1  2  3             1
                         |
                         2
                         |
                         3

```

# Answer
> 1 votes
To union-by-size two trees, you have to find their roots first. Since union-by-size takes logarithmic time (your first bullet), then first must take logarithmic time as well.

Here is a more formal argument. Say you want to union-by-size two trees $T\_1$ and $T\_2$. Assume that their heights are logarithmic in their sizes:

$H(T\_1)\le \log(n\_1)$ and $H(T\_2)\le \log(n\_2)$

Where $H$ is the height function and $n\_1$ (resp. $n\_2$) is the number of nodes in tree $T\_1$ (resp. tree $T\_2$). There are two cases to consider: either one tree has fewer nodes than the other or both trees have the same number of nodes.

# Case # 1

Say $n\_1\lt n\_2$. The resulting tree $T$ has height $H(T)=\max\\{H(T\_1)+1, H(T\_2)\\}$

Depending on the max we have:

$H(T)\le \log(n\_1) + 1\le \log(2n\_1)\le \log(n\_1 + n\_2)\le \log(n)$ (because $n\_1\lt n\_2$)

Or,

$H(T)\le \log(n\_2)\le \log(n)$

# Case # 2

In this case, $H(T)\le \max\\{H(T\_1),H(T\_2)\\}+1$.

Again depending on the max we have:

$H(T)\le \log(n\_1)+1\le \log(2n\_1)\le \log(n\_1+n\_2)\le \log(n)$ (because $n\_1=n\_2$) and likewise for the other one.

For the base case choose $n=1$ because $H(T)=0\le \log(1)=0$

---
Tags: algorithms, heuristics, union-find
---


# Question
Title: Why are there more non-computable functions than computable ones?
I'm currently reading a book in algorithms and complexity. At the moment I'm, reading about computable and non-computable functions, and my book states that there are many more functions that are non-computable than computable, in fact the majority is non-computable it says. In some sense I can intuitively accept that but the book does not give a formal proof nor does it elaborate much on the topic.

I just wanted to see a proof/let someone here elaborate about it/understand more strictly why there are so many more non-computable functions than computable ones.

# Answer
The are *countably* many computable functions:

Each computable function has at least one algorithm. Each algorithm has a finite description using symbols from a finite set, e.g. finite binary strings using symbols $\\{0,1\\}$. The number of finite binary strings denoted by $\\{0,1\\}^\*$ is countable (i.e. the same as the number of natural numbers $\mathsf{N}$).

Therefore there can be *at most* countably many computable functions. There are *at least* countable many computable function since for each $c\in \\{0,1\\}^\*$, the constant function $f(x)=c$ is computable.

In other words, there is a correspondence between:

* the set of computable functions,
* the set of algorithms,
* $\\{0,1\\}^\*$, the set of finite strings from $\\{0,1\\}$, and
* $\mathbb{N}$, the set of natural numbers.

On the other hand, there are *uncountably* many functions over strings (or natural numbers). A function $f:\mathbb{N} \to \mathbb{N}$ (or $f:\\{0,1\\}^\* \to \\{0,1\\}^\*$) assigns a value for each input. Each of these values can be chosen independently from others. So there are $\mathbb{N}^\mathbb{N}=2^\mathbb{N}$ possible function. The number of functions over natural numbers is equal to the number of real numbers.

Since only countably many of functions are computable, most of them are not. In fact the number of uncomputable functions is also $2^{\mathbb{N}}$.

If you want to picture this intuitively, think about natural numbers and real numbers, or about finite binary strings and infinite binary strings. There are way more real numbers and infinite binary strings than natural numbers and finite strings. In other words $\mathbb{N} \< 2^\mathbb{N}$ (for a proof of this fact see Cantor's diagonal argument and Cardinal arithmetic).
> 37 votes

# Answer
Here is an "explicit" construction of uncountably many non-computable Boolean functions. Let $K$ be some fixed non-computable Boolean function, say the characteristic function of the halting problem. Consider the set of functions $$ F = \\{ f \colon \mathbb{N} \to \\{0,1\\} : \forall x \in \mathbb{N}, f(2x) = K(x) \\}. $$ Each $f \in F$ is non-computable, and $F$ is uncountable.

There is a similar construction with computable functions. Given a computable function $R$, let $$ G = \\{ g \colon \mathbb{N} \to \\{0,1\\} : \exists n \in \mathbb{N} \forall m \geq n, g(m) = R(m). \\} $$ In other words, $g \in G$ if it differs from $R$ on finitely many values. All functions in $G$ are computable (hard-code the finitely many differences). In contrast to the previous situation, $G$ is countable.

So there are lots of non-computable function since we have "infinitely many" degrees of freedom - actual infinity rather than "potential" infinity like in the computable case.
> 9 votes

---
Tags: computability, turing-machines, combinatorics
---


# Question
Title: Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem
The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we happily go from

$\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n)$

to

$\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n)$

considering only $n=2^k$. We assure ourselved that this step is valid -- that is, $T \in \Theta(T')$ -- because $T$ behaves "nicely". In general, we assume $n=b^k$ for $b$ the common denominator.

It is easy to construct recurrences which do not allow this simplification by using vicious $f$. For example, above recurrence for $T\\,$/$\\,T'$ with

$\qquad f(n) = \begin{cases} 1 &, n=2^k \\ n &, \text{else} \end{cases}$

will yield $\Theta(n)$ by using the Master theorem in the usual way, but there is clearly a subsequence that grows like $\Theta(n \log n)$. See here for another, more contrived example.

How can we make this "nicely" rigorous? I am quite certain that monotonicity is sufficient, but not even the simple Mergesort recurrence is monotone; there is a periodic component (which is dominated asymptotically). Is it enough to investigate $f$, and what are necessary and sufficient conditions on $f$ that ensure the Master theorem works?

# Answer
> 12 votes
Throughout this answer, we assume $f$ and $T$ are non-negative. Our proof works whenever $f = \Theta(g)$ for some monotone $g$. This includes your Mergesort example, in which $f=\Theta(n)$, and any function which has polynomial growth rate (or even $\Theta(n^a \log^b n)$).

Let's consider first the case that $f$ is monotone non-decreasing (we'll relax this assumption later). We concentrate on your sample recurrence $$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n). $$ This recurrence needs two base cases, $T(0)$ and $T(1)$. We make the assumption that $T(0) \leq T(1)$, which we also relax later on.

I claim that $T(n)$ is monotone non-decreasing. We prove by complete induction that $T(n+1) \geq T(n)$. This is given for $n = 0$, so let $n \geq 1$. We have $$ \begin{align\*} T(n+1) &= T(\lfloor (n+1)/2 \rfloor) + T(\lceil (n+1)/2 \rceil) + f(n+1) \\ &\geq T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n) = T(n). \end{align\*} $$ This implies that $$ T(2^{\lfloor \log\_2 n \rfloor}) \leq T(n) \leq T(2^{\lceil \log\_2 n \rceil}). $$ So if $T(2^m) = \Theta(T(2^{m+1}))$, we're done. This is always the case if the solution for powers of two is of the form $T(n) = \Theta(n^a \log^b n)$.

Now let's relax the assumption that $T(0) \leq T(1)$. Consider a new recurrence $T'$ defined in exactly the same way, only $T'(0) = T'(1) = \min(T(0),T(1))$. We can prove by induction that $T'(n) \leq T(n)$. Similarly, we can define a new recurrence $T''$ satisfying $T''(0) = T''(1) = \max(T(0),T(1))$, and then $T(n) \leq T''(n)$. Invoking the Master theorem, we see that $T'=\Theta(h)$ and $T''=\Theta(h)$ for the *same* function $h$, and so $T = \Theta(h)$ as well.

Now let's relax the assumption that $f$ is monotone. Suppose that $f = \Theta(g)$ for some monotone function $g$. Thus $cg(n) \leq f(n) \leq Cg(n)$ for some $c,C\>0$ and $n$ large enough. We assume for simplicity that $n=0$; the general case can be handled as in the previous paragraph. Again we define two recurrences $T',T''$ by replacing $f$ with $cg,Cg$ (respectively). Once again the Master theorem will give the same result (up to constant multiples), which is also identical (up to constant multiples) to what we would get by solving the original recurrence only on powers of two.

---
Tags: asymptotics, proof-techniques, recurrence-relation, master-theorem
---


title: Quadratic residue and integer factoring

text:
# Question
Title: Quadratic residue and integer factoring
I often read that deciding whether or not a number $r$ is a quadratic residue modulo $n$ is an interesting (and hard) problem from number theory (especially if $n$ is not prime).

I am looking at the following special case of this problem: Let $p$ and $q$ be two different prime numbers and $n:=pq$. Given $r$ between $1$ and $n$. Decide if there exists an $x\in\mathbb{Z}/n\mathbb{Z}$ such that $x^2\equiv r\pmod{n}$.

My question is: The functional version of this problem i.e. "Find such an $x$ as above" yields an randomized algorithm for integer factoring. So it is *very* interesting for practical reasons like "breaking RSA". Is there any such result for the decision version of this problem? If not, what are typical problems that let us think that deciding quadratic residuosity it is a hard problem?

And furthermore, is the special case I'm looking at really a special case? Or can I solve the general case with an arbitrary $n$ with an oracle for the decision problem above?

# Answer
> 5 votes
Tibor Jager and Jörg Schwenk show in The Generic Hardness of Subset Membership Problems under the Factoring Assumption that factoring reduces to distinguishing quadratic residues from numbers with Jacobi symbol 1, *for generic ring algorithms*. These are algorithms whose only "API" to integers are ring operations (addition, multiplication, subtraction, division), equality comparisons and generating a random element. They also show that the Jacobi symbol, which can be efficiently computed in polynomial time, has no efficient generic ring algorithm. So their result doesn't answer your question, other than implying that the answer isn't known.

---
Tags: cryptography, number-theory
---


title: HamCycle to HamPath reduction

text:
# Question
Title: HamCycle to HamPath reduction
I've seen a reduction that's done by adding another vertex to the graph and creating a path through that vertex.

Why do I need to add a vertex? Cant I just remove an edge? Lets say the graph with the HamCycle is G,s,t when removing the edge between s and t dont I get a path the goes through all the vertexes that's qualified as a Hamiltonian path?

# Answer
> 4 votes
First of all I think that the direction of the reduction of your question is from Hampath to Hamcycle (you prove the NP-hardness of Hamcycle reducing the NP-complete problem Hampath to it).

Now given an instance of Hampath: $G,s,t$:

1) there is an edge between $s$ and $t$
2) there is not an edge between $s$ and $t$

In both cases the extra node $u$ is needed in order to force $s,u,t$ to be consecutive nodes in the Hamiltonian cycle.

The new graph $G'$ with a new node $u$ and new edges $(s,u), (u,t)$ (in the first case you split the original edge) will have an Hamiltonian cycle iif the original graph $G$ has an Hamiltonian path from $s$ to $t$.

You can "play" with these two graphs:

---
Tags: complexity-theory, np-complete, reductions
---


title: Tiling of squares

text:
# Question
Title: Tiling of squares
**Motivation**: This question is motivated by my previous question . In that question, my statment of the uniqueness requirement is not interesting since it leads to easily computable function. I am interested in constructing uncomputable function from a simple combainatorial problem.

We want to tile $m\times m$-square using two types of tiles: $1 \times 1$-square tile and $2 \times 2$-square tile without overlapping. We require packing the maximum number of $2 \times 2$-squares while posiblliy leaving some of the $m \times m$-squares uncovered?

Let us define a function $f(n)$ that gives the size of largest tillable square using $n$ $1\times 1$-squares and maximum number of $2 \times 2$-squares.

Is this function computable? Is it computable if we use Trominos instead of $2 \times 2$-squares?

# Answer
> 4 votes
This function is (still) computable, by a subset of the reasoning in the previous question: No squares are tileable using $n=4k+2$ or $4k+3\ 1\times 1$ tiles; arbitrarily large squares are tileable using $n=4k\ 1\times 1$ tiles, and using $n=4k+1\ 1\times 1$ tiles and an arbitrary number of $2\times 2$ tiles, one can cover a $(2k+1)\times(2k+1)$ square but none larger. The results for $n\equiv 2,3\pmod 4$ are because no square can be congruent to those numbers mod 4; the result for $n\equiv 0\pmod 4$ is essentially trivial (pack the $1\times1$ tiles 4 at a time into $2\times2$ tiles). For the final case, just note that any tiling of a $(2t+1)\times (2t+1)$ square can only use $t^2\ 2\times2$ tiles, meaning that at least $4t+1$ squares are left over for the $1\times 1$ tiles - in other words, $n\geq 4t+1$, or seen the other way around, $f(n)\leq \frac{n+1}{2}$. Since this bound is acheivable, then the value is exactly $f(n)=\frac{n+1}{2}$.

For the case of trominos, either L or straight, your function $f()$ is ill-defined; the squares mod 6 are exactly 0, 1, 3, 4 so the number of $1\times 1$ blocks will have to be the same, but for any $n$ in the appropriate residue classes, arbitrarily large squares can be tiled. The core reason is simple: unlike the case where the 'extra' tiles are $2\times 2$, there's no 'squareness' or evenness constraint here on the number of extra tiles that can be placed. This means that from e.g. a tiling of a $5\times 5$ square one can then generate an $11\times 11$ square by abutting two edges with $5\times 6$ rectangles (made up of $2\times 3$ bricks, which are then made up of either the straight or ell pieces) and then putting a $6\times 6$ rectangle in the remaining corner; from this one can go on to build a $17\times 17$ square, etc. Since $6\times n$ rectangles are constructable for all $n\gt1$, any $k\times k$ square can be 'amplified' this way to get a $(k+6)\times(k+6)$ square. What's more, trying to force the tilings to be 'fault-free' probably won't be any help - it should be possible to use local changes to modify any of these tilings so there are no global faults.

Unfortunately, there are no relatively 'simple' tiling problems that are known to be undecidable, and while I wouldn't say there can't be any, they seem unlikely to me - there's just too much structure in the space of solutions to allow for undecidability. (Of course, one can transcribe Wang tiles into polyominos and get undecidability of arbitrary polyomino tiling that way, but the tiles in question are much more complicated than it sounds like you're after.)

---
Tags: computability, combinatorics
---


# Question
Title: Is $(aaaaa)^n aa (aaaaa)^n$ a regular language?
Is the language $\lbrace (aaaaa)^n aa (aaaaa)^n \mid n \in \mathbb{N} \rbrace$ regular? It looks like I need infinitely many states so it is not regular.

# Answer
The language consists of those strings that contain $5 n + 2 + 5 n = 10 n + 2$ symbols $a$ for some $n \in \mathbb{N}$, i.e., $$\lbrace(aaaaa)^n aa (aaaaa)^n \mid n \in \mathbb{N}\rbrace = \lbrace (aaaaaaaaaa)^n aa \mid n \in \mathbb{N} \rbrace.$$ It is regular because it is accepted by the automaton which has twelve states $s\_0, \ldots, s\_{11}$ with a starting state $s\_0$, accepting state $s\_2$, and transitions $s\_i \stackrel{a}{\longrightarrow} s\_{i+1}$ for each $i = 0, \ldots, 10$, and one more transition $s\_{11} \stackrel{a}{\longrightarrow} s\_0$. In essence, this automaton counts the number of letters modulo 10 and accepts if the answer is 2.
> 10 votes

# Answer
We can prove a more general theorem. The language $\\{ a^n : n \in A \\}$ is regular if and only if the set $A$ is eventually periodic, i.e. there exist $m$ and $k$ such that for all $n \geq m$, $n \in A$ iff $n+k \in A$.

Indeed, a language of this form is clearly regular. For the other direction, consider a DFA accepting the language. It has outdegree $1$ and so must consist of a path leading into a cycle. Given that representation, we see that it can be represented using an eventually periodic $A$.
> 6 votes

---
Tags: formal-languages, regular-languages
---


title: Bipartite graph question

text:
# Question
Title: Bipartite graph question
Assume you are given a bipartite graph $G = (U, V, E)$ and you are given an integer $n$. Assume also that for each $v \in V$, you are given two integers $v\_{min}$ and $v\_{max}$ (where $v\_{min} \le v\_{max}$).

The problem is to find a subset $U'$ of $U$ of size $n$ such that for each $v \in V$, the number of edges coming into $v$ from $U'$ is between $v\_{min}$ and $v\_{max}$.

Given a problem like this, can we determine efficiently whether there is a solution? And, if there is a solution, can we find one efficiently?

If we can't do so efficiently, is there an approximation algorithm?

# Answer
> 7 votes
Your problem is NP-hard, by reduction from set cover. Given an instance of set cover with universe $V$, sets $U$ and number $n$, draw an edge between a set and a point if the set contains the point. Let $v\_\min = 1$ and $v\_\max = |U|$. A subset $U'$ satisfies the $v\_\min,v\_\max$ constraints iff it is a set cover. So if there is a set cover $W$ of size $m \leq n$, you can complete it to some $U'$ of size $n$ by adding $n-m$ sets and get a solution to your problem. Conversely, any solution to your problem is a set cover of size $n$.

Set cover is also hard to approximate better than $\log n$ (under reasonable assumptions), and this carries over to your problem. Your problem could be much harder.

---
Tags: algorithms, graphs, bipartite-matching
---


title: Weak and strong completeness

text:
# Question
Title: Weak and strong completeness
What does a pseudo-polynomial algorithm tell us about the problem it solves? I don't see how running time improves if the algorithm is exponential in the input length and polynomial in the input value; so how do we explain this shift from exponential to polynomial?

# Answer
As it is stated in "Computers and Intractability: a Guide to the Theory of NP-Completeness" A pseudo-polynomial-time algorithm will display '**exponential behavior**' only when confronted with instances containing '**exponentially large**' numbers, which might be rare for the applications we are interested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time algorithm.”

You can consider knapsack as a good example of **weakly-Np Complete problem**. In this case the complexity of the dynamic programming solution is $O(nW)$ which is well in most **practical** cases.

It is known that there is no pseudo-polynomial time algorithm for **Strong NP-Complete** problems (like Steiner Tree) unless P=NP.
> 6 votes

# Answer
This answer pertains to *quasipolynomial* algorithms rather than *pseudopolynomial* ones.

A quasipolynomial algorithm tells us that the problem is probably not NP-hard. The (somewhat) commonly-believed Exponential Time Hypothesis (ETH) states that 3SAT on $n$ variables requires time $2^{\Omega(n)}$. Since 3SAT is in NP, the ETH implies that any NP-complete problem requires time $2^{n^{\Omega(1)}}$, which grows faster than quasipolynomial (assuming by the latter is meant $2^{\log^{O(1)} n}$).
> 1 votes

---
Tags: algorithms, complexity-theory, np-complete, pseudo-polynomial
---


# Question
Title: What use are groups, monoids, and rings in database computations?
Why would a company like Twitter be interested in algebraic concepts like groups, monoids and rings? See their repository at github:twitter/algebird.

All I could find is:

> Implementations of Monoids for interesting approximation algorithms, such as Bloom filter, HyperLogLog and CountMinSketch. These allow you to think of these sophisticated operations like you might numbers, and add them up in hadoop or online to produce powerful statistics and analytics.

and in another part of the GitHub page:

> It was originally developed as part of Scalding's Matrix API, where Matrices had values which are elements of Monoids, Groups, or Rings. Subsequently, it was clear that the code had broader application within Scalding and on other projects within Twitter.

What could this broader application be? within Twitter and for general interest?

---

It seems like composition aggregations of databases have a monoid-like structure.

Same question on Quora: What is Twitter's interest in abstract algebra (with algebird)?

---

I have math background but I'm not computer scientist. It would be great to have "real-world" uses of monoids and semi-groups. These are normally considered useless theoretical constructs, and ignored in many abstract algebra courses (for lack of anything interesting to say).

# Answer
The main answer is that by exploiting semi-group structure, we can build systems that parallelize correctly without knowing the underlying operation (the user is promising associativity).

By using Monoids, we can take advantage of sparsity (we deal with a lot of sparse matrices, where almost all values are a zero in some Monoid).

By using Rings, we can do matrix multiplication over things other than numbers (which on occasion we have done).

The algebird project itself (as well as the issue history) pretty clearly explains what is going on here: we are building a lot of algorithms for aggregation of large data sets, and leveraging the structure of the operations gives us a win on the systems side (which is usually the pain point when trying to productionize algorithms on 1000s of nodes).

Solve the systems problems once for any Semigroup/Monoid/Group/Ring, and then you can plug in any algorithm without having to think about Memcache, Hadoop, Storm, etc...
> 28 votes

# Answer
Monoids are ubiquitous in programming, just that most programmers don't know about them.

* Number operations like addition and multiplication.
* Matrix multiplication.
* Basically all collection-like data structures form monoids, where the monoidal operation is concatenation or union. This includes lists, sets, maps of keys to values, various kinds of trees etc.
* For a given type $A$ functions $A\to A$ together with the identity function on $A$ form $A$'s endomorphism monoid.

Some other operations don't form monoids but semi-groups. A good example is searching for the minimal element of a sequence of elements: $a\cdot b$ represents the minimum of $a$ and $b$ wrt some given ordering.

Because monoids are so general, they allow to write very generic functions. For example, folding over a data structure can be expressed as mapping every its element to a monoid and then using the monoidal operation to combine them to a single result.

Another nice and very general example is the generalization of exponentiation by squaring to monoids (or semi-groups). We can write a single function that computes $\underbrace{a\cdot\ldots\cdot a}\_{n-\mbox{times}}$ only in $O(\log n)$ operations. Applying it to different monoids we get:

* fast exponentiation of numbers;
* fast exponentiation of matrices (this can be used to compute Fibonacci numbers in $O(\log n)$ multiplications);
* fast method for building large finger trees, as appending one element takes $O(1)$ time but merging 2 trees takes $O(\log(\min(n\_1,n\_2)))$.
* etc.

For more examples see Examples of monoids/semigroups in programming.
> 11 votes

# Answer
One important problem in distributed file systems (**DFS**) is to generate files from distributed blocks. The area of Erasure code from information theory and Algebra (groups, rings, linear algebra,...) is used extensively in distributed fault tolerant file systems for example in HDFS RAID (Hadoop Based File System). Social network and Cloud companies are extensively based on DFS, so they need people who are master in Algebra and Erasure Code to design better and high performance systems (like Reed-Solomon codes, etc).

This is also good poster for their application (algebra) in cloud storage: Novel Codes for Cloud Storage
> 7 votes

# Answer
If your question is

> What are examples of groups, monoids, and rings in computation?

then one example I can think of off-hand is for path-finding algorithms in graph-theory. If we define a semiring with $+$ as $\min$ and $\cdot$ as $+$, then we can use matrix multiplication with the adjacency matrix to find all-pairs-shortest-path. This method is actually described in CLRS.

While this may seem only theoretical from an algebraic perspective it allows us to utilize very heavily optimized linear algebra libraries for graph problems. Combinatorial BLAS is one such library.
> 6 votes

# Answer
The set of all words over some finite alphabet together with concatenation forms the free monoid $(\Sigma^\*, \cdot)$. Therefore, the whole field of formal language can be viewed through the algebraic lense, and it is sometimes taught like this.

In return, considerations on formal languages have yielded the Earley parser which can be extend to parse on semirings. This is useful in natural language processing and other areas using stochastic models for (formal) languages.
> 4 votes

# Answer
> I have math background but I'm not computer scientist. It would be great to have "real-world" uses of monoids and semi-groups. These are normally considered useless theoretical constructs, and ignored in many abstract algebra courses (for lack of anything interesting to say).

There is rather too much interesting to say. However, it's more a topic of discrete math and combinatorics than for abstract algebra and analysis, at least for the less trivial topics. There is also the question how much you have to know about a certain topic before you can tell somebody else it would be an interesting mathematical topic related to monoids and semigroups. For example, I find the following topics (related to semigroups) interesting:

* finite semigroups and Krohn-Rhodes theory
* partial symmetries, inverse semigroups, groupoids and quasicrystals
* semirings and tropical geometry
* partial orders and Möbius functions
* submodular functions and (Dulmage-Mendelsohn like) decompositions

Do I know much about each of these topics? Probably not. There are also many more mathematical topics related to monoids and semigroups, some of them are more internal to semigroup theory itself (like Green's relations), others are more general and not specific to semigroups (universal semigroups, homomorphism and isomorphism theorems, quotient structures and congruences), but also important from a mathematical point of view. The topics I did cite above mostly have "real world" applications, but there are more related topics that also have "real world" applications.

---

The above is not an answer to the real question, but only addresses the "... are normally considered useless theoretical constructs ... for lack of anything interesting to say ..." remark. So I listed some "interesting" points, claimed that those mostly have "real world" applications, and now Hi-Angel requests a bit of info about those applications. But because "there is rather too much interesting to say," don't expect too much from that info: The Krohn-Rhodes theorem is a decomposition theorem for finite semigroups. Its applications involve the interpretation of the wreath product as a sort of composition (of transducers) in connection with the theory of automata and regular languages, and occurs in the classification of regular languages using pseudovarieties. Mark V Lawson: two tutorial lectures and background material contained (404 now) good material on Inverse Semigroups. The basis for their applications are their connection to the symmetric inverse semigroup, i.e. the set of all partial bijections on a set. One can also start with basic algebraic characterizations of inverse semigroups, but this approach risks to neglect the connections to partial orders which are important for many applications. Some day I will have to blog about a specific application of inverse semigroups as "hierarchy" used to compress semiconductor layouts. Applications of semirings have already been described in the other answers (and tropical geometry would take us far from computer science). Because monoids and semigroups are also related to partial orders, such nice topics like Möbius functions as described in Combinatorics: The Rota Way are also related. And then also topics from Matrices and Matroids for System Analysis like the Dulmage-Mendelsohn decomposition become related, which were one of my motivations to study lattice theory (and hidden hierarchical structures).
> 2 votes

---
Tags: reference-request, discrete-mathematics, database-theory, applied-theory, group-theory
---


# Question
Title: Looking for non-entry level implementation of foundational algorithms and data structures in python. where to look?
I'm an autodidact who works best with a mix of theory and implementation examples. I'm having a hard time finding resources on implementing algorithms and data structures in Python (2.7-3.X preferably). I found a text ...mastering basic algorithms in the python language but I find it to be far too introductory and thus cluttered with unnecessary prose, which makes it for me difficult to move efficiently over it. What I have in mind is a text or github gist or whatever really, that has some coded python imps of what I've determined to be foundational data-structures in algorithmic's(not to sure on the usage/conjugation of that). Specifically I'm looking for trees, traversal, dynamic and greedy algorithms and the like. If this question is a repeat, or adequately answered elsewhere, links are adequate replies.

# Answer
> 3 votes
David Eppstein has a bunch of algorithms implemented in Python in his PADS repository.

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: design of self-loops and final states in fsm
I am learning about automata and finite state machines. Consider the following automaton, that accepts the word 'ab', does not have to be infinite, just once:

alphabet: 'a','b' states: 1,2, 3 (3 is the final state and 1 is the initial state)

transitions:

```
state 1, symbol a, state 2
state 2, symbol b, state 3

```

First part of my questions:

Question 1. Is it required to add self-loops at 1 for 'b', and a self-loop for 'a' at 2?

Question 2. What about at state 3(final)? Should I add self-loops for 'a' and 'b'?

I basically need to know, how to design my final state. So that even if my alphabet was expanded (say a, b, c), and I have a 'dump' state, with the following transitions:

```
state 1, symbol a, state 2
state 1, symbol b or c, state dump

state 2, symbol b, state 3
state 2 symbol a or c, state dump

```

Question 3. Now from final state 3, should I add a transition to dump state, with symbol values a,b,c ???

Your assistance is much appreciated.

# Answer
> 0 votes
Your original automaton is fine, it accepts the singleton $\\{ab\\}$. Here is a pictorial representation:

In the above automaton it's implicit that given a state and a letter for which there is no arrow going out of that state, then the automaton "crashes". If you want to be complete, you can add a dead state that absorbs strings that don't belong in the language. Here is the complete automaton:

If you add self-loops at 1 and/or 2, you will change the language that the automaton accepts. Look at this:

The self-loop at 1 labeled with $b$ changes the language to $\\{ab, bab, bbab, bbbab, \dots\\}$.

---
Tags: finite-automata
---


# Question
Title: Running time of a nested loop with $\sum i \log i$ term
So I have the following pseudo-code:

```
Function(n):
for (i = 4 to n^2):
    for (j = 5 to floor(3ilog(i))):
        // Some math that executes in constant time

```

So far, I know that to find this i will be calculating

$\sum\_{i=4}^{n^2}\sum\_{j=5}^{3i \log\_{2}i}C$ where $C$ is a constant, but I am completely lost as to how to proceed past the first summation which, if I'm not mistaken, will give me $3C \cdot (\sum\_{i=4}^{n^2}(i \log\_{2}i) - 5(n^2 - 4))$, but from here I'm lost. I don't need exact running time, but the asymptotic complexity.

All help is greatly appreciated! I realize that this might be a duplicate, but I haven't been able to find a nested for loop problem of this nature anywhere...

# Answer
> 4 votes
$$F(n) = \sum\limits\_{i = 4}^{n^2} \sum\limits\_{j = 5}^{3i\log i}C = C\sum\limits\_{i = 4}^{n^2}(3i\log i - 4) = 3C\sum\limits\_{i = 4}^{n^2}i \log i - \Theta(n^2)$$

For asymptotic analysis, we can start the summation from $i = 1$ instead of $4$. Let

$\begin{align} T(n) &= \sum\limits\_{i = 1}^{n^2}i\log i = \sum\limits\_{i = 1}^{n^2}\log {i^i} \\ &= \log {1^1} + \log {2^2} + \log {3^3} + \dots + \log {(n^2)^{n^2}} \\ &\le n^2 \cdot \log (n^2)^{n^2} \ \ \text{(there are \\(n^2\\) terms)}\\ &= 2n^4 \log n \\ &= O(n^4 \log n) \end{align} $

Now, since $f(x) = x\log x$ is a continuous increasing function in $x \in \[1, \infty)$, you can verify that :
$\int\limits\_{1}^{n^2}x\log x \ dx \le \sum\limits\_{x = 1}^{n^2}x\log x \ \ $ (changing $i$ to $x$ simply because $x$ looks better when integrating).

According to Wolfram, $\int\limits\_{1}^{n^2}x\log x \ dx = \frac{1}{4}\left(n^4 \log \left({\frac{n^4}{e}}\right) + 1\right) = n^4 \log \left({\frac{n}{e}}\right) + \frac{1}{4}$

Therefore, $\sum\limits\_{x = 1}^{n^2}x\log x = \Omega(n^4\log n)$.

Combining the upper and lower bounds, we have $T(n) = \Theta(n^4\log n)$

Overall, $F(n) = \Theta(n^4\log n) - \Theta(n^2) = \Theta(n^4 \log n)$.

So, your loops have complexity $\Theta(n^4 \log n)$.

**Remarks**:
1. You can show the lower and upper bounds in a similar way by observing that: $\int\limits\_{1}^{n^2}x\log x \ dx \le \sum\limits\_{x = 1}^{n^2}x\log x \le \int\limits\_{0}^{n^2}(x+1)\log {(x+1)} \ dx$
2. For the above inequalities, you can use the method of Riemann sum (use the left and the right Riemann sums to see the two bounds). Draw unit-width rectangles on an increasing function to see these bounds.
3. I have done some implicit simplifications, such as just ignoring the constant $3C$ term, or starting the summation from $1$ instead of $4$ since we are dealing with $\Theta$. I have also made the common but slight abuse of notation when equating or subtracting $\Theta$ terms, without affecting the answer.

# Answer
> 1 votes
Let $N=n^2$, let's compute the sum $S=\sum\limits\_{i=1}^{N} i \ln i=\sum\limits\_{i=1}^{N} \ln i^i$

$S=\ln 1 + \ln 2^2 + \ln 3^3 + \dots+\ln N^N=\ln (1\times 2\times 2 \times 3 \times 3 \times 3 \times \dots)$

$=\ln (N!\times N!/2!\times N!/3! \times \dots)=N\ln N! - \Theta(1)$

Using Stirling's formula we get:

$S=N(N\ln N - N + O(\ln N)) - \Theta(1) = \Theta(N^2\ln N)$

Now replace $N$ by $n^2$:

$S=\Theta(n^4\ln n^2)=\Theta(n^4 \ln n)$

---
Tags: time-complexity, algorithm-analysis, asymptotics
---


# Question
Title: Which non-regular languages are in $AC^0$?
For example, I know that the non-regular language $a^nb^n$ is in $AC^0$. I would like to know more examples like this.

# Answer
Languages in $AC^0$ can be more complicated than naive intuition might suggest.

* Obviously, $AC^0$ contains $\\{a^n b^n c^n\\}$, which is non-context-free.
* Every unary language is in nonuniform $AC^0$; for example, the halting problem expressed in unary.
* Addition can be implemented in $AC^0$ with a carry-lookahead adder. Here the input is $2n$ bits representing two numbers, and the output contains $n+1$ wires (equivalently, each output bit can be realized in $AC^0$)
* Multiplexing: $\\{w x: |w|=2^n, |x|=n, w\[x\] = 1\\}$ is in $AC^0$.

A multiplexer is a function on $2^n+n$ variables which outputs the value of one of $2^n$ variables, where the index is determined by the $n$ variables. (The same holds if the index is written in unary.)
* Computation of 3SAT formulas is in $AC^0$.

The input consists of $n$ variables, followed by some clauses, each one contains three literals, where each literal is an index of the variable (unary or binary, does not matter) and a bit indicating possible negation. You can evaluate the literals with multiplexers and then add a layer of ORs and then a big AND on top.
* $AC^0$ does not contain majority, but it contains approximate majority: a function that is equal to majority if the output is $\geq \frac{1}{2}+ \varepsilon$ zeroes or ones. See "Approximate Counting with Uniform Constant-Depth Circuits" by Ajtai.

$AC^0$ is closed under logical operations, concatenation and composition, so you can combine above examples. Now you should feel some respect for $Parity \notin AC^0$ and other circuit lower bounds!
> 10 votes

---
Tags: complexity-theory, regular-languages, circuits
---


title: Meaning of the Halting problem

text:
# Question
Title: Meaning of the Halting problem
The Halting Problem is defined as:

$H\_{TM} = \\{ \langle M, w \rangle \mid \text{\\(M\\) halts on input \\(w\\)}\\}$

I'm not sure what it means. Is $H\_{TM}$ a collection of Turing Machines such that all of them accept/reject the word $w$? Is that a specific word? Or does that mean any word in their alphabet?

Thanks

# Answer
> 5 votes
The set (or language if you will) $H\_{TM}$ is a set of *pairs* $(M,w)$ where $w$ is any string of your alphabet and $M$ is a Turing machine, and $M$ halts with $w$ as input.

This means that a pair $P = (M,w)$ is in the set $H\_{TM}$ if and only if $M(w) \downarrow$.

*Deciding* this set is however not possible. There is no Turing machine that accepts this language and nothing more. This is a version of the halting problem (hence the $H$).

# Answer
> 5 votes
We first choose an alphabet of symbols that our Turing machines can read and write on the tapes. Typically we have three symbols: $0$, $1$, and "empty". A *word* is a finite sequence of symbols.

If $u$ and $v$ are words we can form a new word $\langle u, v \rangle$ which represents the two words put together (this requires some coding so that we can tell where one words stops and the other begins).

A Turing machine can be be described by a word.

Like in all decidability problems, **$H\_{TM}$ is a set of words**. More precisely, $H\_{TM}$ contains all those words of the form $\langle M,w \rangle$ where $M$ is a Turing machine, $w$ is any word, and $M$ halts when we run it with input $w$.

# Answer
> 1 votes
here is a simple/informal definition of the halting problem with minimal symbolic/mathematical language. first, consider the Turing machine. Turing machines solve different problems based on (programming via) their state table.

now, the state table of any Turing machine itself can be encoded as a string, just like any inputs to a Turing machine. now consider a hypothetical machine ${TM}\_H$ which accepts an encoding pair of a state table of a machine $M$, and an input string $w$: $\langle M, w \rangle$. suppose this $TM\_H$ accepts the input iff (if and only if) machine $M$ halts on input $w$. by Turing's famous halting problem proof (1936), ${TM}\_H$ cannot exist, ie this "problem" is uncomputable.

the $H\_{TM}$ you describe is the description of this same problem in terms of set/language membership. a string is in the set $H\_{TM}$ iff $M$ halts on $w$.

---
Tags: computability, turing-machines
---


# Question
Title: Find the median of a list of sorted arrays
**Input:** A set of $\ell$ arrays $A\_i$ (of numbers).
The elements within each array are in sorted order, but the set of arrays is not necessarily sorted. The arrays are not necessarily the same size. The total number of elements is $n$.

**Output:** The $k$th smallest element out of all elements in the input.

What's the most efficient algorithm for this problem?

Is it possible, for example to achieve a running time of $O(\ell + \log n)$?

# Answer
You can do it in $O(l + k \text{ log } l)$ time and $O(l)$ extra space as follows:

1. Build a binary heap with one entry for each of the arrays. The key for entry $i$ is the smallest element in array $A\_i$. This takes $O(l)$ time.
2. Select the smallest entry from the heap and remove it (taking $O(\text{log } l$) time). Add that entry back to the heap using the next smallest entry in the relevant array as its key (again $O(\text{log } l)$ time).
3. Do the previous step $k$ times. The last element you remove from the heap is your answer.

If you replace the binary heap with a Fibonacci heap, I think this gets you down to amortized $O(l + k)$ time, but in practice it'll be slower than the binary heap unless $l$ is HUGE.

I suspect that the Fibonacci heap bound is optimal, because intuitively you're going to have to inspect at least $k$ elements to find the $k$th smallest one, and you're going to have to inspect at least one element from each of the $l$ arrays since you don't know how they're sorted, which immediately gives a lower bound of $\Omega(\text{max}(k, l)) = \Omega(k + l)$.
> 5 votes

# Answer
Here is a randomized $O(\ell\log^2 n)$ algorithm. It can probably be derandomized using the same trick used to derandomize the usual quickselect.

We emulate the classical quickselect algorithm. In each phase, you pick a pivot and calculate how many elements are below it, in $O(\ell\log n)$, using binary search in each list. Then you remove elements on the wrong side, and repeat. The process ends after $\log n$ iterations in expectation.
> 5 votes

# Answer
This seems to be resolved by the paper Generalized selection and ranking (Preliminary Version) by Frederickson and Johnson in STOC '80.

They give upper and lower bounds of: $\Theta(\ell + \sum\_{i=1}^\ell \log|A\_i|)$ which turns out to be $\ell \log n$ for most array size distributions.

The actual algorithm to achieve the upper bound is apparently given in a previous paper: *Optimal algorithms for generating quantile information in X+Y and matrices with sorted columns*, Proc. 13th Annual Conference on Information Science and Systems, The Johns Hopkins University (1979) 47-52.
> 1 votes

# Answer
An $\ell$-way merge takes time $\Theta(n \log \ell)$ (use an efficient way to represent a priority queue of the head elements in each list), then you pick the $k$-th element in constant time. I think this is discussed in Knuth's "Sorting and searching" for sorting. Getting the smallest (or largest) clearly takes $\Theta(\ell)$, for an unsorted array it is $O(n)$ IIRC.

Please describe your algorithm.
> 0 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Can one have a condition like this in semidefinite programming?
Is it possible to have the following condition in a semidefinite programming as a constraint?

$ M= \left\[ {\begin{array}{cc} a & \sqrt{u} \\ \sqrt{u} & b \\ \end{array} } \right\] \geq 0$

where $\geq 0$ means positive semidefinite.

# Answer
> 5 votes
Assuming that *a*, *b*, and *u* are real variables in your semidefinite program, the answer is negative.

The important fact here is that each constraint in a semidefinite program defines a convex set. Your condition cannot be written as a constraint in a semidefinite program because the set of points (*a*, *b*, *u*) ∈ ℝ3 that satisfy the condition is not convex. I suggest that you try to prove that this set is indeed not convex, but here is a proof (put the mouse cursor in the box below to show the proof):

> Proof: (*a*, *b*, *u*) = (1, 1, 1) and (*a*, *b*, *u*) = (3, 3, 9) satisfy the condition, but their midpoint (*a*, *b*, *u*) = (2, 2, 5) does not satisfy the condition.

---
Tags: optimization
---


title: Intuition about decidability

text:
# Question
Title: Intuition about decidability
Given a language, how do you go about deciding if it's decidable or not? For example:

Given a DFA $A\_0$ and a TM $M\_0$

$L\_1 = \\{ \langle M \rangle \\, | \\, M \mbox{ is a TM and }L(M) = L(A\_0) \\}$

$L\_2 = \\{ \langle A \rangle \\, | \\, A \mbox{ is a DFA and }L(A) = L(M\_0) \\}$

What's the intuition/process of figuring out if $L\_1$, $L\_2$ are decidable or not?

This is not homework, $L\_1$ is not decidable and $L\_2$ is decidable, but I have not idea why, and how to solve this problem and problems similar to it. If you could explain to me the process of doing that you will help a lot.

# Answer
> 6 votes
For the first *undecidable* language $L\_1$ you can apply the Rice's theorem:

**Theorem (Rice’s Theorem)**: Let L be a language of the form

$L = \\{ \langle M \rangle | L(M)\mbox{ has some property }P\\}$,where

1. P is non-trivial, i.e. there exist at least one machine M such that $\langle M \rangle \in L$, and at least one machine $M$ such that $\langle M \rangle \notin L$.
2. P is indeed a property of the language of TMs, i.e. whenever $L(M\_1) = L(M\_2)$, we have $\langle M\_1 \rangle \in L$ if and only if $\langle M\_2 \rangle \in L$.

Then L is undecidable.

You can pick a Turing machine that decides $A\_0$ and one that decides $\overline{A\_0}$, so $L\_1$ asserts a nontrivial property of $\langle M \rangle$, and so it is undecidable.

For the second *decidable* language $L\_2$ the machine $M\_0$ is *fixed* (it is not part of the language). So $L(M\_0)$ is regular or it is not regular. If it is not regular then $L\_2 = \emptyset$ (trivially decidable). If $L(M\_0)$ is regular then there is a DFA $A\_{M\_0}$ such that $A\_{M\_0} = L(M\_0)$ and the language $L\_2$ becomes:

$L\_2 = \\{ \langle A \rangle | L(A) = L(A\_{M\_0}) \\}$

but the equivalence of two DFAs is decidable, so $L\_2$ is decidable.

# Answer
> 0 votes
just looked this up in Hopcroft/Ullman, *Introduction to Automata Theory, Languages, and Computation.* $L\_2$ seems to reduce to the question "is $L=R$ where $R$ is a given regular set?". on p281 the table states this is undecidable if $L$ is an r.e. set, ie recursively enumerable, ie a TM.

---
Tags: turing-machines, undecidability
---


# Question
Title: Don Knuth and MMIXAL vs. Chuck Moore and Forth -- Algorithms and Ideal Machines -- was there any cross-pollination / influence in their ideas / work?
**Question:**

**To what extent is it known (or believed) that Chuck Moore and Don Knuth had influence on each other's thoughts on ideal machines, or their work on algorithms?**

I'm interested in citations, interviews, articles, links, or any other sort of evidence. It could also be evidence of the form of A and B here suggest that Moore might have borrowed or influenced C and D from Knuth here, or vice versa. (Opinions are of course welcome, but references / links would be better!)

**Context:**

Until fairly recently, I have been primarily familiar with Knuth's work on algorithms and computing models, mostly through TAOCP but also through his interviews and other writings.

However, the more I have been using Forth, the more I am struck by both the power of a stack-based machine model, and the way in which the spareness of the model makes fundamental algorithmic improvements more readily apparent.

A lot of what Knuth has done in fundamental analysis of algorithms has, it seems to me, a very similar flavour, and I can easily imagine that in a parallel universe, Knuth might perhaps have chosen Forth as his computing model.

That's the software / algorithms / programming side of things.

When it comes to "ideal computing machines", Knuth in the 70s came up with the MIX computer model, and then, collaborating with designers of state-of-the-art RISC chips through the 90s, updated this with the modern MMIX model and its attendant assembly language MMIXAL.

Meanwhile, Moore, having been using and refining Forth as a language, but using it on top of whatever processor happened to be in the computer he was programming, began to imagine a world in which the efficiency and value of stack-based programming were reflected in hardware. So he went on in the 80s to develop his own stack-based hardware chips, defining the term MISC (Minimal Instruction Set Computers) along the way, and ending up eventually with the first Forth chip, the MuP21.

Both are brilliant men with keen insight into the art of programming and algorithms, and both work at the intersection between algorithms, programs, and bare metal hardware (i.e. hardware without the clutter of operating systems).

Which leads to the question as headlined...

**Question: To what extent is it known (or believed) that Chuck Moore and Don Knuth had influence on each other's thoughts on ideal machines, or their work on algorithms?**

# Answer
> 9 votes
There is some evidence: This paper was presented at the ACM SIGPLAN History of Programming Languages Conference (HOPL II, April, 1993), co-authored by myself, Chuck, and Don Colburn, an erstwhile colleague now unfortunately deceased. It references, in turn, a very early work that Chuck wrote when Forth was in what might be called an "alpha" form, "Programming a Problem-oriented Language".

I worked with Chuck from 1970 until 1982, when he left FORTH, Inc. to pursue chip-level implementations of Forth. I know that he referenced Knuth's books and papers for specific algorithms from time to time, but do not believe Knuth influenced the design of Forth in any way. In the time I worked with him, the two men never met. Whether Knuth was aware of Forth or of Chuck I cannot say.

# Answer
> 2 votes
A 60 response thread on comp.lang.forth (Knuth, MMIX & Forth) provides an interesting contrast between Charles Moore's Forth / stack machines in general and Knuth's MIX/MMIX and register machines in general.

The takeaway is that Knuth's thinking was driven by other objectives (predictable run time, representing the majority of computing architectures, abstracting away specific constraints into a 'super-machine') rather than those that drive Forth and stack machines (simplicity of design, minimality, realizability).

So Knuth pursued register designs with MIX and doubled-down on register designs (256 of them) with MMIX.

The following comments are highlighted:

* foxchip (Jeff Fox) (#3, #7 in the thread)
* Anton Ertl (#14, #41),
* Rick Hohensee (#17, #29),
* Bernd Paysan (#30, #39)

---
Tags: programming-languages, history
---


# Question
Title: Can every algorithm's running time be expressed as $\Theta(f(n))$?
That is, can the running time of every algorithm $A$ be written as $O(f\_A(n))$ and $\Omega(f\_A(n))$, for the same function $f\_A$?

# Answer
> 12 votes
The best case running time and the worst case running time on inputs of length $n$ can each be expressed in this way (as can any function of $n$), however, the two measures do not need to coincide. Details follow.

The running time of an algorithm is not a function only of input size $n$ but a function of the input and there are various running time measure that you can define as functions of $n$. You can define $f\_A(n)$ as the worst case (=largest) running time over inputs of size $n$ and $g\_A(n)$ as the best case (=smallest) running time over inputs of size $n$. Alex's argument is basically that $f\_A(n) = \Theta(g\_A(n))$ is not true for every algorithm $A$. The big-oh, big-omega and big-theta notations are used to denote the growth rate of a function as its argument goes to infinity - **by itself $\Omega()$ doesn't say whether you are talking about worst case running time or best case running time, and neither does $O()$**. So for the insertion sort you have:

* $f\_A(n) = \Theta(n^2)$ because you never need more than $O(n^2)$ steps to finish sorting and for each $n$ there is an input (reverse order) for which the algorithm takes at least $C n^2$ time for some constant $C$.
* $g\_A(n) = \Theta(n)$ because for each $n$ there is an input (sorted array) for which insertion sort runs in linear time and of course you need at least linear time to read the array.

And of course $f\_A(n) = \Theta(f\_A(n))$ and $g\_A(n) = \Theta(g\_A(n))$. However, $f\_A$ and $g\_A$ need not be monotonically increasing, they can oscillate infinitely often.

If you feel comfortable with all that you might check this discussion too: http://blog.computationalcomplexity.org/2005/01/big-omega.html

# Answer
> 4 votes
To show that Sasho's answer doesn't just hold for pathological algorithms, here's an example.

Consider a factorization algorithm that (1) tests whether a number $N$ is prime, (2) checks whether $N$ is divisible by small primes, (3) uses a factorization algorithm that is superpolynomial (such as all known ones).

In the cases where $N$ is prime or $N$ only has small prime factors, the algorithm runs in polynomial time in the input size $\log N$. For the hardest numbers to factor, the best known algorithm runs in time $2^{\Omega(\log^{1/3} N)}$, much slower.

# Answer
> 2 votes
No. For some inputs an algorithm can run faster or slower.

For instance, insertion sort can run in $O(n)$ time when the input array is already sorted but it requires $\Omega(n^2)$ time for arrays in reversed order.

# Answer
> 2 votes
Yes. If your alphabet $\Sigma$ is finite then the number of words of length $n$ is finite for every $n \in \mathbb{N}$.

This means that if you have an algorithm A, you can define $f\_A$ as being $f\_A(n) = \max\_{w}t(A(w))$ where the $\max$ is taken over all strings of length $n$ and $t(A(w))$ is the time measure of $A$ run on input $w$. The worst case complexity of $A$ is then $\Theta(f\_A)$.

You can define it similarly for average and best case by taking respectively average and minimum of all time measures.

# Answer
> 1 votes
As a simple proof-by-contradiction take a look at any algorithm who's complexity depends on more than one variable, e.g.: $\mathcal{O}(nk)$.

In such a case it is rarely possible to express running time as $\mathcal{O}\big( f(n) \big)$.

# Answer
> 1 votes
Consider the following problem:

1. Input: a list $l$ of integers of length $n$ and an integer $m$.
2. Output: a list $l'$ containing the elements of $l$ in ascending sorted order if $n$ is even, or a Boolean value indicating whether $m$ is contained in $l$ if $n$ is odd.

Consider the following algorithm:

```
if n % 2 = 0 return sort(l)
else if n % 2 = 1 return search(l, m)

```

The best-case behavior of this is that $n$ is odd, in which case the lower bound is $\Omega(n)$ (assuming linear search); the worst-case behavior is when $n$ is odd, in which case the upper bound is $O(n \log n)$. So the "universal" case of this algorithm does not have a $\Theta$ bound.

Note that the best and worst cases of this algorithm do have $\Theta$ bounds. Bounds apply to cases, not to algorithms (when we apply bounds to algorithms directly, a case is usually understood; often we mean the worst case, but sometimes - as in this example - we mean a sort of "universal" case considering all inputs without weighting).

---
Tags: algorithms, time-complexity
---


# Question
Title: Definition of Strongly Parsimonious Reduction
There is a well known definition of **parsimonious reduction**.

The standard definition of parsimonious reduction is very intuitive. It simply means that the two problem have the same number of solutions, when on input of one of them we applied function $f$.

We say there is a parsimonious reduction from #A to #B if there is a polynomial time transformation $f$ such that for all $x$, $|\\{y,(x, y) \in A\\}| = |\\{z : (f(x), z) \in B\\}|$.

I am interested in definition of **strongly parsimonious reduction**.

The only definition I found:

"Strongly parsimonious reduction of $R'$ to $R$ is a parsimonious reduction $g$ that is coupled with an efficiently computable 1-1 mapping of pairs $(g(x), y) \in R$ to pairs $(x, h(x, y)) \in R'$ (i.e., $h$ is efficiently computable and $h(x, ·)$ is a 1-1 mapping of $R(g(x))$ to $R'(x)$). For technical reasons, we also assume that $|g(x)| ≥ |x|$ for every $x$."

The problem is I simply don't understand what this definition means. I tried to separate it to smaller block, but so far with no success. According to the definition there are two function $g(x)$ and $h(x,y)$ are they are applied simultaneously to two different problem $R$ and $R'$. How the usages of two function can be explained. What is the difference between two reduction, parsimonious reduction and strongly parsimonious reduction.

I would appreciate any help in understanding the definition of strongly parsimonious reduction.

# Answer
> 9 votes
A search problem is defined by a relation like $R$. The task is given an input $x$ find a solution $y$ s.t. $R(x,y)$ is true.

A counting problem is defined as counting the number of solutions of a search problem, i.e. given an input $x$ we want to compute the number of $y$s s.t. $R(x,y)$ holds. The counting problem associated with search problem $R$ is denoted by $\\#R: \Sigma^\* \to \mathbb{N}$, $x \mapsto \\#y: R(x,y)$.

A parsimonious reduction $f$ between counting problems only needs to preserve the number of $y$s, i.e. for all $x$,

$$\\#y:R(x,y) = \\#z:S(f(x),z)$$

A strongly parsimonious reduction has an the extra property that you mentioned. The meaning of the property should become clear if you look at it in the following way:

> Assume that we want to use the search problem $S$ to solve the search problem $R$.
> On an input $x$ for $R$, we first compute $g(x)$ which is an input for $S$.
> Then we use $S$ to find an $S$-solution $y$ for $g(x)$, i.e. $(g(x),y)\in S$.
> Finally we compute $h(x,y)$ to obtain an $R$-solution for $x$.

Now if we want to preserve the number of solutions between these two search problems, we can make sure that for every $x$, the function $h(x,\cdot)$ that computes an $R$-solution for $x$ from an $S$-solution $y$ for $g(x)$ is a bijection.

The difference should be clear now: not only the number of $R$-solutions for $x$ and $S$-solutions for $g(x)$ are equal, there is an *efficient* bijection between those solutions.

---
Tags: complexity-theory, reductions
---


# Question
Title: Is the ambiguity of a regular tree grammar decidable?
Is there an algorithm which decides whether a regular tree grammar $G$ is ambiguous, i.e. there exists a tree $t\in L(G)$ which can be parsed by the grammar in more than one ways, using only leftmost derivations?

Is there a proof available about the decidability, or a cite to a paper which proposes such an algorithm?

# Answer
Start by considering regular *string* grammars. We can determine whether one such grammar $G$ is ambiguous by constructing the intersection of the grammar with itself, with a direct product construction. The nonterminals are pairs $(A,B)$ of nonterminals from the original string grammar $G$. The new grammar of course also derives the original language $L(G)$, but the new grammar has a nonterminal $(A,B)$ with $A\neq B$ in a succesful derivation, iff $G$ is ambiguous. It is decidable whether any given nonterminal occurs in a succesful derivation, so ambiguity is decidable for regular grammars.

The same is true, mutatis mutandis, for regular tree grammars.
> 3 votes

---
Tags: formal-languages, computability, formal-grammars, ambiguity, tree-grammars
---


# Question
Title: What do time complexity reductions prove?
I may have missed something in my classes - but with $A\leq\_{P}B$... Does this show that, if $A\in \textbf{NP-Complete}$, that $B\in \textbf{NP}$ or $B\in \textbf{NP-Complete}$?

Or maybe I got things backwards. If $A$ is polynomial-time-reducable to $B$, and $B$ is $\textbf{NP}$-complete, does that make $A$ $\textbf{NP}$ or $\textbf{NP}$-complete?

# Answer
> 4 votes
$A \leq\_p B$ denotes that you can reduce $A$ to $B$ in polynomial time. That is, you can always transform an instance of $A$ to an instance of $B$ and you do this in polynomial time. Now if you have a polynomial time algorithm for solving an instance of $B$, you also have a polynomial time algorithm for solving an instance of $A$, clearly.

To show that $C$ is $\mathsf{NP}$-complete, you need two conditions to hold. First, $C$ must be in $\mathsf{NP}$. Second, every problem in $\mathsf{NP}$ is reducible to $C$ in polynomial time.

# Answer
> 4 votes
If $A\leq\_{P}B$ and $A\in \textbf{NP-Complete}$, then $B\in \textbf{NP}-Hard$. $NP-Hard$ is a class of problems that are "**at least as hard as the hardest problems in NP**". (Image is from Wikipedia)

---
Tags: complexity-theory, terminology, reductions
---


title: Polynomial time reductions

text:
# Question
Title: Polynomial time reductions
I'm having a very hard time understanding what's what.

$$L\_{1}\leq\_{p}L\_{2}$$

If $L\_2$ is stated to be in $\textbf{NP}$, is it necessarily true that $L\_1$ is $\textbf{NP}$-Complete? I need to show the following for an assignment, but I'm having a dispute with a fellow student because he claims that I can't claim that $L\_1$ is $\textbf{NP}$-Complete...

> Suppose that $L\_1\leq\_p L\_2\leq\_p L\_3$. Also suppose that $L\_3$ is in $\textbf{NP}$. Explain how to solve $L\_1$ deterministically in exponential time.

I say (and I could be wrong - and that's a strong possiblity since I have very little understanding of this material) that since $L\_3$ is in $\textbf{NP}$, $L\_2$ also has to be in $\textbf{NP}$, and so therefore $L\_1$ has to be in $\textbf{NP}$. And if that's the case, then $L\_1$ can easily be converted to a deterministic algorithm through a breadth first search through the non-deterministic computation tree. Is there something I'm missing?

# Answer
You asked two questions. What you are missing is that those two questions are unrelated.

Question 1:

> $$L\_{1}\leq\_{p}L\_{2}$$
>
> If $L\_2$ is stated to be in $\textbf{NP}$, is it necessarily true that $L\_1$ is $\textbf{NP}$-Complete?

No. Consider the case where *L*1 and *L*2 are the same easy problem.

Question 2:

> I need to show the following for an assignment, but I'm having a dispute with a fellow student because he claims that I can't claim that $L\_1$ is $\textbf{NP}$-Complete...
>
> > Suppose that $L\_1\leq\_p L\_2\leq\_p L\_3$. Also suppose that $L\_3$ is in $\textbf{NP}$. Explain how to solve $L\_1$ deterministically in exponential time.
>
> I say \[…\] that since $L\_3$ is in $\textbf{NP}$, $L\_2$ also has to be in $\textbf{NP}$, and so therefore $L\_1$ has to be in $\textbf{NP}$. And if that's the case, then $L\_1$ can easily be converted to a deterministic algorithm through a breadth first search through the non-deterministic computation tree. Is there something I'm missing?

There is nothing wrong with your proof. (Okay, I would not call the exponential-time simulation of a nondeterministic polynomial-time Turing machine “breadth-first search,” but that is a separate issue.) As your fellow student said, it is true that you cannot claim that *L*1 is NP-complete, and indeed *you have never claimed that *L*1 is NP-complete*, so your proof for Question 2 does not contradict the answer to Question 1.
> 7 votes

---
Tags: complexity-theory, terminology, np-complete, reductions
---


# Question
Title: Concrete understanding of difference between PP and BPP definitions
I am confused about how **PP** and **BPP** are defined. Let us assume $\chi$ is the characteristic function for a language $\mathcal{L}$. *M* be the probabilistic Turing Machine. Are the following definitions correct:
$BPP =\\{\mathcal{L} :Pr\[\chi(x) \ne M(x)\] \geq \frac{1}{2} + \epsilon \quad \forall x \in \mathcal{L},\ \epsilon \> 0 \\}$
$PP =\\{\mathcal{L} :Pr\[\chi(x) \ne M(x)\] \> \frac{1}{2} \\}$

If the definition are wrong, please try to make minimal change to make them correct (i.e. do not give other equivalent definition which use counting machine or some modified model). I can not properly distinguish the conditions on probability on both the definitions.

Some concrete examples with clear insight into the subtle points would be very helpful.

# Answer
> 10 votes
That looks correct to me. The difference between BPP and PP is that for BPP the probability has to be greater than $1/2$ *by a constant*, whereas for PP it could be $1/2+ 1/2^n$. So for BPP problems you can do probability amplification with a small number of repetitions, whereas for general PP problems you can't.

# Answer
> 12 votes
Vor's answer gives the standard definition. Let me try to explain the difference a bit more intuitively.

Let $M$ be a bounded error probabilistic polynomial-time algorithm for a language $L$ that answers correctly with probability at least $p\geq\frac{1}{2}+\delta$. Let $x$ be the input and $n$ the size of the input.

**What distinguishes an arbitrary $\mathsf{PP}$ algorithm from a $\mathsf{BPP}$ algorithm is the *positive gap* between the probability of accepting $x\in L$ and the probability of accepting $x\notin L$.** The essential thing about $\mathsf{BPP}$ is that the gap is at least $n^{-O(1)}$. I will try to explain why this distinction is significant and allows us to consider $\mathsf{BPP}$ to be considered efficient algorithms (even conjectured to be equal to $\mathsf{P}$) whereas $\mathsf{PP}$ is considered inefficient (actually $\mathsf{PP}$ contains $\mathsf{NP}$). All of this comes from this gap.

Let's start by looking at $\mathsf{PP}$ more carefully.

Note that if an algorithm uses at most $r(n)$ random bits during its execution and the error probability is smaller than $2^{-r(n)}$ then error probability is actually $0$, there cannot be any chose of random bits that will make the algorithm answer incorrectly.

Furthermore, an algorithm with running time $t(n)$ cannot use more than $t(n)$ random bits, so if a probabilistic algorithm's error with worst-case running-time $t(n)$ is better than

With a similar argument we can show that the case where the difference between the probability of accepting an $x\in L$ and the probability of accepting an $x\notin L$ is too small is similar to the case where we don't have almost no difference as in $\mathsf{PP}$ case.

Let's now move towards $\mathsf{BPP}$.

In probabilistic algorithms, we can boost the probability for correctly answering. Let's say we want to boost the correctness probability to $1-\epsilon$ for say error probability $\epsilon=2^{-n}$ (exponentially small error).

The idea is simple: run $M$ several times and take the majority's answer.

How many times should we to run $M$ to get the error probability to be at most $\epsilon$? $\Theta(\delta^{-1} \lg \epsilon)$ times. The proof is given at the bottom of this answer.

Now let's take into the consideration that the algorithms we are discussing need to be polynomial-time. That means that we cannot run $M$ more than polynomially many times. In other words, $\Theta(\delta^{-1} \ln \epsilon) = n^{O(1)}$, or more simply

$$\delta^{-1} \lg \epsilon = n^{O(1)}$$

This relation categorizes the bounded error probabilistic algorithms into classes depending on their error probability. There is no difference between the error probability $\epsilon$ being being $2^{-n}$ or a positive constant (i.e. doesn't change with $n$) or $\frac{1}{2}-n^{O(1)}$. We can get from one of these to the other ones while remaining inside polynomial time.

However if $\delta$ is too small, say $0$, $2^{-n}$, or even $n^{-\omega(1)}$ then we don't have a way of boosting the correctness probability and reducing the error probability sufficiently to get into $\mathsf{BPP}$.

**The main point here is that in $\mathsf{BPP}$ we can efficiently reduce the error probability exponentially so we are almost certain about the answers and that is what makes us consider this class of algorithms as efficient algorithms. The error probability can be reduced so much that a hardware failure is more likely or even a meteor falling on the computer is more likely than making an error by the probabilistic algorithm.**

**That is not true for $\mathsf{PP}$, we don't know any way of reducing the error probability and we are left *almost* as if we are answering by throwing a coin to obtain the answer (we are not completely, the probabilities are not half and half, but it is very close to that situation).**

---

This section gives the proof that to obtain error probability $\epsilon$ when we start with an algorithm with gap $(\frac{1}{2}-\delta,\frac{1}{2}+\delta)$ we should run $M$ $\Theta(\delta^{-1} \lg \epsilon)$ times.

Let $N\_k$ be the algorithm that runs $M$ for $k$ times and then answers according to the answer of majority. For simplicity, lets assume that $k$ is odd so we don't have ties.

Consider the case that $x \in L$. The case $x \notin L$ is similar. Then $$\mathsf{Pr}\\{M(x) \text{ accepts}\\} = p \geq \frac{1}{2} + \delta$$ To analyze the correctness probability of $N\_k$ we need to estimate the probability that majority of the $k$ runs accept.

Let $X\_i$ be 1 if the $i$th run accepts and be $0$ if it rejects. Note that each run is independent from others as they use independent random bits. Thus $X\_i$s are independent Boolean random variables where $$\mathbb{E}\[X\_i\] = \mathsf{Pr}\\{X\_i=1\\} = \mathsf{Pr}\\{M(x)\text{ accepts}\\} = p \geq \frac{1}{2}+\delta$$

Let $Y = \Sigma\_{i=1}^k X\_i$. We need to estimate the probability that majority accept, i.e. the probability that $Y\geq\frac{k}{2}$.

$$\mathsf{Pr}\\{N\_k(x) \text{ accepts}\\} = \mathsf{Pr}\\{Y \geq \frac{k}{2}\\}$$

How to do it? We can use Chernoff bound which tells us the concentration of probability near the expected value. For any random variable $Z$ with expected value $\mu$, we have

$$\mathsf{Pr}\\{|Z-\mu| \> \alpha\mu\\} \< e^{\frac{\alpha^2}{4}\mu}$$

which says that the probability that $Z$ is $\alpha\mu$ far from its expected value $\mu$ is exponentially decreases as $\alpha$ increases. We will use it to bound the probability of $Y \< \frac{k}{2}$.

Note that by linearity of expectation we have $$\mathbb{E}\[Y\] = \mathbb{E}\[\Sigma\_{i=1}^k X\_i\] = \Sigma\_{i=1}^k \mathbb{E}\[X\_i\] = kp \geq \frac{k}{2} + k\delta$$

Now we can apply the Chernoff bound. We want an upper-bound on the probability of $Y\< \frac{k}{2}$. The Chernoff bound will give an upper-bound on the probability of $|Y-(\frac{k}{2}+k\delta)| \> k\delta$ which is sufficient. We have

$$Pr\\{|Y - kp| \> \alpha kp\\} \< e^{-\frac{\alpha^2}{4}kp}$$

and if we pick $\alpha$ such that $\alpha kp = k\delta$ we are done, so we pick $\alpha = \frac{\delta}{p} \leq \frac{2\delta}{2\delta+1}$.

Therefore we have

$$Pr\\{Y \< \frac{k}{2} \\} \leq Pr\\{|Y - (\frac{k}{2}+k\delta)| \> k\delta\\} \leq Pr\\{|Y - kp| \> \alpha kp\\} \< e^{-\frac{\alpha^2}{4}kp}$$

and if you do the calculations you will see that

$$\frac{\alpha^2}{4}kp \leq \frac{\delta^2}{4\delta+2}k = \Theta(k\delta)$$

we have

$$Pr\\{Y \< \frac{k}{2} \\} \< e^{-\Theta(k\delta)}$$

We want the error to be at most $\epsilon$, so we want

$$e^{-\Theta(k\delta)} \leq \epsilon$$

or in other words

$$\Theta(\delta^{-1} \lg \epsilon) \leq k $$

One essential point here is that in the process we will use many more random bits and also the running time will increase, i.e. the worst-case running-time of $N\_k$ will be roughly $k$ times the running-time of $M$.

Here the mid point of the gap was $\frac{1}{2}$. But in general this doesn't need to be the case. We can adopt a similar method for other values by taking other fractions in place of majority for accepting.

# Answer
> 7 votes
Using your notation:

$BPP =\\{L : \exists $ a probabilistic polynomial-time Turing Machine $ M, $ and a costant $ 0 \< c \leq 1/2$ such that $\forall x \\; Pr\[\chi\_L(x) = M(x)\] \geq \frac{1}{2} + c\\}$

$PP =\\{L : \exists $ a probabilistic polynomial-time Turing Machine $ M$ such that $\forall x \\; Pr\[\chi\_L(x) = M(x)\] \> \frac{1}{2}\\}$

The difference has been pointed out by adrianN, and you can also take a look at Wikipedia PP vs BPP

---
Tags: complexity-theory, terminology, randomized-algorithms, complexity-classes
---


# Question
Title: How does "δ:Q×Σ→Q" read in the definition of a DFA (deterministic finite acceptor)?
How do you say $\delta\colon Q \times \Sigma \to Q$ in English? Describing what $\times$" and $\to$ mean would also help.

# Answer
> 5 votes
$\delta$ is a function which takes a current state and a letter from the alphabet as arguments and produces next state.

It might be easier to understand when you realize that it is just a function that takes a pair, for instance $(q\_0, a)$ where $q\_0 \in Q$ is a state and $a \in \Sigma$ is a letter in the alphabet, and $\delta(q\_0, a) = q\_1$ means that if *in state $q\_0$ you read an 'a', proceed to state $q\_1$*.

It is the definition of a transition function which is used for example in Turing machines.

$\times$ means Cartesian product and $\to$ means "produces" or "maps to".

# Answer
> 4 votes
The statement $\delta\colon Q \times \Sigma \to Q$ translates to: The function $\delta$ assigns every pair formed by an element of $Q$ and an element of $\Sigma$, an element of $Q$. Instead of "assigns" you could also say "maps to". I assume that $\delta$ is the transition function for a finite automaton. Then you can say, $\delta$ assigns every pair, formed by a state and character a new state.

Here is a short explanation how to interpret the symbols you are asking for:

* In mathematics we often don't want just name a function $f$, we also want to say something about it by defining its *domain* $I$ and *codomain* $O$. To use an algorithmic analogue, the domain represents all possible inputs, and the codomain all possible outputs. (Of course a function can describe more complicated things than an algorithm can do.) If we want to denote the function we write $f\colon I \to O$.
* The $\times$ operator denotes the *cartesian product*. Simply speaking it is used to define *tuples*. For example, if you want to make a mathematical statement about *pairs* (with a distinguished first and second entry) you write $A\times B$ for the set of pairs, where the first entry is taken form $A$ and the second entry is taken from $B$. Analogously you can define larger tuples. The formal definition is $$ A\_1 \times A\_2 \times \cdots \times A\_n := \\{(a\_1,a\_2,\ldots,a\_n)\mid a\_1\in A\_1,\ldots ,a\_n\in A\_n\\}.$$

# Answer
> 1 votes
The statement $\delta: Q\times\Sigma\mapsto Q$ can be read as follows: given a state and a symbol the automaton moves to another state (possibly the state it was in). The $\times$ is like "and" in English meaning that you can pick any element from the first set $Q$ and any element from the second set $\Sigma$. More precisely, it's called the Cartesian product of the sets $Q$ and $\Sigma$. You can think of it as an operator that takes sets and outputs a new set that is the combinations of elements from $Q$ and $\Sigma$. Here is a simple example:

$Q=\\{q\_0,q\_1\\}$

$\Sigma=\\{a,b\\}$

$Q\times\Sigma=\\{(q\_0,a),(q\_0,b),(q\_1,a),(q\_1,b)\\}$

The symbol $\mapsto$ assigns elements taken from the right set to elements taken from the left set. You can think of it as a 2-column table, here is an example:

$(q\_0,a)$ maps to $q\_1$ and so on.

---
Tags: formal-languages, finite-automata
---


# Question
Title: Is every language with a finite number of strings regular?
1. Is every language with a finite number of strings regular?
2. Is the language of all strings regular?

I am new to this topic and got confused. Can any one please help me with this?

# Answer
1. Yes. Assume the language is $L=\\{w\_1,w\_2,\ldots, w\_n\\}$. then you can form the regular expression $w\_1 + w\_2 + \cdots + w\_n$, which describes $L$.

You can also argue with finite automata or regular grammars.
2. Yes, if your alphabet is $\Sigma=(a\_1,\ldots,a\_k)$ then the regular expression $(a\_1+a\_2+\cdots +a\_k)^\*$ describes the languages of all possible strings over $\Sigma$.
> 11 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: Natural RE undecidable problems but not Turing-complete
The Halting problem is a natural undecidable language which is complete for the set of recursivly enumrable sets. I am interested in undecidable but not Turing-complete language such that we can not reduce the Halting problem to it.

What is the most **natural** undecidable RE problem which is not Turing-complete?

# Answer
> 9 votes
There indeed are sets that are undecidable but not Turing complete. However, I'm not sure there is such a thing as a *natural* undecidable not Turing complete language.

Emil Post set out on a search for exactly this (See Post's problem) and his research resulted in the Simple sets. To quote from the Wikipedia article:

> \[Its existence\] was affirmed by Friedberg and Muchnik in the 1950s using a novel technique called the priority method. They give a construction for a set that is simple (and thus non-recursive), but fails to compute the halting problem.

---
Tags: computability, turing-completeness
---


# Question
Title: Can we make a problem harder than NP and coNP if they are not equal?
Let us assume that $\mathsf{NP} \neq \mathsf{coNP}$. Consider the graph 3-colorability problem.

Since $\mathsf{NP} \neq \mathsf{coNP}$ implies $\mathsf{P} \neq \mathsf{NP}$ and 3-coloribility is $\mathsf{NP}$-complete and its complement is $\mathsf{coNP}$-complete , we have:

1. 3-coloribility is not in $\mathsf{P}$, i.e. there are no polynomial-time algorithm for deciding if a given graph is 3-colorable.
2. non-3-coloribility is not in $\mathsf{NP}$, i.e. there are no polynomial-time verifier with polynomial-size certificatesfor non-3-colorability.

However, we know that for many classes of graphs, polynomial algorithms exists for 3-colorability and also they have polynomial-time verifiers with polynomial-size certificates for non-3-colorability. But this is not the case for all graphs since we we assumed that $\mathsf{NP} \neq \mathsf{coNP}$.

We can define the following problem:

> Input: a graph $G$,
> Task: determine if $G$ is 3-colorable or non-3-colorable and provide a certificate for the answer. The certificate is either a 3-coloring or a non-3-colorability certificate.

What is the complexity of this problem?

YES version is in $\mathsf{NP}$ . And the NO version is in $\mathsf{coNP}$. Note that the answer is not always YES since $\mathsf{NP} \neq \mathsf{coNP}$.

# Answer
**Note:** this answer was posted for the original post.

> Given a graph G: is there an algorithm, bounded by a polynomial of order k, that can determine if G is 3-colorable-or-non-3-colorable and provide a certificate?

If you fix the graph then the problem is trivial. There is always an algorithm that answers in constant time. There is no input.

If the graph is the input, then the answer is always YES. Any graph is either 3-colorable or not 3-colorable.

> Note that the answer is not alway yes since NP ≠ Co-NP

I don't see how this is relevant.
> 4 votes

# Answer
> Given a graph G: is there an algorithm, bounded by a polynomial of order k, that can determine if G is 3-colorable-or-non-3-colorable and provide a certificate?

I think what you meant here was: given a graph $G$, find whether there is a certificate or short proof for whether it is 3-colorable. What you're missing here is that there is no optimal polynomial time algorithm that finds such certificates, if possible. You can always extend a given "optimal" algorithm by hardwiring the answer to a finite number of graphs.

Moreover, for any graph $G$ there is an algorithm that outputs YES, NO, or DON'T KNOW, never makes a mistake, and is correct on $G$. It's even linear time \[edit: actually constant time\]. Furthermore, the algorithm is provably correct.
> 0 votes

---
Tags: complexity-theory, complexity-classes
---


title: Regular language properties

text:
# Question
Title: Regular language properties
For regular languages $R, S$ and $T$, which of the following are true?

1. $R \cup S = S \cup R$
2. $(R \cup S) \cdot T = RT \cup ST $
3. $R^\* \cdot S^\* = (R \cup S)^\*$

# Answer
1. True
2. True
3. False

To find the proofs, proceed as follows:

1. Show that any string $x \in R \cup S$ belongs to $S \cup R$, and vice versa.
2. Ditto 1.
3. Find a string $x$ that is in $(R \cup S)^\*$ but not the LHS. *Hint: what about $rsr$ where $r \in R, s \in S$?*
> 5 votes

# Answer
1. $x\in R\cup S \iff x\in R \vee x \in S \iff x\in S \vee x \in R \iff x\in S\cup R$
2. $x\in(R\cup S)T \iff \exists u, v \mid (x=uv)\wedge (u \in R\cup S)\wedge (v\in T) \iff \exists u, v \mid (x=uv)\wedge (u \in R \vee u \in S)\wedge (v\in T) \iff \exists u, v \mid (x=uv)\wedge (u\in R \wedge v\in T) \vee (u\in S \wedge v\in T) \iff \exists u, v \mid (x=uv)\wedge (x\in RT)\vee (x\in ST)\iff x\in RT\cup ST$.
3. Let $R=\\{0\\}$ and $S=\\{1\\}$.
> 2 votes

---
Tags: formal-languages, regular-languages, sets
---


title: Application of Expander Codes

text:
# Question
Title: Application of Expander Codes
I need to give a talk about expander codes at university (I'm a student of computer science). Since they have been introduced to show a family of codes looking good when thinking of the Shannon theorem, I wonder what real world application for expander codes exist.

As far as I know one has a real hard time when encoding but decoding is quite fast. Why aren't they used to encode write only media or similar? What is their big disadvantage?

# Answer
One area that you could consider is **Fault Tolerant Parallel Computation**. Expander codes and graphs could be efficiently used in them like:

Highly fault-tolerant parallel computation, by Daniel A. Spielman

On word-level parallelism in fault-tolerant computing
> 2 votes

---
Tags: graphs, combinatorics, coding-theory, expanders
---


title: Simple lower bounds against AC0

text:
# Question
Title: Simple lower bounds against AC0
It is known that $Parity \notin AC^0$ (nonuniform), but the proof is rather involved and combinatorial. Are there simpler, but weaker lower bounds, say for $NP \not \subseteq AC^0$ or $NEXP \not \subseteq AC^0$?

For example, can nontrivial simplifications be obtained in the proof of $NEXP \not \subseteq ACC^0$ to deal only with the special case of $AC^0$?

# Answer
I guess it depends on your point of view, but the proof via approximating polynomials (along the lines of Razborov-Smolensky) that Parity isn't in AC0 is not so involved...

The natural way in which one would modify the proof that "NEXP is not in ACC0" to yield "NEXP not in AC0" would be to give a SAT algorithm for AC0 circuits that beats exhaustive search. However, all known SAT algorithms of this kind actually use the same or similar techniques as the "Parity not in AC0" lower bounds, so the proof would not get any simpler. (It would be interesting to find an AC0 SAT algorithm where this is not the case.)
> 7 votes

---
Tags: complexity-theory, lower-bounds, circuits
---


# Question
Title: Is a relational database just a $ \geq 2$-dimensional array?
In terms of comparing data structures, is a relational database just a \>1 dimensional array? I'm just asking because I don't know much about databases, but I know a bit about data structures.

I am trying to make this clear in my mind.

# Answer
> 4 votes
No, it isn't. A data structure can be described in two ways:

1. How does it store the data.
2. Which operations are supported, their performance (usually given as asymptotic time- and/or space-complexity), and what laws do they obey.

Obviously, a database doesn't store all its data as a single array.

Arrays support, as basic operations, retrieving an element by index and storing an element under an index. Operations required for databases are (to a first approximation) given by relational algebra: selection, projection, union, difference, and join (or product).

# Answer
> 2 votes
Technically, you could say that a database can be represented as a huge array. The benefit of a DB, however, is the ability to represent this huge array very succinctly.

More theoretically, the benefit of a DB can be compared to the topological fact that cylinder sets can be represented succinctly, as opposed to more complex subsets. Essentially, a DB is a representation of a cylinder set as a multiplication of its respective dimensions.

# Answer
> 1 votes
In database literature this idea is widely known as universal relation.

# Answer
> 0 votes
There is some basic similarity between relational DB and large array (table~multidimensional array).

Relational DB is based on **relational algebra** which makes it powerful. By using relational operators, information could be retrieved, updated, inserted, deleted etc... in DB efficiently.

Considering array as a simple data structure, it only supports **read/write operators** in constant time $O(1)$. while in relational db you can write lots of complex queries using relational algebra.

---
Tags: data-structures
---


# Question
Title: How are programming languages and foundations of mathematics related?
Basically I am aware of three foundations for math

1. Set theory
2. Type theory
3. Category theory

So in what ways are programming languages and foundations of mathematics related?

EDIT

The original question was "Programming languages based on foundations of math"

with the added paragarph of

And implementations of theory
1. Type theory in Coq
2. Set theory in SETL
3. Category theory in Haskell

Based on a suggestion this was changed to "How are programming languages and foundations of mathematics related"

Since this is one of those questions were I did not know enough about what I was asking but wanted to learn something, I am modifing the question to make it more valuable for learning and others, yet leaving the details in so as not to make the current answer by Andrej Bauer seem off topic.

Thanks for all the comments and the answer so far, I am learning from them.

# Answer
\[Note: this paragraphs is now outdated.\] The title of your question contains an unwarranted assumption, namely that programming languages are "based on foundations of mathematics". This is generally not the case, although the two areas do have important relationships. A more accurate statement would be that (some) programming languages were designed using foundational techniques. A better question to ask would be *"how are programming languages and foundations of mathematics related?"*

The most general connection is embodied in the slogan *proofs-as-programs*, which can be made to work in several ways. The Curry-Howard correspondence is the most obvious one. With it we relate at once type theory, logic, and programming. But it should be emphasize that the Curry-Howard correspondence does not work very well in the presence of general recursion (because every type becomes inhabited), which every general-purpose programming language supports.

A subtler way of making the slogan proofs-as-programs work is to use realizability. Here too we relate proofs and programs, but now the direction goes from proofs to programs: every proof gives a program, but not every program is necessarily a proof.

The main example of a programming language based on a foundation is Agda, which simply *is* an implementation of dependent type theory. However, Agda is not a general-purpose programming language because it does not support general recursion. Every function in Agda is total, and there are computable functions which cannot be implemented in Agda. In practice programmers won't notice this, but they will notice that Agda does not allow undefined values, for example infinite loops.

Coq is *not* a programming language but rather a proof assistant. However, it too has extraction capabilities which give programs from proofs. Proof assistants and programming languages should not be confused with each other.

We should not forget that prolog and other logic programming languages take their inspiration from the idea that *computation as proof search*. This of course relates them closely to logic.

Haskell is a general-purpose programming language which is based on domain theory. That is to say, its semantics is domain-theoretic because it has to account for partial functions and recursion. The Haskell community has developed a number of techniques inspired by category theory, of which monads are best known but should not be confused with monads. More generally, advanced programming features are usually treated with a combination of domain theory and category theory, but this is not something that the Haskell programmer in the street is adept at. The so-called "syntactic category" of Haskell types is a lay man's view of how Haskell and category theory correspond to each other.

Set theory (classical or constructive) seems to inspire ideas in programming language to a lesser extent. Of course, constructive set theory has its connection to programming through constructive logic. One important application of intuitionistic set theory to programming languages was given by Alex Simpson who used it to make synthetic domain theory work. But this is quite advanced stuff, maybe see these slides. Jean-Louis Krivine has developed a very interesting brand of realizability for classical set theory. This seems a good way to relate classical set theory and programming.

In summary, the theory of programming languages uses foundational techniques. This is not surprising, as we consider computation to be a fundamental concept. But it is too naive to say that programming languages are "based" on a certain foundations. In fact, the trichotomy of foundations "set theory -- type theory -- category theory" is again just a useful high-level observation that can be made mathematically precise in various ways, but there is nothing necessary about it. It is a historic accident.
> 29 votes

# Answer
this is a very complex topic and there are many great books on the subject, a recent one is called Turings Cathedral, origins of the digital universe and also Engines of logic, mathematicians and the origins of the computer.

computer languages have evolved over many decades, but believe it or not there are two original programming languages which show that mathematics and computer science are intimately intertwined:

there are two key figures who crossed mathematical and computer science boundaries wrt "programming languages":

* information theory pioneered by Shannon shows the deep connections between mathematics and computer science
* another key figure that crosses between mathematics and computer science is Von Neumann. he invented the von neumann architecture of storing programs in memory.

even earlier "programming languages":

* the english word "computer" originally meant something more like a "calculator" that used mathematical operations on numbers and its meaning has shifted substantially to the general-purpose programming concept of today. so there is a connection between programming languages and early calculators.
* punch cards used in weaving looms from the late 19th and early 20th century were a "programming language" for weaving patterns. note that punch cards were used for programming mainframes much in the 1960s. these were originally seen as "calculating machines" (using mathematics!) not so much modern, general purpose computers.
* Babbage and Ada Lovelace developed the rudimentary early concepts of "programming languages" in the mid 1800s on a "calculating engine"
* boolean algebra was originally a purely mathematical concept invented by Boole
* the ancient (millenia old) *abacus* for mathematical calculation is seen as a forerunner of the modern computer. but it could be said that operations for manipulating it were a sort of "programming language" (followed by humans)

however, in modern programming languages as the abstraction has increased and scaled, the clear, direct connection to mathematics has somewhat decreased over the decades, but its always going to be quite intrinsic and in some ways, it has strengthened. for example languages such as Java with its strict types has connections to mathematics, and in the starting in the late ~1990s mainstream computer languages (eg c++, Java, Ruby etc) started explicitly implementing many mathematical higher-level objects as near primitives in the languages such as sets, trees (eg Btrees or hashmaps), etc.
> 7 votes

---
Tags: programming-languages, history, type-theory, category-theory
---