# Question
Title: Partitioning bag of sets such that each set in a group has a unique element
Suppose I have a bag (or multiset) of sets $S = \\{s\_1, s\_2, \dots, s\_n\\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one element not found in any other set in that group. Formally, the criterion for a group $G = \\{g\_1, g\_2, \dots \\} \subseteq S$ is:

$$\forall i: \left(g\_i \setminus \bigcup\_{j\neq i} g\_j\\;\neq\\;\emptyset\right) $$

The partition $P = \\{\\{s\_1\\}, \\{s\_2\\}, \dots\\}$ always satisfies this requirement, so there is always a valid solution. But what is the smallest number of groups needed? Is this problem feasible or NP-complete?

Another formulation of this problem is to partition a multiset of integers into groups such that each integer has a bit set in its binary expansion that no other integer in its group has set.

# Answer
> 2 votes
It is NP-hard. Here is a reduction from a variant of vertex cover:

> Given a graph $G$ with $n$ vertices and a positive integer $k$ **where $n+k$ is even**, determine whether there is a vertex cover with size $k$.

This variant is also NP-complete.

Given an instance graph $G$ with $n$ vertices $v\_1,\ldots,v\_n$ and $m$ edges $e\_1,\ldots,e\_m$, as well as an integer $k$, we construct $nm+1$ elements $x\_{11},\ldots,x\_{1m},\ldots,x\_{nm},y$. We define $U=\\{x\_{11},\ldots,x\_{1m},\ldots,x\_{nm},y\\}$ for convenience. Also,

* For each vertex $v\_i$, we construct a *vertex set* $S\_i=U\backslash\\{x\_{i1},\ldots,x\_{im}\\}$.
* For each edge $e\_j=(v\_{i\_1},v\_{i\_2})$, we construct an *edge set* $T\_j=(U\backslash\\{x\_{i\_11},\ldots,x\_{i\_1m},x\_{i\_21},\ldots,x\_{i\_2m},y\\})\cup\\{x\_{i\_1j},x\_{i\_2j}\\}$.

We ask if $\\{S\_1,\ldots,S\_n,T\_1,\ldots,T\_m\\}$ can be partitioned into $(n+k)/2$ groups such that within each group each set has at least one element not found in any other set in that group.

If there is a vertex cover with size $k$, say without loss of genrality $\\{v\_1,v\_2,\ldots,v\_k\\}$, then the partition can be $\\{S\_1,T\_{c(1,1)}, T\_{c(1,2)},\ldots\\}, \ldots, \\{S\_k,T\_{c(k,1)}, T\_{c(k,2)},\ldots\\}, \\{S\_{k+1},S\_{k+2}\\},\ldots,\\{S\_{n-1},S\_n\\}$ where $v\_i$ covers $e\_{c(i,1)}, e\_{c(i,2)}, \ldots$ (if $v\_i$ and $v\_{i'}$ both cover an edge $e\_j$, we arbitrarily allocate $T\_j$ to one of the groups containing $v\_i$ and $v\_{i'}$.)

On the other hand, if there is a $(n+k)/2$-partition, we can always adjust it to the form above without increasing the number of groups, thus obtain a vertex cover with size at most $k$. First, we observe that

1. If a group contains at least two vertex sets, then it cannot contain any other set. We call such group a *vertex group*.
2. If a group contains exactly one vertex set $S\_i$, we call it a *mix group*. Moreover, if this group contains at least two edge sets, then the edges corresponding to the edge sets in this group must all be incident to the vertex $v\_i$. (If a group contains exactly one vertex set $S\_i$ and one edge set $T\_j$, and the edge $e\_j$ is not incident to the vertex $v\_i$, we call such group a *bad* group.)
3. If a group contains no vertex set, then there exist at most two vertices such that each edge corresponding to an edge set in this group must be incident to one of the two vertices. We call such group an *edge group*.

The adjustment is roughly described as follows:

1. We arbitrarily choose two bad groups $\\{S\_i,T\_j\\},\\{S\_{i'},T\_{j'}\\}$ and regroup them as $\\{S\_i,S\_{i'}\\},\\{T\_j,T\_{j'}\\}$. We repeat this process until there are at most one bad group.
2. If there is still a bad group $\\{S\_i,T\_j\\}$, suppose $e\_j$ is incident to $v\_{i'}$, then consider the group containing $S\_{i'}$. There are two cases:

1. This group is a vertex group, say $\\{S\_{i'}, S\_{i''}\\}$. Then we regroup these sets to $\\{S\_{i'},T\_j\\}$, $\\{S\_i,S\_{i''}\\}$.
    2. This group is a mix group. Then we simply move $T\_j$ to this group.

After the adjustment above, there is no bad group any more.

3. For each group containing no vertex set, due to Observation 3, there are two vertices $v\_i,v\_{i'}$ such that each edge corresponding to an edge set in this group is incident to at least one of $v\_i,v\_{i'}$. For convenience, we denote respectively by $\mathcal{T}\_i$ and $\mathcal{T}\_{i'}$ the edge sets with corresponding edges incident to $v\_i$ and $v\_i'$ (one edge $e\_j$ may be incident to both $v\_i$ and $v\_i'$, we arbitrarily allocate $T\_j$ to one of $\mathcal{T}\_i$ and $\mathcal{T}\_{i'}$). Consider the group(s) containing $S\_i$ and $S\_{i'}$. There are four cases.

1. $S\_i$ and $S\_{i'}$ belong to the same group, then we regroup these sets to $\\{S\_i,\mathcal{T}\_i\\},\\{S\_{i'},\mathcal{T}\_{i'}\\}$.
    2. The two groups are both vertex groups, say $\\{S\_i,S\_{i''}\\},\\{S\_{i'},S\_{i'''}\\}$. We regroup these sets to $\\{S\_i,\mathcal{T}\_i\\},\\{S\_{i'},\mathcal{T}\_{i'}\\},\\{S\_{i''},S\_{i'''}\\}$.
    3. The two groups are both mix groups, we then simply move $\mathcal{T}\_i$ to the group containing $S\_i$, and $\mathcal{T}\_{i'}$ to the group containing $S\_{i'}$.
    4. One is a mix group (say the group containing $S\_i$) and the other is a vertex group (say $\\{S\_{i'},S\_{i''}\\}$). We then move $\mathcal{T}\_i$ to the group containing $S\_i$ and regroup remaining sets to $\\{S\_{i'},\mathcal{T}\_{i'}\\},\\{S\_{i''}\\}$.

After these adjustments, there are only vertex groups and "good" mix groups. The vertices corresponding to the vertex sets in these "good" mix groups form a vertex cover.

As a result, the decision version of your problem is NP-complete.

---
Tags: complexity-theory, np-complete, sets, partitions
---


# Question
Title: Does quantum computing convert any O(2^n) algorithm into a polynomial running time and how?
For example, if it is a $ O(2^n) $ algorithm that loops through 0 to $ 2^n - 1 $ and check whether the number of 1 bits is divisible by 3, 5, 7, 9, 11, does quantum computing reduce it to non-exponential time and how?

# Answer
> 3 votes
No it does not. I mean probably. Because no-one really knows.

What do I mean by we don't know? We're not even 100 % sure whether P=NP or not and if it does, sure a quantum computer can solve any NP problem in polynomial time, same as a deterministic Turing machine.

However we assume that is not the case and we also expect the classes of NP and BQP (bounded-error quantum polynomial-time) to overlap, but each may contain problems the other one does not (i.e. neither contains the other). If NP contains something BQP does not, it surely has to be at least all NP-complete problems, including the TSP you mentioned in one of your comments. With these assumptions quantum computer cannot solve TSP in polynomial time (even with a given probability).

What we do have right now is Grover's algorithm, which provides quadratic speedup for black-box problems. Which means if the best we can come up with is brute force in $O(2^n)$ steps, Grover can solve it in $O(2^{(n/2)})=O(\sqrt{2}^n)$ steps *with a given probability*. That is it gives a quadratic speed-up, not exponential.

---
Tags: quantum-computing
---


# Question
Title: Question for "Only if" part for the theorem "A language is Turing-recognizable iff some enumerator enumerates it."
I am trying to prove the theorem

> A language is Turing-recognizable iff some enumerator enumerates it.

I proved the "if" part, but I have no idea of proving the "only if" part, so I searched a proof for the "only if" part of this theorem. In the proof that I found, it says

> Let $\sum$ be the alphabet of the Turing machine $M$, and let $s\_1$, $s\_2$, ... be a list of all possible strings of $\sum^{\*}$. We define the enumerator $E$ as follows:
> 1. Run $M$ for $i$ steps on each input $s\_1$, $s\_2$, ... , $s\_i$.
> 2. If any computation of $M$ accepts, print out the accepted string.

In this proof, I can't understand why do we need to run $M$ for only $i$ steps. I think the number of simulation steps may not be enough to simulate strings. Is it guaranteed that simulating $M$ finishes in $i$ steps?

# Answer
In slightly more detail, what's happening is:

1. Run the machine on input $s\_1$ for one step. If it accepts, list the string.
2. If the machine didn't halt on the previous step, run the machine on $s\_1$ for one more step and then on $s\_2$ for a step. As before, if the machine accepts either string, list them and remove them from consideration.
3. Do the same thing on $s\_1, s\_2, s\_3$.
4. Continue forever.

This process, called *dovetailing*, will eventually list all and only those inputs which the TM will accept.
> 2 votes

# Answer
A language is *Turing-recognizable* (or *Recursively enumerable*) *iff* there exists a *Turing Machine* which will enumerate all valid strings of the language.

What you probably miss in the above proof is the fact that $i$ can take any value ... when we say $i$ steps, we can mean $10$, $100$, $100000$, $\infty$ steps. Basically $i$ is an index that indicates the number of words in the language; the enumerator $E$ could very well run forever (if the language has an infinite number of strings).
> 1 votes

---
Tags: turing-machines
---


# Question
Title: How to prove LastToken problem is NP-complete
Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding one token to some neighboring node. The LastToken problem asks whether, given a graph $G$ and an initial number of tokens $t(v) \ge 0$ for each vertex $v$, there is a sequence of moves that results in only one token being left in $G$. Prove that LastToken is NP-complete.

I'm learning how to prove NP-complete recently but having trouble to understand the concept of NP. As far as I know, to prove a problem is NP-complete, we first need to prove it's in NP and choose a NP-complete problem that can be reduced from. I'm stuck on which NP-complete problem that can reduce to my problem. As I interpreted this is sequencing problem and I'm guessing I can either reduce Ham Cycle or Traveling Sales Man to my problem, but I don't see any connection between them so far. How should I start a good approach?

# Answer
> 2 votes
Here is a reduction from the Hamiltonian path. Given a graph $G=(V,E)$. Add a vertex $v\_0$ to the graph and connect it to all vertices in the graph. Set $t(v\_0)=2$. Set $t(u) = 1$ for all $u \neq v\_0$.

Claim. The previous reduction is correct. Try to prove it formally as an exercise.

**Edit.** Here is a brief proof of correctness. We have to prove that the created instance is a yes-instance of your problem, if and only if the given instance is a yes-instance of the Hamiltonian path problem. First, let $G$ be a yes instance of the Hamiltonian path. Let $v\_1, \dots v\_n$ be a Hamiltonian cycle in the graph. Now we describe a winning strategy for the last-token, where in the step $i$ we take two tokens from the vertex $v\_{i-1}$ and add one to the vertex $v\_{i}$. It is easy to prove by induction, that in step $i+1$ all vertices $v\_0, \dots v\_{i-1}$ have no tokens in them, the vertex $v\_i$ has two and all vertices $v\_{i+1}, \dots v\_n$ have exactly one token. In the $n-th$ step we take the two tokens left in $c\_n$ and put one token in $v\_0$ and we are done. Note that $v\_i$ has always a common edge with $v\_{i+1}$ since the are consecutive in a Hamiltonian path.

On the other hand, assuming the reduced instance is a yes-instance, we prove that the given graph is Hamiltonian. Since all but one vertex have exactly one token. We have only one choice for the first vertex. In each step we take two tokens from a vertex and add a token to another one. It is easy to prove inductively that in each step all but at most one vertex have at most one token in them. One vertex can have two tokens wich is the only choice for the next step. Using this claim, it is also easy to prove that to vertex can be chosen twice. Hence, if we were able to choose $n+1$ vertices, we must have a permutation of the $n$ vertices with $v\_0$ starting in $v\_0$ and this permutation must be a Hamiltonian path since we always have an edge between two consecutive choices in the game.

# Answer
> 0 votes
The Above answer works in its entirety to add to it, think of a situation where we have a no instance of the hamiltonian path problem. Then some node must be visited more than once, this collides with the inductive step of our yes instance as we must eventually give a value 1 to a node with 0. we then will have nodes with all 0's and 1's and will not be able to take from any node on the graph we, therefore, will have to claim no on our last token problem.

---
Tags: complexity-theory, np-complete, decision-problem
---


# Question
Title: What is the relation between a programming language and the language of its input?
I find some references say that

> all the features of programming language fall within what can be captured by context-sensitive grammars. In fact, no programming language known to humankind anything that cann't.

and

> Actually, most of programming language is context-free language.

Q1: Are the claims correct? I did not find some bibiographies about a precise description or even a proof.

Let $\Gamma$ be the alphabet of the instructions of a programming language. Given a specific procedure $P$, all of its control flows belong to $L\_{P}$. $L\_{P}$ describes how does it control its data.

At the same time, for every $x \in \Sigma^\*$, $P$ computes it and gives an output $P(x)$. Assume that $P$ is used to slove a decision problem, i.e., $P(x) \in \\{ 0,1 \\}$. There is a language $L'\_{P} = \\{ x \in \Sigma\* \mid P(x) = 1 \\}$. If we regard $P$ as a machine, $L'\_P$ describes the computational power of $P$.

It is obvious that $L\_P$ and $L'\_{P}$ are totally different.

Q2: What is the relation between $L\_P$ and $L'\_{P}$? Is there a conclusion such that $$L\_P \in CFL \Leftrightarrow L'\_P \in CFL$$ or $$L\_P \in CSL \Leftrightarrow L'\_P \in CSL$$

# Answer
There is no interesting relation between a programming language (the set of words which are syntactically valid programs) and the set of words that are accepted by a program written in said programming language.

Note that it is possible to design a Turing powerful programming language which, as a formal language, is the set $1^\* = \\{\epsilon,1,11,111,\ldots\\}$.

Still, program $1^n$ will accept a language $L\_n$ which is completely unrelated to $1^\*$. Indeed, by Turing completeness, for any r.e. language $A$ there is some $n$ such that $A=L\_n$.

The crucial aspect to consider here is the semantics of the programming language, the way we map each program $1^n$ to its behavior, and ultimately to the set of accepted words $L\_n$. Even if $1^\*$ is a very simple language, the semantics can still make it Turing powerful, so that $L\_n$ can be any r.e. language.
> 2 votes

---
Tags: formal-languages, context-free, programming-languages, context-sensitive
---


# Question
Title: Why is the assignment rule the way it is in Hoare Logic?
Why is the assignment rule the way it is in Hoare Logic/Axiomatic Semantics? I can't wrap my head around why the assignment rule is backwards from what I expected.

I understand Hoare logic is use to prove formal propositions of the state of a program as commands are executed. Thus, if we execute the command $$x:=e$$ I would have expected that the **next** state has such substitution...but it seems the substitution happens **before** we execute the assignment which I find bizzare. I would have expected:

$$ \\{ P \\} x:= e \\{P\[e/x\]\\}$$

Given that $P$ are statements about the program state.

I'm sure there is a good explanation for this and sorry if this is a basic question, I know it must be. But can someone explain it to me?

---

Bonus Question:

Why don't we write the assignment rule as:

$$ \\{ Q \\} x:= e \\{Q\[x/e\]\\}$$

note its NOT the same as my original suggestion because we have the $x$ and $e$ swapped around. i.e. in the post condition wherever we have an $e$ we place an $x$ (which is fine because the statement we just execute is that $x$ holds the value of $e$, so we should be able to replace $e$ for $x$ in the post condition if the pre condition help.

---

Related posts that I've read that have not helped:

---

Appendix:

For us dyslexics, in this question this is what the substitution notation means:

$$ P\[e/x\] = P\[e \to x\] $$

i.e. replace every free occurrence of $x$ with expression/term/thingie $e$.

# Answer
> 3 votes
So after reading and thinking about it more this is my explanation (thanks software foundations):

The key confusion for me seems to be the meaning of $P\[e/x\]$ (replaces every free instance of x with e). What this does is wherever you see the symbol $x$ literally remove it and place $e$. e.g. $ P\[e/x\] = (x+y+1)\[e/x\] \to P\[e/x\] = (e+y+1)$ so notice how $x$ literally disappeared from $P$. So what we want is once we do the assignment:

$$ x:= e$$

that the statement is true if we had $x$ instead of $e$. So if the rule is:

$$ \\{ P\[e/x\] \\} x:= e \\{ P \\}$$

then what we want is, when we plug $x$ for $e$ we want the statement in consideration to be true. So before we started the code we have $P\[e/x\]$. Then we run the assignment and all instances of $e$ disappear and we get $x$'s to replace them. That **must** be true if the code that ran was assignment (since $x$ now hold the value $e$, so you can remove $e$'s and place $x$).

Thats the explanation of the abstract concept. Lets (shamelessly) use the software foundations (SF) example:

> {{ Y = 1 }} X ::= Y {{ X = 1 }} In English: if we start out in a state where the value of Y is 1 and we assign Y to X, then we'll finish in a state where X is 1. That is, the property of being equal to 1 gets transferred from Y to X.

Another useful paragraph from SF:

> Similarly, in {{ Y + Z = 1 }} X ::= Y + Z {{ X = 1 }} the same property (being equal to one) gets transferred to X from the expression Y + Z on the right-hand side of the assignment. More generally, if a is any arithmetic expression, then {{ a = 1 }} X ::= a {{ X = 1 }} is a valid Hoare triple.

---

Addendum from comment's great observation:

> it is important to recognize that the rule { P \[ e / x \] } x := e { P } allows both the expression e and the variable x to occur in the postcondition. In other words, the inference rule allows you to deduce a postcondition in which any subset of the occurrences of e in the precondition have been replaced with x , including none of them. Moreover, it allows you to deduce all of these different postconditions simultaneously.

---

Reply to bonus why is

1) $ \\{P\[e/x\]\\} x:=e \\{P\\} $

better than

2) $ \\{ Q \\} x:=e \\{Q\[x/e\]\\} $:

Besides the subtle point of replacing x with expressions that might be invisible (e.g. e=0, should we replace $0$ with an infinite number of $x$'s? What if the zeros are not there...the rules should be syntactic but I think it's better to avoid such confusions), I think this is the reason:

> What the rule of assignment should capture is that we are assigning the expression e to the variable x. Thus, only x should be "replaced" by e. Intuitively, in the code (or more precisely the state of the program $\sigma$) when x starts holding the value e, it doesn't randomly mean that everywhere where there might be an e it becomes x after executing the assignment $x:=e$. In fact what it does mean is that now in the post condition we have x's. Now those x's if we did not have the assignment should have the value of $e$ i.e. we only "undo" the replacement/assignment the assignment command did. Not every other random expression e. In short, the only way to know where to place the correct e's is by starting in the post condition after the assignment has been done, then starting from there place e's. If we do it backwards we might be replacing e's we didn't want to replace (even if they were probably true, which I guess they should since we are saying x holds the value e after assigning e to x).

# Answer
> 2 votes
Assume we are running program `x := e`, and let $\sigma$ be the initial state, and $\sigma'$ be the final state.

The crucial intuition here is: the value of $x$ in the *final* state $\sigma'$ is the same as the value of the expression $e$ in the *initial* state $\sigma$. Indeed, the latter is the value we assign to $x$ with the command `x := e`.

Hence, if $P(-)$ is a property on values, the formula $P(\mbox{$x$-in-the-final-state})$ is equivalent to $P(\mbox{$e$-in-the-initial-state})$. In other words $P(x)$ in the *postcondition* (in state $\sigma'$) is really equivalent to $P(e)$ in the *precondition* (in state $\sigma$).

Using the substitution is only a more formal way to consider the postcondition as a "formula which depends on $x$", i.e. as $P(x)$, and then requiring $P(e)$ as precondition.

---
Tags: programming-languages, logic, semantics, software-verification, hoare-logic
---


# Question
Title: Sequential subsequence removal with arbitrary predicate
I want to extract sub-sequences from a sequence of float values. The "scale" and range of these values is arbitrary (as I can manipulate it at will) but the "shape" is consistent.

For a visual example:

I want to extract the above five stacks as five "chunks". I want them in the order they occur (left-to-right). Do not be too distracted with the visual, though, as there can be an arbitrary number of points within the interval, but guaranteed $N\_{points} \< 2000$.

I have tried framing this problem as a dynamic partitioning problem, as an iterative subsequence extract problem, and something like $argmax$ but applied multiple times on a shrinking sequence.

Please pardon the ambiguity; I am struggling to even articulate the problem in a useful fashion. Critique and guidance would be much appreciated

# Answer
> 1 votes
Set *threshold* to, say 30 (arbitrary value greater than noise in the plot) and start from left to right, if value is greater than threshold, keep it as *run* \- collect data to temporary array, if values drop below threshold then discard data and create new array for another run.

This will cut 5 bars and discard data between, if you want to keep data, you have to decide the shape (divide evenly between bars, keep it to left or to right).
It may happen that data drops below threshold in the bar (not visible in plot), then keep counter of dropped values, if it is small, add them to last run.

# Answer
> 1 votes
Use changepoint detection. This will identify the boundaries between the clusters.

---
Tags: arrays, partitions, subsequences, space-partitioning
---


title: Triangulation of disjoint line segments

text:
# Question
Title: Triangulation of disjoint line segments
Given a set of disjoint line segments in the plane, prove (or disprove) that you can always join the line segments to make a near-triangulation where the vertices are the endpoints of the segments, the outer face is a cycle and every segment is an edge of the triangulation.

# Answer
> 1 votes
This task interested me, at least in non-degenerate case. I've tried to google it and suddenly found a beautiful approach described here (starts with "Next, the constraints are added to the Delaunay triangulation...", but we don't care about Delaunay here).

Name the set of segments $S$. First, forget about segments and build *any* triangulation $T$ of all endpoints of $S$. Then repeat the following process for all segments one-by-one:

If $e \in T$, we are done with this step. Otherwise, remove all edges of $T$ having an interior intersection point with $e$. One can see that it will unite some triangles of $T$ into *one* polygon. Add $e$ to $T$; it will break this polygon into two smaller polygons. Triangulate them both and add needed edges to $T$.

The key point is that if $e \in S$ was added to $T$, it will never be removed, because segments in $S$ don't have interior intersection points. So, after this process $S \subset T$.

---
Tags: algorithms, graphs, computational-geometry, discrete-mathematics
---


# Question
Title: Algorithm for fewest number of moves with artificial minimum
I asked a question recently, but I need to be able to add an artificial minimum number of steps that can be larger than the Dijkstra minimum.

To summarize, I built an undirected graph with edges representing possible moves of 1's, 10's, 100's, etc to get from one value to another.

```
public static UndirectedGraph<int, IEdge<int>> GetMinimumMovesGraph()
{
    var graph = new UndirectedGraph<int, IEdge<int>>();
    // load a graph that handles bases of 10's up to 10,000
    for (int i = 0;i <= 10000; i++)
    {
        for (int j = i+1; j <= 10000; j++)
        {
            // only add edges if difference is base of 10
            if (j - i == 1 || j - i == 10 || j - i == 100 || j - i == 1000)
            {
                graph.AddVerticesAndEdge(new UndirectedEdge<int>(i, j));
            }
        }
    }
    return graph;
}

```

So, the minimum distance from 46 to 121 is 8 steps/moves:

* add 100 (146) - 1 move
* subtract 10 (136) - 1 move
* subtract 10 (126) - 1 move
* subtract 1 five times (121) - 5 moves

**Let's say the minimum number of steps through the graph has to be greater than 8 e.g. 10, 15, etc.**

For example, a game application could stipulate that you must move at least 11 times in the problem above, so a possible answer could be:

* all steps above (8 moves)
* add 1 - (9)
* subtract 1 - (10)
* add 1 - (11) (we're at the minimum number of moves here, but we're at 122)
* subtract 1 - (12) (correct answer)

So, these "dummy" moves are allowed, but aren't there scenarios where simple dummy moves may outnumber a shorter path to the answer?

I think I found an Eppstein implementation in C# that should give k-shortest paths, but can anyone explain the meaning of the vertices with two letters? e.g. What does the vertex "A,E" mean, and how can it have a single edge between "B,I"?

```
g.CreateEdges("A,E", "B,I", 20, "alpha");

```

**What if I had to specify an odd or even number of moves?**

Can this be done with the existing graph, or is there another graph structure that would support it? Weights, directions? Could I build the graph differently to describe the criteria e.g. not adding edges until certain number of edges exist back to the source, but then I would need Dijkstra on every iteration at build time

# Answer
We construct a directed graph $G'$ with $V'=V \times \\{0, \dots, k\\}$ when $k$ is the lower bound on the path length. For every edge $uv$ in $E$ and $i\<k$ we add $(u,i)(v,i+1)$ and $(u,k)(v,k)$ to $E'$.

Now we search for a shortest directed path from $(s,0)$ to $(t,k)$ in $G'$ to find the shortest path from $s$ to $t$ in the original graph $G$.

The digraph $G'$ has $(k+1)n$ vertices and $(k+1)m$ edges. Hence, the running time is still polynomial

Searching for the shortest odd (or even) path works similarly. Indeed I think that any regular (as in NFA recognizable) constraint on the path can be solved like that.

Edit: Note that the second entry in the tuples stays the same. To be more precise, consider any path $P=v\_0v\_1…v\_kv\_{k+1}…v\_n$ on $G$ with length $≥k$. Then there is a corresponding path $P'=(v\_0,0)(v\_1,1)…(v\_k,k)(v\_{k+1},k)…(v\_n,k)$ on $G'$. Similarly, every path on $G'$ induces a path on $G$.
> 1 votes

# Answer
There is a neat way to solve this with dynamic programming. First of all we can notice that the minimal number of moves will always be at most $9 * \lg(N)$. Let's denote this number as $B$.

Now let's have the a recursive function $f(u, d)$, which returns true or false depending on whether there is a path of length exactly $d$ from $Start$ to $u$ (in our case, $Start$ is the source number):

```
f(u, d) {
   if (u == Start and d == 0) {
       return true
   }

   for (v in adj(u))
       if (d > 0 and f(v, d - 1) == true)
           return true

   return false
}

```

Now to find the answer we can simply check if some of $f(Target, i)$ for $8 \leq i \leq B$, is true. Unfortunately, as it is, the function is exponential, however, we can notice that the result only depends on the pair $(u, d)$. So after computing this value once, we can store it in a $N \times B$ matrix and compute it only once. This idea is known as memoization (you can google it to find more information).

The complexity of the algorithm will be $O(N * \lg(N))$, as every cell of the matrix will be computed at most once.

Another possible approach is to use BFS/Dijkstra on the graph you described but with a tiny difference - we will also add another criteria to the vertices (the parity of the current path). Basically we will have 2 * $N$ vertices and the edges will be constructed like:

```
for u in range(0, 10000)
    for x in {1, 10, 100, 1000}
        v = u - x
        if v >= 0
             add_edge([u, 0], [v, 1])
             add_edge([u, 1], [v, 0])

```

Now if we find the shortest path from \[$Start$, 0\] to \[$Target$, 0\], we will be sure that it has an even length. If we want an odd-length path, we can find the path from \[$Start$, 0\] to \[$Target$, 1\]. Finally, if these paths are too short, we can extend them by adding +1, -1, +1, ... +1, -1. The complexity of this idea will be $O(N)$ if we use BFS.
> 0 votes

# Answer
You can solve your problem using two applications of Dykstra's algorithm. Suppose we want to find the shortest path from $s$ to $t$ with $\ge \ell$ edges. This can be decomposed into a shortest path with exactly $\ell$ edges from $s$ to some vertex $v$, followed by a shortest path from $v$ to $t$ of any number of edges.

So, first build a graph that computes for each $v$ the length of the shortest path from $s$ to $v$ using exactly $\ell$ edges. This can be done by computing the answer for all $v$ for paths with 1 edge, then for all $v$ for paths with 2 edges, and so on.

Second, we'll compute for each $v$ the shortest path from $v$ to $t$. This can be done by running Dykstra's algorithm, starting from $t$, on the reverse of your graph (after flipping the orientation of all edges).

Finally, iterate over all $v$, and sum up the length of the shortest path from $s$ to $v$ and from $v$ to $t$, and take the shortest one found.

The total running time is $O(|V| \cdot |E|)$. The first stage can be done in $O(|V| \cdot |E|)$ time. The second stage uses Dykstra's algorithm, so it can be done in $O(|E| \log |V|)$ time. The third stage can be done in $O(|V|)$ time. The time to do the first stage dominates.
> 0 votes

---
Tags: algorithms, graphs, coin-change
---


# Question
Title: Owned state in MOESI protocol-transitions?
I understand that MESI is a subset of the MOESI cache coherency protocol. But what does the Owned state in the MOESI protocol represent? What are the differences in state transition due to the extra Owned state in MOESI as compared to MESI?

For example consider same cache line in processor P1 is in OWNED state & processor P2 is in SHARED state. What happens when there is a write request to P2?

# Answer
Owned state indicates that the data is shared between multiple caches/memory levels and is modified(by the owner) unlike modified state which indicates that only this cache has the only valid value and has modified the value. This eliminates the need for writing back to the main memory before sharing the data with anyone. Hope that helps.
> 1 votes

# Answer
> For example consider same cache line in processor P1 is in OWNED state & processor P2 is in SHARED state. What happens when there is a write request to P2?

Owned means that the P1 has written to the cache line and it is dirty but not written back to memory. P1 will answer any requests for the current value instead of main memory answering them until it writes it back.

If P2 wants to write it needs to get the E (exclusive) state. So will will (usually) broadcast this on the bus and P1 will then need to write it's value back to main memory, all other processors will invalidate the line and then P1 will be free to take the exclusive state and modify the line.
> 0 votes

---
Tags: computer-architecture, cpu-cache, protocols
---


title: Dijkstra without decrease key

text:
# Question
Title: Dijkstra without decrease key
I was reading through this paper, "Priority Queues and Dijkstra's Algorithm" by Mo Chen et al., which suggests using Dijkstra's without edge relaxation, but to rather to just insert new nodes. Please see the pseudo code listed on the right-hand side below, which is taken from page 16 of that paper.

But to me the code looks wrong. I think the comparison should be

```
k <= d[u]

```

and also the update of the d\[u\] in the next line seems redundant to me. I think the delete-min operation can never return a vertex with distance label k which is strictly less than d\[u\] since whenever a vertex distance pair is inserted into the priority queue the distance array d is updated. Am I correct in assuming that this is a mistake in the paper?

# Answer
You are right. Checking `k < d[u]` is not sufficient and updating `d[u]` on the next line is not necessary.

The check prevents proceeding when the source is picked up from the queue (then `k = 0` and `d[s] = 0`). Also, `d[u]` (`u` is fixed) is monotonically decreasing as loop proceeds, so even though it is updated after `(u, d[u])` is put on the queue, `k >= d[u]` holds when `(u,k)` is picked up from the queue. Moreover, if `d[u]` is strictly smaller than `k` , the element should simply be ignored since it cannot be the shortest path to `u`.

You can change the condition to `k == d[u]` and remove following update to `d[u]`.
> 3 votes

---
Tags: graphs, shortest-path, heaps, priority-queues, dijkstras-algorithm
---


# Question
Title: Validity of self refering state with linear temporal logic 'X' connective
Lets say we have model like the one above or a similar one where a node refers back to itself.

Now let's say if I want to know the validity of the formula:

$M, s\_2 \models Xr$

Will this be valid or not. In my textbook it says :

$\pi \models X\phi$ iff $\pi^2 \models \phi$

If we are starting at state 2 then our path would be $S\_2 -\> S\_2 -\> ...$

So, I'm not sure since state 2 is not actually transitioning to another states like State 0 or 1. Otherwise would transitioning to the same state in a path $\pi$ be enough to satisfy the "X" connective.

# Answer
Your textbook correctly states that

$\pi \models X\phi$ iff $\pi^2 \models \phi$

under the assumption that $\pi$ is a word/trace of the transition system and the characters of the word are numbered starting with 1.

So the question that you should ask is how an infinite trace from state $s\_2$ would look like and then evaluate the formula on that trace. LTL is only defined on infinite traces, so these are the ones that you should be looking at.

Note that checking if

$M, s\_2 \models Xr$

holds does not make sense (in general), as LTL is defined over traces, but from a state in a labeled transition system, there could be multiple traces. So it is not clear what $M, s\_2 \models Xr$ should mean - does it mean that it's defined on *any* trace or *every* trace? This syntax seems to come from computation tree logic (CTL).
> 1 votes

---
Tags: linear-temporal-logic
---


# Question
Title: What's the flaw in the P != NP proof in the article "The Computational Complexity of the Traveling Salesman Problem"
I am reading through some proof of inequality of ***P*** and ***NP*** but they are not accompanied by the flaws in the reasoning so I'm trying to find them by myself, just to see if I'm getting the logic right. As an example I am currently reading this (very short) proof that ***P != NP*** and for me the lack in the argomentation is the following: what the author writes about the algorithm is sacrosanct but does not deny in any way the possible existence of algorithms or tricks that would allow to solve the problem in polynomial time.

Am I right on this one?

# Answer
> 5 votes
Yes, you are right: there are plenty of other possible algorithms the author ignores. Briefly, the author claims that the $\Theta^\*(2^n)$ dynamic programming approach in the paper is nessecary to solve TSP. However, he completely ignores any sort of structure that may or may not exist in TSP instances.

So, we can look at special cases of TSP where we do know that we have special structure to see their argument is insufficient. For a simple example, consider the graph class where there is exactly one tour with cost $X$ and all edges not part of this tour have cost $\>X$. Clearly, we can find a tour in $O(|E|)$ by selecting all edges with cost $\le X$. Note that if the argument of this paper would apply to the general case, it would also apply to this one, so this is a contradiction with his argument. Clearly, even if the claim of the author is correct, he has not proven it.

# Answer
> 1 votes
From the article: "This lower bound is confirmed by the fact that the fastest known deterministic and exact algorithm which solves the Traveling Salesman Problem was first pub- lished in 1962 and has a running-time of Θ∗(2n)".

I very much doubt that anything found in 1962 is the fastest known algorithm for anything. It's a very strong claim with absolutely no evidence. As far as I know, there are algorithms that solve problems with 10 thousands of nodes. So this statement is unacceptable to prove the claim.

But if you prove that the currently fastest known algorithm from 2019 doesn't run in polynomial time, that still doesn't prove anything. Because for P ≠ NP to be true, not only known algorithms but *any* algorithms must run in non-polynomial time.

---
Tags: complexity-theory, p-vs-np
---


title: triangle inequality TSP is NP-complete?

text:
# Question
Title: triangle inequality TSP is NP-complete?
I have been reading online source and it mentioned triangle inequality TSP is NP-complete but without proof. In general, the reduction from HAM-cycle problem to TSP works for asymmetric and symmetric TSP problem. So, I wonder how to start a basic approach to prove triangle inequality TSP is NP-complete.

# Answer
If you accept a proof that TSP without triangular equation is NP-complete then it is easy: If you take an instance of "TSP without triangular equation", then you just add a large enough constant to each edge to get the triangular equation, solve it as an instance of "TSP with triangular equation", and that solves your original problem.
> 1 votes

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


# Question
Title: Can polynomial many-to-one reduction be done to a specific problem instance?
Let's say I reduce the problem $A \in L$ to $B \in K$ , with a function $f: \Sigma^{\*} \rightarrow \Gamma^{\*}$ such that $w \in L \Leftrightarrow f(w) \in K$ . I know if I want to solve $A$, given some polynomial time algorithm for $B$, I just have to transform $A$ to $B$ and solve $B$. So it can be thought as:

> The reduction must be done from arbitrary instance of $A$ to a legal instance of $B$

My question is, do I have to reduce to *arbitrary* instance of $B$ or *some* instance of $B$? I.e. reduction from TQBNF to Generalized Geography is done to some valid graph instance, but there exist many more valid instances of Generalized Geography.

# Answer
> 2 votes
The mapping does not have to be surjective (onto) nor injective (one-to-one). In fact, any problem that can be solved in polynomial time can be polynomial time many-one reduced to any problem that has at least one accepting instance and at least one rejecting instance: just solve the original problem in polynomial time, then return the accepting instance if the original problem was an accepting instance, or the rejecting instance if the original problem was a rejecting instance.

That said, the Berman–Hartmanis conjecture states that all *NP-complete* problems are *polynomial time isomorphic*, meaning that there is a *bijective* polynomial-time many-one reduction between them with a polynomial-time inverse. This is currently an unproven conjecture, and only refers to NP-complete problems.

---
Tags: complexity-theory, reductions
---


# Question
Title: How to convert a centralized algorithm to a distributed algorithm?
Is there any algorithm or procedure to convert a centralized algorithm to a distributed algorithm? Is there any theoretical result or relevant complexity analysis?

# Answer
> 2 votes
Sure. If you have a distributed system with N machines, you can always run the centralized algorithm on machine 1 and let machines 2..N sit idle.

If you're asking whether all sequential algorithms can be parallelized, that's an open question, but it's believed that the answer is no: see the NC complexity class. As Wikipedia states,

> there are probably some tractable problems that are "inherently sequential" and cannot significantly be sped up by using parallelism.

P-complete problems are good candidates for problems that are likely not amenable to speedup by parallelism.

If you're asking whether all algorithms can be made reliable in a distributed system, that is a subtle question that depends on what kinds of failures you are considering. You might look into consensus protocols, state machine replication, and the CAP theorem.

---
Tags: distributed-systems
---


# Question
Title: Weighted Average of Multi-Output Neural Networks
\[1\] discusses how to construct an ensemble of neural networks by giving each network a certain weight $\alpha\_i$: \begin{equation} f\_\mathrm{GEM}(\boldsymbol{x}) = \sum\_{i=1}^N \alpha\_i f\_i(\boldsymbol{x}) \end{equation} where each $\alpha\_i$ is obtained using a correlation matrix which is defined in the following way: \begin{equation} C\_{ij} = E\[m\_i(\boldsymbol{x}) m\_j(\boldsymbol{x})\] \end{equation} where $m\_i(\boldsymbol{x}) \equiv f(\boldsymbol{x}) - f\_i(\boldsymbol{x})$, with $f(\boldsymbol{x})$ being the target function and $f\_i(\boldsymbol{x})$ being the output.

I was wondering how should one compute $C\_{ij}$ when the neural network has multiple outputs. Would one firstly calculate $\boldsymbol{m}\_i(\boldsymbol{x}) \equiv \boldsymbol{f}(\boldsymbol{x}) - \boldsymbol{f}\_i(\boldsymbol{x})$ for all examples and then compute $C\_{ij} = E\[\boldsymbol{m}^T\_i(\boldsymbol{x}) \boldsymbol{m}\_j(\boldsymbol{x})\]$? I tried doing that (with MNIST data) but the accuracy was not better than when taking a simple average of all the networks in the ensemble. I would appreciate any help on this.

\[1\] M. P. Perrone and L. N. Cooper, "When networks disagree: Ensemble methods for hybrid neural networks," in Artificial Neural Networks for Speech and Vision. Chapman and Hall, 1993, pp. 126-142.

# Answer
*Background:* The simplest method of ensembling is to take an unweighted average of the outputs of the ensembles. In general, if you want to use a simple ensemble of neural networks for classification, there are two reasonable options:

1. Average the logits from each model, then apply softmax once to the averaged estimate.
2. Each model applies softmax to get that model's confidence score, then average the confidence scores from each model.

Both are reasonable approaches. Both can be used with multi-class classification: you independently average all the logits or confidence scores for each class separately. You could try both to see which works better. Personally, I would expect option #2 might work better, but the best test is to try them.

*Perrone and Cooper's method:* The framework you summarize generalizes the simple method, from an unweighted average to a weighted average, where the weights are calculated in a particular way. In principle, that theoretical framework can be used for any univariate function, i.e., any function that outputs a real number, as long as we know what the "correct" output is for each instance in the training set.

In the context of multi-class classification with neural networks, you'll only be able to use Perrone and Cooper's method with option #2, i.e., applying it to the confidence scores from the models. You can still use it in a multi-class classification setting straightforwardly, by applying it separately to each class: to get the confidence score of the ensemble for class $c$, take a weighted average of the confidence scores of each model in the ensemble, with weights derived based on the formulas you listed. Basically, for 10-class classification, you treat this as 10 separate univariate functions (each class is treated independently).

*Caveats:* That paper is from 1993. I don't know if it is the best way to create an ensemble of neural networks. For one thing, they appear to be using MSE error as their loss. Early work on neural networks used MSE loss, but since then we have learned that cross-entropy loss typically works a lot better for classification tasks. I am not sure that their method of computing the weights will "play well" with cross-entropy loss. So, it's not clear to me that their method will perform better than a simple ensemble (unweighted average) of models trained with cross-entropy loss. I encourage you to do some experiments before relying too heavily on their approach.
> 1 votes

---
Tags: neural-networks
---


# Question
Title: Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$
> I want to find a Context-Free Grammar for $L:=\\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\\}$

I've tried the following:

$G=(V,\Sigma,R,S)$ with $\Sigma=\\{a,b,c,\lambda\\}$, $V=\\{S,B\\}$, $S=S$ and $$R=\\{S\to \lambda\mid aSc\mid B,\\;B\to bBc\mid \lambda\\},$$ which would output $L:=\\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\\}$, in my opinion. I've tried to test my grammar by applying the rules in different combinations and I didn't spot any error yet.

*So I'm asking myself:*
Is there a way to to see if $L(G)=L$ or do I need to assume, that I've done everything correctly after testing some cases?

# Answer
> 4 votes
1. $S\to\lambda$ is unnecessary because $S\to B$ and $B\to\lambda$.
2. The grammar recognizes the desired language.

You can prove the second assertion pretty easily using induction (for example on the length of the derivation, or the length of the sentence).

You'll probably find it easier to prove two assertions independently:

1. If a sentence is in $L$, then it is in $L(G)$.
2. If a sentence is in $L(G)$, then it is in $L$.

Together, these prove equivalence.

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


# Question
Title: Why does $L = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belong to $\mathrm{P}$?
My professor said that the *non-regular* language $L\_{1} = \\{ 0^n 1^n \space | \space n \in \mathbb{N} \\}$ belongs to $\mathrm{P}$. I do understand that all regular languages belong to $\mathrm{P}$ as it's easy to determine and so can be computed in $\mathcal{O}(n^k)$, but why do most *non-regular* languages not belong to $\mathrm{P}$ but $L\_{1}$ does? Is it also possible to give an example of a language $L$ that does not belong to $\mathrm{P}$?

# Answer
> 7 votes
You can easily write a polynomial-time algorithm to decide $L\_1$ (just count the zeros and check you see the same number of ones), so the language is in $\mathrm{P}$.

Most non-regular languages are not in $\mathrm{P}$ because there are uncountably many languages in total, but only countably many languages in $\mathrm{P}$.

The halting problem is not in $P$. If you want a computable example then, by the time hierarchy theorem, any language that is $\mathrm{EXP}$-complete is not in $\mathrm{P}$.

This answer is intentionally brief because all the things I've mentioned are well-known facts that you should be able to look up, now that you know what to look for. If you need more detail, I suggest asking a new question about that, after checking that we don't already have a question about it.

---
Tags: complexity-theory, time-complexity, regular-languages, finite-automata
---


# Question
Title: How to XOR two binary numbers having different lengths?
If we have:

**x = 1101** and **y = 101**

How to XORing these numbers?

# Answer
There are multiple ways to interpret this XOR.

The most common one is that you XOR bit-wise, and that these strings represent numbers, so adding 0 to the left doesn't change their value.

Then $5 \equiv 101 \to 0101$ and then you XOR bit-wise.

```
x 1101
y 0101
------- XOR
  1000

```

which gives 8, if we are talking about unsigned numbers. However, the above depends on **my** understanding of **your** system. Change the assumptions, change the results.
> 4 votes

# Answer
Look first you should know is your numbers in Signage system value or not if they are in Signage system value you should do some stuff 1\_ your number is positive (it means the last bit is zero such as 101 this number is -3) so in this case if you want to increase the number of bits you should add 1 to last bit . in your case the number 101 turns into 1101 and 1101 xor 101 turns into 1101 xor 1101 and the answer is 0000 2\_ but if your numbers were normal (not in Signage system value mode) very easy you add zero to last bit . in your case 1101 xor 101 become 1101 xor 0101 and the answer is 1000
> 0 votes

# Answer
if x and y are integer values, then

```
int XOR(int x,int y)
{
    return x^y;
}

```

whereas, if x and y are strings, then

```
string XOR(string x,string y)
{
    auto temp= bitset<4>(x) ^ bitset<3>(y);
    string u;
    u=temp.to_string();
    return u;
}

```
> 0 votes

---
Tags: logic, arithmetic
---


# Question
Title: Being a computer organizations and architecture expert
One of the greatest challenge in learning one is how broad the literal computer science is. Just talking about memories and CPUs would just took you to endless adventure of this technology. How does the expert manage to understand all of this if I ever want to be one of them?

Maybe someone ever be on my position, not just want to survive the exam but wanted to be the expert of this field especially on the hardware side and rarely ever grasp all the concepts.

# Answer
> 2 votes
1. Study and practice for years. Years and years.
2. No one understands all of it. Everyone specializes.
3. People get a broad sense of the field, but they don't learn all of it. Then, they learn what they need to know, when they need to know, and only then.

So, keep at it. You can understand enough to be effective, even if you don't know everything.

---
Tags: computer-architecture
---


# Question
Title: Showing that the class of regular languages are closed under merging / modified shuffle
Consider $ab$ and $cd$ which are two words. We merge these two into 6 possibilities: $abcd, acbd, acdb, cabd, cadb, cdab$

So in general, a merge of words/sequences $x, y ∈ Σ∗$ , is a word of length $|x| + |y|$ with both $x$ and $y$ as disjoint subsequences in it.

For two languages $L1$ and $L2$ their merge is defined as the set of all possible merges of two words $x ∈ L1, y ∈ L2$.

So basically, a merge is a modified shuffle and should be of length that of the sum of the length of two languages, and should also be in order (see $ab$ and $cd$ example, as $b$ could not come before $a$).

I was thinking of just connecting the states of all $L1$ and $L2$ but this seems wrong as if you connect them all like a fully connected graph, one can jump and go back which is not acceptable.

What's a basic idea on the construction I could do to prove this?

# Answer
Express the two languages as NFA. Use a product construction. Think carefully about what transitions should exist in the product automaton.
> 1 votes

---
Tags: regular-languages
---


title: Encoding order relations in CNF

text:
# Question
Title: Encoding order relations in CNF
I want convert timetable scheduling problems to SAT problems. Suppose there are $t$ time slots and $c$ classes. I will define $t\times c$ variables $x\_{ij}$, which is true iff class $j$ takes place in time slot $i$. My problem is: suppose there is a constraint that class $a$ takes place after class $b$. How to encode that efficiently in CNF?

# Answer
> 1 votes
Variable $a\_i$ set means class $a$ is in timeslot $i$, with a similar encoding for class $b$. Higher values of $i$ means later time slots. If class $a$ must occur before class b then you need clauses to declare that exactly one of $a\_i$ or $b\_{i+1}$, $b\_{i+2}$ ... is set. You need one such declaration for each $a\_i$ possibility. E.g.

ExactlyOne($a\_1, b\_2, b\_3, b\_4, ...$)

ExactlyOne($a\_2, b\_3, b\_4, b\_5, ...$)

ExactlyOne($a\_3, b\_4, b\_5, b\_6, ...$)

which is efficiently encoded using *commander variable encoding* as described in Efficient CNF Encoding for Selecting 1 to N Objects. The scheme requires $O(n)$ clause growth, unlike the naive encoding method which requires $O(n^2)$ clause growth.

---
Tags: np-complete, encoding-scheme, normal-forms
---


title: Conflict serializibility

text:
# Question
Title: Conflict serializibility
So, the task is to prove the following:

> If S is a schedule containing at most one write action, then S is conflict-serializable.

The answer is yes, but I disagree, because the following schedule contains at most one write action, and is not conflict-serializable:

> R1(A), R2(A), W2(A), R1(A).

Am I completely wrong? Or is the answer wrong?

# Answer
> 1 votes
In transaction theory, it's usually assumed that a transaction reads or writes a same data item at most once. So your schedule is not valid since the transaction 1 reads A twice.

Unfortunately, text books do not always make it very easy to find. Here are some quotes I can find.

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman "Concurrency Control and Recovery in Database Systems" P.21 Section 2.1

> To keep this notation unambiguous, we assume that no transaction reads or writes a data item more than once.

Gerhard Weikum, Gottfried Vossen "Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery" P.47 Section 2.3

> To exclude redundancies of this kind, we henceforth make the following assumptions: in each transaction each data item is read or written at most once

# Answer
> 0 votes
The resulting precedence graph for your example will contain a cycle due to $R1(A) W2(A) R1(A)$. Hence its not conflict serializable. Since one example is sufficient to disprove the statement, therefore I agree with you. The answer might be wrong.

---
Tags: concurrency, database-theory
---


# Question
Title: Probability of detecting errors in codewords
I have been struggling with the below question for quite some time, and I don't have a pointer to move forward.

> A certain Error Control Coding scheme using block codes takes an input block (dataword) of 500 bits and appends a 50 bit code to produce a 550 bit codeword which is then transmitted across channel that causes individual bits to flip with a probability of 0.1 independently. The pairwise Hamming distances between all the codeword pairs is so large that the probability of an error occurring that converts one to the other can be neglected, except as follows: two codewords C 1 and C 2 have a Hamming distance of 10, and two codewords C 3 and C 4 have a Hamming distance of 6. Assuming no knowledge about what datawords may be more or less likely to be desired to transmit, what is the probability that a given block transmission will be corrupted by the channel but the error will go undetected by the receiver? You may answer with an expression, but the answer has to be completely numerical (no symbols).

My thought process about this question is that the probability needs to be calculated as such : Pr(Selecting either C1 or C2) * P(error in C1 or C2) + Pr(Selecting either C3 or C4) * P(error in C3 or C4).
I feel the Pr(error) is given by a binomial distribution of 55CX(0.1)^x(0.9)^550-x where X=10 or 6.

First, am I thinking about the problem correctly ? If yes , how do i derive the probability of selection of a particular codeword ?

Edit: I don't have the exact source per se, because this question is from a random uni final exam that I found on the internet. I am prepping for my own exam, and came across this question.

# Answer
> 1 votes
I think your approach is fine, but the question is not fully well-defined (unless I'm missing something).

The general error probability is $$\sum\_{i} \Pr(C\_i\text{ is transmitted})\Pr(\text{error}\mid C\_i\text{ is transmitted}).$$ The questions explicitly says that the error probability of all codewords except $C1,C2,C3,C4$ is negligible, so the error becomes:

$$\sum\_{i\in\\{1,2,3,4\\}} \Pr(C\_i\text{ is transmitted})\Pr(\text{error}\mid C\_i\text{ is transmitted}).$$

Computing the error probability is easy: if the Hamming distance is $x$, it takes $\lfloor x/2\rfloor +1$ bit-flips (**or more**) to corrupt the codeword, and $x$ bit-flips (or more?) to be undetected by the receiver. You can easily compute that in a similar way to what you wrote, and get a reasonable bound. However, the question explicitly says that the terms $\Pr(C\_i\text{ is transmitted})$ are unknown, yet it requires you to give an exact numerical answer. contradiction.

---
Tags: probability-theory, computer-networks, error-correcting-codes
---


# Question
Title: Convert a polygon mesh into a b-spline surface
$\textbf{Problem:}$

Getting a $\textit{polygon-mesh}$ as input, I have to construct a surface that looks exactly to the given input. My task is to generate a $\textit{b-spline}$ surface that exactly looks like the connected polygon mesh. It is obvious that my $\textit{b-spline}$ surface has to have a degree of one in both directions $\textit{u}$ and $\textit{v}$.

$\textbf{Output:}$

As an output for my solution. I have to generate a matrix of $\textit{control point}$ that represent that generated surface.

One property of this matrix is that each elements of each row and column are connected with each others. If our control points matrix is a $ n \times m$ matrix, then let $C\_i$ a column of this matrix with $C\_i = \<e\_{1i}, e\_{2i}, \dots, e\_{mi}\>$ then there must exist path in the polygon from $e\_{1i}$ to $e\_{mi}$.

One thing to consider if there is no edge between $e\_{ji}$ to $e\_{(j+1)i}$, we can construct one as long as this edge lies inside the polygon.

$\textbf{my trivial idea}$

Assuming that the polygon has $n$ nodes. I create $n$ other nodes inside the polygon near each original node. I create then a $2 \times n$ matrix. The first row contains all the points constructing the polygon. Second row contains the corresponding additional inserted node. In order to connect two additional inserted nodes, i have to make sure that the line between two nodes is kept inside the polygon.

This idea works only for simple structure and the complexer is the polygon the hard to find these additional points.

Any good solutions maybe ?.

# Answer
> 1 votes
Without any assumptions on the input mesh, you cannot in general get a *single* b-spline surface that replicates an arbitrary polygon mesh. You would need the mesh to be connected, but you would also need some fairly significant assumptions about the mesh topology. At the very least, you would want the input mesh to be manifold. (It might be possible to contrive a method for creating a single b-spline that exactly matches an arbitrary polygon mesh except on a set of measure zero, but in many cases the spline would have to be *extremely* degenerate and overlap with itself in strange ways.)

On the other hand, if you are allowed to use multiple disconnected b-spline surfaces in the output, then the problem is easy.

A degree-1 b-spline surface with a 2x2 control point matrix and no internal knots is just a quadrilateral with bilinear interpolation in the interior. In particular, if you set two adjacent control points to the same location in 3D space, you get a triangle. (c.f. Bézier triangle)

Any polygon mesh can be subdivided into a triangle mesh through well-known methods. Once you have done that, you can just separately convert each triangle into a 2x2 b-spline surface.

---
Tags: graphs, computational-geometry, polygons
---


# Question
Title: diagonal lemma and the negation function
Carnap's diagonal lemma asserts that for every computable formula **f**, accepting a natural number as argument and resolving to {false,true}, there exists a logic sentence **s** for which:

s $\leftrightarrow$ f($\ulcorner s\urcorner$)

With $\ulcorner s\urcorner$ the Gödel encoding for logic sentence s.

I have a problem with the example function f($\ulcorner s\urcorner$) = $\neg$s. It looks like according to Carnap's diagonal lemma, there exists a logic sentence **s** for which the following could hold:

s $\leftrightarrow$ $\neg$s

This is obviously, in one way or another, a wrong interpretation of what the lemma says or implies, but I cannot explain why it is wrong ... What's wrong?

# Answer
> 3 votes
The way you've stated the diagonal lemma is odd *(and I've not seen it put that way before)*. The standard phrasing is:

> For every formula $\varphi(x)$, there is some sentence $\sigma$ such that $$PA\vdash \sigma\leftrightarrow\varphi(\ulcorner\sigma\urcorner).$$

**Note that there is no $f$ here!** Rather, we're talking about *properties*: intuitively, the conclusion is that PA proves "$\sigma$ is true iff $\sigma$ has property $\varphi$." This makes things a little easier to see, in my opinion: in order to implement your argument we'd want to let $\varphi$ be the formula "is false."

So what your argument lets us conclude is that no such $\varphi$ exists - that is, Tarski's theorem.

---

Now let's shift to the language of the OP, and see how the version of the diagonal lemma that you state emerges.

Suppose $f$ is a computable function from (codes for) sentences to $\\{0,1\\}$ *(treating $0$ as false and $1$ as true)*. Then $f$ is representable in PA, say by $\psi\_f$. Let $\varphi\_f$ be the formula $$\psi\_f(\ulcorner\sigma\urcorner)=1.$$ Then applying the diagonal lemma as stated above with $\varphi=\varphi\_f$ we get some $\sigma$ such that $$PA\vdash\sigma\leftrightarrow \psi\_f(\ulcorner\sigma\urcorner)=1$$ (which could suggestively be written in a minor abuse of notation as "$PA\vdash\sigma\leftrightarrow f(\ulcorner\sigma\urcorner)$" - conflating $0/1$ with true/false and conflating $f$ with its representing formula).

The argument you gives shows that the map $n$ sending a sentence to the truth value of its negation is **not** computable; more snappily, the set of true sentences of arithmetic is not computable. (Note that this is actually weaker than the conclusion gotten above, since every computable function is definable.)

# Answer
> 2 votes
Carnap's lemma applies to computable functions. Your function is not computable.

---
Tags: logic
---


# Question
Title: Algorithms for procedural generated mazes
For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important).

There are many Maze generation algorithms, but they only work on a finite grid.

What if instead you are working on an infinite grid? But you only need to know finite of the grid at a time (the application I have in mind is a character wandering around in a grid). What are some algorithms I could use?

In particular, it would be best if the algorithm wasn't biased by which parts of the maze you choose to evaluate first.

One algorithm I thought of was a modification of randomized Kruskal's algorithm. Basically, to calculate a part of the grid, you add the walls to the list, and then eliminate walls until the part of the grid you want to reveal, along with the parts of the maze already revealed, are all in the same set. This might have bias though depending on which parts you evaluate first.

# Answer
If you have to create the maze:

* Without boundaries
* Generated uniformly
* Generated from a seed

It is unfortunately impossible without risking an endless loop, but most times it is good enough to create a **really** large maze.

Daedalus has lots of features and implements all the algorithms on this page. To generate a really big maze in Daedalus, start the program -\> press `File` -\> `run script` -\> `Worlds largest maze` -\> click `Ok` -\> press `i`.

From Daedalus features: (beware the rabbit hole)

> **World's Largest Maze**: This script has the option to use different algorithms to generate the parts of the Maze being viewed, which are nested cell fractal, binary tree, recursive division, unicursal Labyrinth, classical Labyrinth, and Hilbert curve Labyrinth.
>
> Mazes created here are enormous, and measure at least a billion passages on each side. Visiting one cell per second, it would take over 31 years just to walk from one side of the Maze to the opposite side, and that’s assuming no walls are in your way. Wall following to actually solve the Maze will take on average 31 billion years

Wall following a maze this large on a regular computer, would take over 100 years. Exceeding the lifetime of a person, I would say this is "big enough".

> **Nested Fractal**: This creates a fractal Maze, which is composed of smaller Mazes connected together. Each cell of an outer Maze contains an inner Maze nested inside of it, where this Maze nesting process can be repeated multiple times.
>
> Consider a 10^9 by 10^9 passage Maze, or a 10x10 Maze nested with 9 levels total. If we want at least a 100x100 section around us, we only need to create the 100x100 passage submaze at the lowest level, and the seven 10x10 Mazes it's nested within, to know exactly where the walls lie within a 100x100 section. To ensure the Maze remains consistent and never changes as you move around, have a formula to determine a random number seed for each coordinate at each nesting level.

The nested fractal maze has an obvious texture, where you can see the maze is split up into "blocks"

This is the closest i have come to an infinite maze, and it should be possible to extend this by adding randomization to the edges of the lowest level to break the "blocky" texture.

From Daedalus features:

> **Binary Tree**: The algorithm creates Mazes with the special property that each cell has a passage that leads either up or left, but never both or neither. This creates a biased texture, where one can always easily travel diagonally up and to the left without hitting barriers or having to make choices. Moving down and to the right is when the Maze becomes a challenge, so the Maze is hard to solve but easy to solve backwards. The Maze forms a binary tree, with the upper left corner the root, where each node or cell has one or two children, and one unique parent which is the cell above or to the left of it.

> **Recursive Division**: The algorithm creates a Maze by adding walls, where the area within the Maze is divided by a randomly positioned horizontal or vertical wall with a passage opening within it. Each subarea is then recursively divided with more walls until all areas are filled.

Every time we subdivide, we only have to subdivide the part of the maze we are in.

The images are from World's Largest Maze in Daedalus, (the subjectively best) open-source maze generation program, written in C++, and it even has its own scripting language. If you want a more detailed explanation of the algorithms, you can also check out the source code. The images above are **colored** based on the distance you have to walk to another cell. **Black** cells can't be reached without exiting the viewport.
> 2 votes

# Answer
Generating such unbiased maze it's a very hard problem, since long term dependencies in the tree appear from the fact that you have an infinity maze, i.e. There is a chance that the path from 2 neighboring positions goes through several `part of the grid` away non calculated yet.

Here is one idea that might help. Imagine you have already calculated several quadrants. Since the final (infinite board) will be a tree, from any position you need to be able to reach a border exit. Here a border exit is a wall location that has not wall and is adjacent to a calculated quadrant and a non calculated quadrant.

When you want to calculate some quadrant, take all wall location in some arbitrary order, and make Kruskal, but add a dummy node that represent the outside. Whenever a node is connected to this node, it can goes outside the quadrant. You stop when all nodes are connected to this dummy node. Note that you will not have a tree but a forest.

Make sure you understand the approach described above. Now I will described a solvable issue with this approach.

Here there is just one problem. How can I decide when a wall location shared by two quadrants, if it will contain a wall or not. Why is this a problem? Because you need to be consistent generating both quadrants, while keeping the connected tree property. Let's denote first quadrant as quadrant $ZERO$. For each quadrant take the Manhattan distance from this quadrant to quadrant $ZERO$, if two quads have the same distance they will not be adjacent. Assign to each quadrant the responsibility of generating the border walls to the neighboring quadrants with distance from $ZERO$ greater that itself.
> 0 votes

# Answer
consider the uniform spanning tree. we get an *unbiased* maze on a grid (or any graph) by performing a "loop-erased random walk".

Prim algorithm or any BFS also returns a spanning tree, I think.
> 0 votes

---
Tags: algorithms, graphs, randomized-algorithms, spanning-trees, computer-games
---


# Question
Title: If a problem is in P solved via dynamic programming, is it also in NP?
So I can solve a given problem using dynamic programming in $O(n^2k^2)$ time complexity. This means that the problem is in P. But I am asked if it is in NP.

My answer is, "Since it is also polynomial time solvable, the problem is also in $NP$".

Is that a correct statement? If not, is a problem in P solved via dynamic programic also NP?

# Answer
> 19 votes
### Any problem in P is also in NP

A decision problem that's in P is also in NP, because you can give the verification logic like this: for yes instance `x`, use empty string as a certificate, and solve `x` in polynomial time. You get the result that it's yes instance (that's by definition of P) and that means verification is done in polynomial time.

Note that, the order written as $n^2 k^2$ doesn't simply mean the problem is in P (Check "Pseudo-polynomial time" in wikipedia.) For example, Knapsack problem can be solved by the dynamic programming and its order is $O(n W)$ where $n$ is the number of products and $W$ is the maximum weight for the knapsack. But $W$ is actually considered exponential of the input size and Knapsack problem is known to be NP-complete.

# Answer
> 6 votes
Any problem that's in P is also in NP, since P is a subset of NP.

# Answer
> 1 votes
One way to think of this is that problems in NP lift a restriction by not necessarily meeting the polynomial time requirement in a deterministic manner. Problems in P and NP meet the polynomial time requirement, but problems in P are those that meet it deterministically. Since P vs. NP is still an open question, it could be that everything in NP is also in P, even though most computer scientists don't think this is the case. If P is not equal to NP, then the NP-complete class of problems is mutually exclusive with P -- meaning that these problems cannot meet the polynomial time requirement deterministically.

---
Tags: p-vs-np
---


# Question
Title: Does computational complexity theory take into account problems with subjectivity in the verification of a solution?
When we discuss **P vs NP** we are looking at the difference between problems that are **easily solved** versus **easily verified** (wrt polynomial vs exponential time).

But in both cases these are **black-and-white results**. We do/don't solve the problem, we do/don't verify the problem.

What about cases where there is **subjectivity to the verification**? Problems where 2 people don't agree on the solution, since the solution may depend on context, environment, etc.

Does computational complexity deal with the subjectivity in verification, or are all problems modeled as black-and-white results?

# Answer
> 3 votes
No. Computational complexity doesn't deal with subjectivity. In computational complexity, we consider formal languages that are precisely defined, so there is no subjectivity.

---
Tags: complexity-theory, p-vs-np
---


title: WebHook versus API

text:
# Question
Title: WebHook versus API
I've read many blogs about this but I still get somehow confused, specially why a webhook is a thing vs an API and not just a subset of API.

The way I interpret from most places (and interpret is the key work here) is that a webhook is just a passive "webmethod" that expects a POST (from what I read in most places). How is this different from any other operation that expects a POST in an API?

APIs operations are always passive are they not? They don't trigger by themselves, a request must be done to them.

So, I'm not following. In my head webhook is just a fancy name for an API method that accepts only the HTTP POST verb.

Please, shed some light. Really confused here with all the fuzz.

Note: really sorry if this is not the right community for this kind of question. If so, please indicate the right one and I'll change.

# Answer
Yes, in some sense a webhook is an API.

However... typically when we use the word "webhook", we are thinking of a particular kind of use. Normally, they are used as for notifying the server of an event that might be of interest to it. They're not an arbitrary API; they usually have a specific purpose.

As far as I know, there is no formal definition of the term, so nothing forces people to use terminology in this way -- this is just my informal sense of how the word tends to be used.
> 1 votes

---
Tags: terminology, api-design
---


# Question
Title: What's the meaning of this service specification
What's the meaning of the example statement here?

"A service specification S describes an interface: it specifies the behavior of certain program elements (functions or subprograms) through statements expressed in program logic. For instance, these might be such statements:

1. \[...\]
2. *x, y : N\[{x\>0} y := x * x {y \> x}\]*

"

The quote is from the article "On The Hourglass Model" By Micah Beck, Communications of the ACM, July 2019, Vol. 62 No. 7, Pages 48-57

# Answer
> 4 votes
That means:

For all natural numbers x and y,
if the value of variable x is greater than zero
then after the assignment statement "y := x\*x" is executed
the predicate "y \> x" will be true.

---
Tags: formal-methods
---


# Question
Title: How to write grammar production rules to describe recursive structures?
I'm trying to describe a data structure by production rules. The structure is recursive; say a list of type $A$ made of elements of type $A$ or $B$.

Writing the grammar, I build this:

> $(S \rightarrow AS|ε)$ $(A \rightarrow AA|bA|ε)$

where $b$ is a terminal representing element $B$ of my list.

The production $A \rightarrow AA$ got me a little baffled... is there something right? Thank you.

# Answer
Yes, you can use context-free grammars to describe data structures, but only if the data structure is linear (e.g., a linked list of integers). Context-free grammars are not well-suited for trees or graphs (for those, you need something more powerful).

There's nothing wrong with a production like $A \to AA$; that's a valid rule that can appear in a context-free grammar.
> 0 votes

---
Tags: data-structures, formal-grammars
---


# Question
Title: Divide N sticks among M boys as homogeneously as possible (ignoring order)
There are $N$ sticks. $N$ is an integer greater than zero. I want to divide it among $M$ boys. $M$ is also a positive integer. Partitioning $N$ among $M$ is easy, but doing it as evenly as possible is difficult for me to think through. Can someone suggest an algorithm? Similar questions exist on this site, but I could not find an answer that solves this problem, though it is possible that I overlooked something.

**EDIT:**

The sticks are all homogeneous, the same in every respect. What I mean by "as evenly as possible" is that if there are 6 sticks and 3 boys, the division algorithm should output 2-2-2. If there are 5 sticks among 3 boys, it should output 1-2-2. The disparity between the minimum stick holder and maximum stick holder should be minimized. Ordering does not matter (e.g. 1-2-2 is the same as 2-1-2).

# Answer
```
# Divide perfectly homogeneously, as large as possible
for i = 0 to M
    array[i] = N / M    # integer division, resulting in floor

# Divide remainder
for i = 0 to N modulus K
    array[i] += 1

```
> 0 votes

# Answer
Give some of the boys $\lfloor N/M \rfloor$ sticks (i.e., divide and round down), and some of them $\lceil N/M \rceil$ sticks (divide and round up). Once you fix those two numbers, that uniquely determines how many boys get $\lfloor N/M \rfloor$ sticks and how many get $\lceil N/M \rceil$ sticks -- do some simple arithmetic, try a few examples, use the fact that $\lceil N/M \rceil = \lfloor N/M \rfloor + 1$ if $M$ doesn't evenly divide into $N$, and you'll work out the general formula.
> 4 votes

# Answer
Give them $\lfloor\frac{N}{M}\rfloor$ sticks and then distribute the rest of sticks ($N-\lfloor\frac{N}{M}\rfloor$) among them by giving one stick to each boy until there are no more sticks. By solving it this way, the time complexity will be $\max(\lfloor\frac{N}{M}\rfloor, N \bmod M)$ .
> 0 votes

---
Tags: algorithms, optimization, integer-partitions
---


# Question
Title: How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?
In the context of languages (not grammars), I know following:

> 1. $LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k)$
> 2. $LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k)$
> 3. $LL(0)\subset LR(0)$
> 4. $LL(n)\subset LR(1)$ for all $n$'s

How does $LL(n)$ languages compare with $LR(0)$, for $n\>1$?

# Answer
> 1 votes
They are incomparable.

1. Every $LR(0)$ language has the prefix property (no sentence is a prefix of another sentence). But many $LL(k)$ languages don't have this property ($a^\*$, for example).
2. The language $\\{a^nb^mc\mid n\ge m\ge 0\\}$ is $LR(0)$ but is not $LL(k)$ for any $k$.

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


# Question
Title: P Vs NP can never be proven one way or the other!
Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem.

And since if we prove that any problem in NP is a P that would mean that we have NP=P.

So by that logic either NP==P or it can never be proven that NP is not P and if somebody proves that, then won't they be contradicting the result itself. I mean they solved one NP problem which was this proof so by that logic all other problems should now be in class P.

Let me know if I got something wrong here.

# Answer
> And I found out that proving P Vs NP is an NP problem.

I think the two different meanings of the word "problem" are mixed here. When we discuss P and NP, they are the class of decision problems, which are essentially maps from the set of bits sequence to boolean values. On the other hand, "NP =/= P" is a long standing mathematical problem (general meaning,) but "NP =/= P" itself is a single proposition, and usually it's not considered as decision problem.

If you convert "NP =/= P" to a decision problem as the map from single point to true/false (this is completely valid formalization), its complexity is constant time (algorithm can simply return true or false, though we don't know which one is correct,) so it's in P and NP.

> if somebody proves that, then won't they be contradicting the result itself

Proving "NP =/= P" means we know the correct return value in the algorithm above, and that doesn't contradict with anything. The result simply claims there is a NP problem that is not P. The decision problem "NP =/= P" is just an instance within class P. Both facts can hold simultaneously.
> 1 votes

---
Tags: np-complete, np, p-vs-np
---


# Question
Title: Uniqueness of solution in Arden's theorem
Geeksforgeeks contains a proof of Arden's theorem, asserting that $R=QP^\*$ is the *unique* solution to $R=Q+RP$. The proof is reproduces below.

My question is:

> What is the logical reasoning to prove that any equation is the **unique (only solution)**? Particularly in this case, how can the procedure below logically lead to the proof that R=QP\* must be the **unique (only solution)**?

Here is my understanding of the proof:

1. Recursively substitute $R$ in $R=Q+RP$ with $Q+RP$
2. Establish the recursive definition of $R$
3. Generalize the definition to $R=QP^\*$

*Disclaimer: The proof below is second part of a 2-parts proof from the original Geeksforgeeks's proof of Arden’s Theorem. Originally, the proof starts out to prove **$R=QP^\*$ is a solution to $R=Q+RP$**. I omitted this part here because I want to focus on the second part of the proof, which is to prove uniqueness. However, to clear any confusions, please allow the proof below to be based on the assumption that **$R=QP^\*$ is a solution to $R=Q+RP$** has been correctly proven prior and that **$R=QP^\*$** can be used as a corollary for proof below, which try to prove **$R=QP^\*$ is the unique solution to $R=Q+RP$, given P does not contain $\epsilon$***

> Given that $P$ and $Q$ are two regular expressions over $\Sigma$, and $P$ does not contain $\epsilon$. Start with: $$R = Q + RP$$
>
> Now, replace $R$ by $R = Q + RP$: $$ \begin{align\*} R &= Q + (Q + RP)P \\ &=Q + QP + RP^2 \end{align\*} $$
>
> Again, replace $R$ by $R = Q + RP$: $$ \begin{align\*} R &= Q + QP + (Q+RP)P^2 \\ &= Q + QP + QP^2 + RP^3 \\ &= \cdots \\ &= Q + QP + QP^2 + \cdots + QP^n + RP^{n+1} \end{align\*} $$
>
> Now, replace $R$ by $R = QP^\*$ to get $$ R = Q + QP + QP^2 + \cdots + QP^n + QP^\*P^{n+1} $$
>
> Taking $Q$ as a common factor, $$ \begin{align\*} R &= Q(\epsilon + P + P^2 + \cdots + P^n + P^\*P^{n+1}) \\ &= QP^\*, \end{align\*} $$ as $\epsilon + P + P^2 + \cdots + P^n + P^\* P^{n+1}$ represents the closure of $P$.
>
> Thus, $R = QP^\*$ is the unique solution to $R = Q + RP$.
>
> **Clarifications**:
>
> I asked this question with the assumption that this is a valid proof $R=QP^\*$ is the *unique* solution to $R=Q+RP$ (a). There are two basis for my assumption:
>
> (1) This is the most popular proof found on the Web, I have included multiple sources as samples below. Across different authors, the proof takes exactly the same form as the procedure demonstrated above. Therefore, through inductive reasoning, I believe that this proof and its similar forms is a valid proof of (a). Otherwise, all those authors somehow collectively give a false proof.
>
> (2) The procedure is logically and mathematically valid at each and every step, including the generalization of P\* given that P does not contain $\epsilon$ as demonstrated above. Therefore, through deductive reasoning and (1), I believe that this proof and its similar forms is a valid proof of (a) until otherwise disproved through valid and sound counterargument.
>
> Of course, what missing here is the intuitive reasoning from which one can derive that this proof indeed validly proves (a) to be true. *Moreover, I am very curious and interested in the general intuitive and logical reasoning to prove anything as a unique solution.*
>
> I am not asking for a new proof. If for logical and/or mathematical reason, you can prove that this proof is invalid and MUST be discarded. Please present your evidence/counterargument in your answer. Please note that though I am not in any way qualify to be a
> mathematician, I am quite aware of logical reasoning, as well as most fallacies and cognitive biases. So it might happen that I reject your proposed answer on the ground of invalid and/or unsound argument. This is in no way means that I want to offend you. If I made anyone feel so, I would like to apologize with my deepest sincerity. I am very appreciative of all the help I can get. **Lastly, thank you Yuval Filmus, Hendrik Jan and D.W. who had been awesome people because you guys spent valuable time and efforts to put up with me for this question. Thanks guys.**

Other sources from simple search of "Arden's Theorem Proof" on Google and Youtube

nesoacademy's Youtube Channel | Bhai Bhai Tutorials's Youtube Channel | Palak Chhajed's Youtube Channel | Theory of Automata and Formal Languages By Anand Sharma | tutorialspoint | sanfoundry

# Answer
Suppose $R = Q + RP$, where $\epsilon \notin P$.

Let us first prove by induction that $QP^i \subseteq R$ for all $i \geq 0$. The base case $Q \subseteq R$ is clear. Now suppose that we know that $QP^i \subseteq R$. Then $QP^{i+1} \subseteq RP \subseteq R$.

Since $QP^i \subseteq R$ for all $i \geq 0$, it follows that $QP^\* \subseteq R$.

Conversely, let us prove by complete induction on $|w|$ that if $w \in R$ then $w \in QP^\*$. Let $w \in R$, and assume (by induction) the claim for all shorter words. Since $R = Q + RP$, either $w \in Q$ or $w \in RP$. In the former case, clearly $w \in QP^\*$. In the latter case, $w = xy$, where $x \in R$ and $y \in P$. Since $\epsilon \notin P$, $y \neq \epsilon$, and so $|x| \< |w|$. Hence by the induction hypothesis, $x \in QP^\*$. It follows that $w \in QP^\*P \subseteq QP^\*$.

We have shown that $R \subseteq QP^\*$, and so $R = QP^\*$.

For the case $\epsilon \in P$, see this answer.

The "proof" you provided isn't a proof. It is a very convoluted way to show that $QP^∗$ is a solution, but it doesn't prove uniqueness at all. I suggest ignoring it.
> 4 votes

# Answer
This is not a valid proof.

You ask for the intuitive reasoning that makes this proof valid, but there's no amount of intuitive reasoning you can add to make it valid. It's just simply not a good proof. It's not a matter of adding intuition; there is no rescuing it.

A valid proof starts with facts that are known to be true; then each derives a new fact from previously known facts, using a valid inference rule or axiom. The so-called proof you have listed does not take that form. For instance, let me highlight two flaws:

* The first step of the "proof" you refer to says "Now, replacing R by R = QP\*, we get". This first step is already not valid. It makes an assumption that is not justified (it assumes that we know that R = QP\*); so this step is not valid. Basically, the proof is flawed because it uses a circular argument: it starts by assuming what is to be proved, and derives what is to be proved. That proves nothing. Since you said you know logical fallacies, this is the fallacy of circular reasoning.
* The second part of the "proof" again has the same flaw, where it says "Now, replace R by R = QP\*". Here it is assuming what is to be proven.
* The "proof" doesn't have the right structure to prove uniqueness. You can't prove that $x=5$ is the unique solution to an equation by first assuming that $x=5$ and then proving that it follows that $x=5$. It doesn't do anything to show that the solution is unique. It just claims "Thus, R = QP\* is the unique solution", but without any justification for that statement. It doesn't even try to explain the justification -- we are forced to guess.

---

I think the primary lesson here is that I suggest you adjust how you judge the credibility of sources of technical information.

I realize you found this proof on a popular website, but popularity is not a guarantee of correctness; it is merely a hint that is sometimes useful. I realize that you found it on multiple websites, but that is not strong evidence; it's not unusual on the Internet to find multiple people copy-pasting the same wrong thing. I realize that GeeksforGeeks is highly regarded by some and might be useful for some purposes (e.g., particularly for coding-contest-style questions and interview-style questions), but in my experience, its quality is highly variable, and in particular, it is not a reliable resource for mathematical and theoretical topics. I have personally seen multiple articles there that are sloppy, a poor reference, or just plain wrong. Now I've seen one more. It might also be useful to mention that articles on Geeksforgeeks are not written by a single person -- they are written by many different authors, some of whom might be more knowledgeable than others, and in any case, the authors are only people, so they can make mistakes.

If you want to find credible resources, a better place is to find a well-regarded textbook on automata theory or the theory of formal languages. That will be a much more reliable reference than Geeksforgeeks.

I'd also encourage you to reflect on why you've been having a hard time believing it when three separate people have told you that the article was wrong -- two of whom are, as it happens, experts on this subject. That might be an enlightening exercise.
> 2 votes

---
Tags: formal-languages, regular-languages, regular-expressions, proof-techniques
---


title: Show that a problem is NP-Complete

text:
# Question
Title: Show that a problem is NP-Complete
The problem is, K\_longestPath:

> We are given a graph in which some of the vertices are "cities". No two cities have an edge between them, thus every city must be at distance at least 2 from each other city. We have to find a path that goes through each such city without forming a cycle.

We are given the Graph with a valid configuration of cities and we have to find if there exists such a path.

At first I was thinking solving this with Hamiltonian path, but to show that the problem is NP-complete I have to find an algorithm that will change it's inputs to be inputs for this problem that we got, and I don't know how to do this..

# Answer
You need to choose an NP-hard problem, and show a deterministic polynomial-time algorithm that transforms any instance of this NP-hard problem to an instance of your city problem that is true if and only if the original instance was true. As you suggested in the question, *Hamiltonian path* is a good choice for the starting problem.

Try to create an algorithm that takes any Hamiltonian path instance and constructs a "city problem" instance which has the same truth value. You must also write a **proof** that, for any input instance of Hamiltonian path, the corresponding output instance of the "city problem" has the same truth value.

Hint 1:

> Think about subdividing edges.

Hint 2:

> If you take an arbitrary (undirected simple) graph and subdivide each edge once, you get a graph in which none of the original vertices are adjacent to each other.
> 1 votes

---
Tags: np-complete, proof-techniques, correctness-proof, proof-assistants
---


# Question
Title: Deriving recursive definition from function specification
Given this function specification, where name `xs` is bound to a list, `#` denotes its cardinality and `.` is the `list index` operator...

$$\left( \sum i: 0 \leq i \< \\#xs: xs.i * (i + 1) \right)$$

I need to derive a recursive function using induction.

Base case: `[]`

\begin{align} \left( \sum i: 0 \leq i \< \\#\[\]: xs.i * (i + 1) \right) && \text{(Textual substitution - xs is free)} \\ \left( \sum i: 0 \leq i \< 0: xs.i * (i + 1) \right) && \text{(Def. of #)} \\ \left( \sum i: False: xs.i * (i + 1) \right) && \text{(Algebra)} \\ \left( \sum i: 0 \leq i \< \\#xs: xs.i * (i + 1) \right) && \text{(Empty range)} \end{align}

Inductive case: `(x:xs)`

\begin{align} \left( \sum i: 0 \leq i \< \\#(x:xs): (x:xs).i * (i + 1) \right) && \text{(Textual substitution - xs is free)} \\ \left( \sum i: 0 \leq i \< 1 + \\#xs: (x:xs).i * (i + 1) \right) && \text{(Def. of #)} \end{align}

How can I proceed from here ?

# Answer
> 3 votes
Your notation and understanding are pretty good.

It is easier to consider `(xs:x)` as the inductive case instead of `(x:xs)`

\begin{align} \sum\_{i:\ 0 \leq i \< \\#(xs:x)} &(xs:x).i * (i + 1)\\ &=\sum \_{i:\ 0 \leq i \< \\#xs+1} (x:xs).i * (i + 1) \\ &=\sum\_{i:\ 0 \leq i \< \\#xs} (xs:x).i * (i + 1)+\sum\_{i:\ i=\\#xs}(xs:x).i * (i + 1)\\ &=\sum\_{i:\ 0 \leq i \< \\#xs} xs.i * (i + 1)+x\*(\\#xs+1),\\ \end{align} where we assume that list index starts with 0.

If we denote the function by $f$, the above equality becomes $$ f(xs:x) = f(xs) + x\*(\\#xs+1), $$ which is the recursive step of a recursive definition.

The base case, as you have indicated, is $$ f(\[\]) = \sum\_{ i:\ 0 \leq i \< 0} \[\].i * (i + 1) = \sum\_{i: \text{ empty set}}\[\].i * (i + 1) =0.$$

---

**Exercise**. Derive the following recursive formula of the same function $f$. $$ f(x:xs) = f(xs) + t(xs)+ x, $$ where $$t(xs)=\sum\_{i:\ 0 \leq i \< \\#(xs)} xs.i,$$ the sum of items in $xs$.

---
Tags: proof-techniques, recursion, induction, calculus-of-constructions
---


# Question
Title: Why no DPDA can accept Palindrome? (according to this proof)
This proof is from the book "Introduction to Languages and the Theory of Computation" by John C. Martin.

My question is from the pink part at the second page:

> It follows in particular that no sequence of moves can cause M to empty its stack.

and further, it talks about $y\_x$ that is my second question. I can't understand what $y\_x$ is.

I'll appreciate it if someone please describe me the whole proof.

# Answer
> 1 votes
No sequence of moves may empty the stack, this is seen as follows. Since the PDA is deterministic, its computation is determined by its input. So we have to argue that the computation on $x$ will not empty the stack. If it would empty the stack, then the PDA blocks, and can no longer continue. But observe that $xx^R$ is a palindrome, so there should be an accepting computation on $xx^R$. This implies that the computation on the prefix $x$ should not block.

Your second question. For input $x$ we can look at all continuations $xy$. For each $y$ determine the stack height that is obtained. We choose an $y$ for which this is minimal and call this specific string $y\_x$ (to indicate it depends on $x$).

---
Tags: pushdown-automata, computation-models
---


# Question
Title: Shortest paths from a source in weighted graph with only one negative weighted edge
Of course assuming there aren't any negative cycles. I saw this question somewhere. And i saw a complicated solution which says to build three such graphs and connect between them in a very complicated manner. My question is why isn't my simple solution good for it? My simple solution is to first find the negative edge . And then start traversing from that edge with dijkstra. I think once you start with that edge, dijextra should work. So that way i mange it in O(e + vlogV) . So why isn't my easy solution mentioned there. Is my solution correct?

# Answer
No. The negative edge will not always be part of the shortest path. For example, in the digraph

A \<==\[+1\]== B ==\[+4\]==\> C ==\[-1\]==\> D ==\[+4\]==\> E

the shortest path departing from B is the path from B to A, and does not include the negative edge (C,D).

Even when the negative edge is part of the shortest path, it won't necessarily be the first edge of the path.
> 2 votes

# Answer
I want to add that the method of replacing the weight of negative edge by $0$ or $a\>0$ also has drawbacks. Consider the following example:

If we replace $-10$ with something non-negative, Dijkstra will never find path $0 \rightarrow 1 \rightarrow 2$, and it will say that the optimal path from $0 \rightarrow 2$ has weight $1$.

Running Dijkstra on some copies of the initial graph is a common and understandable method, if it is explained properly. Here it's enough to have two copies of the vertex set. Let $G=(V,E)$ be the initial graph, where $e=(u, v, w)$ is the negative edge of weight $w$. Then let $V\_0$ and $V\_1$ be two copies of $V$, each connected by all edges from $E$ except $e$, and draw edge $e'=(u\_0, v\_0, w)$. One can prove that Dijkstra works correctly in such graph, and the optimal answer for each vertex $v$ will equal $\min({d\[v\_0\], d\[v\_1\]})$.

If we don't want to multiply a graph, we can guarantee the occurrence of the negative edge in all shortest paths by compressing $u$ and $v$ into one super-vertex $S$. Edges of the new graph should be modified of the following way: $(x \rightarrow u)$ should go **to** $S$ now, $(v \rightarrow y)$ should go **from** $S$, $(u \rightarrow y)$ and $(x \rightarrow v)$ should go away.
> 0 votes

---
Tags: algorithms, graphs, data-structures
---