# Question
Title: Functions with small support have small circuits
I have been trying to understand the use of circuit models for boolean functions, and came across this question, that I am trying to struggle to understand:

Show that if a function $f\colon \\{0,1\\}^n→\\{0,1\\}$ has a support of size $k$, then it can be decided by a circuit of size $O(nk)$.

I understand that for any binary functions of this sort, the maximal size of the circuit is $O(n2^n)$, and I have a feeling that this could be useful for proving the statement, but I am not exactly sure where to proceed from there. Furthermore, I also understand that the "support" referred to in this question is actually the language defined by the function, but again, this leads me nowhere.

Any help on this would be much appreciated.

# Answer
> 0 votes
Consider the AND function: $$ x\_1 \land \cdots \land x\_n. $$ Its support size is $1$, and its circuit complexity is $O(n)$. By negating inputs, you can get a circuit for any function whose support size is $1$. By ORing together $k$ such functions, you can get a circuit of size $O(kn)$ for any function whose support size is $k$.

---
Tags: complexity-theory, circuits, boolean-algebra, upper-bound
---


# Question
Title: Solve the following recurrence-relations: $T(n)=5T(n/3)+T(2n/3)+1,T(n)=2T(\sqrt{n})+\log_2(n)$
Solve the following recurrence-relations:
my attempet for the first one was doing upper bound and lower bound by changing for lower $6T(n/3)+1$ and for upper $6T(2n/3)+1$ but i didn't get the same order for $\Theta$ $T(n)=5T(n/3)+T(2n/3)+1,T(1)=c$

$T(n)=2T(\sqrt{n})+\log\_2(n),T(4)=2$
I'm not sure if I solved this right but:
setting $y(n)=T(2^n)$ we get
$y(n)=2T(\sqrt{2^n})+\log\_2(2^n)=2y(n/2)+n$ using the master's theorem we get that $y(n)=\Theta(nlogn)$ and therefore $T(n)=\Theta(log(n)loglog(n))$ And for the first recurrence i still don't know

# Answer
> 1 votes
Now that we know the answer, we could simplify the proof.

Let's prove that $$T(n)\in\Theta\left(n^2\right)$$

Define $k=k\_n$, *index* of $n$ in base $3/2$, to be the smallest $k$ such that $n/(3/2)^k\<1$.

---

**Upper bound:**

Assume that $C$ is very large such that $T(1)\leq C=C\cdot1^2$, $1-3C\<-C/2$, and that for all $k\<K$ and all $m$ with index $k$ we have $$T(m)\leq C(m^2-1/2)$$

**Note:** We are going to use the $-1/2$ to carry out the induction as it was done in the other answer.

Let $n$ be of index $K$. Then $n/3$ and $2n/3$ are of index smaller than $K$. It follows that

$$\begin{align}T(n)&=5T(n/3)+T(2n/3)+1\\ &\leq 5C(n/3)^2-5C/2+C(2n/3)^2-C/2+1\\ &=Cn^2\left(5/3^2+(2/3)^2\right)+1-3C\\ &=Cn^2+1-3C\\ &\leq Cn^2-C/2\\ &=C(n^2-1/2)\end{align}$$

---

**Lower bound:**

Assume that $D$ is such that $D\>0$, $T(1)\geq D\cdot 1^2=D$, $1-3D\geq -D/2$, and that for every $k\<K$ and $m$ of index $k$ we have $$D(m^2-1/2)\leq T(m)$$

Let $n$ be of index $K$. Then $n/3$ and $2n/3$ are of index smaller than $K$. Therefore,

$$\begin{align} T(n)&=5T(n/3)+T(2n/3)+1\\ &\geq 5D((n/2)^2-1/2)+D((2n/3)^2-1/2)+1\\ &=Dn^2\left(5/3^2+1/(3/2)^2\right)-5D/2-D/2+1\\ &=Dn^2+1-3D\\ &\geq D\left(n^2-1/2\right) \end{align}$$

---

By induction we have proven that for all $n$ we have $$D(n^2-1/2)\leq T(n)\leq C(n^2-1/2)$$

Therefore, $$T\in \Theta(n^2-1/2)=\Theta(n^2)$$

# Answer
> 0 votes
You would just need to follow Akra-Bazzi's argument for your particular case.

Let's prove that $$T(n)\in\Theta\left(n^2\left(\frac{3}{2}-\frac{1}{2n^2}\right)\right)$$

Here $$\frac{3}{2}-\frac{1}{2n^2}=1+\int\_{1}^{n}\frac{dx}{x^{2+1}}$$

First let $b=\min(3,\frac{3}{2})=\frac{3}{2}$. Let $k\_n$ be the smallest positive integer such that $n/b^{k\_n}\<1$. Call this $k\_n$ the *index* of $n$ base $b$.

Let $p$ be the solution to $5/3^p+1/(3/2)^p=1$. This is, $$p=2$$

---

**Upper bound:**

Take $C$ such that $T(1)\leq C$ and $Cn^p\int\_{2n/3}^{n}\frac{dx}{x^{p+1}}=5C/8\geq 1$.

Then $T(1)\leq C=Cm^2\left(1+\int\_{1}^{m}\frac{dx}{x^{p+1}}\right)|\_{m=1}$

Assume that for all $k\<K$ and all $m$ of index $k$ we have

$$T(m)\leq Cm^2\left(1+\int\_{1}^{m}\frac{dx}{x^p+1}\right)$$

Let $n$ be of index $K$. Then $n/3$ and $2n/3$ have index smaller than $K$. Using the assumption we have that

$$\begin{align}T(n)&=5T(n/3)+T(2n/3)+1\\ &\leq 5C(n/3)^p\left(1+\int\_{1}^{n/3}\frac{dx}{x^{p+1}}\right)+C(2n/3)^p\left(1+\int\_{1}^{2n/3}\frac{dx}{x^{p+1}}\right)+1\\ &\leq5C(n/3)^p\left(1+\int\_{1}^{\mathbf{2}n/3}\frac{dx}{x^{p+1}}\right)+C(2n/3)^p\left(1+\int\_{1}^{2n/3}\frac{dx}{x^{p+1}}\right)+1\\ &=C\left(5/3^p+1/(3/2)^p\right)n^p\left(1+\int\_{1}^{2n/3}\frac{dx}{x^{p+1}}\right)+1\\ &=Cn^p\left(1+\int\_{1}^{2n/3}\frac{dx}{x^{p+1}}\right)+1\\ &\leq Cn^p\left(1+\int\_{1}^{n}\frac{dx}{x^{p+1}}\right)\end{align}$$

So, by induction on the index of $n$ we get that for all $n\geq1$

$$T(n)\leq Cn^p\left(1+\int\_{1}^{n}\frac{dx}{x^{p+1}}\right)=Cn^2\left(\frac{3}{2}-\frac{1}{2n^2}\right)$$

---

**Lower bound:**

Now let's prove the bound from below. It is a very similar argument.

Take $D$ such that $0\<D\leq T(1)$ and $Dn^2\int\_{n/3}^{n}\frac{dx}{x^{p+1}}=4D\leq 1$.

Assume that for all $k\<K$ and all $m$ of index $k$ we have that $$Dm^p\left(1+\int\_{1}^{m}\frac{dx}{x^{p+1}}\right)\leq T(m)$$.

Let $n$ be of index $K$. Then $n/3$ and $2n/3$ are of index smaller than $K$. Using the assumption we have that

$$\begin{align}T(n)&=5T(n/3)+T(2n/3)+1\\ &\geq5D(n/3)^p\left(1+\int\_{1}^{n/3}\frac{dx}{x^{p+1}}\right)+D(2n/3)^p\left(1+\int\_{1}^{2n/3}\frac{dx}{x^{p+1}}\right)+1\\ &\geq5D(n/3)^p\left(1+\int\_{1}^{n/3}\frac{dx}{x^{p+1}}\right)+D(2n/3)^p\left(1+\int\_{1}^{n/3}\frac{dx}{x^{p+1}}\right)+1\\ &=(5/(3^p)+1/(3/2)^p)Dn^p\left(1+\int\_{1}^{n/3}\frac{dx}{x^{p+1}}\right)+1\\ &=Dn^{p}\left(1+\int\_{1}^{n/3}\frac{dx}{x^{p+1}}\right)+1\\ &\geq Dn^p\left(1+\int\_{1}^{n}\frac{dx}{x^{p+1}}\right)\end{align}$$

Hence, for all $n\geq1$ $$Dn^2\left(\frac{3}{2}-\frac{1}{2n^2}\right)=Dn^p\left(1+\int\_{1}^{n}\frac{dx}{x^{p+1}}\right)\leq T(n)$$

---
Tags: recurrence-relation, check-my-answer
---


title: Showing that $F$ is a monotone function

text:
# Question
Title: Showing that $F$ is a monotone function
I am currently studying the textbook *Principles of Program Analysis* by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter **1.3 Data Flow Analysis** says the following:

> **The least solution.** The above system of equations defines the twelve sets $$\text{RD}\_\text{entry}(1), \dots, \text{RD}\_{\text{exit}}(6)$$ in terms of each other. Writing $\overrightarrow{RD}$ for this twelve-tuple of sets we can regard the equation system as defining a function $F$ and demanding that: $$\overrightarrow{RD} = F(\overrightarrow{RD})$$ To be more specific we can write $$F(\overrightarrow{RD}) (F\_\text{entry}(1)(\overrightarrow{RD}), F\_\text{exit}(1)(\overrightarrow{RD}), \dots, F\_\text{entry}(6)(\overrightarrow{RD}), F\_\text{exit}(6)(\overrightarrow{RD}))$$ where e.g.: $$F\_\text{entry}(3)(\dots, \overrightarrow{RD}\_\text{exit}(2), \dots, \overrightarrow{RD}\_\text{exit}(5), \dots) = \overrightarrow{RD}\_\text{exit}(2) \cup \overrightarrow{RD}\_\text{exit}(5)$$ It should be clear that $F$ operates over twelve-tuples of sets of pairs of variables and labels; this can be written as $F : (\mathcal{P}(\mathbf{\text{Var}\_\star \times \mathbf{\text{Lab}\_\star}))}^{12} \to (\mathcal{P}(\mathbf{\text{Var}\_\star \times \mathbf{\text{Lab}\_\star}))}^{12}$ where it might be natural to take $\mathbf{\text{Var}\_\star} = \mathbf{\text{Var}}$ and $\mathbf{\text{Lab}\_\star} = \mathbf{\text{Lab}}$. However, it will simplify the presentation in this chapter to let $\mathbf{\text{Var}\_\star}$ be a *finite* subset of $\mathbf{\text{Var}}$ that contains the variables occurring in the program $\mathbf{S\_\star}$ of interest and similarly for $\mathbf{\text{Lab}\_\star}$. So for the example program we might have $\mathbf{\text{Var}\_\star} = \\{ x, y, z \\}$ and $\mathbf{\text{Lab}\_\star} = \\{ 1, \dots, 6, ? \\}$.
>
> It is immediate that $(\mathcal{P}(\mathbf{\text{Var}\_\star \times \mathbf{\text{Lab}\_\star}))}^{12}$ can be partially ordered by setting $$\overrightarrow{\text{RD}} \sqsubseteq \overrightarrow{\text{RD}}^\prime \ \ \ \text{iff} \ \ \ \forall i : \text{RD}\_i \subseteq \text{RD}\_i^\prime$$ where $\overrightarrow{\text{RD}} = (\text{RD}\_1, \dots, \text{RD}\_{12})$ and similarly $\overrightarrow{\text{RD}}^\prime = (\text{RD}\_1^\prime, \dots, \text{RD}\_{12}^\prime)$. This turns $(\mathcal{P}(\mathbf{\text{Var}\_\star \times \mathbf{\text{Lab}\_\star}))}^{12}$ into a complete lattice (see Appendix A) with least element $$\overrightarrow{\emptyset} = (\emptyset, \dots, \emptyset)$$ and binary least upper bounds given by: $$\overrightarrow{\text{RD}} \sqcup \overrightarrow{\text{RD}}^\prime = (\text{RD}\_1 \cup \text{RD}\_1^\prime, \dots, \text{RD}\_{12} \cup \text{RD}\_{12}^\prime)$$
>
> It is easy to show that $F$ is in fact a monotone function (see Appendix A) meaning that: $$\overrightarrow{\text{RD}} \sqsubseteq \overrightarrow{\text{RD}}^\prime \ \ \ \text{implies} \ \ \ F(\overrightarrow{\text{RD}}) \sqsubseteq F(\overrightarrow{\text{RD}})^\prime$$ This involves calculations like $$\text{RD}\_\text{exit}(2) \subseteq \text{RD}\_\text{exit}^\prime(2) \ \ \text{and} \ \ \text{RD}\_\text{exit}(5) \subseteq \text{RD}\_\text{exit}^\prime(5)$$ imply $$\text{RD}\_\text{exit}(2) \cup \text{RD}\_\text{exit}(5) \subseteq \text{RD}^\prime\_\text{exit}(2) \cup \text{RD}\_\text{exit}^\prime(5)$$ and the details are left to the reader.

