# Question
Title: building NFA for { a^p; p is a prime number, m is a fixed number and m >p >0 }
$\\{a^p; p$ is a prime number, $m$ is a fixed number and $m\geq p \geq 0 \\}$

I know this is regular since it is finite, but I don't understand how to build an NFA for this if we do not know what $m$ is. Is there a way to draw the NFA regardless?

# Answer
> 0 votes
Your DFA has states $S\_0$ to $S\_m$ and E. You start at state $S\_0$.

Any state transitions to E if the next input symbol is not a. States $S\_m$ and E transition to state E on any input; state $S\_i$ for 0 ≤ i \< m goes to state $S\_{i+1}$ on input a.

$S\_i$ is an accepting state if and only if i is a prime. All other states are non-accepting.

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


# Question
Title: Building maze to maximize shortest path, may be given waypoints and teleports
How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (Assuming sizes between 8x8 and 30x30. Using C or C++ if that matters) Or, is this so complex that it would take way longer?

There is an area, where an automated traveler follows a shortest path algorithm at all times. Playing the builder, find the way to maximize the number of points the traveler must visit.

The area is typically between 8x8 and 30x30, given in the form:

```
.F......
......a.
........
........
.....1X.
........
.A......
........
..O.....
.X......
..X.....
..X.....

```

Where there is:

* Always a single `O`, the starting point
* Always a single `F`, the ending point
* Always many `.`, empty points that can either be traveled or built on
* Sometimes `X`, points designating they are blocked for traveling or building
* Sometimes pairs of letters (i.e. `A` and `a`, but never `F`, `O`, or `X`), indicating a teleport when visiting the uppercase letter for the first time to the lowercase letter
* Sometimes numbers (i.e. `1`), designating waypoints

The automated traveler follows a shortest path algorithm at all times. It must begin at the starting point, if there are waypoints pass over them in order, and finish at the ending point. The traveler may pass over the ending point or subsequent waypoints early, but the game doesn't end and the waypoints aren't counted as visited, until they are the active next destination. If there are any, the traveler must not pay attention to any teleport spots; they must take the shortest path between points as if they cannot see these teleport spots. The exception to this rule is if there are multiple paths with the shortest length between last source to next destination and one of them travels through an active teleport spot, the path with the teleport must be taken. (Otherwise, can choose any of the multiple shortest paths.) If the shortest path forces them into a teleport spot, they teleport the first time they visit the uppercase letter to the corresponding lowercase letter. The traveler can move horizontally and vertically. The traveler can move diagonally between two points if the 2x2 square containing both points is clear of blocking points.

So, if the traveler needs to travel from the lower left to upper right point, here they can move diagonally and only count 2 moves:

```
..
..

```

But here, again traveling from the lower left to upper right point, they cannot move diagonally and must count 3 moves:

```
X.
..

```

The game always starts with an open path to reach all required destinations.

You, the builder, get to take all of your actions first, and none once you decide you are complete and allow the traveler to begin. The builder can place additional `X` points that block travel on them, but they cannot make it impossible to reach any of the required destinations. The builder cannot place any other points, such as more teleports or waypoints. The builder cannot remove anything given to them already in the area (other than replace empty points.) Strategy may include blocking points to force: otherwise out of the way travel; backtracking; and traveling between teleports. Optimal strategy might include trying to connect the starting, ending, and destination teleport spots in short paths, and forcing a long backtracking path to waypoints.

This is to come up with possible strategies for a tower defense game. Certain aspects of the game, such as multiple waves, limitations on resources, and attack towers, are ignored to simplify and just focus on the maze-like aspect of the game.

# Answer
Just a note: even the simpler version without waypoints and teleports is NP-hard:

Start with a maze in which the dots mimic the edges of a grid graph $G$ of max degree 3, and $X$s are placed "around" them (the dots are "corridors"). Put the $O$ in a corner and the $F$ near it with a dot in the middle.

Maximizing the shortest path (adding more Xs) is equivalent to finding an Hamiltonian path in the original graph $G$ which is NP-complete (each new $X$ must block a "corridor", i.e. it removes an edge of $G$).
> 2 votes

# Answer
Unfortunately this sounds related to the max-cut problem, which is NP-complete. (I.e. essentially impossible even for relatively small input sizes.) 8x8 is already stretching it, but maybe the constraints on the problem means we can come up with an algorithm that will cope with that size, and if we're *very* lucky will go up to 30x30.

**Actually, see bottom for my final attempt, that I think could easily succeed within the allotted time, and generate an optimal solution.**

## Back of the envelope

Assume an empty 8x8 grid. We could brute force all the squares being "wall" or "not wall". This would leave us with 264 combinations, which is totally impossible. OK, if more than half of the squares are walls then there are not enough squares to form a longer path than if there were fewer walls. So we can maybe cut it down to 232, which is 4 billion.

OK, 4 billion is actually manageable. Each configuration would require a breadth-first search which we'll assume takes 100ns. That's 10000 per core per second. 232 / 10000 / 32 = 4 hours. The breadth-first search could take 100 times as long due to going back and forth between waypoints, I'm not sure. So, could be 400 hours. Going to 9x9 makes things take 25 times as long. Ouch.

## First thought

Let's think about choosing paths rather than walls. First we explore paths to the first waypoint, then the second, etc.

Of course this allows paths that can go round in circles forever. But we can fix that by pruning paths that "return" to already visited nodes without having hit any more waypoints (because they are clearly not the shortest path anymore). Is there a nice way to detect that?

This "already visited nodes" thing reminds me of Dijkstra's algorithm. It would be good if we could just take the "best" (longest shortest) path to a waypoint. But I think there may be a problem with the choice of previous paths influencing where walls might go. Furthermore, the "longest" path to waypoint 1 may decrease the "longest" path to waypoint 2, so we can't just keep track of the longest path to waypoint x.

It takes walls in a certain place to "force" a path to go a certain way, but this can be overdone e.g. when there are two similar paths of equal length, you don't need to use walls to block one off.

Well, we could keep a list of possible wall configurations for every path from the start to waypoint X, and then start with each of those as we head for the next waypoint. Only walls adjacent to the path matter; all the rest of the space is "don't care". In fact, sometimes even walls adjacent to a path can be "don't care", as long as they would not create a shorter path to the waypoint.

