# Question
Title: How are vertex capacities defined in a flow network?
I'm new to network flows and I'm reading this topic from Cormen's Algorithms book (3rd edition) from 26 chapter. I came across this problem from the 26.1 section

> Suppose that, in addition to edge capacities, a flow network has vertex capacities. That is each vertex has a limit $l$ on how much flow can pass though . Show how to transform a flow network $G = (V, E)$ with vertex capacities into an equivalent flow network $G' = (V', E')$ without vertex capacities, such that a maximum flow in $G'$ has the same value as a maximum flow in $G$.

I want to understand how the author has defined vertex capacities here? Because from my understanding, the most general definition would be

$l(v) = \sum\limits\_{e \text{ into } v} f(v) - \sum\limits\_{e \text{ out of } v} f(v)$

but if this is so, then for all $v$ not in the set of source and sink nodes,

$l(v)= 0$, so we are never really setting any limit. Please help me understand the vertex capacity term.

# Answer
> 1 votes
Just like edges have capacities on them (i.e, how much flow is allowed to go through them), they have added capacities for nodes.

If a node $v$ has capacity $C\_v$, then any flow with $\sum\_{e \text{ into } v} f(e)\>C\_v$ is considered *invalid* (it violates the node capacity rule).

---
Tags: linear-programming, network-flow
---


# Question
Title: Can any language be expressed by regular expression?
I'm studying Autoamta Theory currently and am wondering if any Language (for example Lanugage L in Alphabet A={a,b}) can be expressed by regular expression.

In my current understanding the rule is "L is acceptable by Automaton \<=\> L is rational"

But does that automatically mean that for every regular L there is also a regular expression?

# Answer
Every rational language can be represented by (at least one) rational expression, and every rational expression represents a rational language. That means for any rational language, you can find the equivalent expression (though it might not always be a simple task). In fact, there are algorithms that convert any NFA into an equivalent rational expression and vice versa, proving their equal expressive power: for example the McNaughton-Yamada-Thompson algorithm for converting a rational expression to an NFA and Kleene's algorithm for converting an NFA to a rational expression.

Rational expressions and languages are usually referred to as "regular" in English, but the word "rational" is also used. Be careful with the term "recognizable", however, because it is usually taken to mean "Turing-recognizable" in English discourse in automata theory – these languages form a much larger group than rational languages, and include many non-rational languages.
> 2 votes

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


title: Halting problem is undecidable proof-:

text:
# Question
Title: Halting problem is undecidable proof-:
Confused with this proof. I will point my confusions here.

what is R(M)? They say it is representation of turing machine but what is it exactly? Is it tuples of turing machine? How do we decide w is input here? Because later when doing R(M)\*R(M) we call R(M) as input.

how can we just assume that H'-:

when M halts with input w, loops

when M does not hal with input w, halt?

What logic are we using while making H' from H? Can you tell me about that?

why did we made a copy? was it to get input as R(M)? I don't know how and why about that though I am just looking at R(M)\*w and thinking if we get R(M)\*R(M) the input will be R(M).

From M halts we get to D halts, how can we say so?

It is still M not?

https://slideplayer.com/slide/10708471/

# Answer
Trying to answer the many questions you have here to the best of my ability:

> what is R(M)? They say it is representation of turing machine but what is it exactly? Is it tuples of turing machine?

It is some representation of some Turing Machine $M$. The exact format of the representation is not important for this proof, just that it unambiguously specifies a particular Turing Machine.

> How do we decide w is input here?

We do not "decide" any input. We are trying to prove by contradiction that there exists no TM $H$ that solves the Halting Problem; so we begin by assuming such $H$ exists and therefore works correctly for any representation of TM $R(M)$ and input $w$. $w$ can be any string but will be the string representation of a Turing Machine in the further construction of this proof.

> What logic are we using while making H' from H? Can you tell me about that?

Suppose you were given the state transition table for $H$. All you need to do is to replace the accepting state(s) of $H$ with an infinitely looping state. This is your $H'$. Now, clearly for any input, $H'$ loops if and only if $H$ accepts the same input, halts otherwise.

> why did we made a copy? was it to get input as R(M)?

Exactly so. $D$ simulates $H'$ with the input $R(M), R(M)$. $D$'s ultimate behavior emerges from the $H'$ we constructed earlier: if $R(M)$ halts with the input $R(M)$, $H'$ doesn't halt so neither does $D$. But if $R(M)$ does *not* halt with the input $R(M)$, $H'$ halts and so does $D$.

In other words, $D$ is a Turing machine that, given some representation of a Turing Machine $R(M)$ as input, halts if and only if $M$ does *not* halt when given $R(M)$ as input, and otherwise. We arrive at a contradiction by having $R(D)$ being given to $D$ itself as input.

> From M halts we get to D halts, how can we say so?

Notice we are giving $R(D)$ as input to $D$. Therefore $H'$ executes with $R(D), R(D)$ as input. What happens next? Either:

* $H'$ loops forever, which means $H$ says $D$ halts on the input $R(D)$, in which case $H$ was wrong, OR
* $H'$ halts, which means $H$ says $D$ doesn't halt on the input $R(D)$, in which case $H$ is also wrong

So we have a contradiction from assuming the existence of $H$ – therefore such TM cannot exist.
> 1 votes

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


title: Is the MCP language really np hard?

text:
# Question
Title: Is the MCP language really np hard?
I have a graph $G=\left(V , E\right)$ and source $s$ and target $t$.

I also have a weight function $w: V\rightarrow \mathbb{R^+}^k$, meaning a vertex given $k$ non negative weights.

There is an upper bound vector $C \in \mathbb{R^+}^k$.

The problem definition is to find a path from $s$ to $t$ such that it is not too heavy.

What too heavy means? For each $1\<i\<k$ the coordinate $i$ for the weight of a path (sum of edges...) must be smaller than $C\_i$.

I read somewhere that this problem is np hard, but I don't think it is. I think its solvable by running many iterations that any shortest (by $w\_i$) weight path. And then iterating over again.

I want to ask if my approach is correct or if its not and its really np hard, how you show it?

# Answer
Your problem is NP-hard even for $k=2$, as it can be seen by a reduction from the partition problem.

The reduction is as follows: Let $S = \\{s\_1, \dots, s\_n\\}$ be a set of $n$ positive integers. Let $\varepsilon = \frac{1}{2n}$.

Create a graph that has $n+1$ vertices numbered from $1$ to $n+1$ and $2n$ edges. Specifically, for each $i \in \\{1, \dots, n\\}$ add two parallel edges\* $e\_i$ and $f\_i$ between $s\_i$ and $s\_{i+1}$. Pick $w(e\_i) = (s\_i,\varepsilon)$ and $w(f\_i) = (\varepsilon, s\_i)$. Pick $C = (T, T)$, where $T =\frac{1}{2} + \frac{1}{2}\sum\_{i=1}^n s\_i$.

There is a path from vertex $1$ to vertex $n+1$ of total weight at most $C$ if and only if there is a subset $S'$ of $S$ such that $\sum\_{s \in S'} s = \frac{1}{2}\sum\_{i=1}^n s\_i$.

If you multiply all involved weights by $2n$, you can show that the problem remains hard even when all numbers involved are positive integers. Moreover, a similar reduction from the 3-partition problem shows that this special case is strongly NP-Hard.

* Here I'm using parallel edges for simplicity but the graph can be made simple by splitting the edges with an intermediate vertex and tweaking the edge weights.

The following graph with $C=(50,50)$ is a counterexample to your algorithm. All unlabelled edges have weights $1,1$.
> 2 votes

---
Tags: graphs, weighted-graphs
---


# Question
Title: If $\Sigma_i^P = \Sigma_{i+1}^P$ then for all $k \ge i$ holds $\Sigma_k^P = \Sigma_{k+1}^P$
I am struggling with the following remark from lecture:

> Suppose the Polynomial Hierarchy collapses at the $i$-th level, i.e. $\Sigma\_i^P = \Sigma\_{i+1}^P$. Then for all $k \ge i$ holds $\Sigma\_k^P = \Sigma\_{k+1}^P$.

The only similar relation I know of is $\Sigma\_i^P \subseteq \Pi\_{i+1}^P \subseteq \Sigma\_{i+2}^P$ holds, but I do not understand see how this could help here. I have also tried to use induction, but it lead to nowhere. Could you please give me a hint?

Following nir shahar's answer I now have the following:

We aim to proof this claim by induction:

* Induction Basis: $\Sigma\_i^P = \Sigma\_{i+1}^P$
* Induction Hypothesis: $\Sigma\_{k-1}^P = \Sigma\_{k}^P$ for some $k \ge i$.
* Induction Step: We want to show that $\Sigma\_k^P = \Sigma\_{k+1}^P$.

Following nir shahar's answer I tried to use the oracle definition of the polynomial hierarchy, so $\Sigma\_k^P = NP^{\Sigma\_{k-1}SAT}$ and $\Sigma\_{k+1}^P = NP^{\Sigma\_{k}SAT}$.

> Remark: We defined $\Sigma\_{i}SAT$ as the set of formulas $\phi$ such that
>
> $$\phi \exists y\_1\forall y\_2 \ldots Q\_i \phi(y\_i,\ldots,y\_k)$$
>
> , where $Q\_i = \exists$ if $2 \nmid j$ and $Q\_i = \forall$ if $2 \mid j$.

However, I just do not understand why these two should be equal. Could you please give me a another hint?

# Answer
> 1 votes
**Hint 1:** Substitute directly into the definition of the hierarchy with oracles. Use induction in the proof.

**Hint 2:** It is well known that $\Sigma\_kSAT=\Sigma\_k^P$. Try to use this in your proof (make sure you learned this in class! Its an important theorem)

# Answer
> 1 votes
Hint: Try to reduce the quantified boolean statement to an equivalent one in $\Sigma\_k SAT$. This should establish the subset relationship which can be used to argue for equality of the two classes.

---
Tags: complexity-theory
---


# Question
Title: How do websites verify that an email exists during the registration process?
Everybody knows that if you try to register to a website with an email that does not exist, the website labels the email as "invalid". How do they know that?

# Answer
A common strategy is to not bother checking if the email address is valid. Instead, you just send an email to the address with a link that finishes the registration. If the address is wrong, you won’t be able to tap the link and finish registration.

In the email you include some very clear wording that this email was received because someone tried to register at your site, and if the recipient didn’t do that, then they should *not* tap the link.

You might include a code on your registration site that needs to be entered when the confirmation link is tapped, so the receiver at an incorrect email address is not able to finish the registration.

So on the registration page: “Please enter your email address. A confirmation link will be sent to your email, please enter abcd in the confirmation site”

The link sent contains an id identifying the new member, and will finalise the registration if the user enters abcd.

This will only work if the email address is the one of the person registering.
> 2 votes

# Answer
While the question of how Twitter *specifically* works is not relevant to this site, there is a real scientific question lurking here: how might software be able to tell if an email is real or not?

It is impossible to tell in general. But in practice people would use two partial methods:

* First, using pattern matching. Often an email is not legit if it does not have exactly one `@` sign, or if it contains any invalid Unicode characters. Beyond this there is no way to give any more specific check without rejecting certain valid emails.
* Second, if you have access to a database of some kind listing all valid emails. This only works if you are one of the major email providers (e.g. Google), or if you have your users log in to your site through Google's API. In these cases, Google can directly check your email against the database to see if it is valid.
> 1 votes

---
Tags: computer-networks
---


# Question
Title: Sequential History in Herlihy and Wing's Linearizability paper
I've been reading Herlihy and Wing's paper *Linearizability: A Correctness Condition for Concurrent Objects* (*ACM Transactions on Programming Languages and Systems*, 12(3):463–492, 1990; PDF) and there's one piece of the paper that is a fairly small detail, but on which I'm stuck anyway. They define a sequential history as one satisfying two conditions:

1. First event of $H$ is an invocation
2. Each invocation, except possibly the last, is immediately followed by a matching response. Each response is immediately followed by a matching invocation.

**Question 1** Since an invocation and response *match* iff they have the same *object* and *process*, does "each response is immediately followed by a matching invocation" imply that *all* events in a sequential history share the same object and process (since each event matches the prior event)?

**Question 2** Later in section 2, they offer the following as an example of a sequential history, even though it involves multiple processes:

```
q Enc(x) A
q Ok() A
q Enq(y) B
q Ok() B
q Deq() B
q Ok(x) B
q Deq() A
q Ok(y) A
q Enq(z) A
q Ok() A

```

I suspect that the definition of *sequential history* actually doesn't include the constraint "each response is immediately followed by a matching invocation" but maybe it does and I'm just misreading it. In either case, thanks for any enlightenment anyone can provide!

# Answer
> 2 votes
I'm stuck on the same detail and luckily found your post. Agree that the word "**matching**" in "Each response is immediately followed by a **matching** invocation" should be omitted. The evidence is that the word is omitted in the paper, *Axioms for concurrent objects*, by the **same authors**. Link: http://www.cs.cmu.edu/~wing/publications/HerlihyWing87a.pdf

# Answer
> 0 votes
I've come to the conclusion that the constraint "each response is followed by a matching invocation" should omit the word "matching", and the paper should be read as if it weren't there. My evidence for this is that related literature and conference proceedings seem to omit it, either literally or effectively.

For example, the proceedings *Principles of Distributed Systems: 14th International Conference* (Google Books) includes a summary of a sequential history and linearizability and omits the second constraint completely:

> History $H$ is called *Sequential* if the first event of $H$ is an invocation, and each invocation, except possibly the last, is immediately followed by a matching response.

Another conference proceedings that I found, *Networked Systems: Second International Conference* (Google Books) includes the second constraint without the word "matching":

> A history is *sequential* if its first event is an invocation, and then (1) each invocation event, except possibly the last, is immediately followed by the matching response event, and (2) each response event, except possibly the last, is immediately followed by an invocation event.

---
Tags: distributed-systems
---


title: Hoare's Axiom Scheme Precondition

text:
# Question
Title: Hoare's Axiom Scheme Precondition
I have a question about determining preconditions for Hoare's Axiom Scheme. For example, if we have `P { x=2 } x==1` and we are trying to determine the precondition, P, could we just set P as false giving us `False { x=2 } x==1`. I've read some of the other posts on this forum about Hoare's Axiom Scheme but am having a hard time wrapping my head around the topic.

# Answer
Yes. You can set P to be false. However, the resulting statement won't be very useful.

Let's back up, and consider how to interpret a statement like `P {x=2} x==2`. This is saying that for every state of the program that satisfies `P`, if you execute `x=2` in that state, then the state of the program afterwards will satisfy `x==2`. How useful is this? Well, the more states that satisfy, the more powerful and useful a statement this is -- the more you have learned.

So, a statement like `true {x=2} x==2` is correct, and also very useful: it works no matter what the prior program state. It says that, no matter the previous program state, if you execute `x=2`, then the expression `x==2` will hold afterwards.

In contrast, a statement like `false {x=2} x==2` is correct, but not useful. It is correct, because it claims that for every program state that satisfies `false`, then executing `x=2` will leave you in a program state where `x==2`. This is vacuously true, since there are no program states that satisfy `false`. However, it is not very useful. There are no program states that satisfy `false`, so there are no program states where this tells you something useful about what will happen if you execute `x=2`.

Now let's move on to the example you gave, of `P {x=2} x==1`.

How about `true {x=2} x==1`? This is incorrect. It's not true. If you start in a program state where, for instance, `x==7`, then this will satisfy `true`, but after executing `x=2`, the condition `x==1` will not be satisfied. So, that's just a faulty claim.

How about `false {x=2} x==1`? This is a correct claim. For the same reasons as explained above, it is vacuously true. However, for the same reasons as explained above, it is not useful: there are no situations where this is a useful claim to know, since there are no program states that satisfy `false`.

---

Generally we look for the *weakest* precondition. Here a precondition that is "strong" is one that is restrictive; thus "False" is strong and "True" is weak. Notice that weak preconditions are one that apply to more prior states, and thus are more useful (can be applied to a larger set of prior states), so the weaker the precondition `P`, the more useful the statement will be. In other words, the weakest precondition is in some sense the most useful precondition. "False" is a very strong precondition; while it might be a valid precondition, it is not useful.
> 1 votes

---
Tags: hoare-logic
---


# Question
Title: Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?
Let suppose we order the nodes first by degree (in + out), to get a list of node structures:

```
Node:
   labels: []   # lexicographic ordered
   out_arrows: []  # ordered by ordering of the nodes
   in_arrows: []   # ordered by ordering of the nodes

```

Then how should we order the nodes that have equal degree? Or am I approaching this the wrong way? My end goal is to have O(Q) to O(log N) graph lookup where N is the size of my library and Q is the size of a much smaller query graph. Not only that but once you convert the serialized data to a hashable type such as a string, then you can perform the search using a standard data structure (dictionary or map).

What is some work done in this area, i.e. have people already thought of this standard form serialization and search method?

---

Note that the *key* graphs my library will hold are relatively small (5-50) nodes, but their may be a million of them in the library. So it's not advised to perform a usual subgraph isomorphism search of the whole library say using Ullmann's algorithm, because for the most part, the graph is disconnected.

# Answer
Graph canonization is well-studied, and there are sophisticated algorithms for it; see https://en.wikipedia.org/wiki/Graph\_canonization. The standard answer is to use existing, well-tuned software, such as Nauty, rather than trying to invent your own.

How to implement in Python is out of scope of this site (but I would investigate API bindings or running it on the command line).

See also Graph isomorphism problem for labeled graphs.
> 1 votes

---
Tags: graphs, search-algorithms, graph-isomorphism, search, subgraphs
---


title: Pure Directed Graph

text:
# Question
Title: Pure Directed Graph
How can a directed graph be efficiently represented in a purely functional language like Haskell? Could someone suggest relevant materials on this topic? (functional pearls perhaps?) Thanks.

# Answer
There are many reasonable approaches, but one is an adjacency list representation. You can use any convenient data structure for the adjacency list; I anticipate that a dictionary (ordered map) will be useful.
> 1 votes

---
Tags: algorithms, graphs, functional-programming, haskell
---


# Question
Title: How many Integers can be represent in Double-Precision floating-point form
How to calculate the number of Integers that can be represent in Double-Precision floating-point form?

# Answer
Just count them.

You need to know the format of a double-precision floating point number. That's technically platform dependent, but practically all platforms these days use the same representation, IEEE-754 binary64. As you might expect from the format's name, that's a 64-bit encoding. It consists of three bit fields:

* sign: 1 bit
* exponent: 11 bits The actual exponent is the stored exponent - 1023 ("the exponent bias") and stored exponents 0 and 2047 (the largest value) are special. None of the values with stored exponent 2047 is an integer; these are either infinity (if the fraction is 0) or different "not a number" (NaN) values, if the fraction is not 0. If the stored exponent is 0, then the value is either 0 (if the fraction is 0) or a "subnormal" number; no subnormal number is an integer. Note that the result is that there are exactly two ways of representing 0, because the sign bit is independent. However, these are considered the same value.
* fraction: 52 bits The fraction has an implicit binary point to its left; the actual significand is the fraction plus 1. (In other words, there is an implicit 1 to the left of the implicit binary point.)

Since the fraction has 52 bits, every valid number whose exponent is at least 52 is an integer. Those numbers have stored exponents between $1023+52$ and $2046$, inclusive, which is a total of $972$ possible exponent values. For each of these, there are $2^{52}$ possible positive numbers, all distinct.

In addition, there is a representation for every integer from $1$ to $2^{52}-1$. And for every positive integer, the corresponding negative integer can be formed by setting the sign bit to 1.

So, in all, we have $(972 * 2^{52}) + (2^{52}-1) = 973\*2^{52}-1$ positive integers, the same number of negative integers, and $0$.
> 1 votes

# Answer
As rici answered, all large floating-point numbers are indeed integers, plus some small floating-point numbers, that's almost half the floating-point numbers.

But maybe you actually want to know: Which is the largest interval so that *all* integer values in that interval can be represented exactly as floating-point numbers?

Using the IEEE-754 format, 32 bit floating point numbers have a 23 bit mantissa plus one implicit leading mantissa bit, 64 bit floating point numbers have 52 + 1 bit mantissa, and 80 bit floating point numbers have a 64 bit mantissa.

As a result, all integers $-2^{24} ≤ i ≤ 2^{24}$, $-2^{53} ≤ i ≤ 2^{53}$ and $-2^{64} ≤ i ≤ 2^{64}$, depending on the format, can be represented exactly as floating point numbers; the next integer outside those intervals can't.
> 1 votes

---
Tags: combinatorics, floating-point, numerical-algorithms
---


# Question
Title: Negation of the semantics of the Until operator in LTL
I have been looking at the Until operator and the release operator and when introduced to the release operator it was suggested that it is equivalent to:

$\phi R \psi \equiv \neg(\neg\phi U \neg \psi)$

But when trying to get from the semantic definition of the Until operator to the semantic definition of the Release operator by negation I get stuck part way. Specifically, I get stuck trying to negate a $\forall j \< i$ expression as I will show below.

So the semantic definition of Until:

$\pi \models \phi U \psi \iff \exists i \geq0, \pi\[i\] \models \psi \land \forall j\leq i-1, \pi\[j\]\models \phi$

Putting the negations in:

$\pi \models \neg(\neg\phi U \neg\psi) \iff \neg(\exists i \geq0, \pi\[i\] \models \neg\psi \land \forall j\< i, \pi\[j\]\models \neg\phi)$

$\iff \forall i \geq 0, \neg(\pi\[i\]\models\neg\psi)\lor \neg(\forall j \< i,\pi\[j\]\models\neg\phi)$

$\iff \forall i \geq 0, (\pi\[i\]\models\psi)\lor (\exists j \< i,\pi\[j\]\models\phi)$

In words, I am ending up with globally $\psi$ or globally there always exists some predecessor that satisfies $\phi$. Which cannot be correct as $\pi\[j\]$ is not defined when $i=0$.

The semantic definition for the release operator that I was aiming for is:

$\pi \models \phi R\psi \iff (\exists i\geq 0, \pi\[i\]\models\phi \land \forall j\leq i, \pi\[j\]\models\psi)\lor (\forall k \geq 0, \pi\[k\] \models \psi)$

So I have part of the expression correct ($\forall k \geq 0, \pi\[k\] \models \psi \equiv \forall i \geq 0, (\pi\[i\]\models\psi)$), but I am really stumped about how to get the second part or where I went wrong.

Any help enlightening me is greatly appreciated!

Thanks!

# Answer
First, note that you did not really get the "first part the the expression correct". The first formula is, roughly, of the form

$$ \forall i, (p(i) \lor q(i)) $$ while the second one is of the form $$ r \lor (\forall k, p(k)) $$ Note the different bracketing.

That being said, you have two definitions for the semantics of the release operator, and you want to prove them equivalent. So far, you tried to manipulate those formulae according to standard logical rules (a correct approach), but failed to do so. Indeed, as far as I can see, that approach can not succeed. The nice news is that you do not need to use that approach: in order to prove that definition $A$ and $B$ are equivalent, you can also write two distinct proofs, one for $A \implies B$ and one for $B \implies A$. In writing such proofs, you can leverage all the known results from mathematics, not just those allowing formula manipulation.

In your specific case, you will need to use the well-ordering property of natural numbers, stating that any non-empty set of naturals must have a least element. Let me sketch a part of the proof.

Assume your first definition, and let's prove the second one. We consider two cases.

1. If $\pi\[k\] \models \psi$ for all $k$, then the second definition is trivially true.
2. Otherwise, $\pi\[k\] \not\models \psi$ for some $k$. This means that the set of natural numbers $\\{k|\pi\[k\] \not\models \psi\\}$ is not empty, hence has a least element -- let $m$ be that element. This means that $m$ satisfies $\pi\[m\] \not\models \psi$, and that (minimality) $\forall n\<m, \pi\[n\] \models \psi$. Now, using the hypothesis, we can obtain that $\exists j\<m, \pi\[j\]\models\phi$. From this and minimality we obtain the thesis.

Note that you still need to prove the other direction.
> 2 votes

# Answer
Not sure whether its correct but I think that the until operator for LTL requires at least one instance of the pre condition to hold so

⊨⟺∃≥0,\[\]⊨∧∀≤−1,\[\]⊨

should really be

⊨⟺∃≥1,\[\]⊨∧∀≤−1,\[\]⊨

since you can't have without first having so the reason you get the undefined behaviour at i = 0 is because your original definition is wrong. There is not an i = 0 where \[\]⊨
> 0 votes

---
Tags: logic, semantics, model-checking, linear-temporal-logic, predicate-logic
---


# Question
Title: Are there any FNP-complete problems with a unique solution?
Are there any FNP-complete problems where there's only one possible solution?

For example, the travelling salesman problem can have multiple routes all shorter than $X$. There's only one shortest route, but it can't be validated that a given route is the shortest route in polynomial time.

I'm interested in either such an FNP-complete problem, or a proof this is impossible.

# Answer
> 1 votes
Are we talking about solutions or certificates? Since NP-complete problems are decision problems, a solution (to each instance) is always either "yes" or "no" and hence it's unique.

If we are talking about certificates, then no. Each yes-instance of a NP-complete problem admits infinitely many polynomial-length certificates. Indeed if $c$ is a yes-certificate and $T$ is a verifier, then you can always consider the certificate obtained by prepending, e.g., any number $k$ of zeros to $c$. The corresponding verifier is obtained from $T$ by first dropping the leading $k$ zeroes and then simulating $T$.

# Answer
> 1 votes
Travelling salesman problem: Given a number of locations and distances, we can ask: 1. Is there a tour of length \<= L? 2. Is L the length of the shortest tour? 3. Which is a shortest tour?

The first is obviously in NP. The second is obviously in co-NP. The third is not a decision problem. So there is no certificate for “is R the shortest route” unless NP = co-NP.

But take “Hamiltonian path”: Given n locations which are all connected or not connected, is there a path connecting them all?

Apart from the fact that there are 2n essentially equal paths, it seems quite possible that some instances will have exactly one connecting path and therefore a unique certificate based on the path.

# Answer
> 0 votes
This question is knows as UP versus NP

EDIT: turns out the author of this paper is a crank, so you can ignore the rest of this answer.

Surprisingly enough it's been proved that UP=NP!

The Quadratic Congruences problem asks if, for constants $a$, $b$, and $c$, there exists $x$ such that $x\<c$ and $x^2 \equiv a\mod b$. It is known to be NP-complete even if we know the prime factorization of $b$.

The paper shows that given any solution to this problem we can find the smallest positive solution in polynomial time if we have the prime factorization of $b$. This means that the question:

For constants $a$, $b$, and $c$, what is the smallest positive $x$ such that $x\<c$ and $x^2 \equiv a\mod b$?

Is both FNP-complete and has a unique solution.

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


# Question
Title: What does it mean to 'provide' an API call?
So I have a database pre-loaded with data related to food recipes and the assignment says: 'Provide an API call that allows us to specify an ingredient or set of ingredients and return full recipes containing those ingredients.'

I am not sure if this means to create a webpage with a search box that would allow the client to enter text, search, and display recipes from the search query?

Any good opinion would be helpful.

# Answer
> 1 votes
An API is an Application Programming Interface. So it is intended for two progammmed component to communicate. It is not a Human-Machine Interface, hence does not involve a web page for communication.

In your question, it could be a subprogram (in whatever variant or language) that can be called, with ingredients spécified in some way, possibly as parameters or in some other way such as global variables. This subprogram would get the recipies and make them available to the caller program in some adequate way.

Getting more into specifics depends on the various constraints of the system being developed. So here it is up to you as only you know the details.

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


title: Find k closest numbers to the median

text:
# Question
Title: Find k closest numbers to the median
The formal problem statement is: Given a set S of n distinct numbers and a positive integer k\<=n, determine the k numbers in S closest to the median.
**My thoughts:**
I have read about the median of median algorithm, which goes like group n elements in groups of 5 and finds the median of them and then recursively finds the median of the resulting array, which will have size n/5. This runs in O(n) time. So once we have the median, how to go about finding the k closest element to it, that seems to be another tricky thing.

# Answer
> 2 votes
**Hint 1:** try to transform the $n$ elements in such a way that the $k$ closest to the median will be the smallest $k$ elements after the transformation.

**Hint 2:** now use a standard algorithm to find the $k$'th smallest value (also known as the $k$'th order statistic). You might have learned an algorithm that computes this as a variation of the quickselect algorithm

---
Tags: algorithms
---


# Question
Title: Finding permutation of jobs such that each job finishes before deadline
Consider a set of jobs, each having its deadlines and process time. How to find a permutation of them such that if they are executed in that sequence, they all finish before their deadline
or figure out that no such permutation exists.

**My Thoughts:**
There could be some greedy strategy, but I am not sure how to arrive at that.

# Answer
> 2 votes
The greedy strategy you are looking for is Earliest-Deadline-First and it's optimal in minimizing maximum lateness.

Minimizing sum of latenesses is NP-complete.

---
Tags: algorithms
---


# Question
Title: Is there a more efficient way to obtain the optimal input sequence in this finite-state system
**Context:**

Consider $M$ finite state systems with evolution given by: $$ x^i\_{k+1} = f(x\_k^i,u\_k) $$ where $x\_k^i\in\\{1,\dots,X\\}$ is the state of system $i\in\\{1,\dots,M\\}$, $k\geq 0$, and $u\_k\in\\{1,\dots, U\\}$ is some input which we can use at time $k$ to control the evolution of all systems (notice that $u\_k$ is shared across the $M$ systems). In addition, $f:\\{1,\dots,X\\}\times\\{1,\dots,U\\}\to\\{1,\dots,X\\}$ is the same for all systems as well.

The goal is to choose the correct sequence $u\_0,\dots,u\_K$ to minimize $$ J = \sum\_{i=1}^M J\_i, \ \ \ \ J\_i = \sum\_{k=0}^K g(x^i\_k, u\_k) $$ where $K\>0$ is some maximum time to be considered, and given some initial states $x\_0^1,\dots,x\_0^M$.

If $M=1$, I have observed that this is basically a deterministic finite state system optimal problem, which can be solved using dynamic programming. The solution is to construct a transition graph of how $x\_k$ evolves in time according to the decisions $u\_k$ and vertices weighed by $g(x\_k,u\_k)$. Then, one can find the shortest path in such transition graph, starting from $x\_0$. This can be solved in polynomial time in $K, X, U$. (I am following "Dynamic programming and optimal control", Ch 2 from D. Bertsekas for this part)

**Issue:**

For general $M$, one can stack all state vectors in $x\_k = \[x\_k^1,\dots,x\_k^M\]^T\in \\{1,\dots,X\\}^M$ which result in a deterministic finite state system as well. However, now the amount of states is $X^M$. Thus, if we attempt to use the previous approach using dynamic programming, the most we can achieve is polynomial time in $X^M$ which is not polynomial in $M$.

**Question:**

Is there a way to solve this problem, resulting in a polynomial time in $M$?

I'm not sure this is possible. However, the fact that the systems do not interact with each other (other than sharing the input $u\_k$) makes me think there is something smarter we can do other than stacking together the state of all systems.

# Answer
It's NP-hard, so no, there is no polynomial-time algorithm (unless P=NP).

You can construct a reduction from 3SAT. A formula $\varphi$ with $M$ clauses on $K$ variables corresponds to $M$ finite state systems run for $K$ steps. Here $u\_k$ is the $k$th variable, and you construct $f,g,x\_0$ so that $\sum\_k g(x^i\_k,u\_k)$ is zero if $u\_1,\dots,u\_K$ satisfy clause $i$ of $\varphi$, or $\>0$ if not. (This can be easily arranged. You have $2M$ states, each of the form $(i,\text{True})$ or $(i,\text{False})$; $x^i\_0=(i,\text{True})$; $f$ is designed so that if you read in a variable that violates clause $i$ while in state $(i,\text{True})$, you transition to $(i,\text{False})$; and $g(i,\text{True})=0$ and $g(i,\text{False})=1$.) Now there exists an input sequence such that $J=0$ iff $\varphi$ is satisfiable.
> 2 votes

---
Tags: dynamic-programming, shortest-path, optimal-strategy
---


# Question
Title: What is the point of encoding universal turing machines?
I am unable to understand why do we need to encode turing machine at all? I heard that we are trying to build a programmeable turing machine but can't relate how encoding it will make this programmeable.

Please share some insights. PS I have seen different encoding in different slides, are all encodings fine?

https://slideplayer.com/slide/6019689/

here is different encodings.

here is again different encodings-:

https://www.cs.usfca.edu/~galles/cs411/lecture/lecture15.pdf

# Answer
> 2 votes
It does not matter whether we are thinking about Turing machines or actual computers that you use every day – they all *encode* information all the time.