Appendix A gives the following definition for *monotone function*:

> The function $f$ is *monotone* (or *isotone* or *order-preserving*) if $$\forall l, l^\prime \in L\_1 : l \sqsubseteq\_1 l^\prime \Rightarrow f(l) \sqsubseteq\_2 f(l^\prime)$$

From earlier in the textbook:

>

>

I am trying to do as the author said, and show that $F$ is a monotone function. However, I have so far been unable to make progress. It seems to me that such a proof should proceed by showing that, for some arbitrary element of the set of elements $F(\overrightarrow{\text{RD}})$, if we use the fact that $\overrightarrow{\text{RD}} \sqsubseteq \overrightarrow{\text{RD}}^\prime$, then we can deduce that said arbitrary element is also an element of the set $F(\overrightarrow{\text{RD}})^\prime$, and so $F(\overrightarrow{\text{RD}}) \sqsubseteq F(\overrightarrow{\text{RD}})^\prime$. However, it seems to me that the textbook is very poorly written, and so it is difficult for me to even understand what said arbitrary elements of the set $F(\overrightarrow{\text{RD}})^\prime$ even are (they seem to be some kind of cartesian product, but I get very confused when trying to figure out precisely what they are). So how is it shown that $F$ is a monotone function?

# Answer
> 0 votes
Let me start by giving a formula for the function $F$: \begin{align\*} \newcommand{\ent}{\mathsf{RD}\_{\mathit{entry}}} \newcommand{\ext}{\mathsf{RD}\_{\mathit{exit}}} \newcommand{\Lab}{\mathbf{Lab}} \newcommand{\bx}{\mathbf{x}} \newcommand{\by}{\mathbf{y}} \newcommand{\bz}{\mathbf{z}} &F(\ent(1),\ldots,\ent(6),\ext(1),\ldots,\ext(6)) = \\ (&\\{(\bx,?),(\by,?),(\bz,?)\\}, \ext(1), \ext(2) \cup \ext(5), \ext(3), \ext(4), \ext(3), \\ &(\ent(1) \setminus \\{(\by,\ell) \mid \ell \in \Lab\\}) \cup \\{(y,1)\\}, \\ &(\ent(2) \setminus \\{(\bz,\ell) \mid \ell \in \Lab\\}) \cup \\{(z,2)\\}, \\ &\ent(3), \\ &(\ent(4) \setminus \\{(\bz,\ell) \mid \ell \in \Lab\\}) \cup \\{(z,4)\\}, \\ &(\ent(5) \setminus \\{(\by,\ell) \mid \ell \in \Lab\\}) \cup \\{(y,5)\\}, \\ &(\ent(6) \setminus \\{(\by,\ell) \mid \ell \in \Lab\\}) \cup \\{(y,6)\\}). \end{align\*} In order to show that $F$ is monotone, you need to show that the following hold whenever $\ent(i) \subseteq \ent'(i)$ and $\ext(i) \subseteq \ext'(i)$ for $i \in \\{1,\ldots,6\\}$:

* $\\{(\bx,?),(\by,?),(\bz,?)\\} \subseteq \\{(\bx,?),(\by,?),(\bz,?)\\}$.
* $\ext(1) \subseteq \ext'(1)$
* $\ext(2) \cup \ext(5) \subseteq \ext'(2) \cup \ext'(5)$
* $\ext(3) \subseteq \ext'(3)$
* $\ext(4) \subseteq \ext'(4)$
* $\ext(3) \subseteq \ext'(3)$
* $(\ent(1) \setminus \\{(\by,\ell) \mid \ell \in \Lab\\}) \cup \\{(y,1)\\} \subseteq (\ent'(1) \setminus \\{(\by,\ell) \mid \ell \in \Lab\\}) \cup \\{(y,1)\\}$
* $(\ent(2) \setminus \\{(\bz,\ell) \mid \ell \in \Lab\\}) \cup \\{(z,2)\\} \subseteq (\ent'(2) \setminus \\{(\bz,\ell) \mid \ell \in \Lab\\}) \cup \\{(z,2)\\}$
* $\ent(3) \subseteq \ent'(3)$
* $(\ent(4) \setminus \\{(\bz,\ell) \mid \ell \in \Lab\\}) \cup \\{(z,4)\\} \subseteq (\ent'(4) \setminus \\{(\bz,\ell) \mid \ell \in \Lab\\}) \cup \\{(z,4)\\}$
* $(\ent(5) \setminus \\{(\by,\ell) \mid \ell \in \Lab\\}) \cup \\{(y,5)\\} \subseteq (\ent'(5) \setminus \\{(\by,\ell) \mid \ell \in \Lab\\}) \cup \\{(y,5)\\}$
* $(\ent(6) \setminus \\{(\by,\ell) \mid \ell \in \Lab\\}) \cup \\{(y,6)\\} \subseteq (\ent'(6) \setminus \\{(\by,\ell) \mid \ell \in \Lab\\}) \cup \\{(y,6)\\}$

I'm sure you can work it out.

---
Tags: partial-order, data-flow-analysis, lattices, order-theory
---


title: Average of all sums of subarrays

text:
# Question
Title: Average of all sums of subarrays
I ran into a very hard question.

We have array of $n$ integers. for $1 \leq i \leq j \leq n$. we want to set $c\_{ij}$= Sum of all values in the range $i$ to $j$ of this array. we want to finding average of all possible $c\_{ij}$ in this array. if 4 basic operation in math $(+,-,\*,/)$ can be done in $O(1)$. the best algorithm can be works in $O(n)$.

this example is example from my made easy preparation class. anyone can describe me in simple words how this algorithm can be?

# Answer
> 1 votes
It's not so clear what is meant by "sum of all values in the range $i$ to $j$". This probably means the sum of entries in *locations* $i$ to $j$.

Let us denote the entries of the array by $a\_1,\ldots,a\_n$. The entry $a\_k$ is counted in those $c\_{ij}$ such that $i \leq k \leq j$. There are $k(n+1-k)$ of these, out of a total of $\binom{n}{2}$. Therefore the quantity you are interested in is $$ \frac{1}{\binom{n}{2}} \sum\_{k=1}^n k(n+1-k) a\_k. $$

---

Here is another interpretation, in which we sum all values in the array which belong to $\\{i,\ldots,j\\}$. Even this can be solved in linear time!

Suppose that some entry of the array has value $k$. What is its contribution to the average of the $c\_{ij}$? It is counted in some $c\_{ij}$ iff $i \leq k \leq j$. Out of the $\binom{n+1}{2}$ many $c\_{ij}$'s, there are exactly $k(n+1-k)$ in which the entry is counted, therefore its contribution to the average is $$ \frac{k(n+1-k)}{\binom{n+1}{2}} \cdot k = \frac{2k^2(n+1-k)}{(n+1)n}. $$ Summing this over all values in the array, we obtain the desired $O(n)$ algorithm.

---
Tags: algorithms, time-complexity, data-structures
---


# Question
Title: Relative primality is primitive recursive
How do I prove that the predicate $P(x , y)$ is primitive recursive, where $P(x,y)$ holds if $x,y$ are relatively prime?

# Answer
> 0 votes
Two numbers $x,y$ are *not* relatively prime iff there exists some common factor $a \> 1$, which divides both $x$ and $y$. This common factor can be bounded by $a$. Therefore $x,y$ are not relatively prime iff there exist $a,b \leq x$ and $c \leq y$ such that (i) $a \geq 2$, (ii) $x = ab$, and (iii) $y = ac$.

---
Tags: computability, primitive-recursion
---


# Question
Title: 2-Approximation algorithm for for messages across a cyclic network
**Question**
There are $n$ computers arranged in a cycle ($1,2,3..,n,1$), with undirected edges between adjacent computers. There are $m$ messages that need to be delivered. Message $i$ ($1 \le i \le m$) has to be sent from computer $s\_i$ to computer $t\_i$. There are two ways to deliver a message $i$: clockwise from $s\_i$ to $t\_i$ or anti-clockwise from $s\_i$ to $t\_i$. Aim is to send all messages in such a way that the number of messages going through the most frequently used edge is minimized. We need to devise a $2$-Approximation algorithm for the same.

**Example**
Let $n=4$. Let $m=2$. And let $s\_1=1,t\_1=4$ and $s\_2=2,t\_2=3$. Then if we send message $1$ in the following way: $1 \to 2 \to 3 \to 4$ and message $2$ as: $2 \to 3$. The most frequently edge used is $2 \to 3$, through which $2$ messages go. We can do better than this.

Message $1$: $1 \to 4$ and delivery of message $2$ remains same $2 \to 3$. Then both the edges are most frequently used. But only $1$ message goes through most frequently used edges.

**My approach 1**
For every message with probability $\frac{1}{2}$ send it in clockwise direction and with $\frac{1}{2}$ in anti-clockwise direction.
But this gives a bad performance, which can be seen with the help of the following example:
$n=10000$, $m=200$ and $s\_i = i,t\_i=i+1$ for $1 \le i \le 200$. Then the optimal answer is $1$ (ie. every edge has at most $1$ message going through it). Which can be achieved by sending message $i$ as $i \to (i+1)$.
Also this is the only way to achieve the optimal. If anyone of the messages were sent in the other direction the answer increases. For eg. if $x$ of the $200$ messages were sent in other direction, all these $x$ would use say edge $800 \to 801$. So the answer would be at least $x$. Thus in this case the random solution picks the optimal arrangement with only probability $\frac{1}{2^{200}}$, which is very less and for other arrangements answer gets bigger.

**My approach 2**
I turned towards greedy. Where for message $i$ we send it in the direction where it will travel through lesser number of edges, ie. we send it along the shorter route. Then I argued as below

(I consider $n$ odd for now, and also don't consider some other corner cases)

For an arbitrary input $n$, $m$ (and the respective source and sinks) let the optimal be $p$ (that is $p$ is the number of messages going through the most frequent used edge), then the optimal arrangement cannot have more than $2p$ messages for which longer routes were chosen. **Reason**: longer routes have at least $\frac{n+1}{2}$ contiguous edges, for example for $n=7$, if I list all thecontiguous subsets of size $\frac{n+1}{2}$ (the possibilities of longer route)

$$ 1,2,3,4 \\ 3,4,5,6 \\ 4,5,6,7 \\ 6,7,1,2 \\ 7,1,2,3 \\ $$

and lets say $p=1$. Then as first two subsets (nearly the half) have a common element $4$, and so do the last three subsets (again nearly the half) have common element $7$ (this is true for arbitrary odd $n$). There can be a case where (in the optimal arrangement) $p$ of the longer routes lie in first half of subsets and another $p$ of longer routes in the second half of subsets. But if more than $2p$ are there. There would be at least $p+1$ in a single half of subsets, making the answer $p+1$ which is a contradiction.

And as changing direction of a message can at worst increase the answer by $1$. The greedy should have answer $\le 3p$ (change all $2p$ longer routes to short, to get to what greedy outputs).

But I seem to be stuck beyond this. As this gives approximation factor of $3$ (I did not consider $n$ is even case, as I think if odd case is handled it will be just about the corner case of source and sink being at exactly $\frac{n}{2}$ distance).
Maybe in my reasoning I overestimated somewhere.

I had also tried tried to obtain bounds using weak duality by expressing problem as LP relaxation. Assuming my working was correct what I could get is $1\le$ optimal. Which is trivially true.

PS: I would highly appreciate hints only.

# Answer
> 1 votes
Start with an integer program for your problem.

For each $i$, there is a variable $x\_i \in \\{0,1\\}$ which represents which way the $i$'th message is routed. You can express the number of messages going through an edge $e$ as some linear combination $y\_e$ of the $x\_i$'s. Your goal is to minimize $\max(y\_e)$. Equivalently, you want to minimize $m$ under the constraints $m \geq y\_e$.

Now consider the LP relaxation. Determine which way to route the $i$'th message by rounding $x\_i$.

---
Tags: graphs, approximation, randomized-algorithms, greedy-algorithms
---


# Question
Title: Concept of M-augmenting path to find a larger matching than $M$
I'm reading section 16.1 of the book, Combinatorial optimization, Polyhedra and efficiency by Schrijver. Here, he starts with a matching $M$ and describes a path $P$ that is $M$-augmenting if:

1. The path has odd length (in terms of edges).
2. Its ends are not covered by $M$.
3. Its edges are alternately out of and in $M$.

Theorem 16.1 then states that we either have a matching of maximal size or an augmenting path exists.

I don't understand this statement. See the graph below for example. For now, we have the edge between vertices 2 and 5 in a matching $M$. I can't find any path that satisfies the three conditions above. Yet, this is obviously not a maximal matching since the edge between vertices 1 and 4 can be added to increase its size. What am I missing and why is my understanding so way off?

Further, if I'd used 1-4 as my initial matching, it would have been impossible to find a path that satisfies condition 2.

Conversely, I take the graph the the author himself provides as an example of an augmenting path. In the simple linear graph below (which is also a linked list), an augmenting path satisfying the three conditions above exists. However, where is the edge that can be added to this graph to increase the size of $M$?

# Answer
> 1 votes
Actually, I realized what I was missing shortly after posting the question and squinting at the pictures again. Instead of deleting, figured I'd simply post the answer for future reference. The thing I was missing was that the new matching won't have the same edges as the original matching. In the first figure, 3-\>5-\>2-\>4 is such a path and 2-\>4 $\cup$ 3-\>5 becomes a larger matching.

---
Tags: graphs, matching
---


# Question
Title: Min weighted edge cover: don't follow proof in Schrijver
I'm reading section 19.3 of Combinatorial Optimization by Schrijver where he details an algorithm for finding the min-weight edge cover. His method works for general graphs, but I'm particularly interested in bi-partite graphs. To find the min-weighted edge cover of a graph $G=(V,E)$ with a weight function $w: E \to R$, he first defines a clone graph, $\tilde{G} = (\tilde{V},\tilde{E})$. He then defines a larger graph, $G'=(V',E')$ whose set of vertices, $V'$ is the union of $V$ and $\tilde{V}$. The edges, $E'$ and weight function $w'(E')$ are as follows:

1. $w'(e)=w'(\tilde{e})=w(e)$ for $e \in E$
2. $w'(v,\tilde{v})=2\mu(v)$ for each $v \in V$ where $\mu(v)$ is the minimum weight edge of $G$ incident on $v$.

Now, we construct a minimum weight perfect matching, $M$ for $G'$ and this yields a minimum weight edge cover $F$ for $G$ once we replace any edge $v\tilde{v}$ in $M$ by an edge $e\_v$ of minimum weight of $G$ incident on $v$.

Now, for the proof that this works, the author notes that $w(F)=\frac{1}{2}w'(M)$. So far so good.

Then, he states that any edge cover $F'$ for $G$ gives by reverse construction a perfect matching $M'$ in $G'$ with $w'(M')\leq 2w(F')$.

This is the part I don't understand. How does one go about constructing this new perfect matching, $M'$ and further prove the inequality?

# Answer
> 1 votes
Let $M$ be a maximal subset of $F'$ which is a matching. Any vertex $v$ not covered by $M$ must be covered by some edge $e\_v=(v,w)$ in $F'$. Since $M$ is maximal, $w$ must be covered by $M$. It follows that if $v\_1 \neq v\_2$ are not covered by $M$, then $e\_{v\_1} \neq e\_{v\_2}$.

The matching $M'$ consists of the two copies of each edge in $M$, and of the edges $(v,\tilde{v})$ for each $v$ not covered by $M$. Edges of the first type have total weight $2w(M)$. Since $w(v,\tilde{v}) \leq 2w(e\_v)$, edges of the second type have total weight at most $2w(F' \setminus M)$ (this crucially uses that $e\_{v\_1} \neq e\_{v\_2}$ for any $v\_1 \neq v\_2$ not covered by $M$). Hence $w(M') \leq 2w(F')$.

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


# Question
Title: What is a disequality path in the context of equality graphs?
1. A path consisting of a number of disequality edges and a single equality edge
2. A path consisting of equality edges
3. A path consisting of a number of equality edges and a single disequality edge
4. A path consisting of disequality edges

The answer is number three, right? Who has any reasonable doubts or general short references?

# Answer
Suppose we have a bunch of variables $v\_i$ and a bunch of equations $v\_i = v\_j$ and disequalities $v\_i \neq v\_j$. We can describe out knowledge as a graph whose vertices are the variables and whose edges are the equations (equality edges) and disequalities (disequality edges).

An *equality path* is a proof that $v\_i = v\_j$. Such a proof consists of a path from $v\_i$ to $v\_j$ using only equality edges. A *disequality path* is a proof that $v\_i \neq v\_j$. Such a proof consists of a path from $v\_i$ to $v\_j$ in which exactly one edge is a disequality edge.

When the domain of the variables is larger than 2, then equality paths are the only way to deduce equality from the givens, and disequality paths are the only way to deduce disequality from the givens. This is a nice exercise. In the binary case, however, a path with an even number of disequality edges is a proof of equality, and a path with an odd number of disequality edges is a proof of disequality.
> 1 votes

---
Tags: graphs, satisfiability
---


# Question
Title: Does there exist a undecidable infinite language with only a finite undecidable subset?
I know that there's no such thing as a finitely sized undecidable language. However, does there exist an undecidable language where a finitely sized set of undecidable elements are 'hiding among' an infinite set of decidable elements?

In order to formalize this, let's build a deciding machine that answers $\text{YES}$, $\text{NO}$, or $\text{MAYBE}$. A correct decider for a language may always answer $\text{MAYBE}$, but if it answers $\text{YES}$ or $\text{NO}$ its answer must be correct. Such a decider can always be constructed for any (undecidable) language - in the worst case it simply always returns $\text{MAYBE}$.

Does there exist an undecidable language $L$ for which a correct decider exists that only answers $\text{MAYBE}$ for a finite number of elements of $L$?

# Answer
Let $S$ be the set of elements on which the decider $T$ answers MAYBE. We can construct a new decider $T'$ which correctly decides $L$ as follows:

* If the input is in $S$, answer the hardwired correct answer.
* Otherwise, run $T'$.

Hence $L$ is decidable.

This actually shows that if $L$ is undecidable, then every decider for $L$ must make infinitely many mistakes.
> 2 votes

---
Tags: undecidability
---


title: Approximate LP for vertex cover problem

text:
# Question
Title: Approximate LP for vertex cover problem
I am studying the topic of vertex cover on coursera and how it can be solved approximately by linear programming. Suppose the optimal solution for the vertex cover problem is $OPT$. I do not understand why the approximate solution $$\sum\_u w\_u x^\*\_u \leq OPT$$

where $w\_u$ is the weight to each vertex and $x^\*\_u$ is the approximate solution to the vertex cover problem and $0 \leq x\_u^\* \leq 1$

Can someone provide an explanation on how it is possible for the equation above ?

# Answer
> 2 votes
Let's start with an integer program for vertex cover:

\begin{align} &\min \sum\_{v \in V} x\_v \\ \text{s.t.}\\;\\; & x\_u + x\_v \geq 1 &&\text{for every } (u,v) \in E \\ & x\_v \in \\{0,1\\} &&\text{for every } v \in V \end{align} Here $V$ is the set of vertices and $E$ is the set of edges.

The optimal solution for this integer program is the minimum vertex cover in the graph. We denote its value by OPT.

Unfortunately integer programming is NP-hard to solve exactly, so we consider a linear programming *relaxation*, replacing the constraint $x\_v \in \\{0,1\\}$ by the constraint $x\_v \in \[0,1\]$:

\begin{align} &\min \sum\_{v \in V} x\_v \\ \text{s.t.}\\;\\; & x\_u + x\_v \geq 1 &&\text{for every } (u,v) \in E \\ & 0 \leq x\_v \leq 1 &&\text{for every } v \in V \end{align}

Every feasible solution of the original integer program is also a feasible solution of the linear programming relaxation. In other words, the linear program is minimizing over a set of solutions which contains the set of solutions to the integer program. Therefore the optimal value of the linear program is bounded from above by OPT.

More abstractly, if $A \subseteq B$ then $$ \min\_{x \in B} \phi(x) \leq \min\_{x \in A} \phi(x). $$ In our case, $A$ is the set of solutions to the integer program, $B$ is the set of solutions of the linear program, and $\phi$ is the objective function $\sum\_{v \in V} x\_v$.

---
Tags: optimization, linear-programming, vertex-cover
---


# Question
Title: Proof the number of expected node in a binary using mathematical induction
> The following algorithm constructs a binary tree.

```
MakeArray(array[x:y]) (
 if(x==y):
  the root is x
 else:
  pick a number r as root
  MakeArray(array[x:r-1])
  MakeArray(array[r+1:y])
)

```

> Let $a\_n$ be the expected number of nodes which have two children in the tree with $n$ nodes generated.
>
> Prove $a\_n = \frac{n-2}{n}+\frac{1}{n}\sum\_{i=0}^{n-1}(a\_{i}+a\_{n-i-1})$ using mathematical induction.

I have no idea where to start as I don't even know how to construct a proper equation to carry on the proof. Any help is appreciated.

# Answer
If the array has length $n = 1$ then the constructed tree consists just of a root. Therefore $a\_1 = 0$. Similarly, $a\_0 = 0$ (this is a corner case).

Now suppose that $n \geq 2$. Without loss of generality, assume that $x = 1$, and so $y = n$. The array splits into two halves: $1,\ldots,r-1$ and $r+1,\ldots,n$. The first has length $r-1$, and the second has length $n-r$. If $r = 1$ or $r = n$, the one of these halves is empty; this happens with probability $\frac{2}{n}$. So with probability $\frac{n-2}{n}$, the root has two children. Defining $i = r-1$, we see that $i$ is chosen uniformly among the $n$ options $0,\ldots,n-1$, and the two subarrays have lengths $i,n-1-i$. From here it is straightforward to deduce your formula, using linearity of expectation.

Your formula simplifies to $$ a\_n = \frac{n-2}{n} + \frac{2}{n} \sum\_{i=0}^{n-1} a\_i. $$ This implies that $$ (n+1)a\_{n+1} - na\_n = n-1 + 2 \sum\_{i=0}^n a\_i - (n-2) - 2 \sum\_{i=0}^{n-1} a\_i = 1 + 2a\_n, $$ and so $$ a\_{n+1} = \frac{n+2}{n+1} a\_n + \frac{1}{n+1} \Longrightarrow a\_{n+1} - a\_n = \frac{a\_n}{n+1} + \frac{1}{n+1}. $$ Now \begin{multline} a\_{n+2} - a\_{n+1} = \frac{a\_{n+1}}{n+2} + \frac{1}{n+2} = \frac{a\_n}{n+1} + \frac{1}{(n+1)(n+2)} + \frac{1}{n+2} =\\ \frac{a\_n}{n+1} + \frac{1}{n+1} = a\_{n+1} - a\_n. \end{multline} In other words, $a\_n$ is an arithmetic progression. You can check that $a\_n = \frac{n-2}{3}$ for $n \geq 2$.
> 1 votes

---
Tags: binary-trees, induction, mathematical-foundations
---


# Question
Title: Which of these properties hold for all FO theories? (but not regarding fragments thereof)
Which of these properties hold for all FO theories? (but not regarding fragments thereof)

a. Decidable

b. At least expressive as propositional logic

c. NP-complete

a) Decidable: no, some first order theories are not decidable.

b) Propositional logic lacks expressiveness, so possibly yes. However, are hence all FO theories more expressive than propositional logic?

c) NP-complete: An undecidable FO-theory is not NP-complete

Are a) and c) correct? How about b), is there a counter example?

# Answer
Your answers to (a) and (c) are correct. To tell whether (b) is correct we need a precise notion of expressiveness.

The issue is that propositional logic and first-order logic have totally different semantics: their notions of "model" are *valuation* and *structure* respectively. When two logics use the same notion of "model" we can straightforwardly compare their expressive powers by looking at what sets of models their sentences can pin down respectively. For example, SOL is strictly more expressive than FOL since there is an SOL-sentence whose class of models is not the class of models of any FOL-sentence (e.g. take an SOL-sentence whose models are exactly the finite structures, and observe via compactness that no FOL-sentence can do this). But this direct comparison idea doesn't even make sense for FOL vs. propositional logic.

Now for the specific question you ask, due to the fact that you look at **all FOL theories** this is arguably a moot point since there is a particular FOL-theory which is extremely simple, namely it only has two formulas up to semantic equivalence and it is linear-time decidable:

> Take the theory in the empty language of a one-element pure set.

