# Question
Title: Linear programming maximizes the minimum distance problem
I have a problem with creating an equation for linear programming solver.

Company wants to open stores in `k` cities. For the purpose of even coverage of the entire area, these cities should be selected from the available `n` candidates in such a way that it maximizes the minimum distance between any pair of selected cities.

I don't know how to define maximizes the minimum problem in graph in linear equation. Can any one give me some hints?

Thank you very much.

# Answer
Let's first define some variables.

$$x\_i \in \\{0, 1\\}$$ $$w\_i \in \mathbb{Z}^+$$

Where $x\_i=1\iff $ location $i$ is selected and $w\_i$ equals the minimum distance from node $i$ to any selected city if $x\_i=1$ and $\infty$ otherwise. We will use $D$ to represent $\infty$ and in practice $D$ can just be the diameter of the graph. We can constrain these variables below.

$$ \begin{align} \sum\_{i=1}^nx\_i &= k\\ w\_i & \leq \texttt{distance}(i,j) + D(2 - x\_i - x\_j)& \forall j\neq i \end{align}$$

It remains to find the minimum across all $w\_i$. We will let this minimum be $y$. We constrain $y$ as follows $$y \leq w\_i \\;\\; \forall i$$

Now the objective function is clear, we want to find the largest $y$ that satisfies our constraints $$\text{maximize }{y}$$

Our first constraint verifies that we select $k$ locations. The second gives us the minimum distance from a selected point to any other selected point. The third ensures that we find the minimum across these distances. Unfortunately, this is not a linear program but a mixed integer program.
> 2 votes

# Answer
If I have understood your question right, this an open NP problem. For 1D problem, there is a polynomial dynamic-programming algorithm. But for 2D, there exists an approximative greedy algorithm for solving it.

**Algorithm**

```
selectedStores = {}
randCity = choose a random city
stores ∪ {A}
while 1 to k
   choose the farthest city from all cities in selectedStores
end

```

As you may have guessed, you need to run a preprocess in *O(n^2)* to find all the minimum distances from each city to all other cities in case all of them are simple points on a plane or you can use the Floyd-Warshall algorithm for extracting shortest path from each city to others if you have a graph-based input.

Note that, by `farthest city from all cities in selectedStores` in the algorithm, it means considering the distance of all cities which are not selected for building a store to their nearest center (the city that is selected for building the store inside it) inside the selectedStores set. From all the left cities select the one which has the farthest distance to its nearest center (This policy is responsible for maximizing the minimum distance).

The selected cities are not the best optimal solution but it solves the problem in polynomial time and it is proved that the problem of cities on a plane (without path between them) solves the problem with cities needed to cover an area with a radius twice the covering radius of the optimal solution and it's not really important if there exists a path between them until you have calculated all the shortest paths before running the greedy algorithm.
> 1 votes

# Answer
With the hope of providing insight into how to solve your problem, I will refer to the case of a grid $N\times N$. Let $\rho\_{ij}$ denote the distance between two points $i$ and $j$, $i, j\in G$. The distances between any pair of nodes shall be stored as a *parameter* of your linear programming task, and can be given any values ---e.g., euclidean distance, Manhattan distance ...

There are various ways to model your case but I will go straight ahead to the one that (I think!) performs better because it requires less binary variables than other methods. Let $x\_{ij}$ denote the decision variable which takes the value 1 if and only if points $i$ and $j$ are selected and 0 otherwise ---it is also possible to set up a linear programming task with a binary decision variable $x\_i$ taking the value 1 if and only if location $i$ is selected but that leads to a quadratic number of binary variables. Obviously, $x\_{ij}=x\_{ji}, \forall i, j$, and this is the first constraint.

Secondly, to ensure that no more than $k$ points are selected, note that if $\sum\_j x\_{ij} \> 0$ then point $i$ has been selected (same reasoning could have been followed by columns). Thus, let $r\_i$ denote a binary variable whose value is computed with the following constraint: $Mr\_i \>= \sum\_j x\_{ij}, \forall i$. Clearly, if point $i$ is selected, then at least one variable $x\_{ij}=1$ for some $j$. Because $r\_i$ can only take values from the set $\\{0, 1\\}$, it is required to multiply it by an arbitrarily large constant $M$.

Only in appearance the constraint $\sum\_i r\_i = k$ ensures that exactly k points are selected. Note, however, that $r\_i=1$ means that point $i$ is connected to at least 1 point, so that the constraint just guarantees that *at least* $k$ points have been selected. Alternatively, the constraint $\sum\_{i,j} x\_{ij} = k (k-1)$ seemingly solves the issue by constraining the solver to select $k$ pairs of nodes so that the total number of pairs is exactly equal to $2{k\choose 2}$. This is wrong again as it is not guaranteed that these pairs are taken with the minimum number of points. However, putting both constraints $k$ points are necessarily selected.

We come now to the core of your question, how to model the minimum distance between each pair of selected points. As $x\_{ij}$ denotes whether points $i$ and $j$ have been selected, then let $d\_\<$ denote the minimum distance among all pairs of selected points: $d\_\< \leq x\_{ij}\rho\_{ij}$. This almost works as $d\_\<$ will be certainly upper-bounded by the minimum distance between each pair of selected nodes. Unfortunately, it forces $d\_\<$ to take the value $0$ because $x\_{ij}\rho\_{ij}=0$ for those cases where neither $i$ nor $j$ have been selected. To properly compute the minimum distance between each pair of *selected* nodes it is necessary thus to ignore those cases where either point has not been selected. For this, it just suffices adding $M (1-x\_{ij})$ resulting in the constraint $d\_\< \leq x\_{ij}\rho\_{ij} + M (1-x\_{ij})$ with $M$ being an arbitrarily large constant.

Finally, the objective function shall just simply maximize the minimum distance $d\_\<$: $\max z = d\_\<$

Hope this helps,
> 0 votes

---
Tags: algorithms, linear-programming, integer-programming
---


# Question
Title: Are all subsets of NP-complete languages also NP-complete?
Is the following assertion true or false?

> If the language $L$ is NP-complete and $Q ⊆ L$, then $Q$ is NP-complete.

I know for example that $k$-coloring is NP-complete if I take $k$ as input, but 2-coloring is an infinite subset of this which is in P (see link). Therefore, for me, the assertion is *false*. However, I'm working through languages, and I cannot figure out an example (with language) useful to show false the assertion.

# Answer
Take any infinite NP-complete language $L$. The language $L$ has uncountably many subsets, and particular there is some uncomputable subset $Q \subseteq L$. Since $Q$ is uncomputable, in particular it is not in NP, and so not NP-complete.

You can also try your example. Let $L$ consist of all pairs $(G,k)$ such that $G$ can be colored using at most $k$ colors, and let $Q$ consist of all pairs $(G,2)$ such that $G$ is bipartite; note that $Q \subseteq L$. It is known that $L$ is NP-complete, whereas $Q$ is in P. Therefore $Q$ is not NP-complete unless P=NP.
> 1 votes

---
Tags: np-complete
---


# Question
Title: Dividing unequal parts as equaly as possible
I'm dividing up an animation project among 20 students. The whole film is 4955 frames long, so each student should have as close to 248 frames as possible. However, the scenes have an unequal number of frames that cannot be changed, and each student must have a whole scene (nobody can have .45 of a scene.) What is the easiest way to divide these scenes up to make sure each student gets as close to 248 frames as possible?

# Answer
The original number of frames you have is 4955 frames and every student should receive as close to equal amount of frames as possible, the following is a solution I would suggest:

4955 frames / 20 students = 247.75

we take 247 (floor) and 248 (ceiling) as the possible number of frames that each student can get, now to figure out how many of those students should get 248 (the rest will get 247):

4955 mod 20 = 15

15 students will receive 248 frames and 5 will receive 247 frames

This works because .75 is 15/20 which therefore means 15 out of 20 got the ceiling value of the original division and the rest got the floor to equalise to .75
> 1 votes

# Answer
First define the function you want to minimise: Let A = number of frames divided by number of students, this is how many frames each student should get (but most likely not an integer).

Then if a student has $S\_i$ frames, count that as a deviation of $|S\_i - A|^k$ for k = 2 or 3 for example and optimise the sum of all deviations; if you choose k large then the optimum will avoid students being outliers.

A workable algorithm: Sort the scenes by number of frames in descending order. Take the scenes in turns and assign each of them to the student who currently has the lowest number of frames.

Then find two scenes that could be swapped to improve the total deviation, repeat until there is no swap improving the outcome.
> 0 votes

---
Tags: algorithms
---


title: Analysis of Pan-cake sorting

text:
# Question
Title: Analysis of Pan-cake sorting
i was implementing pan-cake sorting. We can implement it by taking largest element to start and flipping it recursively (**Like selection sort**).

However it is mentioned that the **A\[i\] has to be a permutation of \[1, 2, ..., A.length\].**

My question is, what if A\[i\] is not a permutation of \[1,2,..., A.length\]? How to solve that?

# Answer
> 0 votes
Let's suppose the input array is $A = \[3,1,4,5,2\]$. When sorting this array using pancake sorting, only flips of prefixes of the array are allowed. Flipping the first four elements, i.e. replacing $3145$ by $5413$, gives $A = \[5,4,1,3,2\]$. Then, flipping all five elements gives $\[2,3,1,4,5\]$, which brings the largest element to its correct position. By repeating this process to bring the next largest element to the last-but-one position, and so on, the array can be sorted.

The number of flips required to sort an array of length $n$ is at most $2n-3$. This is because bringing the largest $n-2$ elements to their correct positions can be done using at most $2n-4$ flips (because at most two flips are required for each element, as mentioned in previous paragraph). Finally, the elements in the first two positions can be sorted using at most one flip.

The problem of finding the minimum number of flips to pancake-sort an array is still open.

---
Tags: algorithms, algorithm-analysis, time-complexity, sorting, permutations
---


# Question
Title: Space Complexity of Bottom-Up Merge Sort
What is the space complexity of Bottom-up merge sort? It uses iteration rather than recursion so it will not use stack. But will an auxiliary array be used for the merge operation? Please explain. Thank you.

# Answer
> 1 votes
Yes, an auxiliary array is required for the merge operation. The space complexity would be $\Theta(n)$, where $n$ is the size of the input.

The merge subroutine can create a temporary array to store the result of the merge operation and its contents can then be copied into the input array. Or, an array having the same size as input can be created in the beginning and passed as an extra argument to the merge subroutine.

---
Tags: algorithms, sorting, mergesort
---


# Question
Title: What parts of linear algebra are used in computer science?
I've been reading *Linear Algebra and its Applications* to help understand computer science material (mainly machine learning), but I'm concerned that a lot of the information isn't useful to CS. For example, knowing how to efficiently solve systems of linear equations doesn't seem very useful unless you're trying to program a new equation solver. Additionally, the book has talked a lot about span, linear dependence and independence, when a matrix has an inverse, and the relationships between these, but I can't think of any application of this in CS. So, what parts of linear algebra are used in CS?

# Answer
> 10 votes
The parts that you mentioned are basic concepts of linear algebra. You cannot understand the more advanced concepts (say, eigenvalues and eigenvectors) before first understanding the basic concepts. There are no shortcuts in mathematics. Without an intuitive understanding of the concepts of span and linear independence you won't get far in linear algebra.

Some algorithms only work with full rank matrices – Do you know what that means? Do you know what can make a matrix not full rank? How to handle this? You will have no clue if you don't know what linear independence is.

The Gaussian elimination algorithm that is used to solve linear equations can actually be numerically unstable if implemented improperly, and this is something that you might have to worry about in some cases. Without understanding the algorithm you won't know where the problem comes from and whether there's anything you can do about it – not at the level of algorithms for solving linear equations, but at the level of coming up with the correct linear equations to solve.