It still seems like an intractable number of cases. But not necessarily. There are not that many ways to take an empty grid (start and end in opposite corners) and create a maximum length snaking path. As you make the path shorter, fewer squares get covered so more of them become "don't care". (What kind of crazy data structure you would need, I don't care ;)

Would this make the problem tractable, even for 8x8 grids? I'm not sure. On its own, I doubt it.

## Second thought

We could try to find the "best" partitioning of the space so that there are as many "mandatory crossings" as possible. E.g. if 1, 3 and 5 are on one side and O, 2, 4, and * are on the other, there are 6 crossings. A partition is a continuous path composed of horizontal, vertical, or diagonal segments. (Let's also say that it cannot be more than the side length of the maze, e.g. for 8x8 maze the partition path cannot be more than 8 points.)

There must be a "gap" in this partition and it will be on ALL paths through the maze.

I posit that all crossings between "actual" waypoint hits must go through the same gap (otherwise there are simply more choices which allows for shorter paths between waypoints.) So can we try each node along the path in turn, and then "divide and conquer" on the two sides of the partition, and see which comes out best?

Sadly, no, because there may be other gaps where some paths "cross back over" to form loops that add steps, or travel along the partition path itself.

Maybe dynamic programming can help, but as the crossings-over can have a big impact on the other side of the partition, I think further additions to this approach will be necessary.

## Divide and conquer?

Well, what if we chop the grid into quarters? For an $n\times n$ grid, this means the side length of each quarter is of length $\frac{n}{2}$. Then we divide again, and those quarters have boundaries of length at most $\frac{n}{4}$, etc. (For simplicity ignore diagonals.) For each of these subdivisions, we need to create some information about its perimeter so that it can be "stitched" to its neighbour. We will begin at the level of individual squares, combine each of them with a neighbours (yielding 1x2 blocks), combine these blocks with their neighbours (4x4 blocks), and so on until we hit the total maze size.

So here's my proposal, which hopefully will work. For each subdivision, we can list all "candidate" configurations of the space within. For *each* of these candidates, we store:

```
for each of the 4 sides:
    for each pair of edge pieces:
        for each possible run of consecutive waypoints (including none)
            { minimum path length, list of waypoints included }

```

"For each pair of edge pieces" is roughly $m^2$ for a subdivision with side length $m$. This is excellent!! I was expecting something exponential.

Yes, when stitching we need to combine every configuration of one subdivision against every configuration of another. That's on the order of $m^4$. But then we can throw out a lot of duplicate configurations, or configurations that are identical except for a shorter path somewhere than another one, or configurations where waypoints are lost. This is why I said "candidate" configurations above.

This would be tough to implement, but I would hazard to say this would take a short time **to get an optimal answer** for 30x30. If we are talking $m^4\log m$ we are talking a few thousand times some large constant. Even if that large constant is 0.1 seconds, we are talking about 5 minutes. I think 0.1 seconds is an overestimate, even on 1 core. (This algorithm would be very fiddly to parallelise anyway.)

What about teleporters? Perhaps along with the other information, have flags which say "teleporter x may come out of this edge", and also add cases for every combination of waypoints that sort of say "getting to this waypoint WILL teleport you the first time you take it" or "getting a longer shortest path length WILL teleport you the first time you take it". Then those things are combined to figure out if the teleport *actually* gets taken and calculate accordingly.

So there you have it. You probably wanted something easier to implement (even if non-optimal), but hey, this is the Computer Science stack exchange.

## Implementation notes

Implementing this sounded fun, so I decided to give it a go. Although I think I'm close, it's running up to some 400 lines of Python, and debugging is probably going to be a nightmare. So I'm giving up.

My WIP is too long to reasonably post, but I thought I would write some notes here in case anyone wants to try.

The strategy is to divide-and-conquer, halving along the longest side until you get to 1x1 tiles. There's a "Boundary conditions" object which lists all distinct paths from any edge segment to any other edge segment (including from a segment to itself, this is required e.g. for the case where you go through the edge, hit a waypoint, then go back across the same edge).

These paths are culled based on the assumption that the player will choose the best path. This is done by giving each path a `set()` of properties, and any path that is a subset of another path *and* has $\geq$ length is culled.

Merging two adjacent subsections of the grid is done by first taking the common edge, and computing all possible paths from each segment of that edge to each other segment (including itself). Then, a new "Boundary conditions" object is constructed by taking all its outside segments and computing all paths from them to all others. E.g. for the left half, the existing paths are considered, but also all paths that hit the "common edge" in between. The set of paths is culled.

Starting from the 1x1 squares and building upwards, each subsection of the grid has a list of *many* potential boundary conditions. These represent different possible internal configurations (but some internal configurations produce the same boundary conditions so can be forgotten). Each merge involves taking all possible boundary conditions of one section and merging them with all possible boundary conditions of the other.

But doesn't each 1x1 square start out with the just 1 boundary condition and so the larger sections also have 1 each? Well, not quite. Empty spaces have two potential boundary conditions: those that leave them empty and those where a wall has been built.

Starts, ends, waypoints and teleporters can all be handled using a path's set of "properties". When a path contains the start, end, and ordered waypoints properties, it causes all other paths to be culled during its processing step, and becomes a candidate solution.

Oh the complexity...
> 1 votes

---
Tags: algorithms, complexity-theory, graphs, algorithm-analysis
---


# Question
Title: What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$
Is it known if complexity class of all sparse languages is contained within e.g. $\mathsf{EXP}$ or $\mathsf{EXPSPACE}$? Or what is the smallest time or space complexity class that contains complexity class $\mathsf{SPARSE}$?

# Answer
If by SPARSE you mean the set of languages where the acceptance occurs on a set of zero density, then it is not in EXP or EXPSPACE. It isn't even computable. To see this, pick your favorite computable enumeration of Turing machines T\_n, and consider the language L in the alphabet {0,1} where a string S is in L if and only if L is consists just of n 1s, and where T\_n halts on the blank tape. Since the problem of whether a given Turing machine halts on the blank tape is undecidable (if one can do it, one can solve the Halting Problem), our language L is undecidable. Using this same trick with a padding argument we can make languages which are as sparse as we want but are not computable.
> 1 votes

# Answer
I'm not sure if it's the smallest class, but the natural candidate is $P/poly$ \- for each $n$, the "advice" can just encode all acceptable strings of length $n$ (by definition of $SPARSE$, their number is polynomial).

$P/poly$ is also a strict superset of $SPARSE$: for example, it contains $\Sigma^\*$.
> 0 votes

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


# Question
Title: Show that if $\mathcal{H}$ is PAC learnable in the standard one-oracle model, then $\mathcal{H}$ is PAC learnable in the two-oracle model
This is a question $9.1$ from **Understanding Machine Learning Chapter 3**. It goes like this:

> Consider a variant of the PAC model in which there are two example oracles: one that generates positive examples and one that generates negative examples, both according to the underlying distribution $\mathcal{D}$ on $\mathcal{X}$. Formally, given a target function $f : \mathcal{X} \to {0,1}$, let $\mathcal{D}^+$ be the distribution over $\mathcal{X}^+ = \\{x \in \mathcal{X}: f(x) = 1\\}$ defined by $\mathcal{D}^+(A) = \frac{\mathcal{D}(A)}{\mathcal{D}(X^+)}$, for every $A \subset \mathcal{X}$. Similary $\mathcal{D}^-$ is the distribution over $\mathcal{X}^{-}$ induced by $\mathcal{D}$.

> The definition of PAC learnability in the two-oracle model is the same as the standard definition of PAC learnability except that here the learner has access to $m^{+}\_{\mathcal{H}}(\epsilon, \delta)$ i.i.d. examples from $\mathcal{D}^+$ and $m^{-}\_{\mathcal{H}}(\epsilon, \delta)$ i.i.d. examples from $\mathcal{D}^{-}$. The learner’s goal is to output $h$ s.t. with probability at least $1-\delta$ (over the choice of the two training sets, and possibly over the nondeterministic decisions made by the learning algorithm), both $L\_{(\mathcal{D}^+,f)}(h) \leq \epsilon$ and $L\_{(\mathcal{D}^−,f)}(h) \leq \epsilon$

I am trying to prove that if $\mathcal{H}$ is PAC learnable in the standard one-oracle model, then $\mathcal{H}$ is PAC learnable in the two-oracle model. My attempt so far:

Note that $$L\_{(D,f)}(h) = \mathcal{D}(\mathcal{X}^+)L\_{(\mathcal{D}^+,f)}(h) + \mathcal{D}(\mathcal{X^{-}})L\_{(\mathcal{D}^-,f)}(h).$$ Let $d = min \\{ \mathcal{D^+}, \mathcal{D^-}\\}$, then if $m\geq m\_\mathcal{H}(\epsilon d, \delta)$, then it is clear that: $$\mathbb{P}\[L\_{(D,f)}(h)\leq \epsilon d\] \geq 1-\delta \implies \mathbb{P}\[L\_{(D^+,f)}(h)\leq \epsilon\] \geq 1-\delta$$ And, $$\mathbb{P}\[L\_{(D,f)}(h)\leq \epsilon d\] \geq 1-\delta \implies \mathbb{P}\[L\_{(D^-,f)}(h)\leq \epsilon\] \geq 1-\delta$$

So we know that if we have $m\geq m\_{\mathcal{H}}(\epsilon d, \delta)$ samples drawn iid from $\mathcal{D}$, then we can guarantee $\mathbb{P}\[L\_{(D^+,f)}(h)\leq \epsilon\] \geq 1-\delta$ and $\mathbb{P}\[L\_{(D^-,f)}(h)\leq \epsilon\] \geq 1-\delta$.

How do I choose $m\_{\mathcal{H}}^+(\epsilon, \delta)$ and $m\_{\mathcal{H}}^-(\epsilon, \delta)$ such that if we have $m^+ \geq m\_{\mathcal{H}}^-(\epsilon, \delta)$ samples iid according to $\mathcal{D}^+$ and $m^- \geq m\_{\mathcal{H}}^-(\epsilon, \delta)$ drawn iid according to $\mathcal{D}^{-}$, then we can guarantee $\mathbb{P}\[L\_{(D^+,f)}(h)\leq \epsilon\] \geq 1-\delta$ and $\mathbb{P}\[L\_{(D^-,f)}(h)\leq \epsilon\] \geq 1-\delta$?

When is drawing $m^+$ samples according to $\mathcal{D}^+$ and $m^{-}$ samples according to $\mathcal{D}^-$ the same as drawing $(m^+ + m^-)$ samples according to $\mathcal{D}$?

# Answer
Recall the following lemma. Let $X,Y$ be two random variables satisfying $\Pr\[X\le\epsilon\]\ge 1-\delta$ and $\Pr\[Y\le\epsilon\]\ge 1-\delta$ then $\Pr\[X\le \epsilon \land Y\le \epsilon\]\ge 1-2\delta$.

Suppose $\mathcal{H}$ is PAC learnable (realizable and proper). Let $m(\epsilon,\delta)$ be the guaranteed PAC sample complexity. Given $m(\epsilon,\delta/2)$ samples from $D^+$ and $m(\epsilon,\delta/2)$ samples from $D^-$, find $h\_{ERM}$ that is consistent with all samples (both positive and negative). Since $\mathcal{H}$ is PAC learnable, we know that $\Pr\[L\_{D^+}(h\_{ERM})\le\epsilon\], \hspace{1mm} \Pr\[L\_{D^-}(h\_{ERM})\le\epsilon\]\ge 1-\delta/2$. Note that we strongly used the fact that the PAC bound is achieved by any sample consistent hypothesis. Now Use the above lemma to show that the overall empirical risk minimizer is a 2-oracle PAC learner for $\mathcal{H}$.
> 1 votes

---
Tags: machine-learning, probability-theory
---


# Question
Title: social network analysis - relations between people with weights
I asked this question on datascience.stackexchange but they directed me here.

I have a social network represented as a set of people S and individual weights for each of person (weight is the cost of person). I also have defined relationships between these people (whether people know each other or not). I must find such a subset D, such that every person in this subset either belongs to the set S or knows someone from the set S directly.

There will be a lot of such subsets. I want the subset whose sum of weights of people is the smallest.

Let's see example:

**D = {(John(7), Adam(15), Viktor(6), Bob(2)} and connections are John - Adam - Viktor - Bob. Solutions are Adam,Bob(17) OR John,Victor(13) OR Adam,Victor(21) OR John,Bob(9). The best is the last one - John,Bob(9).**

I thought to create a directed graph where:

* Each vertex represents person
* Each vertex has a weight assigned to it
* Edges between vertices indicate whether the people know each other or not

I imagine this as a minimum spanning tree on directed graphs problem. I found Chu-Liu/Edmond's algorithm, I know that this algorithm works for edge-weighted graphs and I have vertices-weighted, so I just set the edge weights to what are the weights of the vertices at the end of the edge. But this is not optimal solution. I don't need direct connections between people in the set D.

So after I have result from that algorithm, I can apply on it some greedy algorithm, which will go recursively over each element and check how removing it from the subset D will affect the structure - when the sum of the weights will be minimal and will ensure that no element falls out of set D (check below).

**Refer to an example, my MST result will be John,Adam,Victor,Bob(27). Best solution is John,Bob(9). Interesting bad solution is Viktor,Bob(8) - the sum is minimal, unfortunately John will fall out of the D subset.**

Also I assume that:

* cost of a person doesn't correlate with their degree in the network (numbers of acquaintances)
* the maximum number of people and acquaintances (vertices and edges) is about 400

Is my way to solve this problem is good? Do you suggest any other solutions for that?

# Answer
First a few comments/questions about your approach:

* Why do you think your problem has anything to do with minimum spanning trees? I fail to see the connection.
* Why is your graph directed when the original problem seems to state that the "know eachother" relation is symmetric? (if A knows B then B knows A)
* For your "greedy post-processing" can you do better than looking at all possible subsets of D? In other words, how does your MST help you compute the correct subset?

Then to answer your question:

If I understood you correctly, the problem you want to solve is a weighted version of dominating set. It is NP-Hard and thus unlikely to be solvable efficiently in the worst case when the number of people increases.

By googling "minimum weight dominating set" you will however find approximation algorithms, heuristics or "practically efficient" algorithms which might do the trick if the number of people in S is not too large (or the specific instance happens to be nice enough). I'm not sure how well they would perform for your considered graph size.

Alternatively, if the number of people in S is really not large (say fewer than 25) then you might consider simply brute-forcing through every possible subset of S.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Why is the following language undecidable?
I'm currently learning for my exams this semester and tried to solve some old exams from the last years.

The question is to show, that L ist undecidable. $L=\\{w|T(M\_w)\neq\emptyset \land \forall x \in T(M\_w): xx\in T(M\_w)\land xxx\notin T(M\_w)\\}$

I showed that the language $L'=\\{w | T(M\_w)\neq \emptyset\\}$ is undecidable due to the Rice Theorem. I created to Turing Machines $M\_1$ with $T(M\_1)=\emptyset$ and $M\_2$ with $T(M\_2)=\Sigma^\*$ to show that the language L' is not trivial. (since $1\in L$ and $2\notin A$. With out loss of generality i assume those machines have the Gödelindexes 1 and 2)

My problem now is, that I know no way to show, that this result transfers to the language L. I know that the language L must only contain such Gödel Indexes, that for those indexes the following TM must accept infinite words (because in case of $x\in T(M\_w)$ there must be $xx\in T(M\_w)$... and therefore must be $xxxx\in T(M\_w)$ etc.)

I would love to hear suggestions / answers! Thanks in advance

# Answer
> 0 votes
This is a direct consequence of Rice's theorem. A word $w$ is in $L$ if $T(M\_w)$ satisfies the following semantic property:

> $T(M\_w)$ is non-empty, and for any $x \in T(M\_w)$, we have $x^2 \in T(M\_w)$ and $x^3 \notin T(M\_w)$.

In order to show that this language is undecidable according to Rice's theorem, we need to exhibit two Turing machines $w\_1$ and $w\_2$: one which doesn't satisfy the property, and another one which does satisfy it. We can take $w\_1$ to be some machine such that $T(M\_{w\_1}) = \emptyset$, and $w\_2$ to be some machine such that $T(M\_{w\_2}) = \\{ a^{2^n} : n \geq 0 \\}$.

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


title: Is MAX-averageSAT a well-known problem?

text:
# Question
Title: Is MAX-averageSAT a well-known problem?
Is there any variant of the Boolean SAT or Max-SAT problem that has a flavor of maximizing or minimizing the average of the weights of the satisfied clauses of a WCNF formula? Any literature on an optimization problem of similar flavor would be appreciated. Thanks.

# Answer
> 1 votes
This problem is new to me. It has similar hardness to weighted MaxSAT; there is a polynomial-time Turing reduction in both directions. Here is a key fact:

> Let $\varphi,(w\_1,\dots,w\_n)$ denote a weighted CNF formula, where $w\_1,\dots,w\_n$ are the weights on the clauses. Then the following two conditions are equivalent:
>
> * There is an assignment to $\varphi,(w\_1,\dots,w\_n)$ so that the average of the weights of the satisfied clauses is at least $a$.
> * There is an assignment to $\varphi,(w\_1-a,\dots,w\_n-a)$ so that the sum of the weights of the satisfied clauses is at least $0$.

This lemma yields an equivalence between weighted MaxSAT and weighted MaxAverageSAT.

For instance, if you have an instance of weighted MaxAverageSAT that you want to solve, here is how you can solve it using an off-the-shelf solver for weighted MaxSAT. Basically, use binary search on the average $a$. Given $a$, you can test whether it is possible to achieve an average at least $a$, by using the solver on $\varphi,(w\_1-a,\dots,w\_n-a)$ and checking whether it gives you an assignment where the sum of the weights is at least $0$; you can then use this to determine whether to increase $a$ or decrease $a$ in the binary search. After polynomially many iterations of binary search, you'll narrow it down to a small enough range that you can uniquely determine the maximum achievable average.

---
Tags: optimization, np-complete, satisfiability, 3-sat, maxsat
---


title: Complexity of specific cases of MAX2SAT

text:
# Question
Title: Complexity of specific cases of MAX2SAT
I know that MAX2SAT is NP-complete in general but I'm wondering about if certain restricted cases are known to be in P. Certainly the languages

$L\_k:=\\{ \phi \\,|\\, \phi\\,\text{is an instance of 2SAT which has an assignment satisfying at least k clauses.}\\}$

can be solved in $O(n^k)$ through brute force search since for each language $k$ is fixed. However, I'm wondering about the case when a fraction of the clauses is specified. Does any fraction yield an NP-hard problem? Specifically I'm wondering about the case of satisfying at least half of the clauses of a 2SAT instance.

The reduction I saw from 3SAT to MAX2SAT constructs 10 clauses from each clause in 3SAT such that out of these ten, exactly 7 are satisfied when the original 3SAT clause is satisfied and at most 6 are satisfied when the original clause is not satisfied. So in this reduction the fraction of $7/10$ works but $1/2$ does not because unsatisfying truth assignments of a 3SAT instance can still yield an instance of 2SAT that has an assignment satisfying more than half of the clauses. I thought about another construction or adding extra clauses to an instance of 2SAT but I've been unsuccessful so far.

# Answer
> 4 votes
You can always satisfy at least half of clauses: for each variable $x$, find the number of clauses that contain $x$ and the number of clauses that contain $\lnot x$. Select the one which satisfies the most clauses. Remove clauses containing $x$ and $\lnot x$. Repeat for other variables.

Since for each $x$ we satisfy at least half of removed clauses, we satisfy half of the clauses overall.

On the other hand, it's also tight: let $\alpha \> \frac 12$ be the fraction of clauses for which we can give an answer. Let $\beta \> \frac 12$ be the maximum fraction of clauses we can satisfy in a specific clause. Then we can add clauses so that $\beta$ (for the new clause) becomes arbitrary clause to $\alpha$:

* If $\beta \< \alpha$, then we can add clauses $(x\_i \lor \lnot x\_i)$, until $\beta \> \alpha$ (since these clauses are always true, $\beta$ increases).
* If $\beta \> \alpha$, we can add clauses $(x\_i)$ and $(\lnot x\_i)$, until $\beta \< \alpha$ (since exactly half of clauses is true, $\beta$ decreases).

I didn't check, but to get $O(\frac 1m)$ difference (i.e. to find the exact number of clauses), I think it suffices to add $O(m)$ clauses. In other words, if we can solve for some $\alpha \> \frac 12$, we can check for any $\beta$ whether $\beta$ fraction of clauses can be satisfied, and therefore we can solve MAX2SAT in polynomial time.

---
Tags: complexity-theory, np-complete, reductions, satisfiability, 2-sat
---


# Question
Title: How to express a type that represents an associative array whose keys determine the type of the value?
I'm fairly new to type systems and theory, so I would appreciate some guidance in a problem that sparked my interest.

I would like to understand what type system features are required so a compiler can enforce that a given key will return a value of the same type as the one the key was associated with in the first place.

A practical version of my problem is to declare a Map in TypeScript that allows a developer experience like in the pseudocode below:

```
const cache =  new  Map<K,  V>()

cache.set('Foo',  Error('R'))

cache.set('Bar',  1)

cache.get('Foo')  // Return value typed as Error.

cache.get('Bar')  // Return value typed as number.

cache.get('Qux')  // Compilation error.

```

What would the type of `K` and `V` be?

# Answer
> 2 votes
What happens if I try to get `Bar` before it has been set? If you expect a compilation error, then you are not talking about a single type, but instead a sequence of types, where the type changes after each call to the set method. Look into 'strong update' and 'linear types'.

Why not just use a record type?

```
type MyRecord = { Foo : Error, Bar : number }

```

# Answer
> 0 votes
Existential types will do the trick.

Your question is not clear on this point, but as far as I can tell the keys are intended to be strings, and the values can have any type.

The type of `cache.get` is `string → ∃ t . t`, i.e., a function taking a string and return a results of type `t`, for some type `t`.

The type of `cache.set` is `∀ t . string → t → unit`.

---
Tags: type-theory, dependent-types
---


title: For an NFA, can we always find a RAM?

text:
# Question
Title: For an NFA, can we always find a RAM?
For an NFA, can we always find a RAM, which recognises the same language?

# Answer
> 2 votes
If RAM is a Random Access Machine (i.e., a rudimentary computer with registers, memory and assorted instructions), the answer is just "build a DFA that recognizes the same language, simulate that DFA in code". I.e., have a transition table that tells you the next state for each combination of state and input symbol; start in the start state, check if the state after consuming all input is final.

More abstractly: RAM is equivalent in computing power to a Turing machine. As regular languages are decidable, they can be decided by a (deterministic) Turing machine or a RAM.

---
Tags: complexity-theory, formal-languages, computability, finite-automata, discrete-mathematics
---


# Question
Title: Finding a source of a directed acyclic graph in linear time
Given a directed acyclic graph $D = (V,A)$, a vertex $v \in V$ is a *source* if its *indegree* is zero, meaning that it has only outgoing arcs.

Does there exist a linear time algorithm to find a source in a given directed acyclic graph?

Follow-up question: Can one in linear time find all sources?

# Answer
As Yuval mentions, the datastructure is important here. I'll try to give a solution for some of the types of adjacency lists:

1. **Incoming edge list**: For each node, there is a list of vertices from which there is an incoming edge to this node. You can simply scan all vertices and check if the size of their adjacency list is $0$ or not. A size $0$ list means no incoming edges, so the node is either a source or disconnected. Assuming a connected graph, this scan of each vertex will give you a list of *all* sources (or you can stop after finding one) in $O(|V|)$ time - linear in the number of *vertices*.
2. **Outgoing edge list**: For each node, there is a list of vertices to which there is a directed edge from this node. Keep a bit-string with each bit representing a vertex, initialized to 0. Starting from the first node, start scanning its list for vertices to which there is an outgoing edge from this. Every such node (neighbour) cannot be a source, so keep setting their corresponding bit in the bit-string. At the end, all vertices whose corresponding bits are still unset, are the source vertices. You can do this in time linear in the *size of the graph* \- $O(|V| + |E|)$.
3. **Both lists together**: For each vertex, there is a mixed list of vertices which have an edge *to* or *from* this vertex, with some other attribute indicating which of the two is actually the case. The approach is similar to 2 above, with the addition that any incoming edge immediately rules out the current vertex (and you can mark its bit set). Unlike in point 2 where you need to go through all vertices, here, you might find some source sooner. If you don't stop, you will have all sources. For both cases, time is again linear in the *size of the graph* \- $O(|V| + |E|)$.
4. **Both lists separately**: Just pick the incoming edge list and follow 1.

As a side note, if choosing the datastructure is in your hands, you might want to analyze what all operations you intend to perform, and how frequently, and choose an appropriate datastructure.

**Edit:** For case 1, if you have a dag where the number of sources is *very* small as compared to $|V|$ (eg, in a tree with one source), *and* where the average distance from any vertex to a source is small as compared to $|V|$ *and* you only want any one source, you can use a faster on average algorithm (although worst case asymptotic complexity will be the same). Select any vertex at random, and go to any of its parent (from the incoming edge list), and on to its parent and so on, till you reach a node which has no parent - a source. This small gain of efficiency is for very limited types of graphs with a slightly more complex algorithm.
> 22 votes

# Answer
Let's consider a simpler question. Suppose that you know your graph is a tree. Then you can find the source node in linear time. Just select a random node, if it is the root then you have your answer, if not it should be a child or parent then traverse back until you reach the root. This can be done in $O(|V|-1)$.
> 0 votes

# Answer
first do a topological sort (linear time), $v\_1, \ldots, v\_n$ so that $v\_i$ is not a child of $v\_j$ for any $i \< j$.

```
all_source = []
for v in [v1,...v_n]:
   if v is_not visited:
      all_source.append(v)
      dfs(v)

```
> 0 votes

# Answer
Assuming you have a graph G=(V, E) given in adjacency list format. (to be clear here the list contains all outgoing edges from the source). You can construct the inverse of the graph G in linear time. Then you can iterate over the inverse graph and collect all vertices that have empty adjacency list. These vertices have no outgoing edge in the inverse graph which means they have no incoming edges in the original graph, therefore, these are your source vertices.

The running time is linear. Constructing the inverse of the graph takes a max of O(|V|+|E|) time. Iterating over the inverse of the graph takes O(|V|) time.
> -1 votes

---
Tags: algorithms, graphs
---


# Question
Title: How to group intervals which overlap by some amount?
I have an algorithm that generates a list of intervals. The algorithm is run *m* times. Lets mark the intervals as tuples `(s1, e1), (s2, e2), .., (sn, en)`. It is possible to add the run ID to the tuple (though I don't think it helps).

The goal is to "clean" spurious ranges (appearing in few runs) and to find groups of at least *k* almost perfectly overlapping intervals out of *m* runs of the algorithm, where *k* is close to *m*. E.g. if we have 10 runs, *k* will be 7-9.

By almost perfectly overlapping I mean `>0.95` overlap, but exact requirement is user-defined (won't be 0.5 or such). The overlap should be between all intervals in the group (i.e. intersection). However, since I am trying to translate an eyeball analysis into exact requirements this requirement might be too strong ..

The differences in the intervals generated by multiple runs of the algorithm stem from a random factor (seed) as well as slightly different ranges may passing requirements, therefore there is some 'wiggling room' in the results. It also detects some ranges infrequently (think local minima), ranges which should be ignored as spurious.

The origin of the problem is running multiple times some algorithm that searches a range for "interesting" areas. By the nature of the algorithm, each run may return slightly different ranges as well as, at times, a range not seen before.

The intervals can be viewed as integers, though in reality the intervals I get may be real number in any range. I assume I can always use a min-max scaler to, for example, have the ranges have (approximated) integer values in the 0-1000 range or similar.

Below is a (very simple) example of the problem marked as I would do manually. The three **green** intervals and the three **red** intervals should be reported as groups, whereas the other three are a group on their own. The overlap of the blue interval is too small. The Yellow interval is not "similar" to the red ones in size.

There may be problems like in the diagram below which I am not sure how to address. The green (bottom) interval and the one above it are certainly "the same" as are the red one and the one below, however the green and red are already too far apart to be considered a group.

My initial idea was to build an interval graph. On that I can greedily find the point at which most intervals intersect, than somehow (no clear idea how yet) I would remove intervals which should not belong to the group. Once done I remove the group from the graph and repeat.

Another method I thought about, but which is O(N^3) (and not guaranteed to yield a good result) is to calculate the overlap of all pairs, selecting the best and merging (union? intersection? average start/end?) then repeating until there are no more "interesting" overlaps.

I consider an overlap interesting if it is larger than some percentage, e.g. 95%.

Are there any algorithms already achieving something similar? Any direction someone can point me in?

# Answer
Here is one interpretation of your problem:

> Given $n$ observed intervals $I\_1,\dots,I\_n$ and $k$, find $k$ disjoint inferred intervals $J\_1,\dots,J\_k$ that maximizes the number of observed intervals are covered by at least one of the inferred intervals. Say that $I\_i$ is covered by $J\_j$ if they have at least 95% overlap, where the overlap between $I\_i,J\_j$ is measured as $|I\_i \cap J\_j|/|J\_j|$ where $|\cdot|$ denotes the length of an interval.

This problem can be solved with dynamic programming. Sort the endpoints of the observed intervals. For each endpoint $e$ and each $k\_0$ with $0 \le k\_0 \le k$, let $f(e,k\_0)$ denote the maximum number of observed intervals that can be covered by $k\_0$ disjoint inferred intervals that are all in $\[-\infty,e\]$. Then you can write a recurrence relation for $f$: in particular,

$$f(e',k\_0) = \max(f(e^\*,k\_0), \max \\{f(e,k\_0-1) + \eta : e\<e'\\})$$

where $e^\*$ is the endpoint immediately before $e$, and $\eta$ is the number of observed intervals that are covered by $\[e+1,e'\]$.

---

That said, I suspect a more pragmatic approach might be to use some standard clustering algorithm, adapted for this problem. For instance, you might use k-means on the centers of the intervals. Given a set of intervals that have been clustered together, you might use the median of their left endpoints and median of their right endpoints to define a new interval that serves as the clusterhead. You can probably come up with other heuristics. It's plausible that this might be adequate in practice.
> 1 votes

---
Tags: clustering, intervals
---


# Question
Title: How does the OS handle multiple stacks in its physical memory?
Without assuming ASLR...

Processes have virtual addresses, and they manage stacks & heaps of their own. However, these all get mapped to physical addresses somewhere on the memory.

Let's say we have Process A and Process B. Process A starts before Process B. Process A puts some stuff on the stack. We switch to Process B. It puts some stuff on the stack.

However, Process A finishes, and all its elements need to be removed off the stack. However, Process B's elements are still on the stack, so we can't just force the stack pointer down.

How is this relieved? Or is physical memory really all heap?

# Answer
The point you make at the very end of your question is the right one.

No modern computer has a stack. In hardware terms it turns out to be superfluous, wasteful and useless.

A stack is superfluous because one can easily perform the operations “write a value”, “retrieve the last value written”, and so on by having a pointer to a memory location. “Push” can be implemented by advancing the pointer and writing to the location it points to; “pop” by reading the pointed-to location and undoing the advance of the pointer. (On Intel architectures the pointer is a register called SP, and “advancing” decrements SP before writing to memory). This emulation of a stack requires *no hardware at all* \- only memory, which exists already.

A hardware stack is wasteful because it requires special mechanisms over above the “read at location”, “write at location” which we already have because we have RAM. (Some early or embedded microprocessor architectures have gone the other way, having a very few levels of stack on-chip).

A hardware stack is useless because fashionable computer languages such as C cannot function with a stack in the strict sense - they need to access not just the last pushed value (such as a return address) but values pushed earlier on, which can be the arguments to a subroutine, for example.

Returning therefore to your main question: among the memory assigned to a process there is an area of memory which the process will use for its stack. Its stack pointer will point into that area. Switching from one process to another involves saving the whole state of the old process *including the stack pointer* and loading the whole state of the new process *including the stack pointer*. Because there is no special stack as such, on process termination everything is simply forgotten: nothing else needs to be done.
> 3 votes

# Answer
Each process has its own stack, its own stack pointer, and so on. They are at independent locations. So whatever happens with Process A has no effect on Process B.
> 1 votes

# Answer
The operating system assigns memory space to each process. The memory space is assigned to real memory, or to swap space, or when not used at all not represented anywhere. Memory space is virtual, so multiple processes can have what looks like the same address space.

Each process is responsible for how its address space is used. So if multiple processes each have a stack, each process is responsible for its stack and doesn't care about others at all. The operating system doesn't care about any of the stacks. The operating system just makes sure that each process can access its address space and nothing else.
> 1 votes

---
Tags: operating-systems, memory-management, virtual-memory, stacks
---


# Question
Title: Complete proof of PAC learning of axis-aligned rectangles
I have already read PAC learning of axis-aligned rectangles and understand every other part of the example.

From *Foundations of Machine Learning* by Mohri, 2nd ed., p. 13 (book) or p. 30 (PDF), I am struggling to understand the following sentence of Example 2.4, which is apparently the result of a contrapositive argument:

> ... if $R(\text{R}\_S) \> \epsilon$, then $\text{R}\_S$ must miss at least one of the regions $r\_i$, $i \in \[4\]$.

i.e., $i = 1, 2, 3, 4$. Could someone please explain why this is the case?

The way I see it is this: given $\epsilon \> 0$, if $R(\text{R}\_S) \> \epsilon$, then $\mathbb{P}\_{x \sim D}(\text{R}\setminus \text{R}\_S) \> \epsilon$. We also know from this stage of the proof that $\mathbb{P}\_{x \sim D}(\text{R}) \> \epsilon$ as well. Beyond this, I'm not sure how the sentence above is reached.

# Answer
> 1 votes
Let $R\_S, R\_T$ denote the sample rectangle (smallest consistent rectangle) and the target rectangle correspondingly. Since $R\_S\subseteq R\_T$, $R(R\_S)\le \mu\left(R\_T\setminus R\_S\right)$. The intuition behind taking strips of mass $\epsilon$ around the edges of $R\_T$ is that you want to satisfy two conditions:

1. The strips, $r\_1,...,r\_4$ should have large enough mass so that with high probability $m(\epsilon)$ samples do not miss them (this would follow from a simple bound for a geometric random variable).
2. The strips should have small enough mass, so that if all were seen by the samples, then $R\_T\setminus R\_S\subseteq \bigcup\limits\_i r\_i$, where the latter union has small probability thus bounding $R(R\_S)$.

Your question is settled by the geometric argument in the second point. If all strips were seen by the samples, then we can only err on points in the strips.

---
Tags: machine-learning
---


title: When and Why do I Rehash?

text:
# Question
Title: When and Why do I Rehash?
I am studying hashing and reading the part of universal hashing. I have read that I want to draw a hash function from universal hash families when I rehash. When and why do I rehash?

One reason to rehash seems to be load factor or hash table size. When I want to lower the load factor and increase hash table size, then I need to rehash. Any other reasons, especially in real database development? Thanks!

# Answer
One example is consistent hashing. The usual scenario used for motivation is assigning files to servers. To avoid having too many files associated with a single server, you map $n$ files to $m$ servers via some hash function $h:\[n\]\rightarrow\[m\]$. Suupose you add a new server or that an existing server crashes, then you would have to rehash all the files to maintain functionality (this entails actual copying of the contents). One solution that avoids this is mapping each file and sever to the unit circle, and associating each file with the first server met when moving anticlockwise. If $h:\[n\]\cup\[m\]\rightarrow \left\\{(\cos t,sin t)| 0\le t\le 2\pi\\}\right\\}$ satisfies SUHA, i.e. $h(i)$ is uniformly distributed on the unit circle when $i$ is uniformly distributed over $\[n\]\cup \[m\]$, then the expected number of files moved after a crash is $\frac{n}{m}$.
> 2 votes

---
Tags: algorithms, hash
---


# Question
Title: Union of every language within group of decidable languages is also decidable?
So I was trying to solve following exercise:

Let $(L\_{i})\_{i \in \mathbb{N}}$ be a family of decidable languages - this means that every $L\_{i}$ is decidable. Then $\cup\_{i \in \mathbb{N}}L\_{i} $ is also decidable. Right or wrong?

The solution states, that this statement is wrong because we can set $L\_{i}:=\\{f(i)\\}$ with $f : \mathbb{N} \rightarrow H\_{0}$ and will therefore receive $\cup\_{i \in \mathbb{N}}L\_{i} = H\_{0}$. At the same time $L\_{i}$ languages are still decidable, for every $i \in \mathbb{N}$ because they are finite.

However I still struggle to understand how exactly a language can be decidable with $f : \mathbb{N} \rightarrow H\_{0}$, because I thought that $H\_{0}$ was not decidable.

Thanks in advance!!

# Answer
You don't define $H\_0$. Presumably it's an undecidable set.

First, $f : \mathbb{N} \to H\_0$ only means that all the values of $f(x)$ are in $H\_0$, i.e. the image of $f$ is a subset of $H\_0$: $f(\mathbb{N}) \subseteq H\_0$. The proof of the counterexample involves a stronger property: it constructs a function $f$ whose image is exactly $H\_0$, that is, $f(\mathbb{N}) = H\_0$.

Second, the image of a recursive set by a recursive function is not necessarily recursive. It's obviously recursively enumerable, by definition of “recursively enumerable”: if $g$ is recursive, then it's partial recursive, and $g(\mathbb{N})$ is a recursively enumerable set. But $g(\mathbb{N})$ might not be recursive. For example, consider a function $g$ whose input is an encoding of a program (that doesn't take arguments) and an integer: $g(\langle P,n\rangle)$ which runs $P$ for $n$ steps and returns $\langle P\rangle$ if $P$ terminates in less than $n$ steps and $0$ otherwise. The function $g$ is recursive (its definition is an algorithm to run it), but its image is the set of encodings of terminating programs, which is not decidable. Coming back to our original problem, it's possible to have a recursive $f$ such that $f(\mathbb{N}) = H\_0$ but $H\_0$ is not recursive.

Third, $f$ might not be recursive anyway. (And if you apply the previous paragraph, you'll notice that it can't be recursive if $H\_0$ is not recursively enumerable.) All you know is that there exists a function $f$ such that $f(\mathbb{N}) = H\_0$. An example of how to define this function is: $f(x) = x$ if $x \in H\_0$ and $f(x) = h\_0$ if $x \notin H\_0$, where $h\_0$ is the smallest element of $H\_0$. This is a perfectly good mathematical definition, but it isn't an algorithmic definition: since $H\_0$ isn't decidable, there's no algorithm to choose between the case $x \in H\_0$ and the case $x \notin H\_0$.

Intuitively speaking, to decide whether $x \in \bigcup\_{i\in\mathbb{N}} L\_i$, you need to figure out which $i$ to check, then check whether $x \in L\_i$. But there's no reason why there would be an algorithmic way to pick $i$. (And to make things worse, $x$ might be in multiple $L\_i$, possibly infinitely many — but the proposed property is wrong even if the $L\_i$ are disjoint, as seen with the example of singletons which can easily be renumbered to make them distinct and therefore disjoint.)
> 1 votes

---
Tags: undecidability, halting-problem, finite-sets
---


title: change turing machine to RAM

text:
# Question
Title: change turing machine to RAM
How can we convert a given Turing Machine into a Random Access Machine? I understand that we can use the transition function to come up with a sort of algorithm but how can we translate all of it into a set of instructions (load/add etc).

For example, here's a TM:

```
M = ({q 0 , q 1 , q accept , q reject }, {0, 1}, {0, 1, t}, δ, q 0 , q accept , q reject )

```

having a transition function as follows:

Now, how can I formulate a set of RAM instructions from this?

Sample Solution:

# Answer
> 1 votes
You can implement, on a RAM machine, an interpreter that simulates the behavior of an arbitrary Turing machine (that's just a matter of programming, and there's nothing conceptually interesting or difficult about it); then use it on this particular Turing machine. That's much easier to do, but might not lead to nice code for the RAM machine.

Or, you can understand/reverse-engineer the algorithm the Turing machine is using (this could be difficult), and then figure out how to implement that algorithm on a RAM machine (which is just a matter of programming once you understand the algorithm).

Asking "how do I write code on a RAM machine?" is not very different from "how do I write code in assembly language?"; you just do it, and there's not a lot of deep scientific or conceptual ideas needed, once you know what algorithms you are using.

---
Tags: formal-languages, turing-machines, computability, church-turing-thesis
---


# Question
Title: Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable?
I want to ask if $\\{w|\forall x\in T(M\_v):|w|\>|x|\\}$ is decidable if v is a Index of a random but fixed Turing Machine with $|T(M\_v)|\<\infty$.

My idea: It is co-semi-decidable since as soon as i find an $x\in T(M\_v)$ with $|x|\geq |w|$ I have shown that this sepcific w is not in the set. I think it aint semi-decidable, since there can always be an $x\in T(M\_v)$ which is longer than w. Therefor i also think the problem ist undecidable.

Do i oversee something ?

# Answer
Yes, you are missing something.

The first argument that this language is co-semi-decidable is correct. However, the second one is wrong (and not formally written. A formal proof could not consist of such arguments, they are only for intuition usually).

Now to show why it is fully decidable: We know that $|T(M\_v)|=c\<\infty$. Now, since this is a constant smaller than infinity, there must be an $x\_0\in T(M\_v)$ for which $|x\_0|$ is the longest from the words in $T(M\_v).$

Now, build the turing machine that accepts $w$ iff $|w|\>|x\_0|$.

Since $x\_0$ is the longest, then if $|w|\>|x\_0|$ we will have that $\forall x\in T(M\_v):|w|\>|x\_0|\ge|x|$ and thus $w$ is in your language. Now, if $|w| \le |x\_0|$, then obviously $w$ is not in your language.

Thus $w$ is in your language iff $w$ is accepted by the turing machine we built.
> 1 votes

---
Tags: undecidability, decision-problem, semi-decidability
---


title: running RAM on a given input

text:
# Question
Title: running RAM on a given input
I understand how RAM commands work but I am unable to understand how we use a given input string and find the output. For instance,

there's a Random Access Machine which has an input {0,1}\*. The program logic is as follows:

1: read

2: store 1

3: read

4: add 1

5: read

6: add 1

7: load 1

8: if a=2 go to 11

9: print 0

10: goto 12

11: print 1

12: end

Now, on the input tape we have i=11101011. How can I find the content of the output tape? What's the approach?

When we see read, do we only read the first character? If yes, then what exactly do we add 1 to? Is the output also supposed to be in binary?

# Answer
Check your definitions. Often the convention is "input is the contents of memory positions 0 to $n$", result might be e.g. accept if register 0 is non-zero when the RAM halts.
> 1 votes

---
Tags: complexity-theory, turing-machines, computability, finite-automata, church-turing-thesis
---


# Question
Title: Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)
language = arbitrary word followed by exact same arbitrary word = u * u (with u being out of non-empty words of alphabet {0, 1} )
(sorry for the formatting, see screenshot-link for conventional/clear expression)

The purpose is to prove that the given language is not a context-free-language (using the pumping lemma).

So i thought that this language should definitely be pumpable, since you can choose x and z as corresponding parts in one of the u/"halves". So if word to be pumped is "0101" then you choose e.g. x=1 (0**1**01) and z=1 (010**1**) and the remaining parts that stay static are assigned with u=0 (**0**101), y=0(01**0**1), and v=empty.
If pumped zero-times/i=0 word reads: 00
i=1: 0101
i=2: 011011
i=3: 01110111
(and so on)

(For more complicated words you would need to use all three (u, y, v), but the basic principle would still be that x and z are assigned corresponding parts of the word and u,y,v would be assigned the remainder. (This doesn't work for the extremely small words 00,01,10,11 that would become empty when zero-pumped, but as long as the exceptions are finite / of finite/fixed number this isn't a problem AFAIU.)
Clearly this is wrong, but can anybody explain *how/why*?

# Answer
Some strings in your language are pumpable, others aren't. You have to look for one that isn't pumpable. Use the fact that the relevant piece is of limited length.

In your case, say the pumping length is $N$, and take $\sigma = 0^N 1^N 0^N 1^N$. You'll find that however you position the part that gets pieces repeated, you won't be able to increase the first *and* second stretch of $0$ or of $1$, or get the correct repeat by pumping around one of the $0/1$ boundaries.
> 1 votes

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


title: Algorithm to find all connected objects

text:
# Question
Title: Algorithm to find all connected objects
I'm creating a webapplication in which I render multiple objects using Three.js. These objects are saved in a list and can be connected to each other (but don't have to be), and when they are, they are rendered next to each other.

The user can select an object in this list using the UI that I made.

An example of how the objects can be positioned is in the image below. When I select the most left object I want the whole chain to be rendered, but not the 'singular' objects that are in the same list.

I hope this is clear enough, if not I will gladly elaborate.

Now the problem that I'm having:

The (simplified) list can look like this:

```
  {
    id: 1,
    connectedObjects: [{ id: 2 }, { id: 5 }],
  },
  {
    id: 2,
    connectedObjects: [{ id: 1 }, { id: 3 }],
  },
  {
    id: 3,
    connectedObjects: [{ id: 2 }, { id: 4 }],
  },
  {
    id: 4,
    connectedObjects: [{ id: 3 }],
  },
  {
    id: 5,
    connectedObjects: [{ id: 1 }],
  },
  {
    id: 6,
    connectedObjects: [],
  },
  {
    id: 7,
    connectedObjects: [],
  },
  {
    id: 8,
    connectedObjects: [],
  },
];

```

Now I want to write an algorithm that checks which objects are all in the same 'group' as the selected object. So the last three (6, 7, 8) will not be rendered.

This is in JavaScript but if someone points me in the right direction with some pseudocode or a general idea that would be great!

# Answer
Thanks for your answers!

I looked into both connected components in an undirected graph and the Disjoint set and went for the latter.

After researching this dataset I found a few packages that provided an implementation, but I used this one:

> https://github.com/nawatts/disjoint

I'm a junior developer and haven't really come in contact with this kind of problems so your points in the right direction are very much appreciated.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Resetting Vector clocks in distributed systems
I understand that vector clocks are preferred over lamport clocks because sometimes lamport clocks cannot account for the casuality and we use extra space to store the timestamps in the vector clocks. What i dont understand is about the resetting of the vector clocks. Why do the vector clocks overflow and how the resetting is done in such scenario?

# Answer
Vector clocks overflow for the same reason that regular integers do. Vector clocks generally maintain a fixed number of bits per process to capture the event count for each respective process. There is naturally a maximum value that each of these bit strings can represent. Any one of these values can potentially be increased beyond their capacity, and thus overflow. For example, if we presume that one process has the following vector clock:

$\vec{P3} = (5, 3, 7) = (101\_2, 011\_2, 111\_2)$

And then $P3$ has an internal event, increasing their event count from 7 to 8:

$111\_2+1=000\_2$

This number is too large to be represented with only 3 bits. And so the clock overflows back to zero. This will prevent us from properly computing causal ordering in this system, and undermines the consistency of the distributed system.

We can of course allocate many bits to each process to reduce this risk. However, since the vector clocks are regularly passed between processes, we would like to minimise this since it reduces the throughput of communication channels (regardless of whether it is a network, file, shared memory etc).

Therefore we require a mechanism to safely reset clocks within the system, such that we can maintain the constraints of the distributed algorithm. From my understanding this can be done in a few ways:

**Blocking Globally**

If a process detects that its own counter is about to overflow, it sends a message to every other process informing them to reset their event count for that process on their local clocks. This will halt the distributed algorithm until the process that initiated the reset receives confirmation from every other process.

**Consensus Protocols**

Depending on how the distributed algorithm is structured, we may not require the full event history to ensure causal ordering for events. Some distributed algorithms have *rounds of consensus* which allow us to repeatedly incrementally work from a point of stability. These are like rounds in a card game, and offer natural opportunities to reset clocks. This is particularly true of Gossip algorithms. This is very similar to the global blocking algorithm above, but does not wait until an overflow to reset clocks.

---

There might be some other vector clock reset mechanisms that I am not aware of. It is also possible to organically grow the number of bits used per process as required (which might actually be easiest).

You can read more on these topics with the following academic papers:
> 2 votes

---
Tags: distributed-systems, clocks
---


# Question
Title: determining timeouts / retry attempts in distributed systems
**Is there a methodical procedure for determining the optimal timeout / retry strategy for dealing with a remote server that handles processes responses for requests, given some probability distribution of response time?**

For example, suppose I have a client program which requests a web page from some server, and I know roughly the probability distribution of its response time, e.g. 95% of the time I'll get a response with a gamma distribution, and 5% of the time my request will get lost and a response never sent. So maybe 80% of the time I'll get a response within 100 milliseconds, and 90% of the time I'll get a response within 500 milliseconds.

On one hand, I could set a timeout of 500 milliseconds and retry with another request after then. Or I could set a timeout of 100 milliseconds. A longer timeout means I have more chance of success, but I have to wait longer. A shorter timeout means I can reduce my wait time potentially, at the cost of increasing the chance of failure (I give up too early; the server will respond). Or I could just send two identical requests up front and take whichever response arrives first -- this seems like it might be the optimal strategy, but something seems wrong here. (why then wouldn't I send 100 identical requests? I guess I'm not modeling the fact that lots of additional requests would clog the server queue.)

Please help; I know this is a fairly general question, but I have no idea where to look for more information of this type. I never took any classes on distributed systems in college + am trying to improve responsiveness of a client program.

# Answer
> 1 votes
The simplest solution I have found to this problem is using **rolling percentile latency**. The optimal timeout will shift based on hardware, network configuration and the state of the operating system. Therefore it cannot be fixed/established beforehand, but approximated at runtime. The typical practice in industry is to maintain P95 and P99 response times. These are durations in which 95% and 99% of requests complete respectively over some time duration. So you could perhaps store the last hour of request times, and if the current request is longer than 95% of the others in the last rolling 60 minutes, then you deem that a timeout.

This will adapt and gradually become more strict if response times are fast, and more lenient if they become slow.

You can read more about percentile latency here.

---
Tags: optimization, distributed-systems
---


# Question
Title: How much space an ascii character really takes on a 64 bit word addressable memory?
I know that an ASCII character needs 1 byte of memory for storage, but if a computer uses a 64-bit word addressable memory does it mean that the character actually takes 8 bytes even when only 1 byte was needed?

Does being a 64-Bit word addressable memory mean the same as being a 64-Bit machine?

# Answer
It depends. A program can store 1 ASCII character in each 64-bit word, or 8 ASCII characters in each 64-bit word. It's up to each individual program to decide how it wants to store and format its data in memory. The latter would probably be more typical.
> 1 votes

---
Tags: computer-architecture, memory-management, memory-hardware, memory-allocation
---


# Question
Title: Can User Level Thread read/write Kernel thread?
As far as I read in a OS text book (Operating Systems by Silberschatz) Kernel mode is for privileged task, so it it true to claim that "*User Level Thread can read/write Kernel threads*" ?

Generally speaking, Is there any kind of protection between user and kernel level threads?

# Answer
No. In most operating systems, kernel memory is protected using virtual memory mechanisms, so a user process cannot read or write to kernel memory.

A user thread is part of a user process, and has the same permissions as the process. So, a user thread will not be able to write to kernel memory.
> 3 votes

# Answer
Im not really sure, but this is my take on trying to guess what it could be from logical reasoning

---

* A thread is a specific type of process. Generally speaking, any process in user mode will not be able to do any Kernel-mode operation.
* However, threads have a shared memory system, and they don't know about each other (pipes between threads are a 3rd party communication through an "imaginary" file) and thus there should be no constraint on using the memory within a User-mode thread, even if it is shared with a Kernel-mode thread.
* Its impossible to create a thread with Kernel-mode if you are in User-mode, but if you are in Kernel-mode you can change your privileges to be User-mode. Kernel code is usually trusted, and therefore creating a thread in User-space for a Kernel-mode process is *probably* still considered trusted.

So my **guess** is **No,** there is no protection.
> 1 votes

---
Tags: operating-systems, threads, os-kernel
---


title: Approximate bin-packing?

text:
# Question
Title: Approximate bin-packing?
Let $X\_1,...X\_n$ denote some bins, and $w\_1,...w\_m$ some positive real numbers, where $m \in \mathbb{N}$, and the order matters, so e.g. we can't switch the position of $w\_n$ and $w\_1$. The goal is to take a subset of $\\{w\_1,...w\_m\\}$ and assign it for each bin, i.e. $\\{w\_1,...w\_{i1}\\}$ would go to bin 1, $\\{w\_{i\_1+1},... w\_{i\_2}\\}$ would go to bin 2,...$\\{w\_{i\_{n-1}+1},...w\_{m}\\}$ would go into bin $n$, such that each bin contains "roughly" an equal sum of $w\_i's$, e.g. the sums for $X\_1,...X\_n$ could approximately equal $100$, so $X\_1$ could have a sum of 104, $X\_2$ could have a sum of 97,... etc. Let's say this "equal sum" is $Z$.

Letting $Y\_i$ be the sum for each $i^{th}$ bin, is there a way to choose Z such that the error is minimized, error being defined as $\sum\_i |Y\_i-Z|$, where $1 \leq i \leq n$?

# Answer
> 1 votes
I assume you want to put items $w\_1$ to $w\_{i\_1}$ into the first bin, $w\_{i\_1+1}$ to $w\_{i\_2}$ into the second bin, etc. etc. The number n of bins is given. This can be done with something similar to dynamic programming.

Examine all possible choices for $\_1$ and calculate the error from bin 1 for each of these choices.

Then examine all possible choices for $i\_2$. For each $i\_2$ pick all possible $i\_1$ and pick one where the total error from bin 1 and bin 2 is as small as possible. For each $i\_2$, remember which $i\_1$ was used with it.

Then examine all possible choices for $i\_3$ etc. For $i\_n$ there is obviously only one choice, and you have the solution.

You will notice that you make quite a few stupid choices. If you have 10 bins, X = 100, and the sum of weights is 1,000 then puting items with very little weight or total weight over 200 into the first bin is likely stupid. To help with this we find a non-optimal solution with a greedy algorithm. Then we don't accept anything that must be worse than the greedy algorithm. In the example, if the greed algorithm finds a solution with error = 100, then we would never put less than 50 or more than 150 in weight into the first bin.

---
Tags: algorithms, combinatorics, packing
---


title: Dataset of Hard Instances of SUBSET-SUM

text:
# Question
Title: Dataset of Hard Instances of SUBSET-SUM
I know for factoring we have the RSA Numbers, in which factoring one of them quickly (usually) indicates a breakthrough in the field. However, I want to know if there's something similar for SUBSET-SUM, in which there are hard instances that if solved, would be a "big deal"? I found this, but they don't seem to be unsolved.

One way would to take the RSA numbers, convert them to 3-SAT, then convert to SUBSET-SUM, but the weights generated are very large. Maybe there's a way to convert FACTOR (the special case of two prime factors, to be specific) directly to SUBSET-SUM without having to go through 3SAT (not the main question; just a thought)?

For the RSA numbers in particular, we know how long each non-trivial factor is: $\frac k2$, where $k$ is the number of bits of the number $n$. Maybe we can use that to shrink the number of variables to only $n$, without having to make extra variables and unnecessarily fill the problem with "junk".

# Answer
> 0 votes
Note that FACTOR isn't known to be NP-complete.

---
Tags: subset-sum
---


# Question
Title: Use of pumping lemma for not regular languages. (Proof Verification)
$L=\\{w \in \\{0,1,a\\}^\* | \\#\_0(w) = \\#\_1(w) \\}$

We show that L is not regular by pumping lemma.

We choose w=$0^p 1^p a$

|w| = 2p+1

Now |xy| has to be $\leq p$

So x and y could only contain zeros. And $z=1^p a$

$xy^iz= 0^p 1^p a$

Now let i = 0

$xy^0z=0^{p-|y|} 1^p a$

Now hence $p-|y| \neq p$ this choice of i would lead to a word that is not in L. So we can not pump y and stay in the language.

So L is not regular.

I'm trying to learn the usage of the pumping lemma. Is my proof correct?

Any suggestions are welcome. Thanks!

# Answer
Use your freedom to pick a string to work with. The string $0^p 1^p$ is all around nicer.

Assume $L = \\{ w \in \\{0, 1, a\\}^\* \colon \\#\_0 w = \\#\_1 w \\}$ is regular, so it satisfies the pumping lemma. Let $p$ be the constant of the lemma, we know $p \ge 1$. Pick $w = 0^p 1^p$, so $\lvert w \rvert = 2 p \ge p$, by the lemma there is a division $w = x y z$ with $\lvert x y \rvert \le p$ and $y \ne \varepsilon$ so that for all $k \ge 0$ the string $x y^k z$ belongs to $L$.

What does the above tell you about $x, y, z$? Can you derive a contradiction by picking e.g. $k = 0$? You finish it off.
> 0 votes

---
Tags: pumping-lemma, check-my-answer
---


title: PageRank vector

text:
# Question
Title: PageRank vector
I computed the PageRank vector for the example given in https://en.wikipedia.org/wiki/PageRank (where the picture shows that node B ends up with a score of 38.4, node C with 34.3, node D with 3.9). I implemented the PageRank algorithm, but my numbers are slightly different: 39.8 for node B, and 36.1 for node C, 3.5 for node D, etc). I was wondering if anyone could simulate and obtain the same results they have. My question is what algorithm was used to obtain their numbers.

My algorithm is as follows. Starting with the uniform distribution $r$, I did power iteration using the equation $r = Ar$, where $A = 0.85 M + 0.15 J$, $M$ is the transition matrix of the Web graph given in the example, and $J$ is the matrix whose every entry is $1/N$ ($N=11$ is the number of nodes).

# Answer
I fixed it and I am now getting the same numbers as in their example. Earlier, I used the equation $r=(0.85M+0.15J)r$ to update $r$, and at the end of each iteration I would scale $r$ so that it sums to $1$. This scaling is necessary because the Web graph can have dead ends, in which case the components of $Mr$ need not sum to 1 even if the components of $r$ sum to 1. Now, I compute the first term $0.85Mr$, and then I redistribute the remaining pagerank (of $1$ minus sum of components of $0.85Mr$) evenly among all the nodes. The latter algorithm distributes the pagerank among all the nodes slightly more uniformly.
> 0 votes

---
Tags: data-mining
---


# Question
Title: Is this a known problem in graph theory?
My basic problem includes a graph where each node $i$ is associated with a weight $c\_i$, and the problem is to find a minimum (or maximum) weighted independent set with a fixed cardinality $p$. This is I believe a well-known problem in graph theory that is well-studied for different types of graphs.

Now, suppose I am dealing with a generalized form of the problem as following. The weight of each node can take $p$ different values, that is each node is associated with $p$ different weights. The aim is again to find a minimum (or maximum) weighted independent set with a fixed cardinality $p$, however, each type of weight can be selected only once. Precisely, if the weight type $j$ is selected for the node $i$, i.e., we select the weight $c\_{ij}$, then the other selected nodes cannot take a weight of type $j$.

My question is that, is this still a graph theory problem? Is it a known generalization in the graph theory problems?

Any help and/or reference is appreciated.

# Answer
If $G=(V,E)$, with $V=\\{v\_1,v\_2,...,v\_n\\}$ and weights $\\{c\_{i,j}, i=1,2,...,n, j=1,2,...,p\\}$ is the given graph, then we can construct the **strong product** (I finally found the name of the operation) $G\boxtimes K\_p$ of $G$ and $K\_p$, where $K\_p$ is the complete graph with $p$ vertices. This is the graph with vertices $\\{v\_{i,j},i=1,2,...,n, j=1,2,...,p\\}$ and edges $\\{v\_{a,b},v\_{c,d}\\}$ where either:

1. $a=c$,
2. $b=d$ or
3. $\\{v\_a,v\_c\\}\in E$. (The actual condition of the strong product reduces to this since in $K\_p$ all vertices are adjacent).

We give the vertex $v\_{i,j}$ the weight $c\_{i,j}$, for $i=1,2,...,n$ and $j=1,2,...,p$.

The problem on $G$ is equivalent to the problem **minimum (maximum) weighted independent set** in the weighted $G\boxtimes K\_p$. If a vertex $v\_{i,j}$ of the new graph is chosen this corresponds to choosing vertex $v\_i$ of the original graph and using the $j$-th weight $c\_{i,j}$ corresponding to it.

The set of edges of $G\boxtimes K\_p$ are exactly those that prevent the corresponding choices in $G$ to use adjacent vertices or reusing weights with the same index:

* Condition $1$ defines edges in the strong product that prevent the equivalent of using two weights from the same original vertex.
* Condition $2$ prevents using the weights with the same index from different vertices of the original graph.
* Condition $3$ prevents that two vertices that were neighbors in the original graph are selected.

**Example:**

If $G$ is the graph

and $p=2$, then $G\boxtimes K\_2$ would be the graph

Images created with this tool.
> 2 votes

---
Tags: graphs, weighted-graphs, set-cover
---


# Question
Title: Is it possible to construct a finite state automata for a decimal adder?
Suppose the strings are of the form x#y#z , where x,y,z are strings formed from the alphabet $\Sigma=(0,1,2,3,4,5,6,7,8,9)$ . The language is accepted if x+y=z is satisfied, for example : 56#65#121 is accepted, but 2#97#104 is not. Is it possible to find a finite automata for such a language ? I cannot fathom how decimal addition could be carried out using a DFA .

# Answer
> 5 votes
Interestingly, the question in the body has a negative answer, but the question of the title has a positive answer, if you choose the appropriate representation for the data.

Let me explain this for a binary adder (I let you generalize the argument for a decimal adder). First represent the numbers $x$ and $y$ to be added in reverse binary, with a final $0$ and make sure they have the same length by adding further $0$'s at the end if needed.

For instance, $22 = 2 + 4 + 16$ would be represented by $011010$ and $13 = 1+4+8$ by $101100$. Their sum $35 = 1 + 2 + 32$ is represented by $110001$. Now, just read this data column by column \begin{matrix} 22 \to &0&1&1&0&1&0\\ 13 \to &1&0&1&1&0&0\\ 35 \to &1&1&0&0&0&1 \end{matrix} to get $(0,1,1)(1,0,1)(1,1,0)(0,1,0)(1,0,0)(0,0,1)$. Taking all representations of the triples $x, y, z$ such that $x + y = z$, you get a regular language on the alphabet $\\{0,1\\}^3$, recognised by the following automaton

The trick behind this representation is that addition can be obtained by a sequential transducer.

# Answer
> 1 votes
Definitely, this language is neither a regular language that can be accepted by FA nor a context free language that can be processed by PDA. This fact can be proved easily by pumping lemma.

This language is only a context sensitive language and can be accepted by a LBA (linear bounded automaton) or standard turing machine.

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


title: Why don't passwords prove P != NP?

text:
# Question
Title: Why don't passwords prove P != NP?
Pardon my ignorance on the matter but,

Verifying passwords = Polynomial (linear)

Guessing passwords = Exponential

Since each guess has nothing to do with one another, exponential time is best possible time (but verifiable in linear time).

# Answer
The main problem with your argument is that guessing a completely unknown password doesn't fit in the framework of P vs NP. P and NP are classes of **decision problems**. This means that you are given an input and you have to answer "yes" or "no". For example, in the Hamiltonian graph problem you are given a graph and you answer either "this graph is Hamiltonian" or "this graph is not Hamiltonian". There is also **no hidden information**. If you answer "no", I can't suddenly say "aha, there is an additional edge in the graph that I didn't tell you about, which makes it Hamiltonian, so you're wrong". Guessing a password doesn't have a yes-no answer and it involves hidden information, so it's not a decision problem.

Maybe you are thinking of some interpretation of password guessing that is a decision problem. If so, you should clarify what you mean.
> 4 votes

# Answer
You just need a mathematical proof that cracking a password cannot possibly done in polynomial time. The only evidence is “all these clever people tried, and they did not succeed”, which is the exact same situation as for P≠NP.
> 0 votes

# Answer
Problems in complexity theory have to **scale** with respect to some parameter. A 9x9 Sudoku for example can be solved by brute forcing all solutions - this in itself is not an exponential algorithm until we measure its growth with respect to $n$.

Back to your problem. Suppose we phrase the problem of guessing passwords as a decision problem. What is your input to describe a particular instance of the problem, if not the password itself?

Now suppose again we have the password is fixed with the problem statement. For example, one could have the password be digits of $\pi$, and the input is the length $n$. Well, there always "exists" a non deterministic Turing machine that can simply output that string without calculuation as well.

This just sheds some light on NP hardness. This link provides you with a definition of P, NP and NP-hardness.
> 0 votes

---
Tags: np-complete, decision-problem, complexity-classes, p-vs-np
---


title: Go-Back-N Protocol not efficient?

text:
# Question
Title: Go-Back-N Protocol not efficient?
Let's say we have five packets

> p1 p2 p3 p4 p5

to be sent sequentially:

and for some reasons, p3 got delayed so it the the last packet to arrive recevier.

so below is the receiving order on the receiver's end

> p1 p2 p4 p5 p3

and according to the Go-Back-N Protocol, the receiver will only send acknowledge of `p2` when it receive `p5`.

then the receiver receives `p3` right after `p5`, and then it sends acknowledge of `p3` to the sender.

But there will still be a timeout and the sender still has to re-send `p4` and `p5`,even though the receiver did receive all packets, isn't this Go-Back-N Protocol really inefficient?

# Answer
> 1 votes
The Go-Back-N protocol is often presented for didactic purposes as a first, maybe crude attempt at tackling loss of packets or of order in connection-oriented communications, without obeying the constrains of Stop-and-Wait protocols, also introduced for didactic purposes. It is no wonder it appears inefficient -- it probably was never meant to be so. Selective Repeat can be considered as a performance improvement in terms of retransmissions over Go-Back-N, and in practice TCP itself relies on a hybrid solution of the two.

---
Tags: computer-networks, tcp
---


title: Big O notation, code time complexity

text:
# Question
Title: Big O notation, code time complexity
does appending an element to a list through a for loop work in O(1) time or O(n) time? In addition, what is the time complexity does "".join that list into a string work in?

# Answer
> 1 votes
It totally depends upon the particular implementation. In linked-lists which support circularity (where the first element, possibly a sentinel, links back to the last one) the task can indeed be achieved in $O(1)$ time, for it requires fetching a pointer to the tail of the list; on the other hand, on implementations which do not support doubly-linked elements or other fancy mechanisms, a full iteration to the back of the structure might be necessary, thus requiring $O(n)$ time.

On a side note, the term list refers to an ADT (Abstract Data Type), which is merely a type coupled with a set of operations and specifications. Thus, the term list does not inherently have to be linked to the pointer-based implementation; in fact, an ADT implementation such as Java ArrayList may be also realized on arrays, giving a random-access time complexity on any location (including the tail) in $O(1)$ time.

# Answer
> 0 votes
For the first question, based on the fact that you're appending using a **for loop** it implies that you're doing it in O(n) since you'll loop at most n times where n is the current length of the list.
The time complexity for "".join() in Python is O(len(list)) since it'll have to iterate through the list once while creating the string.

---
Tags: time-complexity
---


# Question
Title: Is there any consequence to the existence of $\mathsf{PSPACE}$-complete sparse language like with Mahaney's theorem?
Mahaney's theorem states that the existence of $\mathsf{NP}$-complete sparse language would lead to $\mathsf{P = NP}$. Is there any result result regarding the same for the complexity class $\mathsf{PSPACE}$, like "if there is a $\mathsf{PSPACE}$-complete sparse language, $\mathsf{PP = PSPACE}$" or the same for any other complexity class within $\mathsf{PSPACE}$?

# Answer
A quick result is that $PSPACE=\Sigma\_2$.

First show that $PSPACE\subseteq P/Poly$, and as a result $PSPACE\subseteq \Sigma\_2$ (If finding an entry of a computation table is in P/Poly, then it is also in $\Sigma\_2$, since we can guess a circuit and locally verify its correctness as described here).

To see why having a PSPACE-complete sparse language $S$ puts PSPACE in P/poly, given $L\in PSPACE$, let $f$ be a reduction from $L$ to $S$. Note that if $|f(x)|$ depends only on $|x|$, then $L\in P/Poly$ since we can concatenate the circuits for $f$ and for $S$ (which is in P/Poly due to being sparse). To overcome the fact that $f$ might vary in the output's length for same input size, note that on length $n$ inputs $f$ can produce output of length $\le n^c$, so given $x$ we can take as a hint all $|x|^c$ circuits for $S$ on input sizes $0,1,...,|x|^c$. Among these circuits, we have the "right" circuit which is able to determine the membership of $f(x)$ to $S$.
> 1 votes

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Probability of winning a turn-based game with a random element
I am preparing for a programming exam on probability theory and I stumbled across a question I can't solve.

Given a bag, which contains some given amount of white stones $w$ and some given amount of black stones $b$, two players take turns drawing stones uniformly at random from the bag. *After each player's turn a stone, chosen uniformly at random, vanishes, and only then does the other player take their turn.* If a white stone is drawn, the player, who has drawn it, instantly loses and the game ends. If the bag becomes empty, the player, who played second, wins.

What is the overall probability that the player, who played second, wins?

I assume it's a dynamic programming question, though I can't figure out the recursion formula. Any help would be greatly appreciated. :)

**Example input**: $w$ = 3, $b$ = 4, then the answer is, I believe, 0.4, which I arrived at after computing by hand all possible ways for the game to go, so not very efficient.

# Answer
> 1 votes
Let us denote by $\Pr(w, b)$ the probability of P2 winning given its their turn and there are $w$ white stones and $b$ black stones remaining and similarly we write $\overline\Pr(w, b)$ for the probability of P2 winning given it is P1's turn.

From the rules of the game we get that any of the following cases can occur in P2's turn (assuming that enough stones are left):

1. White is drawn and P2 loses. This happens with probability $w / (w + b)$.
2. Black is drawn and a white stone vanishes. The probability for this is $b / (w + b) \cdot w / (w + b - 1)$.
3. Black is drawn and a black stone vanishes. We find the probability for this to be $b / (w + b) \cdot (b - 1) / ( w + b - 1)$.

If it is P1's turn to play we find similar cases:

1. White is drawn and P2 wins. This happens with probability $w / (w + b)$.
2. Black is drawn and a white stone vanishes. The probability for this is $b / (w + b) \cdot w / (w + b - 1)$.
3. Black is drawn and a black stone vanishes. We find the probability for this to be $b / (w + b) \cdot (b - 1) / ( w + b - 1)$.

We can now factor $\Pr$ and $\overline\Pr$ using our case distinctions and some simple probability theory: $$ \begin{align\*} \Pr(w, b) &= \Pr(\text{Case 1.2}) \cdot \overline\Pr(w - 1, b - 1) + \Pr(\text{Case 1.3}) \cdot \overline\Pr(w, b - 2), \\ \overline\Pr(w, b) &= \Pr(\text{Case 2.1}) + \Pr(\text{Case 2.2}) \cdot\Pr(w - 1, b - 1) + \Pr(\text{Case 2.3}) \cdot \Pr(w, b - 2) \end{align\*} $$ Note that we can combine these 2 equations to find a recursive formula for $\Pr$ (which I will not type out here for brevity). Coupling these with the initial values $\Pr(w, b)$ where $w + b \leq 4$ (which can be precomputed) will give us an algorithmic way to find the desired probability.

---
Tags: dynamic-programming, probability-theory
---


# Question
Title: The meaning and relevance of the locution ''no terminating implementation'' in type theory
In the context of a discussion of Haskell https://stackoverflow.com/questions/62509788/the-intuition-behind-the-definition-of-the-co-reader-monad, I was told that

> There is no terminating implementation for the polymorphic type $(e \to a) \to a$

and that we couldn't have a function of type $((e \to a) \to a) \to e$ or a function of type $(r \to x) \to x$, for these would not be ''implementable''.

These types are well formed in the STLC, in the sense that we can construct them using the rules of type-formation. And I don't see why we can't form lambda terms of this shape, such as $\lambda c\_{((a \to t) \to t)}. \\, b\_a$, or $\lambda p\_{e \to a}.\\,b\_a$.

What is therefore the problem? Specifically, what is a ''terminating implementation'' in the context of the STLC? I believe this relates to the fact that $(e \to \bot) \to \bot$ is not constructively equivalent to $e$, but I would appreciate if someone could spell this out for me.

# Answer
You can *always* inhabit a type by a free variable: the type $\tau$ is inhabited by the free variable $x\_\tau$. When people speak about "implementation" of a type they mean a *closed term*, i.e., one without free variables. The examples you gave contain free variables, namely $b\_a$.

In *pure* simply-typed $\lambda$-calculus all terms are "terminating" in the sense that the calculus is strongly normalizing, so whatever reductions you take they will always lead to the (unique) normal form.

In $\lambda$-calculus extended with recursive definitions (such as Haskell) we can inhabit every type $\tau$ with a closed term, for instance in Haskell the type `t` is inhabited by `a` defined as

```
a :: t
a = a

```

Once we have recursive definitions, it is easy to write closed terms that do not terminate (or do not have a normal form).
> 7 votes

---
Tags: lambda-calculus, type-theory, functional-programming
---


# Question
Title: Combinatorial Problem similar in nature to a special version of max weighted matching problem
I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem.

I have a general graph $G(\mathcal{V},\mathcal{E},\mathcal{W})$. I want to find a maximum weight matching of the graph $G$ that must cover a certain subset of vertices and has a specific size. For example, if I have a graph with eight vertices, I want to find a max weighted matching that must cover the subset of vertices $\mathcal{V}'=\\{1,2,3\\}$ and the size of the matching is $\lceil{|\mathcal{V}'|/2}\rceil$. So one more vertex needs to be chosen that maximizes the weighted matching. How to find the optimal solution in polynomial time if possible?

# Answer
Maximum Weight Matching algorithms are incremental, so to achieve a maximum weight matching of a bounded size, just stop after so many iterations. To achieve the other constraint, For each terminal vertex in $\mathcal{V}'$, increase the weight of each incident edge by a huge constant amount $U$. Try to prove that this answers your question (note that edges incident to two terminals have to be increased twice to keep the total increase constant in all valid solutions).

**Note.** It might help in the proof to distinguish different cases according to the size of $\mathcal{V}'$ compared to $k$ (the size of the matching).
> 0 votes

---
Tags: combinatorics, traveling-salesman, matching
---


# Question
Title: Conditions for string substitution commutativity
Let's say I have two substitutions given \[a:=b\] and \[c:=d\]. What are some conditions that hold for a,b,c,d ∈Σ\* iff forall s∈Σ\* s\[a:=b\]\[c:=d\]=s\[c:=d\]\[a:=b\]

Also you can assume that a,c≠ but you cannot assume so for b and d.

# Answer
It's really simple. Just build two finite state transducers A and B , one for each substitution, then perform their composition A○B and B○A check if they are equivalent. Checking equivalence of transducers is undecidable, but in this case the transducers should be functional and equivalence in this special case is decidable.
> 0 votes

---
Tags: formal-languages, substrings, string-matching
---


# Question
Title: Algorithmic problem of regular, context-free, and recursively enumerable languages
Consider a language $L\_1$ that is recursively enumerate, $L\_2$ that is regular, and $L\_3$ that is context-free.

Are the following problems algorithmically decidable?

1. Is $L\_1 \cap L\_2 = L\_3$?
2. Is $L\_1 \cap L\_3 = L\_2$?

I think problem 1 is undecidable since $L\_1 \cap L\_2$ is a recursively enumerable language it can be expressed as a Turing machine and since $L\_3$ is context free it can be expressed as a Grammar or Turing machine. Since we cannot determine the equivalence of two Turing machines, the problem is undecidable.

I think problem 2 is also undecidable for similar reasons, only the right hand side ($L\_2$) is regular instead of context-free.

Am I correct?

# Answer
Both questions are undecidable. Notice that the empty language is both regular and context-free. Thus we can state that the problem of determining if $L\_1 \cap L\_2$ is context-free is at least as hard as determining if $L\_1$ is context-free (and similarly determining if $L\_1 \cap L\_3$ is a regular language is at least as hard as determining if $L\_1$ is a regular language). By Rice's Theorem any non-trivial property about a Turing-Machine is undecidable and thus your two questions are undecidable.

For a detailed proof/answer to your second question look at this post. IT shows how you would apply Rice's Theorem in your cases.
> 1 votes

---
Tags: formal-languages, turing-machines, regular-languages, context-free, undecidability
---


# Question
Title: Is this applet implementation for the Go-Back-N ARQ protocol correct?
I was reading a textbook describing the Go-Back-N (GBN) protocol with Finite State Machines as pictured below:

$\Lambda$ just means "initial state" or "no action", depending on the context. My questions are

1. This is the interactive animations link to GBN https://media.pearsoncmg.com/aw/ecs\_kurose\_compnetwork\_7/cw/content/interactiveanimations/go-back-n-protocol/index.html. Let's say we are sending packet 0, packet 1 and packet 2, and packet 1 is lost beforen it arrive receiver. So when it is timeout, GBN will make sender re-send packet 1 and packet 2, And I found an interesting thing which is,if you try the link with above scenario and you send packet 3 just before timeout occurs,this action reset the timer, because you can see the timeout is postponed(otherwise you will see packet 1,2,3 flying in screen).But according to the sender's FSM, after you send packet 3, timeout occurs immediately, then the sender will re-send packet 1 and packet 2, but it didn't happen as timeout is postponed, which contradicts the fact that time is only get reseted when `base = nextseqnum`?
2. On the receiver's FSM, why it needs to set `expectedseqnum = 1` and make a packet based on it? why we cannot set `expectedseqnum = 0` as the only initialized action?

# Answer
> 1 votes
I'll address question 2 first, since it seems easier than the other one. The answer is simply because both transmitters begin tagging their payload messages from `1`, namely with `nextseqnum = 1`; you can see this is so for the sender from the top-left corner of the image you posted. Don't be misled by the fact that the receiver issues the `sndpkt = make_pkt(0, ACK, checksum)` at the outset; that first packet is only crafted, but not sent (it would if the receiver hit the `default` state). On the other hand, there might be an inconsistency in the way the applet enumerates its packets, since it starts from `0`.

---

Question 1 seems to ask: if a sequence of packets `0`, `1`, `2` is sent and

* Packet `1` is lost
* A new packet, `3`, is sent just before the timeout

then no timeout occurs, although no instruction seems to be encoding for that. Although I counted the passing of time with my hands, your observation seems to be correct: given the above conditions, upon sending a new packet, the events associated with a timeout do not manifest. This could be due to a small bug in the applet, although I would ascertain more before contacting the book authors.

> which contradicts the fact that time is only get reseted when base = nextseqnum?

Beware! The timer is also reset upon receiving an acknowledgement that is not the last one, as shown at the bottom of Figure 3.20. However, I do not think your experiment is affected by this behavior since the triggering conditions aren't met.

---
Tags: computer-networks, tcp
---


# Question
Title: When is Huffman code the most unoptimal?
By giving an Huffman coding tree and the total frequency of the characters. how can I find the most unoptimal frequencies for each character such that the size of the code will require the most possible of bits?

# Answer
There are several definitions of "unoptimal".

As vonbrand noted, Huffman coding falls back to binary encoding if all frequencies are equal.

For longest code length, this happens if the frequencies are Fibonacci numbers.

For worst compression rate compared to the entropy, this happens with an alphabet of two symbols where $p\_0 = \varepsilon$ and $p\_1 = 1-\varepsilon$. The Shannon entropy approaches $0$ bits per symbol as $\varepsilon \rightarrow 0$, but any Huffman code requires $1$ bit per symbol.

For size of the Huffman tree, there is no "worst case", because the size is the same no matter what the frequencies are. For an alphabet of $n$ symbols, the Huffman tree must have $n$ leaves and $n-1$ branches.
> 1 votes

# Answer
All frequencies the same. Thus there is no space for compression.
> 0 votes

---
Tags: huffman-coding
---