title: NP-completeness of graph problem

text:
# Question
Title: NP-completeness of graph problem
I am studying for my final exams in complexity theory and I came across a graph problem which I cannot fully prove that it is NP-complete. Its gist is the following:

> Assume that you have a weighted directed graph, where the weight of each edge is the travel time between the two corresponding nodes. There are goods on each location of value $v\_i$ that you can acquire once. Each good has a time deadline $d\_i$ after which it expires.

> You want to answer whether you can accumulate a total value $V$.

I have to show that the problem above is NP-complete. Skipping the proof that it is in NP, what's left is to show that we can reduce a known NP-hard problem to it. I believe the Knapsack problem is a good candidate if one uses the following reduction:

Each item in the Knapsack problem becomes a node in our graph. The weight of the item is the time to travel to this node from all other nodes, and the value of the item is the value of the good at this node. We are asked if we can reach a total value of V, the same as in the Knapsack problem.

This construction can be done in polynomial time. Therefore, our problem is NP-hard.

My questions:

1. Is there any better way to map the different expiration deadlines to the Knapsack problem?
2. Do you see another known NP-hard problem that is a better fit than the Knapsack problem?

# Answer
> 0 votes
Let $G = (V, E)$ be an undirected graph. Assume the value is $v\_i = 1$ for each vertex and the weight is $w\_e = 1$ for each edge. Also assume the deadline is $d\_i = |V| - 1$ for each vertex.

Then you can accumulate a total value $|V|$ if and only if there is an hamiltonian path in $G$.

---
Tags: algorithms, complexity-theory, knapsack-problems
---


# Question
Title: Efficient way to calculate many Dutch auctions?
I have 4,500 ($N$) unique items, and I want to auction each one off to the highest bidder (break ties arbitrarily).

Each item has $T$ binary traits. Since it is too complex for the $B$ bidders to specify a bid for each individual item, instead the bidders express preferences in the form of "I am willing to pay $x$ for an item with the following traits: $t\_1, ... t\_k$".

My plan right now is for each bidder and for each item, compute the bidder's bid: $0$ if the item does not meet the bidder's preference and $x$ otherwise. Then iterate over all items and for each item, select the highest bidder for that item. (Each bidder can only buy a maximum of 1 item.)

The runtime for the above procedure seems to be $O(N * B)$. For $T \<\< N \<\< B$, what's the optimal way to auction these items?

# Answer
One reasonable way to select bids would be to formulate this as a matching problem.

Build a bipartite graph, with one left vertex per bidder and one right vertex per item. Add an edge from a bidder to each item that meets the bidder's preference, with weight $x$ (the bidder's willingness to pay). Then find a maximum-weight matching in this bipartite graph using a standard algorithm, such as the Hungarian algorithm.

This will give you the optimal way to assign items to bidders, where "optimal" means that you extract the most money from bidders.
> 0 votes

---
Tags: sorting, data-compression, constraint-satisfaction
---


# Question
Title: L = {⟨M⟩ : there does not exist w ∈$Σ^*$ such that M rejects w } is in coRE?
given this lanauge: $L=\left\\{\langle M\rangle\right.$ : there does not exist $\mathrm{w} \in \Sigma^\*$ such that M rejects $\left.\mathrm{w}\right\\}$.

how can I determine whether it is in $R, R E \backslash R, \operatorname{coRE} \backslash R$, or $\overline{R E \cup c o R E}$?

I tried to prove the it is in $coRE\backslash R$, by reducing from the following language: $E\_{T M}=\\{\langle M\rangle: L(M)=\emptyset\\}$ but I'm not sure I can iterate over $\Sigma^\*$ where it might be infinite run on a Turing machine

# Answer
> 1 votes
$L$ is clearly not recursive: given a Turing machine $M$, consider $\overline{M}$ the machine where you reverse accepting and rejecting states.

Then it is clear that $\langle M\rangle\in E\_{TM}$ if and only if $\langle \overline{M}\rangle \in L$.

However, $L$ is indeed in $coRE$, this can be proved by dovetailing: given a Turing machine $M$, the following algorithm will halt in finite time and answer correctly if $\langle M\rangle \notin L$, and never halts if $\langle M \rangle \in L$ (we consider inputs in lexicographic order for example):

```
n ← 1
while true:
    for i = 1 to n:
        simulate one more step of computation of M on the nth input;
        if it halts and rejects, then return false;
    n ← n + 1

```

---
Tags: turing-machines, reductions
---


# Question
Title: What is the difference between deterministic and confluent?
I understand deterministic as a function for some input will always give the same output, and these inputs and outputs can be sets of values represent by a predicate.

I understand confluent as convergence of a rewriting system, ie the rewritten terms always converge to some term, which could also represent a predicate.

It seems like these definitions are very similar in what they achieve.

Would all deterministic systems be confluent and vice versa?

Or is determinism really about the paths taken and exact timmings of computations to reach an answer, ie a deterministic algorithm must always have the same trace of paths for every run?

Also there is a notion of choice in non-deterministic algorithms, how does this fit in?

I feel like these definitions should work across sequential and concurrent systems, but for concurrent systems the exact timings are less important as the scheduler controls this.

# Answer
> 2 votes
If a binary relation is confluent and terminating, then the map from initial state to final state is total and deterministic. The converse also holds.

If a binary relation is confluent, the binary relation need not be a function.

You'll have to decide what you mean by "deterministic" and whether you refer to what the original state ultimately leads to (then the answer to your question is yes, as mentioned in the first paragraph of this answer) or whether you refer to the behavior in a single step of the system (then the answer is no, as mentioned in the second paragraph of this answer).

# Answer
> 2 votes
In terms of abstract rewriting, confluence and determinism are different notions. Let $\to$ be a binary relation on a set. The relation $\to$ is *deterministic* if $b = c$ whenever $b \leftarrow a \to c$. The relation $\to$ is *confluent* if there is some $d$ such that $b \rightarrow^\* d$ and $c \rightarrow^\* d$ whenever $a \rightarrow^\* b$ and $a \rightarrow^\* c$. It can be easily shown that every deterministic relation is confluent by tiling each $\leftarrow \cdot \to$ by $=$.

The converse does not hold. Consider the set $A = \\{ a, b, c, d \\}$ and the binary relation $\to$ defined by $a \to b$, $a \to c$, $b \to d$ and $c \to d$. The relation $\to$ is confluent but not deterministic as $a \to b$ and $a \to c$ but $b \neq c$.

> I understand confluent as convergence of a rewriting system

Confluence and convergence are different in abstract rewriting. A relation $\to$ is *convergent* (or complete) if it is confluent and *terminating*, that is, there is no infinite sequence $a\_0 \to a\_1 \to \cdots$.

---
Tags: nondeterminism, term-rewriting
---


# Question
Title: Generalizing Matrix Chain problem: optimal summation in a tree
Matrix Chain Problem can be viewed as the problem of finding the optimal summation order in a path-structured tensor network. How hard is the problem if we extend it to trees?

For instance, take the following sum, written in Einstein summation notation $$A\_i B^i\_j C^j\_k D^k$$

This corresponds to the tensor network below:

There are 3 edges $e$, corresponding to indices $i,j,k$, each with their own dimension $d\_e$. One possible summation order is below:

$$((A\_i B\_j^i) C\_k^j) D^k$$

The number of multiplications, aka, total cost of this order is

$$d\_i\times d\_j + d\_j\times d\_k + d\_k$$

Given a list of dimensions $\\{d\_e\\}$, finding the order which minimizes total cost is equivalent to the Matrix Chain problem, solvable in $n \log n$ time (wikipedia).

Take the following sum in Einstein summation notation:

$$A\_{ij}B^{i}\_{kl}C^j\_{mn}D^k E^l F^m G^n$$

This corresponds to the tensor network below, binary tree of depth $D=3$:

There are 6 edges $e$, each corresponding to an index of dimension $d\_e$. One way of computing the sum is the breadth-first search order

$$(((((A\_{ij}B^{i}\_{kl})C^j\_{mn})D^k) E^l) F^m) G^n$$

Each step is a contraction of two tensors, requiring the number of multiplications which is the product of dimensions of all indices occurring in either tensor. IE, cost of computing $Y\_i^l=X\_{ijk}Y^{jkl}$ is $d\_i\times d\_j\times d\_k\times d\_l$.

Total cost of computing this sum in breadth-first search order is $$d\_j\times d\_i\times d\_k \times d\_l +d\_k\times d\_l\times d\_j\times d\_m\times d\_n+d\_k\times d\_l \times d\_m \times d\_n + d\_l \times d\_m \times d\_n +d\_m\times d\_n + d\_n$$

For a tensor network with $n$ tensors, forming a complete binary tree of depth $D$, given a list of dimensions $\\{d\_e\\}$, what is the complexity of finding an order which minimizes total cost?

PS: if we allow leaves to have free indices (ie, dangling edges in this graph), this kind of representation is an instance of "Hierarchical Tucker Decomposition"

# Answer
If you restrict yourself to *linear* contraction orders, i.e., you only contract tensors adjacent to the set of already-contracted ones, you can actually do this in polynomial time. I have recently proved this in my Master's thesis. The result follows from a fascinating yet non-trivial connection to *database join ordering* (I recommend these slides for join ordering). I also have a preprint, but the thesis explains it properly.

If you want *general* contraction orders, i.e., you contract any two adjacent tensors, this is still an open problem (I learned this from the author of Xu et. al; that is also the reason they optimized for a weaker cost function, i.e., minimizing the largest intermediate tensor). Actually, the situation is similar in join ordering: the problem for tree queries is still open (Moerkotte et al.).

However, you can provide *near-optimal* general contraction orders for trees. The key idea is to regard the linear order of the optimal algorithm as a chain and run the textbook cubic-time dynamic programming to build the optimal contraction tree given that order. This idea was first explored in Neumann et al. (linearized dynamic programming) and has been shown to provide near-optimal solutions. Beyond the optimality result, I empirically validated that this holds for tensor networks as well. Recently, Ibrahim et al. proposed the same approach, but their linearization, i.e., the permutation of the leaves, is chosen greedily. The advantage of having an optimal algorithm for the linearization is that you are *at least* optimal in the regime of linear orders, so you can provide robustness that a greedy algorithm cannot.
> 2 votes

---
Tags: algorithms, time-complexity, dynamic-programming
---


# Question
Title: Difference between Row Major Order and Column Major order
Let take a multi-dimensional array: $a\[2\]\[3\]\[4\]$

Here $a$ is a three-dimensional array, which means that it is a collection of two-dimensional array's.

Therefore `sizeof(a)` = No.of 2D arrays * Size of each 2D array = $2\*(3\*4) = 24$ elements.

Now my observations are:

1. If Row Major Order is taken, then we have 2 arrays of a\[3\]\[4\] so each array has $12$ elements.
2. If we take Column Major Order, then we have 4 arrays of a\[2\]\[3\]; that is we have only $6$ elements per array.

Is this approach of calculation right?

# Answer
The only difference between Row Major Order and Column Major Order in the case of ANSI C is that the memory access patterns are different.

Suppose we have an array $a\[i\]\[j\]$ which is stored in Row Major Order and we decide to iterate by columns, then the CPU would take more time to process this set of instruction as compared to the case where we decide to iterate by rows. Using the correct access pattern helps the Operating System use caches more effectively.