In short, don't be lazy, and take it on faith that these things are useful.

# Answer
> 7 votes
Linear algebra is sometimes extremely useful and powerful in graph algorithms. With the matrix-tree theorem you can efficiently count the number of spanning trees a graph has (you need to understand eigenvalues). A more challenging application, where you need an even firmer grasp of linear algebra is the FKT algorithm for computing the number of perfect matchings in a planar graph in polynomial time.

There are many more exciting examples of uses of linear algebra in algebraic graph theory and spectral graph theory. The algorithms that arise are not only for counting problems like the two examples I gave. For instance, you can also check for connectivity, or compute the diameter of a graph.

# Answer
> 6 votes
One of the most well known uses of linear algebra is in Google's Pagerank algorithm:

> The PageRank values are the entries of the dominant left eigenvector of the modified adjacency matrix.

# Answer
> 3 votes
Almost anything involving computer graphics, animation, computer vision, image processing, scientific computing, or simulation of physical phenomena will involve extensive use of vectors and matrices (linear algebra) from simple things like representing spatial transformations and orientations, to very complex algorithms. These things used to be the domain of supercomputing, but now these very same fields are the core of all the coolest apps on your desktop, phones, and everywhere else, from video games to computational photography to self-driving cars. Linear algebra is everywhere.

# Answer
> 2 votes
There are plenty of matrix algebra based algorithms and techniques out there. And that's great. Principal component analysis is an example of some fairly useful applied linear algebra. The same can be said about Fourier analysis, which also has its roots in orthogonality and inner products. So there are direct applications.

**BUT**, even more importantly, taking a linear algebra class is valuable because it teaches you to think in a certain way. Most good linear algebra classes place emphasis on generalisation, logic and proofs. Is something true in general, or just certain specific, common cases? How can you be certain? Being able to think about how to prove your assumptions is good because it helps you keep yourself from making bad assumptions and writing code that doesn't generalise in the way you're assuming it does. It also helps you think about how to generalise things which might otherwise be difficult to generalise, and that let's you solve bigger problems.

In summary, it's good to keep in mind that linear algebra is good because it's weight lifting for the part of your brain that is useful in computer science.

# Answer
> 0 votes
Solving a system of linear equations (which can be done with the Gaussian elimination method), linear programming (which can be solved with the simplex method), least squares, and compressed sensing (see the Wikipedia article) are practical problems that arise in many application areas. Linear algebra helps with developing correct and efficient algorithms for these problems.

See the text \[Cormen, Leiserson, Rivest and Stein, "Introduction to Algorithms, Third Edition"\], where Chapter 28 is on matrix operations and Chapter 29 is on linear programming.

---
Tags: education, linear-algebra, didactics, mathematical-foundations
---


# Question
Title: Is the constant pi (not Raspberry) ever used in general computer science?
Is the constant pi (not Raspberry) ever used in general computer science? If so, how so or when is it applicable?

# Answer
> 1 votes
The $\pi$ constant is not used in theoretical computer science due to some intrinsic value or utility of the constant itself. However, it is (obviously) used in the simulations of physical systems or mathematical equations in which it appears. Precisely for this reason, one of the efforts that computer scientist and mathematicians have made in this regard was to identify new methods and algorithms to be able to generate as many digits of its decimal expansion as possible.

If today we know $\pi$ up to *31.4 trillion decimal places* we owe it to the computational power of electronic systems.

# Answer
> 0 votes
One assumption that is often used by researchers in the wireless sensor networks community is to model the region of coverage of a transmitter node as a circle (of unit radius, say) centered at that node. The graph representing such a network is called a *unit disk graph* because the vertices of the graph correspond to certain locations in the plane, and two vertices are joined by an edge if and only if unit disks centered at those locations intersect. You can search the literature for "unit disk graphs" - my guess is that pi shows up many papers that investigate theoretical bounds or guarantees on the performance of such networks.

# Answer
> 0 votes
$\pi$ does show up in the fast Fourier transform, which is a central algorithm in many areas of computer science.

---
Tags: computer-architecture, computer-networks, computer-algebra
---


title: Proving a language is not Semidecidable

text:
# Question
Title: Proving a language is not Semidecidable
I have the language $L = \\{ \langle M\_1, M\_2 \rangle : L(M\_1) \subset L(M\_2)\\}$ and I'd like to prove that it is not Semidecidable. To do so, I need to use a reduction from $\neg H$. I cannot use Rice's theorem. I'm having a hard time with this, and would appreciate a walkthrough.

# Answer
Using contradiction suppose $L=\\{\left\< M\_1,M\_2 \right\>|L(M\_1)\subset L(M\_2)\\}$ is semi-decidable. So there exists Turing machine $T$ which for input $\left\<M\_1,M\_2\right\>$ if $L(M\_1)\subset L(M\_2)$ will halt and accept.

We should use this Turing machine $T$ to make another Turing machine $T'$ which halt and accept on input $\left\<w,M\right\>$ if $M$ doesn't accept $w$. To do so, you have to make another Turing machine $M'$ using $w$ that you are sure $w\notin L(M')$. Thus you can give $\left\< M',M\right\>$ as input to $T$ and look for its output. If it accept it means that $L(M')\subset L(M)$ which means $w\notin L(M)$.
> 1 votes

---
Tags: formal-languages, semi-decidability
---


title: Human brain vs computer

text:
# Question
Title: Human brain vs computer
I am looking for a problem that can not be solved by computer but can be solved by human while computer can verify if the answer is correct or not. In fact what is the question in my head is that is there a way to clearly show the smartness in human brain compared to huge computation power of the processors.

# Answer
This is indeed, an open problem. The ***Church-Turing thesis***, in its most popular conception, states that anything that can be computed by a human with a pen and paper can be computed by a ***Turing Machine***. We have not yet been able to prove or disprove this thesis, therefore no one can tell you such a problem.
> 2 votes

# Answer
We know that there are problems (like the halting problem) that absolutely cannot be solved by a computer because there is no algorithmic solution. But a human cannot solve those problems either.

We also know that there are problems that humans can solve, but which we do not know how to solve with a computer *with our current state of knowledge and technology*. Problems in image processing ("is there a teddy bear in this picture ?") or natural language processing ("do these two English sentences have equivalent meanings ?") fall into this category. The difficulty here is showing that any of these problems absolutely cannot ever be solved by a computer, given a clever enough program and enough processing power and time - it is not at all clear how you could establish that.

We do not know of any problem that can be solved by a human and absolutely cannot ever be solved by a computer, no matter how powerful.
> 2 votes

---
Tags: algorithms, complexity-theory, artificial-intelligence, computer-vs-human, human-computing
---


# Question
Title: Can every regular expression be written as sum of products?
I was trying to prove that Parikh Image of every regular language is semi-linear. Even though it is true for CFL, but this question was about regular languages. To prove this, I decided to proceed as follows:

**Lemma 1:** Every regular expression can be written as *sum of products with star*, i.e., $R = R\_1 + R\_2+ ... +R\_n $ where each $R\_i$ is a regular expression not involving any $+$.

**Lemma 2:** The Parikh image of a language corresponding to a regular expression that doesn't involve any $+$ is linear.

I proved the lemma 2 by induction on the structure of this specific type of regular expression. (which was easy and correct, by the way).

After proving (allegedly) these, it was easy to state that the Parikh image of the language defined by $R$ is just the union of linear sets, hence it is semi-linear.

I proved the lemma 1, again, using induction on the structure of the regular expression, but I am not sure if it is correct. Moreover, I am not sure if the **Lemma 1** is even valid or not!

My proof was as follows:

1. $R = a $ where $ a \in \Sigma$ or $a=\epsilon$. This is already in the same form we required.
2. $R = R\_1.R\_2$ . This is also in required form.
3. $R = (R\_1 + R\_2).R\_3$. Replace by $R\_1.R\_3 + R\_2.R\_3$.
4. $R = (R\_1 + R\_2)^\* $ Replace by $(R\_1^\*.R\_2^\*)^\*$

Do you think this proof is wrong, or even worse, the statement if wrong!

# Answer
> 3 votes
I think you have to be more careful in the inductive steps, but it seems you basically have the argumentation ready. According to me proper induction would be

> If $R\_1$ and $R\_2$ can be written as sum of products, then so can $R\_1\cdot R\_2$, $R\_1+R\_2$ and $R\_1^\*$.

The proof could be completed as:

If $R\_1$ and $R\_2$ can be represented as sum of products as $R\_1 = R\_{11} + R\_{12} + ... + R\_{1n}$ and $R\_2 = R\_{21} + R\_{22} + ... + R\_{2m}$, then:

1. $R = R\_1\cdot R\_2$ will be equivalent to ($R\_{11}\cdot R\_{21} + R\_{11}\cdot R\_{22} + ... + R\_{11}\cdot R\_{2m}) + ... (R\_{1n}\cdot R\_{21} + R\_{1n}\cdot R\_{22} + ... + R\_{1n}\cdot R\_{2m})$, by the distributivity of concatenation over union, which is in the required form.
2. $R = R\_1 + R\_2$, then $R$ is already a sum of products.
3. $R = R1^{\*}$ can be reduced to sum of products by repeated application of the law: $(R\_1 + R\_2)^\* = (R\_1^\*\cdot R\_2^\*)^\*$ and distributivity of concatenation over union.

Hence we can write each regular expression as sum of products.

This is called the **disjunctive normal form** of regular expressions.

---
Tags: formal-languages, automata, regular-expressions
---


# Question
Title: Does there exist a subset of substrings for reconstructing another string?
I am looking for a high performance algorithm to check whether I can reconstruct a given string using a given set of substrings. More details:

Let's say our strings are over the alphabet $\Sigma$.

**Inputs**:

* A string $S \in \Sigma^\*$
* A finite set of strings $A = \\{a\_1, a\_2, ..., a\_n\\} \subset \Sigma^\*$.

**Output**:

* Whether $\exists m: \exists b\_1, b\_2, \ldots, b\_m \in A: b\_1+b\_2+\cdots+b\_m = S$

where $+$ is string concatenation.

For example, if $S={}$"$abcd$" and $A = \\{$"$ab$"$,$"$cd$"$,$"$ac$"$\\}$, the answer is True. For the purposes of this question, assume that strings in $A$ can be reused multiple times if necessary.

# Answer
> 3 votes
If reusing strings in $A$ is allowed you can solve it with dynamic programming: First, store strings in $A$ in a prefix tree (just a reversed suffix tree link), and recursively detrmine if $S\[i:end\]$ can be constructed from $A$: Let $\ell$ be the length of the string, and wlog assume $S$ is appended by $\\$$ and $A\gets A\cup \\{\\$\\}$. Moroever, let $m\[i\]\in\\{0,1\\}$ indicate if $S\[i:\ell\]$ can be constructed by elements in $A$. Initialize $m\[i\]\gets \infty$ for $i=0,\dots, \ell-1$ and $m\[\ell\]=1$ (because $S\[\ell\]=\\$$). Now, suppose $f(i)$ is the function that recursively computes $m\[i\]$ if it hasn't been computed already. When $f(i)$ is called, start at the root of the suffix tree of $A$, and traverse $S\[i\], S\[i+1\], \dots$ on the suffix tree until index $j$ , such that the corresponding node is in $A$, and recursively call $f(j)$. If returns $1$, set $m\[i\]=1$ and return $1$. Otherwise, repeat the process with traversal of $S\[j+1\], S\[j+2\], \dots$ until another member in $A$, or a leaf is reached. If there was no success, set $m\[i\]=0$ and return $0$. To decide the problem, call $f(1)$. The worst case complexity is the complexity is $\ell d$, with $d$ being depth of the suffix tree (longest sequence in $A$), plus the cost of construction of the prefix tree.