A computer can process *only* sequences of bits $0$ and $1$ (and even $0$ and $1$ are further encoded as electrical signals). It cannot process any text, nor images, nor sound *directly*. *All* data that is ever processed by a computer is encoded using $0$'s and $1$'s. I hope that's clear.

Now, a computer may simulate another computer. Here is a ZX Spectrum simulator which simulates my childhood computer on your computer. But of course, you do not think that your computer contains an actual small copy of a 1986 computer, do you? It's clear that there is a *program* which simulates ZX Spectrum – and that program is made of $0$s and $1$s that encode Spectrum ZX.

The situation is entirely analogous with Turing machines. If you want one Turing machine to simulate another, you *must* represent it on the tape somehow – because just like ordinary computers work with $0$s and $1$s, so Turing machine work with whatever is written on the tape. When you write down a description of a Turing machine onto a tape, well that is when you encoded it.

# Answer
> 1 votes
The Turing Machine is thought (Church-Turing thesis) to perfectly represent the intuitive idea of computation; that is, for any operation that is computable, a Turing Machine exists. After the Turing Machine is defined and understood, a logical next step for automata theory research is to consider what properties of Turing Machines can be computed by Turing Machines.

The input taken by a Turing Machine is a finite string; therefore in order to be passed as an input, a TM must be rendered into a string that unambiguously describes it. Without establishing the existence of a formal encoding the idea of passing a TM as input would be a poorly-defined procedure.

The slides you have attached show a binary encoding is used with unary values and zero as a separator symbol; this is not the only possible encoding and encodings do not have to be strictly binary, any fixed-size symbol set will do. However, binary is often preferred because of its simplicity, the analogy to real-world binary computers and to show the power of TMs even with very limited symbol sets. Any encoding that uniquely describes any TM with a finite set of symbols works – the important thing is that we know encoding a TM as a finite string is possible.

As for programming: one particularly interesting outcome of encoding Turing Machines is the existence of the Universal Turing Machine: a TM that, for some selected type of encoding, is capable of simulating *any* thus encoded Turing Machine given to it as an input and determine its state, tape contents and head position after an arbitrary number of steps. This is important for two main reasons: it is the theoretical cornerstone for the idea of a programmable computer, and it is exceedingly useful for almost any theoretical work on the computability of various properties of TMs.

# Answer
> -1 votes
**In a nutshell:** *Suppose there is no encoding, but the initial specification of the Turing Machine (TM). Then the universal Turing machine (UTM) has in its tape alphabet all the tape symbols of the simulated TM. Since it can simulate any TM, and there is no bound on TM tape alphabet size (though each is finite), the UTM must have an infinite set of tape symbols. This is not permitted as all (U)TM must be finitely specified.*

First I should remark that your title is wrong: we do not need to encode universal Turing machines (UTM), but the Turing machines (TM) that we wish to simulate with the UTM.

First we must at least agree on a standard format to represent TMs, so that we can define them precisely, and use them for proofs or hand simulation. This representation must be a string since it is intended to be put on the UTM tape. Basically we use a state alphabet and a tape alphabet plus a few other symbols such as L and R, and a variety of punctuation symbols, so that we can represent each of the transitions. Then we can represent the TM as a long string composed of all the small string representing the transitions, plus various details that may be needed such as the initial state and the list of accepting states, and a few symbols to separate the string components and read them when needed.

Given such a presentation $\xi$ of a TM $M\_\xi$, one can simulate by hand its computation on a tape $\tau$ in $\Sigma^\star$.

A universal Turing machine (UTM) is a TM that will do that same simulation of $M\_\xi$ when provided with a tape containing the specification of $M\_\xi$ and the tape content on which $M\_\xi$ is supposed to compute.

As I understand it, the question you ask is why do you have to encode the specification of $M\_\xi$ rather than than use directly the original specification $\xi$ with the original alphabets as they were given.

A first reason is very simple. The UTM is supposed to be able to simulate all machines, but its tape alphabet may not contains the symbols used in the TM specification $\xi$. Fortunately, all specifications are defined up to symbol renaming. This allows us to replace any set of symbols (alphabet, state set, ...) by another such set of the same size. Thus we can replace all the symbols in $\xi$ by symbols in the tape alphabet $\Sigma\_U$ of the UTM. This may be seen as a very simple encoding. But it is not enough.

The next problem may be that the tape alphabet $\Sigma\_U$ is too small, smaller than the number of distinct symbols in $\xi$. Whatever the design of the UTM, this is bound to happen because a UTM must have a finite tape alphabet, but there is no bound on the (finite) size of TMs.

The answer to that is to encode the symbols in $\xi$ not with symbols of $\Sigma\_U$, but with a set of strings chosen in $\Sigma\_U^\star$. And there is an infinite number of them.

There are other reasons why this encoding is necessary for the TM to be simulated by a UTM, but this at least tells you why you cannot do without it.

The UTM may be seen as a programmable computer that executes a compiled program (the encoded TM specification) produced by a compiler (the encoding process) from a high-level language (the initial TM specification).

---
Tags: turing-machines
---


# Question
Title: Convert a dfa to rule for a asterisk case
Here is a simple but very common grammar rule case in EBNF format, the `Statements` is a none terminal symbol and `Statement` is none terminal symbol:

```
Statements ::= (Statement ';')*

```

After converting this rule to NFA, and then do the subset contruction for converting the NFA to DFA, and at last get the dfa:

```
State0 -> Statement -> State1 -> ';' ->State0
State0 -> ε -> State0

```

The `State0` is the DFA's start state representing the none terminal symbol `Statements`, also it is the finish state. From `State0` input `Statement` and traslate to `State1` and input ';' at `State1`, translate to `State0`. Also, `State0` could translate to self with the `ε`.

And after converting the above dfa to regular grammar following the algorithm in dragon book, i get the following grammar rules:

```
Statements -> ε
Statements -> Statement Extend_NT
Extend_NT  -> ';' Statements

```

It added the new none terminal symbol `Extend_NT`, but i want to get the following the regular grammars which does not contain the extend symbol `Extend_NT`:

```
Statements -> ε
Statements -> Statement ';' Statements

```

So the question is that is there any algorithm could get the above result that does not contain the new none terminal symbol `Extend_NT`?

Or it is just a engineering problem?

Solved: I have solved this by removing the extend symbol in parsing stage. For example, in LALR parsing stage, when to reduce a symbol, i can remove the extend symbol at same time.

# Answer
> -1 votes
Solved: I have solved this by removing the extend symbol in parsing stage. For example, in LALR parsing stage, when to reduce a symbol, i can remove the extend symbol at same time.

---
Tags: finite-automata, formal-grammars, regular-expressions, compilers, parsers
---


# Question
Title: Automated Query Equivalence Solver (MongoDB)
The query-equivalence problem is undecidable. However there are theorem provers that attempt to solve instances of undecidable problems. I am curious how I could go about using an automatic theorem prover (or other solvers) to prove that one MongoDB query is equivalent to another. The MongoDB query language is large, so I will focus on a small subset in the aggregation language.

Although my target is the MongoDB aggregation language, I think advice for query equivalence for SQL would be helpful too.

For example let's say I want to prove `[$match: {...}, $sort: {...}]` is equivalent to `[$sort: {...}, $match: {...}]`. \\$match and \\$sort pass documents from the previous pipeline stage to the next. \\$match is a filter that only passes on documents where its predicate argument evaluate to true, and \\$sort takes all documents given and sorts them on a field, then returns all documents. Essentially these are SQL `WHERE` and `ORDER BY` on a particular collection.

I understand why these queries produce the same result but I do not know how to prove it, or how to encode queries to allow a theorem prover to attempt to solve the problem.

How do I encode a query for a solver? It seems like I would need to communicate the behavior of different operators to it, like for example expressing that sorting an array leads to an array with the same elements but in increasing order. Thank you!

# Answer
I'm not an expert on formal verification, so I'll share a non-expert perspective.

A general approach is: formalize the semantics of each operation (in whatever logic is accepted by your chosen theorem prover), then formulate the theorem you are trying to prove (that both queries yield the same results for all possible databases), then ask the theorem prover to prove it.

The details of how you go about that will depend a lot on the particular theorem prover you have chosen, the set of operations you want to support, how you formalize the semantics of each operation mathematically, and how much human assistance you want to provide the theorem prover.

There are a wide range of theorem provers, which strike different points in the tradeoff between automated proving (without human assistance) vs expressivity and based on different mathematical logics.

There are also likely to be multiple ways to formulate the semantics of the operations mathematically. For instance, suppose you know that all of your operations will only select some of the rows of input and/or re-order them, but will not produce new rows not found in the input or modify existing rows. Then the output of an operation could be represented by a sequence $(r\_1,r\_2,\dots,r\_k)$ of indices, where $r\_i$ is the index of a row in the input (namely, the $i$th row returned by the operation). Then each operation becomes a function $f$ that maps from an input to a sequence $r$; you can formulate the semantics of the composition of operations; and proving the equivalence of operations amounts to proving that they represent the same function.

Another approach, instead of formulating this as theorem proving of mathematical statements, would be to formulate this as formal verification of programs. You can view an operation as a program that takes an array as input (the database is an array of rows), and produces an array as output (an array of rows). You can write down code that implements the sort operation, and code that implements the match operation. So, now you can write down two subroutines: one that sorts then matches; and one that matches then sorts. Finally, you can try to use formal verification to prove that both subroutines yield the same output, on all possible inputs.

If you try to do this in practice, you'll probably quickly run into the limitations of the current state of the art in automated theorem proving and program verification. Theorem provers generally require a lot of hand-holding to prove non-trivial mathematical statements (they may require you to specify statements of lemmas that are useful to proof, or give hints on how to prove a statement). Program verification tools also generally require a lot of hand-holding to verify non-trivial programs correct (for instance, they may require you to specify many loop invariants). They are getting better, but it's still a non-trivial effort.

To learn more, you might start by looking at how to formally verify a sorting algorithm correct. That will give you ideas on possible ways you could formulate the kinds of properties you want to prove.

See also A general picture of formal verification in software.
> 1 votes

---
Tags: undecidability, database-theory, databases, automated-theorem-proving
---


# Question
Title: What is the difference between NP hard and NP complete?
What is the definition of P, NP, NP-complete and NP-hard?

here is a good answer but it really doesn't answer mym question.

> np-hard-: a problem A is NP hard if for all B$\in$NP, B is polynomial time reducible to A.(i.e A is easier than B). Then why is A called NP Hard? It should be called NP easy problem? Isn't it?

> np complete-: A problem is NP complete if problem is in both NP and NP hard.

SO basically np complete=np hard. What is the difference between np hard and np complete?

# Answer
> 2 votes
So I got it. NP hard problem is not necessarily in NP. That's the difference.

---
Tags: complexity-theory
---


# Question
Title: Comparing various ways to move a game actor having time-dependent velocity
Assume I have a game actor (name it `MyActor` for further references) to be moved up and down according to $z=f(t)=A\sin \omega t$ (or any non constant velocity). The game engine provides us with

* callable `GetGameTimeSinceCreation()` to obtain the age of the actor.
* overridable `Tick(float DeltaTime)` in which we put our code to move the actor.

