# Question
Title: How to do better than brute-force for this problem?
I am trying to solve a competitive-programming-style problem which I've boiled down to the following: given two arrays $a, b$ of length $n$, where $a\_i, b\_i \> 0$ for all $i=1\ldots n$, compute $$\max\_{i, j : i\neq j} \quad a\_ib\_i + a\_jb\_j + \max \\{ a\_ib\_j, a\_jb\_i \\}. $$

Of course, this can be solved by brute force by searching over all relevant pairs $(i,j)$, which is $\Theta (n^2)$. I'm wondering how to come about a more efficient solution, e.g. running in $\mathcal{O} (n\log n)$ time.

I toyed around with an approach where I sorted $a$ and $b$, then iterated through $i = 1\ldots n$ and performed binary-searches at each iteration, but I've been unable to get the right answer, much less prove correctness. I thought of a geometric interpretation of the objective in terms of areas of rectangles, which led me to an alternate form of the objective: $$\max\_{i,j : i\neq j} \quad (a\_i + a\_j)(b\_i + b\_j) - \min\\{ a\_ib\_j, a\_jb\_i \\},$$ but I'm not sure this is useful.

I would appreciate some help figuring out how to tackle this problem.

# Answer
> 2 votes
I think it is possible to solve this problem in $\mathcal O(n \log n)$. Note that this is an improvement to this answer, which previously did not handle that $i \ne j$. See below for how this is added. Also note that what described below is a version of the Convex Hull Trick.

First, observe that the $\max\\{a\_i b\_j, a\_j b\_i\\}$ is unnecessary: It can be replaced by $a\_i b\_j$, since we get the other result by swapping $i, j$.

This leaves us with finding this: $$\max\_{i, j} \quad a\_ib\_i + a\_jb\_j + a\_ib\_j $$

Our approach will now be to iterate over $i$ and find the largest $j$ in $\mathcal O(\log n)$ time. Note that for this, it suffices to, given $c$, find $j$ maximizing this: $$\max\_{j} \quad (a\_j + c) b\_j $$ (Set $c := a\_i$ and observe that $a\_i b\_i$ is not dependent on $j$)

Now notice that this defines a collection of functions $f\_j(x) = a\_j b\_j + x b\_j$, which are all linear (plus offset). We now want to find which of these functions is the largest, given $x$. We now build a data structure that can solve this quickly (i.e. in $\log n$).

First notice that for functions with the same $b\_j$, the one with the highest $a\_j$ is always higher. Geometrically, these are parallel lines, but those with higher $a\_j$ are higher. We thus ignore all such dominated functions.

Then notice that a function with higher $b\_j$ eventually dominates those with smaller $b\_j$. We will now build a ordered list, where the function that dominates for $x \to \infty$ comes first, the ones that dominates to the left of it comes second, etc. The list will only contain those functions that dominate somewhere. Graphically, the list would contain `[black, blue, red, green]` , since the functions in this image below would dominate in that order from right to left. `orange` does not appear, since it dominates nowhere:

So we start with the function with the highest $b\_j$ and add it to the list. The list is ordered such that the functions dominating more left come last, and we add from the back¹. Not that each function dominates in a unique interval. We also store the right end of this interval (which is $+\infty$ for the first function).

We now add the other functions, in order of decreasing $b\_j$. (This means we sort the arrays once, which is $\mathcal O(n \log n)$). To add such a function $f$, compare it with the function $g$ currently dominating the most on the left (which is the last function in the list). There are several options, depending on where $g$ starts dominating $f$ (which we can compute easily with some linear algebra):

* $f$ dominates $g$ on some interval, but not on the entire interval where $g$ dominates. It still leaves space for $g$ to dominate somewhere. In this case, we add $f$ to the back of the list.
* $f$ dominates $g$ everywhere. In this case, we remove $g$ (we drop $g$), and continue with the rest of the list.
* $f$ dominates $g$ nowhere: Technically, the point of domination is $\<0$. As an optimization, we can choose to do leave the list unchanged (but it does not really matter, the algorithm should still work for numbers $\<0$).
* As a special case, we can also do the pruning of smaller functions with equal $b\_j$ here: If two functions have same $b\_j$, process those with higher $a\_j$ first, and drop the others here since they never dominate.

The runtime analysis here is easy, once you see that each step either adds a function directly, or drops a function, where each function is only dropped once. Thus by amortized analysis, where each function in the list has a potential of $2$ (and adding thus requires a potential of $3$), we see that this is works in $\mathcal O(n)$.

We now have a sorted list that tells us where each function dominates. Thus, we can find the highest function for given $x$ in $\mathcal O(\log n)$ by binary search.

This means we're done. We can find for each $i$ the highest $j$ by doing the above binary search with $x := c := a\_i$. We have $n$ iterations of the outer loop, each taking $\mathcal O(\log n)$. We also have $\mathcal O(n \log n) + \mathcal O(n)$ (for sorting and building the function sorted list) of setup time. Together, that's $\mathcal O(n \log n)$.

---

To handle $i \ne j$, we must additionally keep track of the second-highest function each. This seems to actually not be that hard, the trick is to maintain a similar data structure for the second-highest function.

When adding a function $f$, all the functions that we dropped are now the second-highest functions on the interval left of the intersection point of $f$ with $g$ (the function it non-trivially intersects with). But first, we notice that right of the intersection point, $f$ is now a candidate for the second-highest function, that is also higher than all second-highest functions left of the intersection point. So we can add it to the second-highest-function lookup structure (using a regular insert), and then force-add all the things we dropped, that were to the left of the intersection point. What is tricky here is that there are various edge-cases, and that the data structure is no longer as well-behaved (since when going right, functions can become *less* steep).

This idea actually generalized to also keeping track of the $m$-th highest list. The runtime complexity for an insert should then be $\mathcal O(n m)$ using amortized analysis. For us, $m=2$ is sufficient, making it linear.

I've implemented this, and tested it a bit, and it seems to work. But I am sure there are bugs somewhere, and it's quite possible that this approach is wrong in general. But have a look yourself here: https://github.com/JoJoDeveloping/some-optimization-problem

Unfortunately, I don't see how to extend this to handling $i \neq j$. Perhaps you can somehow save the second-hightest function for each point? But I don't know how to build this lookup structure efficiently. The second-highest function is also way less well-behaved (observe that `blue` is the second-highest function for two disjoint intervals in the picture above).

---

1: This allows us to use an array. Alternatively, we can use a linked list and convert it to an array later.

# Answer
> 1 votes
Okay, so I think I found *a bit* of an optimization?

---

Firstly, since arrays are accessed by the same index, - you aren't dealing with 2 arrays, you're dealing with array of 2-tuples
and 2-tuples can represent points on 2D plane: $(x\_i, y\_i)$

And for brevity, let's call what we optimize over as function $f()$: $$f((x\_1,y\_1), (x\_2,y\_2)) := x\_1y\_1 + x\_2y\_2 + max(x\_1y\_2, x\_2y\_1)$$

---

Main property to use is this:

$$x\_1 \le x\_2\text{ and }y\_1 \le y\_2\implies\forall P : f((x\_1,y\_1), P)\le f((x\_2,y\_2),P)$$

So we can define that condition as partial ordering
$$P\_1(x\_1,y\_1) \le P\_2(x\_2,y\_2) \iff x\_1\le x\_2 \text{ and } y\_1\le y\_2$$

In other words, points that are "above and to the right at the same time" are "bigger" and can be substituted in place of "smaller" ones to get bigger value.
This allows us to prune "smaller" points, with only exception being... taking "bigger" and "smaller" point together (because we can't repeat indices)

This gives a way for 2 pruning techniques:

1) if point is less than 2 (or more) other points - prune it completely
2) if point $P\_1$ is less than only 1 other point $P\_2$ \- prune it, but store $f(P\_1,P\_2)$

And it can be achieved by
1) sorting our tuples strictly (first by x, and **only if** $x\_1 = x\_2$, you sort by y) - $O(n\*log(n))$
2) running one sweep from largest x to the smallest, while remembering 2 highest y values encountered - prune by the 2 rules above, store unpruned points and highest encountered f() - $O(n)$

---

Now you have some candidate maximum $f()\_{\text{comparable}}$ and a set of maximal points (incomparable between each other, but bigger than all the rest).

What to do with these? I have no idea

Incomparable points are nice in that in each pair one has "bigger x" and the other has "bigger y" (think about their set as strictly-decreasing function) - so we know which branch is taken in that $max()$ from $f()$

One more idea - x and y can be scaled with same multiple for all points, so now our "strictly-decreasing function" can be limited to $(0,1\]\times (0,1\]$. Does it give anything? idk

# Answer
> 1 votes
I think if you use my preprocessing before Jojo's line algo, it will work for $i \ne j$

Jojo's algo assumes you need both $ij$ and $ji$ to find the optimum, but my prunning defines exactly which Point should be the first and which should be the second in each pair.

So best "second" Point can be found "on the go" while constructing that line structure

---

resulting algorithm would be

1. sort by $x$ and $y$ \- $O(n \log n)$
2. prune lower-left points, get best $f()$ from pruned Points - $O(n)$
3. for each Point left, in already sorted order - $n \text{ times}$
a) find best $f()$ from the data structure - $O(\log n)$
b) add the Point to the data structure - $O(1)$

neither step applies Point onto itself
and (what concerned me much more) same $(a,b)$ tuple repeated would work fine as well

---

Implementation

# Answer
> 0 votes
What I would try: Sort the arrays by $a\_i \cdot b\_i$. Combine them starting with the smallest indices, and you should be able to show that any smaller product needs components of different sizes, because you want to combine a large a\_i with a large b\_j.

So if the largest products are say about 100, a product 50 x 1 could be useful.

Or maybe make two copies of the arrays, one sorted by a\_I and one sorted by b\_j, and combine a large a\_i with a large b\_j.

# Answer
> -1 votes
If you convert all (ai, bi) to coordinates on a graph, I believe this can be solved similarly to the, closest pairs problem. Which has a nlogn solution, related to comparing all coordinates together to find some max or min value.

---
Tags: algorithms
---