However this has no bearing on the running time complexity of the code and for all arrays which occupy space below a certain threshold, the difference would be hardly noticeable.

One final note:

1. If Row Major Order is taken, then we have $2$ arrays of $a\[3\]\[4\]$ so each array has $12$ elements. Total no.of elements $= 2\*12 = 24$ elements.
2. If Column Major Order is taken, then we have $4$ arrays of $a\[2\]\[3\]$ so each array has $6$ elements. Total no.of elements $= 4\*6 = 24$ elements.
> 2 votes

# Answer
Consider this :

```
int[][] data = {1,2,3}, {4,5,6}, {7,8,9};
for(int i = 0; i < data.length; i++){ //Rows
    for(int j = 0; j < data[i].length; j++){ //Columns
        int elements = data[i][j];
        System.out.print(elements + " ");
    }
    System.out.println();
}

```

In a Row-Major traversal of an array, the elements are stored in the following order in the memory: 1,2,3,4,5,6,7,8,9. So, the first element will be `data[0][0]`, second element will be `data[0][1]`, third element will be `data[0][2]`, … and the last element being `data[2][2]`.

On the other hand, in a Column-Major traversal,

```
int[][] data = {1,2,3}, {4,5,6}, {7,8,9};
for(int j = 0; j < data[0].length; j++){ //Columns
   for(int i = 0; i < data.length; i++){ //Rows
        int elements = data[i][j];
        System.out.print(elements + " ");
    }
    System.out.println();
}

```

the elements are stored in the memory as follows: 1,4,7,2,5,8,3,6,9. So, the first element will be: `data[0][0]`, second element will be `data[1][0]`, third will be data`[2][0]`, … and the last being `data[2][2]`.
> 0 votes

# Answer
Speaking of $2$ arrays $\[3\]\[4\]$ vs. $4$ arrays $\[2\]\[3\]$ is misleading, as it might be understood with the same storage order for all arrays.

The truth is closer to $2$ arrays of $3$ arrays of $4$ elements vs. $4$ arrays of $3$ arrays of $2$ elements, if that is understood as the storage order.

Then the commutativity/associativity rule $2\cdot(3\cdot4)=4\cdot(3\cdot2)$ obviously holds.

There are six possible ways to permute three indexes, but only two are considered: direct and reverse.

---

In 3D, the terminology *row/column* is not so helpful because there is no universal orientation convention and no unique word for the third dimension (can be *layer*).
> 0 votes

---
Tags: programming-languages
---


# Question
Title: NP-completeness of problem based on non-arbitrary instance
To prove that a problem is NP-complete, one has to show that it is both (a) in NP and that it is (b) NP-hard by reducing a known NP-complete problem to it in polynomial time.

Regarding the reduction, I understand that the instance of the known NP-complete problem must be **arbitrary** to avoid loss of generalisation.

Does the instance of the target problem also need to be arbitrary or can one assume specific values to its inputs to make the reduction easier?

Also, if one can assume specific values and carry out the reduction/proof, does the proof also hold for an arbitrary instance of the target problem?

From my understanding, if a **specific** instance of the target problem is proven to be NP-hard via reduction, then an arbitrary instance of the same problem is **at least as hard** as its specific instance, thus also NP-hard. Is this logically/mathematically sound?

# Answer
A **specific** instance is never NP-hard. The concept of NP-hardness only applies to languages (classes of instances, if you will).

If your reduction from $A$ to $B$ is $f$, then $f$ is a function from the set of instances of $A$ to the set of instances of $B$. The function does not need to be injective nor surjective.

If $A$ is a NP-hard problem and you have a (Karp) reduction $f$ from $A$ to $B$, then the restriction of $B$ in which the instances are guaranteed to be in the image of $f$ is also NP-Hard. Since this is a (not necessarily proper) subset of all instances of $B$, the language $B$ is also NP-Hard.
> 6 votes

---
Tags: algorithms, complexity-theory, np-complete, np-hard
---


# Question
Title: How does Post's theorem connect to concepts of universality and computability in theoretical computer science?
Since functional completeness is a kind of universality, there might be deep connections to other universal phenomena like Turing completeness.

# Answer
I don't think they are formally related. Post's theorem concerns Boolean functions $\mathbb{B}^n \to \mathbb{B}$ (where $\mathbb{B} = \\{0, 1\\}$), which are always trivially computable by a Turing machine.

Differing concrete domains aside, in the abstract, Post's theorem is about finite lists of Boolean functions, whereas Turing completeness applies to a more general model of computation, not necessarily given as a finite list of operations. For example, Conway's game of life is Turing complete, but this model of computation is not built from a finite list of functions like in Post's theorem. Post's theorem instead characterizes when a finite list of functions $f\_1, f\_2, \ldots, f\_k$ is expressively complete, i.e. can express all Boolean functions.

The closest analogy to Post's theorem in the context of computability would be if we can give an *exact characterization* of when a list of functions $f\_1, f\_2, \ldots, f\_k$ can express all Turing-computable functions. I'm not aware of such a *general* characterization, though I'm sure it has been studied! Of course, we have many *specific* examples: the lambda calculus operations ($\lambda$ abstraction and function application) are enough; WHILE programs (WHILE, IF THEN, and variable assignment) are enough; and so on. But I am not aware of any theorem of the form: you give me a list of functions or function constructors, and I'll tell you whether or not they are Turing-complete.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: How Can the Bounded Search Tree Algorithm for Closest String run in $\mathcal{O}(kd)$ per node?
I am trying to understand an algorithm for solving Closest String using bounded search trees, as found in *Parameterized Algorithms* (Cygan et al., 2015).

Assume we have a set of $k$ strings $x\_1, ..., x\_k$ all of length $L$ and an integer $d$. The problem is to determine if there exists a string $y$ such that $d\_H(y, x\_i) \leq d$ for all input strings $x\_i$, where $d\_H$ is the Hamming distance. If this is the case, $y$ is known as a *center string*.

The algorithm goes as follows - I'm going fast since I'm assuming the reader knows about it, just to make sure we're on the same page:

1. Organize the input strings into a $k \times L$ matrix. If any columns in this matrix have the same character for all strings, delete them, as they are an obvious choice for a solution.

1.5. \<we may already be done if the matrix ends up large or small enough\>

2. Let $z = x\_1$. If $z$ is a center string, we are done. If $z$ is not a center string, then there exists an $x\_i$ with $d\_H(x\_i, z) \> d$, so there are at least $d + 1$ positions where $x\_i$ and $z$ differ. If a (hypothetical) string $y$ is a center string, then there is at least one position where $x\_i$ and $y$ are the same. So we can pick $d + 1$ of these positions and recurse with a modified $z$ such that $z\[p\] = x\_i\[p\]$ for each of these positions - for at least one of these $x\_i\[p\]$ must be equal to $y\[p\]$. Since each level of recursion has at least one branch that brings $z$ closer to $y$, we will reach $y$ after $d$ steps (assuming it exists).

Now the complexity of this is supposed to be $\mathcal{O}(kL + kd(d + 1)^d)$. The $kL$ is for step 1. We can only recurse $d$ times, with $d + 1$ children at each level, that's where the $(d + 1)^d$ comes from. That leaves $kd$ as the time cost of step 2 at each node.

But how is the task of 1. checking whether $z$ is a center string and 2. picking out the $x\_i$ and the $d + 1$ positions supposed to be doable in $\mathcal{O}(kd)$? After deleting the trivial columns in step one, our matrix is up to $kd$ columns wide. So comparing $z$ to $x\_i$ for each $i$ requires iterating over up to $kd$ characters, leading to $\mathcal{O}(k^2d)$. We cannot make any assumptions about the content of the matrix - the strings could all be identical, the instance could be unsolvable, it could be just-barely solvable - only that its width is between $k + 1$ and $kd$. How does one come up with this complexity? Or have I misunderstood the complexity bound they gave?

# Answer
Please see Theorem 1 from the original paper. The distance of $z$ to $x\_i$'s can be updated in $O(k)$ time.

Note that $z$ might not necessarily be chosen from the given set of strings $x\_1 , \dotsc, x\_k$. So, the algorithm change the string $z$ at one position at each step of the recursion. Since only one alphabet is changed, its distance to a particular string can be updated in $O(1)$ time.
> 1 votes

---
Tags: strings, hamming-distance
---


title: Zero sum game: dp recursion strategy

text:
# Question
Title: Zero sum game: dp recursion strategy
Trying to solve the zero-sum problem described here, where two opponent players at each turn can choose to collect 1, 2 or 3 stones with different values, with the objective of getting more points at the end of the game (and assuming each player is playing optimally).

All presented solutions based on recursion suggest to save at each position in an array (memoization) the points difference between the 2 players, thus deriving the current step as the number of stones taken minus the difference at the following position.

I tried instead a different approach, where I save at each array position the best score any player get starting from that position onward. I then compute a single recursion step as the number of points collected in the current turn plus the best score the same player might get from here on (recursion), taking into account the player are alternating.

My solution fails with some test cases and I wanted to understand if there is a problem with the theory (or if I just have to counter check the implementation).

# Answer
It is certainly a valid approach to compute "at each array position the best score any player get starting from that position onward".

---

If a player starts first from position pos, denote that best score as best\_score\_from\_pos(pos, "Alice"). Otherwise, denote that best score as best\_score\_from\_pos(pos, "Bob").

The recurrence relations are
best\_score\_from\_pos(pos, "Bob") = value\_sum\_from\_pos(pos) - best\_score\_from\_pos(pos, "Alice")
and
best\_score\_from\_pos(pos, "Alice") = max(
stoneValue\[pos\] + best\_score\_from\_pos(pos+1, "Bob") ,
stoneValue\[pos\] + stoneValue\[pos+1\] + best\_score\_from\_pos(pos+2, "Bob"),
stoneValue\[pos\] + stoneValue\[pos+1\] + stoneValue\[pos+2\] + best\_score\_from\_pos(pos+3, "Bob") )
when the indices for stoneValue are within bound. If out of bound, replace the corresponding argument for the max function with 0.

If best\_score\_from\_pos(0, "Alice") * 2 \> total value, Alice wins.
If best\_score\_from\_pos(0, "Alice") * 2 \< total value, Bob wins.
If best\_score\_from\_pos(0, "Alice") * 2 == total value, it is a tie.

---

It is slightly more complicated to implement the approach above than the "presented solutions" that computes for each position "the points difference between the 2 players". On the other hand, the approach above is somewhat easier to understand.

By the way, my implementation of the approach above passes all tests for the LeetCode problem.
> 1 votes

# Answer
There is a well known algorithm to solve Zero sum games called MiniMax algorithm. The reason for the failure of your above mentioned approach: Let's say at Alice's turn she took a move to maximize her score in the next turn Bob will try to minimize Alice's score. I think you focussed on only one player's action and didn't take account of other player's action . *Score\_of\_player(Alice,i)=Max(Min(Score\_of\_player(Bob,i-1)))* where i is the number of turns
> 0 votes

---
Tags: algorithms, dynamic-programming, board-games, memoization
---