Note that if we invoke `GetGameTimeSinceCreation()` in `Tick(float DeltaTime)` as follows

```
void MyActor::Tick(float DeltaTime)
{
   float PreviousAge = GetGameTimeSinceCreation() - DeltaTime;
}

```

`GetGameTimeSinceCreation()` called in the **current** tick is equal to `GetGameTimeSinceCreation()` called in the **previous** tick plus `DeltaTime` called in the **current** tick.

I found there are 3 ways to move the actor:

### Case 1: Only use $z=f(t)$

```
void MyActor::Tick(float DeltaTime)
{
   float T = GetGameTimeSinceCreation();
   Location.Z = A*Sin(W*T);
}

```

### Case 2: Use $z(t)=z(t-\Delta t) + f'(t) \\,\Delta t$

\begin{align} z(t) &= z(t-\Delta t) + \lim\_{\Delta t \to 0}\frac{f(t)-f(t-\Delta t)}{\Delta t}\\,\Delta t\\ &= z(t-\Delta t) + f'(t) \\, \Delta t \end{align}

```
void MyActor::Tick(float DeltaTime)
{
   float T = GetGameTimeSinceCreation();
   Location.Z += A*W*Cos(W*T)*DeltaTime;
}

```

### Case 3: Use $z(t)=z(t-\Delta t) + f(t)-f(t-\Delta t)$

\begin{align} z(t) &= z(t-\Delta t) + \frac{f(t)-f(t-\Delta t)}{\Delta t}\Delta t\\ &= z(t-\Delta t) + f(t)-f(t-\Delta t) \end{align}

```
void MyActor::Tick(float DeltaTime)
{
   float T = GetGameTimeSinceCreation();
   Location.Z += A*(Sin(W*T)-Sin(W*(T-DeltaTime)));
}

```

### Question

In my opinion:

* Case 1 is accurate and needs least computations.
* Case 2 is approximation but needs less computations compared to Case 3.
* Case 3 is approximation and needs more computations.

I am wondering why there are still game developers using Case 3, for example, in this tutorial (please proceed to the end of Step 3 to see the relevant code).

I want to know the differences between them from computer scientist's perspective.

# Answer
I can't see any general answer -- I expect it might depends on the circumstances. In the specific situation you mentioned, for the specific choice of $f$ you mention, Case 1 seems better to me, if we ignore the computation time. Cases 2 and 3 might suffer from accumulated roundoff error. For some functions, Case 2 might be faster.

But who knows? I could imagine in some applications there could be other considerations that are not apparent here, or that vary depending on the specific usage.
> 2 votes

---
Tags: comparison, computer-games
---


# Question
Title: What does $g \to \lambda$ mean in the L-System for the dragon curve?
I am playing with L-System using the wonderful tool `jflap`. Below is the L-System for the dragon curve in the "JFLAP book: JFLAP – An Interactive Formal Languages and Automata Package " (you can find it in the left column of its homepage).

What does the third rewriting rule "$g \to \lambda$" mean? I did not find any references.

# Answer
> 3 votes
"$\lambda$" is commonly used to represent the empty string, although "$\epsilon$" could be the more common one.

This was introduced earlier in that book, section "3.1 Grammar Editing" of chapter "Regular Grammars".

> On the last row you will enter the production $A \rightarrow \lambda$, a $\lambda$-production. To do this, enter $A$ into the left cell, but leave the right cell blank. **The right field is really empty, but will display with a $\lambda$** to signify that it is a $\lambda$-production.

In the case of $\text{L}$-system, a $\lambda$-production rewriting rule means the symbol on the left will be gone in the next iteration.

---
Tags: formal-languages, automata, formal-grammars
---


# Question
Title: How many possible arithmetic operations are there between two N-bit numbers?
It's generally considered to be the case that there are sixteen possible *logical* operations between two N-bit numbers and four possible *logical* operations on one N-bit number. I'd like to know how many possible *arithmetic* operations there are between two N-bit numbers. I'm asking in the context of ALU design, so I think in order to answer, it might first be helpful to clarify what precisely "arithmetic" means in this context. I suppose it is something to do with operations that can be expressed in algorithms that use a carry bit and maybe it means that they operate on numbers in two's compliment (or not) but this is all quite vague and insufficient to answer the question.

# Answer
Due to the imprecise nature of the question, it is hard to give a precise answer. Since my "post" mostly shares links to my own thoughts and answers to related questions, I won't even try to pretend that this would be an appropriate answer to the question (-\> community wiki).

> I'm asking in the context of ALU design, ...

I also pondered questions related to arithmetic and CPU primitives in the past, but more from the perspective of the "user" of the CPU, not the "designer".

The answer to my question Which associative and commutative operations are defined for any commutative ring? hints at how to answer this type of question from a category theory perspective where "natural operation" has a precise meaning. The discussion also provides examples of operations that are not "natural" in that sense, but are still defined generically for any commutative ring.

My motivation for pondering questions of which CPU primitives would be needed for "good support of parallelization" of the type that "would be available to hardware itself on the circuit level" can be seen in my question Is scalable hardware support for LogCFL (= sAC^1) possible? and in my unfocused review of related work and "opinions" in ALogTime, LogCFL, and threshold circuits: dreams of fast solutions. Uzi Vishkin seems to have made a much more serious effort than I ever will, and even argued his case from an economic perspective:

> Alas, the software spiral is now broken: (a) nobody is building hardware that provides improved performance on the old serial software base; (b) there is no broad parallel computing application software base for which hardware vendors are committed to improve performance; and (c) no agreed-upon architecture currently allows application programmers to build such software base for the future

My own CPU "user" perspective (and actual relevant work and an appropriate short survey of existing work) can be seen in Theory and practice of signed-digit representations and in my answer to the question What number representation is this? This material might be interesting in that it shows that there is both relevant existing work that is not widely known, as well as useful representation systems not yet properly explored and worked out.

I recently revisited that kind of questions from the perspective to focus less on numbers and arithmetic: Useful primitives CPUs could provide, from TC0 (or NC1)

> I just listened to XYZ talking about "How Universal Is the Idea of Numbers?", and bashing the concept as an accidental historical artifact. He suggested that totally different computational primitives could exist, that are sometimes more useful than numbers.

Interestingly enough, I learned this Monday about concrete actually missing CPU primitives from this perspective: "shuffle" operations between the individual bytes and bits of CPU registers. AES seems to use those, and the non-availability of those "shuffle" operations currently seems to make hardware implementation much faster than software implementation than really necessary. But that still raises the basic question again whether it would have been possible for CPUs to provide a sufficiently comprehensive set of primitives.
> 1 votes

# Answer
There are 2n input bits, and if you assume a carry bit, it's 2n+1 input bits. There are n output bits plus a carry bit, so n+1 output bits.

For each output bit we can divide the set of input bits into those that produce an output of 0, and those that produce an output of 1. There are $2^{2n+1}$ possible ways to choose a subset of 2n+1 input bits.

Since there are n+1 output bits, we raise this to the power n+1, for a total of $2^{(n+1)(2n+1)}$ possible arithmetic functions processing 2n input bits and a carry bit, and producing n output bits and a carry bit. Without the carry bit, it is just $2^{2n^2}$ possible arithmetic functions.
> 0 votes

# Answer
Let us define the logic for all arithmetic as: XOR3(A,B,C)

Only difference between arithmetic functions would be how carry or borrow passes between slices. I support at least seven useful carry chain configurations in my own ALU.

Carry, Borrow, Worrob (B-A's carry for reverse subtraction) Borrow-like magnitude comparisons A=B, A\<=B, A=\>B, A\<\>B. I count seven meaningful ways to pass carry.

Not counting options that lock the chain for logic. Not counting rotate left, which also gives A plus A.

https://hackaday.io/project/174243/gallery#2b97119f08463dbe2b61c01254eea4ba
> 0 votes

---
Tags: logic, arithmetic
---


# Question
Title: polynomial time approximation algorithm problem
How can we actually define a polynomial-time 4-approximation algorithm for vertex cover or knapsack problem?

For say we have 2 approximation problems which less than equal 2C\*. But when we have a larger or 4 approximation sizes how we can derive it.

# Answer
For vertex cover: start with an empty vertex cover $S$. Iteratively consider the edges of the graph. For each edge $e=(u,v)$, check if $\\{u,v\\} \cap S = \emptyset$. If that's the case we say that $e$ is **special** and we add both $u$ and $v$ to $S$.

At the end of the algorithm $S$ is a vertex cover containing at most twice as many vertices as a minimum vertex cover. To see that that's the case notice that special edges form a matching, that $|S|$ is twice the number of special edges, and that all vertex covers must contain at least one endpoint of each special edge.
> 1 votes

---
Tags: algorithms, time-complexity, np-hard, approximation, polynomial-time-reductions
---


# Question
Title: Window slider difference between GoBackN vs Selective Repeat
I am trying to learn about GoBackN and Selective Repeat ARQ. And I have the following practice question:

> Consider sender A and receiver B which communicate using an ARQ protocol. The current window at A is \[12, 18\] and A receives ACK 16 from B.
>
> a. What is the new window of A when A and B implement Go Back N ARQ? Provide an explanation of how you obtained your result.
>
> b. What is the new window of A when A and B implement Selective Repeat ARQ? Provide an explanation of how you obtained your result.

My answers are:

a) The slider doesn't move until the ACK 12 arrives, if the ACK 12 doesn't arrive until the timer goes off, then A sends the packets 12 to packet 18 once again.

b) The slider doesn't move until the ACK 12 arrives, if the ACK 12 doesn't arrive until the timer goes off, then A sends the packets 12. Other packets that didn't receive their relative ACKs are also sent if their timers go off as well, but packet 16 is acknowledged so it is skipped.

Are my answer and logic correct? If not, what is the problem with it? Thanks a lot in advance

# Answer
> 0 votes
You should check whether GoBackN uses **cummulative** acknowledgements or not. Personally, I do not see how GoBackN can work with selective acknowledgements, but I have heard that there are some books that describe GoBackN without them.

Assuming that acknowledgements are cummulative, your answer to (a) is incorrect. In this case packet 16 will implicitly acknowledge packets before 16 and thus window will slide, to (please check numbers) \[17, 23\].

Note: missing ACKs can mean either that the packets were not delivered, or that packets were delivered, but ACKs were lost. The sender can obviously not distinguish between these two. In case of GoBackN with cummulative acknowledgements, in this case you can actually avoid retransmissions.

Note 2: why I don't understand how GoBackN works without cummulative ACKs. Suppose that packets 12-16 are actually delivered, but ACKs 12-15 are lost. ACK 16 is ignored, and eventually, packets starting with 12 are retransmitted. At the same time the receiver is expecting packet 17. What is the receiver supposed to ACK when packet 12 arrives. In case of cummulative ACKs, receiver always ACKs last received (or next expected) sequence numbers, and sender corrects his window.

The case with selective acknowledgements works as you descirbed.

---
Tags: computer-networks
---


# Question
Title: What is the outermost class 2^Σ* referring to on the Extended Chomsky Hierarchy?
After having searched a bit, it seems I can't find terminology or references for this outermost class, 2Σ\* in blue -- see below. What is it describing?