*(Of course if you allow inconsistent theories this is even easier, but that seems silly. Incidentally note that $(i)$ the example above really does have to be that "small" per here and here, and $(ii)$ this also addresses (c).)*

Since propositional logic isn't that simple, it's pretty clear that this is an FOL-theory which is not as expressive as propositional logic in any meaningful sense. But I think it's still worth highlighting this ambiguity, since there will be less trivial situations where we want to compare very different logics and there we will absolutely need a precise definition to say anything.
> 1 votes

---
Tags: reductions, logic, satisfiability, smt-solvers
---


title: Inductive proof for Euclid's algorithm

text:
# Question
Title: Inductive proof for Euclid's algorithm
I'm studying *The Algorithm Design Manual* and the proof exercises of the first chapter are really hard(at least for a first-timer). I asked a question on here about the previous question in the exercises two days ago and I still haven't been able to go through the whole page.

Anyway, I'm trying to inductively prove Euclid's algorithm(I'm think the deductive proof is simpler but I want to familiarize myself with Inductive proofs). No matter how I approach the problem, I just prove the algorithm in a deductive way that doesn't require induction in any way.

I would really appreciate if you could give an inductive proof of Euclid's algorithm or provide me with a resource that does so.Thanks in advance.

```
The greatest common divisor of positive integers x and y is the largest integer
d such that d divides x and d divides y. Euclid’s algorithm to compute gcd(x, y)
where x > y reduces the task to a smaller problem:

gcd(x, y) = gcd(y, x mod y)

Prove that Euclid’s algorithm is correct.

```

Edit:

The deductive proof that I know of is as follows:

A. given that a,b,c,y,x are all integers we can prove: a|b ^ a|c → a|(xb + yc)

B. p,q,r and t = (pr + q) are all integers.we want to prove gcd(pr+q,p)=gcd(p,q) let m = gcd(pr+q,p) and n = gcd(p,q) since A, n|p ^ n|q → n|pr + q n is a common divisor of (pr+q,p) and m is the greatest common divisor of (pr+q,p) therefore, m \>= n.

C. P: m|p which we know is true Q: m|(pr + q) which is also true R: m|q we know that m|p ^ m|q → m|pr + q is true, so based on this and P,Q and R we can deduce that R is true.

m is a common divisor of (p,q) and n is the greatest common divisor of (p,q) therefore, n \>= m.

B is true Q is true B ^ Q → m = n is also true.

therefore, m = n

gcd(pr+q,p) = gcd(p,q)

# Answer
> 1 votes
Here is Euclid's algorithm.

The input is two integers $x \geq y \geq 1$.

While $x \> y$, the algorithm replaces $x,y$ with $y, x\bmod y$.

The final output is $x$.

In order to prove that this algorithm correctly computed the GCD of $x$ and $y$, you have to prove two things:

* The algorithm always terminates.
* If the algorithm terminates, then it outputs the GCD (partial correctness).

The first part is proved by showing that $x + y$ always decreases throughout the loop. The second part is proved by induction, using the equation $$ \mathit{gcd}(x,y) = \mathit{gcd}(y,x\bmod y). $$ Both parts also use the loop invariant $x \geq y \geq 1$.

What you call the "deductive proof" is only part of the proof of partial correctness. It forms the main technical part inside a proof by induction on the number of iterations.

---
Tags: algorithms
---


# Question
Title: Min weighted edge cover - is the greedy algorithm sub-optimal?
The post here: Solving the min edge cover using the maximum matching algorithm provides a way to obtain the min edge cover from a maximum matching by greedily adding edges on top of the maximum matching until all vertices are covered. Now, thinking about the min-weighted edge cover problem, it would seem this approach can be extended. First, find the minimum weighted matching with maximum edges, and then add edges of the smallest weight greedily, smallest weight ones first.

However, reading section 19.3 of the book "Combinatorial optimization: polyhedra and efficiency" by Schrijver, a more complicated algorithm is presented. This makes it seem like my approach above is sub-optimal. Is it possible to find a counter-example, preferably on a bi-partite graph where my greedy algorithm would fail to provide an optimal solution? I haven't been able to find one with some toy graphs.

# Answer
> 1 votes
Here is a counterexample to your proposed algorithm:

The optimal solution consists of 3 edges and costs 3+1+1=5, but the min-cost maximum-cardinality matching, which consists of 2 edges and costs 3+3=6, will be chosen by the first step of your algorithm and immediately returned, as it is already a solution. (The only other maximum-cardinality matching costs 1+6=7.)

---
Tags: graphs, optimization, combinatorics
---


# Question
Title: How do we know that $F^{n + 1}(\overrightarrow{\emptyset}) = F(F^n(\overrightarrow{\emptyset}))$?
I am currently studying the textbook *Principles of Program Analysis* by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter **1.3 Data Flow Analysis** says the following:

> **The least solution.** The above system of equations defines the twelve sets $$\text{RD}\_\text{entry}(1), \dots, \text{RD}\_{\text{exit}}(6)$$ in terms of each other. Writing $\overrightarrow{RD}$ for this twelve-tuple of sets we can regard the equation system as defining a function $F$ and demanding that: $$\overrightarrow{RD} = F(\overrightarrow{RD})$$ To be more specific we can write $$F(\overrightarrow{RD}) (F\_\text{entry}(1)(\overrightarrow{RD}), F\_\text{exit}(1)(\overrightarrow{RD}), \dots, F\_\text{entry}(6)(\overrightarrow{RD}), F\_\text{exit}(6)(\overrightarrow{RD}))$$ where e.g.: $$F\_\text{entry}(3)(\dots, \overrightarrow{RD}\_\text{exit}(2), \dots, \overrightarrow{RD}\_\text{exit}(5), \dots) = \overrightarrow{RD}\_\text{exit}(2) \cup \overrightarrow{RD}\_\text{exit}(5)$$ It should be clear that $F$ operates over twelve-tuples of sets of pairs of variables and labels; this can be written as $F : (\mathcal{P}(\mathbf{\text{Var}\_\star \times \mathbf{\text{Lab}\_\star}))}^{12} \to (\mathcal{P}(\mathbf{\text{Var}\_\star \times \mathbf{\text{Lab}\_\star}))}^{12}$ where it might be natural to take $\mathbf{\text{Var}\_\star} = \mathbf{\text{Var}}$ and $\mathbf{\text{Lab}\_\star} = \mathbf{\text{Lab}}$. However, it will simplify the presentation in this chapter to let $\mathbf{\text{Var}\_\star}$ be a *finite* subset of $\mathbf{\text{Var}}$ that contains the variables occurring in the program $\mathbf{S\_\star}$ of interest and similarly for $\mathbf{\text{Lab}\_\star}$. So for the example program we might have $\mathbf{\text{Var}\_\star} = \\{ x, y, z \\}$ and $\mathbf{\text{Lab}\_\star} = \\{ 1, \dots, 6, ? \\}$.
>
> It is immediate that $(\mathcal{P}(\mathbf{\text{Var}\_\star \times \mathbf{\text{Lab}\_\star}))}^{12}$ can be partially ordered by setting $$\overrightarrow{\text{RD}} \sqsubseteq \overrightarrow{\text{RD}}^\prime \ \ \ \text{iff} \ \ \ \forall i : \text{RD}\_i \subseteq \text{RD}\_i^\prime$$ where $\overrightarrow{\text{RD}} = (\text{RD}\_1, \dots, \text{RD}\_{12})$ and similarly $\overrightarrow{\text{RD}}^\prime = (\text{RD}\_1^\prime, \dots, \text{RD}\_{12}^\prime)$. This turns $(\mathcal{P}(\mathbf{\text{Var}\_\star \times \mathbf{\text{Lab}\_\star}))}^{12}$ into a complete lattice (see Appendix A) with least element $$\overrightarrow{\emptyset} = (\emptyset, \dots, \emptyset)$$ and binary least upper bounds given by: $$\overrightarrow{\text{RD}} \sqcup \overrightarrow{\text{RD}}^\prime = (\text{RD}\_1 \cup \text{RD}\_1^\prime, \dots, \text{RD}\_{12} \cup \text{RD}\_{12}^\prime)$$
>
> It is easy to show that $F$ is in fact a monotone function (see Appendix A) meaning that: $$\overrightarrow{\text{RD}} \sqsubseteq \overrightarrow{\text{RD}}^\prime \ \ \ \text{implies} \ \ \ F(\overrightarrow{\text{RD}}) \sqsubseteq F(\overrightarrow{\text{RD}})^\prime$$ This involves calculations like $$\text{RD}\_\text{exit}(2) \subseteq \text{RD}\_\text{exit}^\prime(2) \ \ \text{and} \ \ \text{RD}\_\text{exit}(5) \subseteq \text{RD}\_\text{exit}^\prime(5)$$ imply $$\text{RD}\_\text{exit}(2) \cup \text{RD}\_\text{exit}(5) \subseteq \text{RD}^\prime\_\text{exit}(2) \cup \text{RD}\_\text{exit}^\prime(5)$$ and the details are left to the reader.
> Consider the sequence $(F^n(\overrightarrow{\emptyset}))\_n$ and note that $\overrightarrow{\emptyset} \sqsubseteq F(\overrightarrow{\emptyset})$. Since $F$ is monotone, a straightforward mathematical induction (see Appendix B) gives that $F^n(\overrightarrow{\emptyset}) \sqsubseteq F^{n + 1}(\overrightarrow{\emptyset})$ for all $n$. All the elements of the sequence will be in $(\mathcal{P}(\mathbf{\text{Var}\_\star \times \mathbf{\text{Lab}\_\star}))}^{12}$ and since this is a finite set it cannot be the case that all elements of the sequence are distinct so there must be some $n$ such that: $$F^{n+1}(\overrightarrow{\emptyset}) = F^n(\overrightarrow{\emptyset})$$ But since $F^{n + 1}(\overrightarrow{\emptyset}) = F(F^n(\overrightarrow{\emptyset}))$ this just says that $F^n(\overrightarrow{\emptyset})$ is a *fixed point* of $F$ and hence that $F^n(\overrightarrow{\emptyset})$ is a solution to the above equation system.

I am confused by this part:

> But since $F^{n + 1}(\overrightarrow{\emptyset}) = F(F^n(\overrightarrow{\emptyset}))$ this just says that $F^n(\overrightarrow{\emptyset})$ is a *fixed point* of $F$ and hence that $F^n(\overrightarrow{\emptyset})$ is a solution to the above equation system.

How do we know that $F^{n + 1}(\overrightarrow{\emptyset}) = F(F^n(\overrightarrow{\emptyset}))$, and how does this then imply that $F^n(\overrightarrow{\emptyset})$ is a *fixed point* of $F$ and therefore that $F^n(\overrightarrow{\emptyset})$ is a solution to the above equation system?

I've read a number of seemingly relevant facts, but I'm struggling to put them together to clarify my above confusion. In **Appendix A.1 Basic Definitions**, the textbook (see the above link) says that $\perp = \sqcup \emptyset = \sqcap L$ is the *least element*. And, in the above excerpt, the authors tell us that $(\mathcal{P}(\mathbf{\text{Var}\_\star \times \mathbf{\text{Lab}\_\star}))}^{12}$ is a complete lattice with least element $\overrightarrow{\emptyset} = (\emptyset, \dots, \emptyset)$. Then, in **Appendix A.4 Fixed Points**, the textbook says that, if $L$ satisfies the Ascending Chain Condition, then there exists $n$ such that $f^n (\perp) = f^{n + 1} (\perp)$ and hence $\text{lfp}(f) = f^n(\perp)$, where lfp stands for "least fixed point".

# Answer
In this case, the notation $F^n$ denotes iterated composition, that is, repeatedly applying the function $F$, for $n$ iterations:

* $F^0(x) = x$.
* $F^1(x) = F(x)$.
* $F^2(x) = F(F(x))$.
* $F^3(x) = F(F(F(x)))$.
* $F^4(x) = F(F(F(F(x))))$.
* $F^5(x) = F(F(F(F(F(x)))))$.

And so on.

---

There are two common ways to define function iteration inductively: \begin{align} F^0(x) &= x, & F^{n+1}(x) &= F^n(F(x)) \\ F^0(x) &= x, & F^{n+1}(x) &= F(F^n(x)) \end{align} Both definitions are equivalent, and you can show the following property under both: $$F^{i+j}(x) = F^i(F^j(x))$$

---

Now suppose that $F^n(x) = F^{n+1}(x)$, and let $y = F^n(x)$. Then $$ F(y) = F(F^n(x)) = F^{n+1}(x) = y, $$ and so $y$ is a fixed point of $F$ (which, by definition, is an element $y$ such that $F(y) = y$).
> 2 votes

---
Tags: partial-order, data-flow-analysis, lattices, order-theory, fixed-point
---


title: Circular path visiting fewest nodes

text:
# Question
Title: Circular path visiting fewest nodes
I don't know what this problem is called, so I haven't been able to Google for it, but I have a graph problem that I feel must have been solved many times before, and I just cannot find a good solution.

Given a directed graph, and nodes A and B, I want to find a route that takes me from A to B and back to A again, going through the fewest number of nodes. I have attempted to solve it with various versions of the shortest path problem, but it doesn't get me there. There could be a short path \[A\]-\>\[1\]-\>\[2\]-\>\[B\] from A to B, and one \[B\]-\>\[3\]-\>\[4\]-\>\[A\], that I can stitch together to get a tour that visits four nodes besides A an B (the nodes 1, 2, 3, and 4). But there might also be longer paths, \[A\]-\>\[x\]-\>\[y\]-\>\[z\]-\>\[B\] and \[B\]-\>\[z\]-\>\[y\]-\>\[x\]-\>\[A\] that ends up only visiting three nodes, because the paths overlap.

If I try to use a standard shortest-path approach, my thinking was to conceptually double the graph, so edges out of B would go into a copy of the graph, and look for the shortest path from A to A' where A' is the copy of node A. That gives me a shortest path cycle, but if I visit the same node going from B to A as I do going from A to B, then it counts as much as visiting a new node, where it should be free. The cost of visiting a node in the "copied" graph depends on the path I took in the first graph, and if I start carrying that information with me, the heap I use for finding the shortest path has to remember not only a node but a path. The state-space explodes, and so does the running time.

I am not convinced that this is something that has an efficient solution, and I might be able to brute-force something with a branch-and-bound approach that does track paths, changing the scoring of nodes in the "copied" graph. But before I start thinking along that path (no pun intended), I would like to know that I am not missing something trivial and that the problem has an efficient solution.

I would greatly appreciate any pointers to how to attack this problem, or just confirmation that it might be a problem that doesn't *have* an efficient solution, so I can give up on trying to find one.

# Answer
Consider a directed cycle from $A$ to $B$ and back with the minimum number of nodes, and subject to that, with the minimum number of edges. The directed cycle is composed of two paths: $A\to B$ and $B\to A$. Since the cycle minimizes the number of edges, these paths are simple. However, it may be that the two paths are not disjoint. If so, let $x$ be the first node on $B\to A$ which appears in $A\to B$. This decomposes the cycle as follows: $$ A\to x \to B \to x \to A. $$ By construction, the cycle $x \to B \to x$ is simple (no nodes are repeated). Also, the condition on the number of edges guarantees that all nodes on this cycle do not appear in $A\to x$ or $x \to A$ (otherwise, we could take shortcuts that would shorten the cycle). Therefore, if we denote the optimal cost of an $A\to B\to A$ cycle by $c(A,B)$ (excluding the two endpoints) and the optimal cost of a *simple* $A\to B\to A$ cycle by $s(A,B)$, we have $$ c(A,B) = \min(s(A,B), \min\_x c(A,x) + s(x,B) + 1). $$ We can compute $c(A,B)$ iteratively: start with $c(A,B) = s(A,B)$ (which you know how to compute), and then repeatedly apply the equation above until the situation stabilizes, which should happen within $n$ iterations or so.
> 1 votes

---
Tags: graph-traversal, directed-graphs
---


# Question
Title: Can a classical supercomputer solve a large Max-Cut Problem?
The Fugaku is the most powerful computer. Its performance is 442,010 TFlop/s. That number does not mean much to a layman like me. I want to know how fast it can solve a hard problem. For example, can it solve the Max-Cut Problem of 1,000 vertices in minutes, hours,...,years?

By the way, what is the best record of solving the Max-Cut Problem by any classical computers?

# Answer
> 1 votes
It's not that straightforward. NP-hardness means *worst case intractability*. This means that there are plenty of easy instances of Max-Cut with a huge number of vertices (i.e. much more than just one thousand), but also rather tiny instances that are extremely hard in practice. So you can't measure hardness by the size of an instance.

If you want to see examples & runtimes, have a look at the results from the yearly competitions around the Boolean satisfiability problem (SAT).

---
Tags: np-complete, high-performance-computing
---


# Question
Title: Prove that any subtree in a red-black tree has at least $2^{bh(x)} -1$ internal nodes
I'm reading the book *Introduction to Algorithms*. In the book, in the initial step of proving that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$, they prove that any subtree rooted at any node $x$ in a red-black tree has at least $2^{bh(x)} -1$ internal nodes. However I couldn't wrap my head around this proof.

They do an induction where this holds for the base case when $x$ is a leaf by $2^{bh(x)}-1 = 2^0 - 1 = 0$. However, when they do the induction, they say that *a child of node $x$* has at least $2^{bh(x)-1}-1$ internal nodes (by the way isn't the correct way to put is to start with *subtree rooted at a child of node $x$...*?). This part confuses me a little bit, is it too trivial to say that it has $2^{bh(x)-1}-1$ nodes given that $bh(x)$ is the black-height (the number of black nodes on any simple path from a node not including itself), or is this related to the rules of the red-black tree which are:

> 1. Every node is either red or black.
> 2. The root is black.
> 3. Every leaf (NIL) is black.
> 4. If a node is red, then both its children are black.
> 5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

# Answer
> 0 votes
It turns out trivial. I think I found the answer myself. First of all, $bh(x)$ gives us the black-height rooted from the node x. A subtree rooted from node x, in the worst case (in terms of the number of nodes it has) should not include any red nodes. Any node should be there in order to satisfy the $bh(x)$ number and nothing more. In that case we would boil down to a perfect subtree of the height $bh(x)$ and we now that a perfect binary tree has $2^{bh(x)}-1$ nodes. This is the least number of nodes it can have.

The subtlety in the question is that since we are considering the child of a node x that has $bh(x)$, it has at least $2^{bh(x)-1}-1$ nodes due to the possibility of losing 1 black-height by walking from x to its child.

PS: Even though what i wrote above seems sensible to me and maybe gives insight to the lemma even without the need of induction, after a little bit of careful reading, that claim is nothing but the just the induction hypothesis that holds for the leafs and propagates to the top of the three.

---
Tags: red-black-trees
---


# Question
Title: In counterfactual regret minimization, why are additions to regret weighted by reach probability?
I'm reading the algorithm on page 12 of An Introduction to Counterfactual Regret Minimization. On lines 25 and 26, we accumulate new values into $r\_i$ and $s\_i$:

* $25.\space \space r\_I\[a\] ← r\_I\[a\] + \pi\_{-i} . (v\_{\sigma I \rightarrow a}\[a\] - v\_{\sigma}\[a\])$
* $26. \space \space s\_I\[a\] ← s\_I\[a\] + \pi\_{i} . \sigma^t(I, a)$

$r\_I\[a\]$ is the accumulated regret for information set $I$ and action $a$. $s\_I\[a\]$ is the accumulated strategy for information set $I$ and action $a$.

$\pi\_{i}$ is the probability of reaching this game state for the learning player (for whom we're updating strategy and regret values in the current CFR iteration). $\pi\_{-i}$ is the probability of reaching this game state for the other player.

Why do we multiply by $\pi\_{-i}$ and $\pi\_{i}$ to accumulate the strategy and regret on lines 25 and 26? Couldn't we just do this:

* $25.\space \space r\_I\[a\] ← r\_I\[a\] + (v\_{\sigma I \rightarrow a}\[a\] - v\_{\sigma}\[a\])$
* $26. \space \space s\_I\[a\] ← s\_I\[a\] + \sigma^t(I, a)$

It seems to me it doesn't matter exactly how much we adjust the strategy and regrets in this CFR iteration—so long as we do enough CFR iterations, won't we end up with good values for $r\_I$ and $s\_I$ in the end?

# Answer
Algorithm 1, which I refer to in the question, produces a strategy that minimizes **cumulative counterfactual regret**.

The motivation is to get a strategy which minimizes **overall regret** (as defined earlier in the paper). That's because such a strategy approximates a nash equilibrium strategy.

In other words, cumulative counterfactual regret was designed to be:

* computable with a reasonable runtime; and
* an upper bound on overall regret, so that minimizing cumulative counterfactual regret minimizes overall regret.

In Regret Minimization in Games with Incomplete Information it is proven that overall regret is bounded by cumulative counterfactual regret. I'm reading through the proof currently, and will update this answer with an intuitive explanation if possible.

But for future readers who come across this, reading that proof could be a promising direction for understanding the motivation behind Algorithm 1 and the underlying formulas.
> 1 votes

---
Tags: artificial-intelligence, probability-theory, game-theory
---


# Question
Title: Is occurrence typing (flow-sensitive typing) a form of dependent typing?
I take occurrence typing to be typing that "... allows the type system to ascribe more precise types based on whether a \[check\] succeeds or fails." (adapted from the Racket docs with "predicate check" replaced with "check")

Here's a TypeScript example:

```
function foo(x: string | number) {
    switch (typeof x) {
        case "string":
            // the type of x is `string` here:
            x.length
            break
         case "number":
            // the type of x is `number` here:
            x * 3
            break
    }
}

```

playground link

I take "dependent types" to mean "types that depend on terms". reference reference

The type of `x` (a type) depends on `x` (a term). So is there dependent typing in the example above? More generally, is occurrence typing a form of dependent typing?

I could see an argument that the answer is "no" if we interpret "dependency" such that it is expressed via binding. So then a "dependent type" would be a type `T x` where `T` is a type and `x` is a term. But then maybe even on this definition occurrence typing counts as dependent typing, if we allow T to be something fancy like a type-level `x -> if x is a string then string else number`.

# Answer
> 1 votes
No, I would not consider this a dependent type. The type of `x` does not depend on the value of `x`.

I suppose you could say that the type of the expression `x` depends on the type of the variable `x`, but that doesn't make this dependent typing.

You link to Wikipedia, but the Wikipedia article on dependent types say "a dependent type is a type whose definition depends on a value" and says " The return type of a dependent function may depend on the *value* (not just type) of one of its arguments" and "A dependent pair may have a second value of which the type depends on the first value". Here the type of `x` does not depend on values; only on the types of the variables. Beware that these English sentences describing terms like "dependent types" or "occurrence types" are not to be taken too seriously and you need to look at the precise mathematical formalism if you want to be precise.

I would not consider the feature you describe as dependent typing. Rather, I would consider it an instance of flow-sensitive typing.

---
Tags: type-checking, dependent-types
---


# Question
Title: Find sets of weighted objects to maximize number of sets with weight >= X
I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number of objects.

1). What is a fast and correct algorithm to solve this?
2). Is this NP-complete, hard, or neither?

Ideally, I'd want the left over set of objects that does not add up to x to be maximal as well, but would settle for an understanding of how to solve the problem without this.

# Answer
> 1 votes
This problem is NP-hard as it can be seen by a reduction from $3$-partition.

In the $3$-partition problem we are given a (multi-)set $\mathcal{S}$ containing $3n$ positive integers $x\_1, \dots, x\_{3n}$ and the goal is that of deciding whether there exists a partition of $\mathcal{S}$ into $n$ sets $S\_1, \dots, S\_n$ of $3$ elements each, such that, for each $i$, $\sum\_{x \in S\_i} x = T$, where $T = \frac{1}{n} \sum\_{i=1}^{3n} x\_i$.

It is known that this problem remains NP-hard even when each $x\_i$ is strictly between $T/4$ and $T/2$. We will therefore restrict to such instances.

To obtain an instance of your problem, it suffices to use the same set of integers $\\{ x\_1, \dots, x\_{3n} \\}$ (i.e., $N=3n$) with $X = T$. Clearly, since the sum of any two input elements can be at most $2 \cdot (\frac{T}{2}-1) \< T = X$, we have that, in any partition $\mathcal{P}$ of $\\{ x\_1, \dots, x\_{3n} \\}$, the number of sets $S \in \mathcal{P}$ such that $\sum\_{x \in S} x \ge X$ can be at most $N/3 = n$.

If the answer to the 3-partition instance is "yes", then the same partition $S\_1, \dots, S\_n$ exactly matches this upper bound in the instance of your problem. On the other hand, if the answer to the 3-partition instance is "no", then in any partition of $\\{ x\_1, \dots, x\_{3n} \\}$ there is at most one set with sum smaller than $T$, i.e., there are at most $n-1$ sets with sum at least $T$.

To summarize: the answer to the instance of $3$-partition is yes if and only if the optimal solution to the corresponding instance of your problem has measure at least $n$.

Your problem is not NP-complete since it does not belong to NP (since it is not a decision problem). Unless P=NP there is no efficient (polynomial-time) algorithm for your problem.

---
Tags: algorithms, optimization, combinatorics, sets, weighted-graphs
---


title: PRECISE DPLL algorithm definition

text:
# Question
Title: PRECISE DPLL algorithm definition
I am confused about the precise definition of the DPLL algorithm. Various sources tend to define DPLL differently:

1. In pages 110-114 of the book Handbook of Satisfiability(Editors: Biere, A., Heule, M., Van Maaren, H., Walsh, T. Feb 2009. Volume 185 of Frontiers in Artificial Intelligence and Applications) it defines it as backtracking + unit propagation.

Also can be accessed from: http://reasoning.cs.ucla.edu/fetch.php?id=97&type=pdf (pages 106-110).

2. In wikipedia: https://en.wikipedia.org/wiki/DPLL\_algorithm#:~:text=In%20logic%20and%20computer%20science,solving%20the%20CNF%2DSAT%20problem. it defines it as backtracking + unit propagation + pure literal elimination.
3. And in original 1962 paper: https://archive.org/details/machineprogramfo00davi/page/n5/mode/2up it mentions 3 rules: one-literal clause rule(unit propagation), affirmitive-negative rule(pure literal elimination) and rule for eliminating atomic formulas(creating resolvents).

Therefore, I am looking for a clear and strict definition of DPLL algorithm. Maybe it should be considered as purely backtracking algorithm and unit propagation and pure literal elimination as its extensions? Or maybe unit propagation is essential part of the algorithm and pure literal elimination is considered to be extention..?

# Answer
> 1 votes
What you are finding is that there are multiple versions of DPLL, all of which might have the name DPLL attached to them, even though they are a little different in some specifics. If you need to distinguish between them, then I suggest you introduce your own terminology. I don't think it really matters which one you call the "one true DPLL algorithm". If you have to pick one, you could use the specification in the original paper, but I suspect it's probably best to understand "DPLL" as referring to a family of closely related algorithms that are very similar to each other but not identical.

"backtracking + unit propagation" is not a definition of an algorithm; it is at best a high-level summary.

# Answer
> 1 votes
I have only one thing to add to D.W.'s answer which is worth considering. This is Wikipedia's pseudocode for DPLL:

```
function DPLL(Φ)
    if Φ is a consistent set of literals then
        return true;
    if Φ contains an empty clause then
        return false;
    for every unit clause {l} in Φ do
        Φ ← unit-propagate(l, Φ);
    for every literal l that occurs pure in Φ do
        Φ ← pure-literal-assign(l, Φ);
    l ← choose-literal(Φ);
    return DPLL(Φ ∧ {l}) or DPLL(Φ ∧ {not(l)});

```

Now consider what would happen if `choose-literal` always chose a pure literal if were it available:

```
function DPLL(Φ)
    if Φ is a consistent set of literals then
        return true;
    if Φ contains an empty clause then
        return false;
    for every unit clause {l} in Φ do
        Φ ← unit-propagate(l, Φ);
    l ← choose-literal(Φ);
    if l is a pure literal then
        return DPLL(Φ ∧ {l});
    else
        return DPLL(Φ ∧ {l}) or DPLL(Φ ∧ {not(l)});

```

Are they *really* different algorithms?

---
Tags: algorithms, definitions
---


# Question
Title: How to solve cubing, batching, and routing problem together?
I am working on an order picking project, which requires to cube the items into several totes in a trolley, then batching the totes, followed by parallel aisle picking/routing.

The input data has some orders with items. Items have locations, 3 dimensions. Each tote has the same size. One trolley can fit 4 totes.

The cubing part could just use approximate volume.

The goal is to create batches with planned picking route.

The size of the problem: about 50-80 items per order. 5-10 orders during the picking window.

The problem is intertwined if we want to minimize the distance. Should the cubing part solved separately without considering the batching and routing? If so, is this a VRP?

I assumed the cubing is a bin backing/multiple knapsack problem, and is first fit algorithm good enough? Which heuristic performs better?

# Answer
> 0 votes
First, you need to understand how you are going to pick. That means, in one tote, do you want only one order or multiple items of different orders can end up into one tote. If it is latter, is there any sorting or consolidation area to separate out?

Is it like one order must go into one carton?

After we have those answers, I would always prefer first cubing and then, according to our strategy, pick them, and for the optimal path, obviously use VRP.

Prefer using https://or.stackexchange.com/

---
Tags: optimization, routing
---


# Question
Title: Store a n-bit string using only O(log n) space
Is it possible to somehow store a $n$ bit string using only $\mathcal{O}(\log{n})$ space? I am thinking if the string could be stored using a hash function, but I am not sure if it is even possible.

# Answer
> 4 votes
There are $2^n$ many $n$-bit strings, but only polynomially many strings of length $O(\log n)$.

# Answer
> 1 votes
When you say "store", I suppose you're also expecting to be able to retrieve the original string based on the shorter string, right?

If so, then the answer is a categorical no. And not only to log(n), but even to n-1.

Theorem: it is not possible to construct a program that reversibly converts *all* possible strings of length n to strings of length m, where m\<n.

Proof by contradiction: let's suppose there was a program that could reversibly convert all strings of size n, to strings of size m. There are 2^n inputs, and 2^m outputs, where 2^n \< 2^m. But in order to revert the conversion, there must be at least two outputs that revert to the same input, therefore the conversion is not reversible.

This proof is another way of explaining the pigeonhole principle: you cannot put 10 pigeons in 9 pigeonholes, without using at least one of the pigeonholes at least twice.

A lot of people seem to be surprised by this. Isn't storing data in a smaller size the entire point of lossless compression? Compressors are based on finding patterns that can be stored with less data, but ultimately, the same theorem proves that it is not possible to create a program that can losslessly compress *all* possible inputs to a smaller size.

---
Tags: space-complexity, hash
---


# Question
Title: Beta reduction of S combinator in pure lambda calculus
S is defined as `S x y z = x z (y z)`

This suggest that `(y z)` should be evaluated just after `x z` and the the results of `x z` is applied to the results of `(y z)`.

I'm implementing call by value in lambda calculus, I would need to support parenthesis when evaluating this expression right? Does this affect the results? I thought that the order would not matter, so why the parenthesis in `(y z)`?

Regards

# Answer
> 4 votes
Parentheses matter. Honestly, if you are unclear about how $\lambda$-calculus works, it is going to be rather hard to implement it.

Here is an explicit counter-example: $$(K S)(K S) = S$$ but $$K S K S = ((K S) K) S = S S \neq S.$$

I would recommend learning about parsers, abstract syntax trees, and other bits and pieces that make up an implementation of a programming language.

An example of the implementation of the $\lambda$-calculus is available as `lambda` at PL Zoo. See `repl-in-browser` for an implementation that runs in the browser (an instance of which is available here).

---
Tags: lambda-calculus, combinatory-logic
---


# Question
Title: CFG to CFL conversion (production rule with both left and right recursion)
Is there a general rule to convert a CFG to its CFL?

For example, how do I approach the following question?

> What is the language generated by the following CFG? $$ S \to aS \mid Sb \mid \epsilon $$

As per my understanding, $S\to aS$ is $a^\*$ and $S\to Sb$ is $b^\*$.

But how do I make sure that the language is $a^\* b^\*$ without having to derive a lot of strings?

In particular, is there a way to make it either in left or right recursion, so that it is easier to understand the structure?

# Answer
> 1 votes
> Is there a general rule to convert a context-free grammar to a context-free language?

The answer depends on what you mean by "context-free language". A context-free grammar is one way to describe context-free languages, so in some sense the answer is a trivial "yes" – a context-free grammar is already a description of a context-free language.

Presumably you are interested in a more explicit description. In this case, the answer is probably "no", though it's impossible to tell unless you define your problem formally. The reason for the negative answer is the following undecidability result: given a context-free grammar over an alphabet $\Sigma$, determining whether it generates $\Sigma^\*$ is undecidable.

> How do I make sure that the language is $a^\* b^\*$ without having to derive a lot of strings?

In mathematics, the way to know things for sure is to *prove* them.

> Is there a way to make it either in left or right recursion so that it is easier to understand the structure?

If a grammar contains only left-recursion or only right-recursion, then it is a left-regular grammar or a right-regular grammar, respectively (actually, whether this is true depends on what you mean by *left-recursion* and *right-recursion*, so I am making a guess). (Another common term is left-linear/right-linear grammar.) Such a grammar generates a regular language. Given that it is undecidable whether a given context-free grammar generates a regular language, there is no simple transformation that can change an arbitrary context-free grammar into one with only left-recursion or only right-recursion.

A grammar mixing left-linear and right-linear rules is known as *linear*; such grammars describe *linear languages*, a sub-class of all context-free languages which contains non-regular languages such as $\\{a^nb^n \mid n \geq 0\\}$, generated by $S \to aT \mid \epsilon, \\, T \to Sb$.

It seems that even determining whether a given linear grammar describes a regular language is undecidable, see the comments to this answer by J.-E. Pin.

---
Tags: context-free
---


title: Prove that ${NP}^{NP}=\Sigma_2$

text:
# Question
Title: Prove that ${NP}^{NP}=\Sigma_2$
I've head the lecture today and we saw this theorem:

> $\mathsf{NP}^{\mathsf{NP}}=\Sigma\_2$

But without a proof.

Here are the definitions I use:

A language $L$ belongs to $\Sigma\_k$ if there is a deterministic Turing machine $M(x,y\_1,y\_2,\dots,y\_k)$ such that:

* There exists a constant $c$ such that $|y\_i|=|x|^c$ and $M(x,y\_1,y\_2,\dots,y\_k)$ runs in time $\mathit{poly}(|x|)$.
* $x\in L$ iff $\exists\_{y\_1}\forall\_{y\_2}\exists\_{y\_3} \dots M(x,y\_1,y\_2,\dots,y\_k)=T$,
where the quantifiers are alternating between existential and universal, and start with existential.

$\mathsf{NP}^{\mathsf{NP}}$ is the class of all languages of languages in $\mathsf{NP}$ with oracle calls to a language in $\mathsf{NP}$.

I thought maybe to use $\mathsf{SAT}$ as it is an $\mathsf{NP}$-complete language.

Can someone please help me understand why this is true?

# Answer
> 3 votes
Suppose first that $L \in \Sigma\_2^P$. Then there exists a machine $T(x,y,z)$, running in time $\mathit{poly}(|x|)$, such that $$ x \in L \Leftrightarrow \exists y \forall z \\, M(x,y,z) = T $$ Using the reduction in Cook's theorem, given $x,y$, we can express $\exists z \\, M(x,y,z) = T$ as a SAT instance. Therefore given a SAT oracle, we can verify that $y$ satisfies $\forall z \\, M(x,y,z)$. This shows that $L \in \mathsf{NP}^{\mathsf{NP}}$.

In the other direction, suppose that $L \in \mathsf{NP}^{\mathsf{NP}} = \mathsf{NP}^{\mathsf{SAT}}$. There is thus an oracle Turing machine $M(x,y)$, running in time $\mathit{poly}(|x|)$, such that $$ x \in L \Leftrightarrow \exists y \\, M^{\mathsf{SAT}}(x,y) = T. $$ (The notation $M^{\mathsf{SAT}}$ means running $M$ with a SAT oracle.)

How can we tell that $M^{\mathsf{SAT}}(x,y) = T$ without access to a SAT oracle? The idea is to "guess" the answer of every SAT query, and prove the necessary information to verify this answer. Suppose that $M$ queries $q \stackrel?\in \mathsf{SAT}$. If $q \in \mathsf{SAT}$ then we can provide a witness for it, namely a satisfying assignment. If $q \notin \mathsf{SAT}$ then we know that every assignment does not satisfy $q$.

Accordingly, we construct a machine $M'(x,y',z')$ in the following way. The witness $y'$ consists of the original witness $y$, together with the following information: the number of SAT queries performed by $M$; for each SAT query $q\_i$, the answer $b\_i$; for each positive answer, the corresponding satisfying assignment $a\_i$. The "cowitness" $z'$ consists of an assignment $a\_i$ for each negative answer to a SAT query.

The machine $M'$ acts simulates $M$. Whenever $M$ makes a SAT query $q\_i$, it determines the answer from $y'$. If $b\_i = T$, it verifies that $a\_i$ is a satisfying assignment for $q\_i$. If $b\_i = F$, it verifies that $a\_i$ is *not* a satisfying assignment for $q\_i$. The new machine $M'$ accepts if all verifications succeed, and additionally $M$ accepts.

This shows that $L \in \Sigma\_2$, completing the proof of your statement.

---
Tags: complexity-theory
---


# Question
Title: Solving T(n) = 2*T(n-1)+4 witht the Master Theorem
I am wondering if there is a way to solve a recurrence time function with the master theorem if no $b$ exists. Like in this case. $$ T(n) = 2\times T(n-1)+4$$

# Answer
> 1 votes
By expansion you can see it is $T(n) = \Theta(2^n)$ (suppose $T(1) = 1$):

$$ T(n) = 2T(n-1) +4 = 2(2T(n-2)+4) + 4 = 2^2T(n-2) + 2\times 4 + 4 = \ldots = $$

$$ 2^{n-1}T(1) + 2^{n-2}4 + \cdots + 4 = 4\left(\sum\_{i=1}^{n-1}2^i\right) = 4(2^n - 1) $$

# Answer
> 1 votes
Let $S(n) = T(n)/2^n$. Then $$ S(n) = S(n-1) + \frac{4}{2^n}. $$ Since the series $\sum\_{n=1}^\infty \frac{4}{2^n}$ converges, we see that $S(n) = \Theta(1)$, and so $T(n) = \Theta(2^n)$.

---
Tags: time-complexity, master-theorem
---


# Question
Title: Solving $T(n)=3T(\lfloor \frac{n}{3}\rfloor) +2n\log n$
I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$ with base case $T(n) = 1$ if $n \leq 1$.

I am sure that the Master Theorem does not work. I am trying a lot with the substitution method, but I am very frustrated since I can't find a solid expression. Does any one have a good "hint" or good idea on how to solve this in a nice way?

# Answer
> 2 votes
Ignoring floors (see, e.g., the paragraph "Ignoring Floors and Ceilings Is Okay, Honest" in Chapter 1 of Algorithms for a discussion), your recurrence is of the form $$ T(n) = aT(n/b) + f(n), $$ with $a=b=3$ and $f(n) = 2 n \log n$.

You can then immediately apply the master theorem since, for $k=1$, $f(n) \in \Theta(n^{\log\_b a} \log^k n) = \Theta(n \log n)$.

The solution to the recurrence is then: $$ T(n) \in \Theta(n^{\log\_b a} \log^{k+1} n) = \Theta(n \log^2 n). $$

---
Tags: asymptotics, master-theorem
---


# Question
Title: Why $((+ 1) ((+ 1) 1))$ is not a $\delta-$redex?
I was reading http://barrywatson.se/lsi/lsi\_delta\_reduction.html, where

> ```
> ((+ 1) 2) →δ 3 is a δ-reduction.
> ((+ 1) ((+ 1) 1)) is a not a δ-redex.
>
> ```

Wouldn't $((+ 1) ((+ 1) 1)) \rightarrow ((+1) 2)) \rightarrow 3$?

# Answer
Because the definition of $\delta$-reduction requires that

> for all $1≤i≤n$, $N\_i$ is normalized

and the second argument $((+1) 1)$ is not normalized.

As you observe, we can first reduce the $\delta$-redex $((+1) 1)$ to $\delta$-normal form $2$; then $((+1) 2)$ is a $\delta$-redex which can be reduced to $\delta$-normal form $3$.
$((+ 1) ((+ 1) 1)) \triangleright\_\delta ((+1) 2)) \triangleright\_\delta 3$ is a correct reduction, but $((+ 1) ((+ 1) 1))$ isn't a redex in the first step; $((+ 1) 1)$ is.
> 3 votes

