# Question
Title: A good way to hash two numbers with known properties together
I have two 64-bit numbers `a` and `b` which have a few properties: only 49 out of the 64 bits are used (15 bits are always 0), and the two number's binary representations are disjoint (`a & b == 0`). I am looking for a good way to hash the two numbers together into a deterministic 64-bit integer.

Tabular hashing with randomly generated keys works wonderfully, but I was wondering if there was a faster non-iterative alternative. The target is to minimize the number of collisions between two unique sets of `a` and `b`.

# Answer
> 1 votes
I don't know of a good way to use your special properties. But I do know a very fast provably good hash.

Choose three random 64-bit integers $x, y, z$ (which must be independent of your input $a, b$). Then the following function $h$:

$$h(a, b) = xa + \lfloor ya / 2^{64}\rfloor + yb + \lfloor zb / 2^{64}\rfloor \mod 2^{64}$$

is an $2^{-63}$-ADU (almost delta universal) hash function, per *Short-output universal hash functions and their use in fast and secure data authentication* by Long Hoang Nguyen and Andrew William Roscoe. That is, if $(a, b) \neq (a', b')$ then for *any* $\delta$ (including $\delta = 0$ which implies collision resistance) $$\Pr\[h(a, b) + \delta \equiv h(a', b') \mod 2^{64}\] \leq 2^{-63}.$$

Note that computing $\lfloor pq / 2^{64}\rfloor$ only takes a single instruction on modern CPUs - it is the high bits of the 64x64-bit product. On Intel x86-64 this is always returned by the MUL instruction which returns both parts, on ARM64 it is given by the MULHI instruction.

So in total computing this hash takes 4 multiplication and 3 addition instructions.

# Answer
> 0 votes
Normally comparing objects involves comparing subobjects that can be compared and hashed, you write a good hash function once that combines hash values and use that everywhere and never worry about the problem anymore.

In your case, you might calculate hash(a or b) or hash (a ^ b) or hash (a + b). However, six months from now your assumptions may become false, so if you suddenly have many pairs where a = b or b = a+1 then hash(a ^ b) will be an awfully bad hash value.

---
Tags: hash, binary
---


# Question
Title: Binary subtraction using two's compliment
(22)10 - (65)10= (?)2 Perform this operation using 2's compliment method.Use 8bit representation of numbers

# Answer
As signed 8-bit numbers 22 is 00010110 and 65 is 01000001. To do subtraction you just use two's complement of what you are subtracting by, which is the same as just inverting it and adding 1. So 01000001 (65) would become 1011111**1**. Now let's add 00010110 (22) and 10111111.

```
   ¹¹¹¹¹
  00010110
+ 10111111
----------
  11010101

```

Now if there were to be a carry in this addition we would ignore but lucky enough there was no extra carry. Our answer is given to us in signed two's complement. If we want to find the decimal value of this answer you first reverse the two's complement by inverting all the bits (00101010) and adding one (00101011). This gives us the decimal value of 43, and since the leftmost bit of our original answer is a 1 that means that it is negative. Giving you -43 or 11010101.
> -2 votes

---
Tags: binary
---


# Question
Title: Does the Y combinator contradict the Curry-Howard correspondence?
The Y combinator has the type $(a \rightarrow a) \rightarrow a$. By the Curry-Howard Correspondence, because the type $(a \rightarrow a) \rightarrow a$ is inhabited, it must correspond to a true theorem. However $a \rightarrow a$ is always true, so it appears as if the Y combinator's type corresponds to the theorem $a$, which is not always true. How can this be?

# Answer
> 24 votes
The original Curry-Howard correspondence is an isomorphism between intuitionistic propositional logic and the simply-typed lambda calculus.

There are, of course, other Curry-Howard-like isomorphisms; Phil Wadler famously pointed out that the double-barrelled name "Curry-Howard" predicts other double-barrelled names like "Hindley-Milner" and "Girard-Reynolds". It would be funny if "Martin-Löf" was one of them, but it isn't. But I digress.

The Y combinator does not contradict this, for one key reason: it is not expressible in the simply-typed lambda calculus.

In fact, that was the whole point. Haskell Curry discovered the fixpoint combinator in the untyped lambda calculus, and used it to prove that the untyped lambda calculus is not a sound deduction system.

Interestingly, the type of Y corresponds to a logical paradox which isn't as well-known as it should be, called Curry's paradox. Consider this sentence:

> If this sentence is true, then Santa Claus exists.

Suppose the sentence were true. Then, clearly, Santa Claus would exist. But this is precisely what the sentence says, so the sentence *is* true. Therefore, Santa Claus exists. QED

# Answer
> 10 votes
The Curry-Howard relates type systems to logical deduction systems. Among other things, it maps:

* programs to proofs
* program evaluation to transformations on proofs
* inhabited types to true propositions
* type systems to logical deduction systems

If the type system admits a Y combinator, then that means that the corresponding logical deduction system is *inconsistent* — every theorem is true. On the program side, the Y combinator allows any function of type $a \to b$ to be defined, for any $a$ and $b$: $Y (\lambda x. x) \to Y (\lambda x.M)$. The corresponding deduction rule allows any proposition to be derived from any other proposition. Thus the logical system is inconsistent.

The Curry-Howard correspondence is just that: a correspondence. In itself, it doesn't say that certain theorems are true. It says that typability/provability carries from one side to the other.

The Curry-Howard correspondence is useful as a proof tool with many type systems: simply typed lambda calculus, system F, calculus of constructions, etc. All these type systems have the property that the corresponding logic is consistent (if the usual mathematics are consistent). They also have the property of not allowing arbitrary recursion. The Curry-Howard correspondence shows that these two properties are related.

The Curry-Howard still applies to non-terminating typed calculi and inconsistent deduction systems. It's just not particularly useful there.

# Answer
> 0 votes
Look at the construction for $Y = λf·(λx·f (x x))(λx·f (x x))$. Carefully apply the type rules to it $$\begin{align} f:& C → A,\\ x:& B → C,\\ x:& B,\\ x x:& C,\\ f (x x):& A,\\ λx·f (x x):& B → A,\\ λx·f (x x) (λx·f (x x)):& A,\\ λf·(λx·f (x x) (λx·f (x x))):& A → A, \end{align}$$ where, in order to make the applications $x x$ and $(λx·f (x x))(λx·f (x x))$ consistently work, we need the following equations $$B = B → C,\quad A = B.$$

As with all other cases of type-matching, this puts restrictions on the set of types involved in the typing. This typing is assumed to hold for all $(A,B,C)$ that satisfy these equations. In logic, if you have a statement $B$ that satisfies the equivalence $B ⇔ B → C$ with respect to another statement $C$, then by Modus Ponens: $C$ follows from $B$. Since $(⋯) → (⋯)$ is monotonically increasing with respect to the second argument, then that means $B$ follows from $B → B$, which - in logic - is the tautology value $⊤$, therefore $B = ⊤$. Since $C$ follows from $B = ⊤$, then we also have $C = ⊤$.

Under Curry-Howard, $⊤$ would correspond to a type that solves $⊤ = ⊤ → ⊤$ and contains all other types. Its key equivalences, motivated by logic, would be $A → ⊤ ⇔ ⊤$ and $⊤ → A ⇔ A$. For the construction given above, the types are all restricted to $A = B = C = B → C = ⊤$.

There is no finite construction that yields a generic type $Y: (A → A) → A$, except with $A = ⊤$. On the other hand, a *rational infinite* construction $f(f(f(⋯)))$ yields the type $f(f(f(⋯))): A$, for any $f: A → A$, so that you could write $$Y = λf·f(f(f(⋯))): (A → A) → A.$$ The corresponding proof is infinite (though rational). It has an end - consisting of an infinite number of Modus Ponens all identical in form, followed by a discharge of hypothesis - but no beginning.

If you apply this to the combinator $I = λx·x: A → A$, you get what one might call the "Curry Paradox Term" $(λf·f(f(f(⋯)))) I$, whose corresponding proof is similarly infinite, but is capped off with that final Modus Ponens with the tautology $A → A$ to get the conclusion $A$, for arbitrary $A$.

If you abstract $λf·f(f(f(⋯)))$ using the rule $λx·x y = U (λx·y)$, where $U = λxλy·y(xy)$, then you can proceed to write $Y = U(U(U(⋯)))$. The combinator $U$ has, as its most general type, $$U: ((A → B) → A) → (A → B) → B.$$ So, it applies to this construction of $Y$, provided you impose the constraint $A = A → B$, which lands everything right back at the previous construction of $Y$. The corresponding proof is an infinitely-layered natural deduction proof (though rational infinite), with an infinite number of hypotheses discharged.

So, I'm not sure you can get $Y$, with the typing $Y: (A → A) → A$ for arbitrary $A$, even with rational infinite combinator expressions.

On the other hand, $(λf·f(f(f(⋯)))) U: (A → B) → B$, with the constraint $A = B$ imposed by the construction, works just fine as an equivalent form for $Y$.

A brief search uncovers two articles that touch on the issue Infinite λ-Calculus And Types and All the λ-Terms are Meaningful for the Infinitary Relational Model.

---
Tags: logic, recursion, type-theory, combinatory-logic, curry-howard
---


# Question
Title: How to motivate freshman students towards automatic groups?
I'm a new professor and working at a computer science college. I'm going to be responsible for giving a one-hour lecture to motivate my students to study automatic groups.

I'm very experienced as a teacher and I think that I'm a really good speaker, but no idea about how to make these topics friendly and attractive for students who are just coming from high school.

I wonder how to find references and if you have any success experience on that to share with me.

Our ultimate goal is to make students interested in our research lab in which I'm a new member as well.

They're not going to take a course. But it is suppose to be something to make students to motivated enough to come to our lab, ask questions about the topic (in general and naive way), and maybe in the future become postgraduate students.

# Answer
> 1 votes
There is no way this is at an appropriate level for students just graduating from high school. Save it for much more advanced students. It requires considerable mathematical sophistication -- and probably understanding of what automata are -- even to understand what an automatic group is and why one should care about.

Instead, know your audience. Describe something that it is at an appropriate level for them, where they can reasonably learn something new and inspiring, given the background they have.

You might check out CMU's course on Great Ideas in Theoretical Computer Science for some ideas: that is almost surely still too advanced (see its prereqs), but it gets closer.

---
Tags: automata, cellular-automata, group-theory
---


title: NFAs that accept a regular language

text:
# Question
Title: NFAs that accept a regular language
Just a quick question about regular languages and which NFAs accept them: If I were to draw an NFA that accepts a particular regular language, does that mean the NFA can only accept strings in that language or can the NFA accept every string in that language and some extra ones?

For example, for the regular language a+ ∪ (ab)+ (given as a regular expression) the corresponding NFA that I drew looks like this:

This NFA would accept any string in the given regular expression (a, aa, aaa, ab, abababab, etc) but it would also accept some extra strings that aren't in the expression (aba, aaaab, aaabab, etc). Would the NFA be correct because it includes every string in the regular expression? Or would it be incorrect because it includes some strings that aren't in the expression? Any and all advice is much appreciated. Thank you!