# Answer
> 2 votes
$2^{\Sigma^{\*}}$ means the powerset of the full language $\Sigma^{\*}$. It means the set of all subsets of $\Sigma^{\*}$, including the empty set and $\Sigma^{\*}$ itself, i.e., all possible languages with alphabet $\Sigma$.

Here is the simple understanding. When we want to describe a language $X$ with alphabet $\Sigma$, for each string $w$ in $\Sigma^{\*}$, there are $2$ choices, including $w$ in $X$ or excluding $w$ from $X$. All these choices are independent.

---
Tags: terminology, chomsky-hierarchy
---


title: Linear programming for prefix of graph

text:
# Question
Title: Linear programming for prefix of graph
Question: Consider an arbitrary directed graph $G$ with weighted vertices, the weights can be positive, negative or $0$. The prefix of $G$ is a subset of vertices $P$ such that there's no edge $(u \rightarrow v)$ if $v \in P$ and $u \not\in P$. Find an integer linear programming to describe the maximum weight prefix of G.

I'm new to linear programming and struggling in come up a LP solution.

The objective function seems trivial, we let $x\_v$ be a variable to indicate whether that vertex in or not in the prefix. Thus we have, $$\sum\_{v \in V} w(v)x\_v$$

However, I'm not sure how to impose the prefix constraint such that if we pick a vertex $v$, we must have to pick its prefix vertex say $u$, if there's a directed edge from $u$ to $v$. So it seems like we have to check all edges, for each directed edge $(u \rightarrow v)$, if $v \in P$ then $u \in P$. I can only describe this verbally, any suggestion is highly appreciated.

# Answer
To encode the fact that if $(u,v)$ is an edge then you you cannot have $u \not\in P$ and $v \in P$ you can add (for each edge) the following constraint:

$$ (1-x\_u) + x\_v \le 1, $$

equivalently: $$ x\_v - x\_u \le 0. $$
> 2 votes

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


# Question
Title: How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?
According to this Wikipedia article, unrestricted grammars are equivalent to Turing machines. The article notes that I can convert any Turing machine into an unrestricted grammar, but it only shows how to convert a grammar to a Turing machine.

How do I indeed do that and convert the Turing machine the recognizes language $L$ into an unrestricted grammar? I have tried replacing transition rules with grammar rules, but a Turing machine can have many different configurations of states as well...

# Answer
We encode the Turing machine's tape content in sentential forms; a special set of non-terminals encodes the current state. There can only be one of them in the sentential form at any point in time, placed to the right of the symbol the TM is currently pointing at.

The second crucial idea is that we have to *reverse* the process: TMs take the word as input and convert it to $1$ or $0$, or they don't terminate. The grammar, however, has to generate the word. Luckily, grammars are inherently non-deterministic, so we can just let it "guess" where the accepting $1$ came from; all words that cause the TM to accept can be generated then.

Let $\cal{Q} = \\{Q\_0,\dots,Q\_k\\}$ the set of state-nonterminals; w.l.o.g. let $Q\_0$ be the starting-state-nonterminal and $\cal{Q}\_F \subseteq \cal{Q}$ the set of accepting-states-nonterminals. First, we need starting rules that generate all possible accepting configurations:

$\qquad \displaystyle S \to \\#1Q\_f\\# \qquad$ for all $Q\_f \in \cal{Q}\_F$.

Similarly, we terminate when we "reach" the starting state in the correct position, namely on the first symbol:

$\qquad \\#aQ\_0 \to \\#a \qquad$ for all $a \in \Sigma$.

Translating the actual state transitions is straight-forward:

$\qquad \begin{align} aQ &\to cQ' \qquad\ \\,\text{ for } a,c \in \Sigma \land (a,Q,N) \in \delta(c,Q') \\ aQb &\to acQ' \qquad \text{ for } a,b,c \in \Sigma \land (b,Q,L) \in \delta(c,Q') \\ abQ &\to cQ'b \qquad\\, \text{ for } a,b,c \in \Sigma \land (a,Q,R) \in \delta(c,Q') \end{align}$

There are some technical kinks to iron out; for instance, you have to get rid of the boundary markers $\\#$ at the end. That can be done by spawning two special nonterminals instead of terminating, swapping those to the ends and then removing the $\\#$ along with them. Furthermore, more $\\#$ have to be created on demand; that requires some hacking of the rules with $d=\\#$.

Also, the construction becomes a bit more complicated if the TM uses non-input symbols. In that case, the termination rules may be wrong: if there are non-input symbols somewhere on the tape, we have not generated a proper word. This can be fixed similarly to removing $\\#$: spawn a special non-terminal from $Q\_0$ that is swapped to the right and only removed if all symbols are from $\Sigma$.
> 10 votes

# Answer
Here's another way to do it without going in reverse.

Assume WLOG that the Turing Machine clears the tape before accepting and has special markers $\triangleright, \triangleleft$ denoting the start and end of the tape that is in use. Furthermore, assume that there is a single accept state, so that the unique accepting configuration is $\triangleright q\_{accept} \triangleleft$. The strategy will then be to start with $\triangleright q\_{start} w \triangleleft w$, simulate the TM with the rules of the grammar (within $\triangleright, \triangleleft$) and then send $\triangleright q\_{accept} \triangleleft \to \epsilon$.

The start variable of the grammar has the following rule $$ S \to \triangleright q\_{start} B. $$

Where $B$ is the start symbol for a grammar generating $\\{w \triangleleft w: w \in \Sigma^\*\\}$ (Check here for a reference on how to do this.)

For each transition of the form $\delta(q, a) = (q', a', R)$ have the rule

$$ qa \to a'q' $$

For each transition of the form $\delta(q, a) = (q', a', L)$ have the rule

$$ bqa \to q'ba' $$

Following the convention that going left past the end of left end of the tape makes you stay in place you also need rule $\triangleright q a \to \triangleright q' a'$.

Also, allow the tape to extend to the right if needed using the rule $\triangleleft \to \sqcup \triangleleft$, and allow the tape to shorten with $\sqcup \triangleleft \to \triangleleft$. You can show by induction that the configuration at of the Turing machine is exactly the intermediate string generated by the grammar after any number of steps.

Finally, add the rule

$$\triangleright q\_{accept} \triangleleft \to \epsilon.$$

So that for any $w \in L(M)$,

$$ S \to ... \to \triangleright q\_{start} w \triangleleft w \to ... \to \triangleright q\_{accept} \triangleleft w \to w. $$

If $w \notin L(M)$, we never reach $\triangleright q\_{accept} \triangleleft$, and the grammar never terminates.
> 1 votes

---
Tags: formal-grammars, turing-machines, simulation
---


# Question
Title: A question about hash problems in CLRS book
Consider the following problem 11.2-6 from CLRS book:

Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, including the length $L$ of the longest chain. Describe a procedure that selects a key uniformly at random from among the keys in the hash table and returns it in expected time $O(L(1+\frac{1}{\alpha}))$.

I found the solution:

Choose one of the $m$ spots in the hash table at random. Let $n\_k$ denote the number of elements stored at $T\[k\]$. Next pick a number $x$ from $1$ to $L$ uniformly at random. If $x \< n\_j$ , then return the $x^{th}$ element on the list. Otherwise, repeat this process. Any element in the hash table will be selected with probability $\frac{1}{mL}$, so we return any key with equal probability. Let $X$ be the random variable which counts the number of times we must repeat this process before we stop and p be the probability that we return on a given attempt. Then $E\[X\] = p(1+\alpha)+(1−p)(1+E\[X\])$ since we’d expect to take $1+\alpha$ steps to reach an element on the list, and since we know how many elements are on each list, if the element doesn’t exist we’ll know right away. Then we have $E\[X\] = \alpha+ \frac{1}{p}$. The probability of picking a particular element is $\frac{n}{mL} = \frac{\alpha}{L}$, so we have $E\[X\] = \alpha + \frac{L}{\alpha} = L(\frac{\alpha}{L} + \frac{1}{\alpha}) = O(L(1 + \frac{1}{\alpha})).$

I have two questions:

1. Why Any element in the hash table will be selected with probability $\frac{1}{mL}$?
2. why $E\[X\] = p(1+\alpha)+(1−p)(1+E\[X\])$ contains $(1+E\[X\])$ and then $E\[X\] = \alpha+ \frac{1}{p}$?

# Answer
"Any element in the hash table will be selected with probability $\frac{1}{mL}$" is slightly confusing. It should be "Any pair of $(s, x)$, where $s$ is a slot in the hash table and $x$ is an index, $1\le x\le L$ will be selected with probability $\frac{1}{mL}$".

There are $m$ choices for $s$ and $L$ choices for $x$. Since these two choices are independent, there are $mL$ equally possible choices in total. That means, each pair will be selected with probability $\frac{1}{mL}$.

"$E\[X\] = p(1+\alpha)+(1−p)(1+E\[X\])$" is an equation with a single unknown variable, $E\[X\]$, with all other variables, $p$, $\alpha$ considered as known. Can you solve this linear equation of one unknown?
> 1 votes

---
Tags: algorithms, data-structures, hash
---


# Question
Title: Check Proof Using Pumping Lemma to Show Language Not Regular
Please check my proof where I use the pumping lemma to show that the language $B=\\{0^n1^n | n≥0\\}$ is not regular.

I'll state the pumping lemma here for clarity:

> **Pumping lemma** If $A$ is a regular language, then there is a number $p$ (the pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:
>
> 1. for each $i≥0, xy^i z∈A$,
> 2. $|y|\>0$,
> 3. and $|xy|≤p$.

Assume that $B$ is regular. I choose $s$ to be the string $0^p1^p$. Because $s$ is a member of $B$ and $s$ has length more than $p$, the pumping lemma guarantees that $s$ can be split into three pieces, $s = xyz$, where for any $i ≥ 0$ the string $xy^iz$ is in $B$. I present the following case to show that this is impossible.

1. Divide $s$ into $xyz$: let $x=ε,y=0^p,z=0^p$. In this case, the string $xyyz$ has more 0s than 1s and so is not a member of $B$, violating condition 1 of the pumping lemma. This case is a contradiction. Therefore $B$ is not regular.

# Answer
> 0 votes
To show there is a problem in your proof, I will try to make a similar proof, using another language. I hope you will find that the conclusion of my proof is incorrect and that you will see the similarities with yours. I will then try to explain in more details what the problem is.

> Consider the language $L = \\{a^mb^n\mid m,n\geqslant 0\\}$. I assume that $L$ is regular. Since it is regular, it verifies the pumping lemma. Let then $p$ be the constant in the pumping lemma, and $s = ab^p$. Since $s\in L$ and $s$ has length greater than $p$, then $s$ can be split into $s = xyz$ where for $i\geqslant 0$, $xy^iz\in L$.
>
> I choose the following split to prove a contradiction: divide $s$ into $x = \varepsilon$, $y = ab$ and $z = b^{p-1}$. In this case, $xyyz = abab^p$ is not a word of $L$ therefore $L$ is not regular.

Now obviously there is a problem with the conclusion because $L = a^\*b^\*$ is clearly a regular language.

To see the problem, let's do a bit of logic. The pumping lemma states:

> Being regular $\Rightarrow$ Verifying pumping lemma conclusion

Therefore, we conclude (with contraposition):

> Not verifying pumping lemma conclusion $\Rightarrow$ Not being regular

This is the property used to prove a language is not regular. Let's look a little bit closer to the pumping lemma conclusion:

> $\exists p$ such that, $\forall s$ of length $\geqslant p$, $\exists xyz$ verifying the three properties

The negation of that conclusion is therefore:

> $\forall p$, $\exists s$ of length $\geqslant p$, $\forall xyz$, the three properties are not verified.

That's why I insist that you need to consider ALL $xyz$ decompositions.

Now to go back to Sipser's proof, contrary to what you seem to say in an above comment, I do not claim that the proof is wrong, I claim that your interpretation of it is wrong. Indeed, Sipser says that for a fixed $p$, we consider $s = 0^p1^p$. He then consider a decomposition where $y$ consists only of $0$'s. But he does that because, implicitly, he considers that the decomposition verifies the properties 2. and 3., meaning that $|y| \> 0$ and $|xy| \< p$. Since $|xy| \< p$, that means $xy$ is included in the $0^p$ part of $s$.

By doing that, he is still considering all decomposition of $s$, but is implicitly discarding those that do not verify 2. or 3. (because those ones are already missing some properties needed for the conclusion of the pumping lemma).

# Answer
> -1 votes
Close but not quite right: pay close attention to the fact that we require that $s$ may be divided into $xyz$ in *some* way that satisfies the three conditions. You show one division that does not satisfy the conditions; what about the rest of the possibilities? (Hint: $s$ is well-chosen in the sense that it limits the form of $xyz$ divisions quite significantly)

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


# Question
Title: Prove finding a spanning tree with no more than 50 leaves is NP-hard
This is a homework question. Consider the problem of finding if an undirected graph $G$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard?

I think it is and I'm trying to prove it. So far I've tried to reduce Vertex Cover to this problem. My idea is that the internal nodes of a spanning tree of $G$ form a vertex cover of $G$, but I'm stuck at trying to relate the internal nodes to the number of leaves of the spanning tree.

# Answer
> 4 votes
Yes, this problem is indeed $\text{NP}$-hard.

Here is a hint of proof. Draw several trees with 2 leaves. What kind of graphs are they?

---
Tags: algorithms, complexity-theory, graphs, trees, spanning-trees
---


# Question
Title: When is a stuck state not final and when is a maximal sequence not complete in transition systems?
Reading the book Practical Foundations for Programming Language.

In section 5.1 Transition Systems, the author said that

> Whereas all final states are, by convention, stuck, there may be stuck states in a transition system that are not final.

> Thus every complete transition sequence is maximal, but maximal sequences are not necessarily complete.

It seems that in practice a stuck state is always final, but I wonder when is a stuck state not final? (Could you give me an example?)

Also, if we think that the stuck state is always final, it seems no different between maximal and complete?

> A transition sequence is maximal iff there is no $s$ such that $s\_n \mapsto s$, and it is complete iff it is maximal and, in addition, $s\_n$ final.

Also, do the states mentioned here refer to different states? If there is a fixed-point state in a transition system, the state is final or stuck?

Thanks.

# Answer
> 1 votes
In practice, a "final" state usually represents the state when the running of a program in a certain programming language is returning a value. (Nothing is considered as a value as well.) No more instruction can be carried out.

In contrast, a "stuck" state can also represents the state when the running of a program got stuck (in the usual sense of English) when there is no instruction can be done further. For example, when a program is assigning a string to a variable that can only hold a number. There is nothing further that can be done by the program, since "no transition is possible", assuming nothing like some exception mechanism to deal with that kind of "illegal" situations is available.

One central purpose of designing a programming Language and writing a compiler/interpreter is to ensure the running of a program will never got into a "stuck" state except when it returns.

"If there is a fixed-point state in a transition system, the state is final or stuck?" If defined as final, that state is final (and stuck). Otherwise, it is neither final nor stuck.

---
Tags: programming-languages, semantics, transition-systems
---


# Question
Title: How do we decide whether or not to accept $\epsilon$ in dfa?
Can I exclude $\epsilon$? Will that make a difference. This is really confusing me. It seems everything could contain $\epsilon$. Is there some way of thinking to realize this contains $\epsilon$ or not. I was looking at a DFA for $a$ followed by $b$. And it also contained $\epsilon$ which seems confusing to me. That means $\epsilon$ is there everywhere (most cases). Can I ignore it?

# Answer
A DFA is a tuple $(Q,\Sigma,\delta,q\_0,F)$, where $Q$ is a finite set, $\Sigma$ is a non-empty finite set, $\delta$ is a function from $Q \times \Sigma$ to $Q$, $q\_0$ is an element of $Q$, and $F$ is a subset of $Q$. We extend $\delta$ to a function $\hat\delta$ from $Q \times \Sigma^\*$ to $Q$ as follows: $\hat\delta(q,\epsilon) = q$ and $\hat\delta(q,x\sigma) = \delta(\hat\delta(q,x),\sigma)$. Finally, the language accepted by the DFA is $$ L=\\{ w \in \Sigma^\* : \hat\delta(q\_0,w) \in F. \\} $$ In particular, $\epsilon \in L$ iff $\hat\delta(q\_0,\epsilon) \in F$ iff $q\_0 \in F$.

---

You mention a DFA "containing $\epsilon$". My guess is that you saw an automaton with $\epsilon$ labelling one of the edges. This is a pictorial representation of an $\epsilon$-NFA, a generalization of DFAs which allows such transitions, and whose semantics we skip in this answer.

---

Examples:

A DFA where $q\_0\in F$, whose language is the words not containing "ab", which includes $\epsilon$:

A DFA where $q\_0\not\in F$, whose language is the words containing "ab", which does not include $\epsilon$:

An $\epsilon$-NFA, whose language is the words containing "a...b" ("ab" as a subsequence), which does not include $\epsilon$:
> 2 votes

---
Tags: finite-automata
---


# Question
Title: Does the Minimum Spanning Tree include the TWO lowest cost edges?
Wikipedia's Minimum Spanning Tree reads:

> **Minimum-cost edge**
>
> If the minimum cost edge e of a graph is unique, then this edge is included in any MST.
>
> Proof: if e was not included in the MST, removing any of the (larger cost) edges in the cycle formed after adding e to the MST, would yield a spanning tree of smaller weight.

So far so good, but what about the **two** minimum cost edges? Since I cannot think of any counter-example for which it doesn't hold, I have written the following Python script. It generates a random graph, weights it with consecutive integers (1, 2, 3, ...), calculates its (unique) MST, and repeats until the second lightest weight of the MST is not 2.

```
n = 8
p = 0.3
while True:
    G = nx.erdos_renyi_graph(n, p)
    for (w, (x, y)) in enumerate(G.edges(), 1):
        G[x][y]["weight"] = w
    edges = list(nx.minimum_spanning_edges(G, data=False))
    weights = sorted(G[x][y]["weight"] for (x, y) in edges)
    # print(weights)
    if weights[1] != 2 and len(weights) > 1:
        print(weights)
        break

```

You can convince yourself that this script works as intended by uncommenting the first `print`, or by replacing `weights[1] != 2` by `weights[2] != 3` (which makes it stop when the MST doesn't includes the edge of weight 3).

However, it doesn't terminate, which seems to indicate that the Wikipedia's proposition could be extended to the **two** lowest cost edges.

There is a possibility that such graphs are rare, that the parameters of my random generator are biased against them, or my consecutive weights are wrong somehow.

What do you think? Can you prove this extension, or produce a counter-example?

# Answer
If the MST does not contain at least one among the two minimum-cost edge then add it to the MST (you get a graph with a single loop and the loop has length 3 or larger) remove from the loop the edge having larger cost (it costs more than the one you just introduced) and you are left with a Tree and this tree is Spanning and it costs less than the original one.

Proved by contradiction!
> 3 votes

# Answer
For simple graphs\*, it is true for the following reason:

1. Kruskal’s algorithm is correct
2. Kruskal’s algorithm works as follows:
    * sort the edges by increasing weight
    * repeat: pop the cheapest edge, if it does not create cycles, include it in the MST
3. Two edges cannot construct a cycle in a simple graph

By the correctness of Kruskal’s algorithm, the two uniquely smallest weight edges are always part of an MST. (It also follows that the three uniquely smallest weight edges are always part of an MST unless those three form a triangle.)

* Simple graphs have no parallel edges
> 24 votes

# Answer
Assuming that the graph has at least $3$ vertices, is connected, and edges have distinct weights you can see that the two edges with the lowest weights must belong to the (unique) MST of the graph by noticing that they cannot induce any cycle and hence they must be selected by Kruskal's algorithm.

Alternatively, you can notice that each cycle must contain at least $3$ edges and hence none of the two edges with the smallest weights can be the edge of maximum weight in the cycle.
> 4 votes

---
Tags: graphs, weighted-graphs, minimum-spanning-tree
---


# Question
Title: how do you deal with complex algorithms?
I'm in the first year of computer engineering and I feel completely lost when it comes to solving hard programming exercises. I think it's due to a bad modus operandi. And that is why I'm asking this question. My question is that: what do you do when you have to do a difficult task? In other words, what do you do when you have to deal with algorithms that are not so obvious. How do you deal with those tasks?

# Answer
> 2 votes
Here are some tips for reading algorithms, but also for coming up with new ones. Almost all algorithms are composed of multiple *conceptual steps*. What counts as a conceptual step depends on context and your personal background, but usually it is more than a mere increment like $i \leftarrow i + 1$.

* **make conceptual steps explicitly:** sometimes the way algorithms are written down do not show the steps explicitly or show them already intermingled (e.g., for efficiency of execution). Try breaking down (or reformulating) the algorithm in a way that shows all steps explicitly in a granularity that suits you.
* **understand which granularity of steps suits you:** e.g., avoid unfolding loops, avoid unfolding recursion. Almost always, doing so is counterproductive to understanding an algorithm. Instead, formulate invariants for loops or use induction hypotheses for your conceptual understanding (see next point).
* **state invariants, pre-, and post-conditions for every step** to improve your understanding of what every step expects, computes, and returns.
* **execute the algorithm with a toy example as input** that is neither too trivial nor too complicated. Follow the input and output data between each step.

**Example 1:** Wikipedia shows a recursive algorithm to solve Tower of Hanoi. It looks deceptively simple, being only five lines of Python code.

```
def move(n, source, target, auxiliary):
    if n > 0:
        move(n - 1, source, auxiliary, target)
        target.append(source.pop())
        move(n - 1, auxiliary, target, source)

```

As a freshperson back then, I had a hard time understaind this algorithm in my first semester of CS. I had always tried unfolding the recursion to understand its inner workings -- but that's massively counterproductive. Instead, key to understanding was:

1. formulate pre-condition and post-condition for `move`
2. use the technique of induction to understand the code's correctness/functionality:
    * for $n = 0$, we understand that `move` is correct
    * for $n \> 0$, in lines 3 and 6 we take for granted that the calls to `move(n - 1, ...)` work correctly for valid input. Thus, we only have to verify whether inputs supplied in these function calls is valid in the sense of pre-conditions formulated in Step 1.

# Answer
> 1 votes
With practice, many things that are hard for you today won’t be hard in the future.

To solve problems that stay hard, number one advice: Talk to someone else. Explain the problem and why it is difficult. That step alone often solves the problem! Or you get advice, or at least ideas how to tackle the problem. And sometimes, the problem just *is* hard.

And in many cases, the advice will tell you that you don’t actually *need* to solve the hard problem. Many people start with a problem x, figure out that they can solve x by solving y, and then y turns out to be hard - and ignore other ways to solve x.

---
Tags: algorithms
---


# Question
Title: Proof that the complement of a finite language is always an infinite language
Let's say that we have a language $L$ that is finite.
How can I prove that the complement of $L$, i.e., $\bar{L}$, is always an infinite language?

Obs.: infinite language in this case means that is possible to construct an infinite set of words that are acceptable by $\bar{L}$.

# Answer
> 4 votes
The set $\Sigma^\*$ is an infinite set (you can build a bijection between the naturals and the words in $\Sigma^\*$ if you wish to prove this, or you can observe that, for every $k \in \mathbb{N}$, $\Sigma^\*$ contains at least one word of length $k$).

Let $L$ be a finite language and suppose towards a contradiction that $\overline{L} = \Sigma^\* \setminus L$ is finite. Then $\Sigma^\* = L \cup \overline{L}$ must also be finite (since it's a finite union of finite sets). This provides the sought contradiction.

# Answer
> 2 votes
Here is a formal proof for the statement (**warning**, this really *is* a formal proof, and hence is not very intuitive):

Let $\Sigma$ be a non-empty alphabet (either finite or infinite), and let $L\subset \Sigma^\*$, with $|L|\in \mathbb{N}$ ($L$ is finite).

Let $\alpha \in \Sigma$. By definition of the klenee-star operator, we can construct a function $g:\mathbb{N}\rightarrow \Sigma^\*$ by $g(k)=\alpha^k$ ($\alpha$ repeated $k$ times). This function is one-to-one, since $|g(k)|=|\alpha^k|=k$ (where $|w|$ denotes the *length* of the string $w$), and thus for any $k\_1, k\_2$ with $g(k\_1)=g(k\_2)$ we must have $k\_1=|g(k\_1)|=|g(k\_2)|=k\_2$.

Thus, we proved that $\aleph\_0=|\mathbb{N}|\le |\Sigma^\*|$.

Now, let us begin showing that $\aleph\_0\le |\Sigma^\* \setminus L|$. Denote by $n\_{max}:=\max\\{|w|\mid w\in L\\}+1$, and define $f:\mathbb{N}\rightarrow (\Sigma^\*\setminus L)$ by $f(k)=\alpha^{n\_{max}+k}$.

First, we have to show that this really is a function (by showing that $f(k)\in \Sigma^\*\setminus L$ for all $k\in\mathbb{N}$). Indeed, if we assume towards contradiction that $f(k)\in L$ for some $k$ \- we get that $|f(k)|\<n\_{max}$ by the definition of $n\_{max}$. But $|f(k)|=|\alpha^{n\_{max}+k}|=n\_{max}+k \ge n\_{max}$ which is clearly a contradiction (we got that $n\_{max}\<n\_{max}$).

Now we have to show that $f$ is one-to-one. By a similar argument to what we did before to prove that $\Sigma^\*$ is infinite, we can conclude that $f$ is one-to-one, and hence $\aleph\_0=|\mathbb{N}|\le |\Sigma^\*\setminus L|=|\bar L|$ which is exactly what we wanted to show.

# Answer
> -1 votes
Lets denote $n:=|L|\in \mathbb{N}$.

For any nonempty $\Sigma$, it is clear that $\Sigma^\*$ is infinite.

By definition, $\bar L = \Sigma^\*\setminus L$. Therefore, $|\bar L| = |\Sigma^\*\setminus L| = |\Sigma^\*|-|L| = \infty - n=\infty$.

It is not a formal proof (neither a valid one), but it should suffice for you as **intuition** to understand why $\bar L$ is infinite.

---
Tags: formal-languages
---


title: Hashing using chaining

text:
# Question
Title: Hashing using chaining
In resolving collisions while hashing by chaining , if we store keys in the list in sorted manner, will we obtain any substantial performance in successful searches , insertion, deletion? What would be the time - complexities of these operations if we maintain sorted lists in chaining?(assume keys are integers)

# Answer
There is no asymptotic speedup. Searching a sorted list requires examining $n/2$ items on average and $n$ items in the worst case (where $n$ is the length of the list), searching an unsorted list requires examining $n/2$ items on average if the item is in the list and $n$ items in the worst case, so the worst-case asymptotic running time is $O(n)$ either way.

Inserting into a sorted list takes $O(n)$ time, while inserting into an unsorted list can be done in $O(1)$ time if you use an appropriate data structure (e.g., a linked list).
> 0 votes

---
Tags: time-complexity, data-structures, hashing
---


title: Subset sum with only two item types

text:
# Question
Title: Subset sum with only two item types
Suppose we have $r$ copies of the integer $a$ and $t$ copies of the integer $b$, and a capacity $C$. We would like to find the maximum sum of the given integers, that is at most $C$.

This is a special case of the subset sum problem. Since there are at most $(r+1)(t+1)$ possible sums, one can just check all of them and find the maximum sum that is at most $C$. But this takes time $O(r t)$, while the size of the input - if it is given in binary - is $\log{(r t a b)}$.

Is there an algorithm that solves the problem in time polynomial in the size of the binary representation of the input?

# Answer
As kcsquared notes, this is an instance of integer linear programming (ILP) in two dimensions. Lenstra showed that ILP can be solved in polynomial time when the number of dimensions is constant; the special case of two dimensions was apparently proven earlier by Scarf. This proves that your program can be solved in polynomial time, as you were hoping.
> 2 votes

---
Tags: polynomial-time, partitions, subset-sum
---


# Question
Title: Can Deterministic Context free Grammars be ambiguous?
I know that DCFL are unambiguous languages and DCFL languages have one-to-one correspondence with LR grammars.

But I wanted to know if there can be an instance that deterministic context free grammar is ambiguous.

# Answer
No, there is no deterministic context-free grammar that is ambiguous since any deterministic context free grammar (DCFG) must be unambiguous.

Here is definition 2.47 of the book *introduction to the theory of computation*, third edition, by Michael Sipser.

> A deterministic context-free grammar is a context-free grammar such that every valid string has a forced handle.

Furthermore, here is definition 2.62.

> An LR($k$) grammar is a context-free grammar such that the handle of every valid string is forced by lookahead $k$.

A DCFG is the same as an LR(0) grammar. All LR($k$) grammars are unambiguous, by definition.
> 2 votes

# Answer
I was also struggling with this problem. I think I might have found an ambiguous DCFG G = ({S,T,A},{a,u,v},R,S), where R is defined as

S -\> ATa | aTa

T -\> uv

A -\> a

G is ambiguous because there are two different leftmost derivations for string auva.

S =\> ATa =\> aTa =\> auva

S =\> aTa =\> auva

However, G is also a DCFG because there is only one leftmost reduction

auva \>-\> Auva \>-\> ATa \>-\> S

which means that there are a total of three valid strings: auva, Auva, ATa. And we can show that each of them has a forced handle by enumerating all possibilities.
> -1 votes

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


# Question
Title: Find all combinations of adjacent records matching a graph template
I have a graph theory or combinatorics problem that probably has a solution, but I haven't been able to find it. The problem can be simple: in the second figure below, choose one yellow block from each oval such that the blue edges between the blocks look like the edges in the first figure below. Find all possible such combinations.

The background to this problem is we want to allow a user to define an arbitrary undirected graph to serve as a query template, for example:

For every node, the user can define criteria that must be satisfied, and we then query multiple different APIs to get matching records, with each record being associated with one edge of the query template, as illustrated in the figure below:

An example of a record would be `AC`, with `A` matching the criteria specified for `n0` and with `C` matching the criteria for `n1`. The line between `A` and `C` indicates the two of them together form a record.

We want to find every combination (unordered set of records) where every record within each combination meets these two conditions:

1. one record per query template edge, e.g., `AC` for `e0`, `CF` for `e1`, etc
2. records that share a query template node (like `n1`) must also share a corresponding record node (like `C`)

For the figure above, we should get the combinations below:

```
{ AC, CF, FK, KI, IC }
{ AC, CF, FK, KI, ID }
{ AC, CH, HK, KI, IC }
{ AC, CH, HK, KI, ID }
{ BC, CF, FK, KI, IC }
{ BC, CF, FK, KI, ID }
{ BC, CH, HK, KI, IC }
{ BC, CH, HK, KI, ID }
{ BD, DH, HK, KI, IC }
{ BD, DH, HK, KI, ID }

```

How would I properly describe this problem in graph theory or combinatorics terminology? Is there an optimal solution to finding the combinations of records, considering that we're trying to avoid limitations on the query template and the number of records per query template edge could be in the hundreds of thousands?

# Answer
If I understand your problem accurately, it is NP-hard. As such, there is no efficient solution.

I will show a reduction from 3SAT. In particular, suppose we have a 3SAT formula $\varphi$ with variables $x\_1,\dots,x\_m$ and $m$ clauses. For each $i$, introduce an oval with two nodes inside it, one for $x\_i$ and one for $\overline{x\_i}$. For each clause, introduce two ovals, with the following shape:

Ddraw a blue line between $A$ and the node for the first literal in the clause; a blue line between $B$ and the node for the second literal in the clause; and a blue line between the $C$ and the node for the third literal in the clause. That is the record graph.

Finally, draw a query template that requires there to be a line between each of the two ovals of each gadget; and a line between the left oval of each gadget and the corresponding three ovals for the three variables occurring in the clause.

Now, if I understand your matching rules correctly, there is a satisfying assignment to $\varphi$ iff the query template has a match in the record graph.
> 1 votes

---
Tags: graphs, combinatorics
---


title: DFA minimazation (dead state)

text:
# Question
Title: DFA minimazation (dead state)
I was trying to minimize given DFA:

|  | a | b |
| --- | --- | --- |
| -\> 1 | 4 | 2 |
| F 2 | 1 | 1 |
| 3 | 1 | 4 |
| F 4 | 1 | 1 |

I've watched few videos about solving this problem and decided to use the equivalance method. While doing it I've come to the solution below:

* 0 Equivalance: {1,3} {2,4}
* 1 Equivalance: {1} {3} {2,4}

|  | a | b |
| --- | --- | --- |
| -\> 1 | 2,4 | 2,4 |
| F 2,4 | 1 | 1 |
| 3 | 1 | 2,4 |

which translates into the following graph:

State 3 looks dead to me. Should I even draw it if the solution is correct? What would be the point of this state?

Kind regards,

# Answer
It's inaccessable; you don't need it.
> 2 votes

---
Tags: finite-automata
---