---
Tags: lambda-calculus
---


# Question
Title: Strengthening a given attack on discrete log
I am trying to prove the following claim:

> Let $(G,\*)$ be a cyclic group of size $m$ with generator $g$. Assume there exists some adversary $A'$ of size $T'=\frac{\left(T-O\left(\log m\right)\right)}{2}$, for some $T$, such that $$\mathbb{P}\_{b\gets G}\left\[A'(b)=\log\_{g}(b)\right\]\>\frac{1}{2}.$$ Show that there exists an adversary $A$ of size $T$ such that $$\mathbb{P}\_{b\gets G}\left\[A(b)=\log\_{g}(b)\right\]\>\frac{3}{4}.$$ Assume multiplication over $G$ requires $O(1)$ circuit.

How can I prove this claim? Intuitively, since $A$ is bigger than $A'$ in about $O(\log m)$, the construction should be based on dividing the problem into halfs recursively, as in binary search. However, I can't think of any clever way to do that...

# Answer
Suppose that we had a stronger guarantee: $A'$ is a randomized algorithm, and for every $b$, $\Pr\[A'(b) = \log\_g b\] \> 1/2$, *over the randomness of the algorithm*. In that case, you would construct $A$ by running $A'$ several times, and checking each output until you get one that satisfies $g^{A'(b)} = b$.