# Question
Title: What is the difference between type inhabitant and subtyping?
I am confused with the terms inhabitant vs. subtyping.

For example,

1. We usually think that "john is an inhabitant of Human". This sentence is correct, because john is an individual, and an individual belongs to the set Human (that reflects the meaning of inhabitant). However, if we think of john as a subset with only one element, we could also say "john is a subtype of Human", is that right?
2. As we all know Cat is a subtype of Animal. However, it seems no problem if we think Cat as an inhabitant of the Animal? (Suppose in the discourse, the sets Dog, Fish, Human, etc are not overlapping, i.e. treat Dog, Fish, Human, etc as individuals)?

My question is that

1. How to formally distinguish inhabitant and subtyping?
2. Does subtyping-framework actually need the concept of inhabitant? (because it seems useless).

Thanks.

# Answer
There is an obvious difference: you are an inhabitant (member) of humankind, but since you are not a collection of little humans you are not a subset of humanity. And as Bertrand Russell taught us all, one should *not* conflate an object $x$ with the singleton set $\\{x\\}$.

The relevant analogy is $$\frac{\text{element}}{\text{subset}} = \frac{\text{inhabitant}}{\text{subtype}},$$ with the caveat that subtyping can be quite different from the subset relation (for instance in object-oriented languages with a class hierarchy).

We can also note that $\in$ and $\subseteq$ are expressible in terms of each other, as already noticed by the OP: $$x \in A \iff \\{x\\} \subseteq A$$ and $$A \subseteq B \iff \forall{x \in A} . x \in B.$$ But just because two concepts are expressible in terms of each other, that does not mean they are the same concept.
> 1 votes

# Answer
I'll answer using the words instanceof (instead of inhabitant) and Class (instead of Type) since these are the terms in UML.

It seems to me that you are thinking about classes anb subclasses like sets of individuals and subsets of individuals. However, I would suggest, following \[1\], interpreting a class as a set of properties (e.g. Person is the set of properties of being Animal and being Rational), and a subclass as a superset of such properties (e.g. Child is the set of properties of Person, together the property of being underage). In some sense, we are used to say that a Child inherits all the properties of Person, and adds some additional properties (being underage).

A subtyping, then, only says which classes "inherits" which properties from which other classes (Child inherits from Person, Person inherits from Animal, etc). Do note that this is a relation among classes (e.g., sets of properties).

An instanceof, however, states which objects satisfies such properties (john is an instance of Child because it satisfies all the properties of Person plus being underage).

Saying that john is a subtype of Human sounds strange because, in essence, you are saying that john is a set of properties, whereas john is, as you were saying, a real world individual.

Saying that Cat is an instanceof Animal sounds strange too because, in essence, you are saying that (the concept of) Cat is a real world object satisfying the properties of Animal. The concept of Cat, as a set of Properties, inherits all the properties of Animal, but it does not satisfy them (i.e., the concept of Cat is not mortal).

If you like (first-order logic) formalism, again, following \[1\] you can formalize these as:

* Objects can be seen as logic constants: $John$, $Mary$, etc
* Classes can be seen as logic Predicates: $Person$, $Child$
* instanceof can be seen as a logic ground atom: $Person(John)$
* subtypeof can be seen as a logic constraint: $\forall x. Child(x) \rightarrow Person(x)$

\[1\] Olivé, A. (2007). Conceptual modeling of information systems. Springer Science & Business Media.
> 0 votes

---
Tags: type-theory, formal-methods, knowledge-representation, ontologies
---


# Question
Title: Have I correctly defined the language of strings that have balanced parenthesis?
I am trying to learn about formal languages and I was wondering how I would go about defining the language that contains all strings which have matched parentheses and this is the definition I came up with —

$L = \\{(x\*)|x\in L\\}\cup\\{\epsilon\\}$

Here, $($ and $)$ denote the literal characters '(' and ')' respectively. I use the union to make sure that the empty string is considered a valid string.

I am concerned here about whether referencing $L$ in the definition of $L$ is a meaningful thing to do, and if it isn't how I would go about defining such a language.

# Answer
> 1 votes
Referencing $L$ in the definition of $L$ is not meaningful, because it makes the definition self-referential/circular, which isn't kosher. You can't define a concept in terms of the concept. While there are structured ways to address the challenges associated with self-reference in definitions (e.g., recursively defined types, least fixed points), this can be tricky and might be best avoided at your level of experience.

A better way to define such a language is through a context-free grammar that generates this language.

--

Related: See https://en.wikipedia.org/wiki/Recursive\_definition, https://en.wikipedia.org/wiki/Circular\_definition, https://en.wikipedia.org/wiki/Least\_fixed\_point, https://en.wikipedia.org/wiki/Dyck\_language

---
Tags: formal-languages
---


# Question
Title: Does making the keys of a hashtable the same length make the hashtable any better?
The question popped up in my head. The hash function used is Murmur3.

# Answer
> 1 votes
*Making* keys the same size doesn't make a huge amount of sense, but fixed-sized keys for key-value stores and database indexes are an important use case. In the real-world, people do sometimes want to search on integers, or IP addresses, or DNA $k$-mers.

If your keys are *naturally* the same size, then this enables an interesting optimisation, and unlike most uses of the word "optimisation", this one actually is "optimal".

For the sake of exposition, we'll assume a few things:

* You are using a hash table that is a power of two in size, $2^n$ slots.
* The hash function returns $m$ bits, and $m\>n$.
* This hash table is a *set*, so we don't need to consider the "value" part of a key-value store. This is easy to add in later, but I'm only doing this so I don't have to keep talking about it.

What you typically do hash the key, and take the (say) lowest-order $n$ bits from the hash value, and this determines the hash slot. Within each hash slot, you then store the key in full.

One common technique, if keys are large, is also to store the hash value in each entry, because that comparison is cheap. It only costs $m$ extra bits per entry.

The first observation is that you don't need to store all $m$ bits, because $n$ of those bits are implied by the hash slot. So to support this technique, you only need to store $n-m$ bits in each entry.

So, in summary, each entry needs two things:

* $m-n$ bits of hash value, and
* a copy of the key.

Now here's the clever bit. Suppose that your keys are *also* $m$ bits in size, and suppose, furthermore, that your hash function is *invertible*. Then the key is completely recoverable from the hash value, which in turn is recoverable from the hash slot number and the additional $m-n$ bits of information stored in the entry.

So the key need not be stored at all.

(Constructing invertible hash functions is not difficult; given a non-invertible hash function using, you could use something like a Feistel network.)

Now, let's look at the space usage as a whole.

If the hash table is full, with a load factor of 1, then you need to represent a subset of $2^n$ items from a universe of $2^m$ possible items. There are ${ 2^m \choose 2^n}$ possible subsets, and so any representation must use at least $\log { 2^m \choose 2^n}$ bits (all logarithms are base 2).

By Stirling's approximation:

$$\begin{eqnarray\*}& & \log { 2^m \choose 2^n} \\ & = & \log \left(2^m\right)! - \log \left(2^n\right)! - \log \left(2^m - 2^n\right)! \\ & = & \left( m 2^m - 2^m \log e\right) - \left(n 2^n - 2^n \log e\right) - \left( (2^m - 2^n) \log \left( 2^m - 2^n \right) - (2^m - 2^n) \log e \right) + O(m) \\ & = & m 2^m - n 2^n - (2^m - 2^n) \log \left( 2^m - 2^n \right) + O(m) \\ & = & m 2^m - n 2^n - (2^m - 2^n) \left( n + \log (2^{m-n} - 1) \right) + O(m) \\ & = & m 2^m - n 2^n - (2^m - 2^n) ( n + m - n ) + O(m) \\ & = & (m - n) 2^n + O(m) \end{eqnarray\*}$$

The second-last step introduces the assumption that $2^m \gg 2^n$, so $\log(2^{m-n}-1) = m - n + O(m)$.

In other words, the minimum number of bits required is, under these assumptions, exactly the same as storing $2^n$ records of $m-n$ bits each! So the only overhead required is whatever is needed to maintain the structure of the hash table itself (e.g. the overhead of storing multiple records in a bucket).

If this were a minimal perfect hash function, or a low-overhead technique such as cuckoo hashing, this representation is asymptotically optimal.

# Answer
> 0 votes
It makes the hash table unusable if I can’t have x and yz and abc as keys.

---
Tags: hash-tables
---


# Question
Title: Linear algorithm for off-line minimum problem
I've been reading a paper "A Linear Time Algorithm for Maximum Matchings in Convex, Bipartite Graphs" by Steiner and Yeomans. In this paper at some point they solve an off-line minimum problem that is stated as follows:

You are given an empty set $S$ and a sequence of $n$ $\textrm{INSERT}(i)$ and $m$ $\textrm{EXTRACT-MIN}$ calls. $\textrm{INSERT}(i)$ will insert a number no greater than $n$ into the $S$ (I think we can even claim that each number is inserted exactly once). And $\textrm{EXTRACT-MIN}$ will find minimum element from the $S$, delete it from the $S$ and return it. The problem is to determine sequence of results of $\textrm{EXTRACT-MIN}$ calls.

Paper authors don't provide an algorithm implementation for this problem and claim that this problem can be solved in $O(n)$ by referencing "Data Structures and Network Algorithms" by Tarjan.

I haven't found any mentions of off-line minimum problem in this book and all references I found on the internet reference a problem from "Introduction to Algorithms" by Cormen et al. But this problem is suggested to be solved using a disjoint-set data structure, which leads to $O(n\alpha(n))$ amortized complexity, which is clearly not $O(n)$ worst-case.

So my question: is there really a $O(n)$ algorithm for this problem or is it a some mistake in the paper?

# Answer
> 2 votes
The paper "A linear-time algorithm for a special case of disjoint set union" (1983) by Gabow and Tarjan gives an $O(m+n)$ time algorithm to process $m$ union and find operations on $n$ elements, under the condition that the *union tree* is given as well. The union tree is a rooted tree where the vertices initially are labelled with the individual elements, and the union operations replace two adjacent vertices by a single vertex with the set union as its label, contracting the edge.

Note that in the algorithm of exercise in Cormen et al. you mention (as well as the algorithm from the book referenced in the Gabow and Tarjan paper), the union operations are described by a union tree where each initial set has an edge to its predecessor and successor in the sequence of extract-min/insert operations. This means we can apply the algorithm from Gabow and Tarjan to perform the union-find operations in the offline-min algorithm, and obtain an algorithm that runs in linear time.

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


# Question
Title: Why is encrypting with the same one-time-pad not good?
To encrypt a message $m\_1$ with a one-time-pad key $k$ you do $Enc(m\_1,k) = m\_1 \oplus k$.

If you use the same $k$ to encrypt a different message $m\_2$ you get $Enc(m\_2,k) = m\_2 \oplus k$, and if you perform Xor of the two ciphertext you get $$( m\_1 \oplus k) \oplus ( m\_2 \oplus k) = m\_1 \oplus m\_2$$

so, OK, there is some information leakage becuse you learn $m\_1 \oplus m\_2$, but why is it not secure? I have no way to learn (say) $m\_1$ unless I know $m\_2$. So why is it wrong to use $k$ twice??

# Answer
> 19 votes
> I have no way to learn (say) $m\_1$ unless I know $m\_2$.