The worst-case scenario in many cases will be avoided because the recursive call search stops as soon as one solution is found. So in practice, the $\ell d$ part might be much less. The construction of the suffix tree can be expensive depending on $A$. But if $A$ is used for several strings $S$, the cost is amortized. If $A$ is really big and $S$ is short, it might be better to just sort elements of $A$ and do a binary search instead of traversal.

---
Tags: algorithms, strings, substrings
---


# Question
Title: CNF satisfiability with a bound on number of clauses
Consider the CNF-sat problem with n literals and k clauses. If k scales linearly in n, we get np-completeness (e.g., 3-sat where each literal appears at most 4 times). Do we still get np-completeness if we restrict attention to problem instances where k scales sublinearly in n? For this question, I am not requiring clauses to consist of 3 literals, but I still need the formula to be CNF.

More generally, how does complexity scale (for known algorithms) with k?

# Answer
Here is an $n^{O(k)}$-time SAT algorithm: try all (at most $n^k$) ways how to select one literal from each clause, and accept whenever the selection is such that it does not include any contradictory pair (i.e., a literal and its negation). So, if $k$ is substantially smaller than $n$, you get a subexponential algorithm, and you should not be able to prove NP-completeness of such a restricted problem.
> 2 votes

---
Tags: complexity-theory, np-complete, satisfiability, 3-sat, sat-solvers
---


title: search problem vs optimization problem

text:
# Question
Title: search problem vs optimization problem
This is mostly a terminological question: **Is there a fundamental difference between "optimization problems" and "search problems"?** **Apologies if this is an obvious question**

As I understand it, we can define the two as follows (note, I consider the problem for a fixed input size for brevity):

> **Search problem.** Given a set $X$ of candidate solutions, and a property $P:X\to \\{\text{True}, \text{False}\\}$, find an $x\in X$ such that $P(x)$.
>
> **Optimization problem.** Given a set $X$ of candidate solutions, and a criterion function $F:X\to \mathbb R$, find an $x\in X$ such that $x\in \arg\max\_{y\in X} F(y)$.

But it seems to me that to say that a search problem $P\_S$ is "reducible" to an optimization problem $P\_O$ is an understatement: They seem to be exactly the same apart from a "stylistic" difference:

> Given a search problem $P\_S=(X,P)$, define optimization problem $P\_O=(X,F)$ where $F(x) = \begin{cases}1 \quad \text {if } P(x)\\0\quad \text {if } \neg P(x) \end{cases}$
>
> Given a optimization problem $P\_O=(X,F)$, define search problem $P\_S=(X,P)$, with $P(x)= \begin{cases}\text{True} \quad \text { if } x \in \arg\max\_{y\in X} F(y)\\\text{False}\quad \text { if } x \notin \arg\max\_{y\in X} F(y)\end{cases}$

**Is there really not a fundamental difference between these two problems?** Or are they fundamentally different in some way that I'm overlooking?

# Answer
> 3 votes
The fundamental difference in these two problems lies in the verification of a proposed solution.

The solution of a search problem is only as hard to verify correct as the predicate itself.

The solution of an optimization problem needs special arguments or proofs to avoid having to search the entire domain to verify a solution correct, which often may not exist or are not known.

This means that simply finding a solution is enough for a search problem, but without a proof or exhaustive search an instance for an optimization problem is uncertain.

# Answer
> -1 votes
I think search problem is to search for a solution (or many solutions) that satisfies a condition. Whereas, Optimization problem is to search for the best solution that satisfies a condition. When the search space becomes large, we can't expect to be able to find out the optimal solution, then we turn the search problem into an optimization problem, with the hope that as searching for the best solution we may find some acceptable one. By doing so, we are using the optimization techniques which do not promise to find the optimal solution, instead of using the search techniques, which always do.

---
Tags: optimization, terminology, search-problem
---


# Question
Title: Algorithm to match / link complementary pairs
I'm working on a problem where I have a large number of pairs

e.g

1 -\> 2

4 -\> 3

2 -\> 8

..

And a "match" would be considered 1 -\> 2 and 2 -\> 8 to make 1 -\> 2 -\> 8, as "1 -\> 2" ends with 2 and "2 -\> 8" starts with 2.

Given a large set of pairs, i'd like to create the longest possible chain. I know I could brute force it, but I'm wondering if there is a better way