Now suppose that the guarantee is $\Pr\_b\[A'(b) = \log\_g b\] \> 1/2$. You would like to somehow get "independent samples" of $A'(b)$. You can accomplish that using randomized self-reducibility. I'll let you fill that out since it's your exercise. The resulting algorithm is randomized, but by choosing the optimal randomness, you get a deterministic (but non-uniform) algorithm with the same guarantees.
> 1 votes

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


# Question
Title: Optimal way to pack items with multidimensional weight such that the number of items is minimized?
I am given a set of items S = {a1,a2,a3,...,an}. Each item has a corresponding M dimensional bit vector indicating the properties of that item. For example, if item x has corresponding vector: {0, 1, 0}, then item x does not have property 1, does have property 2, and does not have property 3.

I am also given a M dimensional "goal" vector indicating the number of items I need that match each property. For example, if my goal vector is: {1, 3, 2}, then I need 1 item with property 1, 3 items with property 2, and 2 items with property 3.

My question is, how can I select a subset of items from the set S such that the constraints listed in the goal vector are met exactly and so that the number of items selected from S is minimized? What is the name of this problem, and what is an efficient algorithm for solving it? Also, what algorithm would I use for the opposite scenario where I would like to maximize (instead of minimize) the number of items used?

Could this be a variation on the knapsack problem or the bin packing problem?

# Answer
This problem is NP-hard, so you can't expect a general algorithm that is efficient and always correct. In particular, in the special case where the goal vector has only 1's and 0's in it, it becomes an instance of the exact cover problem.

Your problem can be viewed as an instance of the multidimensional subset sum problem.

If you have to solve it in practice, I would suggest formulating it as an instance of integer linear programming and using an off-the-shelf ILP solver.
> 1 votes

---
Tags: algorithms, knapsack-problems, packing
---


# Question
Title: How to show ambiguous context-free grammars in Chomsky normal form is Turing recognizable?
**So this question has two questions and i have to use the answer from 1 to answer question 2. Assuming that my answer for 1 is good. I need help with 2. ( Correct me if wrong please.)**

**Question 1 :**

Show the following language is decidable

> $L=\\{\langle G,w \rangle $ : $G$ is a grammar in normal form of Chomsky and $w$ is a word on the terminal alphabet that can be derived in $G$ by at least 2 differents derivations trees. $\\}$

In other words, find an algorithm that when given a grammar that is in normal form of Chomsky and a word $w$, it concludes after a finite number of steps if yes or no $w$ can be derived by two derivations trees.

**Here's my attempt (correct me if this is wrong) :**

Entry : $\langle G,w \rangle $

1. Try every derivations in $G$ of length $2|w| -1$.
2. If two derivations generate $w$ stop and accept $\langle G,w \rangle $. Else stop and reject $\langle G,w \rangle $.

**Question 2 :**

Show that this language is **Turing recognizable** $K = \\{\langle G \rangle : G$ is a grammar in normal form of Chomsky and $G$ is ambiguous ( can have two derivation tree for same word).$\\}$ In other words, give an algorithm that when given an grammar in normal form of Chomsky, it returns **"true"** if $G$ is ambiguous and return **"false"** or doesn't stop when $G$ is not ambiguous. ( Give an answer based on the algorithm used in question 1)

**My reflexion on question 2 :**

For this part i am kinda lost, i know that we will use algorithm of question 1 to be able to return true but for the infinite loop part i am not sure on how to say this.

I am also not sure if i can use a word "$w$" since our entry is a grammar $G$.

Entry : $\langle G \rangle$

1. Apply algorithm from question 1 if it returns true, return true. ( Because question 1 basically confirm that the CNF is ambiguous).
2. note sure how to handle the rest for it to loop.

# Answer
Your answer to question 1 is nice and correct.

---

On question 2, of course, you can use a single word $w$ to test the grammar $G$. However, it is not enough to use just one word, since the grammar could be ambiguous on another word.

Well, we can use **all** words to test the grammar.

Here is the high-level description of a Turing machine $R$ that recognizes $K$.

> Loop through all words:
>
> > for each word $w$, try every derivation in $G$ of length $2|w|−1$. If two derivations generate $w$ stop the machine and accept $G$.

There are many ways to loop through all words. For example, we can fix an arbitrary order of all terminals and iterate by short-lexicographic order.

Note that when $G$ is not ambiguous, $R$ will run forever. That means $R$ is not a decider for $K$. In fact, no Turing machine can decide $K$ since $K$ is undecidable.
> 0 votes

---
Tags: turing-machines, discrete-mathematics, semi-decidability
---


title: Kleene's Theorem and TMs

text:
# Question
Title: Kleene's Theorem and TMs
I wanted to know that based on Kleene's theorem (a language is regular iff some FSA recognizes it), does every regex have a TM (Turing machine) that halts on exactly the same language?

Is this implication valid or are we not entirely sure about this? (ambiguous/unclear given the theorem). Kind of like the Church-Turing thesis about computation in the future and all computation in general.

# Answer
We can prove the following theorem:

**Theorem**: A language $L$ is regular if and only if there exists a DFA or NFA for language $L$.

Turing machines are more powerful than DFAs and NFAs. In particular, every finite state automaton can be simulated by some Turing machine.

So, according to the above propositions, the answer to your question is yes: every regex has a Turing machine whose language is identical.
> 5 votes

---
Tags: turing-machines, automata, finite-automata, halting-problem, church-turing-thesis
---


# Question
Title: Two-Sum - Range Allowance Algorithm Design
**What is the best way to find if there are two individual capacities that sum to a total capacity within a range of plus and minus the total capacity?**

* Optimize for runtime over memory complexity.
* The same item cannot be selected twice.

**Inputs**

* An Int representing the total capacity
* An Int representing the range above and below the total capacity sums are allowed to be within.
* An Array of Int's representing items' individual capacities.

**Output**: A Boolean representing whether it is possible for two of the items to equal the total capacity plus and minus the given range.

*Samples*

*1.*

* Input: `[4, 5, 2, 6]`
* Total capacity: `10`
* Range Allowance: `0`
* Expect: `true` because `4` \+ `6` equal `10`.

*2.*

* Input: `[4, 5, 2, 5]`
* Total capacity: `12`
* Range Allowance: `2`
* Expect: `true` even though there are no two numbers that equal `12` directly, there are two numbers that sum to `10` which is within the range allowance provided.

*3.*

* Input: `[4, 5, 2, 7]`
* Total capacity: `14`
* Range Allowance: `1`
* Expect: `false`

# Answer
This can be solved in $O(n \log n)$ time, much like the ordinary two-sum problem. Sort the items by increasing capacity. Let $t$ denote the desired target (the total capacity), $t$ the amount you can go up or down, so our desired target range is $\[t-u,t+u\]$, and $A$ the array of elements. We will do a linear scan over the items, left-to-right.

Suppose our linear scan is pointing at the $i$th item, with capacity $A\[i\]$. We'll ensure that the indices $j,k$ are chosen so that $A\[j\]$ is the largest value in the array that is $\< t-u-A\[i\]$, and $A\[k\]$ is the smallest value in the array that is $\> t+u-A\[i\]$. Notice that if $k \ge j+2$, then we have found a solution to the problem. (You'll need to handle the special case where $i=j+1,k=i+1$ specially.) Also, each time you increment $i$ by one, it is easy to update $j$ and $k$, by moving $j$ and $k$ to the left as much as needed. Since $i$ only increases and $j,k$ only decrease, it follows that the linear scan does only $O(n)$ work. So, the total running time is dominated by the time to sort the algorithm.
> 1 votes