# Answer
The language of an NFA $A$, denoted $L(A)$, is the set of words $w$ such that there is an accepting run of $A$ on $w$. Hence, when we claim that an NFA $A$ recognizes a language $L$, we mean that $L(A) = L$, and by that we mean equality of sets, that is, we have two-sided containment:

(1) $L(A)\subseteq L$: every word $w$ that $A$ has an accepting run on is such that $w\in L$.

(2) $L\subseteq L(A)$: $A$ has an accepting run on every word in $L$.

What you did is a suggestion of an NFA that satisfies only condition (2) w.r.t your language. It does not make sense, and it is also not hard to obtain such an NFA: an NFA that accepts all inputs has a language that includes all other languages. So yes, your solution is incorrect as it does not recognize the language of the regular expression -- condition (1) does not hold, your NFA accepts more words than it should.
> 1 votes

# Answer
The "corresponding NFA", as you call it, for $a^+ ∪ (ab)^+$ is not your $$→ q\_0,\quad q\_0 \overset{a}→ q\_0,\quad q\_0 \overset{a}→ q\_1,\quad q\_1 \overset{b}{→} q\_2,\quad q\_1 →,\quad q\_2 → q\_0,\quad q\_2 →,$$ but this $$→ q\_0,\quad q\_0 \overset{a}→ q\_1,\quad q\_0 \overset{a}→ q\_2,\quad q\_1 \overset{b}→ q\_3,\quad q\_2 \overset{a}→ q\_2,\quad q\_2 →,\quad q\_3 \overset{a}→ q\_1,\quad q\_3 →.$$

Your NFA corresponds to the regular expression $(a ∪ ab)^+$, and it could just as well be written as this $$ → q\_0,\quad q\_0 \overset{a}→ q\_1,\quad q\_0 \overset{a}→ q\_2,\quad q\_1 \overset{b}→ q\_2,\quad q\_2 → q\_0,\quad q\_2 →. $$
> 0 votes

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


# Question
Title: Generalization of a Markov random field and a Bayesian network?
I am seeking a graphical model that is a generalization of both a Markov random field (MRF) and a Bayesian network (BN).

From the Markov random field wiki page:

> A Markov network or MRF is similar to a Bayesian network in its representation of dependencies; the differences being that Bayesian networks are directed and acyclic, whereas Markov networks are undirected and may be cyclic. Thus, a Markov network can represent certain dependencies that a Bayesian network cannot (such as cyclic dependencies); on the other hand, it can't represent certain dependencies that a Bayesian network can (such as induced dependencies).

From the above description, particularly the last sentence, it appears that neither MRFs nor BNs are more general than the other.

**Questions:**

* Is there a graphical model that encompasses both MRFs and BNs? *(I think I’ve answered this, see the update below)*
* What is the form of its factorization?

I believe such a graphical model will need to be directed so as to be able to model the (undirected) dependencies in a MRF (by included a directed edge in each direction). Mixed graphs also may be relevant.

---

**Update:**

I believe I've answered the first part of my question. It seems the natural generalization is that of a chain graph (also see: N. Wermuth and S. L. Lauritzen. "On substantive research hypotheses, conditional independence graphs and graphical chain models." *J. R. Statist. Soc. B*, 52:21–50, 1990.). The second question, on their factorization, still stands. That is, what is the definition of a Markov blanket for a chain graph (the Markov blanket for a Markov random field is the neighbor set whereas for a Bayesian network, it is the parent nodes, children nodes, and parents of the children nodes).

# Answer
Check factor graphs which may solve both questions https://en.m.wikipedia.org/wiki/Factor\_graph
> 0 votes

---
Tags: graphical-models, bayesian-network
---


# Question
Title: Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs
Let $G=(V,E)$ be an unweighted directed acyclic graph with a set $V$ of vertices and a set $E$ of edges. The all-pairs shortest path problem can be solved efficiently using the Floyd-Warshall algorithm. The new objective is to find a subset of maximum cardinality $S \subseteq V$ such that for every pair of vertices $v$ and $u$ in $S$, the length of the shortest path from $v$ to $u$, if it exists, is greater than or equal to a positive natural number $k$.

This problem could be stated as a bottleneck capacity maximization problem in a complete directed weighted graph. You are given a complete weighted directed network and the objective is to find an induced subgraph with $m$ vertices where the minimum arc capacity is greater than or equal to $k$.

The reduction gives the arc from $v$ to $u$ a weight equal to the shortest path computed by Floyd-Warshall from $v$ to $u$ (if there is no path, a weight of $\infty$ is given). Is there an efficient/polynomial time dynamic programming approach to solve the problem?

# Answer
*\[EDIT: updated answer to apply to directed acyclic graphs.\]*

**Lemma 1.** *This problem is equivalent, under approximation-preserving poly-time reductions, to Maximum Independent Set in undirected graphs.*

Independent Set is NP-complete and NP-hard to approximate within a factor of $n^{1-\epsilon}$ (for any $\epsilon\>0$), so so is this problem:

**Corollary 1.** *The problem is NP-complete and NP-hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon\>0.$*

---

*Proof of Lemma 1.* First we describe the reduction *from* Max Independent Set. Given an instance $G=(V, E)$ of Max Independent Set, the reduction outputs the directed graph $G'$ obtained from $G$ by directing each edge so that $G'$ is acyclic (e.g. arbitrarily order the vertices, then orient $(u, v)$ from $u$ to $v$ if $u$ comes before $v$ in the ordering), and take the "distance budget" $k$ to be $2$.

To see that the reduction is correct, note that a given vertex subset $S$ is an independent set in $G$ iff no two vertices in $S$ share an edge, which holds iff no two vertices in $S$ are at distance 1 in $G'$.