Edit - I can give more precise context for the problem (Sorry, i'm a student currently in data structures who has not taken an algorithms course)

The datapoints in the pairs would be song names which well flow together. There is a subreddit called "/r/ocrableach" which posts pairs of songs where the ending of one song blends well with the beginning of another song.

An item can appear multiple times in the data set, but i will be discarding repeats as i build my chain.

I'd like to pull posts from /r/ocrableach and try to build the longest continuous playlist based on the song pairs.

If I have the pairs

```
"Okra -> Bleach"
"Bleach -> I THINK"
"On God" -> "Okra"

```

I'd like to start constructing a linked list like this:

```
"Okra -> Bleach" and "Bleach -> "I THINK" match
= "Okra -> Bleach -> I THINK"

"Okra -> Bleach -> I THINK" and "On God -> Okra" match
= "On God -> Okra -> Bleach -> I THINK"

```

I'm essentially checking if the tail of one pair matches with the head of the "chain" to see if it can be added.

# Answer
> 1 votes
Assuming you don't want to repeat a song, this is the problem of finding a longest path in a directed graph. Here the graph has one vertex per song, and an edge $s \to t$ if the ending of song $s$ blends well with the beginning of song $t$.

Unfortunately, the longest-path problem is NP-hard. (See, e.g., Is finding the longest path of a graph NP-complete?, How to prove NP-hardness of a longest-path problem?.) This means that you should not expect to find an efficient algorithm for your problem that works on all graphs and that is always correct. Instead,if you want to solve it in practice, your best will be to look for approximation algorithms or heuristics.

Unfortunately, it is also known that there are no approximation algorithms with guaranteed performance, i.e., that are guaranteed to find a path that is close to the longest, for all graphs. (See https://en.wikipedia.org/wiki/Longest\_path\_problem#Approximation.) So your best bet is to look for heuristics... or hope your graph has some special structure.

If you are willing to allow repeated songs, then the problem becomes tractable in theory, but the resulting algorithms are probably going to provide poor-quality results in practice. In particular, if you find any cycle in the graph, then it is possible to traverse the cycle an unbounded number of times, achieving an arbitrarily long path. Unfortunately these algorithms have a decent chance of producing a cycle of short length, which means that your playlist will just repeat the same few songs over and over... which is probably not what you'd hope for.

One simple heuristic might be to pick a starting vertex randomly, do depth-first search starting from that vertex, find the leaf in the tree with largest depth, and use the path from the root to that leaf as your playlist. You could repeat a few times from a few different random starting points and take the best playlist found. There are no guarantees for how well this will perform; you'd have to try it out to see.

---
Tags: algorithms
---


title: TM decidable or undecidable problem

text:
# Question
Title: TM decidable or undecidable problem
Problem:

> Given a TM $M$ on the alphabet $\\{0,1\\}$, determine if there is some input on which $M$ executes for at least 5 steps.

Is this problem decidable or not?

To check if the problem is decidable or undecidable, I describe an algorithm as follow:

$A$: on input the TM $M$

1. $A$ generates all strings $w$ of length at least 5 characters.
2. For each string $w\_i$, $A$ runs $M$ on $w\_i$ and checks whether it performs at least 5 steps. If yes, $A$ accepts, otherwise $A$ repeats the control on the string $w\_{i+1}$.

Algorithm $A$ could run forever, and so one could not tell whether $M$ performs at least 4 steps on some input string. The problem sounds to me undecidable. However I can build a complementary algorithm of $A$ (i.e. $A'$) and I can build a new algorithm $B$ using $A$ and $A'$ in parallel. In this case the problem sounds to me decidable.

# Answer
Your problem is decidable. If $M$ always executes less than 5 steps, then it never sees more than the first 4 symbols of its input. Hence it suffices to run $M$ on all inputs of length at most 4.
> 2 votes

---
Tags: turing-machines, undecidability, decision-problem
---


# Question
Title: Test if there exists an integer k to add to one sequence to make it a subsequence of another sequence
Suppose that sequence $A$ contains $n$ integers $a\_1,a\_2,a\_3,\ldots,a\_n$ and sequence $B$ contains $m$ integers $b\_1,b\_2,b\_3,\ldots,b\_m$. We know that $m \geq n$. We assume without loss of generality that both sequences $A$ and $B$ are sorted in ascending order.

What's the fastest algorithm to determine if there exists an integer $k$ such that the sequence $a\_1+k,a\_2+k,a\_3+k,\ldots,a\_n+k$ is a subsequence of the sequence $B$?

Here is a naive algorithm, which would take $O(n(m-n))$ time. Store the sequence $B$ as a hashtable. For each element $b\_j$ of the $B$ (except the largest $n$ elements), use $b\_j-a\_1$ as your guess at $k$; you can verify this guess by checking whether each of $a\_1+k,\dots,a\_n+k$ are in the hashtable $B$. This takes $O(n)$ expected time per guess at $k$, and you make $m-n$ guesses, so in total the expected running time is $O(n(m-n))$. Can we do better?

I came across this problem while trying to match two binary images (testing whether one image contains the other).

# Answer
> 3 votes
Here is a heuristic that won't always work, but should work with high probability if the integers in the arrays are chosen randomly from a large enough space.

Initialize a hashtable of counts $C$ to all zeros. Then, repeat $t$ times: randomly pick $i,j$, compute $b\_j-a\_i$, and increment $C\[b\_j-a\_i\]$. Finally, sort $C$ by counts, from largest count to smallest; then for each of the largest few values of $C\[k'\]$, try $k'$ as your guess at $k$, and verify each guess.

Notice that in each iteration, the probability of incrementing $C\[k\]$ is at least $1/m$; whereas if $l\ne k$, we expect $C\[l\]$ to be incremented much more rarely (assuming the integers in the arrays are random and large enough). Thus, after $t$ iterations, we expect $\mathbb{E}\[C\[k\]\] \ge t/m$ but $\mathbb{E}\[C\[l\]\] \ll t/m$. So, once $t$ is large enough, $C\[k\]$ should be larger than every other entry in $C$.

How large does $t$ need to be? I expect that $t = O(m \log m)$ should suffice, based on a central limit theorem approximation for the counts $C\[l\]$, assuming we are willing to accept a small probability of error (which can be driven exponentially small). The constant factor hidden by the big-O notation might be non-trivial.

This is only a heuristic, and there will certainly be inputs where it fails.

# Answer
> 0 votes
Here is an algorithm running in $\mathcal{O}(n\sqrt{n} + m\log m)$ time.

Let $w$ denote the function that for integer $t$, counts the number of pairs that their difference is $t$: $w(t)=\lvert\\{(x,y): x\in A, y\in B, y-x=t\\}\rvert$. If we had access to $w(t)$ we could simply find its maximum and see if it's $n$ or not. The main idea is to estimate $w$ using the Fast Fourier transform. If the numbers are bounded it will produce the exact solution, otherwise, one can use modulus to a sufficiently big number and then verify the solutions once they're found.

Let $N,M$ be integers (to be defined later), and $u,v\in \mathbb{R}^N$ be vectors defined as $$u\[i\] = \lvert\\{x\in A\colon M-x\equiv i \pmod N \\}\rvert$$ $$v\[i\] = \lvert\\{y\in B\colon M+y\equiv i \pmod N \\}\rvert$$ Let $w=u * v$ denote the circular convolution of these two vectors. Then if there is $k$ such that $$\forall x\in A \exists y\in B: y-x=k,$$ then we can conclude $$ w\[k \bmod N\]=\sum\_{i: v\[i\]\neq 0} v\[i\] u\[i-k \bmod N\]= n$$ which by construction is the maximum value that $w$ can attain. Therefore, we only need check if $\max\_i w(i)=n$ or not. Then, we verify the correctness of the solution by checking the original elements. Computing $w$ can be done by FFT and inverse FFT in $\mathcal{O}(N \log N)$ time, and then finding the maximum element and verifying it takes $n$ steps, so overall $\mathcal{O}(N \log N)$ time and space.

If the numbers in both sets are bounded by $N$ this is an exact solution. But if you pick $N$ too small, $w(i)=n$ can happen because of collisions. So we can verify all elements for all the indices that $w(i)\ge n$; there might be several of them, but their number can be bounded. To have $\ell$ such indices, one must have at least $1+2+\dots + \ell$ collisions, which implies $$P\[\lvert\\{i\colon w\[i\]\ge n\\}\rvert \ge \ell\] \le P\[\text{# collisions}\ge (\ell+1)\ell/2\].$$ There are $nm$ pairings of elements of $A$ and $B$. If we pick a prime number $N$ such that $N\>2m$, and pick $M$ uniformly at random from $\\{1,\dots,N\\}$, the collision probability is bounded by $1/2m$, so by Markov's inequality is $$\le \frac{nm/N}{\ell^2/2}\le \frac{n}{\ell^2}$$ So with probability as close to $1$ as you want, $\ell=\mathcal{O}(\sqrt{n})$. Therefore, the overall time complexity of the algorithm is $$\mathcal{O}(n\sqrt{n} + m\log m)$$ in which $m\log m$ is the FFT and iFFT step (since we set $N=2m$), and $n \sqrt{n}$ is the verification step.

There are two ways I see to improve this:

1. One can run $\log n$ separate instances of the algorithm without the verification, and take the intersection of maximum indices that $w\[i\]\ge n$ (after shifting by $M$). If one can show that the number of shared collisions drops by $1/2$ or some other constant every time, this would show a total running time of $\mathcal{O}(m\log^2 m)$.
2. One can construct a better hashing mechanism for $u$ and $v$ and use higher moments for Markov and make the concentration sharper.

Nevertheless, if you're looking for a practical solution this algorithm could work just fine. For instance, the worst-case behavior $\ell\approx\sqrt{n}$ only occurs when the sets are nearly arithmetic progressions. If you pick elements nearly randomly, the guarantee will be much stronger. Furthermore, you can stop the verification step as soon as you find a mistake.

# Answer
> 0 votes
This is a completely different algorithm, which I believe works in $O(m\log m)$ worst case, and should work for integer or real numbers.

Let us assume that $A$ and $B$ are already in ascending order, otherwise spend $O(n\log n+ m\log m)$ to sort them. We slightly strengthen the requirement for algorithm $\mathcal{A}(A, B)$ to return all indices $i$ such that $A$ can be mapped to $B$ with offset $k=b\_i-a\_1$, meaning that the mapping starts at $b\_i$ onwards. The high-level idea is to solve the sub-problems corresponding to a subarray of $A$ and merge the indices in a way that only valid solutions remain.

The recursion, however, depends on how close $A$ is to an arithmetic progression. Formally, let periodicity $\tau(A)$ be defined as: $$\tau(A) = \min \\{s\in\mathbb{N}^+: a\_{i+s+1}-a\_{i+s}= a\_{i+1} - a\_i \text{ for all valid } i, s\\} $$ In words, this means elements of $A$, are periodic with a minimum cycle $\tau(A)$, up to some offset.

**Case I ($\tau(A)\<n/3):$** Let $s=\tau(A)$ and $\ell = a\_s - a\_1$. Recursively compute $I=\mathcal{A}(A\[1:s\],B)$. One observation is that if $i,j\in I$, corresponding to index sets $J\_i, J\_j$, and $b\_j - b\_i = \ell$, the index sets $J\_i, J\_j$ can be concatenated to show $i\in \mathcal{A}(A\[1:2s\],B)$. This is a simple consequence of $A$ being $s$ periodic, and $b\_j = b\_i + \ell$ ensures that the index set $J\_j$ starts where $J\_i$ ends. Let $$R\[i\] = \lvert\\{j \in I\colon j\>i, b\_j - b\_i \text{ divisible by } \ell\\}\rvert$$ Then, $R\[i\]$ can be computed based on $R\[i'\]$ that $i'\>i$, and the new index set $I'$, is the indices that $R\[i\]\ge n/s$. The cost for this step is bounded by $O(m)$.

**Case II ($\tau(A)\>n/3$)**: By definition, for $s=n/3$ there should be an index $i$ that $a\_{i+1}-a\_i \neq a\_{i+1+s}-a\_{i+s}$. If $i\le n/3$, we will have $i,i+s\le 2n/3$ which certifies that $\tau(A\[1:2n/3\])\>n/3$. Otherwise, $i\>n/3$ implies that $\tau(A\[n/3:n\])\>n/3$.

Wlog assume $\tau(A\[1:2n/3)\>n/3$, and choose the lower half $A'=A\[1:n/2\]$ to recurse on (otherwise choose the upper half, same arguments would follow). Recursively compute $I=\mathcal{A}(A',B)$. For each index $i\in I$, check if the rest of the sequence can be found in $B$. Since both sequences are sorted this can be done in $O(n)$ step for each index, which implies an overall $O(|I|\cdot n)$ time to compute the valid indices, and return them as $\mathcal{A}(A, B)$. The efficiency of this step relies on the following claim:

*Claim:* $|I|\le 6m/n$, meaning that solutions are not too much overlapping.

*Proof of claim:* We show $|I|\> 6m/n$ leads to a contradiction. Each index $i\in I$ is the starting point of a set of indices $J\_i=\\{i=j\_1,\dots,j\_{n/2}\\}\subseteq B$, that map $A'$ to $B$ up to some offset. Collectively, there are at least $3m$ indices: $$\sum\_{i\in I} |J\_i| = |I|n/2\ge 6m/n \cdot n/2=3m$$ Since $|B|=m$, by pigeonhole principle, there is at least one index $x\in B$ appears in 3 separate solutions: $$\exists x\in B, r,s,p\in I\colon\\; x\in J\_r\cap J\_s\cap J\_p$$

Let $s $ be the median of the three $r\<s\<p$. Since $x\in J\_s$, and $|J\_s|=n/2$, $x$ partitions $J\_s$ to two parts, one of which should have less than $n/4$ indices, which we assume is the lower part: $$J\_s=\\{j\_1=s, j\_2, \dots, j\_\ell=x\\}, \ell\le n/4$$ By construction, $s=j\_1$ is mapped to $a\_1$, up to $a\_\ell$ up to some offset. But we also have $x\in J\_p$, this implies a periodict less than $\ell\le n/4$ in $A'$, which contradicts $\tau(A')\>n/3$. (there's a few details I will add later)

**Overall Complexity** At each step of the recursion, we pay $O(m)$. The periodicity $\tau(A)$ can also be computed in $O(n)$, by computing the longest suffix which is also prefix, of $\mathrm{diff}(A)$, that is the increment array $a\_2-a\_1, \dots, a\_n-a\_{n-1}$. However, the size of the problem reduces by at least $1/2$ in each recursive step. There will be $\log n$ steps in worst case, which implies the time complexity is bounded by $O(m \log n)$. Adding the sorting costs, and since $m\>n$, the overall complexity is bounded by the sorting time $O(m\log m)$

---
Tags: algorithms, integers, subsequences
---


# Question
Title: How does a CPU differentiate between 1-operand instructions and 2-operand instructions?
Suppose that we have 5 different instruction categories (1 OP, 2 OP, 0 OP, branch, and sub-routine instructions), how does a CPU manage to know which category is which whenever it reads an instruction from IR register using the least number of bits for each category? For instance, PDP-11 uses 4 bits (15 → 9) for two-operand instructions and 10 bits (15 → 8) for one-operand ones to denote the opcode of a particular instruction, how does it identify in the first place whether it's a two-operand or a one-operand instruction so that it would read the first 4 or 10 bits accordingly?

# Answer
> 2 votes
Normally the opcode encoding is designed to make it easy to tell. The details of exactly how that works will depend on the particular architecture. For instance, in your example, the first 4 bits might be enough to determine which category the instruction is in. This decoding is performed by the instruction decoder.

As Ran G. explains,

> usually, either all instructions have the same length -- and then different OPCODEs signify different operations, or the instructions have variable length, and then there is some sort of prefix-coding that allows the CPU to determine which instruction it is (and what it length is) by its prefix.

# Answer
> 1 votes
In theory, the opcode is held in the instruction register (IR) until the instruction is complete. There is a cycle counter that is re-initialised each time a new instruction is started.

The IR controls what happens at each cycle. For example, with a 0-operand instruction, the program counter is not incremented until the end of the instruction. With a 2-operand instruction:

* cycle 0: a fetch is done on the PC into IR
* cycle 1: the program counter is incremented
* cycle 2: a fetch is done on the PC into some internal register
* cycle 3: the program counter is incremented again
* cycle 4: another fetch is done on the PC into some internal register
* cycle 5 onwards: the "work" of the instruction is performed
* last cycle: the program counter is incremented so the next instruction is ready to go

The instruction decoder figures this out (whether or not it's easily represented within the bits of the opcode) and switches on the right circuits during the right cycle.

Of course this is just an example. Incrementing the program counter can easily be done at the same time as a fetch. Various 8-bit CPUs worked like this, but modern CPUs do crazy shenanigans so this probably doesn't apply to them except conceptually.

---
Tags: computer-architecture
---


# Question
Title: Are there some good algorithm to select m by three matrices which satisfies certain conditions?
I would like to find an algorithm which select matrices satisfying certain conditions.

We consider integer matrices (entries of the matrices comes from $\\{1,\ldots,n\\}$ for some positive integer $n$) and the numbers in each row are different from each other.

Let me first explain some definitions.

We call a matrix $M$ with m rows and k columns canonical if for all $i \in \[2, m\]$ and $j \in \[2, k\]$, $M\_{i,j} \> M\_{i-1, j-1}$ and for all $i \in \[2,m\]$ and $j \in \[1,k\]$, $a\_{ij} \ge a\_{i-1,j}$. For example, $\left(\begin{array}{ccc}3 & 5 & 9\\2 & 5 & 8\\1 & 4 & 7\\1 & 4 & 6\end{array}\right)$ is canonical.

Let $M$ be a matrix with $k$ columns. Denote by $I\_j$ the set of the elements in the $j$th row. We say that two rows $j\_1, j\_2$ of $M$ i-interlacing if $|J\_{j\_1} \backslash J\_{j\_2}|=|J\_{j\_2} \backslash J\_{j\_1}|=i$ and $J\_{j\_1}\backslash J\_{j\_2} = \\{a\_1,a\_2,\ldots,a\_i\\}$, $J\_{j\_2} \backslash J\_{j\_1} = \\{b\_1,b\_2,\ldots,b\_i\\}$, either $a\_1 \< b\_1\<a\_2\<b\_2 \< \cdots \< b\_{i-1} \<a\_i \< b\_i$ or $b\_1\<a\_1\<b\_2\<a\_2 \< \ldots \< a\_{i-1}\<b\_i\<a\_i$. In particular, if two rows of a matrix are identical, then we say that the two rows are $0$-interlacing.

For example, the first row and the second row of $\left(\begin{array}{ccc}3 & 5 & 9\\2 & 5 & 8\\1 & 4 & 7\\1 & 4 & 6\end{array}\right)$ are $2$-interlacing. The third row and the fourth row of the matrix are $1$-interlacing.

For a matrix $M$ with entries in $\\{1, \ldots, n\\}$, denote $x=x(M)=(x\_1, \ldots, x\_n)$, where $x\_i$ is the number of entries in $M$ which equal to $i$. Denote $q(M)=\sum\_{i=1}^n x\_i^2 + \frac{2-k}{k^2} (\sum\_{i=1}^n x\_i)^2$, where $k$ is the number of columns of $M$. For example, let $M=\left(\begin{array}{ccc}3 & 5 & 9\\2 & 5 & 8\\1 & 4 & 7\\1 & 4 & 6\end{array}\right)$. Then $x(M) = (2,1,1,2,2,1,1,1,1)$ and $q(M)=2$.

I would like to find all $m \times 3$ matrices $M$ with entries in $\\{1, \ldots, 9\\}$ which satisfy the following conditions:

(1) in each row of $M$, any two entries are different from each other; the numbers in each row are increasing from left to right;

(2) any two rows of $M$ are $i$-interlacing for some $i \in \\{0,1,2,3\\}$;

(3) there are two rows of $M$ which are $3$-interlacing;

(4) $M$ is canonical;

(5) $q(M)=2$.

In the cases of $m=2,3,4$, I use many for loops to find out all such matrices. But when $m \ge 5$, it takes infinite time. Is there some fast algorithm to find out all the matrices which satisfy the conditions? Thank you very much.

# Answer
A simple way to deal with this problem—which perhaps can hardly be called a "good algorithm", but nonetheless provides a variety of performance improvements—is to treat it as a constraint satisfaction / combinatorial search problem and apply backtracking. Each matrix entry branches the search tree 9 ways, but many of these subtrees can be trivially eliminated because they immediately violate one of the conditions.

Take the $m = 5$ case that you got stuck on as an example. For condition 1, note that already there are only $\binom{9}{3}^5 = 4,182,119,424$ matrices of size 5x3 with elements in \[1..9\] which have elements strictly increasing from left to right in each row. It's $\binom{9}{3}^5$ because condition 1 is equivalent to, for each row, choosing 3 distinct elements from \[1..9\]. You can of course iterate over such rows with

`for i in 1 to 7, for j in i + 1 to 8, for k in j + 1 to 9`

Moreover, conditions 2 and 4 can be checked as you are generating the rows, rather than only checking these conditions once you have the entire matrix. This should drastically prune the search tree.

Tassle adds (and provides this sample code):

> You can also prune on condition (5) by first computing all possible profiles $x(M)$ which lead to $q(M)=2$, and then trying to find all satisfying matrices with a specific profile. Out of all 490314 ways to choose 15 numbers in {1...9}, only 84 lead to $q(M)=2$. In fact, using this, even python on my quite slow machine can manage m = 5 in a reasonable time.

This sort of brute forcing is also embarrassingly parallel and requires hardly any memory, so consider dividing the space of matrices among however many CPU cores you have.
> 2 votes

# Answer
Here is an iterative algorithm to enumerate such matrices, which proceeds by induction on $m$. I suspect it will be be better than brute force.

Let condition (2') be that every pair of rows is $i$-interlacing for some $i\in \\{0,1,2\\}$.

Note that every matrix that satisfies conditions (1), (2), (3), (4) can be broken up into the concatenation of a matrix $M^1$ that satisfies conditions (1), (2'), (4), a row $r^2$ that when paired with some row of $M^1$ is 3-interleaving, and a matrix $M^3$ that satisfies conditions (1), (2'), (4). So, we will enumerate all $M^1,r^2,M^3$ and look at their combinations. We'll do it in a smart way that ensures that their concatenation satisfies conditions (4), (5).

Write $r\prec r'$ if row $r$ can precede row $r'$ in a canonical matrix, i.e., $r\_0\<r'\_1$ and $r\_1\<r'\_2$. Write $q(x) = \sum\_{i=1}^9 x\_i^2 - 1/9 (\sum\_{i=1}^9 x\_i)^2$.

By induction, assume we have a data structure that lists all $m' \times 3$ matrices that satisfy conditions (1), (2'), (4), for all $m'\<m$. Arrange the data structure as a hashtable of lists, keyed on the value of $(m',x(M),M\_m')$, where $M\_m'$ denotes the last row of the matrix; looking $(m',x,r)$ up in the hashtable returns a list of all $m'\times 3$ matrices $M$ such that $x(M)=x$, $M\_m'=r$, and $M$ satisfies conditions (1), (2'), (4).

Similarly, assume we have a data structure that lists all $m'\times 3$ matrices that satisfy conditions (1), (2'), (4), for all $m'\<m$, keyed on the value of $(m',x(M),M\_1)$, where $M\_1$ denotes the first row of the matrix.

Now, enumerate all $m^1,x^1,r^1,r^2,m^3,x^3,r^3$ such that $m^1,x^1,r^1$ that is a valid key of the first hashtable, $r^1 \prec r^2 \prec r^3$, $m^3,x^3,r^3$ is a valid key of the second hashtable, $m^1+1+m^3=m$, and $q(x^1+x(r^2)+x^3)=2$. Then every way of pairing a matrix $M^1$ from the first hashtable (keyed on $(m^1,x^1,r^1)$), the row $r^2$, and a matrix $M^3$ from the second hashtable (keyed on $(m^3,x^3,r^3)$) will yield a matrix $M$ (obtained by concatenating $M^1,r^2,M^3$) that satisfies conditions (1)-(5).

To do this enumeration, I suggest you first guess $r^1,r^2,r^3$ such that $r^1\prec r^2 \prec r^3$, then guess $m^1,m^3$ such that $m^1+1+m^3=m$, then enumerate all $x^1$ such that $m^1,x^1,r^1$ appears as a key of the hashtable, then enumerate all $x^3$ such that $q(x^1+x(r^3)+x^3)=2$ and check whether $m^3,x^3,r^3$ is a key in the hashtable. However you can also try other orders of enumeration.

Also, enumerate all $m^1,x^1,r^1,m^3,x^3,r^3$ such that $m^1,x^1,r^1$ that is a valid key of the first hashtable, $r\_1 \prec r^3$, $m^3,x^3,r^3$ is a valid key of the second hashtable, and $m^1+m^3=m$; this gives a $m\times 3$ matrix (obtained by a concatenating $M^1$ and $M^3$) that satisfies conditions (1), (2'), (4). This lets you build up the data structure inductively for $m$ from the data structures for $1,\dots,m-1$.

Further optimization may be possible. The condition $q(M)=2$ is a fairly strong one. For instance, for $m=5$, it implies that $x$ is a permutation of $(1,1,1,1,1,1,2,2,2)$. It implies $\sum\_i x\_i^2=m^2+2$, and we also know $\sum\_i x\_i=3m$. This may be helpful for pruning entries of the data structures, when you know $m$ in advance. For instance, if you know that you only care about $m \le 5$, then you can prune all $x(M)$ that contain 3 or any larger number.

Note also that if you care only about *counting* the number of such matrices, this algorithm gives a way of counting them that may be more efficient than enumerating them. There is no need to store the entire list of such matrices; you can simply store the number of such matrices corresponding to each key in the hashtable.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Inviting an optimal subset of persons such that all friends of a person invited are invited
Let's say that you want to invite a person $u$ in party $P$. The person $u$ will join the party if and only if all the friends of $u$ will join the party as well. Otherwise, $u$ will reject your invitation. Hence, we have two sets: $P$ with all the persons, and $F$ with the friend relations. Suppose $(u, v)$ belongs to $F$. This means that $u$ treats $v$ as a friend of $u$, and thus $u$ will reject your invitation if $v$ does not join the party. Note that $(u, v) \in F$ doesn’t mean that $v$ treats $u$ as a friend of $v$. Also, every person $u$ in $P$ has a quality measure, $p\_u$ (this can be positive or negative and is given). Now I need to find a subset of $P$, such that all those in the subset won't reject my invitation and the qualities among the people is maximized.

Here is an example of a feasible and non-feasible subset: $P = \\{a, b, c, d\\}, F = \\{(a, b),(a, c),(b, d),(b, c)\\}, p\_a = 10, p\_b = 1, p\_c = 1, p\_d = −20$.
A subset $\\{a, b, c\\}$ is not feasible because $d$ is not invited and thus $b$ rejects your invitation.
A subset $\\{b, c, d\\}$ is feasible with total quality is $p\_b + p\_c + p\_d = −18$ which is not maximized. The optimal subset $A$ of this example is $\\{c\\}$ with total quality is $p\_c = 1$.

Now I need to design an algorithm that finds this optimal subset in $O(|P|(|P| + |F|)^2)$ time. My thoughts: The elements in $F$ are directed edges, and the elements in $P$ are the nodes. As we are kind of dealing with a maximum flow problem, and as the required running time resembles the running time of the Ford Fulkerson algorithm $O(VE^2)$, I thought, that $(|P| + |F|)$ should be the amount of edges in the graph. Hence, my thought was to split each node $u$ into two nodes, say $u(\mathrm{in})$ and $u(\mathrm{out})$ with the directed arc $u(\mathrm{in})\rightarrow u(\mathrm{out})$ and edge weight the $p\_u$. This way we have $(|P| + |F|)$ edges. However, the max flow algorithm doesn't necessarily saturate the edges it travels. However, in my case, whenever a node is reached (person is invited)/edge is travelled it adds the full flow $p\_u$.

How would you approach this problem? And what are your thoughts on how the algorithm should work?

# Answer
> 2 votes
This is known as the closure problem. I quote the Wikipedia paragraph describing the reduction to the max flow problem here.

> As Picard (1976) \[1\] showed, a maximum-weight closure may be obtained from $G$ by solving a maximum flow problem on a graph $H$ constructed from $G$ by adding to it two additional vertices $s$ and $t$. For each vertex $v$ with positive weight in $G$, the augmented graph $H$ contains an edge from $s$ to $v$ with capacity equal to the weight of $v$, and for each vertex $v$ with negative weight in $G$, the augmented graph $H$ contains an edge from $v$ to $t$ whose capacity is the negation of the weight of $v$. All of the edges in $G$ are given infinite capacity in $H$.
>
> A minimum cut separating $s$ from $t$ in this graph cannot have any edges of $G$ passing in the forward direction across the cut: a cut with such an edge would have infinite capacity and would not be minimum. Therefore, the set of vertices on the same side of the cut as $s$ automatically forms a closure $C$. The capacity of the cut equals the weight of all positive-weight vertices minus the weight of the vertices in $C$, which is minimized when the weight of $C$ is maximized. By the max-flow min-cut theorem, a minimum cut, and the optimal closure derived from it, can be found by solving a maximum flow problem.

---

\[1\] Picard, Jean-Claude (1976), "Maximal closure of a graph and applications to combinatorial problems", *Management Science*, **22** (11): 1268–1272, doi:10.1287/mnsc.22.11.1268, MR 0403596.

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Is there a proof that "undetectable" malware cannot be written?
In Fred Cohen's paper "Computer Viruses - Theory and Experiments", he proves that for the general case, classifying malware is an undecidable problem. I was wondering whether there might be a similarly well-known proof that an undetectable malware can or cannot be written.

# Answer
For every malware, there exists some detector that will detect it. (For instance, given a specific malware $M$, consider the detector that just checks whether its input is $M$ or not, and if it is, outputs "malicious".)

Conversely, Cohen's result shows that for every detector that classifies all benign samples correctly, there exists some malware that it won't detect.

So, there is an unavoidable arms race, if you want to try to detect malware statically.
> 2 votes

---
Tags: proof-techniques
---


# Question
Title: Kolmogorov Complexity, struggle with equation
I am working on understanding Kolmogorov Complexity. I've been struggling with the following exercise for quite some time now and would appreciate any inputs.

Show that there exists a constant $c$, such that for each $n \in \mathbb{N} -\\{0\\},$${K((01)^2}^n) \leq \lceil \log\_2(n+1)\rceil +c = \lceil\log\_2(\log\_2(\frac{|{(01)^2}^n |}{2}))\rceil +c $

Through experimentation, I've come to the conclusion that $|{(01)^2}^n| = 2\cdot2^n \implies \log\_2(|{(01)^2}^n|)=n+1$. Why is it wrong to simply substitute this in the above equation like so:

${K((01)^2}^n) \leq \lceil \log\_2(n+1)\rceil +c = \lceil\log\_2(\log\_2(|{(01)^2}^n |))\rceil +c $

Why is the length of the string divided by 2 in the problem statement?

# Answer
The statement is equivalent to \begin{align}n+1=\log\_2\left(\frac{|(01)^{2^n}|}2\right)&\impliedby |(01)^{2^n}|=2^{n+2}.\end{align} If $(01)^{2^n}$ means $\underbrace{(01)(01)(01)\cdots(01)}\_{2^n\\,\text{times}}$ then the statement is incorrect as $|(01)^{2^n}|=2^{n+1}$ as you have correctly obtained.
> 0 votes

---
Tags: kolmogorov-complexity
---


title: Prove G have a single MSP

text:
# Question
Title: Prove G have a single MSP
We have undirected connective, weighted graph $G = (V,E)$. we also know that for every $e,e'$ in $E$, $w(e)≠w(e')$. Prove that $G$ has a single MSP. Ideas?

# Answer
I missed the part where $\omega(e) \neq \omega(e')$ for $e\neq e'$ so please only consider my answer for the general case, i.e. Given a graph $G =(V,E)$ how to check if $G$ admits a unique MST.

The answer is based on the following claim.

**Claim.** An MST $T$ is unique, if and only if each edge $\\{u, v\\}$ **not** in $T$ has greater weight than all edges on the path in $T$ between $u$ and $v$.

Assuming for now that the claim is true, the task turns into checking for each edge $\\{u, v\\} \in E \setminus E(T)$, if the path in $T$ between $u$ and $v$ contains an edge with weight at least $w$. If this is the case the answer is **No**. If this is not the case for all edges not in the tree, output **Yes**.

Now we need an algorithmic approach to solve the previous problem. Naively, We start by building an arbitrary MST, then we can traverse the path for each such pair $u, v$, where $\\{u, v\\}$ is not in the tree. However, in a dense graph (say the complete graph $K\_n$), this algorithm has running time of $\theta((n+e)\log n + n^3) = O(n^3)$ since we have $\Theta(n^2)$ edges not in the tree and the length of the path is linear. In the following we show how to do each check in $O(\log n)$ time instead achieving a better total running time.

The trick is to use LCA (lowest common ancestor), a data structure defined on rooted trees, that answers the following queries efficiently. Given a pair of vertices $u, v$ in the tree, find a vertex $w$ with the lowest height, such that $w$ is an ancestor of $u$ and an ancestor of $v$. Note that $x$ is an ancestor of $y$ if it lays on the path from the root of the tree to $y$. LCA can be built in running time $O(n \log n)$ answering queries can be done in $O(\log n)$. there are also better "theoretical" results using sparse-tables. However, this ones suffices our needs. We also need to tweak the data structure to answer queries of the form (what is the maximum weight of a vertex on the unique path from $u$ to $v$), note that this is doable by keeping more data about the tree while building the data structure. Also note the choice of the root in this case does not matter and you can choose any vertex to be root.

Now assuming a black-box is given (the LCA data structure) that in $O(\log n)$ time for two given vertices $u$ and $v$ finds the maximum weight of an edge on the path from $u$ to $v$ in the tree. We can do the following, for each edge $\\{u, v\\}$ not in the tree, call the black-box on $u, v$. If the answer is at least the weight of the edge, output **No**. If the answer is less than the weight for all edges not present in the tree, output **Yes**. The running time can be found as follows. We need $O((n+m)\log n)$ to build an MST. We need $O(n \log n)$ to build the LCA data structure (including rooting the tree and computing the depth and the parent of each vertex). We need $O(\log n)$ pro query totaling in $O(m \log n)$ for all queries. Hence a total running time of $O((n+m)\log n)$.

Now we still have to prove the claim presented in the beginning, namely that the tree is unique if and only if for each edge $\\{u, v\\}$ not in the tree, all the edges on the path between $u$ and $v$ in the tree have strictly smaller weight than the edge $\\{u, v\\}$.

**Proof.** Let $\omega: E \rightarrow R$ be the weight function. Assuming there is an edge $\\{u, v\\}$, such that the path in $T$ between $u$ and $v$ contains and edge $\\{x, y\\}$ where $w(\\{u, v\\} \leq w(\\{x, y\\})$. Then by removing $\\{x, y\\}$ from the tree adn adding $\\{u, v\\}$ we get a spanning tree of total weight at least as good as $T$ and hence an MST is not unique. Try to see why the resulting structure is a tree.

For the other direction, we prove the following claim. If there is a simple cycle $C$ where an edge $\\{u, v\\} \in C$ is heavier than all other edges in the cycle, then there is no $MST$ containing $\\{u, v\\}$ as an edge. Assuming there is such a tree, by removing $\\{u, v\\}$ from the tree, we get two connected components. One of the edges in the cycle (say $e'$) must also connect these two components (since cycles are 2-connected) and hence we can add $e'$ to build a strictly lighter MST, contradicting the claim that the given tree was an MST. Hence $\\{u, v\\}$ is not in any MST as claimed. Now complete the original proof, note that the path in the tree from $u$ to $v$ with the edge $\\{u, v\\}$ build a cycle. Hence, we output **Yes** if all edges not in the tree are heavy for some cycle and hence cannot appear in any minimum spanning tree.
> 0 votes

---
Tags: graphs, trees
---


# Question
Title: (0+ 11*0) + (0 +11*0)(1 +01*0)* (1 +01*0) =1*0(1 +01*0)*
I needed help with the following question which belongs to Arden's theorem as I am having a hard time solving it. Please find the question below

Prove: $$(0+ 11^\*0) + (0 +11^\*0)(1 +01^\*0)^\* (1 +01^\*0) = 1^\*0(1 +01^\*0)^\*$$

# Answer
> 1 votes
Call $(0+11^\*0)$ as A and $(1+01^\*0)$ as B. Then what you have on left-hand side is just: $$ R = A + AB^\*B$$ Using Arden's Theorem we know that in this case: $$R = AB^\*$$

Then what we have simplified is: $$(11^\*0+0)(1+01^\*0)^\*$$ Another simplification using Arden's Theorem would give us: $$(11^\*+ \epsilon)0(1+01^\*0)^\*$$ Which is finally equivalent to: $$1^\*0(1+01^\*0)^\*$$

---
Tags: automata
---


title: Regular expression containing lambda

text:
# Question
Title: Regular expression containing lambda
What is the meaning of lambda here: $$(b+c)^\*(a+\lambda)(b+c)^\*(a+\lambda)(b+c)^\*(a+\lambda)(b+c)^\*$$.

I know that lambda is used in the context of NFA?

Let's suppose we break down the expression to:$$(b+c)^\*(a+\lambda)(b+c)^\*$$

and to:$$(b+c)^\*(a+\lambda)(b+c)^\*(a+\lambda)(b+c)^\*$$

How the above would generate an empty string? Somebody please guide me.

Zulfi.

# Answer
> 1 votes
$\lambda$ denotes the empty string, which is written `""` in programming languages. The regular expression you give matches the empty string because you can choose each "$a+\lambda$" to match $\lambda$, and each "$(b+c)^\*$" to match zero copies of $b+c$. So the expression matches, among other things, $\lambda\lambda\lambda\lambda\lambda\lambda\lambda$, which is just the same thing as $\lambda$.

# Answer
> 1 votes
To generate an empty string you take: $(b+c)^\*$ as $\epsilon$, and all the following elements which have a Kleene-star as $\epsilon$ (I will use $\epsilon$ instead of $\lambda$).

Then you have: $$\epsilon(a+\epsilon)\epsilon(a+\epsilon)\epsilon$$ Which is equivalent to: $$(a+\epsilon)(a+\epsilon)$$

Which is essentially picking two options a or $\epsilon$ twice back to back. If you take $\epsilon$ transition each time, which is actually a transition that does not consume an input, it will essentially accept an empty string as input.

---
Tags: finite-automata, regular-expressions
---


# Question
Title: Conditional lower bounds on the running time of the single source shortest path problem
Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I found papers with lower-bounds on some special models of computing such as PRAM or distributed systems but I was wondering if there is a well-known lower-bound based on the 3-sum, SETH or these kinds of conjectures.

# Answer
> 0 votes
I found a lower-bound on the decremental SSSP based on the online matrix vector hypothesis. Decremental SSSP is a dynamic version of SSSP where updates are edge-deletions. On the other hand, it is appearing clear to me, that typical conditional lower-bounds do not make sense for SSSP, since relevant conjectures show that the exponent can not be improved and do not exclude improvement of log factors. On the other hand, improving the exponent in SSSP means a sublinear algorithm which is excluded since the size of the input is a lower-bound on the running time of any problem.

---
Tags: graphs, shortest-path, polynomial-time, lower-bounds, fine-grained-analysis
---


# Question
Title: Multiple choice knapsack dynamic programming
Giving a the following:

A list of a store items $T=\\{t\_1, t\_2,...,t\_n\\}$.

A list of prices of each item $P=\\{p\_1, p\_2,...,p\_n\\}$.

A list of quantities of each item $Q=\\{q\_1, q\_2,...,q\_n\\}$respectively.

And total bill $M$.

Our goal is to find any possible list of items that its total value is equal to $M$ using dynamic programming.

My question does 0/1 weighted Knapsack problem help, where $M$ can be the capacity of the knapsack, and the weight of each item equal to the quantity of the item. If there is any other better approach I would appreciate any references.

# Answer
It turned out we can achieve it in $O(nM)$ time where $n$ is the number of distinct items in the store, and $M$ is the final bill.

We can build a 2-dimensional array with size $C\[T, M\]$ as follows:

$C\[i, j\] = 1$, if there exists a way to add items from $\\{t\_1,t\_2,...,t\_i\\}$ that adds up to $M$.

$C\[i, j\] = 0$, if we cannot find items that adds up to $M$.

Finally, it's useful to use one extra row and column to make the calculation easier in the recursive solution.
> 1 votes

# Answer
You can model this problem as a 0/1 Knapsack problem by splitting the $i$-th item $q\_i$ times. Let the maximum value in $Q$ be $K$, then the typical 0/1 Knapsack solves the problem in $O(MNK)$ time.

For simplicity, suppose $q\_i$ can be written as $1+2+\dots + j$. Then we can split the $i$-th item into new items of price $1\cdot p\_i, 2\cdot p\_i, \dots , j\cdot p\_i$. The powerful thing about this way of splitting is that there is a combination of items to form $1$ to $q\_i$. For example, if $q\_i=10$ and we split into item {$1, 2, 3, 4\\}$, we can form $6$ using $4+2$, $9$ using $4+3+2$ and so on. Therefore, 0/1 Knapsack will still gives a correct answer. If $q\_i$ cannot be represented as sum of consecutive natural numbers, find the largest $j$ such that $q\_i\geq \sum\_{x=1}^j x$ and $r$ be remainder, then split $q\_i$ into $\\{1,2,\dots ,j, r\\}$. Now each item gives $O(\sqrt M)$ more items in the 0/1 Knapsack, hence our solution now becomes $O(MN\sqrt{K})$.

We can further improve this by using the splitting strategy using power of two's $\\{1, 2, 4, 8,\dots\\}$. Then each item know gives only $O(\lg K)$ new items and our overall solution becomes $O(MN\log K)$.
> 0 votes

---
Tags: algorithms, algorithm-analysis, dynamic-programming, knapsack-problems
---


title: NFA/DFA for $ L= \{a^n b^n a | n\ge0\}$

text:
# Question
Title: NFA/DFA for $ L= \{a^n b^n a | n\ge0\}$
I have made two DFA’s for $ L= \\{a^n b^n a | n\ge0\\}$.

First one has several states. The second one is accepting an empty string also.

Somebody please guide me the correct one.

Zulfi.

# Answer
Since FSM's can't count identical sequences, I don't think both of your answers would be correct. You can take a look here, (pumping lemma) to prove why $L= \\{a^nb^n | n \ge 0 \\}$ is not regular, thus you can't write a FSM for it. Also a good example here shows the proof. On the other hand it would be different if you are meaning $a^\*b^\*a$ which can be written as a FSM.
> 1 votes

---
Tags: finite-automata
---


title: Topological Ordering

text:
# Question
Title: Topological Ordering
I have learnt to solve topological ordering using $in-degree$ method where we have to take the vertices having in-degree $0$ at an instance and arrange them in that order.

> For example consider this question asked in Graduate Aptitude Test in Engineering more commonly known as $GATE$ the entrance exam for $IIT$ $M.Tech$ in India. The question goes like this,
>
> Find the number of topological ordering possible for the given graph--\>

Here we can see that in-degree of A is 0 so we take $A$ as the stating vertex, then we have 2 options either $B$ or $C$, and so on.... The number of possible topological ordering in this case is $6$ as explained below

This method works well for these examples where the number of in-degree 0 vertices is less at a time, but how to solve problems where there are many number of 0 in-degree vertices as the one given below

I think combinatorics will come into picture in such cases, but I am unable to apply it properly. Any help will be highly appreciated.

# Answer
> 1 votes
Unfortunately, there is no "fast" way to count them generally as this problem is #P-Complete. This means that it is basically as hard as every counting version of NP-problems, and is likely not solvable in polynomial time.

For small examples such as this one you can come up with some ad-hoc counting technique however. In this case would try listing all permutations of E,F,G and see how many choices I have for the rest if I insert them in some order. Like this:

* EFG: 1+2+4+6 = 13 (1 choice for A, then 2 for B, 4 for C, 6 for D)
* EGF: 1+2+4+5 = 12 (in A,B,C,D order)
* FEG: 1+2+4+5 = 12 (in B,C,A,D order)
* FGE: 1+2+4+6 = 13 (in B,C,D,A order)
* GEF: 1+2+4+5 = 12 (in D,C,A,B order)
* GFE: 1+2+4+5 = 12 (in D,C,B,A order)

So in total 4\*12 + 2\*13 = 74 topological orderings (with some non-negligeable probability that I miscounted somewhere).

---
Tags: topological-ordering, dag
---


title: Uncomputing measurement gate?

text:
# Question
Title: Uncomputing measurement gate?
So one of Aaronson's lecture note (https://www.scottaaronson.com/democritus/lec10.html) pointed out that, if we'd like to simulate a BQP-oracle, technically speaking, the oracle of address-target form. $$ \forall x\in\\{0,1\\}^n, b\in\\{0,1\\}: |x,b\rangle\mapsto|x,f(x)\oplus b\rangle $$

Because such oracle should linearly extend to superposition inputs, we must detangle the output bit with internal (intermediate) qubits. Then one way is to "un-compute" the entire program, namely for BQP circuit $\tilde{f}$ computing $f$. First compute $\tilde{f}$, then apply a CNOT on the answer bit, finally uncompute everything except the CNOT-source bit.

**So my problem is**, in the previous paragraph, he just simulate the measurement gate by a unitary gate. When we perform the un-computing step, we also uncompute that "fake measurement gate". However, it seems not even make sense to un-measure a state. How should I argue that these techniques would work and eventually take us to $BQP^{BQP}=BQP$ result?

# Answer
You seem to be under the impression that we need to measure a qubit in order to copy it. That is not the case because the copy operation is performed by the mapping $|a,b\rangle \mapsto |a,a \oplus b\rangle$ which, when $b = 0$, can be realized by a CNOT gate. There is no measurement involved at all. You only need to know how many ancilla bits (i.e., initialized to zero) you need beforehand so as to have an adequate quantum circuit size.
> 0 votes

# Answer
The fact that you can simulate intermediate measurements is only used to argue that BQP\_WITH\_MEASUREMENTS equals BQP.

Once having this established, you just forget about it. Yes, you can’t undo a measurement. But the good thing is that you never have to.
> 0 votes

---
Tags: complexity-theory, quantum-computing
---


# Question
Title: Is the problem of deciding whether two programs have the same semantics decidable?
If I have program and I want to check whether other programs have the exact same semantics or not, could I always build a machine that could make that decision?

This is a question relevant to information security as metamorphic malware will perform transformations on its own code which will make it look different to static malware detectors while preserving its semantics. If it is possible to write a machine that can detect whether two programs carry the same semantics, then it is impossible to write "undetectable" malware.

# Answer
Concretely, we are always dealing with syntactical transformations, regardless whether there is a semantic theory that renders these transformations intelligible to us, or not. In the end, our ability to automatically demonstrate that two different programs are equivalent is restricted to properties that can be defined syntactically. Even then, there are limits to what we can do, if we allow the language in which these properties are defined to be rich enough, so the answer to your question, in the general case, would have to be negative.

More specifically though, behind every specific metamorphic process that can be automated there is also a specific strategy, so there are also limits to the efficacy of those malware pieces. Because of that, it may be possible, given some knowledge of this strategy, to target its syntactical features in a controlled way, and automatically crack the code behind it, preventing it from attacking.

Malware creators have the initiative though, which gives them an advantage. This advantage can be amplified with technical skill and mathematical sophistication, so it's not advisable to base your security strategy on the ability to detect and deactivate a piece of software that already entered your system.
> 2 votes

---
Tags: undecidability, decision-problem, semantics
---


# Question
Title: Can there be a context free language that is not recognizable by a PEG?
This is related to this question. Essentially, I want to know whether my reasoning is correct.

1. We know that parsing with a context free grammar is same as boolean matrix multiplication (forward: Valient 1975, backward: Lee et al. 2002), and the latter has a lower bound of O(n^2) for arbitrary matrices.

If so, then there should exist a context free language $L$ such that any context free grammar that can represent it would take $O(n^2)$ for matching a string. This is because say there existed a grammar $G\_n$ that allowed matches faster than $O(n^2)$ for any given CFL, then that grammar would allow faster multiplication for the corresponding Boolean matrices. Since Valient et al. and Lee et al. together shows that multiplication of BMs are same as parsing with a CFG, any BM can then be multiplied faster than $O(n^2)$, which is lower than the lower bound by theory.
2. So there should exist a context free language $L$ such that it takes at least O(n^2) time for checking membership in $L$.
3. PEGs are known to require only linear time (Birman and Ullman 1970), (Loff et al. 2019).
4. If there exist a PEG for $L$, it would be a recognizer that checks the membership in linear time, and hence, can solve matrix multiplication in linear time.

Hence, there does not exist a PEG for $L$.

Where am I going wrong?

**Valient 1975**

> context-free recognition, for $n$ character input strings, can be carried out at least as fast as multiplication for $n \times n$ Boolean matrices

**Lee et al. 2002**

> Any CFG parser with time complexity $O(gn^{3-\epsilon})$, where $g$ isthe size of the grammar and $n$ is the length of the input string, can be efficiently converted into an algorithm to multiply $m\times m$ Boolean matrices in time $O(m^{3-\epsilon/3})$.

**Loff et al. 2019**

> In fact, the only method we know to prove that a language has no PEG is by using the time-hierarchy theorem of complexity theory: using diagonalisation one may construct some language $L\_2$ which is decidable,say, in time $n^2$ (by a random-access machine), but not in linear time, and because PEGs can be recognised in linear time using the tabular parsing algorithm of Birman and Ullman \[2\] (or packrat parsing \[32,33\]), there will be no parsing expression grammar for $L\_2$.

# Answer
> 1 votes
I see two flaws in this proof sketch, one related to CFLs vs CFGs, and another related to nested quantifiers and running time as a function of multiple parameters.

Any time you have a high-level proof strategy that seems to lead to surprising results, it is a good idea to check it carefully by expanding each step to obtain a detailed proof. Expand each claim with a precise statement, by applying the definition or the exact theorem in the literature, and verify carefully that they match up. This is particularly important when dealing with lower bounds, as they tend to introduce nested quantifiers that can lead your intuition astray when thinking only at a high level.

# Flaw #1: CFLs vs CFGs

The proof seems to conflate context-free languages (CFLs) with context-free grammars (CFGs). However, there can be multiple CFGs that all generate the same CFL. At best, your proof strategy shows that there exists a CFG $G$ that can't be parsed by a PEG parser. But that's not surprising; we already know that PEG parsers can only parse CFGs that are in the PEG format. We cannot conclude anything about the corresponding CFL $L(G)$; for all we know, there might exist some other grammar $G'$ that *is* a PEG grammar and that yields the same language, i.e., $L(G)=L(G')$. Your proof doesn't rule that out, so it does not prove that the CFL it constructs can't be parsed by a PEG parser.

A concrete example of this is given at https://en.wikipedia.org/wiki/Parsing\_expression\_grammar#Expressive\_power, which shows a simple CFG that cannot be parsed by a PEG parser, but where there exists another CFG for the same language that can be parsed by a PEG parser.

# Flaw #2: Multiple parameters

It's important to expand out the statement of what is meant by these lower bounds. The lower bound on matrix multiplication means that, for each matrix multiplication algorithm, there exists an infinite family $(A\_1,B\_1),(A\_2,B\_2),\cdots$ of matrices such that $A\_n,B\_n$ are $n\times n$ matrices, and multiplying $A\_n \times B\_n$ using this algorithm takes $\Omega(n^2)$ time.

Lee's reduction describes how to construct a matrix multiplication algorithm from any context-free parser. If we now apply Lee's reduction to the matrix multiplication algorithm obtained from a PEG parser, we obtain an infinite family $(G\_1,w\_1),(G\_2,w\_2),\cdots$ of CFGs and inputs such that parsing them takes a long time. You'll need to dive into the details of Lee's reduction to determine the sizes of the $G\_n,w\_n$. Based on a quick look, it looks to me like the size of $G\_n$ is $\Theta(n^2)$ and the size of $w\_n$ is $\Theta(n^{1/3})$, but I'm not sure whether that's correct; you'd need to figure that out.

Next, you'd need to figure out the running time of a PEG parser, as a function of both the size $g$ of the grammar and the size $n$ of the input string. Standard references state the running time of a packrat parser for a PEG grammar as $O(n)$, but they don't describe the dependence on $g$; is it $O(gn)$? $O(g^2n)$? something else? You'd need to figure that out, and then apply it to the family above, to determine what the asymptotic running time of this parser is on the family $L\_n,w\_n$, and thus what the running time of this matrix multiplication algorithm is on the family $A\_n,B\_n$, to determine whether it contradicts the $\Omega(n^2)$ lower bound.

For instance, if the running time of a PEG parser is $O(gn)$, then Lee's reduction yields a matrix multiplication algorithm that takes $O(n^{2.333\ldots})$ time on the family $A\_n,B\_n$, which does not contradict the known lower bound.

Notice how Lee's result does not provide a single context-free grammar or context-free language where parsing is slow; it provides an infinite family of pairs of languages and inputs (which was not considered in your proof strategy). Also note the importance of getting the nested quantifiers right, and of capturing how the running time of a parser depends on both the size of the input and on the size of the grammar (which was not considered in your proof strategy). Hopefully this highlights how a strategy that sounds good can run into difficulties when one tries to apply it in detail; and one must check those details before assuming the strategy will work out.

---
Tags: formal-languages, context-free, parsers
---


# Question
Title: Give a grammar for a language on Σ={a,b,c} that accepts all strings containing exactly one a
I have created the following solution but its left recursive: S--\> a|bSc|cSb|Sbc Also it is not accepting: "ab" or "cba" or "abb" or abc.

Somebody please guide me.

Zulfi.

# Answer
$$S\rightarrow aA, bS,cS$$

$$A\rightarrow bA, cA, \epsilon$$

Note that you need at least two non-terminals for this language, since you need to differentiate two states, namely whether an $a$ has already been added/found or not.
> 2 votes

# Answer
Another way to arrive at a solution here - you might recognize that this language is regular, since, intuitively, you’d only need to remember whether you’d seen zero a’s, one a, or two or more a’s.

You can build a very simple two-state NFA for this regular language. The start state corresponds to having seen no a’s. It isn’t accepting and has a self-loop on b and c and a transition to a second state on a. That state corresponds to having seen one a, has self-loops on b and c, and dies off on seeing another a. *(Note: I lack the LaTeXpertise to actually draw this automaton out. Please edit this answer if you know how to do that!)*

Once you have this NFA, you can convert it into a CFG (more specifically, a right-linear grammar) as follows:

* Create one nonterminal for each state.
* For each transition from a state $Q$ to a state $R$ on character $x$, add the production rule $Q \to xR$.
* For each accepting state $Q$, add a production $Q \to \varepsilon$.

This construction produces a CFG with the same language as the NFA - do you see why? And, in a cool twist, it produces the exact grammar given by @narekBoljikian in their answer! So you can think of that approach as what you’d get if you built an NFA and then turned it into a CFG.

Hope this helps!
> 4 votes

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


# Question
Title: What is the best algorithm known to learn the regular expression from a set of positive examples?
I have a blackbox program that generates a set of strings. What is the best *regular expression* learner that I can use to learn (approximate) what the blackbox program uses as a generator? Note that I only have positive examples. (Checking whether a string is accepted or rejected is possible but rather costly). I see that algorithms like *RPNI* and *L\** requires both positive and negative examples.

I especially want to avoid over-generalization.

Update: I have been making do with using Sequitur to identify repeating patterns in single strings, and then lining up the resulting patterns to identify common repetitions. However, this feels really kludgy and I would like to improve it. Is this the best one can do? are there better ways?

# Answer
I have wondered something similar and failed to find much in the way of satisfying answers in the literature. Here is what I tentatively came up with.

It seems perhaps what we need is some kind of regularization. If $\theta$ is a model (say, a regular expression), let $c(\theta)$ denote some measure of the complexity of the model (say, the size of the regular expression). Also, let $\ell$ be a loss function, so that $\ell(\theta(x),y)$ denotes the loss incurred based on the model's prediction on string $x$, given that the ground-truth label is $y$. Given a training set $(x\_1,y\_1),\dots,(x\_n,y\_n)$, define the total loss as

$$L(\theta) = \sum\_i \ell(\theta(x\_i),y\_i) + \lambda c(\theta),$$

for some hyperparameter $\lambda\>0$.

Then we could frame the learning task as finding a model $\theta$ that minimizes $L(\theta)$.

In your case, $\theta$ is a regexp, $c(\theta)$ is the length of the regexp, $x\_i$ is a string, $\theta(x\_i)$ is true or false according to whether $\theta$ matches $x\_i$ or not, and you have only positive examples so all of your $y\_i$'s are true. You could also consider other models as well, such as a finite-state automaton (whose complexity is given by the number of states) or a neural network (e.g., a CNN or RNN).

The term $\lambda c(\theta)$ is a regularization term that penalizes model complexity, and thereby combats overfitting. Basically, we're applying Occam's razor, that simpler explanations are more likely to be true. If we omitted this term (or equivalently, set $\lambda=0$), we would indeed overfit and obtain poor generalization: e.g., we might learn the regexp $x\_1|x\_2|\cdots|x\_n$. If we over-regularize (and set $\lambda=+\infty$, say), then we underfit and might learn the regexp $.\*$, which also is not good. The hope is that the regularization term will find a happy medium between these two extremes.

So now the problem reduces to, how can we solve the optimization problem above? Unfortunately, I don't know of any good ways to do this, for the case of regexps.

One approach would be to set an upper bound on the size of the regexp, i.e., choose some hyperparameter $s$, and limit consideration to regexps of length $\le s$; then try to find a regexp $\theta$ that minimizes $\sum\_i \ell(\theta(x\_i),y\_i)$ subject to $c(\theta) \le s$. (This formulation is closely connected to the formulation at the top of the question; the theory of Lagrange multipliers tells us that there is a one-to-one correspondence between $\lambda \leftrightarrow s$ that yields equivalent solutions to the optimization problems.) Unfortunately, I don't know of any good algorithms for solving this optimization problem, i.e., for finding such a regexp $\theta$ that minimizes this loss. Perhaps you could use a SAT solver to solve it; I don't know.

Another possibility is to choose a different model. With CNNs or RNNs, it is easier to fix the size of the neural network architecture (thus implicitly fixing an upper bound on the complexity of the model), and then use gradient descent to find weights $\theta$ that minimize $\sum\_i \ell(\theta(x\_i),y\_i)$. Or, you could use a DFA instead of a regexp as your model, and then I think there are methods you could use to solve this optimization problem. In particular, there are known algorithms for using a SAT solver to find whether there exists a DFA with $\le s$ states that matches every string in a given set of strings; and to minimize $\sum\_i \ell(\theta(x\_i),y\_i)$, you culd plausibly repeatedly choose random subsets of $x\_1,\dots,x\_n$, find a DFA that matches every string in the subset, and check its total loss on the entire training set.

It seems hard to imagine that these are the best one can do, but I haven't been able to find better methods in the literature yet; this is the best I've been able to come up with so far.

Related: https://datascience.stackexchange.com/q/16115/8560.
> 1 votes

---
Tags: machine-learning, formal-grammars, regular-expressions
---


# Question
Title: LR(1) parsing, problem with look ahead symbols
I understand the concept of LR(1) parsing and lookahead symbols. I have the solution to the exercise and it does not agree with my solution.

I'm trying to fill the LR(1) parsing table for the grammar below:

```
S->xAz
S->BAx
A->Ay
A->e
B->yB
B->y

```

Ι don't have to extend the grammar since S does not appear in any right hand side of any rule.

```
First(A)=y,e
First(Ax)=x,y
First(B)=y
First(Ay)=y

```

Lookahead symbols in brackets.

So, I0 = Closure(S-\>.xAz($) , S-\>.BAx($) ) =

```
S->.xAz($)
S->.BAx($)
B->.yB(x,y)
B->.y(x,y)

```

When i try GOTO(0,x) i think that i should go to:

```
S->x.Az($)
A->.Ay(z)
A->. (z)

```

To find the lookahead symbol for **A-\>. & A-\>.Ay** i take **First(z)**. But the official book solution says the lookeahead is **(z,y)**. Where does that y comes from?

Thank you in advance!

# Answer
Since $A\to .Ay$ is in the state constructed for $GOTO(0, x)$, $A\to .A(y)$ and $A\to .(y)$ are also in that state. These combine with the other items for the same productions, which have lookahead $z$.
> 0 votes

---
Tags: compilers, parsers
---


# Question
Title: Predicting the outcome of sporting events with multiplicative scoring
In the Olympic format for sport climbing, eight athletes compete in three rounds of climbing. Their final score is the multiplication of their rankings in each round. For example, an athlete who comes 1st in the first round, 5th in the second round, and 7th in the third will have a final score of $1\times5\times7=35$. The athletes with the lowest final score wins.

Assuming that the competition is already partly underway (possibly even mid-round), is there a computer algorithm to quickly compute the probabilities $P\_{ar}$ of each athlete $a$ achieving a final ranking $r$, assuming the performance of the athletes is entirely random from here on? Even with 8 athletes the brute force method seems too computationally intensive.

If this isn't computationally possible in a reasonable time, is there an algorithm to get "close enough" to those probabilities?

# Answer
> 1 votes
# Brute force

If you want something easy to implement, brute force might be fast enough, assuming at least one round has been completed.

There are $8! = 40320$ possible permutations of the athletes, so in any round, there are 40320 possible rankings. Assuming the first round has been completed, there are only $40320^2 \approx 1.6 \times 10^9$ possible rankings for the next two rounds, all of them equally likely. A program should be able to enumerate all of them in a few seconds or minutes and compute the probability distribution of the final rankings for each athlete.

There are faster algorithms, and I will describe them below, but I'm unsure whether the time it takes to understand and implement them will outweigh the amount of CPU time they save.

# Convolution

Let the random variables $X\_1,X\_2,X\_3$ denote the athlete's ranking in the first, second, and third rounds. Then their final score will be $S = X\_1 \times X\_2 \times X\_3$. Our strategy will be to compute the probability distribution for each $X\_i$, then use that to compute the probability distribution for $S$.

Note that if a round has been completed, then the corresponding probability distribution is easy to compute: it assigns probability 1 to the rank the athlete actually obtained, and 0 to all others.

We can compute the probability distribution for a round that hasn't begun by enumerating all $8! = 40320$ possible permutations, observing the athlete's rank in each, and summing up how often each occurs. Or, more simply, we can note that since all permutations are equally likely, the distribution on the athlete's rank in this round is uniform, i.e., all possibilities have probability $1/8$.

We can compute the probability distribution for a round that has been partly completed by enumerating all $8! = 40320$ possible permutations, filtering out all of them that are incompatible with the results observed so far, then observing the athlete's rank in each that remains, and summing up how often each occurs.

So in this way we can obtain the probability distribution for $X\_1$, $X\_2$, and $X\_3$. Now we obtain the probability distribution for $S$ from these distributions. In particular, the probability distribution for $T = X\_1 \times X\_2$ can be obtained as

$$\Pr\[T=t\] = \sum\_{i=1}^8 \Pr\[X\_1 = i\] \Pr\[X\_2 = t-i\].$$

This requires 8 simple steps for each value of $t$, and there are $30$ possible values of $T$, so this can be done in $8 \times 30$ steps. Next, the probability distribution for $S = T \times X\_3$ can be obtained in the same way. There are $80$ possible values of $S$, so this can be done in $8 \times 80$ steps.

The result is the probability distribution for $S$, the athlete's final score. This works with any number of unfinished rounds, even if one round is partly completed. The total running time is at most $40320 + 8 \times 30 + 8 \times 80$ simple steps, which is very fast; an implemention should complete the computation in millliseconds.

Related: Estimate distribution of a composite variable, largest samples of set of random variables, Polynomial Computation of the probability of a number of independent events.

---
Tags: combinatorics, probabilistic-algorithms
---