# Answer
1. Create a Set `searchSet` to store the item's that have already been examined.
2. Iterate through the input Array of item capacities.

2a. Find the `targetCapacity` for the current item: `totalCapacity - itemCapacity`.

2b. Generate a `targetCapacitiesArray` plus *and* minus the `totalCapacity` and the range allowance provided.

2c. For each capacity in `targetCapacitiesArray`, see if each number is contained in the `searchSet`, and return `true` if found.

2d. Else, add the `itemCapacity` to the `searchSet`.
3. Return `false` if the entire input is iterated through without finding a match.
> 0 votes

---
Tags: algorithms, algorithm-analysis, dynamic-programming, hash-tables, pseudocode
---


# Question
Title: Two-Sum - Pre-sort Optimization Algorithm Design
**Is it possible to optimize the runtime of a two-sum solution by receiving a pre-sorted input either in ascending or descending order?**

# Original Two-Sum

Determine whether there are two items whose individual capacity will perfectly equal the total capacity while ensuring the same item cannot be selected twice.

* Input: An Int representing the total capacity and an Array of Int's representing items' individual capacities.
* Output: A Boolean representing whether it is possible for two of the items to equal the total capacity.
* Time complexity: Linear growth, $O(n)$
* Space complexity: Linear growth, $O(n)$