Next we describe the reduction *to* Max Independent Set. Given an instance $(G=(V, E), k)$ of OP's problem, construct the undirected graph $G'=(V, E')$ where $E'= \\{\\{u, w\\} \subseteq V : d(u, w) \< k\\}$. Then a vertex subset $S$ is an independent set in $G'$ iff it contains no two vertices of distance less than $k$ in $G$. $~~~\Box$

---

For the variant in undirected graphs, there is a bicriteria approximation algorithm:

**Lemma 2.** *For the variant with undirected graphs, in poly time one can compute a set $S\_k$ achieving minimum distance $k$, with size at least the maximum size of any set $S^\*\_{2k}$ achieving distance at least $2k$.*

*Proof of Lemma 2.* The algorithm is greedy: choose any vertex to add to $S\_k$, delete all vertices within distance strictly less than $k$ from the vertex, and repeat until the graph is empty.

Each "ball" of deleted vertices contains at most one vertex from $S^\*\_{2k}$, so $|S\_k| \ge |S^\*\_{2k}|$. $~~~~\Box$

For OP's problem, with *directed acyclic* graphs, the greedy algorithm in Lemma 2 doesn't guarantee such a good bicriteria approximation.
> 4 votes

---
Tags: graphs, np-complete, dynamic-programming, dag
---


# Question
Title: Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree
I have a tree, $T$, with $n$ nodes. My goal is to assign a non-zero weight to each node such that the following condition is met:

> Upon removing any arbitrary node, the total weight of nodes in each resulting connected component should be equal.

Consider the following tree as an example:

```
1 -- 2 -- -3 -- 4
     |
     1

```

In this tree, if we remove any node, the total weight of the nodes in each of the resulting connected components is equal. For instance, if we remove the node with weight $-3$, we end up with two connected components, each with a total weight of $4$.

I am seeking an algorithm that can find these weights in polynomial time.

My initial approach was to assign arbitrary values to the nodes. Then, for each node, I would check if the condition is satisfied when that node is removed. This check can be performed in $O(n)$ time using graph traversal algorithms like BFS or DFS. However, I am unsure how to adjust the tree because correcting the condition for one node seems to disrupt the condition for almost all other nodes.

Any suggestions or insights would be greatly appreciated.

# Answer
Using the idea of @Mahyar, I think there is another way to find a solution to the problem.

Given a tree $T= (V, E)$, find a bipartition of $T = (X\sqcup Y, E)$ (using a simple graph traversal). Consider the following weighting function:

$$w : \begin{array}\[t\]{rcl} V & \to & \mathbb{Z}\\ v & \mapsto & \left\\{\begin{array}{ll} \deg(v) & \text{if }v\in X\\\-\deg(v)&\text{if }v\in Y\end{array}\right. \end{array}$$

Then it satisfies the property.

Indeed, when deleting a vertex of $X$, the resulting connected components are of weight $-1$. When deleting a vertex of $Y$, the resulting connected components are of weight $1$. The total weight of the tree is $0$.

**Proof:**

* $w(T) = 0$. Indeed, $w(T) = \sum\limits\_{x\in X}\deg(x) - \sum\limits\_{y\in Y}\deg(y) = 0$, because the graph is bipartite.
* Deleting a node of $X$ (resp. $Y$) creates connected components of weight $-1$ (resp. $1$). The idea of the proof is basically the same as in @Mahyar's answer: we consider $r\in V$ an arbitrary root. For $v\in V$, we note $h(v)$ the maximal distance from $v$ to a leaf of the tree $T$ rooted in $r$. We prove by induction on $h(v)$ that the result is true.
    + if $h(v) = 0$, $v$ is a leaf, hence of weight $1$ or $-1$. Deleting $v$ creates one connected component of weight $-w(v)$, because $w(T) = 0$;
    + suppose the result true for all $v$ such that $h(v) \leqslant k$, for some $k\geqslant 0$. Let $x\in X\setminus \\{r\\}$ (the case $Y$ is similar) such that $h(x) = k + 1$. In the tree $T$ rooted in $r$, all children of $x$, $v\_1, v\_2, …, v\_{d-1}$, with $d = \deg(x)$, verify $h(v\_i) \leqslant k$. Let $T\_i$ be the subtree rooted in $v\_i$.

    Since each $v\_i\in Y$, using induction hypothesis, for all $i$, $w(T\setminus T\_i) = 1$. That means that $w(T\_i) = w(T) - w(T\setminus T\_i) = -1$. Now, the connected components created by the deletion of $x$ are the $T\_i$'s, and the rest of the tree: $T\setminus (\\{x\\}\cup T\_1 \cup… \cup T\_{d-1})$. The weight of this connected component is: $$w(T) - w(x) - w(T\_1) - … - w(T\_{d-1}) = -1$$
    + the case of the root is similar, just without this last connected component.
> 9 votes

# Answer
We can weight vertices such that the entire tree has a fixed sum of weights; for example, zero.

Let us design a recursive procedure that assigns weights to the vertices of a tree $T$ with root $r$ such that the weight of $T$ is zero, and after removing $r$ from $T$, weight of every remaining component is $S$. We call this procedure $\texttt{root}(r, S)$.

$\texttt{root}(r, S)$ assigns to $r$ a weight of $- S \times \deg(r)$, as weight of $T$ should be zero. We already know that for each child $v$ of $r$, weight of the subtree with root $v$ is $S$. We want to make sure that, when $v$ is removed, every remaining component has the same weight. One such component consists of $r$ and subtrees of children of $r$ except $v$. This component has weight $S' = - S \times \deg(r) + S \times (\deg(r) - 1) = -S$. So, every other component after removing $v$ should also have weight $S'$; if $v$ is not already weighted, a call to $\texttt{root}(v, S')$ will weight vertices in subtree of $v$.

We pick an arbitrary root $r$ and a non-zero $S$, and call $\texttt{root}(r, S)$ in a top-down style. This algorithm runs in time $O(n)$.
> 8 votes

# Answer
All the solutions for $w$ the weight function on the (vertices of the) tree $T=(V, E)$ can be obtained combining Mahyar's and Nathaniel´s answers in this way:

1. Pick any arbitrary numbers $S$ and $S'$.
2. For a bipartition $T = (X\sqcup Y, E)$, assign $S$ to all vertices in $X$, and $S'$ to all vertices in $Y$. This will be the sum of the weights of vertices in each connected component resulting from removing the given vertex.
3. Assign weights $w(x) = S + S' - deg(x) \cdot S$ to vertices $x \in X$, and $w(y) = S + S' - deg(y) \cdot S'$ to vertices $y \in Y$.

This modifies procedure $\texttt{root}(r, S)$ to assign weight $w(r)$. You can see how $\texttt{root}(r, S)$ causes alternating $S$ and $S'$ as it recurses. And the sum of all weights in the tree $T$ is $w(T) = S + S'$ (not necessarily 0).

In Mahyar's answer $S' = -S$, while in Nathaniel´s answer $S = 1$ and $S' = -1$.

For proofs, it is useful to show that, for any tree T holding OP's propery,

* $w(T) = w(v) + deg(v) \cdot S(v)$ for all $v \in V$,
* $w(T) = S(u) + S(v)$ for all adjacent vertices $u,v \in V$.
> 1 votes

---
Tags: graphs, trees, graph-traversal
---


# Question
Title: What is the Computational Complexity of this Difference of Squares problem?
Consider a quadratic function over positive integers. For example say a simple function of the form: $f(n)=3n+4n^2$

Now given any positive integer $C$ find two integers such that: $f(i)-f(j) = C$

What is the complexity of such problems? I tried searching for a bit but didn't find an answer..

# Answer
Here is one possible approach. With $f(n) = an + bn^2$ we have, $C = (i-j)(a + b(i+j))$. Given any $C$, find a factor of it. Let $C = \alpha\beta$ with $\alpha \le \beta$. Now we have to solve for $i - j = \alpha$ and $a + b(i+j) = \beta$. Given any $C$ we have to only enumerate upto $\sqrt{C}$ to get all integral factorizations. Once we have a factorization we can solve the equations to test where integral solution exists. We iterate from 1 upto $\sqrt{C}$ an in each iteration we do some constant number of division operations which again would be of order at most $\sqrt{C}$. Thus overall complexity is $O(C)$.
> 0 votes

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


# Question
Title: in NFA is every state itself contained in set generated by transition function when considering epsilon transition from that state?
in $\epsilon$-NFA (NFAs involving $\epsilon$ transitions) when we have $\epsilon$ transitions, I understand it as where can we go if we don't read any symbol from the input tape, then I think every state $q$ from which we are considering transition must belong to $\delta(q,\epsilon)$ because if we don't read anything, we can of course stay in the state where we are at now, I am asking whether $\epsilon$ transition from state to itself is assumed? for example, if we have some state $q\_i$ which has $\epsilon$ transition to state $q\_j$ then is $\delta(q\_i, \epsilon)$=$\\{q\_j, q\_i\\}$ or just $\\{q\_j\\}$, I think it's just matter of convention and wouldn't make significant difference.

# Answer
Why not make this a bit formal and let's do the following exercise:
For a given NFA, $M = (Q, \Sigma, \delta, q\_0, F)$, let us construct another NFA $M' = (Q, \Sigma, \delta', q\_0, F)$ where $\delta'$ is the same as $\delta$ with additional $\epsilon$-transition self-loop on every state. We would like to prove these two machines are equivalent, that is, $L(M) = L(M')$.

Proof for $L(M) \subseteq L(M')$:
For every string $w \in L(M) \subseteq \Sigma^\*$, there is a transition path in $M$ from $q\_0$ to some final state $q \in F$. By construction the same path also exist in $M'$ thus $w \in L(M')$.

Proof for $L(M') \subseteq L(M)$:
For every string $w \in L(M') \subseteq \Sigma^\*$, there is a transition path in $M'$ from $q\_0$ to some final state $q \in F$. Now, due to our additional $\epsilon$-transition self-loops, this path may contain runs (consecutive repetitions) of the same states. Now if we collapse each run into just a single state, it will give us a trace on $M$ from $q\_0$ to the same final state $q \in F$. Thus, $w \in L(M)$.
> 3 votes

# Answer
The answer depends on what you mean by $\delta(q,\epsilon)$.

First possibility is that $\delta$ specifies the transitions (the arrows in the state diagram). In that case we have $\delta(q\_i,\epsilon) =\\{q\_j\\}$ to indicate the single edge.

The other possibility is that $\delta$ specifies computations, sometimes called the extended transition function: $q\in \delta(p,w)$ iff there is a computation on the input word $w$ starting in state $p$ and ending in state $q$. In that case $\delta(q\_i,\epsilon) =\\{q\_i,q\_j\\}$ is what we need.
> 4 votes

---
Tags: finite-automata, nondeterminism
---


title: Partial polygon matching

text:
# Question
Title: Partial polygon matching
I am looking for fast procedures for polygon matching, i.e. checking polygon similarity under different transforms

* translation only,
* translation + rotation,
* translation + scaling,
* translation + rotation + scaling (= similarity).

The matching can be partial, meaning that there can be a good match on a significant fraction of the outline (say \> 70%), and complete mismatch elsewhere.

The number of vertices is reasonable (say N\<50).

In a variant of the problem, you need to compare two polygons. In another variant, you compare one polygon to a series of polygons, with preprocessing of the single polygon allowed. In a third variant, preprocessing is allowed on all polygons.

Are you aware of solutions to this problem ?

# Answer
There is quite a bit of work on this important problem. Some of the most insightful work is by Helmut Alt and collaborators. He wrote a survey in 2009:

> Helmut Alt. "The computational geometry of comparing shapes." *Efficient Algorithms*. Springer Berlin Heidelberg, 2009. 235-248. (Springer link.)

---

<sup> Image from Helmut Alt & Leonidas J. Guibas. "Discrete geometric shapes: Matching, interpolation, and approximation." *Handbook of computational geometry* 1 (1999): 121-153.). </sup>

---
> 6 votes

# Answer
One reasonable approach is to use RANSAC to find a homography that causes many points to be aligned (or approximately aligned). You'd apply this procedure to align the set of vertices of the first polygon with the set of vertices of the second polygon.

The homography captures translation, rotation, and scaling, so it allows correcting for all of them. RANSAC allows for a subset of the points to match (the points that are approximately aligned are called inliers; the others are outliers), and tries to find a homography that (firstly) maximizes the number of points that are approximately aligned and (secondly) among all such homographies, causes the aligned points to be as closely aligned as possible.
> 2 votes

# Answer
An interesting application of partial polygon matching is symmetry detection in building footprints
> 0 votes

---
Tags: algorithms, computational-geometry, pattern-recognition, polygons
---


title: Graph labyrinth solving sequence

text:
# Question
Title: Graph labyrinth solving sequence
> Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from vertex in question to an other one), one exit is labeled 'a', the other exit is labeled 'b'.

> We have limitless 'memory' but, we don't recognize when we arrive at the same vertex again, so at each step we can only pick if we go exit a or exit b, or we recognize when we have entered the exit vertex. Show that there is an algorithm to get out of any maze!

> Write the algorithm. If n is its input, then its output is a sequence 'a', 'b' that exits any maze with at most n vertices.

I got this assignment (math student) in a course to do with algorithms. I don't believe the actual code outputting the 'a', 'b' sequence is particularly difficult once the structure of the function is found mathematically.

I've had multiple ideas, it is clear, that were we to find a sequence that would guarantee a visit to all vertices, we would be done, as one of them must be the "end" vertex. This would be easy, if the edges weren't directed, because we would try all possible 1-long sequences by doing a 1-long sequence and tracing our steps back and doing the next, if we didnt reach the end. Then do the same with 2-long sequences, and so on. I think the longest sequnces we would have to try would be $ 2^n $ in length and we would get an incredibly long sequence but it could be shown to work. But this solution relies heavily on the fact that we could always trace our way back to the vertex at which we start and thereby doing something like a BFS. That doesn't work here, as we can't go back on edges we came from (at least not necessarily).

I also stumbled upon *De Bruijn sequences*. A *De Bruijn sequence* for a given alphabet (in this case, 'a' and 'b') and a given length 'n' is a cyclic sequence in which every possible subsequence of length 'n' appears exactly once. I don't see how this would work, but maybe if we collate this sequence 'n+1' times, we would visit all vertices, because we would be guaranteed to have tried all 'walks' from all vertices, but I don't see this rigorously at all.

I found similar posts, but their answers are not conclusive at all, and the fact that we do do not recognize a vertex we have already been at significantly complicates this version of the problem. That is why I come to you, I need some serious guidance, as I have no clue about this at all

Edit:

from collections import deque

def generate_graphs(n):

    Generate all strongly connected directed graphs with n vertices and out-degree 2.

    graphs = []
    # Generate all possible graphs with the given constraints
    return graphs

def find_exit_path(graph, start, target):
    """
    Find the path from the start vertex to the target vertex using BFS.
    """
    queue = deque([(start, [])])
    visited = set()

    while queue:
        vertex, path = queue.popleft()
        if vertex == target:
            return path
        visited.add(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append((neighbor, path + ['a'] if neighbor == graph[vertex][0] else path + ['b']))

    return []  # No path found

def solve_labyrinth(graphs):
    """
    Find the solution path that works for any labyrinth in the given set of graphs.
    """
    solution_path = []
    current_vertex = None

def solve_labyrinth(graphs):
    """
    Find the solution path that works for any labyrinth in the given set of graphs.
    """
    solution_path = []
    current_vertex = None

    for graph, start, target in graphs:
        if not solution_path:
            current_vertex = start
        else:
            # Walk along the existing solution path from the start vertex
            current_vertex = start
            for step in solution_path:
                neighbor_a, neighbor_b = graph[current_vertex]
                current_vertex = neighbor_a if step == 'a' else neighbor_b

        exit_path = find_exit_path(graph, current_vertex, target)
        solution_path.extend(exit_path)
        current_vertex = graph[current_vertex][0] if exit_path[-1] == 'a' else graph[current_vertex][1]

    return solution_path

# Generate all graphs with n vertices and out-degree 2
n = 5  # Example number of vertices
graphs = generate_graphs(n)

# Find the solution path
solution_path = solve_labyrinth(graphs)
print("Solution path:", "".join(solution_path))
```

# Answer
Let $G\_1, \dots, G\_m$ be an enumeration of all strongly connected directed graphs on at most $n$ vertices in which every vertex has out-degree 2 (the corresponding edges labelled $a,b$).

The algorithm proceeds in $n^2m$ rounds. In round $(i-1) n^2 + (j-1) n + k$ (where $1 \leq i \leq m$ and $1 \leq j,k \leq n$), the algorithm guesses that the graph in question is $G\_i$, that at the very beginning we were at vertex $\min(j,|V(G\_i)|)$, and that the end vertex is $\min(k,|V(G\_i)|)$. If this is the case, then given what happened in the preceding rounds, the algorithm knows that we are at some vertex $v$. Since $G\_i$ is strongly connected, there is a path from $v$ to $k$. The algorithm follows this path, and checks whether it has reached the (real) end vertex. If so, it terminates, and otherwise, it proceeds to the following round.

---

The sequence output by such an algorithm is known as a *universal traversal sequence* or a *universal exploration sequence*, and there are much more efficient constructions in the literature. Of particular note is the undirected $d$-regular case, in which there is a universal traversal sequence of polynomial length.
> 2 votes

---
Tags: algorithms, graphs, formal-languages, search-algorithms, graph-traversal
---


# Question
Title: Proving tight bound Θ for worst-case running time of an algorithm without proving lower bound Ω
See this answer first: Proving worst-case running time is in $\Omega(n^2)$

Understanding the linked answer for insertion sort leads to the following statement. Prove that the statement is either incorrect or correct.

Statement: If you find $(y)$ for worst case running time of an algorithm using some possible worst input. This finding is sufficient to now state $Θ(y)$ without demonstrating $Ω(y)$ for worst case running time of that algorithm.

Caution:

Using insertion sort as an example - Keep in mind that when you are finding the $y$ in $(y)$ using some sample input that you know is worst, you cannot come up with $y = 2^n$ because you would not get $y = 2^n$ for any input that you can think of sorting. The worst input that you can think of is an array sorted in opposite order which will get you $y = n^2$. Therefore, leads to conclusion that $O(n^2)$ for worst case running time of insertion sort.

This conclusion is also enough to conclude $Θ(n^2)$ for worst case running time of insertion sort if statement given above is true. Statement is general and stated for all algorithms, not just for insertion sort as demonstrated in this example.

# Answer
I would suggest checking exact definitions of asymptotic notations, to say informally: $\Omega(f(n))$ is set of functions that are lower bounded by $f(n)$, while $O(f(n))$ are set of functions upper bounded by $f(n)$, so when you have some example that runs in $O(n^2)$ it doesn't mean that it can't run in constant time, for example in $O(1)$, by $O$ you specify upper bound, not lower bound. I would suggest this Wikipedia article: https://en.wikipedia.org/wiki/Big\_O\_notation#The\_Knuth\_definition.

P.S also I don't understand how the link you provided is connected to the question you asked, the question you linked is about why 1 example input for each n is enough for proving worst-case running time of insertion sort.
> 0 votes

---
Tags: algorithms, asymptotics, proof-techniques
---


# Question
Title: Isn't counting sort a better sorting algorithm for linked lists rather than merge sort?
I have to analyze how every sorting algorithm's complexity would change if it had to sort a linked list and which of all of them is the most efficient. I find everywhere that merge sort is the most efficient one for linked lists, but I don't understand why counting sort isn't better. I think it would still be O(n). Am I missing something? Same with bucket sort and radix sort, would the complexity change with a linked list?

# Answer
> 14 votes
You are comparing apples and orange-colored bicycles here.

*Merge Sort* is a *stable* *Comparison Sort*. As such, it only requires that there must be a *Total Preorder* over the elements.

Comparison Sorts have a lower bound asymptotic worst-case step complexity of $\mathcal{O}(n\log{}n)$. Therefore, Merge Sort's asymptotic worst-case step complexity is as good as it gets for Comparison Sorts. There cannot be a Comparison Sort with a better asymptotic worst-case step complexity.

*Counting Sort* is a *Non-Comparison Sort*. Non-Comparison Sorts *can* be faster than Comparison Sorts, but they can only do this by exploiting some *additional* information or structure about the inputs that makes them less general than Comparison Sorts.

For example, Counting Sort can *only* sort *small non-negative integers*, but has an asymptotic worst-case step complexity of $\mathcal{O}(n + |r|)$, where $|r|$ is the size of the range of possible inputs. Merge Sort can sort elements drawn from an arbitrarily large range, such as integers, which is something Counting Sort cannot do.

*Radix Sort* can sort anything that can be ordered *lexicographically*. Its asymptotic worst-case step complexity is $\mathcal{O}(wn)$, where $w$ is the length of the sort key. Merge Sort can sort elements based on an arbitrarily large sort key, which is something Radix Sort cannot do.

*Bucket Sort* works by distributing the elements into buckets, then sorting those buckets using a Comparison Sort. The worst-case is when all elements end up in the same bucket, in which case Bucket Sort simply degrades to whatever sorting algorithm is used to sort the buckets. Since the sorting algorithm for the buckets is a Comparison Sort, its asymptotic worst-case step complexity cannot be better than $\mathcal{O}(n\log{}n)$, and thus neither can Bucket Sort's.

Typically, Bucket Sort is used with an *Insertion Sort* for sorting the buckets, which has an asymptotic worst-case step complexity of $\mathcal{O}(n^2)$.

In order to actually reap the benefits of Bucket Sort, *a priori* knowledge about the distribution of inputs is required.

In other words, unless you have some additional *a priori* knowledge about the elements of the linked list, you can only use Comparison Sorts, and Counting Sort, Radix Sort, Bucket Sort, and friends are not even an option.

# Answer
> 7 votes
Counting sort is a very particular kind of sort which you can only apply in particular circumstances.

* If the elements you're sorting are floating-point numbers instead of integers, counting sort doesn't work.
* If the elements you're sorting take their values in a huge range with more possible elements than actual elements in the list, then counting sort is probably not worth it (and would have a high space complexity in addition to time complexity).
* If the elements you're sorting are not numbers, but complex objects with one number field that you're sorting on, then counting sort doesn't make any sense (although bucket sort would be a possible generalisation for that case).

If you find yourself in a particular situation where counting sort can apply, sorting n integers taking value in range \[1, k\], then:

* Merge sort has time complexity O(n log(n)) and space complexity O(n);
* Counting sort has time complexity O(n + k) and space complexity O(n + k).

**If** you find yourself in this particular situation and **if** k and n are such that k ∈ O(n), **then** counting sort is more efficient than merge sort.

# Answer
> 0 votes
There is nothing wrong. Counting sort is definitely better in the sense of having a lower time complexity if the integers have a fixed range. And they very likely had a fixed range when you generated the data, even if you didn't realize it.

But remember what a lower time complexity means: It will eventually be faster than the algorithm with higher time complexity with a large enough n. Your n is just not large enough. It might be discouraging if you pick an n much smaller than the range, as counting sort may appear significantly worse. But just try again using an n so that you will wait for minutes for it to finish. There isn't anything that deep here.

# Answer
> 0 votes
A recursive bucket sort can have time complexity O(n\*log(k)/log(n)). The space needed is O(n).

# Answer
> 0 votes
I've found that counting sort is usually faster than mergesort or quicksort as long as `k` (the absolute difference between the largest and smallest element) is within an order of magnitude of `n` (the length of the list). Personally I would only use counting sort if `k` was within `2*n`, and only if I really needed the boost in runtime performance. I've never been in a situation where I needed this.

Keep in mind that this would still take up quite a bit of extra space.

It *is* possible (though not advisable) to make counting sort work with non-integer types such as floating-point numbers, or even strings - but only if you're willing to write your own custom logic to map integers to non-integer values (ordinary hashing wouldn't work because it's not reversible). Again, I can't see this as being useful in most real-world situations, and the space complexity would probably be horrible.

However, there are some hypothetical situations where counting sort/pigeonhole sort would be a no-brainer. The most obvious would be if you knew ahead of time that the integers to be sorted were distinct and that, when sorted, they would compose a sequence of the form `min, min+1, min+2...max`. In such a case, you would only need to compute the `min` and `max` and generate a list of integers within that range in a loop.

In fact, if you knew that `min` was 0 in this case, you wouldn't even need to compute `max`, or even look at the source list's elements at all; you could just output all integers from 0 to `n-1` with a simple loop.

---
Tags: sorting
---


# Question
Title: Prove that a language does not many one reduce to its complement
I am trying to prove that an undecidable language $L$ is not many one reducible to its complement.

The problem goes as follows: Formally prove that $L \not\leq\_m \overline{L}$ for any undecidable $L$. ($\overline L$ is also denoted $L^c$.)

How would I go about proving this? I am unsure how to prove mapping reducibility, especially regarding any language.

I know I will need to use reduction here somehow. And I know that I will need to use the properties of L (like the fact that it is undecidable). Would I have to create a machine and ′ such that halts iff ′?

# Answer
> 0 votes
I believe that to answer this question you need to use concept of Turing degrees.

We know that if L is undecidable, Then there is some least k which L is recursively enumerabe using a Turing machine with an oracle for 0^{k} but L is not decidable with this oracle.

We use this fact to show that L' s complement is not many one reducible to L:

Let's say《To get a contradiction》 that L' s complement is many one reducible to L. So there is some computable function f which:

For all x

x belongs to L' s complement if and only if f(x) belongs to L.

Now, Let's use the fact that for any 2 languages A and B, if A is many one reducible to B and B is recursively enumerabe using an oracle for C, Then A is recursively enumerabe using an oracle for C.

So, because L' s complement is many one reducible to L and L is recursively enumerabe using an oracle for 0^{k}, we can deduct that L's complement is recursively enumerabe using an oracle for 0^{k}.

But this way we can conclude that L is decidable using an oracle for 0^{k}. Which contradicts our assumption which states "L is not decidable using an oracle for 0^{k}."

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


# Question
Title: Is there a combinator that introduces brackets to a combinatory logic expression using just B?
Suppose I have the expression $abcdef$ and I want a combinator $X$ that does this:

$Xabcdef=a(bcd)(ef)$.

Is it possible to express $X$ using just the $B$ combinator, defined by

$Babc=a(bc)$?

Is this possible in general? That is, if I have a string of letters without brackets, is there always a combinator in terms of $B$ only that parenthesizes my expression in the way I want, leaving the order of the letters unchanged?

# Answer
> 1 votes
$X=B(BBB)(BB)$ answers the first question. Indeed,

$B(BBB)(BB)abcdef=BBB(BBa)bcdef=B(B(BBa))bcdef=B(BBa)(bc)def=BBa(bcd)ef=B(a(bcd))ef=a(bcd)(ef).$

For the second question, yes, this may be done in general. Here's a rough proof: if we have $Xabc\ldots xyz = (\textrm{expr})(yz)$, this becomes $Xabc\ldots xyz=B(\textrm{expr})yz$, so $Xabc\ldots x = B(\textrm{expr})$. If $(yz)$ is nested inside other brackets, like, for example, $Xabc\ldots xyz=(\textrm{expr})(x(yz))$, we get $Xabc\ldots xyz=B(\textrm{expr})x(yz)=B(B(\textrm{expr})x)yz$, and again we may then consider just $Xabc\ldots x=B(B(\textrm{expr})x)$. We may then do a further step: $Xabc\ldots x=B(B(\textrm{expr})wx)=BB(B(\textrm{expr}))x$, which means that $Xabc\ldots w=BB(B(\textrm{expr}))$. Continuing doing this, we end up with just $X$ on the left hand side and an expression involving (possibly bracketed) $B$'s on the right hand side.

# Answer
> 0 votes
Set $x\_1 = x$ and $x\_{n+1} = B x\_n$, where $x ∈ \\{B, C, K, W\\}$; and note that - up to η-equivalence, $x\_n = x\_{n+1} I$, since $B f I = f = B I f$ under η-equivalence. We can then also write $x\_0 = x I$. The combinators $\\{B, C, K, W\\}$ are given by the rules $$I x = x,\quad B x y z = x (y z),\quad C x y z = x z y,\quad W x y = x y y,\quad K x y = x.$$

Up to η-equivalence $B\_0 = B I = I$.

Instead of explaining the general case, it should suffice to see an example: $$\begin{align} x v (z y) (y x) &= I x v (z y) (y x)\\ &= B\_4 I x v (z y) y x\\ &= B\_3 (B\_4 I) x v z y y x\\ &= C\_3 X\_b x v y z y x\\ &= C\_4 (C\_3 X\_b) x v y y z x\\ &= C\_5 (C\_4 (C\_3 X\_b)) x v y y x z\\ &= C\_4 (C\_5 (C\_4 (C\_3 X\_b))) x v y x y z\\ &= C\_3 (C\_4 (C\_5 (C\_4 (C\_3 X\_b)))) x v x y y z\\ &= C\_1 (C\_3 (C\_4 (C\_5 (C\_4 (C\_3 X\_b))))) v x x y y z\\ &= W\_4 X\_c v x x y z\\ &= W\_2 (W\_4 X\_c) v x y z\\ &= K\_2 X\_w v w x y z\\ &= X\_k v w x y z, \end{align}$$ where $$ X\_b = B\_3 (B\_4 I) = B\_3 B\_3,\quad X\_c = C\_1 (C\_3 (C\_4 (C\_5 (C\_4 (C\_3 X\_b))))),\\ X\_w = W\_2 (W\_4 X\_c),\quad X\_k = K\_2 X\_w. $$ The $X\_b$ sub-term applies to your question. The remainder applies to the more general question that you didn't ask.

You could also write it as $$K\_2 (W\_2 (C\_1 (W\_4 (C\_3 (B\_3 (C\_4 (B\_4 C\_2))))))) v w x y z = x v (z y) (y x).$$

**Edit:** Before I forget, your example: $$\begin{align} a(bcd)(ef) &= Ia(bcd)(ef)\\ &= B\_3Ia(bcd)ef\\ &= B\_2(B\_3I)a(bc)def\\ &= B\_2(B\_2(B\_3I))abcdef\\ &= B\_2(B\_2B\_2)abcdef \end{align}$$

---
Tags: functional-programming, combinatory-logic
---


title: Why do benchmark results vary at all?

text:
# Question
Title: Why do benchmark results vary at all?
Benchmarking typically consists of getting the current CPU time, executing test code a large number of times, and then subtracting the new CPU time from the previous one. However when you benchmark code multiple times, the results tend to vary either slightly to significantly each time. You will very likely not get the exact same number each time even for the same code and same number of iterations.

However, CPUs have a fixed clock rate (do they not?), and instructions typically take the same amount of time to execute for the same conditions (`add`, `mov`, `or`, etc. typically take a fixed integer number of clock cycles or do they not?), and the same instructions are being executed the same number of times under seemingly the same conditions.

So in theory every benchmark **should** return the exact same number, yet clearly they do not. What goes on behind the scenes in a CPU that could cause variations in benchmark results for the exact same benchmark?

# Answer
Your assumption that the clock rate is constant is wrong. My computer at home can at any time switch each core to one of 15 different clock speeds.

Your assumption that the same operation always takes the same time is wrong. The total processor state is extremely complicated and not exactly reproducible. The benchmark runs on a computer that does other things that can and will affect the benchmark times.
> 5 votes

# Answer
Simply put, benchmark would return the **same, exact number if the cpu is in the same state every time the code is benchmarked.**

---

**What does cpu state mean?** It means the **context of the cpu at that instance of time, which would include registers, cache, pipeline and much more**. To add on, the **OS would demand context switches, paging operations** and more to keep running. It would be practically impossible to reproduce the same scenario for each different run. These constitute, what I would like to call, the logical state of cpu.The benchmarks won't give the same number but would follow a distribution.

**The cpu being a semiconductor device, is bound ultimately by the laws of physics and hence it's actual physical state and environment matters**. Cpu's are engineered to prolong it's life and one such feature is dynamic frequency scaling.

Just as food for thought, benchmarking vacuum tube based systems/punch card based systems(from back in the day) would have a higher chance of giving the same benchmark result(why?)
> 1 votes

---
Tags: cpu, performance, benchmarking
---


# Question
Title: $L_1\in P$ , $L_2\in NP$, is it possible that $L_1\cup L_2 \in P$
Prove\Disprove\Prove that equivalent to $NP=P$ or $NP\ne P$

given $L\_1 \in P$ , $L\_2 \in NP$ is $L\_1 \cup L\_2 \in P$?

Obviously $L\_1 \cup L\_2 \in NP$ because NP is closed under union and $P \subseteq NP$ so $L\_1 \in NP$ as well.

I tried to assume in contradiction that $L\_1 \cup L\_2 \in P$ and build a $TM$ for $L\_2$.

Let $M\_\cup$ be the $TM$ for $L\_1 \cup L\_2 \in P$ and let $M\_1$ be the $TM$ for $L\_1 \in P$

I can accept any $x\in L\_2 /(L\_1 \cap L\_2)$ by checking if $x \in L(M\_\cup)$ and checking if $x \notin L(M\_1)$

I got stuck trying to determine deterministically whether $x \in L\_1 \cap L\_2$

# Answer
Unless I am mistaken, the answer to your original question "Given $L\_1 \in P$, $L\_2 \in NP$ is $L\_1 \cup L\_2 \in P?$" is "not generally, unless $P=NP$" since we can take $L\_1 = \emptyset$. Similarly, if we take $L\_1 = \Sigma^\*$ (the language of all words over the alphabet in question) then $L\_1 \cap L\_2 = L\_2$ so $L\_1 \cap L\_2 \in P$ cannot hold in general unless $P=NP$.
> 2 votes

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


# Question
Title: confusion with the proof of halting problem
From what I have seen on YouTube such as https://youtu.be/Kzx88YBF7dY?si=5j9tzjMFGCn3aCXW,

We have: **Halt**: program x input ---\> yes halt/ no halt

and **opposite** : halt if Halt returns no halt, and, looping if Halt returns yes halt

so the input of opposite should also be : program x input right? not just a single program.

Hence it does not make sense to feed **opposite** program with just an **opposite** program, what comes after is irrelavnet? not a successful proof?

# Answer
> 0 votes
The video pretty clearly shows that `OPPOSITE` takes one input `program` and calls `HALT(program, program)`

So `OPPOSITE` takes its input, copies it, and feeds both the input and the copy to `HALT`.

Does that clear your confusion?

---
Tags: halting-problem
---


# Question
Title: Is there a linear-time algorithm for randomly sampling weighted combinations?
For concreteness, here's the specific problem description: suppose we have a set $S$ of $n$ items $a\_1, a\_2, \ldots, a\_n$ with weights $w\_1, w\_2, \ldots, w\_n$ respectively. The goal is to select a subset of size $k$ such that the probability of selecting the subset $a\_{i\_1}, a\_{i\_2}, \ldots, a\_{i\_k}$ is exactly $\dfrac{w\_{i\_1}\cdot w\_{i\_2}\cdots\cdot w\_{i\_k}}{\sum\_{S\_k\subseteq S, |S\_k|=k}(\prod\_{i\in S\_k}w\_i)}$. If $k=1$ then this is the usual selection from a weighted distribution and can easily be done in time $O(n)$ (or even $O(\log n)$ per sample with $O(n)$ preprocessing). If the $w\_i$ are all equal then this is the usual uniform selection of a combination of $k$ things from a set of size $n$, and there are several well-established algorithms to do this in time $O(n)$. But I don't know of any algorithm for the generalized problem that runs faster than the naive version in $\Theta\_n({n\choose k})=\Theta\_n(n^k)$ time, and even a dip into TAOCP didn't turn up anything. Are there any known fast algorithms for this problem?

# Answer
> 12 votes
There is a very simple $O(n \log k)$ algorithm described in *Weighted random sampling with a reservoir* by Pavlos S. Efraimidis and Paul G. Spirakis, which can be summarized as:

> Associate value $r\_i^{1/w\_i}$ to $a\_i$, where $r\_i$ is an independent random uniform value on $\[0, 1\]$. Sort the elements by their associated values, the $k$ largest values indicate the desired subset.

With a priority queue of size $k$ you don't need to do a full sort and can get away with $O(n \log k)$.

---

To get some mathematical intuition of why this works, you can look at the $k = 2$ case. Let the cumulative density function $F\_w(x) = \Pr\[r^{1/w} \leq x\] = \Pr\[r \leq x^w\] = x^w$, which gives the probability density function $f\_w(x) = wx^{w-1}$. Then we have

$$\Pr\[r\_1^{1/w\_1} \leq r\_2^{1/w\_2}\] = \int\_{0}^1 F\_{w\_1}(x)f\_{w\_2}(x)dx = \int\_{0}^1w\_2x^{w\_1+w\_2-1}dx = \frac{w\_2}{w\_1 + w\_2}.$$

For the full method I recommend reading the paper.

---
Tags: time-complexity, combinatorics, randomness
---


# Question
Title: Should I concatenate three lists together or use two separate while loops in Python? Which option offers a better runtime complexity?
In the context of adding sparse polynomials, you have two alternative approaches to combine the terms from two separate polynomials. One option is to use the line of code `result += self.terms[i:] + other.terms[j:]`, which efficiently concatenates the remaining terms from both polynomials. The other option is to employ two separate while loops like the ones shown below:

```
while i < len(self.terms):
    coeff, exp = self.terms[i]
    result.add_term(coeff, exp)
    i += 1

while j < len(other.terms):
    coeff, exp = other.terms[j]
    result.add_term(coeff, exp)
    j += 1

```

The first approach concatenates the remaining terms into a single list and appends them to the result, while the second approach iterates through the remaining terms in both polynomials and adds them to the result one by one.

The question at hand is: which of these options provides a better runtime complexity when adding sparse polynomials? Your input and insights on this matter would be greatly appreciated."

# Answer
> 1 votes
First, measure. If you can’t measure the difference then it doesn’t matter.

Second, you don’t know the time complexity of add\_term. You need to find its implementation and analyse its behaviour. Reasonable implementations could lead to a runtime that is quadratic in the number of terms. Different reasonable implementations would lead to linear or n log n behaviour.

# Answer
> 0 votes
about slicing I would suggest to check following link: implementation of list slicing and also following answer on big O of list slicing. also try to find list\_concat method here source code of cpython. I assume that list-slicing and list\_concat that are internal staff of python would be fast because of C, so instead of doing it yourself, use slicing and "+" operator. however I would suggest to separately run both program on relatively large lists ($10^6$ size at least and check the time it took).

---
Tags: algorithms, data-structures, python
---


# Question
Title: In the proof that $DSPACE(S)\subseteq DTIME(2^{O(S)})$, why precisely do we require that $S=\Omega(\log n)$
I have read and understood various proofs, but have not been able to understand precisely why we require $S=\Omega(\log n)$.

# Answer
We believe that $DSPACE(X) \subseteq DTIME(X)$ is false. As a consequence, $X$ must be chosen so that $X \neq 2^{O(X)}$. Additionally, considering $DSPACE(X) \subseteq DTIME(Y)$ we want $ Y = 2^{O(X)}$ to allow the Turing machine requiring $X$ space to halt on all of its inputs: this is because the number of configurations is $O(2^{O(X)})$ and any accepting computation must halt within $O(2^{O(X)})$ steps, i.e. this is $2^{O(X)}$ if $X = \Omega(\lg n)$. Moreover, the function $X$ must be space constructible as well, and $\lg n$ is space constructible. This is also consistent with the definition of the complexity classes $L$ and $P$. The former is the class of the languages (or problems) requiring at most $O(\lg n)$ space, the latter the class of languages requiring at most polynomial time. The relationship $L \subset P$ holds because a Turing machine requiring at most logarithmic space can use at most linear time, so polynomial time.
> 0 votes

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


# Question
Title: Are there infinite state machines, and how do their computational power relate to turing machines?
From the internet:

```
A finite-state machine is formally defined as a 5-tuple (Q, I, Z, ∂, W) such that:

Q = finite set of states
I = finite set of input symbols
Z = finite set of output symbols
∂ = mapping of I x Q into Q called the state transition function, i.e. I x Q → Q
W = mapping W of I x Q onto Z, called the output function
A = set of accept states where F is a subset of Q

```

Are there infinite (countable/uncountable) state machines where I change every "finite" to "infinite" in the previous definition? If I do so, how are they different to turing machines in terms of computational power? Why was the turing machine not defined in this way, considering the fact that the TM used an infinite sized tape?

# Answer
Turing machines aren't defined this way simply because automata with an infinite number of states aren't effective. The definition of effective procedures tries to capture our intuitive understanding of algorithms, and Turing machines are meant to formalize effective calculability (and there's reason to believe that they do).

But to be effective, a method must be finite. An infinite "algorithm" isn't very useful, since you can't really give a full description of it. The major problem of formal language/automata theory is to find *finite* descriptions of infinite languages.

---

These automata also don't really capture the same class of languages as TMs do. Indeed, if you generalise FAs to infinite states you can recognise any language $L = \\{a\_1, a\_2, ...\\}$ by combining the finite automata of the summands $\\{a\_i\\}$ in

$$L = \bigcup\_{i \in \mathbb{N}} \\{a\_i\\}.$$

This makes sense, since if we allow infinite "algorithms" then there's an algorithm to compute any function by simply listing all values of the function.
> 6 votes

---
Tags: computability, automata
---


# Question
Title: Mathematical Foundation for Dimensioned Quantities?
Is there support in the foundation of mathematics for dimensioned quantities?

Those immersed in real-world software problems, continually confront the absence of dimensioned quantities in programming languages. Occasionally this results in a billion dollar disaster, such as the Mars Climate Orbiter. This absence appears in the foundation of mathematics!

The absence of support afflicts even Wolfram's Mathematica, which has a bug-riddled subsystem to deal with what it calls "Quantity" entities. I say "bug-riddled" as someone who has attempted to use this subsystem rigorously and found numerous bugs not attributable to my admittedly less-than-masterful grasp of its Byzantine structure, evidenced by the following response to the latest bug with dimensioned quantities I ran into:

For an example of an approach to this vital topic, consider that First Order Logic (FOL) plays a central role in relational intension. Relation tables resulting from the application of intensions are relational extensions. The columns of relation tables may be treated as properties being observed during measurement with each row a specific observation.

Since FOL is at the very foundation of mathematics, it would seem strange if there was no work in CS to found their treatment of dimensioned numbers in terms of FOL.

Note, I'm not suggesting that this is the only rigorous approach to the problem of programming language design in which dimensioned numbers are a natural result of the foundational principles.

I'm just wondering what I'm missing, since it *seems* CS is all-but silent on such an important topic?

# Answer
Of course there is mathematical support for dimensioned quantities. It's kind of trivial from mathematical point of view.

Off the top of my head, here's a suggestion. Given some basic units of measurement, represented by a set of symbols $U$, say $\lbrace \mathtt{g}, \mathtt{m}, \mathtt{s}\rbrace$ consider the free abelian group $F(U)$. Its elements are all possible products of (integral) powers of the basic units, such as $\mathtt{m}/\mathtt{s}^2$ and $\mathtt{s}^2 \mathtt{m}^3$. These correspond to compound units generated from the basic ones. A dimensioned quantity is then just a pair $(q, u)$ where $q \in \mathbb{R}$ and $u \in F(U)$. If this does not satisfy you, then you need to explain what it is that you want the theory to accomplish.

With regards to ensuring correctness of software, there are of course approaches to programmign that ensure correct treatment of dimensioned quantities. For example, there is a Haskell units package, and I am sure many others can be found with a bit of Googling. The problem is not that these things don't exist, but that they don't get used in software development.
> 1 votes

# Answer
Dimensions play an important role in all natural sciences (physics, chemistry, engineering, etc.), but not in mathematics. The reason is that the property of "having a dimension" is not really a property of a quantity. It is a property of a *physical law* that involves that quantity. The property is formulated as a continuous symmetry with respect to multiplication the quantity by a positive real number.

An example is the simple law of "conservation of mass". It says that if we split a chunk of something with mass $m$ into two chunks with masses $m\_1$ and $m\_2$ then $m = m\_1 + m\_2$. This law is invariant with respect to multiplying all masses by a positive real number. So, we may measure masses in kilograms or pounds or whatever, but the law will remain the same.

This would not be true if the law of mass conservation had the form $m = \sqrt {m\_1 + m\_2}$ or something else that is not invariant under multiplication of all masses by a constant. But there aren't any laws like that.

In fact, almost all physical laws that involve masses will always have the same property: we may change the units of mass but the laws will remain the same.

Why is that? Nobody knows. But that's the laws of physics that we have discovered.

So, the fact that "mass has dimension" is really just a property of the physical laws that involve masses.

The same holds for other quantities (distance, time, charge, and so on). All physical laws involving those quantities are invariant under multiplication of all distances by an arbitrary number, all times by another arbitrary number, all charges by another number, etc. There are no laws where a distance $L$ would enter via a formula $L + \sqrt L$, or $L + \frac{1}{L}$, or anything else that is not scaled linearly under multiplication.

This is why physical quantities are always formulated using dimensions. Dimensions enforce the fundamental symmetry under rescaling.

But mathematics is not concerned with just the physical laws. Mathematics studies any equations or laws whatsoever. In mathematics, the equation $m = m\_1 + m\_2$ is just as interesting as $m = \sqrt{m\_1 + m\_2}$.

Also, mathematicians are always looking for simpler and at the same time more abstract formulations of laws. It is simpler to drop dimensions from consideration. If a law is invariant under rescaling, that's interesting and important. There is an entire theory around that (Lie groups and their orbits and representations). But it doesn't help to keep weird names around our equations: kilogram, inch, etc. Those names don't really help to study the mathematical properties of equations.

That's why mathematics-oriented software doesn't support dimensions. Or if it does, its support for dimensions was added as an afterthought.
> 0 votes

---
Tags: mathematical-foundations, philosophy
---


# Question
Title: relation between $\forall$ and implication in intuitionistic logic using curry-howard and propositions as types
I am currently trying to wrap my head around intuitionistic logic and its interpretation using the curry-howard isomorphism and propositions as types.

I came about this explained relation between $\forall$ and $\rightarrow$:

> A function type $s \rightarrow t$ is actually a function type $\forall x:s.t$ where the variable x does not occur in t. \[..\] Moreover, if we have a type $\forall x:s.t$ where x does not occur in t, we can omit x and just write $s\rightarrow t$ without losing information.

I do not get how this can work as I understand a $\rightarrow$ basically as "give me a proof of s and I give you a proof of t" - a mapping function. However, a function that maps needs a parameter, in this case the x which is a proof of s : $f(x):s\rightarrow t$. How can I still have a mapping if I am 'not allowed' to use x and thus any information contained in it anymore?

If I use an example: e.g. proof that every $\mathbb{N}$ is $\mathbb{R}$ I need to use the information contained in the proof that a given number is in $\mathbb{N}$ to show that $\mathbb{N}$ is more restrictive than $\mathbb{R}$ and thus any $\mathbb{N}$ has to be $\mathbb{R}$. However, I do not have 'access' to those information as x (the proof that the number is in $\mathbb{N}$) does not occur in my proof that the number is also $\mathbb{R}$.

# Answer
> 1 votes
The difference between $s\to t$ and $\forall x : s. t$ is that in the second case, the *return **type*** of the function depends on the *input*.

For example, in most languages, you can make a function that takes a natural number and returns an array of that size and it will have type $\operatorname{nat} \to \operatorname{nat} \operatorname{array}$. But if you want to specify it further and say that it doesn't return any array but really an array of that size, then you would want to type it as $\forall n :\operatorname{nat}. \\{a : \operatorname{nat} \operatorname{array} | \operatorname{size}(a)=n\\}$. In both cases the output of the function (the array of size $n$) depends on the input $n$ of the function but in the second case, the return type $\\{a : \operatorname{nat} \operatorname{array} | \operatorname{size}(a)=n\\}$ also depends on the input while in the first case it does not.

Another example would be a function that takes a proof that $m=2$ and returns a proof that $m\le 2$. All it has to do it use the reflexivity of $\le$, which I'll call $\operatorname{le\\\_refl}$. You can define $(\lambda (m:\Bbb N).\lambda (p:m=2).\operatorname{le\\\_refl}(p)):\forall (m:\Bbb N).(m=2\to m\le 2)$. Note that you could also write the type as $\forall (m:\Bbb N).(\forall(p:m=2). m\le 2)$ but since the return type $m\le 2$ of the inner function doesn't depend on the proof $p$ (even though its output does), you can simplify it and use the arrow notation.

Yet another way to think of is that $\forall(x:A).B(x)$ (where I write $B(x)$ instead of $B$ to emphasize that it can depend on $x$) is often written $\Pi(x:A).B(x)$ in type theory. And it makes sense because in a way, this expressions gives you a way to define a type $B$ given $x:A$. And the you look at the set of all functions that take an input $x:A$ and return an element of $B(x)$. Now think of the cartesian $\prod\_{x\in A}B(x)$ product of the elements of the set $\\{B(x)|x\in A\\}$. An element of that is a big tuple indexed by $A$ and if you ask the element in the spot $x\in A$, it gives back an element that's in $B(x)$. So it's the exact same thing. Also note that when you take $B$ to be constant, you get $\prod\_{x\in A}B$ which is usually denoted $B^A$ or $A\to B$.

# Answer
> 0 votes
It seems that your primary issue is that the way the operators are rendered in the setting of higher order type theory and higher order logic seems a bit forced and conflationary. I tend to agree.

An extension of Curry-Howard that stays entirely within first order logic will use natural bijections on indexed categories. I lay out the general framework for including all the usual connectives here in my reply to Categorical semantics explained – what is an interpretation?, where quantifiers are treated with natural bijections involving indexed categories.

In particular, if $$ denotes a category, then $||$ denotes its set (or class) of objects, and for each $A, B ∈ ||$, $(A, B)$ is set of morphisms $f: A → B$. So, if $$ is the Logic category, then included in it would be such natural bijections as $$ (C, ⊤) ⇔ 1(0,0) = \\{1\_0\\},\quad C ∈ ||\\ (C, A ∧ B) ⇔ (C, A) × (C, B),\quad A, B, C ∈ ||\\ (C, A ⊃ B) ⇔ (C ∧ A, B),\quad A, B, C ∈ ||\\ (C, ∀A) ⇔ ^T(K\_TC, A),\quad A, C ∈ || $$ where the category $1$ has $|1| = \\{0\\}$ and $1(0,0) = \\{1\_0\\}$. This involves the product of categories (used for $A ∧ B$) and indexed categories (used for $∀A$). The universal quantifier is then re-conned into this by equating $(∀x:T)A(x)$ with $∀\[x:T ↦ A(x)\]$, i.e. with $∀\[(λx:T)A(x)\]$. I define the notation for $^T$ in the linked reply.

In this formulation, $T$ is just a set. For instance, it could be the set of terms, or it could denote a sort, if you're using a many-sorted logic.

As was pointed out to me (by another reply in that thread), I actually had to make a minor change to the treatment for the universal quantifier. The natural bijection for the universal quantifier I had in the original reply was: $(C, ∀A) ⇔ ^T(C, A)$; but $C ∉ |^T|$. Rather, $C ∈ ||$ has to be *injected* into $|^T|$ by the map $K\_T: C ∈ || ↦ K\_T C ∈ |^T|$ (as the constant function that takes $t ∈ T$ and yields $C ∈ ||$).

This embodies the rule that $C ⊦ (∀x:T)A(x)$ if and only if $C ⊦ A(t)$, for all $t:T$, provided that $C$ is "constant in $x$" (i.e. independent of $x$).

Similar treatments apply to the dual connectives and their natural bijections are listed here for completeness: $$ (⊥, D) ⇔ 1(0,0) = \\{1\_0\\},\quad D ∈ ||\\ (A ∨ B, D) ⇔ (A, D) × (B, D),\quad A, B, D ∈ ||\\ (A ⊂ B, D) ⇔ (A, B ∨ D),\quad A, B, D ∈ ||\\ (∃B, D) ⇔ ^T(B, K\_TD),\quad B, D ∈ || $$ and a similar convention is adopted for the extential quantifier, equating $(∃x:T)B(x)$ with $∃\[x:T ↦ B(x)\]$, or just $∃\[(λx:T)A(x)\]$, if you will.

This embodies the similar rule that $(∃x:T)B(x) ⊦ D$ if and only if $B(t) ⊦ D$, for all $t:T$, provided that $D$ is "constant in $x$".

As I noted in the linked reply, the requirement that each of these be a natural bijection tow-ropes a bundle of operators and equational identities (a.k.a. commutative diagrams) ... but does so in a standard way, rather than by ad hoc impositions.

There are arguments for using higher order logic and higher order type theory. It provides a more direct cover for the way mathematics is normally expressed in the literature and things that can be proven in a few lines may require the size of the universe in spatial storage and massive tree-carnage in paper requirements to do the equivalent of in first order logic. Strictly speaking, however, it isn't part of the Curry-Howard correspondence, but is an independent development stemming largely from de Bruijn and the AutoMath project, and de Bruijn's discovery was independent of that of Curry and Howard (and Lambek). The two lines of development are often confused with one another, but they are separate, though parallel, lines.

The issue of "coherence" also arises: a category or sub-category $$ may be called coherent if $(A,B)$ has either 0 or 1 elements in it, so that from $f: A → B$ and $g: A → B$, one infers $f = g$. Depending on what combinations of connectives, in the list above, that you include, you may get "coherence"; but I don't see that as a problem. There are other ways to fit predicate logic into Curry-Howard that seem to evade this issue: using the idea of "continuations" (Curry-Howard With Predicate Logic And Continuations). I don't know if the method, described above, for handling quantifiers can be grafted onto this.

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


# Question
Title: Optimizing Pairings Between Integers and Intervals for Maximal Matching
Consider the scenario where we are given a collection of n integers. These integers are unordered and may include duplicates. Additionally, we have a set of m ranges, each defined by two integers representing the lower and upper boundaries of the interval. Similar to the integers, these intervals are unordered and duplicates are allowed.

The objective is to create pairs between the integers and the intervals under the following conditions:

An integer can only be matched with an interval if it falls within the range of the interval. For instance, the number 4 can be paired with the interval \[3, 10\], but not with \[5, 10\]. Each integer is allowed to pair with only one interval, and vice versa. The goal is to maximize the total number of such pairs. We are solely interested in determining the maximum number of possible pairs, rather than identifying the specific pairings.

For illustration:

Given a single number 2 and an interval \[4, 10\], there would be no possible pairing, resulting in an output of 0. With the number 2 and an interval \[2, 10\], a single pair can be formed, leading to an output of 1. For numbers 3, 7, 8, 12 and intervals \[0, 10\], \[5, 15\], \[20, 25\], the maximum number of pairs that can be formed is 2. While a straightforward approach might involve an algorithm with time complexity of O(nm), the challenge lies in devising a more efficient solution. The question is whether it's feasible to construct an algorithm with a time complexity of O(max(nlog(n), mlog(m), nlog(m), m\*log(n))), thereby optimizing the process of determining the maximal number of pairs

# Answer
> 0 votes
Consider the case of maximal bipartite matching between the two parties: the set of integers (let's call it $Z$) and the set of intervals (let's call it $I$). From Kőnig's theorem, we know that the maximum possible matching size can be at most $\min(|Z|, |I|)$. Now, how do I efficiently find a maximal matching?

One can use an interval tree $T$ to store all the intervals in $I$. The construction takes $O(|I|\log|I|)$ time with $O(|I|)$ storage cost. Now for each integer $z\in Z$, we query in $T$ to see if it hits some interval $i\in I$. We pair $(z, i)$ and delete $i$ from $T$. Searching and deletion both take $O(\log|I|)$ time. Thus, we have an $O((|I|+|Z|)\log|I|)$ algorithm for maximal matching.

For a maximum matching one can use the Hopcroft–Karp–Karzanov algorithm to get an $O(m\sqrt{n})$ algorithm where the graph has $n$ vertices and $m$ edges. Here we have $n = |I|+|Z|$ and $m \le |I||Z|$. Since $m$ can be of order $O(n^2)$ this gives you a $O(n^{2.5})$ algorithm for dense graphs. To construct this graph, you need $O(n+m)$ operations. In case of sparse graph, the maximum matching can be obtained in $O(m\log{n})$ time (see this ref). In case of sparse input, we can employ interval searching to construct the graph efficiently.

---
Tags: algorithms, matching, bipartite-matching, intervals
---


# Question
Title: How do C compilers distinguish casting from grouping?
In the C language, there's the 2 similar-in-form but distict-in-meaning constructs:

`(type)value` which is a casting, and `(value)`, which is a grouping.

How do a $LR(1)$ parser deal with this? I can think of a compiler that breaks syntax and semantic boundary able to disambiguate it by providing information about the meaning of the token, but how does a generic parser handle this without high-level information?

# Answer
It's not possible for an LR(1) parser to solve this problem without using the Lexer Hack: information from the symbol table, which is able to differentiate type names from variable names, is reported to the parser using two different token kinds for "identifier". The impossibility stems from the grammar being otherwise ambiguous, as shown by the example from the linked Wikipedia article, `(A)*B`, which can be either a cast of a pointer dereference (if `A` is a type) or a multiplication with redundant grouping parentheses around the first operand (if `A` is a variable).

The Wikipedia article goes on to claim that Clang does not use the Lexer Hack, although I see this as a technicality: the Clang parser (which is a hand-written, recursive descent parser, not LR(1) table-driven) gets identifier disambiguation information before deciding what to do, but via a separate semantic analysis query instead of using two distinct token kinds. It's the same information, for the same purpose, just delivered via an adjacent channel.

In a comment on another answer, Ben suggests parsing without (at first) fully disambiguating. Due to the aforementioned ambiguity (among others), this is not possible when using an LR(1) parser (you'd get unresolvable shift/reduce conflicts). However, a Generalized LR algorithm can be used instead, which in general yields an abstract syntax *forest* (which uses node sharing to avoid exponential blowup) rather than a syntax tree. My MS thesis, Elkhound, a Fast, Practical GLR Parser Generator, explored the feasibility of this approach for both C and C++. The resulting parser, called Elsa, could be regarded as a "generic parser \[that handles\] this without high-level information". (Beware: Elsa is relevant to this question as a proof of concept, but is very much a "fixer upper" for anyone trying to use it to parse real-world C/C++. Clang does that job much better.)
> 21 votes

# Answer
They can easily be distinguished by a compiler: In the first case, the thing in parentheses is a type, in the second case it isn’t.

Now if you insist on parsing based on a grammar only, that may be a problem. But there is no reason why a compiler writer would limit themselves in this way. So how does a compiler do it without using high level information? It doesn’t. There is no reason to.
> 12 votes

---
Tags: formal-grammars, ambiguity
---


# Question
Title: Speed up minimizing quadratic function by FFT
I'm trying to understand the following excerpt from a paper:

> **Subproblem 1: computing $S$.** The $S$ estimation subproblem corresponds to minimizing $$ \sum\_{p}(S\_p - I\_p)^2 + \beta((\partial\_xS\_p - h\_p)^2 + (\partial\_yS\_p - v\_p)^2) \tag {7}\label{7} $$ by omitting the terms not involving $S$ in Eq $(6)$. The function is quadratic and thus has a global minimum even by gradient descent. *Alternatively, we diagonalize derivative operators after Fast Fourier Transform (FFT) for speedup.* \[Emphasis added\] This yields the solution $$ S = \mathscr{F}^{-1} \left( \frac{\mathscr{F}(I) + \beta(\mathscr{F}(\partial\_x)^\*\mathscr{F}(h) + \beta(\mathscr{F}(\partial\_y)^\*\mathscr{F}(v))}{\mathscr{F}(1) + \beta(\mathscr{F}(\partial\_x)^\*\mathscr{F}(\partial\_x) + \beta(\mathscr{F}(\partial\_y)^\*\mathscr{F}(\partial\_y))} \right) \tag{8}\label{8} $$ where $\mathscr{F}$ is the FFT operator and $\mathscr{F}^\*$ denotes the complex conjugate. $\mathscr{F}(1)$ is the Fourier transform of the delta function. The plus, multiplication, and division are all component-wise operators. Compared to minimizing Eq. $\eqref{7}$ directly in the image space, which involves very-large-matrix inversion, computation in the Fourier domain is much faster due to the simple component-wise division.

I don't understand how Eq.(8) was derived. How can FFT speed up gradient descent?

Cited by

*"Image Smoothing via L0 Gradient Minimization" Li Xu, Cewu Lu, Yi Xu, Jiaya Jia ACM Transactions on Graphics, Vol. 30, No. 5 (SIGGRAPH Asia 2011), Dec 2011*

pdf link in page 4

# Answer
Firstly, just convert the $\delta\_x$ and $\delta\_y$ operator into Toeplitz matrix $D\_x$ and $D\_x$, then the objective is a linear system. $$ ||S-I||\_2 + \beta||D\_x S - H||\_2 + \beta||D\_y S - V||\_2 $$ You can see the solution $$ S-I+\beta D\_x^T (D\_x S-H) + \beta D\_y^T (D\_y S-V) = 0 $$ yields $$ (1 + \beta D\_x^T D\_x + \beta D\_y^T D\_y)S = I + \beta D\_x^T H + \beta D\_y^T V $$ where $1$ denotes a identity matrix. Note that $(1 + \beta D\_x^T D\_x + \beta D\_y^T D\_y)$ is circulant matrix, so you can use FFT to solve this linear system.
> 0 votes

---
Tags: optimization, fourier-transform, gradient-descent
---


# Question
Title: Are modern ram architectures (DDR4 or SDRAM) Multi-port or Dual-port?
So I recently learned about dual-port and multi-port RAM but I tried doing some research on modern RAM architectures and if they use it but I couldn't find anything on it.

# Answer
> 2 votes
DDR4 is single-port. DDR5 is also single-port, *but* it's dual-channel. It can handle two commands at the same time, like dual-port memory. But those commands are expected to arrive over the same physical channel.

This is part electrical engineering (signal integrity at high speeds), part CPU architecture (multi-core CPU's with caches, main memory is used for cache misses, fairly unpredictable command mix on the DDR bus)

---
Tags: computer-architecture, cpu, memory-hardware
---


# Question
Title: can we computably list every primitive recursive function?
i have seen some articles where they use the diagonalization argument to prove the existence of non-primitive recursive functions. But this should only work if we can create an infinite list of every possible primitive recursisve function in a computable way, like say for eg we should be able to find the output of nth primitive recursive function at the nth input in a computable way. so is there any algorithm which can return any nth input of mth primitive recursive function ?

# Answer
> 3 votes
I'll build on Pål's answer to be a bit more explicit about how we can code PR functions using those operations. First of all, note that we can code any finite sequence of (positive) numbers into a single number such that the $i$'th element of the sequence can be extracted; for instance, this should be doable by mapping the sequence $\\{a\_1, a\_2, \ldots, a\_n\\}$ to the number $2^{a\_1}+2^{a\_1+a\_2}+2^{a\_1+a\_2+a\_3}+\cdots+2^{\sum\_{i=1}^na\_i}$. I'll use the standard notation of representing the value of list function (since the specific details of it don't matter) by $\langle a\_1, a\_2, \ldots, a\_n\rangle$.

From here, we do the standard recursive coding steps. More explicitly, we'll label the code of the function $f()$ by $\overline{f}()$. Then we have:

1. The constant function $C\_n^k$ is coded by $\overline{C\_n^k}=\langle 1, n, k\rangle$.
2. The successor function $S$ is coded by $\overline{S} = \langle2\rangle$.
3. The projection function $P\_i^k$ is coded by $\overline{P\_i^k}=\langle 3, i, k\rangle$.
4. If the codes of $g\_1, g\_2, \ldots$ are $\overline{g\_1}, \overline{g\_2}, \ldots$ and the code of $h$ is $\overline{h}$ then the code of the composition $h(g\_1, g\_2, \ldots, g\_m)$ is $\langle 4, m, k, \overline{h}, \overline{g\_1}, \ldots, \overline{g\_m}\rangle$, where $k$ is the arity of the $g\_i$ (and thus the composite function).
5. If the code of $g$ is $\overline g$ and the code of h is $\overline h$ then the code of the (primitive) recursive applicator is $\overline{\rho(g,h)}= \langle 5, k, \overline{g}, \overline{h}\rangle$, where again $k$ denotes the arity of $g$.

Note that not every natural number necessarily corresponds to a valid function! But given a natural number, we can primitive-recursively determine whether it *does* code a valid function or not, and if it does we can compute the value of that function given specified inputs. This is enough to make the original proof go through.

# Answer
> 6 votes
The primitive recursive functions can be defined in terms of the following five axioms:

1. *Constant function:* $C\_n^k$ is a $k$-ary function that always returns $n$
2. *Successor function:* $S$ is a 1-ary function $S(x) \mapsto x+1$
3. *Projection function:* $P^k\_i$ is a $k$-ary function that returns its $i$th argument
4. *Composition operator*: $h \circ (g\_1, \dots, g\_m) = h(g\_1(\overline x), ..., g\_m(\overline x))$ where $\overline x$ is a list of $k$ values
5. *Primitive recursive operator*: $\rho(g,h)$ takes a $k$-ary function $g$ and a $k+2$-ary function $h$, and essentially runs a (bounded) for loop.

The point is that all these are at most countable infinite and we can enumerate the functions that can be built from these axioms.

---
Tags: algorithms, proof-techniques, primitive-recursion
---


# Question
Title: Reduction from $\mathsf{ALL}_{\mathsf{TM}}$ to it's complement
I'd like to know if there's a reduction $\mathsf{ALL}\_{\mathsf{TM}}\leq\_{m}\overline{\mathsf{ALL}\_{\mathsf{TM}}}$ where of course $\mathsf{ALL}\_{\mathsf{TM}}=\left\\{ \left\langle M\right\rangle \mid\mathsf{L}\left(M\right)=\Sigma^{\*}\right\\} $

All attempts I've tried failed - if for example I try to define the reduction by switching the accept state and the reject state, the construction fails because it doesn't take care of the case where the machine doesn't halt.

# Answer
The short answer to your question is no. There is no such a reduction.

Your question is actually can be answered using theorem which is stated here:

Prove that a language does not many one reduce to its complement
> 0 votes

---
Tags: turing-machines, reductions, undecidability, recursively-enumerable
---


# Question
Title: A pedagogic review on the advantage/drewbacks of distributed computing
I need to understand the motivations behind distributed computing, namely the fact to perform a computation by making physically separated computer, connected by communication links, work together.

I am in particular interested in a review explaining their interest in the context of being more resilient to errors (I know this is among the motivations).

Importantly: I am working in quantum computing, with interest in distributed quantum computing. *I am then not an expert of classical computing* (this is why I am asking for a pedagogic review). Essentially, I would like to better understand the motivations to distribute a computation in the classical paradigm (because there can have a big communication cost, it is not clear that distributing is always a good idea).

# Answer
Some basic pros and cons are outlined here. There are multiple books on the topic as well e.g.

> Kshemkalyani, A. D., Singhal, M. (2011). Distributed Computing: Principles, Algorithms, and Systems. (n.p.): Cambridge University Press.

> Tanenbaum, A. S., Steen, M. v. (2016). Distributed Systems: Principles and Paradigms. Netherlands: Createspace Independent Publishing Platform.

> Peleg, D. (2000). Distributed Computing: A Locality-sensitive Approach. United States: Society for Industrial and Applied Mathematics.
> 2 votes

# Answer
Laslie Lamport is very influential in the field of distributed computation, here is his quote: "A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable'' is a famous Lamport quip. I would suggest to check the article about him. he's trying to formalize that field, which is very hard. So try to find out his works and research his contributions to the field. Even classical distributed computation is still active area of research (especially it's formal verification). thanks for the helpful comments, I edit the answer to add further links, that asks the question "why", about distributed systems. aws about pros of distributed computation, aws engineer about pros of distributed computation.

P.S also since the other answer also provided references, I think author got enough combined resources for the topic, I consider my answer worth to not delete, if there are other suggestions or comments I am very grateful for that, also if arguments will be further provided about irrelevance of my answer, I will gladly delete it. Thanks to this community that I am able to communicate about computer science with people around the world.
> 1 votes

---
Tags: reference-request, distributed-systems
---


# Question
Title: Calculating the highest possible scoring Scrabble move
Let’s say there are n fixed words permitted in some game of Scrabble, on an m x m squares board.

We are assuming an idealized scenario where anyone can write any word on the board. Assume both players have an unlimited number of every word. Or, assume there is only one player, playing every round.

Assume all the allowed words are the same length or shorter than the length of the board.

The number of choices for the first move will be, for each word, the number of positions on the board it can be placed. (I assume this is a subquestion with an easy answer.) (It must be placed on the starting central square).

After a word is lain on the table, maybe we have to calculate the number of choices for the next word just iteratively, where for each adjacent square to all pieces on the board, we count the number of valid scrabble words fitting there, bounded by the amount of available space.

Is it possible to prove what the highest possible scoring move across all possible games of Scrabble is?

Is this an easy problem, or does it suffer from combinatorial explosion?

What is the complexity class of such an algorithm?

# Answer
Scrabble is PSPACE-Complete (see this ref.). Dynamic programming can be used to devise a more tractable solution instead of plain brute force.

Here are some pointers to designing an efficient Scrabble solution: some computer programs, a useful data structure called GADDAG, and a stackoverflow discussion.
> 0 votes

---
Tags: board-games
---


# Question
Title: How reliable is a floating point operation (how often does it makes mistakes)
While computers are very reliable, they can also do errors because of noise. I would like to have an idea of the rough order of magnitude of error per floating point operation in a computer, in a typical environment (in a typical office, like not deep underground for instance), with a reference to a good paper.

I am not looking for rounding errors but I am looking for errors due to noise in the surrounding environment (parasitic electromagnetic fields could eventually flip bits, hence introduce errors inside of the computer for instance).

\[Clarifications\]: What we call noise in physics is not related to "audio" noise. It corresponds to a physical (usually random) process that can introduce errors. An example of noise is thermal noise (a hot system is more prone to error than a cold one).

# Answer
> 3 votes
Not an actual answer, but I think you are interested in the soft error rate of modern computers (or perhaps only the single-event upset rate). These rates will likely vary depending on where the computer runs (space/high atmosphere vs underground facilities).

CPU producing companies should probably have some rough figures about these error rates for their components in standard use conditions.

---
Tags: floating-point
---