# Question
Title: CFG {$w\in ${a,b,c}$^* | $#$_a(w) + $#$_b(w) = $#$_c(w)$}
I'm practicing the following exercise for my exam: CFG {$w\in ${a,b,c}$^\* | $#$\_a(w) + $#$\_b(w) = $#$\_c(w)$} and I'm struggling a bit.

I've already solved {$a^nb^mc^l | n+m=l$} with production rules: $ S\rightarrow aSc | B|\varepsilon \\ B\rightarrow bBc|\varepsilon $,

which is almost the same except the positions of the symbols matter. In the other question the symbols can be anywhere which makes it a lot more difficult for me.

I have also solved: {$w\in{a,b}^\* | $#$\_a(w) = 2$#$\_b(w)$} by using the production rules: $S \rightarrow aSbSa | aSaSb | bSaSa | SS | \varepsilon $, where the position doesn't matter.

I know that for every $a$ we have, we also need to create a $c$, and for every $b$ we have we need to create a $c$, however the position at which you create them don't matter, so you have a LOT of possibilities. So far I tried something like this $S \rightarrow aSc|bSc|T \\ T \rightarrow cTa | cTb | \varepsilon $

However these rules don't produce the string 'bccb' for example. I feel like I need a LOT of rules to create all the possibilities since the positions don't matter. Could someone give me a hint on how to tackle this?

EDIT: I just created an answer that worked but I find it not intuitive at all. Could this be simplified? $S \rightarrow cT | cTTc|TcTc|cTcT|TTcc|ccTT|TccT|\varepsilon \\ T \rightarrow aS | bS $

I found that you can remove a few of the productions which give: $S \rightarrow cT | Tc | ccTT | TccT | \varepsilon \\ T \rightarrow aS | bS$ However I just found this solution by just removing and adding stuff without any reasoning, which will make it hard to reproduce it for other questions

EDIT$^2$ eventhough my exercise checker says the last given CFG is correct, I do NOT think that it is. I can not seem to create the string "cccaaa"

# Answer
> 3 votes
You are interested in the language $L = \\{w\in \\{a,b,c\\}^∗\mid \\#\_a(w)+ \\#\_b(w)= \\#\_c(w) \\}$ but question how to haave the symbols in arbitrary order.

You have solved $\\{w\in \\{a,b\\}^∗\mid \\#\_a(w)= 2\\#\_b(w)\\}$ where the position does not matter.

I suggest you write a grammar for the simpler language $\\{w\in \\{a,c\\}^∗\mid \\#\_a(w)= \\#\_c(w) \\}$ where the order does not matter. Once you obtain a grammar you additionally allow that grammar to have $b$ at any position that is occupied by $a$, and you will get $L$.

---
Tags: context-free, formal-grammars
---


# Question
Title: Optimal graph data structure for set of points that allows dynamic updates
We aim to optimize the execution of a specific task.

Consider a set, **P**, containing **N** 2D points. A new query point, **p1**, is introduced, and the objective is to identify the nearest point in **P** to **p1**. If the distance surpasses a specified threshold, **p1** is incorporated into **P**, increasing its cardinality to **N+1**; otherwise, **p1** is disregarded. Subsequently, another query point, **p2**, undergoes the same process of either addition to **P** or elimination based on proximity criteria.

This continual influx of points, unbeknownst in advance, necessitates dynamic adjustments to **P**. It's essential to emphasize that this process is inherently sequential. Our inquiry revolves around identifying efficient data structures for implementing this sequential task. While k-D trees were explored, a notable challenge was discovered: upon adding a point to **P**, the entire tree must be reconstructed. In simpler terms, the insertion operation of k-D trees appears non-incremental. We are thus seeking alternative data structures that offer efficiency in executing the described task.

# Answer
You are looking for a data structure for nearest neighbor search that supports dynamic updates. I suggest reviewing Wikipedia, as it has a good overview of many different data structures.

Inserting an element into a k-d tree does not require rebuilding the entire tree. See https://en.wikipedia.org/wiki/K-d\_tree#Adding\_elements. In particular, you can insert into the tree efficiently without rebuilding it, and then periodically rebuild the tree, to amortize the cost of rebuilding over many inserts.

Another option is to use locality sensitive hashing. This supports efficient insert and delete operations. It also allows for approximate nearest-neighbor computation, but is not guaranteed to find the exact nearest neighbor. You'll have to decide whether that is sufficient for your application.
> 3 votes

---
Tags: graphs, data-structures, trees, nearest-neighbour, dynamic-algorithms
---


# Question
Title: "Unbounded" binary search in $\log_2(n) + O(?)$ comparisons
Binary search is the well-known algorithm that compares the input value to an entry in a sorted array, and based on the result then decides to check the same input value against another entry either on the left or the right of that array entry. The number of comparisons needed is O(log(n)), but we can specify the number more exactly as $\log\_2(n) + O(1)$

In "Unbounded binary search", There is a secret, positive, whole number, without any information on its upper bound (or the number of bits). Our task is to find the value of the secret number in as few comparisons as possible, where "few" is measured as a function in the value of that secret number.

In each comparison, we get to decide on a number and that number will be compared to the secret number by a black box. The black box then outputs True if the picked number is strictly larger than the secret number, and False otherwise. The cost of calling the black box is 1, regardless of the values involved. We can make all other calculations for free, as long as they don't involve the black box.

A straightforward algorithm starts with 1 and doubles it until the black box outputs True, and then with the found upper bound performs a binary search. This takes $2\log\_2(n) + O(1)$ comparisons, or $\log\_2(n) + f(n)$, where $f(n) = O(\log(n))$. We say that the number of extra comparisons is "$O(\log(n))$". Quicker algorithms are supposedly possible.

What's the quickest algorithm, that gives the lowest number of extra comparisons needed (for large enough n) versus if we knew the number of bits of the secret number?

# Answer
Your question was completely solved by Bentley and Yao, An almost optimal algorithm for unbounded sorting, and Beigel, Unbounded searching algorithms. They showed that if $f\colon \mathbb{N} \to \mathbb{N}$ is a monotone recursive function then there exists an unbounded search algorithm performing $f(n)$ comparisons on input $n$ if and only if $f$ satisfies Kraft's inequality $$ \sum\_n 2^{-f(n)} \leq 1. $$

Kraft's inequality is a bound on the lengths of codewords in a prefix code. To see the connection, observe that you can encode the transcript of an unbounded search algorithm as a binary string, where 0 means "\<" and 1 means "≥". Any two such strings must be different (since the algorithm is correct) and no string can be a prefix of another (since the algorithm would stop upon reaching the prefix), and so the strings form a prefix code, hence $f$ satisfies Kraft's inequality. This was shown by Bentley and Yao.

Beigel showed the other direction: any $f$ satisfying Kraft's inequality corresponds to an algorithm. To see this, partition the unit interval $\[0,1\]$ into intervals of lengths $2^{-f(1)},2^{-f(2)},2^{-f(3)},\dots$ (in this order), and perform binary search on the interval: imagining that the unknown $n$ is located at the middle of its interval, we can identify any subinterval $I$ of $\[0,1\]$ with the subinterval of $\mathbb{N}$ consisting of the points of $\mathbb{N}$ contained in $I$, and accordingly, convert a query about $\[0,1\]$ to a query about $\mathbb{N}$. After $f(n)$ steps, the algorithm has zeroed in precisely on the $n$'th interval, and in particular, has figured out that the answer is $n$.

Concretely, here is an algorithm (suggested by Bentley and Yao) that uses $\log\_2 n + O(\log \log n)$ queries: determine $\lceil \log\_2 n \rceil$ using your algorithm ($O(\log\log n)$ queries), and then run standard binary search (at most $\log\_2 (2n) + O(1)$ queries, since $2^{\lceil \log\_2 n \rceil} \leq 2n$). Conversely, any algorithm must use $\log\_2 n + \Omega(\log \log n)$ queries, due to Kraft's inequality. So the optimal algorithm uses $\log\_2 n + \Theta(\log \log n)$ queries.
> 4 votes

---
Tags: algorithms, time-complexity, binary-search
---


# Question
Title: Prove that $Decision Tree Complexity$ $\leq$ $(Certificate Complexity)^{2}$
I have been trying to understand the following proof but so far no cigars.

**My Understanding:**
For a given function $f$ we can define $C\_{1}(f)$ as a $k$-DNF formula where $k$ represents the size of the certificate and where every clause in the formula is a different certificate. Similarly we can define $C\_{0}(f)$ as a $k$-CNF formula. I also understand that every 1-certificate intersects every 0-certificate in at least one bit (represented by a literal in the formula) otherwise we would have an input that is consistent with both certificates which is not allowed.

To prove, we want to show that construction of a $Decision Tree$ is bounded by $(Certificate Complexity)^{2}$.

**Proof:**
The proof suggests we can randomly sample from the certificates in the $C\_{1}$. Suppose we choose certificate $s$, we can then query all the variables in this clause. If we obtain 1 we are done, else we can "strip-off" from $C\_{1}$ anything that is inconsistent with the bits that have been queried. Each term in $C\_{1}$ gets its size reduced by at least one. The resulting $C\_{1}$ is still such that each pair of clauses has a common literal. This process continues until the value of the function is found or $C\_{1}$ is empty.

**Question:**
I cannot picture how one can construct a branch in a Decision Tree from a certificate which has some bits set as non-decided. Moreover, it is confusing to see how the stripping operates in practice.

# Answer
> 2 votes
Here is the proof in more detail. We are given a function $f\colon \\{0,1\\}^n \to \\{0,1\\}$, and want to design a decision tree for $f$ of depth at most $C\_0(f) C\_1(f)$. This corresponds to an algorithm which makes at most $C\_0(f) C\_1(f)$ many queries to the inputs of $f$ and finds out the value of $f$.

The algorithm will maintain a partial assignment $\alpha$, initially empty, which will consist of these values of the input which have already been determined. It makes $C\_0(f)$ iterations of the following form. At the beginning of each iteration, the algorithm checks whether $\alpha$ satisfies some $b$-certificate of $f$ for some $b \in \\{0,1\\}$ (this is a certificate that certifies that the value of $f$ is $b$), and if so, outputs $b$. Otherwise, it picks an arbitrary¹ $1$-certificate of $f$ which is consistent with $\alpha$. Call that certificate $A$.

The certificate $A$ consists of pairs $(i,b\_i)$, where $i \in \[n\]$ and $b \in \\{0,1\\}$. Some of the $i$ mentioned in $A$ are in the support of $\alpha$ (the support consists of the indices of variables whose values are assigned by $\alpha$); since we assumed that $A$ is consistent with $\alpha$, in this case $\alpha(i) = b\_i$. We ask for the values of the $i$'s in $A$ which are not in the support of $\alpha$, and update $\alpha$ with their values. If all values are consistent with $A$, then we answer $b$, and otherwise we continue to the next iteration, if there is one.

If we have reached the last iteration, we make one last check, whether $\alpha$ satisfies some $b$-certificate for some $b \in \\{0,1\\}$, answering $b$ in that case. Otherwise, we answer $1$ ("final step").

---

At each iteration, the algorithm makes at most $C\_1(f)$ many queries (since the certificate $A$ mentions at most so many variables). Since there are $C\_0(f)$ many iterations, it makes at most $C\_0(f) C\_1(f)$ many queries in total. It remains to argue that it outputs the correct value of $f$. This is clearly the case if it outputs $b$ upon finding a $b$-certificate, so we have to explain why it can answer $1$ at the final step.

Let $x$ be the real input, and suppose that $f(x) = 0$. Choose an arbitrary $0$-certificate $B$ for $x$, which is of size at most $C\_0(f)$. At each iteration $t$ of the algorithm, it chooses a $1$-certificate $A$ consistent with $\alpha$ and so with $B$, and asks all involved variables. Since $A$ is a $1$-certificate and $B$ is a $0$-certificate, the two must have some variable $i$ in common such that $A(i) \neq B(i)$, and this variable gets queried at iteration $t$ (it cannot have been queried earlier since $A$ is consistent with $\alpha$). Hence at each iteration, $|\alpha \cap B|$ increases by at least $1$. Consequently, after at most $|B| \leq C\_0(f)$ iterations, $\alpha$ will satisfy $B$, and so the algorithm will output $0$, without reaching the final step. It follows that if we have reached the final step then necessarily $f(x) = 1$, and so we can safely return $1$.

---

¹The word *random* has a particular connotation in theoretical computation science, and is not appropriate here.

---
Tags: complexity-theory
---


# Question
Title: Parametrized threshold for LP Approximation in Vertex Cover Problem
I would like to have a formal description on how parametrizing the threshold in the approximation of vertex cover using LP would impact the approximation factor of the problem.

The linear programming problem would became:

Let $0\leq t\leq 1$ be the threshold (as a parameter)

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

And the returned set is $S=\\{v:x\_v\geq t\\}$

When $t=1/2$ this problem would have an approximation with a factor of 2. Initially I thought the factor would always be $1/t$, but if $t=1$ then all nodes would be inserted into the vertex cover.

# Answer
> 2 votes
Bazzi, Fiorini, Pokutta, and Svensson showed in their paper No small linear program approximates Vertex Cover within a factor $2-\varepsilon$ that every polynomial size LP relaxation of Vertex Cover has integrality gap $2-\varepsilon$, meaning (essentially) that any one-step rounding scheme cannot improve the approximation ratio beyond $2$.

This doesn't preclude the theoretical possibility that an iterative rounding scheme (see the monograph Iterative methods in combinatorial optimization by Lau, Ravi and Singh) can be used to obtain an improved approximation, but this is considered unlikely since it is UGC-hard to approximate Vertex Cover within $2 - \varepsilon$, as shown by Khot and Regev in their paper Vertex Cover might be hard to approximate to within $2-\varepsilon$.

---
Tags: optimization, approximation, linear-programming, parameterized-complexity, vertex-cover
---


# Question
Title: Name of graph family defined by modular sum
In the context of finite, simple, undirected graphs, associate with each node $v\in V$ an integer $n(v)$ (you can limit this to positive integers without loss of generality). Create the set of edges by defining a threshold $T$, and join an edge $x,y$ iff $n(x)+n(y) \geq T$. These are called *threshold graphs*$^{\[1\]}$ and they are well-studied, their structure has been characterized.

If, instead, $x,y$ are joined by an edge iff $n(x)+n(y)=0\ (mod\ T)$, we form another very simple class of graphs. But have they been studied and do they have a name?

$^{\[1\]}$ Chvátal, Václav; Hammer, Peter L. (1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L.; Korte, B. H.; et al. (eds.), Studies in Integer Programming (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics, vol. 1, Amsterdam: North-Holland, pp. 145–162.

# Answer
> 4 votes
Your graph class is the class of graphs that are a disjoint union of a clique and a bunch of bicliques, possibly singletons.

We can safely assume that the labels $\ell(v) \in \[0,T)$, and it is then clear that every pair of vertices with the same label is going to be a twin.

They will be true twins if and only if $\ell(v)=T/2$ in which case they will necessarily comprise a disjoint clique component.

Otherwise they'll be false twins fully connected to exactly one other (possibly empty) (false) twin class, i.e., they form one side of a disjoint biclique.

---
Tags: graphs, reference-request, modular-arithmetic
---


# Question
Title: Does Cutting Planes solve Pigeongole Principle for holes of different sizes?
Suppose a problem:

> Given $n$ pigeons and $m$ holes of sizes $b\_{i\le m}$ decide if you can put all pigeons in given holes.

It's possible to find a refutation of size $\mathcal O(n^2\log^2 n)$ of this principle when it's encoded as a conjunction of threshold functions, therefore there must exist a polynomial size Frege refutation any time $n\>\sum\_{i=1}^m b\_i$.

However, is Cutting Planes too weak already to have a polynomial size refutation for the $n=1+ \sum\_{i=1}^m b\_i$ case?

# Answer
> 1 votes
Let $x\_{ij}$ state that pigeon $i$ goes to hole $j$. One can axiomatize the pigeonhole principle as follows:

1. Booleanity: $0 \leq x\_{ij} \leq 1$.
2. Pigeon axioms: for all $i$, $\sum\_j x\_{ij} \ge 1$.
3. Hole axioms: for all $j$, $\sum\_i x\_{ij} \le b\_j$.

Summing the pigeon axioms, we get $$ \sum\_{ij} x\_{ij} \ge n. $$ Summing the hole axioms, we get $$ \sum\_{ij} x\_{ij} \leq m. $$ Therefore $n \leq m$, which is a contradiction if $m \< n$.

You might be interested in other encodings of the pigeonhole principlethey can probably be used to derive the axioms above.

---
Tags: complexity-theory, proof-techniques
---


# Question
Title: Nondeterministic Communication Complexity - How to Calculate it from Communication Matrix?
I have been wracking my head around the understanding on how to calculate $N\_{1}(f)$ and $N\_{0}(f)$ from the communication matrix.

**Definitions:**
$N\_{1}(f)$ = least cost of non-deterministic protocol that accepts $f^{-1}(1) = \\{(x,y) : f(x,y) = 1 \\}$

$N\_{1}(f)$ = ceiling( log(number of monochromatic rectangles needed to cover $f^{-1}(1)$))

**Examples:**
I would like to connect understand how this gets translated into the following two examples:

*Equality*
We know that the communication matrix has 1s on the diagonal and everything else is covered with 0.
$N\_{1}(f) = n$ \- this makes sense, I need exactly $n$ rectangles to cover my 1s on the diagonal, one rectangle per cell.
$N\_{0}(f) = \log n + 1$ \- this does *not* make sense. How can you cover all 0s with only that many monochromatic rectangles?

*Greater Than*
We know that the communication matrix has 1s on the diagonal and on top of it and everything else is covered with 0s.
$N\_{1}(f) = n$ \- I am assuming the rectangles are now not just an individual cell in the diagonal, but the whole row.
$N\_{0}(f) = n$ \- I am assuming the rectangles are now the entire column.

If my understanding for $N\_{0}(f)$ for the *Greater Than* is correct, then I do not understand how the colouring works for the *Equality* problem.

# Answer
> 1 votes
Here are the $\log n + 1$ rectanges that cover all 0s in the case of the Equality function: for all $i \in \[\log n\]$ and $b \in \\{0, 1\\}$, there is a rectangle $$ \\{ (x,y) : x\_i = b, y\_i \neq b \\} = \\{ x : x\_i = b \\} \times \\{y : y\_i \neq b \\} . $$

---
Tags: complexity-theory, communication-complexity
---


# Question
Title: An easy explanation of Tree-vs-Aversary Game
I've been reading on the Tree-vs-Aversary game in the example of proving the lower bound of a Decision Tree in the context of Resolution Refutation Proof Complexity. While I understand how the Adversary game can be used in proving the lower bound of the depth of the tree, I have problems visualising the Tree-vs-Adversary game.

**Rules for the game:**
In each round:

* Tree queries for variable $x\_{i}$
* Adversary can either: a) choose value for $x\_{i}$ b) let the tree choose the value but in return obtains a point

Game ends when the Tree solves the problem.

**Lemma:**
If there exist an adversary that can score $\geq r$ points then size of Decision Tree $\geq 2^{r}$

**Question:**
Is there a simple function and a strategy you can provide to more easily visualise it?

# Answer
Here is a simple but somewhat interesting example: the equality function on $n+n$ bits. This function accepts two input binary strings of length $n$, and returns whether they are equal.

Call the two inputs $x$ and $y$. The adversary's algorithm is as follows. When $x\_i$ is queried, if $y\_i$ is unknown, then we let the tree decide, and otherwise, we return $1-y\_i$; and similarly when $y\_i$ is queried. It is not hard to check that the value of the function remains unknown until all inputs have been queried, at which point the adversary has scored precisely $n$ points.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Can the intersection of 2 non-regular languages be a regular and infinite language?
The outline of the exercise is this: Describe two non-regular L1 and L2 languages on A = {a,b} such that L1∩L2 is infinite and regular.

The proposed solution to this exercise is:

**L1 = {a^n b^n | n \> 0}**

**L2 = {a^n b^m | n != m AND word length is even}**

**L1∩L2 = {words of even length}**

What I don't understand, however, is that in L1 since n must be equal for both a and b we will always find words of the type aabb aaabbb ab aaaabbbb while in L2 n and m are different so we will find words of the type aaaabb abbbbb also respecting the condition that they are even, but in the intersection how do we find words of even length if the strings will never be equal, i.e. which string can belong to both L1 and L2?

# Answer
> 2 votes
The intersection of the languages $L\_1$ and $L\_2$ given is indeed empty.

To built a very simple example, let's do the following:

$$A := \\{aaa^nb^n \mid n \in \mathbb{N}\\} \cup \\{bw \mid w \in \\{a,b\\}^\*\\}$$ $$B := \\{aba^nb^n \mid n \in \mathbb{N}\\} \cup \\{bw \mid w \in \\{a,b,\\}^\*\\}$$

Now we have that $A \cap B = b\\{a,b\\}^\*$, which is clearly regular and infinite.

# Answer
> 0 votes
If L1 is non-regular because something at the start and L2 is non-regular because something at the end:

```
L1 = a^n b^n a+ b+ ab, n >= 1
L2 = ab a+ b+ a^n b^n, n >= 1

```

then the intersection is ab a+ b+ ab and regular.

---
Tags: regular-languages, finite-automata
---


# Question
Title: Examples of problems in P but with verifiers with many computations
Let me first specify my question. I am looking for decision problems with polynomial algorithms but such that the simpliest or fastests verifiers do many computations. Here by verifiers I mean both YES and NO verifiers. It might be the case that this is too specific. By "verifiers with many computations" I mean verifiers that use non-trivial computational methods (e.g. dynamic programming, transforms, different methods of computational algebra etc.)

From what I understand most verifiers in $\mathsf{P}$ are either trivial or rely on good characterization theorems but are, themselves, not very complicated algorithms. Is this something to be expected from problems in $\mathsf{P}$? I mean these are the easiest of problems but some have really complicated good characterizations, I would expect that the complexity of the characterization translates somehow to the verifier (but from what I have seen this is not the case).

It might be the case that my question not interesting/stupid but to be honest I cannot see it.

# Answer
> 2 votes
There are none. For every problem in NP, there is a way to build a verifier such that the verifier is very simple and uses only trivial methods.

Proof: Let $L$ be any language in NP. Then it has a verifier $V$, such that $x \in L$ iff $\exists y . V(x,y) = \text{true}$. We call $y$ the certificate or witness.

Now let's construct a new verifier, $V^\*$, as follows. The input to $V^\*$ is a pair $(x,y^\*)$, where the witness $y^\*$ has the form $y^\*=(y,(s\_1,t\_1),(s\_2,t\_2),\dots,(s\_k,t\_k))$. Here the second part of $y^\*$ is the transcript of the execution of $V$ on input $(x,y)$. In particular, if $V$ is a Turing machine, then $s\_i$ is the finite state it is in, and $t\_i$ is the content of the tape, after the $i$th step of execution. $V^\*$ checks whether the transcript is a valid record of an execution starting on input $(x,y)$, and whether it halts with output $\text{true}$.

Now $V^\*$ can be implemented by a very simple algorithm, that uses only trivial methods. The algorithm just checks that each step of execution was done correctly (i.e., looks at $(s\_i,t\_i)$ and $(s\_{i-1},t\_{i-1})$). This is easy to check, given how simple a Turing machine is. Also, it is efficient. The running time of $V^\*$ is at most the square of the running time of $V$.

---
Tags: algorithms, complexity-theory
---


# Question
Title: Efficient compression of simple binary data
I have a file containing ordered binary numbers from $0$ to $2^n - 1$:

```
0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111

```

7z did not compress this file very efficiently (for n = 20, 22 MB were compressed to 300 kB).

Are there algorithms that can recognize very simple structure of data and compress file to several bytes? Also I want to know what area of CS or information theory studies such smart algorithms. "AI" would be too broad, please suggest more concrete keywords.
Notion of symmetry should play fundamental role in data compression, but search queries "symmetry in data compression" and "group theory in data compression" surprisingly return almost nothing relevant.

# Answer
This seems to be a clear use case for delta compression. If $n$ is known a priori this is trivial: store the first number verbatim, and for each next number store only the *difference* to the previous. In your case, this will give

```
0
1
1
1
1
...

```

This can then with simple run-length encoding be stored in $\mathcal{O}(n)$ space, as there are only $\mathcal{O}(1)$ groups (namely, two) of different deltas.

If $n$ is not known, the simplest thing would be a brute-force search for the word-size for which this delta/run-length representation comes out shortest. Perhaps only do this search for randomly-chosen, $\sqrt{N}$-sized chunks, to amortize the overhead of finding $n$ while retaining good reliability.

Unlike D.W.'s “all or nothing” proposal, delta compression with run-length encoding can actually give sensible compression ratios for some simple real-world kinds of content, like low-resolution audio. (It is thus suitable for low-quality, very low-latency and low-power audio compression.)
> 28 votes

# Answer
Sure, of course there are algorithms. Here is my algorithm:

1. First, check if the file contains ordered binary numbers from $0$ to $2^n-1$, for some $n$. If so, write out a 0 bit followed by $n$ one bits followed by a 0 bit.
2. If not, write out a 1 bit, then write out the 7z-compression of the file.

This is extremely efficient for files of that particular structure.

The point is: there is no free lunch in data compression. You might be able to build a compression algorithm that compresses one type of file well, at the cost of compressing others worse. But, if you know a priori something about the nature of the files you will be compressing, you can optimize your algorithm for that particular type of file.

The area is "data compression". See our tag, and read textbooks on data compression.
> 44 votes

# Answer
Anything using a BWT (Burrows–Wheeler transform) ought to be able to compress that fairly well.

My quick Python test:

```
>>> import gzip
>>> import lzma
>>> import zlib
>>> import bz2
>>> import time
>>> dLen = 16
>>> inputData = '\n'.join('{:0{}b}'.format(x, dLen) for x in range(2**dLen))
>>> inputData[:100]
'0000000000000000\n0000000000000001\n0000000000000010\n0000000000000011\n0000000000000100\n000000000000010'
>>> inputData[-100:]
'111111111111010\n1111111111111011\n1111111111111100\n1111111111111101\n1111111111111110\n1111111111111111'
>>> def bwt(text):
    N = len(text)
    text2 = text * 2
    class K:
        def __init__(self, i):
            self.i = i
        def __lt__(a, b):
            i, j = a.i, b.i
            for k in range(N): # use `range()` in Python 3
                if text2[i+k] < text2[j+k]:
                    return True
                elif text2[i+k] > text2[j+k]:
                    return False
            return False # they're equal

    inorder = sorted(range(N), key=K)
    return "".join(text2[i+N-1] for i in inorder)

>>> class nothing:
    def compress(x):
        return x

>>> class bwt_c:
    def compress(x):
        return bwt(x.decode('latin_1')).encode('latin_1')

>>> for first in ('bwt_c', 'nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
    fTime = -time.process_time()
    fOut = eval(first).compress(inputData)
    fTime += time.process_time()
    print(first, fTime)
    for second in ('nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
        print(first, second, end=' ')
        sTime = -time.process_time()
        sOut = eval(second).compress(fOut)
        sTime += time.process_time()
        print(fTime + sTime, len(sOut))

bwt_c 53.76768319200005
bwt_c nothing 53.767727423000224 1114111
bwt_c lzma 53.83853460699993 2344
bwt_c zlib 53.7767307470001 5930
bwt_c gzip 53.782549449000044 4024
bwt_c bz2 54.15730512699997 237
nothing 6.357100005516259e-05
nothing nothing 0.0001084830000763759 1114111
nothing lzma 0.6671195740000258 27264
nothing zlib 0.05987233699988792 118206
nothing gzip 2.307255977000068 147743
nothing bz2 0.07741139000017938 187906
lzma 0.6767229399999906
lzma nothing 0.6767684639999061 27264
lzma lzma 0.6843232409999018 27324
lzma zlib 0.6774435929999072 27280
lzma gzip 0.6774431810001715 27292
lzma bz2 0.6821310499999527 27741
zlib 0.05984937799985346
zlib nothing 0.05989508399989063 118206
zlib lzma 0.09543156799986718 22800
zlib zlib 0.06264000899977873 24854
zlib gzip 0.0639041649999399 24611
zlib bz2 0.07275534999985211 21283
gzip 2.303239570000187
gzip nothing 2.303286251000145 147743
gzip lzma 2.309592880000082 1312
gzip zlib 2.3042639900002087 2088
gzip gzip 2.304663197000309 1996
gzip bz2 2.344431411000187 1670
bz2 0.07537686600016968
bz2 nothing 0.07542737000017041 187906
bz2 lzma 0.11371452700018381 22940
bz2 zlib 0.0785322910001014 24719
bz2 gzip 0.07945505000020603 24605
bz2 bz2 0.09332576600013454 27138

```

(Numbers here are 'first\_compressor second\_compressor time\_taken bytes\_out')

(BWT taken from here)

This is still 'not just a few bytes', but is nonetheless much better than just gzip alone. BWT + bz2 gets down to 237 bytes from 1114111 for a 16-bit input, for instance.

Alas, BWTs are far too slow and memory-hungry for many applications. Especially given this is a naive implementation in Python - on my machine I run out of RAM before 2\**20.

With Pypy I was able to run the full 2\**20 input, and it compresses it to 2611 bytes with a BWT followed by bz2. But taking over 3 minutes and peaking at over 4GB of RAM used...

Also unfortunately, this approach is still O(2^n) output space, it would appear - at least from curve-fitting 1..20.
> 16 votes

# Answer
PNG encoding does exactly what you want. It works on real life data also, not just extremely organized data.

In PNG, each row is encoded with a filter, of which 4 are specified. One of these is "encode this pixel as the difference between its value and the value of the pixel one above it." After filtering, the data is then zip'd using DEFLATE.

This filtering is a specific example of the Delta Encoding mentioned by leftaroundabout in his answer, except instead of following it up with Run Length Encoding you follow it up with the more powerful DEFLATE algorithm. It accomplishes the same goal, only DEFLATE will handle a larger variety of inputs while still providing the desirable compression ratios.

Another tool which is often used in scientific data where simple filter+DEFLATE isn't quite as effective is RICE encoding. In RICE, you take a block of values and output all of the most-significant-bits first, then all of the 2nd-most-significant-bits, all the way down to the least significant bits. You then compress the result. For your data that won't be quite as effective as the PNG style filtering (because your data is *perfect* for PNG filtering), but for a lot of scientific data it tends to lead to good results. In a lot of scientific data, we see the most significant bit tends to change slowly, while the least significant is almost random. This teases apart the highly predictable data from the highly entropic data.

```
0000000000       00000  most significant bits
0000000001       00000
0000000010  =>   00000
0000000011       00000
0000000100       00000
                 00000
                 00000
                 00001
                 00110
                 01010 least significant bits

```
> 9 votes

# Answer
Any practical algorithm searching for specific structures would be limited just to the structures hard-coded into it. You could patch 7z to recognize this specific sequence, but how often is this specific structure going to occur in real life? Not often enough to warrant the time it takes to check inputs for this input.

Practicalities aside, one can conceive of the perfect compressor as an algorithm which tries to construct the shortest program that produces a given output. Needless to say, there are no practical ways of doing this. Even if you tried a brute-force enumeration of all possible programs and checked whether they produced the desired output (not an entirely insane idea), you will run into the Halting problem, meaning that you will have to abort trial runs after a certain number of execution steps, before you know whether this program definitely cannot produce the desired output.

The search tree for such a brute-force approach grows exponentially with program length and is not practical for all but the simplest programs (something like 5-7 instructions long).
> 5 votes

# Answer
Compression ratios depend entirely on the targeted decompressor. If the decompressor can't decode sequential 4 byte numbers more compactly than 4 bytes per number then you are SOL.

There are various things that would allow encoding of sequential numbers. For example a differential encoding. You take n bytes at a time and then take the difference or the xor of the bits and then compress the result. This adds 4 options here to try for every byte count: identity `a'[i] = a[i]`; difference `a'[i] = a[i-1]-a[i]`; reverse difference `a'[i] = a[i]-a[i-1]`; and the xor `a'[i] = a[i]^a[i-1]`. That means adding 2 bits to select the methods and a byte count for 3 out of 4 options.

However not all data is a sequence of the fixed-length records. The differential encoding doesn't make sense for that (unless the compressor can empirically prove that it works for a bit of data).
> 4 votes

# Answer
I have a lossless compression algorithm that compresses randomized binary data at a constant of 28 bytes no matter the input size. Here is a run from 1000 generated bit sequence:

Random Binary Data: 0b1100001011100011000111111110111111101010110001001010101011001101111100011010000000011101010101111111011100000100011001001101000001001100011111000101001011010110011001100100101100011010111000111110111011101101000110011110001011100101110000011001100010010001111101100011011110000000101110001010011101010010110110111010101111100000001111101011010100011011101011110110110100110010001100001010101001000011101010100000000000010001000100000110101011000001001011110001111101100010000000000010011010101011110101000110110010111000001001000101001000111110100010110111100101101110001101010100010010000010111001110110111011111011011000010111010011100100011111000101010101011100110001110111001000011010111000001010100110110101110010011111101000111101001111000000101111110100000011111111100001110000100100101001011010101111100000010100000101100001000111001010110010100100010000110000101100011100011011001000001010111001111110110100010001110011101010000011000011000110110001111110010010111011011110011111011100101110 Original Data Size (bytes): 160 Compressed Number: 1 Steps taken: 1505 Original Length: 1000 Compressed Length: 1 Compression Ratio: 1000.0 Decompressed Number: 0b1100001011100011000111111110111111101010110001001010101011001101111100011010000000011101010101111111011100000100011001001101000001001100011111000101001011010110011001100100101100011010111000111110111011101101000110011110001011100101110000011001100010010001111101100011011110000000101110001010011101010010110110111010101111100000001111101011010100011011101011110110110100110010001100001010101001000011101010100000000000010001000100000110101011000001001011110001111101100010000000000010011010101011110101000110110010111000001001000101001000111110100010110111100101101110001101010100010010000010111001110110111011111011011000010111010011100100011111000101010101011100110001110111001000011010111000001010100110110101110010011111101000111101001111000000101111110100000011111111100001110000100100101001011010101111100000010100000101100001000111001010110010100100010000110000101100011100011011001000001010111001111110110100010001110011101010000011000011000110110001111110010010111011011110011111011100101110 Compressed Data Size (bytes): 28

\[Program finished\] when compressing a million bits in a sequence, it achieves ~ a million compression ratio while maintaining a 28 byte lossless constant.
> -1 votes

---
Tags: information-theory, data-compression
---


# Question
Title: NFA where there are two 0s separated by a multiple of 4
I've been following Automata and Formal Languages in my college and I came across this particular exercise. While the solution presented seems correct, I take on Automata Tutor trying this exercise a 0 out of 10. I can't understand what was wrong here cause overall it seems correct. Thanks a lot if you can help me.

# Answer
> 1 votes
There's a logic contradiction in the exercise; I tried both combinations but nothing seems to work. Tried the logic as Russel said, having a loop composed in this way. Also tried Steven reasoning, given the thought behind that. Seems like the automata at least in Automata Tutor has to begin with both 0 and 1, having a loop composed of 0/1, given the hints the exercise gives, then ending with a 1. The moment you put 0 as the second state goes into the loop and asks for the correct string to be 00000. Then one puts final state the fifth zero and the exercise combines other requests. Upon satisfying them all, I conclude that simply, the exercise itself is not totally correct behind, trying both of the logics linked here. Given this kind of exercise, which you can also find online in other places are implemented as I've shown before or in one other way, a little different but still, doesn't work on Automata Tutor. It's wrong on how the question is posed, I'll tell the teacher on that.

As also Hendrik noted, it's contradicting in the requests, cause one misinterpretes the other ones and it's all conflicting upon itself.

# Answer
> 1 votes
I am not sure if it is just me, but I think that the description of the language from the Automata Tutor is ambiguous. In my understanding, the description is for the language containing all string $w$ such that there exists two 0 in $w$ at positions $i$ and $j$ such that $i$ and $j$ are multiples of 4. I assume that the position of the symbols begins at 0. However, Steven's interpretation (from the comment above) that the language is the set of string that contains two 0 at positions $i$ and $j$ such that $j-i$ is a multiple of 4, also fits the description. It doesn't help that the two sample strings $00000$ and $01010$ works for both interpretations.

One way for us to know is for you to try to create an NFA for the two interpretations and see which one works. Here, I will only describe the NFA for my case and will let you or Steven to fill for the other one (although my construction can easily be modified to implement the other interpretation).

The idea is, the NFA at the beginning is allowed to consume a number of symbols whose total length is a multiple of 4. Think of this as the phase where the NFA guesses position $i$, the position of the first 0. Note that I said *allowed to consume* and *not required to consume* at the start since it is possible for $i$ to be 0, the start position in the string. You can implement this by having a loop composed of 4 states (including the start state) that may consume 4 symbols per loop. The start state is the beginning ang the ending state in this loop. When the NFA decides to exit/skip the loop, it means that it found $i$. So it will move from the start state to an intermediate state $q\_i$ while consuming a 0.

The next phase is to guess position $j$. At state $q\_i$, the NFA can consume 4 symbols at a time again in a loop (same as above, but the beginning and ending state of the loop is now $q\_i$). Otherwise, the NFA can guess to exit/skip this loop and read four symbols, with the last symbol being 0, and enter the accept state, which signifies that it found $j$ already.

Finally, at the accept state, the NFA will consume all remaining symbols.

# Answer
> 0 votes
Interpretation difficulties with *two 0s separated by a multiple of 4* aside, the depicted automaton makes a `1` a requirement.
Approach it from the end:
A `0` after the appropriate distance should take you to an accepting state. No further symbols should lead to a non-accepting state.
Before that `0`, there are three (judging by the example from the feedback. Or four, if I was to interpret *separated by a multiple of 4*) symbols which may or may not be `0`.
And another mandatory `0`.
Symbols preceding that don't matter.

# Answer
> 0 votes
The transition from state 2 to state 3 should be 0

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


# Question
Title: If a person accidentally deletes a few letters when they try to type "IDAHO" or "ILLIONOIS", then when is state name unclear or ambiguous?
## The Short Version of my Question

The following two regular expressions represent two sets of strings.

| REGEX | EXAMPLES OF STRINGS OF TEXT THAT MATCH THE REGEX |
| --- | --- |
| `I?D?A?H?O?` | “IDAHO”
“ID”
“IDH”
“IDAHO” |
| `I?L?L?I?N?O?I?S?` | “ILLINOIS”
“IL”
“ILINOI”
“ILLN” |

What regular expression (regex) represents the intersection of the two sets of strings?

---

## Additional Explanation

When we allow many different abbreviations for the names of the states "IDAHO" and "ILLINOIS" which abbreviations do we have to worry about matching both state names?

In the United States, there are two states named "**IDAHO**" and "**ILLINOIS**".

People write many abbreviations for the state names on mailing envelopes and cardboard boxes.

For example, people usually write, "**ID**" for "**IDAHO**".

An example of a mailing address in shown below:

```
John & Jane Doe
123 Somewhere Lane
Doetown, ID

```

If you accidentally delete a few letters when you try to write or type "**IDAHO**" or "**ILLIONOIS**", then at what point is your spelling of the state name unclear or ambiguous?

# Answer
Answer: `I?O?`.

Simple justification: neither D, A, nor H appear in ILLINOIS, so they cannot appear in the intersection. That leaves only I,O.

Systematic solution: Let me teach you the general way to solve this kind of problem. Convert each regexp to a NFA, then compute the intersection of both NFAs using the product construction. Each of those two steps has standard algorithms that can be found in a good textbook on automata theory (or here on this site).

Realistic answer: The premise is faulty. No one would write `AH` as an abbreviation of `IDAHO`. It's unlikely that all but one the letters of `IDAHO` will be accidentally deleted/omitted, leaving only `H`. So a more practical solution might be to gather some data on common abbreviations of each state and build a more realistic model of in what way people write each state name.
> 2 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Deciding whether a Turing machine decides a language $L$ in at most $n^2$ steps
Let $L$ be a language for which there exists some turing machine deciding it in at most $n^2$ steps.

> Is it decidable whether a given turing machine $M$ decides $L$ and runs in at most $n^2$ steps?

I expect the answer to always be "No", regardless of $L$, but I fail to see exactly how.

# Answer
This problem is indeed undecidable, assuming that $n$ is not a constant but refers to the length of the machine's input.

Consider the problem $P$ of, given a Turing machine $\mathcal{M}$, to decide if it runs in at most $|x|$ steps on every input $x$. Problem $P$ is undecidable.

For any constants $c,c' \> 0$, let $Q\_{L,c,c'}$ be the (promise) problem of:

* given a Turing machine $\mathcal{M}$ such that, for every $x$, either $\mathcal{M}$ halts on $x$ in at most $c\cdot |x|^2 + c'$ steps, or does not halt,
* decide if it runs in at most $c\cdot |x|^2 + c'$ steps on every input $x$ and decides $L$.

**Claim:** There exists $c,c'\>0$ such that problem $P$ reduces to problem $Q\_{L,c,c'}$.

*Proof:* Let $\mathcal{N\_L}$ be the Turing machine which decides $L$ in at most $n^2$ steps. The reduction maps $\mathcal{M}$ to the machine $\mathcal{M}'$ which, on input $x$:

* first, it simulates $\mathcal{M}$ on input $x$ for $|x|$ steps;
* if the machine didn't stop, it loops forever;
* otherwise, it simulates $\mathcal{N}\_L$ on $x$ for $|x|^2$ steps, and returns its output.

Then $\mathcal{M}$ runs in at most $|x|$ steps for every input $x$ if and only if $\mathcal{M}'$ decides $L$ and runs in at most $c\cdot |x|^2 + c'$ steps for every input $x$ for some constants $c,c'$.

Then, using the linear speadup theorem, you can show that the following problem is undecidable: given $\mathcal{M}$, does $\mathcal{M}$ decide $L$ and halts in at most
\begin{cases} |x|^2 \text{ steps} & \text{on every input $x$ of size at least $n\_0$}, \\ k \text{ steps} & \text{on every input $x$ of size at most $k$}, \\ \end{cases} for some constant $n\_0 \in \mathbb{N}$. This problem differs from yours only on finitely many inputs, and so your problem is undecidable.
> 5 votes

---
Tags: turing-machines, undecidability, rice-theorem
---


# Question
Title: Does $\mathsf{P} = \mathsf{NP}$ imply $\mathsf{PO} = \mathsf{NPO}$?
The class $\mathsf{NPO}$ is defined as optimization problems such that the corresponding decision problems defined with a threshold are in $\mathsf{NP}$.

Let $A$ be an optimization problem and $B$ a decision problem associated to $A$ with a threshold. If we can solve $B$ in polynomial time, is it the same for $A$?

I have the answer for some problems, but I am not sure it can be generalized. For example, the optimization TSP could be solved in polynomial time if we can solve the decision TSP in polynomial time:

* one can find the weight of a minimal tour, using dichotomic search;
* for each edge, remove it and check if there is still a minimal weight tour. If that's not the case, remove it, otherwise, keep it.

Another similar question (but I am not sure it is equivalent or not) is the one in the title of the post: does $\mathsf{P} = \mathsf{NP}$ imply $\mathsf{PO} = \mathsf{NPO}$?

# Answer
Every optimization problem is asking about what's the value of a certain parameter closest to some target that's achievable under certain conditions. For example:

> What's the largest clique in the given graph?

Here the clique size is the parameter, the target is $\infty$ and the description of the graph is the set of conditions.

The answer, quite clearly, can require more than one bit of information. Such a problem is called a function problem. Not every function problem is an optimization problem. For example, a function problem can be asking what is the satisfying assignment for the given boolean formula, rather than asking what's the maximum amount of clauses that can be satisfied at once. This establishes that optimization problems are a subclass of function problems.

When talking about $\mathsf{NP}$-optimization problems specifically, we can state that $\mathsf{NPO}\subset\mathsf{FNP}$. The latter being the class of function problems solvable by non-deterministic Turing machines that can run for polynomially bounded time. Its deterministic counterpart is called $\mathsf{FP}$.

The reasoning in your post is correct and from that it follows that $\mathsf{P=NP\iff FP=FNP}$. The property of the $\mathsf{NP}$-complete problems you are using is called self-reducibility.

As for $\mathsf{PO}$ and $\mathsf{NPO}$ specifically, it also follows that $\mathsf{PO\subset FP}$. Therefore, given $\mathsf{FP=FNP}$ it would follow that $\mathsf{NPO\subset FNP\cap NPO=FP\cap NPO}$. And it only makes sense to define $\mathsf{PO}$ in such a way that it is equivalent to $\mathsf{FP\cap NPO}$.
> 2 votes

---
Tags: algorithms, optimization, p-vs-np
---


# Question
Title: Why is my Forrest-Tomlin update worse than recomputing LU?
I wrote a simple C++ implementation of the revised simplex method that recomputes the LU decomposition of the basis from scratch on each iteration. I have to solve problems with many variables but few constraints (say, 50 constraints and 5000 variables or more), so I thought that was ok.

Then I decided to implement a basis refactorization approach, so I chose the Forrest-Tomlin basis update approach. I observed that the program became much slower! I would like to understand why and whether this is expected for the kinds of problems (few constraints, many variables) that I consider.

A few words on how I have implemented Forrest-Tomlin. Say that the initial basis matrix is factorized as $B = LU$. After $k$ updates, I have a factorization $B = LR\_1\cdots R\_k U$ (I am for simplicity ignoring the permutation matrices involved). Then to solve the system $Bx = b$ I have to solve $L R\_1 \cdots R\_k y = b$ and then $Ux = y$. Solving $L R\_1 \cdots R\_k y = b$ is easy since the matrices $R\_i$ are very special; solving a system $R\_i x = b$ takes linear time.

What I have observed after profiling is that most of the time was spent solving systems with the $R\_i$ matrices. With Forrest-Tomlin there is an added cost to solve a system, and since I have many more columns than rows, to find the incoming variable I have to solve many systems, which becomes less efficient the more updates I make. And this extra cost is much higher than computing the LU decomposition from scratch.

Does this make sense? Am I missing something?

# Answer
Forrest-Tomlin is designed to take advantage of the sparse nature of your problem. Since the extra cost does not scale with the number of variables, but the number of constraints, it is not the cause of the issue. The problem could lie in the design of the implementation.
> 0 votes

---
Tags: linear-programming, linear-algebra
---


title: Indexed Priority Queue change key

text:
# Question
Title: Indexed Priority Queue change key
So I was just studying about Indexed Priority Queues and I got confused about the increase key operation.

So basically we have the option to increase a key for an element in log n time because we can look up the index using another array that maps keys to indexes. So let's say that *'A', 'B', 'C', 'D', 'E'* are mapped with priorities *1,2,3,4,5* respectively. So if I increase the key value of *'B'* from *2* to *1*, then that will mean updating the keys\[*1*\]=*'B'*. But now *'B'* is present in two places *1* and *2* which does not seem to be right.

https://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html. In this implementation, it is given to update the key assigned to an index. But what we really need to do is change the index of a key isn't it? That is what means changing the priority of an element in the queue. Or did I understand the algorithm wrong? Please correct me If I did.

# Answer
I think your confusion is due to the fact that you are looking at keys and priorities separately, whereas in the implementation you are referring, they are treated as one. That is, keys are expected to be drawn from some ordered set (they are required to be `Comparable` in the implementation ) and their precedence from the set they are drawn define their priorities.

Consider your example `K =['A','B','C','D','E']`. We assume for the moment that their priorities are based on how they are arranged lexicographically and not based on how you define it in your example . It is important to note here that keys are expected to have indexes prior to inserting them in the priority queue. We achieve this by storing them first in an array, but this is not necessary and you can use whatever means possible to map keys to indices. Now, adding each key to the priority queue is done as `insert(i, K[i])`, for $0 \leq i \leq 4$. This is equivalent to assigning to each index $i$ a priority $K\[i\]$. That is why you observed that the update key changes the assigned key to an index.

I believe what you want is to treat each entries of $K$ as some ordinary element and not as keys, hence not as priorities. You define priorities of the elements using another array $P = \[1,2,3, 4,5\]$ such that the correspondence between elements and priorities is based on their indices. The proper way to store this in the indexed priority queue is `insert(i, P[i])`. To update the priority of an element to $p$, say the priority of 'B', you perform `increaseKey(1,p)` since the index of 'B' in $K$ is 1.

As a final note, observe that to be able to update the priority of an element, you must be able to find its index in $K$. To efficiently perform such queuries, you might want to use a Map to represent $K$ instead of an ordinary array.
> 0 votes

# Answer
In a usual priority queue, you insert items, and you delete the top item. To change a key, the obvious way would be to remove the item, change the key, and insert the item back. The problem is: You don’t know where the item is in your heap. And searching would be O(n) for n items in the priority queue.

Since you know the location of the item, you can remove and re-insert it. Both operation obviously need t be done carefully; other items will be moved and you keep track of these changes. And finally you change the location of the item whose key you changed.

If you say “increment the key” it seems the change in the key is small, so the item would be close to or even in its correct location. Since you know the location of the item, you can start at the top and for the new key you follow the path to the old key as far as possible, minimising the work to be done.
> 0 votes

---
Tags: algorithms, priority-queues
---


# Question
Title: What is "the ability of classical control operators to return multiple times from a single term"?
I am puzzled by a point in this paper by Phil Wadler.

> Figure 6 shows a proof of the law of the excluded middle, $A ∨ ¬A$. The computational interpretation of this proof exploits the ability of classisal \[sic\] control operators to return multiple times from a single term. The term of type $A ∨ ¬A$ first returns an injection into the right of the sum, a continuation that expects a value of type $A$. If the continuation is ever passed such a value, then the original term of type $A ∨ ¬A$ now returns an injection into the left of the sum, containing the value passed to the continuation.

The article includes a sort of parable about the devil, which I don't understand. The parable is also featured on Chris Marten's website, in interactive form, but I don't quite understand that either.

So, my question is, what is this "ability of classical control operators to return multiple times from a single term"?

I think I understand the following:

* $¬A$ is equivalent to $A → ⊥$, which, in the computational interpretation, is a function which takes an A and never returns.
* $A ∨ ¬A$ is equivalent to $¬A → A$ (but also, by commutativity, to $A → ¬A$?) \[Correction: it is equivalent to $A → A$ and $¬A → ¬A$\]

What I am clearly a bit shaky on is the relationship between a negated term and a term which "takes" a value. I assume that this has something to do with the idea of "negative position", but I am struggling to learn more.

# Answer
The control operators in question allow you to capture continuations such that calling the continuation is in some sense equivalent to "returning from" the expression. so, for instance, in (using Haskell syntax):

```
callCC (\k -> ...)

```

There are two ways for the expression to "return" to its context:

1. The `...` can produce some value, and that value is returned
2. Something can call `k` with a value, and that value is effectively 'returned' to the same place

*But*, the kicker is that 2 does *not* require the call to `k` to happen according to the stack discipline that you might be used to thinking about. So, for instance, something as simple as:

```
callCC (\k -> k)

```

results in a continuation value being returned, and if that continuation value is subsequently called, control effectively *jumps back* and "returns again" with whatever value the continuation was called with, even though you are *no longer "within" the lexical scope of the expression*.

So, the `callCC ...` expression can effectively "return" as many times as we can arrange for a smuggled copy of the continuation to be called, because calling the continuation works just like returning from the expression. The expression I gave above is not easy to give a type to, but excluded middle is, and we can implement it like:

```
callCC (\k -> Right (\x -> k (Left x)))

```

So, initially, we return the normal way, with an $A → ⊥$ value in the right-hand case. This is our only choice, because we don't have an $A$ value yet to return. This $¬A$ value has a smuggled copy of the continuation, though. And if it ever gets called with an $A$ value, it calls the continuation to jump back and produce a left-hand case instead (because at that point, we *do* have an $A$ value).

Obviously, all this is not accomplished with actual "time travel" or whatever. It is implemented by saving, discarding, and restoring implicit control flow information. The result is largely the same as if you were jumping back in the program's execution history, though, *except* that other side effects are generally not undone.

Incidentally, $A ∨ ¬A$ is classically equivalent to $A → A$ and $¬A → ¬A$, not the two implications you gave.
> 2 votes

# Answer
Dan Doel's answer is helpful, but I want to include some more introductory info I've uncovered, about what "classical control operators" refers to.

First of all, "classical" doesn't refer here to classical logic. It refers to a range of control operators derived in the 80s and 90s, all of which provide the facility of reifying a continuation (i.e. storing a continuation as a variable). In some cases they offer the more powerful abstraction of delimited continuations.

Wadler's paper refers to Sussman and Steel's call/cc and Felleisen et al.'s $C$ operator. There are many other control operators from this era. They are discussed in (for example) in section 9.4.1 Classical Control Operators of the PLT Scheme manual.

Wikipedia has a different list, focusing exclusively on operators which support delimited continuations:

> Delimited continuations were first introduced by Felleisen in 1988 with an operator called $\mathcal {F}$ first introduced in a tech report in 1987, along with a prompt construct $\\#$. The operator was designed to be a generalization of control operators that had been described in the literature such as call/cc from Scheme, ISWIM's J operator, John C. Reynolds' escape operator, and others. Subsequently, many competing delimited control operators were invented by the programming languages research community such as prompt and control, shift and reset, cupto, fcontrol, and others.
>
> via https://en.wikipedia.org/wiki/Delimited\_continuation#History

call/cc has a type which corresponds to Peirce's Law, while the type of Felleisen's $C$ operator corresponds to double-negation elimination. Each of these theorems is not derivable in intuitionistic logic, but adding either of them to intuitionistic logic gives classical logic. In other words, they are equivalent to the law of the excluded middle.

It's tempting to surmise that the types of any of the classical control operators must add up to some theorems that, when added to intuitionistic logic, give classical logic, but I can't find any articles which confirm this. If this were true, it would imply that the word "classical" in "classical control operators" has a double meaning. The closest thing I've found is these lecture slides by Xavier Leroy: You’ve got to decide one way or the other! Classical logic, continuations, and control operators.

More generally, the term "extract" seems to occur in the literature when referring to the computational interpretations of logical proofs. I was not aware of of this, and it seems to make clear that using the Curry-Howard isomorphism to turn the law of the excluded middle into "code" is a bit of an extrapolation. Frank Pfenning's lecture notes refer to this particular case as evidence that "the whole enterprise of a computational interpretation of classical logic \[is\] brittle and ultimately unsatisfactory".
> 0 votes

---
Tags: logic, curry-howard
---


# Question
Title: How to solve Tower of Hanoi iteratively?
It may seem obvious to many but i am having a hard time figuring out the iterative solution to the Tower of Hanoi problem. There are some solutions on the Internet but without explanations. So can anybody give a sound explanation so that it becomes more intuitive and easy to reason.

# Answer
> 5 votes
You can transform the recursive solution to an iterative solution. To do this, create a stack that will contain items consisting of quadruples ("from", "to", "via", "num\_disks"). For every function "call" in your recursive algorithm, push the parameters to a stack in the iterative algorithm. For every function "return" in your recursive algorithm, pop the parameters from the stack in the iterative algorithm.

Wikipedia has the complete iterative solution.

# Answer
> 3 votes
The iterative solution can be figured out analyzing the recursive solution. Two things worth notice are that:

1. Total no. of moves required are $2^n - 1$ where n is the number of disks. This can be evaluated by the recurrence of the recursive solution.
2. If the poles are arranged in space as:

then for the even number of disks the movement of disks will start in clockwise direction and if the number of disks is odd then the movement will start in anticlockwise direction.

With the help of above two observations we can devise the algorithm as:

```
TowerOfHanoi(source, destination, auxiliary, numDisks)

1. Calculate total no. of moves as pow(2, numDisks) - 1. numDisks is no. of disks.

2. If numDisks is even then interchange the destination pole with the auxiliary pole. (This is to ensure that moves are in clockwise for even disks and anticlockwise for odd disks)

3. for i = 1 to number of moves calculate in step 1:

   a. if i%3 == 1:
      legal movement of top disk b/w source pole and destination pole.
   b. if i%3 == 2:
      legal movement of top disk b/w source pole and auxiliary pole.
   c. if i%3 == 0:
      legal movement of top disk b/w auxiliary pole and destination pole.

```

What is **legal movement** b/w two poles?

The legal movement must respect the constraints of the TOH problem i.e. no larger disk should be placed on smaller disk and we must move only the top disk at a time.

**Cases** for legal movement:

1. **When one of the two poles is empty** we must move the disk from non empty pole to the empty pole.
2. **When the top disk of one pole is smaller than the other** we move the smaller of two disks to the pole with larger disk.

Why the **sub cases a, b, c** of **step 3** of the algorithm work?

We can think of them by starting the trivial cases when `i = 1, 2 and 3`.

For `i = 1`, since we have appropriately decided the sense of movement in `step 2` of algorithm, we can safely make a legal movement b/w source and destination.

For `i = 2`, since the auxiliary pole is empty we can shift the disk to it and have a legal movement b/w source and auxiliary pole.

For `i = 3`, we need to make space for the remaining disks of source so that they could be shifted to the destination. To make space we must have a legal movement b/w auxiliary and destination pole.

After these three trivial steps, if we run through the algorithm we will notice that after every three moves, the destination pole is in a state that it can accept a new disk. So after every three moves, we can go with the other three moves and so on till we exhaust all our moves.

I know that more formally it may be proved with induction but it is enough to get an idea.

# Answer
> 0 votes
Try to visualize the solution mentioned in Navjot Singh's Answer.

---
Tags: algorithms
---


# Question
Title: Why, for Reed-Solomon codes, does the alphabet size depend on block length?
I'm learning about Reed-Solomon codes so apologies if this is a basic question. The alphabet size $q$ in RS codes grows with the block length $n$ \- in particular, we have $q \geq n$.

But intuitively, what's the reason behind this constraint? This is introduced as a part of the definition in the notes I'm reading and I see that it has implications later (e.g. Reed-Solomon codes can beat the Plotkin bound) but it's hazy to me why this must be the case.

# Answer
> 1 votes
You need a large enough alphabet to have enough degrees of freedom yielding codes with optimum minimum distance.

The idea of the RS codes comes from choosing generator polynomials with no conjugacy constraints (unlike the binary cyclic code case where the conjugacy constraints restrict the factorization of $x^n-1$ to products of irreducible factors in one to one correspondence with cyclotomic cosets) thus as a product of linear factors of the form $(x-c)$. Then one can simply choose a product of the form $(x-c)(x-c^2)(x-c^3)\ldots(x-c^{n-k})$ and this is the maximum degree of freedom possible in controlling consecutive roots and obtaining best possible distance.

Recall that in binary alphabet case, designing a BCH code you'll be forced to choose an irreducible factor of the form, e.g., $(x-c)(x-c^2)(x-c^4)$ which due to conjugacy will give a polynomial with coefficients over $GF(2)$ when multiplied out.

No conjugacy constraints are only possible if the generating polynomial and hence alphabet is over the full field $GF(q)$ as opposed to one of its subfields.

---
Tags: coding-theory, error-correcting-codes
---


# Question
Title: recursively enumerable and linear bounded automaton
I have a question about linear bounded automaton. Is it false that every recursively enumerable language is recognized by a LBA ? Because LBA has limited tape size so not all recursively enumerable languages can be recognized by an LBA because some of them may require unbounded space for their recognition ?

# Answer
> 0 votes
One answer to your question can be that if all recursively enumerable languages could be recognised by an LBA, Then LBA would be as powerful as Turing machine. Also we know that the set of languages recognisable by a LBA is equal to set of languages produced by context sensitive grammers. Also we know that restricted grammers are more powerful than context sensitive ones. So LBA being as powerful as Turing machine contradicts the fact that there are languages which have restricted grammers but don't have context sensitive ones.

Another answer can be that if LBA is as powerful as Turing machine, Then halting problem for LBA should be unsolvable which is not, So there is some language which can be recognised only by a Turing machine.

---
Tags: computability, linear-bounded-automata, recursively-enumerable
---


# Question
Title: Would it be possible to run destructors when aborting a thread?
I had a discussion with a C++ developer on whether aborting a thread causes memory leaks. His opinion on how aborting a thread works was

1. all destructors of the stack objects of the thread to abort are executed by the C++ runtime
2. the C++ runtime calls the OS method to abort the thread
3. the kernel gets rid of the stack memory and the kernel thread object

AFAIK, that's not how it is done today, especially not step 1. And since C++ is focusing more on performance than on correctness, I'd say this will never happen.

But: would that even be feasible without changing to garbage-collection memory model?

# Answer
You can abort a C++ thread in such a way that destructors of automatic ("stack") variables are called: just throw an exception that you don't catch (or that you catch only in a `try` block that wraps the thread's main function).

In a comment you said the question is about using `TerminateThread`. By design, `TerminateThread` stops thread execution immediately: "the target thread has no chance to execute any user-mode code", including destructors. It's safe to use only in very specialized circumstances. In general, a thread you terminate might, for instance, be in the middle of modifying a shared data structure while holding a lock. You can't solve this by having a background garbage collector notice the thread is gone and release the lock, because the shared data may be in a state that violates the lock invariant. The thread might even have been in the middle of acquiring or releasing the lock, leaving the GC with wrong information about the lock's state. It's not C++'s fault for "focusing more on performance than on correctness" (a claim I'd dispute in any case); it's simply impossible to guarantee correctness in the face of `TerminateThread`.
> 2 votes

# Answer
I agree, this is not how C++ handles thread abortion. I don't think such correctness guarantees can be achieved in C++ without turning to garbage collection (GC) techniques or binary instrumentation (BI) and changing the current semantics. C++ takes advantage of RAII, hence, it is the responsibility of the constructor to acquire and initialize resources, conversely, it's the duty of the destructor to undo such operations.

Generally speaking, the destructor of an object is executed at the end of the scope where it has been allocated or when the object is explicitly deleted. The former corresponds to additional code that invokes the destructor; it is placed at the end of the current scope and is filled in by the compiler.

The OS' abortion function is generally not graceful. Making it graceful in such a way that allocated objects are correctly freed is challenging. Notice it would require the help of the run-time execution support because the abortion should defer the invocation of the OS' primitive until all freeing has occurred.

Let's say we don't employ GC or BI, then it would require the execution of those pieces of code responsible for invoking the destructor, I think there are two possibilities, one applies at run-time, the other at compile-time:

1. bookkeep ordered references to all allocated instances for each (possibly nested) scope; at abortion time delete all objects pointed by such references via their destructors (this will have problems with loopful data structures),
2. rewire the execution flow in such a way that on abortion all code but the one responsible for invoking destructors is executed (impossible without some form of annotation).

The first proposal is a (badly) simplified version of GC. The second proposal is probably impossible to achieve in a general setting, it would require rewiring all functions of the program in such a way that when the abort function is invoked the program switches to an "abortion mode" that simply disables the execution of the business logic while allowing to execute destructors. I think it is technically possible to achieve a language behaving this way but it wouldn't be C++.

Conversely, let's say we are up to employ GC or BI.

On one hand, let's say we wan to employ GC. C++ is a non-cooperative language, hence making it work with a GC would challenging but the collector would be able to free those objects.

On the other hand, let's say we want to employ BI. This technique requires running the compiled program in a VM and switching to the abortion mode when the abort function is called. One open problem remains: How do we *reliably* distinguish the machine code required for freeing from business code?

Lastly, I think we can agree that it is far simpler and more effective to write the code in such a way that in case an error occurs we behave accordingly; either it IS critical, hence there is nothing to do, or it is not and there is still room for safely cleaning the environment.
> 1 votes

---
Tags: threads, c++, program-correctness
---


# Question
Title: How to translate the problem into a Communication Matrix?
**Description of the problem:**

Alice and Bob are both given as input the same graph and vertex $x$ and $y$ respectively. In the graph there are no self-loops and the given vertex can be the same.

Prove that communication complexity between Alice and Bob for deciding whether $x$ and $y$ are neighbours is at least $log \chi (G)$.

**Current Idea:**

The idea I had was the following: represent the protocol for communication between Alice and Bob as a Communication Matrix and partition it with monochromatic rectangles. From there I want to use the theorem/fact: $D^{CC}(f) \geq log (part(f))$ where $part(f)$ is the least number of monochromatic rectangles in any partition.

**Problem:**

I am not sure how this problem can be translated into a Communication Matrix. Would the inputs be vertices and then 1 would indicate presence of an edge and 0 otherwise?

# Answer
As @jschnei has mentioned in the comment, the answer is:

The communication matrix has rows indexed by Alice's inputs, columns indexed by Bob's input, and value f(x, y) at the cell in the row corresponding to Alice's input x and Bob's input y. In this case, when x and y are any vertices of a graph G, this should give rise to a very familiar matrix.
> 1 votes

---
Tags: complexity-theory, communication-complexity
---


# Question
Title: Testing whether a number (N) is prime or not can be made very fast but it will require storage space
Testing whether a number (N) is prime or not can be made very fast but it will require storage space.

If there is a central repository that stores all prime numbers found till now and if there is a webAPI that returns these numbers or one/few number(s) at a time (sequentially) then it will be very fast to test whether a number (N) is prime or not because now it will be just a simple lookup in the prime numbers file(s) to see whether the number (N) exists in these file(s) or not. The look up will be till the first number greater than N.

If the number (N) exists in these file(s), then it is a prime number else not.

What do people think about my algorithm?

# Answer
> 2 votes
It would be pointless. A well implemented sieve can find prime numbers much faster than you could ever download them.

Now creating a sieve storing a large number of primes will make trial division faster, since only about $2\cdot \sqrt n / \ln n$ divisions will be needed in the worst case.

But for large n primality testing can be done much faster, and so can factoring.

About your other answers: There are billions and billions of 1024 bit numbers that have been proven to be primes (needed in cryptography). Now divide billions and billions by 2^1024 and you see there is no chance that a random 1024 bit integer has ever been checked for primality. And worlds total storage capacity (which is a ridiculous number of gigabytes per person) is not enough to store all 22 digit primes.

# Answer
> 1 votes
Your algorithm is no good. It is not feasible to store all the prime numbers, or all prime numbers of a reasonable size (e.g., 1024 bits). That would require more storage than there are atoms in the universe.

# Answer
> -1 votes
The algorithm mentioned in the question has a storage problem (the required storage is not available as of now and I don't think it will be available in future also), otherwise, this algorithm is the fastest - because only a lookup in the prime number file(s) is required to find whether a number (N) is prime or not (lookup till first prime number \> N) and no divisions have to be done by all the prime numbers which are less than sqrt(N)).

The algorithm mentioned in the question can be effectively used by storing 1 billion 2048 bit prime numbers (in a central repository) to be used by encryption and cryptographic algorithms. Encryption and cryptographic algorithms can save time by getting prime numbers from this repository instead of calculating their own.

---
Tags: primes
---


# Question
Title: What are the definitions for "hard problem" and "easy problem"?
Take for example the following sentence:

> Computing a hash for a message is "easy"; retrieving the message from the hash is "hard".

Intuitively, I can perfectly understand what's written there. But, **in mathematical terms**, when is a problem considered hard and when is it considered easy?

I know that easy/hard should not be confused with "efficient", and I know that efficiency has to do with polynomial time complexity. Does it mean that hardness has nothing to do with asymptotic time complexity?

# Answer
They're not technical terms, so they don't have precise definitions. A problem is "hard" if it requires (or we think it requires) "large" computational resources to solve, and "easy" if it doesn't. "Large" depends on context but, in most contexts, a problem that can be solved in polynomial time is considered "easy".
> 9 votes

# Answer
I was taught in my Computer Science Algorithms class at IIT back in 1992 that "easy" problems are solved with a time/resource complexity of at worst X^3. This makes problems with solutions of x^4 or worse "hard" problems, as well as problems that have an exponential resource characteristic. But a "Google" search today does not provide for "hard" polynomial problems. Focus of "hardness" has been on NPC and NP-Hard for decades and the P vs. NP question.
> 0 votes

# Answer
My definition: Its easy if my computer can find a solution within a few days. And it’s hard if my computer cannot solve it within six months.

That’s instances, not problems. The travelling salesman problem is easy for 20 nodes. Problems are easy / hard if interesting instances are easy / hard. Matrix multiplication is easy, but multiplying two 250,000 by 250,000 matrices is hard.

At some point you decide what’s easy / hard for you.
> 0 votes

---
Tags: time-complexity, complexity-classes
---


# Question
Title: is there an efficient algorithm to find the optimal partition of a matrix?
Consider an $n \times n$ matrix of integers. Define a boundary in the matrix to be a sequence of cells, one per x-coordinate, where the y-coordinates of the boundary either stay the same or go up/down by one for successive values on the x-axis. I would like to find a boundary that maximizes the sum of the cell values on the boundary or "above" it. Here, above means on the side that includes the top left cell. Here is a picture of a non-optimal solution:

Is there an efficient algorithm for this optimization problem?

# Answer
> 4 votes
Call your matrix $A$ and define $S(r,c) := \sum\_{1\leq i\leq r}A\_{i,c}$.

Now call $D(r,c)$ the optimal value for the submatrix consisting of the first $c$ columns of $A$, for a path which ends at row $r$. For convenience, define $D(r,0):=0$ for all $1\leq r \leq n$ and $D(0,c):=DC(n+1,c)=\infty$ for all $1\leq c \leq n$.

Then, for all $1 \leq c,r \leq n$, we have $$D(r,c) = S(r,c) + \max\\{D(r-1,c-1),D(r,c-1), D(r+1,c-1)\\}.$$ This leads to a $O(n^2)$ time dynamic programming algorithm to find the optimal value, which is $\max\_{1\leq i \leq n}D(i,n)$.

I leave it as an exercise to you to work out the details, and modify the algorithm so that you not only get the value of an optimal path, but an optimal path itself.

---
Tags: algorithms, optimization, dynamic-programming
---


# Question
Title: Is the problem of "finding the output given the algorithm halts" not computable?
For simplicity, let's assume all Turing machines print 0 or 1 on the tape. Consider an algorithm $A$, which, given any Turing machine $T$ as the input, outputs $x\in \\{0,1\\}$, satisfying the condition that if $T$ halts, then the last symbol printed by $T$ is $x.$ When $T$ does not halt, it does not matter what the output of $A$ is.

Is it the case that algorithm $A$ does not exist (and thus the problem is undecidable)?

# Answer
> 1 votes
The assumption that the output is one bit does not actually simplify matters - the proof is easier for machines that can output strings.

Let $U\_M$ be the machine which simulates the machine $M$ and outputs the protocol of computation of $M$ (the sequence of successive configurations of $M$ until it halts). If $M$ does not halt, then $U\_M$ also does not halt. The encoding of $U\_M$ can be computed from the encoding of $M$.

Now we can solve the halting problem using the algorithm $A$: given $M$, construct $U\_M$, run $A$ on $U\_M$, and check that the result is indeed the protocol of computation of $M$. If it is the protocol, then $M$ halts, and if not, then $M$ does not halt.

Your version reduces to this one by asking for the protocol bits separately.

UPD: I realized there is an easier construction which uses the diagonal method directly. Suppose $A$ exists. Let $Q\_M$ be the machine which runs $M$ giving it $M$ as an input. Let $B$ be the machine which takes a Turing machine $M$, constructs $Q\_M$, runs $A$ on the machine $Q\_M$, and returns the negation of the result obtained by $A$.

Formally, if $\[M\]$ denotes the encoding of $M$, then by definition of $A$ we have $A(\[M\]) = M()$ if $M() \in \\{0, 1\\}$, and $A(\[M\]) \in \\{0,1\\}$ if $M() = \bot$. We defined $Q\_M() = M(\[M\])$ and $B(\[M\]) = \neg A(\[Q\_M\])$.

Note that $B(\[M\]) = \neg A(\[Q\_M\])$ is always defined, and we get a contradiction $B(\[B\]) = \neg A(\[Q\_B\]) = \neg Q\_B() = \neg B(\[B\])$.

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


# Question
Title: Schduling theory with weekends and holidays
My wife has a small workshop where she fixes dolls.
She works alone without any external help.
She has N orders from her clients, she estimates each order and she has deadline for each order.
She asks me to make a program which will create a schedule for her.
She wants to minimize a number of overdues. Also the program should take care of weekends and holidays.

It seems to be 1||SUM(Uj) problem where Uj is an order...
And there is Moore's algorithm for solving this.
https://web-static.stern.nyu.edu/om/faculty/pinedo/scheduling/shakhlevich/handout04.pdf
"Minimising number of late jobs" part is exactly about this.
But if we have to take holydays into account then
Orders:
A: estimate 1, deadline 3
B: estimate 2, deadline 2
C: estimate 3, deadline 5
c - current day, work day also
w - work day
h - holyday
c h h w w w

Moore's algorithm will position orders like this: B, A, C and all of them will overdue
But there is A, B, C and only B and C are overdue.
Hence Moore's algorithm does not work if holydays and weekends need to be taken into account.

Does anyone know how to approach such a problem?

# Answer
> 1 votes
I solved this problem by fixing units of measurement.
Estimates are counted in "work days", but deadlines are "calendar days"
So, if we take a count of calendar days before a deadline and subtract a count of holydays and other non working days then we will have a deadline in "working days" and Moore's algorithm works fine now.
We can get calendar dates by a similar (but vice-versa) transformation.

---
Tags: scheduling
---


# Question
Title: Algorithm question - check if there exists a path that touches A nodes exactly once and can revisit all other nodes
I am having trouble with a problem where I am given an adjacency list and a list of the nodes that must be visited exactly once to connect two nodes. What is the most efficient way of doing this? This problem is the Hamiltonian Path problem except it is only certain nodes that have to obey this principle. Let me know if there is a name for this problem or if anyone has an idea of how to efficiently do this in maybe polynomial time.

# Answer
As D.W. says, it is NP-hard, so we don't expect the problem to have a polynomial time algorithm, but it is FPT:

You can solve it in time $O(2^{|A|} n^5)$ which is polynomial if you consider $|A|$ *small*, e.g. $|A| = O(\log n)$. The factor $n^5$ can be improved.

Check out the (very accessible) paper by Shortest Cycle Through Specified Elements. Björklund, Husfeldt, and Taslaman, 2012.

This uses exponential space in $|A|$, but there are ways around that (e.g. using inclusion-exclusion methods by Nederlof).
> 2 votes

# Answer
You can't do it in polynomial time (unless P = NP), since it is as hard as the Hamiltonian path problem (consider the special case where you must visit all nodes). One standard approach if you have to solve it in problem and the graph is small enough is to use a SAT solver.
> 0 votes

---
Tags: algorithms, complexity-theory, graphs, hamiltonian-path
---


# Question
Title: I've heard that it isn't possible to encode product types and sum types in a simply typed lambda calculus, but it seems for me that it's false
Of course, it isn't possible to construct them directly since we hasn't these type constructors, but only function constructor (arrow). But suppose there are 2 types $A$ and $B$, from which we need to create a product (or tuple) type $A\*B$ and also sum type $A+B$.

Let's remember the algebra of types: functional type $A \rightarrow B$ is equivalent to exponentiation: $B^A$. Now we need to create some kind of composite type in which addition and multiplication can ultimately be replaced solely by exponents, so we encode the sum and the product.

$P^{A\*B} = (P^B)^A \Leftrightarrow (A\*B) \rightarrow P = A \rightarrow B \rightarrow P$ (functional constructor is right-associative)

and

$P^{P^{A+B}} = P^{P^A\*P^B} = (P^{P^B})^{P^A} \Leftrightarrow ((A+B) \rightarrow P) \rightarrow P = ((A \rightarrow P)\*(B \rightarrow P)) \rightarrow P = (A \rightarrow P) \rightarrow (B \rightarrow P) \rightarrow P$

In this answer, the last technique is called "virtual embedding" by continuation. At the same time, I also heard about some theorems about the non-existence of conjunction and disjunction in implicative propositional logic, but I don't understand why these "virtual" products and sums aren't counted. (According to the Curry-Howard isomorphism, everything demonstrated regarding type theory also works in implicative logic).

Where am I going wrong?

# Answer
A phrase like "it is not possible to encode product types in the simply-typed $\lambda$-calculus (without product types)" means: it is not true that for every type $A$ and type $B$, there exists some type $X$ such that $X$ is (isomorphic to) the product of $A$ and $B$. It does *not* mean that there exist no types that are isomorphic to a type involving a product (in a calculus having product types).

For instance, you are correct that, for all types $A, B, P$ in the simply-typed $\lambda$-calculus with products, we have that $P^{A \times B}$ is isomorphic to $(P^B)^A$, so that we can encode the former type with the latter type when we do not have products. But we cannot construct a type isomorphic to $A \times B$ alone.
> 7 votes

# Answer
You're looking for Church encodings, which are encodings of type constructions and datatypes in the *polymorphic* $\lambda$-calculus. That is, apart from having function types $\to$ we also need $\forall$ to quantify over all types.

For example, let us take your observation that $$((A + B) \to P) \to P) = (A \to B) \to (B \to P) \to P.$$ If we keep $P$ fixed then this is not very useful, but if we make sure that $P$ is arbitrary then it works: $$A + B = \forall P .\\, (A \to B) \to (B \to P) \to P.$$ The other observation of your works also to give $$A \times B = \forall P .\\, A \to B \to P.$$ And here are the natural numbers: $$\mathbb{N} = \forall P .\\, (P \to P) \to (P \to P),$$ The unit type is $1 = \forall P .\\, P \to P$, the empty type is $0 = \forall P.\\, P$, and so on.

This is just the basic idea. The topic has been studied by many people and there are lots of things to learn here. The Wikipedia links are a decent starting point.
> 2 votes

---
Tags: lambda-calculus, type-theory, propositional-logic
---