## Samples

Input: `[4, 5, 2, 6]`

* Total capacity: `10`
* Expect: `true`

Input: `[4, 5, 2, 5]`

* Total capacity: `10`
* Expect: `true`

Input: `[4, 5, 2, 7]`

* Total capacity: `10`
* Expect: `false`

## Pseudocode

1. Create a Set `searchSet` to store the item's that have already been examined.
2. Iterate through the input Array of item capacities.

2a. Find the `targetCapacity` for the current item: `totalCapacity - itemCapacity`

2b. If `searchSet` contains the `targetCapacity`, return `true`.

2c. Else, add the `itemCapacity` to the `searchSet`.
3. Return `false` if the entire input is iterated through without finding a match.

#  Pre-Sort

1. Save a new var `lastTargetCapacity`
2. If the current `itemCapacity` \< `lastTargetCapacity`, there are no possible two-sums and return `false`.

*i.e.*

Input: `[6,2,1,0]`

* Total capacity: `9`

Iterations

1. `targetCapacity = 9 - 6`, `lastTargetCapacity` = 3
2. Return false because the `itemCapacity` of `2` \< `lastTargetCapacity` of `3`.

# Answer
> 0 votes
The Two Sum solution can be optimized for runtime performance given the input Array is pre-sorted in ascending or descending order.

If Binary Search is used to find the `targetCapacity` above, it will run in logarithmic, $O(logn)$, average runtime. This is faster than the pseudocode above that runs in linear, $O(n)$, runtime using iteration and hashing.

If sorting was not provided in the input then it would not be possible to sort and search faster than $O(n)$. The best that could be done would be $O(nlogn)$ with a strategy such as Quicksort and Binary Search.

*See: Stanford - Two Sum Explanation*

# Answer
> 0 votes
Yes, you can solve the two-sum problem in $O(n)$ time, if the numbers are presented in sorted order. See my other answer for how to do it; it involves a linear scan. This is asymptotically optimal, as it already takes $O(n)$ time even to read the input, and solving the problem may require reading the entire input, so there can no further asymptotic improvement.

---
Tags: algorithms, algorithm-analysis, dynamic-programming, hash-tables, pseudocode
---


title: Enumeration of BPP machines

text:
# Question
Title: Enumeration of BPP machines
Can we enumerate all probabilistic Turing machines (with bounded error), like we do for deterministic Turing machines (when using diagonalization arguments against deterministic Turing machines)? If not, does this mean we cannot diagonalize against BPP machines?

# Answer
Yes. Enumerate over all pairs $(M,p)$ of probabilistic Turing machines $M$ and polynomials $p$. Interpret each such pair in the following way: on input $x$, run $M$ for $p(|x|)$ steps, and if it doesn't halt, output "yes".
> 2 votes

---
Tags: complexity-theory, turing-machines
---


# Question
Title: What does an admissible numbering of computable functions look like?
I'm trying to understand how we can construct an admissible ordering of the computable (meaning, partial recursive) functions.

Initially my take on such an enumeration was from the point of view of an enumeration of *programs*. For instance, we could enumerate all possible Turing machines using some set of rules (for instance, first the 1-state machines, then the 2-state machines, with some sort lexicographic order within each of the groups). Or alternatively, perhaps we could encode each program uniquely via some numbering system and then simply take them in increasing order.

These produce computable maps from $\mathbb{N}\to$ set of computable functions. But of course these are not *bijections* since multiple programs will compute the same function.

So my question is, for the purposes of something like Rice's theorem, how does one construct an admissible numbering of the computable functions?

# Answer
The encodings you mention are admissible. Why do you think they need to be bijections?

In fact, there is no admissible numbering of partial computable maps that is a bijection. If there were one, we could decide equality if partial computable maps, which would allow us to implement the Halting oracle.
> 3 votes

# Answer
Any reasonable encoding will do. For example, you can imagine a version of C (or your favorite programming languages) in which integers are unbounded, and there is a reasonable input/output convention. Interpret $i \in \mathbb{N}$ as encoding a string $s\_i$ in ASCII (in base 256). If $s\_i$ is a valid C program, then it encodes some partially computable function. Otherwise, treat $s\_i$ as encoding some fixed partially computable function, say $f(x) = 0$.
> 2 votes

---
Tags: computability, enumeration, encoding-scheme
---


title: Why should I care about lambda calculus

text:
# Question
Title: Why should I care about lambda calculus
I am a programmer by hobby. I stumbled upon lambda calculus from Kevlin Henney's talk lambdas to the slaughter and I was sold! It was an interesting new way of thinking that's entirely different than the way most of us program. But if I want to push someone to learn lambda calculus, what concrete benefits can I state.

I tried for long but the only one I could come up with is that its fun to play around. And it acts as the base of functional programming.

P.S. when I first heard about Lisp I couldn't understand why so many C brackets. After spending some time with lambda calculus, now I know ;P

# Answer
> 2 votes
Your question is a bit like this: *"I am a programmer by hobby, and I learned about von Neumann machines. Why should I care about them?"* And the answer is: because they're the theoretical model of computing machines that transformed our society.

Your question about the $\lambda$-calculus has a similar, but less grandiose answer. The $\lambda$-calculus was invented before Turing machines as an answer to "what is computation?" In itself it is not terribly practical, but it has been immensly influential in programming. Many programming concepts that we use today originated in the $\lambda$-calculus. Various languages support $\lambda$-calculus to various degrees, but almost all of them are in debt to $\lambda$-calculus to some degree (even the ones that are claimed to be "anti" $\lambda$-calculus).

If you are a hobby programmer, you should learn a programming language with good support for $\lambda$-calculus, as that will give you the joy of actually using the concepts. For instance, you can try one of the following:

Many popular languages have partial support for $\lambda$-calculus, which they implement to varying degree. If you know one of them, you could try the functional programming style (which is what $\lambda$-calculus is about), but keep in mind it's not the Real Thing:

LISP belongs to this list as well, as it does not have true support for $\lambda$-abstraction.

# Answer
> 0 votes
You can't. The lambda calculus itself isn't a great practical programming language. But it forms as a basis for functional programming, which is useful. See https://en.wikipedia.org/wiki/Functional\_programming.

---
Tags: lambda-calculus
---


# Question
Title: How to define a path between two sets of vertices?
In section 17.2 of the book "Combinatorial optimization polyhedra and efficiency" by Schrijver, he describes the Hungarian method for maximum weight matching in bi-partite graphs (with classes $U$ and $W$). He defines for a matching, $M$, $U\_M$ and $W\_M$ as the set of vertices in $U$ and $W$ missed by $M$. He then says "if there is a $U\_M - W\_M$ path, find the shortest such path". I'm not sure what this means. How is a path between two sets of vertices defined?

He is describing this path on a directed graph, $D\_M$ where all edges in $M$ are directed from $U$ to $W$ and edges not in $M$ are directed from $W$ to $U$.

# Answer
An $A$-$B$ path is a path that starts at some $a \in A$ and ends at some $b \in B$.
> 2 votes

---
Tags: graphs, shortest-path, weighted-graphs
---


# Question
Title: Can anyone tell me why this search parition for quicksort works?
```
private static < T extends Comparable < ?super T >> int partition(T[] a, int first, int last) {
  int mid = (first + last) / 2;
  sortFirstMiddleLast(a, first, mid, last);

  swap(a, mid, last - 1);
  int pivotIndex = last - 1;
  T pivot = a[pivotIndex];

  int indexFromLeft = first + 1;
  int indexFromRight = last - 2;
  boolean done = false;
  while (!done) {

    while (a[indexFromLeft].compareTo(pivot) < 0)
    indexFromLeft++;

    while (a[indexFromRight].compareTo(pivot) > 0)
    indexFromRight--;

    if (indexFromLeft < indexFromRight) {
      swap(a, indexFromLeft, indexFromRight);
      indexFromLeft++;
      indexFromRight--;
    }
    else done = true;
  }
  swap(a, pivotIndex, indexFromLeft);
  pivotIndex = indexFromLeft;

  return pivotIndex;
}

```

It doesn't seem to touch the first or last elements

# Answer
`sortFirstMiddleLast()` sorts the first, middle, and last elements in-place. Once that's done, there's no need to consider the first or last value because (if the middle value is used as the pivot) they're known to be correctly partitioned.
> 1 votes

---
Tags: algorithms
---


title: P≠NP, yet NP=co-NP

text:
# Question
Title: P≠NP, yet NP=co-NP
I know , if P = NP then it can easily be proven that P = NP = Co-NP. But I was wondering, if we assume P≠ NP, also then can it be proven that, NP =co-NP??

# Answer
We don't know anything either way: it is consistent with our knowledge so far that $\mathsf{P\not=NP}$ and $\mathsf{NP=coNP}$, *and* it is consistent with our knowledge so far that $\mathsf{P\not= NP}$ and $\mathsf{NP\not=coNP}$.

Of course in some sense that's a purely *negative* statement since it's just about the limits of our current knowledge, not really about the mathematics itself. Here's an actual theorem which says, in a precise sense, that the "standard" tools of complexity theory cannot show anything about $\mathsf{NP}$ vs $\mathsf{coNP}$ even assuming $\mathsf{P\not=NP}$:

> There are oracles $A$ such that $\mathsf{P}^A\not=\mathsf{NP}^A$ and $\mathsf{P}^B\not=\mathsf{NP}^B$ but $\mathsf{NP}^A=\mathsf{coNP}^A$ and $\mathsf{NP}^B\not=\mathsf{coNP}^B$.

This should recall the Baker-Gill-Solovay theorem that $\mathsf{P}$ vs. $\mathsf{NP}$ cannot be decided via *relativizing* methods. The proof is similarly a forcing argument, but it's a bit more intricate. I'll add a reference once I can track it down.

(I do not know whether we similarly have a "natural proofs" barrier here. I suspect we do, but that argument is more involved.)
> 4 votes

---
Tags: complexity-theory, np
---


# Question
Title: What is softmax in reinforcement learning?
There are multiple very complicated articles about softmax online. I just want to know a few things about it:

1. Why do we need softmax? What is the "problem"? What does it do?
2. How does it do it?

I find it very hard to get through all the math when I don't really get what it is all about. The problem is that all the things I read online is very complicated written and no one seems to just get to the point.

I hope you can help.

# Answer
> 0 votes
Ok, I have read a very good explanation to what softmax is.

A dog is programmed to walk through a maze. One start point has very few walls. The way it is programmed with the epsilon greedy algorithm, the dog will sooner or later start to walk mostly to the right or mostly to the left. That is a problem because it at some point might just walk in a circle the entire time. To get that out one could make it choose left or right randomly from time to time - but that is not really a good approach for obvious reasons.

So instead you use something called softmax. Softmax just smoothens the decision process: like taking out the walking-left or walking-right.

---
Tags: reinforcement-learning
---


# Question
Title: What is the difference between Big O and asymptotic notation?
Are the two interchangeable or is there a difference?

# Answer
Bachmann–Landau notation or asymptotic notation is collection of notations one of which is Big-$O$. So they are not interchangeable, because as asymptotic notation also is known little-$o$, big-$\Omega$, big-$\Theta$ etc.

Historically this symbol was introduced by German mathematician Paul Bachmann and then adopted by German number theoretician Edmund Landau and American mathematician L.E. Dickson . Big-$O$ was shorthand for function rate of growth, which is called its ***order***.

History also can be viewed in the book by Florian Cajori - A history of mathematical notations-Dover Publications (1993), page 31.
> 1 votes

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