That is exactly the problem - if you re-use the same key, and someone has access to one message you encrypted in both plaintext and encrypted form, they can use that to find your key: $$ (m\_2 \oplus k) \oplus m\_2 = k $$

As an alternative scenario, if you use the same key over and over, the attackers may be able to guess just pieces of various encrypted message, and each successful guess reveals a piece of the key $k$, so that over time more and more of the key is revealed.

This general strategy for breaking a cryptosystem is known as a known plaintext attack. Many systems, like AES and RSA, are believed to be secure against these attacks. But a one-time pad becomes completely insecure against them unless a new pad is used for every encryption, which is why they are named "one-time pads".

# Answer
> 13 votes
It's insecure precisely due to the reason you mention - there is some information leakage.

Basically, if you have any assumptions about plaintexts (english text, files with known structure, etc), it leads to an easy statistical analysis. Probably using it **twice** doesn't change the practicality of the attack significantly, but using it many times with a non-random plaintext, eventually reveals enough information to recover the key.

Finally, if you have the ability to use it only **twice**, you also have the ability to use it only **once** \- the restriction is that these one-time-pads are not to be used potentially unknown and over time, damaging number of times.

At one extreme, if you're aware (known plain-text) that the $m\_1$ is just a null-string of the length of the pad, you have handed the attacker the key prior to computing $m\_2$.

Known plain-text attacks are fairly common, it's reasonably easy to coerce an encryption mechanism to encrypt something you know a-priori. If not, you can usually make reasonable statistical assumptions.

# Answer
> 6 votes
Suppose you use a one-time pad with English text, and you use it twice. Now, you can get $(m\_1 \oplus k) \oplus (m\_2 \oplus k) = m\_1 \oplus m\_2$.

English text has an entropy of something like 1.3 bits per letter. The XOR of two messages has 2.6 bits per letter. There are 26 letters in the alphabet, so this gives $\log\_2 26 = 4.7$ bits per letter. This means that, even if you take the XOR of two English texts, there is still theoretically enough information to decode both of these texts. Furthermore, I am pretty sure that I have read that cryptanalysts are able to do it in practice.

If you want to use a one-time pad twice, you need to compress your message first. And even then, if you don't use a nearly-perfect compression algorithm, and you use the one-time pad multiple times, there will be enough entropy left to theoretically recover the messages. I don't know how hard it would be in practice.

# Answer
> 5 votes
The thing is that even if you know nothing about $m\_1$ and $m\_2$, you might be able to recover them both from $m\_1 \oplus m\_2$.

Actually, for many cases, it is very simple. Here's a simple visualization.

# Answer
> 3 votes
Here's an intuitive way of representing the approach without recourse to mathematics. Let's say you have two encrypted messages which have been encrypted by the same one time pad.

1. Make a guess at a word or phrase that may be contained in one of the messages. Let's say the phrase "Weather report"
2. Starting with message 1, assume that "Weather Report" occurs at the first letter position.
3. Back-calculate the first 14 characters of the one time pad.
4. Decrypt the first 14 characters of the message 2 using the back-calculated OTP.
5. If the plaintext looks like gobble-di-gook, then go back to step 2 and repeat at the 2nd letter position. However, if you get meaningful text (for example "Good Morning I" then congratulations, you've worked out the first 14 characters of the OTP (and the first 14 characters of each letter)
6. If you get to the end of message 1 without throwing up anything other than random letters, then you can conclude that the phrase "Weather Report" does not occur in message 1. Go back to step 1 with a different phrase such as "Dear Colonel"

# Answer
> 0 votes
When you use a one-time pad, we assume that your one-time pad contains perfectly random numbers, so the encrypted message is also perfectly random, with no way whatsoever to crack it.

But if you encrypt two messages with the same pad, the result is the xor of two very non-random messages. So that alone gives an attacker something to work with. A bad case is having one short message that was first padded by adding xxxxx; in that case we can easily decrypt the end of the second, longer message.

And the big risk is that someone discovers one of the two messages. Say a message is really sensitive until tomorrow 12am, and after that time nobody cares anymore. For example, in combat a message when and where an enemy position will be attacked - after the attack, it's not a secret anymore. So the enemy could get the second message because it's not secret anymore, and then the first message is easily decrypted.

---
Tags: cryptography, information-theory, encryption
---


# Question
Title: Is the problem of Proper Subset of decidable languages decidable?
Given 2 recursive - decidable languages $L\_1$ and $L\_2$ is the problem $L\_1 \subset L\_2$ solvable - decidable?

Since both $L\_1$ and $L\_2$ are recursive - decidable there exist Turing Machines say $M\_1$ and $M\_2$ that decide them.

Say that the problem stated is decidable then there exists a Turing Machine $M\_3$ that given two deciders $M\_i$ and $M\_j$ responds with **YES** if $L(M\_i) \subset L(M\_j)$ otherwise it responds with **NO**.

If $M\_3$ actually exists then there exists a Turing machine say $M\_4$ that decides the Halting Problem and works in the following way:

* Given $\langle M,w\rangle$ it constructs the description of a Turing Machine $M^\*$ that given any input $x$ it erases $x$ from its tape, then writes $w$ on it and simulates $M$ on $w$. If $M$ halts on $w$ then $M^\*$ responds with **YES** and $L(M^\*) = Σ^\*$ otherwise it loops infinitely as $M$ loops on $w$ and $L(M^\*) = \emptyset$.
* Then it constructs the description of a Turing Machine say $M^o$ such that $L(M^o) = Σ^\*$
* Next step is to feed $\langle M^\*,M^o\rangle$ to $M\_3$:

+ If $M\_3$ responds with **YES** then $L(M^\*) \subset L(M^o)$ so $M$ does not halt on $w$ and $M\_4$ responds with **NO**.
    + If $M\_3$ responds with **NO** then $L(M^\*) \not\subset L(M^o)$ so $M$ halts on $w$ and $M\_4$ responds with **YES**.

This is how I approached the problem but my concern is that the way $M^\*$ works does not make it a decider as it may loop forever. Is there any way that I can modify my approach and make it work?

# Answer
> 1 votes
The following is a modification of your approach that works.

The idea is to construct language $L\_1$ so that it is not empty if and only if the given $M$ halts on the given $w$. Then use $M\_3$ to check whether $L\_1$ is empty.

As in the question, a Turing machine responds with **YES** or **NO** means it accepts or rejects respectively. A language is decidable when a decider for it is given. "$\subset$" means "is a proper subset of".

---

Let $D$ be a Turing machine that decides given decidable language $L\_1$ and $L\_2$ whether $L\_1\subset L\_2$.

Given $\langle M,w\rangle$, Turing machine $M\_6$ will do the following.

1. It constructs Turing machine $H$ which on input $x$:

1. Counts the number of symbols in $x$. Let it be $n$.
    2. Simulates $M$ on input $w$ up to $n$ steps. If the simulation halts within $n$ steps, accepts. Otherwise, rejects.

Note that $H$ is a decider. $L(H)$ is empty iff $M$ does not halt on input $w$.
2. It feeds $\langle L(H), \\{\epsilon\\}\rangle$ to $D$. Note that $\\{\epsilon\\}$ is a decidable language.

* If $D$ responds with **YES**, then $L(H) \subset L(E)$, which means $L(H)$ is empty, which means $M$ does not halt on $w$. It responds with **NO**.
    * If $D$ responds with **NO**, then $L(H) \not\subset L(E)$, which means $L(H)$ is not empty, which means $M$ halts on $w$. It responds with **YES**.

$M\_6$ is a decider for the halting problem.

---

The approach above uses $D$ only to decide whether a given decidable language is empty or not. Hence, we have proved, in fact, it is undecidable whether a given decidable language is empty or not.

---

Here is an exercise, which is another stronger form of the exercise in the question.

Is it decidable whether $\\{a^n\mid n\in\Bbb N\\}\subset L\_2$ where $L\_2$ is a decidable language $L\_2$ over an alphabet that has $a$ and $b$?

---
Tags: formal-languages, turing-machines, undecidability, halting-problem
---


# Question
Title: Is this grammar LL(1) and what is it's parsing table?
Let G be a grammar with non-terminal `A`, terminal `a` and these productions:

```
A -> A a

```

It is obvious that this grammar cannot be parsed. There is no way to "exit" the parsing process. However, I am not sure at what point I would determine the `LL(1)` property.

Let's first look at the `FIRST` set for `A`. By looking at our rule, `FIRST(A)` must contain `FIRST(A)`. It does not contain any terminals and it doesn't contain epsilon. Therefore I believe it should be the empty set. Now for the set `FOLLOW(A)`. With `#` being the terminator symbol, and `A` being our "entry point", `FOLLOW(A)` must contain `#`. As the non-terminal `A` is followed by `a` in our rule, `FOLLOW(A) = {#, a}`.

Now for building the parsing table:

For our rule, we examine `FIRST(A a)` which is the empty set, as `FIRST(A)` does not contain epsilon. We don't add anything to the parsing table. Now, if `FIRST(A a)` contains epsilon (which it does not), we examine the set `FOLLOW(A)`. We skip this step, and are left with an empty parsing table.

It is clear that an empty parsing table would reject every input, leading me to believe the grammar must be "invalid". However, as I understand it, the `LL(1)` property is still fulfilled.

Is this correct, or is this grammar not `LL(1)` for some other reason? Can I conclude that having empty `FIRST` sets leads to unparsable grammars in general?

# Answer
> 1 votes
From wikipedia

> A formal grammar that contains left recursion cannot be parsed by a LL(k)-parser or other naive recursive descent parser unless it is converted to a weakly equivalent right-recursive form

---
Tags: formal-grammars, parsers
---


title: How efficient is register renaming?

text:
# Question
Title: How efficient is register renaming?
As I understand, all modern CPUs perform register renaming: given a sequence of instructions to interpret, they check which registers these instructions use, detect patterns where a register's previous value is overwritten, and then map the instruction sequence so that each instruction's "architectural" register is mapped to a physical register address in the register file.

My question is: **How much overhead does this process add?**

Register renaming allows the CPU to have many more registers than the encoding allows, and to better detect independent instructions that can be executed in parallel. And, okay, better instruction-level parallelism means faster execution, especially for high-latency operations like loads.

But to perform the algorithm I described, you basically have to do register allocation in the CPU, right? You have to dynamically allocate register indices, analyze the code to detect live ranges, maybe do some alias analysis if you also want to include spilled registers, etc. The idea that you can do all this work and still come out ahead just seems counter-intuitive to me.

Do CPU-makers just have some extremely efficient heuristics for JIT register allocation? Or is it a case of "this is extremely expensive to do, but even high overhead is worth it if we can get just a few more instructions per second for a given core"?

# Answer
> 1 votes
> How much overhead does this process add?

The process is nowhere near as bad as you made it out to be, more on that next, but there is a more general misconception that I think underlies this question: it presumes that "taking time" while processing an instruction adds overall overhead. That is mostly not the case, as making a pipeline longer affects primarily branch mispredictions (and other restarts) but not the throughput under normal conditions, and usually not even the latency of individual instructions (unless it's a specific part of the pipeline that got longer). Making the pipeline longer is not *free*, but the cost shows up only in limited circumstances, not everywhere all the time.

> But to perform the algorithm I described, you basically have to do register allocation in the CPU, right?

Yes, but since this happens *as the code is running* we have some advantages. For example, we do not need to come up with register names that would be valid statically. We're not statically rewriting the code. It's more like this:

* Decode an instruction.
* For every source operand, replace it with the newest physical register corresponding to that ISA-level register.
* Allocate a physical register the destination operand, update the rename map accordingly.

There is no analysis of arbitrary blocks of code as a whole, it's nothing like what a compiler does, renaming is local, perhaps myopic.. But that's not a limitation, it's actually better that way: this allows a destination to be renamed differently across different iterations of a loop, enabling parallelism across the iterations of the loop. Renaming multiple instructions at once involves something that you might call analysis of the code, but only of a limited number instructions (eg 4, or however wide the renamer is) and only in a local context to "chain" the new name of a destination into the operands of the next instructions that are renamed within the same cycle.

Allocating a register is not a super heavy operation, the "free list" might be represented as a bitvector of available physical registers (with one pulled out using a priority decoder) or as a circular array (small RAM and two indices), either way it's not that big of a deal. Back in university I went with the bitvector approach, it seems that RISCV-BOOM does as well, such low level details are fairly scarce though.

Freeing physical registers can in the simplest case be done based on this principle: when the destination of an instruction is renamed, also record with it the *previous* name of the destination register. When this instruction retires, that previous name can be freed, since it corresponds to a register that no newer instruction can read (all newer instructions would read the *new* name). Back in university, that is the technique I used, and it seems that BOOM does too.

In practice there are several reasons why more complicated techniques are used. The register reclamation algorithm that I sketched is extremely conservative (there are more aggressive techniques), and does not work if multiple ISA-level registers can be renamed to the same physical register (which happens as a result of move-elimination aka zero-latency copying, and as a result of memory bypassing). You can read about some more advanced techniques in eg "Cost Effective Physical Register Sharing".

I'm not sure how reasonable it is to compare a modern pipeline with a hypothetical variant of that pipeline sans renaming (since that invalidates the design), but if I do it anyway, it may add a couple of stages:

* Maybe a front-end stage specifically for Rename, but it depends. There should be some tendency towards extra front-end stages on average, since it adds logic, but whether that results in an extra stage depends on the specifics of the design. It may be possible to spread the renaming logic over stages that were already present (decode, enqueue-to-backend).
* Maybe an extra back-end stage to read from an increasingly large physical register file. The bigger it is, the longer that will take. In the classic RISC pipeline there was no separate "register read" stage, but at least one separate stage for that is present in many modern pipelines. Note that even *here*, adding an extra pipeline stage is still not free but it also does not make instructions slower as such. The extra steps between the reservation station(s) and the actual execution units means that the "wakeup" logic has to(if we want dependent instructions to be able to execute back-to-back, and I do, because lacking that ability *would* actually add overhead to many instructions) wake up (make available for select/issue) instructions some cycles *before* its operands are available (in contrast with the classic Tomasulo algorithm where we wait until the operands have been broadcasted over the result bus), which is less bad than it looks since most instructions have a known fixed latency (so we can predict when their result will be available), but certainly an extra source of complications.

So to recap:

> How much overhead does this process add?

I still don't know exactly how to answer that, but it's not as bad you probably thought.

# Answer
> 0 votes
Remapping registers costs zero time. It can be done easily while moving an instruction into the dispatch queue, so whatever time it takes is hidden. For example "R3 = R7 + R11", we lookup that R7 is currently held in RR65, R11 is currently held in RR43, RR113 is free so from now on RR113 will hold R3, and the instruction "RR113 = RR65 + RR43" is stored in the dispatch queue.

All you do is having *many* rename registers, and using whatever is free right now. There is no need for any clever register allocation algorithm.

And it should be obvious that you can't do out-of-order processing without rename registers. It's not "a few more instructions per second", having no rename registers would be a total disaster and absolutely kill performance. Take this sequence:

```
R1 = R2 / R3
Store R1 at address 2000
R1 = R4 + R5

```

Without rename registers, the third instruction would have to wait (needlessly) for the second one to finish. Which means it would have to wait for the slow division to finish.

---
Tags: computer-architecture, cpu, cpu-pipelines
---


title: Finite State Machine without recursion

text:
# Question
Title: Finite State Machine without recursion
I have found utility in state machines that do not have the complexity of recursion: no self or ancestral transitions.

Is there a name for this sub-category of FSMs? Are they commonly used or considered broadly useful?

# Answer
Decision trees \[1\] are a class of hierarchical control structures that might be what you are looking for.

\[1\] Decision tree in Wikipedia, https://en.wikipedia.org/wiki/Decision\_tree
> 3 votes

---
Tags: finite-automata, terminology
---


# Question
Title: The language of all machines that accepts strings of even length
I have difficulties in proving that for the given language:

$E V E N\_{T M}=\\{\langle M\rangle: M$ is a TM s.t. $|w|$ is even for all $w \in L(M)\\}$.

prove that: $E V E N\_{T M} \in coRE$

I've tried to look at $(E V E N\_{T M})^\complement$ and prove that :

$(E V E N\_{T M})^\complement \in RE$

by building TM M', that will simulate M on words ordered by MINLEX order from $\sum^\*$:

```
 -if M accepts W ,M' check if w has odd length. if it has , M' accepts, otherwise M' continues
   to the next word

  -if M rejects W, and w has odd length, M' accepts, otherwise rejects

  -if M doesn't stop, M' doesn't stop

```

Is it a right direction for solving this?

# Answer
> 1 votes
The trick required to construct the TM for $(EVEN\_{TM})^C$ is that a TM can simulate finitely many TMs in each step, like so:

```
L = []
for word w with |w| odd:
    start simulation of M on w
    add the simulation to L
    for each simulation S in L:
        simulate S one more step
        if S halts and accepts: accept
        if S halts and rejects:
            remove S from L

```

Here $\langle M \rangle$ is ofc the string whose membership we want to test. If an odd length word exists and $w \in L(M)$ than this algorithm will encounter it at some point and start a simulation of $M$ on $w$ and since this simulation steps forward on every succinct iteration, at some point it will halt and our machine will terminate. If no such word exists, it will just loop forever.

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


# Question
Title: Does there exist a Reed-Solomon-like code over decimal symbols?
A Reed-Solomon error-correcting code consisting of N symbols is guaranteed to detect up to N single-symbol replacements in an arbitrarily long input plus the ECC itself, and is also guaranteed to correct up to floor(N/2) single-symbol replacements in the same.

I can't claim to understand the math behind Reed-Solomon ECC, but I notice that all the implementations I could find operate on symbols in base 16, 64 or 256. This seems to suggest that 1024 etc. are also bases in which this scheme can operate with the right polynomial.

Is it possible to have an ECC scheme with exactly the above properties that operates on decimal symbols? Can Reed-Solomon be trivially adapted for this purpose?

(this question is prompted by my answer to a puzzling.SE question)

# Answer
> 5 votes
The property of Reed–Solomon codes that you mention is known as Maximum Distance Separability, and codes with this property are known as MDS codes. In coding theory the most popular type of code is a linear code, and these are only defined over alphabets which are prime powers. However, in the literature you can find some papers on MDS codes on arbitrary alphabets; I'll let you research that yourself.

For the specific case $N=1$, there is a very simple MDS code, namely checksum: you add to the original data a new digit whose value is the negated sum of the other digits (so that all new digits sum to zero). This code can detect any single error.

# Answer
> 2 votes
One implementation in Python is available here:
Decimal Reed-Solomon implementation

See also the article:
Reed-Solomon using decimal numbers

---
Tags: error-correcting-codes
---


# Question
Title: What's the difference between "convex/non-convex optimization" and "quadratic programming"?
I'd like to start by clarifying I'm by no means an expert in any of this, so take everything I say with a grain of salt.

Convex and Non-convex Optimization are subfields of mathematical optimization that focus on minimising convex and non-convex functions respectively. That is, finding the global minimum of functions with one or multiple minima.

Quadratic programming is *also* a subfield of mathematical optimization that *also* focuses on minimising convex and non-convex functions.

Convex and Non-convex Optimization seem to focus on quadratic functions, Quadratic programming *also* focuses on quadratic functions.

I do understand the difference between convex and non-convex optimization, but I'm having trouble understanding how quadratic programming fits into all of this.

I tried Googling my question in several different ways with no luck. I searched this website and it seems this question has never been asked before.

Is there an area of mathematical optimisation that quadratic programming doesn't cover? If there is, I can't seem to find a single example. If there isn't, it seems very odd to me that quadratic programming is differentiated enough that it has a completely separate name and Wikipedia page.

# Answer
> 0 votes
No, quadratic programming does not cover all optimization problems. Quadratic programming is limited to the case where the objective function is quadratic and the constraints are linear functions.

If you have an optimization function where the objective function is not quadratic (maybe it is cubic, or maybe it is some other complicated function), or the constraints are not linear functions (maybe they are quadratic or some complicated function), then that is not an instance of quadratic programming.

There are convex/non-convex functions that are neither quadratic nor linear.

---
Tags: optimization, terminology, quadratic-programming
---


# Question
Title: Prove (p → ¬q) is equivalent to ¬(p ∧ q)
I need to prove the above sequent using natural deduction. I did the first half already i.e. I proved $(p\rightarrow\neg q)\rightarrow \neg (p \wedge q)$, but I'm stuck on where to start for the reverse i.e. proving $\neg (p \wedge q) \rightarrow (p\rightarrow\neg q)$. I figured I would start by assuming $\neg (p \rightarrow \neg q)$ and then working towards a contradiction, but I'm still at a dead end. Can someone point me in the right direction? Thanks.

# Answer
Can we use that $a \to b$ is same as $\neg a \lor b$? If yes then: $$\neg (p \wedge q) \rightarrow (p\rightarrow\neg q) $$ is same as $$(\neg p \lor \neg p) \rightarrow (\neg p \lor \neg q) $$
> 0 votes

# Answer
As a hint, note that $\neg p$ means $p \rightarrow \hbox{False}$. (In some logics, this is the definition of negation.)

Therefore $\neg (p \wedge q) \leftrightarrow (p \rightarrow \neg q)$ means: $$\left( \left(p \wedge q\right) \rightarrow \hbox{False} \right)\leftrightarrow \left(p \rightarrow q \rightarrow \hbox{False}\right)$$

This is just Currying.
> 0 votes

# Answer
One of the ways is this:

LHS

We already know that

(→¬) = (¬ + ¬)

RHS

By demorgan's law,

¬(∧) = (¬ + ¬)

Since LHS and RHS are same, so they are equivalent.
> 0 votes

# Answer
Here is a proof tree in natural deduction of the wanted implication, using $\Gamma = \\{\neg(p\land q), p , q\\}$:

$$\dfrac{ \dfrac{ \dfrac{ \dfrac{ \dfrac{ \dfrac{}{\Gamma\vdash p}\text{ax} \quad \dfrac{}{\Gamma\vdash q}\text{ax} }{\Gamma\vdash p\land q}\land\_i \quad\dfrac{}{\Gamma\vdash \neg(p\land q)}\text{ax} }{\Gamma\vdash \bot}\neg\_e }{\neg(p\land q), p\vdash \neg q}\neg\_i }{\neg(p\land q)\vdash p\rightarrow \neg q}\rightarrow\_i }{\vdash \neg(p\land q)\rightarrow (p \rightarrow \neg q)}\rightarrow\_i$$

Sorry the layout is a bit ugly without appropriate LaTeX packages.
> 0 votes

---
Tags: proof-techniques, propositional-logic, natural-deduction
---


# Question
Title: Partition a graph into connected subgraphs of 3 vertices each
We need to partition a graph into subgraphs of 3 vertices each, such that every subgraph has at least 2 edges.

The problem is similar to the partition into triangles problem (which is NP-complete) but not the same because each subgraphs may contain 2 or 3 edges (unlike the triangles problem, which requires 3 edges in each subgraph).

Is there a polynomial-time algorithm for this problem?

# Answer
> 1 votes
The problem can be equivalently stated as follows:

*Can a graph be partitioned into vertex disjoint paths of lengths $3$*?

The problem is shown to be $\mathsf{NP}$-hard (see Theorem 1 here).

Note that the proof is given for $k$-partition problem. However, it holds for your problem as well. In the proof, the partitions must contain $3$ vertices; note the following statement written in the proof: "We claim that $S'$ can be partitioned into members of $C$ if and only if $G$ can be partitioned into $p = p' + 3q'$ paths of length at most $3$. Since $|V| = 3p$, if $G$ can be partitioned into $p$ paths of length at most $3$, then each of these paths must have exactly $3$ vertices on it."

---
Tags: graphs, partitions
---


title: Can RadixSort be Ω(n log n)?

text:
# Question
Title: Can RadixSort be Ω(n log n)?
I read about RadixSort and its time complexity and the worst best and average time Complexity is O(n) , so my question is can radixSort be Ω(n log n)?

# Answer
The more accurate time complexity analysis for Radixsort gives time complexity as $O(kn)$-time where $k$ is number of digits, or keys (radix is defined as the base by which digits or keys are formed, hence the name radix sort).

For example, if you are given numbers 1 to $n$ in an unsorted list, then radix-sort will do the sorting in $O(n\log n)$ time.

So, radixsort can be $\Omega(n\log n)$ if you have $\Omega(\log n)$ digits in the numbers you are sorting.

See https://en.wikipedia.org/wiki/Radix\_sort.
> 6 votes

# Answer
If radix sort is implemented using counting sort as the auxiliary stable sort the analysis is as follows. Let $n$ be the numbers to be sorted, $d$ the number of digits in each input number and let the range of the digits be $0,1,\cdots,k$. Then the worst case running time is $O(d (n+k))$, so that when $k = O(n)$ the complexity is $O(dn)$. Assuming $d=O(1)$ the complexity is linear.

However the impact of the base used must be taken into account. Assume for instance that you want to sort $n$ base-10 numbers in the range $0,1,\cdots,R$. Then, the number of digits is $d = \lfloor \lg\_{10} R \rfloor + 1$ and the auxiliary storage array will need space for 10 cells. In each iteration you need to insert $n$ numbers into the 10 cells, so that the complexity is $O(n)$. The running time, in total, will be $O(dn) = O(\lg R \ n)$. Therefore when $n \approx R$ the complexity will be $O(R \lg R)$. This show that sorting using base-10 does not work for radix sort. Depending on the base used, the running time may even be bigger than $\Omega(n \ \lg n)$, e.g. it may be $\Omega(n^2)$.
> 0 votes

---
Tags: algorithm-analysis
---


title: Finding MST after adding a new vertex

text:
# Question
Title: Finding MST after adding a new vertex
> Let $G=(V,E)$ which is undirected and simple. We also have $T$, an MST of $G$. We add a vertex $v$ to the graph and connect it with weighted edges to *some* of the vertices. Find a new MST for the new graph in $O(|V|\cdot \log |V|)$.

Basically, the idea is using *Prim* algorithm, only putting in priority-queue the edges of $T$ plus the new edges.

I don't fully understand the reason it works. Why it has to be a minimum spanning tree? What about a case where the heaviest edge in $T$ is $9$ for example, and we have other edges in the graph (And not in $T$) with the same weight?

It was also claimed that $|V|-1$ of the edges must be from the old graph and the other one will be one of the new - I'm not sure it's even correct. What do you think?

# Answer
As stated in your post, the idea is to use Prim's algorithm with only the edges from $T$ and the new edges, let's call them $E'$.

For the sake of simplicity, let's assume that $T$ is the unique MST. (This is not required, but it is easier to reason about correctness in this case.)

Now think about what would happen if we ran Prim's on the full graph after the new vertex and edges had been added. We would start with an arbitrary single vertex and successively add edges that are adjacent to the growing tree.

Here's the key idea: each edge that is added by Prim's on the full graph will either belong to $T$, or to $E'$. If at some step we tried to add an edge in $E$ but not in $T$, then $T$ would not be a (unique) MST.

Since we know that regular Prim's would only add edges from $E'$ and $T$, these are the only edges that need to be added to the priority queue.

As Hendrick Jan said in comments, it is certainly not the case that $|V|-1$ of the edges must be from the old graph, for all of the new edges may be less than the minimum weight edge in the old graph, in which case the MST would include all of the edges in $E'$.
> 6 votes

# Answer
(This is a copy of the answer to the same question on the general StackOverflow)

There exist algorithms that can add a vertex with all its edges to a graph with a known MST in linear time, which is faster than Prim or Kruskal. Probably the most neat algorithm proposed in the paper below \[1\] uses just one cleverly designed DFS call. It is strange that people do not know this algorithm, although it can be explained by its date: it was proposed long before both Prim and Kruskal.

That algorithm is based on an observation that the new MST shall consist of edges that either belong to the old MST or are adjacent to the newly inserted vertex (let's denote it *z* as in the cited paper). Furthermore, it constructs the new MST recursively while performing a depth-first search on the old MST. So its running time is proportional to the number of edges in the old MST, plus the number of edges adjacent to *z*, hence O(n). The way it does it is detailed below.

* While traversing the old MST, the algorithm writes out the edges that definitely belong to the new MST.
* When exiting a vertex *w*, the algorithm has written out all the edges that belong to an MST of the subtree of *w* plus the vertex *z*, except its heaviest edge. The fate of this heaviest edge is to be determined later, because the subtree may be connected to the rest of the graph either via *z* or via some old edge - so the algorithm returns this heaviest edge from the call to DFS.
* To process a *w*, it starts by adding the edge *wz* to the graph, but as it is also the heaviest edge at that moment, it is not yet written out, but kept in a separate variable *t*. Then it iterates over the children of of *w*, if any, and runs DFS recursively on each of them. Let the current child be *r*, and let the DFS call on it return an edge *t'*. One of *rw* and *t'* has to be in the final MST - otherwise some of the vertices in the subtree of *r* will never get connected - so the cheapest one gets written out. The heaviest one may still survive, but first it needs to compete with *t*: it replaces *t* only if *t* is heavier, otherwise keeping *t* is better. Then the algorithm continues with the next child, or, if there are no more children, returns *t*.
* When the algorithm exits from the root vertex of the old MST, there is no other choice than to add the just-returned edge to the new MST, thus completing the run.

Using Python as pseudocode, the algorithm can be written down as follows:

```
def update_mst(w, z):
    visited(w) = True
    t = edge(w, z)
    for r in old_mst_adjacent(w):
        if not visited(r):
            tt = update_mst(r, z)
            rw = edge(r, w)
            if cost(rw) < cost(tt):
                add_to_new_mst(rw)
                t = min(t, tt)
            else:
                add_to_new_mst(tt)
                t = min(t, rw)
    return t

```

Note that \[1\] uses a global variable instead of returning the heaviest edge from the recursive call, but the presented way is, I think, somewhat cleaner to the modern programmers.

\[1\] Francis Chin and David Houck. 1978. Algorithms for Updating Minimal Spanning Trees. J. Comput. System Sci. 16 (1978), 333–344.
> 1 votes

---
Tags: spanning-trees, minimum-spanning-tree, prims-algorithm
---


# Question
Title: Context-sensitive grammar for function calls
Say we have context-free grammar for function declarations and calls (C-style)

```
START = DECLLIST CALLLIST
DECLLIST = FDECL DECLLIST | FDECL
CALLLIST = FCALL CALLLIST | FCALL

FDECL ::= fname lbrac TARGS rbrac semicolon
TARGS ::= TARGFST TARGSREM
TARGFST ::= type name
TARGSREM ::= comma type name | comma type name TARGSREM

FCALL ::= fname lbrac ARGS rbrac semicolon
ARGS ::= ARGFST ARGSREM
ARGFST ::= name
ARGSREM ::= comma name | comma name ARGSREM

```

Non-terminal in uppercase.

Example is:

```
foo(int x, int y);
bar(int x);
foo(x, y);
bar(x, y); // shall be recognized an error but not in CFG

```

Now I want to amend this with context-sensitive rule: any function call need the same number of arguments as its declaration. I understand this will cost me some context-sensitive productions with two or more non-terminals on the left.

This will yield a context-sensitive grammar for decls and calls.

I need some ideas how to build this grammar.

# Answer
As far as I can determine by looking for examples with Google, the answer seems to be: it can be done, but please don't.

Regarding context-sensitive rules, Chomsky wrote: *Rules of this kind are quite common in actual grammatical description* (on p. 363 of: Handbook Of Mathematical Psychology Volume II, Chapter 6). What sort of rule did he have in mind? Have context-sensitive grammars actually been applied to the description of languages? I haven't been able to locate any examples.

To see how it can be done, look at how to generate the language $\\{ a^nb^nc^n \mid n \in \mathbb{N} \\}$, e.g. in Wikipedia, and adapt the same technique to your use case.

The approach to generating $\\{ a^nb^nc^n \mid n \in \mathbb{N} \\}$ is some variation of this:

* Use context-free rules to generate the right amounts of elements without trying to get the order right:

$ S \rightarrow \epsilon \\ S \rightarrow aSBC $
* Use noncontracting rules to shift elements into position to get the order right:

$CB \rightarrow BC$
* Replace the shifted elements with terminals:

$aB \rightarrow ab \\ bB \rightarrow bb \\ bC \rightarrow bc \\ cC \rightarrow cc$

We now have a noncontracting grammar, so

* Use the standard technique for replacing noncontracting rules with context-sensitive rules:

$CB \rightarrow BC$ becomes

$CB \rightarrow CZ \\ CZ \rightarrow WZ \\ WZ \rightarrow WC \\ WC \rightarrow BC$

Done.

The same approach can be applied to your use case: generate the function definitions and applications together, then shift the applications into place.

The problem is that this is quite convoluted. We really want to just match up the signatures of function definitions and their applications; we don't want to generate things out of order and then have rules to gradually shift them into place. It's unnatural and quite hard to read.

The next problem is that with context-sensitive or noncontracting grammars, we can't do any better. The only way to guarantee equality of numbers of $a$s, $b$s and $c$s is to make sure they are generated "at the same time", which can only be done by generating them out of order, which means the shifting is inevitable. (Clearly, this is not a formal proof.)

So the next problem is: if context-sensitive grammars do not provide a natural way of expressing this sort of constraint, what sort of grammar can we use instead?

Well, let's go back to where Chomsky got his idea of context-free grammars: grammars of natural languages, as they have been used in teaching languages for at least the past 2500 years. In such grammars, nonterminals have grammatical features. For instance, in European languages such as English and Russian, noun phrases and verb phrases have the features *number* (singular, plural, etc.) and *gender* (masculine, feminine, etc.), and possibly more. We can then express agreement w.r.t. these features, e.g. subject-verb agreement w.r.t. number. Or, in your case, agreement of function signature between function definitions and their applications.

So we need attribute grammars, in which we can attach such features to nonterminals, and express such agreement.

Attribute grammars allow a direct, natural way to express these constraints. We can not only require the number of arguments of function calls to match up with the number in their definitions, we can also require their types to match up. We can even specify arbitrary type checking if we want to.

One approach to attribute grammars is Van Wijngaarden grammars, which not only allow attributes to be specified for nonterminals, but also completely formalize the manipulation of attribute values. A Van Wijngaarden grammar for $\\{ a^nb^nc^n \mid n \in \mathbb{N} \\}$:

```
S: A(n) B(n) C(n).

A():.
B():.
C():.

A(1n): a A(n).
B(1n): b B(n).
C(1n): c C(n).

n:: .
n:: 1 n.

```

The rules with `:` are the ordinary grammar rules. The attribute `n` has been added to the nonterminals to express the number of terminals to be generated.

The rules with `::` are the meta-rules. They specify the possible values of the attributes; in this case, of `n`.

In this notation, whitespace is insignificant. (Notation for Van Wijngaarden grammar varies.)

`1n` is the string `1` concatenated with the value of the attribute `n`. `n` is an attribute because it is a nonterminal in the meta-grammar.

The magic is in the requirement that within the same rule, different mentions of the same attribute must have the same value. As a consequence, in the first rule, the three different mentions of `n` must have the same value.

As promised, using the `n` attribute allows us to equate the numbers of $a$s, $b$s and $c$s directly, without having to do the symbol shifting required in noncontracting grammars.

In Van Wijngaarden grammars, all attribute values are strings and there are no predefined operations on them, except concatenation. As a result, for complex tasks, quite a large portion of the resulting grammar is dedicated to manipulating complex attribute values using pattern matching, which can look convoluted in its own way.

A Van Wijngaarden grammar for your use case:

```
START:
  DECLLIST(dl) CALLLIST(cl) match(dl with cl).

DECLLIST(dl1+dl2):
  FDECL(dl1) DECLLIST(dl2).
DECLLIST(dl):
  FDECL(dl).

CALLLIST(cl1+cl2):
  FCALL(cl1) CALLLIST(cl2).
CALLLIST(cl): FCALL(cl).

FDECL(name->targs):
  fname(name) lbrac TARGS(targs) rbrac semicolon.

TARGS(name->type,rem):
  TARGFST(name->type) TARGSREM(rem).

TARGFST(name->type):
  type(type) name(name).

TARGSREM(name->type):
  comma type(type) name(name).
TARGSREM(name->type,rem):
  comma type(type) name(name) TARGSREM(rem).

FCALL(name->args):
  fname(name) lbrac ARGS(args) rbrac semicolon.

ARGS(name->type,rem):
  ARGFST(name->type) ARGSREM(rem).

ARGFST(name->type):
  name(name->type).

ARGSREM(name->type,rem):
  comma name(name->type).
ARGSREM(name->type,rem):
  comma name(name->type) ARGSREM(rem).

match(name->targs with name->args):
  match_args(targs,args).

match(name->targs with name->args,rem2):
  match(rem1 with rem2)
  match_args(targs,args).
match(name->targs,rem1 with name->args,rem2):
  match(rem1 with rem2)
  match_args(targs,args).

match(name1->targs1,name1->targs1,rem1 with rem2):
  match(name1->targs1,rem1 with rem2).
match(rem1 with name1->args1,name1->args1,rem2):
  match(rem1 with name1->type1,rem2).

match(name1->targs1,name2->targs2,rem1 with name2->args1,name1->args2,rem2):
  match(name1->type1,name2->type2,rem1 with name1->type1,name2->type2,rem2).

match_args(name1->type with name2):.

match_args(name1->type,rem1 with name2,rem2):
  match_args(rem1 with rem2).

dl1:: dl.
dl2:: dl.
dl:: name->targs.
dl:: name->targs,dl.
targs::.
targs:: name->type,targs.
name:: letter.
name:: letter letterordigit.
letter:: a.
letter:: b.
[...]
letter:: z.
letterordigit: letter.
letterordigit: digit.
digit:: 0.
digit:: 1.
[...]
[...]

```

As you can see, the attributes accumulate all of the relevant information, essentially, data structures expressed in the form of parseable strings. The characters I've inserted, such as `+` and `->` and `with`, have no special significance, they are just characters being concatenated into strings with the values of the attributes. At the top level, in the first rule, we end up with the list `dl` of function declarations and the list `cl` of function calls. We can't just equate them; we have to allow for declarations without any calls (I suppose) and the lists may contain duplicates (I suppose) and may be in a completely different order.

That is what the `match` and `match_args` nonterminals take care of. They perform pattern matching, in the style of Prolog and functional programming languages such as Haskell.

Which leaves me with the final problem; why don't we all specify our grammars using Van Wijngaarden grammars, or some other form of attribute grammar, and instead, are still stuck with being taught the Chomsky hierarchy and limiting technology such as Yacc and ANTLR? Why do we insist on hiding away attribute manipulation within the parser's implementation?

The answer to that is a combination of technical objections, politics, and ignorance. But that is a story for another person and another time.
> 3 votes

# Answer
In a real compiler, normally we don't enforce this kind of rule in the grammar itself. Instead, we parse to a parse tree using a grammar that doesn't enforce this rule; and then we follow it up with a programmatic check on the parse tree to check whether it follows this rule (e.g., whether it obeys the type system, etc.).
> 1 votes

---
Tags: context-sensitive
---


# Question
Title: is the class NP closed under set difference?
I know P is closed under all Boolean operations, but what about NP?

is NP closed under set difference and symmetric difference?

is this table accurate?

Edit: updated table:

# Answer
> 2 votes
It is unknown whether $\mathsf{NP}$ is closed under set-difference.

If $\mathsf{NP}$ were known to be closed under set-difference then we would know that $\mathsf{NP} = \textsf{co-NP}$. Indeed, for $L \in \textsf{co-NP}$, $L = \Sigma^\* \setminus \overline{L}$ where $\overline{L} \in \textsf{NP}$ and hence $\textsf{co-NP} \subseteq \textsf{NP}$. Moreover, for $L \in \textsf{NP}$, $L = \Sigma^\* \setminus \overline{L}$ where $\overline{L} \in \textsf{co-NP} \subseteq \textsf{NP}$ and hence $\textsf{NP} \subseteq \textsf{co-NP}$.

On the other hand, if $\mathsf{NP}$ was known not to be closed under set-difference then we would know that $\mathsf{P} \neq \mathsf{NP}$ (since $\mathsf{P}$ is closed under set difference).

Regarding the symmetric difference, notice that $\Sigma^\* \\, \Delta \\, L = (\Sigma^\* \setminus L) \cup (L \setminus \Sigma^\*) = (\Sigma^\* \setminus L) \cup \emptyset = \Sigma^\* \setminus L = \overline{L}$.

---
Tags: complexity-theory, computability, np, closure-properties
---


title: Budgeted Independent Vertex Cover

text:
# Question
Title: Budgeted Independent Vertex Cover
Suppose that we are given a graph $G = (V,E)$ and a number $n$. The problem is to find an independent set $I$ with $|I| = n$, such that number of vertices covered by $I$ is maximized (that is, the number of vertices adjacent to at least on vertex from $I$). My question: suppose that this problem's name is $\tt{BIVC}$; is there $\alpha\<1$ such that the problem $\alpha$-$\tt{BIVC}$ (finding independent set that covers $\alpha\cdot m$ vertices, where $m$ -- is the maximum, i.e. the solution of $\tt{BIVC}$) is $\mathbf{NP}\text{-}\mathbf{hard}$? Can you give a hint?

# Answer
*Hint*: Finding an independent set of size $n$ is $\mathsf{NP}$-hard.

This much is sufficient to prove that your problem is $\mathsf{NP}$-hard as well.
> 0 votes

---
Tags: graphs, np-hard, approximation
---


title: How to visualize 1 pixel?

text:
# Question
Title: How to visualize 1 pixel?
The CS50 course by Edx that I am pursuing has this statement in their Week 4 practice set:

*A 24-bit BMP file, then, is essentially just a sequence of bits, (almost) every 24 of which happen to represent some pixel’s color.*

If I understand correctly,

101010101110101010101011 will represent a color.

How the length and breadth of 1 pixel defined. It is easy to visualize 1 cm, 1 meter. How to visualize 1 pixel?

Suppose this is the image:

How will the bitmap code look like? Any tool to generate the binary code after uploading the image?

# Answer
> 2 votes
If you think about the sample image provided as a grid of colored squares then the first pixel is the most upper left square and the sequence of bits represents that pixel color.
For each pixel you have 24 bits, assuming the color is expressed as RGB, then you have 8 bits per color channel. So 1 byte per color (from 0 to 255 in decimals).

```
10101010|11101010|10101011
 R:170    G:234     B:171

```

---
Tags: c
---


# Question
Title: Complexity of building a certain-type of tree and traversing such tree?
Given a set of k array :

**K = \[k1 ,k2 ,k3 ,... ,kn\]**

we want to build a tree such that its root node is k\_m ,where m is the highest value in the list and its connected to every other node and again every node is connected to every other node : Ex-

This is a example of such tree made out of array of 4 arrays:

Another example of such tree for an array of 5 array:

I want to know what is the complexity of building such trees and also the complexity of travesing every nodes in such tree.

To clarify ,each node in this tree represent an array from the set of arrays given as input.

# Answer
$$N\_{m+1}=1+\sum\_{i=1}^mN\_i,\\N\_1=1$$

so that by subtraction

$$N\_{m+1}-N\_m=N\_m$$ which is obviously a geometric sequence,

$$N\_m=2^{m-1}.$$

The creation and traversal time are both $O(2^m)$.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: if P = NP, does it mean that P = NP = NP-complete?
Lets **assume P = NP**, so all problems in NP are decidable in polynomial time, Therefore I can solve all problems in NP in polynomial claiming **P = NP = NPC**.

But then, how come Σ\* belongs to P = NPC because I can't reduce the even length string language (as an example of a language that is not trivial) to Σ\*?

one of the steps I made must be incorrect (I sure hope so) please help me find it.

# Answer
> 3 votes
No. Even assuming $\mathsf{P}=\mathsf{NP}$, it is not true that all the languages therein are $\mathsf{NP}$-complete.

An example of a language that is in $P$ but it is not $NP$-complete (regardless of the $P$ vs $NP$ matter) is $\Sigma^\*$, as you noticed. Indeed, there is no way to reduce any language $L \in \mathsf{NP} \setminus \\{ \Sigma^\* \\}$ to $\Sigma^\*$ since, given $x \not\in L$, there is no function $f$ such that $f(x) \not\in \Sigma^\*$. A similar argument shows that $\emptyset$ is not $\mathsf{NP}$-complete.

However, if $\mathsf{P}=\mathsf{NP}$, then it is true that all languages in $\mathsf{NP} \setminus \\{\emptyset, \Sigma^\*\\}$ are $\mathsf{NP}$-complete. To see this, let $A \in \mathsf{NP} \setminus \\{\emptyset, \Sigma^\*\\}$ and pick any $L \in \mathsf{NP}$. Since there are $y,z$ such that $y \in A$ and $z \not\in A$, a valid Karp reduction from $L$ to $A$ is the following: $$f(x) = \begin{cases} y & \text{if } x \in L \\ z & \text{if } x \not\in L \end{cases}. $$ Notice that $f$ can be computed in polynomial time since $L \in \mathsf{NP} = \mathsf{P}$ by hypothesis (and hence it is possible to check whether $x \in L$ in polynomial time).

---
Tags: complexity-theory, np-complete, p-vs-np, check-my-answer
---


title: Mapping Reduction from INFINITE to REG

text:
# Question
Title: Mapping Reduction from INFINITE to REG
given the following languages:

* $INFINITE\_{T M}=\\{\langle M\rangle: M$ is a TM with $|L(M)|=\infty\\}$.
* $R E G\_{T M}=\\{\langle M\rangle: M$ is a TM with $L(M) \in \mathrm{REG}\\}$.

prove the following reduction:

$I N F I N I T E\_{T M} \leq\_m R E G\_{T M}$ I'm having difficulties, building the $M\_f$ machine

would love for some help, got no clue for now :)

edit: if that wasn't clear, would love for initial direction, not for formal solution

# Answer
The following reduction mapping should work. For any input $M\in TM$ we define $M\_f$ as follows: For any $x\in\Sigma^\*$,

1. If $x=0^n1^n$ for any $n\in \mathbb{N}$ then $M\_f$ Accepts.
2. Else, we run simultaneously $M$ on all words $y\in\Sigma^\*$ in Minlex order such that $|y|\geq|x|$. If $M$ Accepts, then $M\_f$ Accepts.
3. If no word was Accepted, we continue running.

It isn't difficult to see that $M\_f$ is computable, and now I will leave you to prove that it is indeed a correct reduction.
> 1 votes

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


# Question
Title: First-Fit-Decreasing algorithm packs items of size at most 1 into bins of capacity 2
Consider the bin packing problem where we are given item sizes $a\_1,\dots, a\_n \in (0, 1)$, and all bins have capacity 2. The task is to pack the items in as few bins as possible, such that the total size of items in each bin is at most 2.

Is it possible to show that the First-Fit-Decreasing algorithm computes an asymptotic 3/2-approximation of an optimal solution, using at most $\frac{3}{2}\text{OPT}+1$ bins? The First-Fit-Decreasing algorithm sorts the items in order of non-increasing size, and the next piece is always packed into the first bin in which it fits.

What I have been able to do is to show that the First-Fit algorithm, which doesn't sort the items by their sizes first, provides a $2\text{OPT}+1$ guarantee: Assume that we open $l$ bins, then for $1≤i≤l−1$, we know that the sum of the piece sizes in bins i and i+1 must be at least 2. Thus, if we let $\text{SIZE}$ denote the total size of the input items, then $$ \text{SIZE}≥2(l−1)/2=l−1 $$ which implies that $$ l≤\text{SIZE}+1 $$ In the best case each bin is filled to capacity such that each bin has a total piece size of 2. Therefore, $2\text{OPT}≥\text{SIZE}$. Thus, we get $l≤2\text{OPT}+1$.

# Answer
Suppose we have used First-Fit-Decreasing algorithm to open $\ell$ bins.

Consider any used bin except the last one. Name it $B$.

**Consider the moment the total piece size of $B$ became greater than $1$, when an item of size $u$ was added.** There are two cases.

* $u\le\frac23$.
Then all items after this item is of size at most $\frac23$. The algorithm would have added them one by one to $B$ until the total piece size in it is less than $\frac23$ away from $2$.
* $u\>\frac23$.
Then the first item in $B$ is of size $\ge u\>\frac23$. So the total piece size in $B$ is $\>\frac23+\frac23=\frac43$.

In all cases, the total piece size in $B$ is $\>\frac43$. Hence the total piece size in all used bins is $\>(\ell-1)\frac43$.

"In the best case each bin is filled to capacity such that each bin has a total piece size of $2$." Therefore, $2\text{OPT}≥(\ell-1)\frac43$, which is what we want.
> 1 votes

---
Tags: algorithms, algorithm-analysis, approximation, greedy-algorithms, packing
---


# Question
Title: What are the ports used for in a practical sense in the Interaction Net paradigm?
I have briefly read through much of the Interaction Combinators paper, and am looking at this blog post for some help, but they both just say basically "each node in the graph must have one active port, and zero or more secondary ports", without explaining what ports are or what ports do, from a software and programming language standpoint.

I don't understand what this diagram means. I get the generic concept of "ports" as sort of input and output things (like data socket ports on the server), but I don't get how exactly they work in this interaction net context.

What are the active ports for, and what are the auxiliary ports for? If you were to think of this as a programming language or computation, what role do the ports play? I know there are some examples of "programming languages for interaction nets" like inpla, but there is no standard yet, so not looking for how to write interaction nets as code necessarily, but just to understand how the ports would work when code executes, at least at a high level. Something more for the lay programmer than a mathematician or computer scientist.

# Answer
> 3 votes
The point of the principal ports is to indicate when a rewrite rule should be activated. In interaction nets, all rewrite rules start with two nodes with connected principal ports. If two ports are connected where one or both are auxiliary, then there will be no rewrite rules associated to that link. Why would we want this? First is to simplify graphical computation. In a more general graph rewrite setup, one would need to solve the subgraph isomorphism problem to see if a subgraph matches the input of the rewrite rule. This could be highly nontrivial. By contrast, checking that two connected ports are principal is rather trivial. Second is determinism. Two rewrite rules cannot overlap without being identical, removing ambiguity. Interaction nets satisfy a strong form of confluence called "strong confluence" which states that all evaluation paths ultimately perform, verbatim, the same collection of rewrites, just in different orders. This means we don't need to worry about evaluation order or synchronization, for example.

The role of ports is, I think, a bit clearer in the original presentation of interaction nets where each port was polarized as either being positive or negative. There, only positive ports could be connected to negative ports. Agents with positive principal ports can be seen as constructors which are waiting to be consumed while agents with negative principal ports can be seen as destructors waiting for something to consume. This idea would appear in your diagram where the arrows of nil and cons are positive while the arrow of append is negative. In such a set up, in order for a destructor to work on an expression, it must have a constructor on top; that is, it has to be in head-normal form. So we can see these ports as enforcing a paradigm where computation happens exactly and only on the heads of expressions. This gives interaction nets some of the same attributes as lazy evaluation without compromising on sharing.

---
Tags: interaction-nets
---


# Question
Title: What happens if we remove the length condition on the pumpable part in the pumping lemma for context free languages?
Let $G$ be any CFG Grammar. There exists number $K$ dependent to $G$ so that for each $w\in L(G)$ with length bigger or equal than $K$, we can be write $w=uvxyz$ such that $uv^nxy^nz \in L(G)\\; \forall\\,n\geq 0$ and $|vy|\geq 1$.

My question is that this statement does not include the case of $|vxy|\leq K$. Should it be included for the theorem completeness, or is it redundant and it is indeed a special case (my professor did not include it e.g. but on Wikipedia and other books I always see that they include it)?

# Answer
It is odd that your professor taught you a weaker version of pumping lemma for context-free languages. I would believe it was unintentional.

---

As noted in the question, the condition $|vxy|\le K$ where $v\ y$ is the pumpable part and $K$ is the pumping length is included in the standard pumping lemma for context-free languages on this Wikpedia page or in common relevant introductory textbooks.

While the weaker version is correct, it is less useful and less powerful for proving a language is not context-free.

* That condition makes it easier to prove many a language is not context-free.
* **There are languages that satisfy the weaker version but not the standard version.** For example, the non-context-free language $$\\{w\\#t\mid w\text{ is a substring of }t,\text{ where }w, t\in\\{a, b\\}^\*\\}.$$

---

It takes little extra work to prove the standard version than the weaker version. It does not make much sense to deviate from the common practice that includes that condition in the pumping lemma.
> 0 votes

---
Tags: formal-languages, context-free, pumping-lemma
---


title: meaning behind activation function

text:
# Question
Title: meaning behind activation function
I have been recently thinking about activation functions and the explainability.

For sigmoid and tanh activation functions, I am thinking of them to be similar to logistic regression as the output of the activation function is very close to binary. So, to me the neural network is making simultaneous decisions and that we are training the neural network to be making better decisions.

But then the meaning behind Relu and related activation functions are lost on me. I don't quite get what the motivation behind them other than the fact that they have faster training times. So can someone enlighten some deeper meaning behind the activation functions?

# Answer
> 0 votes
There is no deeper meaning from an interpretability perspective. Neural networks are, generally speaking, not interpretable. They are universal function approximators, which means they are a way to approximate any function. You don't have to care about how they approximate it, and you shouldn't expect any explanation of how they approximate it or what function they are approximating.

The final layer is special and plays a special role. The softmax function has a particular interpretation. So too does the sigmoid function, which is a version of the softmax for binary classification. You should not expect a similar explanation for activation functions at intermediate layers, because the final layer / final output is unique.

---
Tags: machine-learning, neural-networks
---


# Question
Title: ML model to pick to classify data with inputs as an array of strings?
I have a medical dataset, which is something like this

```
| Disease | Symptoms |
| -------- | -------- |
|  Disease 1  |  ['Symptom1', 'Symptom2', 'Symptom3', ...]  |
|  Disease 2  |  ['Symptom2', 'Symptom11', 'Symptom7', ...]  |
|  Disease 3  |  ['Symptom55', 'Symptom91', 'Symptom65', ...]  |

```

I want a generate a model that when given a set of symptoms as input will be able to relate those symptoms to symptoms in the dataset and then give n-nearest diseases for the given input.

I have tried to run KNN on it, by converting the symptoms into feature vectors with encoding but it does not solve my problem as the input set can contain symptoms that are not the same logically but they mean the same.

For reference the example dataset.

# Answer
> 0 votes
I think what you could do is do a semantic relation first, such as find similarities between the terms first then do the encoding. So if you use a pre-trained model such as BERT or GPT, then you can find the semantic similarities of the symptom terms first. Then after finding the similarities you can group them together to encode the similar symptoms together then feed them into the KNN-classifier.

# Answer
> 0 votes
IMO, the various symptom descriptions should be classified by a human and regrouped. Later, when an unknown expression is fed to the system, it should be scrutinized by an expert. For every group, you can choose a canonical representative or just a number. Better use the Hamming distance than a geometric metric, as the numbers do not relate to proximity/similarity.

I would not rely on automatic synonym or paraphrase analysis, especially as regards health issues.

---
Tags: machine-learning, natural-language-processing
---