# Question
Title: What is the intuition on why the longest path problem does not have optimal substructure?
I was learning about longest paths and came across the fact that longest paths in general graphs is not solvable by dynamic programming because the problem lacked optimal substructure (which I think the statement needs to be corrected to longest **simple** paths on general graphs is **not** solvable by dynamic programming).

If we assume they have to be **simple** (for some reason this is required which I don't appreciate yet) and longest, then its easy to create a counter example. Consider the square graph with 4 nodes A→B→C→D→A.

A longest path from A to D is clearly A→B→C-D. But the longest path from B to C is not part of the longest path to from A to D because the longest path from B to C is B→A→D→C which is clearly not the same as the path B→C (which in this case is in fact a shortest path!).

This seems to work only because we required the paths to be simple. Is it necessary to assume that the paths **must** be simple for us to prove that optimal substructure is **not** present?

I think that the counter example should be good evidence/proof (which I don't deny), I just don't find the counter example very enlightening at all. I see why it proves the point that it doesn't allow optimal substructure but it fails to provide me real understanding or intuition why it should be obvious that there should be **no** longest path optimal substructure. Like for example, why doesn't a cut and paste argument work? If the subpath isn't longest, then just stick in a longer path! It sounds very tempting, I mean, if we put in place something longer then of course it should get longer...though, this is for some reason **wrong**. Does the example actually in fact prove that **DP** can **never** solve longest (simple?) paths efficiently? I don't require for a general proof that its **not** in P (since thats might be asking for a P vs NP solution). I am just after a proof that its **not solvable by DP** (or at least very strong evidence that DP can never solve this longest paths problem or that the problem does **not** have optimal substructure).

I have definitively seen in wikipedia that the problem should be NP-Hard, which means that there is probably no fast algorithm. Not sure if that is the only type of evidence/intuition that exists to provide that optimal substructure should be obviously lacking (or if its not lacking, that it can't be used to make the problem faster). Is that the only way to show that it should **not** be solvable by a fast dynamic program?

Is the reason we require **simple** just because if we don't place that requirement the problem becomes trivial/uninteresting? In other words, if there is any cycle then one has solved the longest path problem to all nodes reachable from that cycle (by finding any path to that cycle). For the nodes that don't have any cycle reachable, we have a acyclic graph, which is solvable by DP (if the weights are positive?). In addition if there are cycles, we have automatically made things have optimal substructure (I think) because any longest path just is made up of longest path which covers two cases, 1 the paths through the cycle or 2 the paths through the DAG, which both contain optimal substructure. So the problem has become trivial without the requirement of simple paths? Or am I missing something or are there better explanations to why simple paths are required? Doesn't the algorithm in this paragraph show that **general** longest paths **are** solvable by DP?

I am also not 100% sure what requirements are needed to guarantee that DP can't be used. Is it necessary to negative edge weights, positive, un-weighted, directed, undirected...what are the requirements?

# Answer
The longest path problem does have optimal substructure, and this can be used to improve the trivial $O(n!)$ algorithm to an $\tilde{O}(2^n)$ algorithm. First we have to generalize the problem:

> Generalized longest path: Given a graph $G=(V,E)$, two vertices $s,t \in V$, and a set of vertices $A \subseteq V \setminus \\{s,t\\}$, find the longest path in $G$ from $s$ to $t$ avoiding the vertices in $A$.

Denoting the solution to this problem by $\ell(s,t,A)$ (the graph is understood), we have the recurrence $$ \begin{align\*} &\ell(s,t,A) = 1 + \max\_{\substack{x \notin A \cup \\{s\\}: \\ (s,x) \in E}} \ell(x,t,A \cup \\{s\\}) \qquad (s \neq t), \\ &\ell(t,t,A) = 0. \end{align\*} $$ If the maximum in the first case is over the empty set (that is, if there is no path from $s$ to $t$ avoiding $A$), we assign $\ell(s,t,A) = -\infty$.

You can solve this recurrence using dynamic programming in time $\tilde{O}(2^n)$.

While there is optimal substructure here, there are too many parameters to keep track of, and this is what makes the problem intractable.
> 14 votes

# Answer
**First of all,** the longest simple path is NP-hard and there is no doubt about that (as the Hamiltonian path reduces to it).

**Secondly,** if you consider the non-simple paths, then the problem does not make much sense, as the non-simple path goes over one edge/vertex more than once, thus it has a loop. As a result of having a loop in the path, the longest non-simple path is **infinite**.
> 3 votes

# Answer
I've been thinking about the same in last 1 hour and came to the following conclusions:

i) Longest path in a graph without cycles has optimal substructure and so does the shortest path.

ii) Longest path without positive cycles has optimal substructure and so does a shortest path without negative cycles.

iii) Longest path with positive cycles and shortest path with negative cycles don't exist as we can loop around the cycle infinitely. So we look at simple paths.

iv) Longest simple path with positive cycles and shortest simple path with negative cycles is NP Hard.

DP solves (i) in O(V+E). Bellman-Ford solves (ii) in O(VE) and Djisktra helps in certain sub-cases of (ii).

Literature is confusing on this topic when longest path is just shortest path with weights negated and vice-versa. I see no reason to give blanket statements like longest path has no optimal sub structure but shortest path has etc.
> 2 votes

---
Tags: algorithms, graphs, optimization, dynamic-programming
---


# Question
Title: Problem with the mapping reduction from $A_{TM}$ to $HALT_{TM}$
Sipser provided the following proof to prove the mapping reduction from $A\_{TM}$ to $HALT\_{TM}$, it in fact tried to build a mapping function:

My problem is the way this proof works. The function must take $\<M,w\> \in A\_{TM}$ and produce $\<M',w'\>$ if and only if $\<M',w'\>\in HALT\_{TM}$ We know by the hypothesis $\<M,w\>\in A\_{TM}$. The machine $M'$ runs $M$ on an input $x$ not the input $w$. Now what if $\<M,x\>\notin A\_{TM}$ and $\<M,w\>\in A\_{TM}$? then $M'$ will output the `loop` while since $\<M,w\>\in A\_{TM}$ the output must be `accept`. As a result the output $\<M',w\>$ which is supposed to be in $HALT\_{TM}$ is not truly corresponded to the input. I would be appreciated if you explain about my problem.

Thanks

# Answer
Your conception of a reduction is incorrect. The reduction takes an *instance* $\langle M, w \rangle$ of $A\_{TM}$ and returns an *instance* $F(\langle M,w \rangle)$ of $HALT\_{TM}$ such that $\langle M,w \rangle \in A\_{TM}$ iff $F(\langle M,w \rangle) \in HALT\_{TM}$.

Second, $M'$ is a Turing machine that accepts a single input $x$. The pair $\langle M',w \rangle$ belongs to $HALT\_{TM}$ if $M'$ halts when running on the input $w$. Hence when analyzing whether $\langle M',w \rangle \in HALT\_{TM}$ or not, the relevant value of $x$ is $w$.

Here is another way to think of the proof. Given a Turing machine $M$, we construct another Turing machine $M'$ such that $M$ accepts $w$ iff $M'$ halts on $w$.

When describing $M'$, we use $x$ to denote its input. There is no definite value of $x$ like your post seems to assume — it stands for the input to $M'$. For a similar example, consider the function $f(x) = x^2$. What is the value of $x$? It has no definite value, being just a place holder. If we plug in $w$ for $x$ then we get $f(w) = w^2$.
> 2 votes

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


title: Was my Huffman coding solution wrong?

text:
# Question
Title: Was my Huffman coding solution wrong?
I finished my exam a moment ago and one of the question was to calculate Huffman coding for given probabilities:

```
A: 0.15
B: 0.2
C: 0.55
D: 0.1

```

I encoded them as follows:

```
A: 110
B: 10
C: 0
D: 111

```

But my lecturer told me that this results seems odd and gave me just a fraction of points for my solution. I argued that all my encodings have unique prefixes. I also said that all my encodings has same length as his (he compared my solution with his reference solution), thus they have same entropy.

Do I really don't understand Huffman codding? I found the theory behind this algorithm amazing so I would like to know.

# Answer
> 3 votes
Huffman's algorithm is actually an "algorithm scheme", that is, a specification for an entire class of algorithms. Roughly speaking, Huffman's algorithm is any instantiation of the following scheme:

> While there is more than one symbol, choose (in an unspecified way) two leaves of minimum total probability, and merge then (in an unspecified order).

Any particular instantiation will include a tie-breaking rule for choosing the two leaves, and will order them in some specific way.

In your case, there is only one choice for the two leaves, but there are several choices for the order (two at each of the three iterations of the algorithm). Hence your distribution supports 8 different "Huffman codes". It might be that the one you chose is not the canonical one which is produced by the specific implementation you were taught in class. The 8 Huffman codes for your distribution are: $$ \begin{array}{c|l|l|l|l|l|l|l|l} A & 110 & 111 & 100 & 101 & 010 & 011 & 000 & 001 \\\hline B & 10 & 10 & 11 & 11 & 00 & 00 & 01 & 01\\\hline C & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\\hline D & 111 & 110 & 101 & 100 & 011 & 010 & 001 & 000\\ \end{array} $$

An important fact to be aware of is that not while Huffman's algorithm is guaranteed to produce a minimum redundancy code, not all minimum redundancy codes can be produced by Huffman's algorithm. See Gallager's classic paper Variations on a Theme by Huffman.

---
Tags: data-compression, huffman-coding
---


# Question
Title: Narrowing the field of a combitorial game
I'm doing a challenge and it has posed a problem I am unfamiliar with. It goes like this, You start with two numbers, 1 and 1. You can combine the numbers in either direction, in this case makes 2,1 and 1,2 or in the case of 3,2 it would produce 5,2 or 3,5. Always starting from 1,1 my challenge is to try to find a pair of numbers in as few "moves" as possible.

My first pass was to build a greedy-first SSS\* like algorithm. Works well for a small space but in the end takes too long on large inputs. So I think I have to massively narrow the search. Or I'm sure someone has seen this before and has come up with a clever workaround.

Any help is appreciated

# Answer
You have discovered the Calkin–Wilf tree, which is the game tree of your game. There is a unique way to reach any pair of coprime positive integers. Given a pair of coprime positive integers, repeatedly subtract the smaller one from the larger one, and you will eventually reach $(1,1)$. Reversing your moves, you obtain the unique way to generate the given (ordered) pair.
> 1 votes

---
Tags: algorithms
---


# Question
Title: What exactly is the semantic difference between set and type?
EDIT: I've now asked a similar question about the difference between categories and sets.

Every time I read about type theory (which admittedly is rather informal), I can't really understand how it differs from set theory, **concretely**.

I understand that there is a conceptual difference between saying "x belongs to a set X" and "x is of type X", because intuitively, a set is just a collection of objects, while a type has certain "properties". Nevertheless, sets are often defined according to properties as well, and if they are, then I am having trouble understanding how this distinction matters in any way.

So in the most **concrete** way possible, what exactly does it **imply** **about $x$** to say that it is of type $T$, compared to saying that it is an element in the set $S$?

(You may pick any type and set that makes the comparison most clarifying).

# Answer
To understand the difference between sets and types, ones has to go back to *pre*-mathematical ideas of "collection" and "construction", and see how sets and types *mathematize* these.

There is a spectrum of possibilities on what mathematics is about. Two of these are:

1. We think of mathematics as an activity in which mathematical objects are constructed according to some rules (think of geometry as the activity of constructing points, lines and circles with a ruler and a compass). Thus mathematical objects are organized according to how they are *constructed*, and there are different **types** of construction. A mathematical object is always constructed in *some* unique way, which determines its unique type.
2. We think of mathematics as a vast universe full of pre-existing mathematical objects (think of the geometric plane as given). We discover, analyze and think about these objects (we observe that there are points, lines and circles in the plane). We *collect* them into **set**. Usually we collect elements that have something in common (for instance, all lines passing through a given point), but in principle a set may hold together an arbitrary selection of objects. A set is specified by its elements, and only by its elements. A mathematical object may belong to many sets.

We are not saying that the above possibilities are the only two, or that any one of them completely describes what mathematics is. Nevertheless, each view can serve as a useful starting point for a general mathematical theory that usefully describes a wide range of mathematical activities.

It is natural to take a type $T$ and imagine the collection of all things that we can construct using the rules of $T$. This is the *extension* of $T$, and it is *not* $T$ itself. For instance, here are two types that have different rules of construction, but they have the same extension:

1. The type of pairs $(n, p)$ where $n$ is constructed as a natural number, and $p$ is constructed as a proof demonstrating that $n$ is an even prime number larger than $3$.
2. The type of pairs $(m, q)$ where $m$ is constructed as a natural number, and $q$ is constructed as a proof demonstrating that $m$ is an odd prime smaller than $2$.

Yes, these are silly trivial examples, but the point stands: both types have *nothing* in their extension, but they have *different* rules of construction. In contrast, the sets $$\\{ n \in \mathbb{N} \mid \text{$n$ is an even prime larger than $3$} \\}$$ and $$\\{ m \in \mathbb{N} \mid \text{$m$ is an odd prime smaller than $2$} \\}$$ *are* equal because they have the same elements.

Note that type theory is not about syntax. It is a mathematical theory of constructions, just like set theory is a mathematical theory of collections. It just so happens that the usual presentations of type theory emphasize syntax, and consequently people end up thinking type theory *is* syntax. This is not the case. To confuse a mathematical object (construction) with a syntactic expression that represents it (a term former) is a basic category mistake that has puzzled logicians for a long time, but not anymore.
> 59 votes

# Answer
In practice, claiming that $x$ being of type $T$ *usually* is used to describe *syntax*, while claiming that $x$ is in set $S$ is *usually* used to indicate a *semantic* property. I will give some examples to clarify this difference in *usage* of types and sets. For the difference in what types and sets actually *are*, I refer to Andrej Bauer's answer.

## An example

To clarify this distinction, I will use the example given in Herman Geuvers' lecture notes. First, we look at an example of inhabiting a type:

$$3+(7\*8)^5:\mathrm{Nat},$$ and an example of being member of a set: $$3\in \\{n\in\mathbb{N}\mid \forall x,y,z\in\mathbb{N}^+ (x^n+y^n\neq z^n)\\}$$

The main difference here is that to test whether the first expression is a natural number, we don't have to compute some semantic meaning, we merely have to 'read off' the fact that all literals are of type Nat and that all operators are closed on the type Nat.

However, for the second example of the set, we have to determine the semantic meaning of the $3$ in the context of the set. For this particular set, this is quite hard: the membership of $3$ for this set is equivalent to proving Fermat's last theorem! Do note that, as stated in the notes, the distinction between syntax and semantics cannot always be drawn that clearly. (and you might even argue that even *this example* is unclear, as Programmer2134 mentions in the comments)

## Algorithms vs Proofs

To summarize, types are often used for 'simple' claims on the syntax of some expression, such that membership of a type can be checked by an *algorithm*, while to test membership of a set, we would in usually require a *proof*.

To see why this distinction is useful, consider a compiler of a typed programming language. If this compiler has to create a formal proof to 'check types', the compiler is asked to do an almost impossible task (automated theorem proving is, in general, hard). If on the other hand the compiler can simply run an (efficient) algorithm to check the types, then it can realistically perform the task.

## A motivation for a strict(er) interpretation

There are multiple interpretations of the semantic meaning of sets and types. While under the distinction made here extensional types and types with undecidable type-checking (such as those used in NuPRL, as mentioned in the comments) would not be 'types', others are of course free to call them as such (just as free as they are as to call them something else, as long as their definitions fit).

However, we (Herman Geuvers and I), prefer to not throw this interpretation out of the window, for which I (not Herman, although he might agree) have the following motivation:

First of all, the intention of this interpretation isn't *that far* from that of Andrej Bauer. The intention of a syntax is usually to describe how to construct something and having an algorithm to actually construct it is generally useful. Furthermore, the features of a set are usually only needed when we want a semantic description, for which undecidability is allowed.

So, the advantage of our more stricter description is to keep the separation *simpler*, to get a distinction more directly related to common practical usage. This works well, as long as you don't need or want to loosen your usage, as you would for, e.g. NuPRL.
> 16 votes

# Answer
To start, sets and types aren't even in the same arena. Sets are the objects of a first-order theory, such as ZFC set theory. While types are like overgrown sorts. To put it a different way, a set theory is a first-order theory *within* first-order logic. A type theory is an extension of logic itself. Martin-Löf Type Theory, for example, is not presented as a first-order theory within first-order logic. It's not that common to talk about sets and types at the same time.

As Discrete lizard states, types (and sorts) serve a syntactic function. A sort/type behaves as a *syntactic category*. It lets us know what expressions are well-formed. For a simple example using sorts, let's say we described the theory of vector spaces over an arbitrary field as a 2-sorted theory. We have a sort for scalars, $\mathsf S$, and a sort for vectors, $\mathsf V$. Among many other things, we'd have an operation for scaling: $\mathsf{scale}:\mathsf S\times \mathsf V\to \mathsf V$. This lets us know that $\mathsf{scale}(\mathsf{scale}(s,v),v)$ is simply not a well-formed term. In a type theoretic context, an expression like $f(x)$ requires $f$ to have a type $X\to Y$ for some types $X$ and $Y$. If $f$ does not have the type of a function, then $f(x)$ is simply not a well-formed expression. Whether an expression is of some sort or has some type is a meta-logical statement. It makes no sense to write something like: $(x:X)\implies y=3$. First, $x : X$ is simply not a formula, and second, it doesn't even conceptually make sense as sorts/types are what let us know which formulas are well-formed. We only consider the truth value of well-formed formulas, so by the time we're considering whether some formula holds, we better already know that it is well-formed!

In set theory, and particularly ZFC, the only non-logical symbol at all is the relation symbol for set membership, $\in$. So $x\in y$ is a well-formed formula with a truth value. There are no terms other than variables. All the usual notation of set theory is a definitional extension to this. For example, a formula like $f(x)=y$ is often taken to be shorthand for $(x,y)\in f$ which itself may be taken as shorthand for $\exists p.p\in f\land p=(x,y)$ which is shorthand for $$\exists p.p\in f\land(\forall z.z\in p\iff \[z = x\lor(\forall w.w\in z\Leftrightarrow w = y)\])$$ At any rate, *any set can take the place of $f$ and everything is a set!* As I pointed out in a different question recently, $\pi(7)=3$ where $\pi$ is the real number is a completely legitimate and meaningful (and potentially even true) set theoretic expression. Basically, anything you write that parses in set theory can be given some meaning. It may be a completely spurious meaning, but it has one. Sets are also "first-class" objects in set theory. (They better be as they are the *only* objects usually.) A function like $$f(x)=\begin{cases}\mathbb N, &\text{if }x=1\\7,&\text{if }x=\mathbb Q\\x\cap \mathbb R^\mathbb R,&\text{if }x=(\mathbb Z,\mathbb N)\end{cases}$$ is a completely legitimate function in set theory. There is nothing even remotely analogous to this in type theory. The closest would be to use codes for a Tarskian universe. Sets are the objects of set theory; types are not the object of type theory.

A type is not a collection of things (neither is a set for that matter...), and it is not defined by a property. A type is a syntactic category that lets you know what operations are applicable to terms of that type and which expressions are well-formed. From a propositions-as-types perspective, what types are classifying are the valid proofs of the proposition to which the type corresponds. That is, the well-formed (i.e. well-typed) terms of a given type correspond to the valid proofs (which are also syntactic objects) of the corresponding proposition. Nothing like this is happening in set theory.

Set theory and type theory are really not anything alike.
> 10 votes

# Answer
I believe that one of the most concrete differences about sets and types is the difference in the way the "things" in your mind are encoded into the formal language.

Both sets and types allow you to speak about things, and collections of things. The main difference is that with sets, you can ask any question you want about things and it will maybe be true, maybe not; while with types, you first have to prove that the question makes sense.

For example, if you have booleans $\mathbb B=\\{\operatorname{true},\operatorname{false}\\}$ and natural numbers $\mathbb N=\\{0, 1,\dots \\}$, with types, you can not ask if $\operatorname{true}=1$ which you can with sets.

One way to interpret this is that with sets, everything is encoded into a single collection: the collection of all sets. $0$ is encoded as $\[0\]=\\{\\}$, $n+1$ is encoded as $\[n+1\]=\\{\[n\]\\}\cup \[n\]$ and $\operatorname{true}$ and $\operatorname{false}$ can be encoded by any two distinct sets. So that it actually makes sense to ask if $\operatorname{true}=1$, as it can be understood as asking if "the encoding chosen for $\operatorname{true}$ is the same as the encoding chosen for $1$". But the answer to this question could change if we chose another encoding: it is about the encodings and not really about the things.

You can then think of types as describing the encoding of the things inside it. With types, to ask the question of whether $a=b$, you first have to show that $a$ and $b$ have the same type, i.e. that they were encoded in the same way, which prohibits questions such as $\operatorname{true}=1$. You could still want to have a big type $S$ in which both $\mathbb B$ and $\mathbb N$ could be encoded, and then given two encodings $\iota\_\mathbb B:\mathbb B\to S$ and $\iota\_\mathbb N:\mathbb N\to S$, you could ask whether $\iota\_\mathbb B(\operatorname{true})=\iota\_\mathbb N(1)$ but the fact that this question depends on the encodings (and the choice of encodings) is now explicit.

Note that in those cases, whether the question made sense was actually easy to see but it could be much harder as in, for example, $(\operatorname{if} \text{very\_hard\_question} \operatorname{then} 1 \operatorname{else} \operatorname{true})=1$.

In summary, sets let you ask any question you want, but types force you to make encodings explicit when the answer may depend on them.
> 4 votes

---
Tags: type-theory, sets
---


title: Cubical type theory for dummies?

text:
# Question
Title: Cubical type theory for dummies?
I read one of those popular papers on cubical type theory, but no wonder I could only see formulas and diagrams without being able to recognize them at all.

So here's what I want. I want a deep enough explanation of what composition, Kan filling and gluing have to do with homotopy type theory. I don't expect there could be an ELI *(insert age)* for it but instead define the word *dummy* in the title as someone having some basic understanding of HoTT and category theory (perhaps, but not necessarily optionally).

# Answer
A year after and I'm writing one myself.
> 9 votes

---
Tags: type-theory, homotopy-type-theory
---


# Question
Title: unambiguous grammar that produce equal number of a and b
is there any **unambiguous grammar** on alphabet={a,b} that can produce strings which have equal number of a and b (e.g. "aabb" , "baba" , "abba") ?

# Answer
> 9 votes
The problem with $S\to aSbS\mid bSaS\mid \varepsilon$ is that you're just making sure you match each $a$ with a $b$ (where we consider an $a$ and a $b$ to be matched iff they appeared during the same derivation step).

To ensure non-ambiguity, you must add a constraint on the matching to ensure that it is unique (while maintaining its existence). One way to do that is to make sure you match the first $a$ (resp. $b$) after your $b$ (resp. $a$) that hasn't been matched yet.

So you'd get something like $$ S\to aB S\mid bA S \mid \varepsilon\\ A \to a \mid b \square\\ B\to b \mid a\square$$

The idea is the following:

* You want $S$ to generate words with as many $a$ as $b$s. At any points you can stop with the $S\to \varepsilon$. If you do add an $a$ with $S\to aBS$, then you need to add a $b$ later, and you put a $B$ to remind you of that, and then you continue with another $S$. The same things applies for $S\to bAS$.
* If you have an $A$, it means that you are one $a$ short. If you read an $a$, everything is fine and you've got nothing else to do. But if you read a $b$, you are now two $a$s short. I left a $\square$ for you to fill to encode that.
* $B$ works like $A$.

---

Solution :

> You are two $a$s short so you are twice one $a$ short: $A \to a \mid b AA$. Similarly $B\to b\mid aBB$

---

For the proof, see this where $a,b,A,B$ are replaced with $0,1,O,I$ and your language is generated by $E$.

# Answer
> -1 votes
The ambiguity of the above grammar can be resolved as

S-\>aBS/bAS/ε
A-\>a/bAA
B-\>b/aBB

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


# Question
Title: Is there a variant of Dijkstra’s algorithm for partial recalculation?
Suppose the following:

* We use Dijkstra’s algorithm to find the shortest route to our destination.
* The start node (current vehicle position) keeps changing, i.e. moving towards the destination along the calculated shortest path. For this reason we use the inverted form, where the cost of a node represents the cost to reach the destination from there, and the destination’s cost is 0—that way the route graph does not need to change as the vehicle moves through it.
* The cost of edges may change while the vehicle is moving towards the destination (e.g. the traffic situation may affect transit times).
* We want to update the route graph based on edge costs without rebuilding it completely. Rather, as a set of changes arrives, we want to determine which nodes are affected by it and set their cost.
* For now, we are neglecting the fact that the cost of an edge may change again before we reach it—the route is always based on current edge costs.

Is there a standard algorithm for this kind of partial recalculation?

# Answer
The paper linked by BlueRaja - Danny Pflughoeft provided the right pointer, though some effort was required to find a solution for the exact problem above, which I am describing here.

Considerations:

* The existing implementation favors Dijkstra over A\*, as we reduce the route graph to a rectangle enclosing the start and destination locations, plus a little extra, and consider local roads only within a certain distance of the start and goal, not within the entire rectangle. (This may give us a non-optimal solution, but that is beyond the scope of this question.) A\* comes with the penalty of calculating the heuristic for each node, in exchange for potentially reducing the number of nodes that need to be expanded. In this particular situation, the penalty exceeded the benefit, i.e. A\* performs worse than Dijkstra here.
* Dijkstra is equivalent to A\* with the heuristic of each node being zero.
* D\*-Lite builds upon LPA\* (Lifelong Planning A\*), which in turn builds upon A\*. (Disclosure: I wrote this Wikipedia article yesterday, any errors in there are likely mine.)
* While A\* and LPA\* are static, D\*-Lite incorporates changes of the start node (movement of the vehicle) into the algorithm—which would require architectural changes.

Considering all of the above, a reasonable solution (in terms of achieving the desired result with acceptable performance and without major architectural changes) seems to be:

* Build upon LPA\*.
* Calculate from goal to start, unlike canonical Dijkstra/A\*/LPA\*, but just like the existing algorithm.
* Use a fixed heuristic of zero for all nodes (which the existing routing algorithm effectively does already).

(By the way, if one assumes a fixed start position and a static heuristic of zero, then D\*-Lite and LPA\* behave identically.)
> 2 votes

# Answer
Yes. A search algorithm that is able to quickly recompute the fastest path when small changes are made is known as an incremental algorithm. For your case specifically, you'll want to use D\*-Lite, the algorithm used by the Mars Rovers.

See here for more information.

*(Note: D\*-Lite is decently complex. If this is for a video game, there are better ways to obtain speed-ups using off-the-shelf A\* implementations)*
> 3 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: How to get initial flow for TSP with missing edges
I need to solve a version of the traveling salesman problem with missing edges. I've decided to use simulated annealing.

How do I generate a valid initial path effectively?

I would use a greedy algorithm, but I can't be sure it will result in a valid path. I could still use it and hope that simulated annealing will find a valid path, but I can't guarantee that it will.

# Answer
> 1 votes
Set the cost on the missing edges to $+\infty$, or some suitably large constant. Then all paths are valid, and you can apply simulated annealing. Simulated annealing will have a very strong incentive to avoid those edges.

In general, you cannot expect any algorithm to both (a) be guaranteed to find a valid path, and (b) be guaranteed to terminate in a reasonable amount of time. That's because finding a valid path is the Hamiltonian path problem, which is NP-hard -- so even finding a single path could be extremely hard, depending on the input graph. Since you presumably want an algorithm that terminates in a reasonable amount of time, that means you'll have to accept the possibility that the algorithm fails to output a valid path. (If not, then you'll have to accept the possibility that the algorithms fails to terminate in your lifetime, which seems just as bad.)

---
Tags: graphs, graph-traversal, heuristics, traveling-salesman
---


title: Interval Scheduling Confusion

text:
# Question
Title: Interval Scheduling Confusion
I am reading some notes about interval scheduling. I gives the following diagram:

and states that:

r2 is compatible with r3, while r2 and r1 are conflicting. Similarly, the set {r1, r3, r4} is compatible, while {r2, r3, r4} is not compatible.

I can understand that set (r1, r3, r4) is compatible. How (r2, r3, r4) are not compatible. Since they are not overlapping, isn't they are compatible?

# Answer
> 1 votes
That looks like an error in your notes. {r2,r3,r4} are compatible.

---
Tags: greedy-algorithms, intervals
---


title: Complexity Reduction Analysis

text:
# Question
Title: Complexity Reduction Analysis
I am struggling to grasp fully grasp complexity reductions, I have this example that I am working through and can not fully comprehend how to determine the complexity of one algorithm given the complexity of another, either $ O$ or $\Omega$
The example algorithm is:

```
  Input: left: array of n integers
  Input: right: array of m integers
  Input: n,m:  size of left and right
  Output: TwoSumSplit(left, right,t)
1 mix = Array()
2 for i = 1 to n do:
3  Add 3(left[I]) + 1 to mix
4 end
5 for i = 1 to m do:
6  Add 3(right[I]) + 1 to mix
7 end
8 return TwoSum(mix,3t)

```

the complexity of TwoSumSplit(TSS) is $\Theta(n + m + TS(n + m))$

My question is how can I determine the complexity of an algorithm given the complexity of another, for example:
$if\space TS(n) = O(n)$
$if\space TS(n^2) = O(n^2)$

then what can be determined of the complexity of TSS?

Using the notation of $A \le\_p B$,I know that "TSS surrounds TS", along with rules such as reducing from unknown to known for $O$ and reducing from known to known for $\Omega$. I've determined that from statements like $if\space TS(n) = \Omega(n)$ nothing can be determined using these stated rules/observations.

Source: Dr. Hendrix; Analysis of Algorithms. Spring 2017 USF

# Answer
If $TS(n) = O(n)$ then $TSS(n,m) = \Theta(n+m)$.

If $TS(n) = O(n^2)$, then all we can say is that $TSS(n,m) = \Omega(n+m)$ and $TSS(n,m) = O(n^2+m^2)$.

How did I reach these conclusions? First of all, clearly $TSS(n,m) = \Omega(n+m)$. If $TS(n) = O(n)$ then $TS(n+m) = O(n+m)$ and so $TSS(n,m) = O(n+m + O(n+m)) = O(n+m)$. Altogether, $TSS(n,m) = \Theta(n+m)$.

If $TS(n) = O(n^2)$ then $TS(n+m) = O((n+m)^2) = O(n^2+m^2)$, since $(n+m)^2 = \Theta(\max(n,m)^2) = \Theta(n^2+m^2)$ (you might prefer the middle form to the one on the right). Therefore $TSS(n+m) = O(n+m+O(n^2+m^2)) = O(n^2+m^2)$.
> 3 votes

---
Tags: complexity-theory, algorithm-analysis, asymptotics, reductions, landau-notation
---


title: Validity of this formula in WS1S logic

text:
# Question
Title: Validity of this formula in WS1S logic
The following formulas are said to be defined in WS1S logic.

$Closed(Z, R) := ∀x ∀y(x ∈ Z ∧ R(x, y) → y ∈ Z)$ $(z\_1, z\_2) ∈ R^∗ := ∀Z.(z\_1 ∈ Z ∧ Closed(Z, R) → z\_2 ∈ Z)$

However since WS1S formula requires bounded second order variables to be finite, I am not sure if the second formula is valid. $Z$ which is bounded here, can be an infinite subset of natural numbers. For example, when $R$ is a $succ$ relation.

There are no restrictions on $R$ stated in the reference.

In the paper Implementing WS1S via Finite Automata by James Glenn and William Gasarch : $∀X∃Y ∀z(¬(z ∈ X) ∨ (z + 1 ∈ Y ))$ is stated to be a valid WS1S formula.
$∀x∃y(y \< x)$ is stated as an invalid WS1S formula.

However if $X$ is finite in the first formula, $Y$ is infinite and hence I think this should not be a valid formula. In the second formula there are no second order variables and therefore it should be a valid formula. Please let me know what am I missing here.

# Answer
The confusion comes mainly from different meanings of validity.

In the context of syntax, we are used to understand 'valid' as syntactically correct. As in '`42["Hello world"]` is a valid C expression'. I believe this is also how you understood Glenn&Gasarch. Their statement does make sense with semantic instead of syntactic validity.

Let me shortly recap semantics of WS1S. Generally, in second-order logic (weak or non-weak), the semantic of a formula is defined relative to an interpretation. The interpretation defines the meaning of all symbols. It consists of a structure and an assignment. The structure defines the universe and the meaning of the symbols from the base vocabulary. The assignment defines the meaning of the free variables. For a formula $\varphi$ and an interpretation $\mathcal I$, the semantics define whether $\mathcal I\models\varphi$ shall hold.

In WS1S, the structure is fixed: The universe is the natural numbers and the only other symbol is interpreted by the successor relation. Hence, for formulae $\varphi$ without free variables (sentences), the semantics can do without mentioning the interpretation. That could be written just $\models\varphi$, or $\models\_{\text{WS1S}}\varphi$. And that is what Glenn&Gasarch mean with validity.

Let me stress that the finite-subset restriction of WS1S is not a syntactic one. The syntax of WS1S is the same as that of S1S (which has quantification over arbitrary subsets). Hence syntactic validity (well-formedness) is not jeopardized by concerns of what can or cannot be achieved with a finite subset. Indeed the only difference between WS1S and S1S is of semantic nature. By definition, $\mathcal I\models \exists X\varphi$ holds

1. (in case of S1S) if there is a subset $S$ of the universe such that $\mathcal I\[\frac SX\]\models\varphi$, or
2. (in case of WS1S) if there is a finite subset $S$ of the universe such that $\mathcal I\[\frac SX\]\models\varphi$.

Now to the other two formulae you asked about. Both are syntactically valid, if you allow binary second-order variables ($R$ in this case) as arguments (which is fine for defining subformulae as building blocks; in the end these variables will have to be substituted by other formulae). As they have free variables, we cannot say anything about semantic validity without having an assignment.

However, the names of the formulae suggest intended semantics. And we can compare the actual semantics to the intended ones.

1. The first formula holds (in the sense of $\models$) iff the set which is assigned to $Z$ is closed to the right under the relation assigned to $R$. That does seem to match the intention.
2. The second formula holds iff the element assigned to $z\_2$ is reachable from the element assigned to $z\_1$ by a path all of whose steps belong to the relation assigned to $R$, or if infinitely many elements are reachable in that way. That does not seem to match the intention.

But again, I would not use the notion of validity to discuss whether a formula fulfills its purpose.
> 1 votes

---
Tags: logic
---


# Question
Title: Understanding Martin Farach's suffix tree algorithm
I feel stuck at this point. I have spent several days trying to get my head around the algorithm, but both resources I have \[1\] \[2\] seems to skip over whatever details that would make me comfortable trying to explain/implement it. I'm going to hope that someone here knows Farachs suffix tree algorithm, but I'll link to the paper below.

I get the individual mechanisms of the algorithm, but I don't understand how to put it all together. By starting at the first step:

(1) Creating the odd tree requires sorting every character pair of the string, but the example used, namely `g = 121112212221` yields the "sorted" list `l = (1,2),(1,1),(1,2),(2,1),(2,2),(2,1)`, and then taking the ranks of `l` yields. `g' = 2,1,2,3,4,3`. I can't see how `l` is sorted, or why it would help to sort it.

(2) Farach mentions that the suffix tree for `g'` needs to be computed recursively. Is this the only step of the algorithm that needs recursion?

\[1\] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.4336&rep=rep1&type=pdf

\[2\] https://www.amazon.com/Computing-Patterns-Strings-William-Smyth/dp/0201398397

# Answer
Not a complete answer but I hope this helps.

re :

> Creating the odd tree requires sorting every character pair of the string, but the example used, namely g = 121112212221 yields the "sorted" list l = (1,2),(1,1),(1,2),(2,1),(2,2),(2,1), and then taking the ranks of l yields. g' = 2,1,2,3,4,3. I can't see how l is sorted, or why it would help to sort it.

Let,

$l$ - list

$g$ - ranks of elements of $l$ in $sorted(l)$

You can easily recover $sorted(l)$ using $l$ and $g$. You just put $i^{th}$ element of $l$ at position $g\[i\]$ in some new array $A$, like this,

```
for i = 0 to len(l):
   A[g[i]] = l[i]

```

Fill out following $A$ to see it.

l = \[3, 2, 4\]

g = \[2, 1, 3\]

A = \[ , , \]
> 2 votes

---
Tags: recursion, suffix-trees
---


title: What does canonical extension mean?

text:
# Question
Title: What does canonical extension mean?
*Density-reachability is a canonical extension of direct density-reachability.* What is meant by canonical extension?

Source: A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf

# Answer
The term 'extension' could generally be interpreted in mathematical sense1 as an **enlargement of the domain of a pre-existing function.**

In your case, assume *Density-reachability* could be described as a process $d\colon A \rightarrow B$ mapping inputs from domain $A$ to output in domain $B$. An enlargement of domain could be viewed as another map $e\colon A \rightarrow A'$ which maps where the old inputs in $A$ could be thought of as special cases in subset of $A'$ that is the image of map $e$.

An extension then could be described as any map $x\colon A' \rightarrow B$ which statisfy $$x \circ e = d$$ There could be many such $x$, so picking extension is a choice. The above equation basically expresses that

> If I pick $a \in A$ from the old domain, translate it to the new domain as $e(a)$, then use this new tool $x$ which could be thought of as an extension of old tool $d$ along the translation $e$, then the final result must agree with just using the old tool $d$ to begin with.

or $$x \circ e(a) = d(a)\qquad; \forall a \in A$$

The term 'canonical' simply implies that the choice of extension is the obvious, natural one of the situation.

1 At least from the perspective of category theory.
> 2 votes

---
Tags: machine-learning
---


# Question
Title: What is the point of (Compactness theorem in the) Overspill principle?
The principle (called a Löwenheim–Skolem theorem by Huth and Ryan) states

> Let $\phi$ be a sentence of predicate logic such that for any natural number $n \geq 1$, there is a model of $\phi$ with at least $n$ elements. Then $\phi$ has a model with infinitely many elements.

IMO, it basically states that if you can always name a number larger than mine arbitrary natural number then your model is infinite. What needs to be proven here? There are no other options obviously for any school kid.

**PS** The answers state that there is a difference between having infinite amount of models and single infinite model. But this is similarly stupid. At first, I do not see whether I claim that I have a single infinite model or approach it by having all denumerable models. Secondly, it does not matter since in any case you should have an infinite model in order to respond to any natural number.

Nevertheless, I started to understand why people (mistakenly) ask me to differentiate between infinite amount of models and models of infinite size. They fail to recognize that principle "The fact that I can always name a number larger than yours implies that we have an infinite model/set", which is intuitive and used to prove the overspill theorem, also implies that the model of infinite size exists. The set of models $A = \\{M\_k, M\_l, M\_m \ldots\\}$ has sizes $S = \\{k, l, m, \ldots\\}$ correspondingly. When you speak about size of models, you basically speak of the numbers in $S$. When you say "a model of size n" you just say "n". Thus, we can forget about set of models and speak only about S. Now, you say that "whatever integer you have, set S contains a larger one." This basically means that S contains an infinite number (i.e. $A$ contains infinite models). What to be proven here?

In other words, what is the point of expanding $\phi$ with infinite set $\\{I\_1, I\_2, \ldots\\}$ in the proof and applying the Compactness theorem? This says that there is an infinite model. But this is obvious without even without it, right from the the premise of the overspill principle.

# Answer
The theorem says that when a sentence has *arbitrarily large* (*finite*) models, then it also has *infinite* models.

The antecedent of the theorem:

> $\phi$ is a sentence of predicate logic such that for any natural number $n \geq 1$, there is a model of $\phi$ with at least $n$ elements.

is equivalent to saying that there are *infinitely many different models*, but it does *not* state that any of these models are infinite in size.

In fact, it would be clearer to use:

> $\phi$ is a sentence of predicate logic such that for any natural number $n \geq 1$, there is a *finite* model of $\phi$ with at least $n$ elements.

This is not exactly the same statement, but as an antecedent within this theorem, it is equivalent.

The consequent:

> $\phi$ has a model with infinitely many elements.

does *not* say anything about how many different models there are - it just says something about the size of at least one of them.

To see that the truth of this theorem doesn't simply follow from its structure, consider the following statement, which has the same structure:

> Let $\phi$ be a sentence of predicate logic such that for any natural number $n \geq 1$, there is an *equivalent* sentence of predicate logic with at least $n$ elements. Then there is an equivalent sentence with infinitely many elements.

Is this a theorem, too? No, this statement is false, for the simple reason that all sentences of predicate logic have finitely many elements by definition.
> 6 votes

# Answer
Your interpretation isn't faithful to the theorem: if *within* a model you can always find a larger number, then the model is infinite. But the theorem says that if there is an infinite number of *finite* models, there is also an infinite model (which is not an obvious consequence).

The statement you quote appears in a book I have (Computability and Logic by Boolos and Burgess) as the "Overspill Principle."

> Overspill Principle: If a set of sentences has arbitrarily large finite models, then it has a denumerable model.

To prove this, let $\Gamma$ be a set of sentences with arbitrary large finite models. For each $m$ let $I\_m$ be a sentence with no nonlogical symbols true in a model iff the model has size $m$ or larger. Let $\Gamma^\*=\Gamma\cup\\{I\_1,I\_2,\ldots\\}$ be the result of adding every $I\_m$ to $\Gamma$. Every finite subset of $\Gamma^\*$ has a model, because every such subset is also a subset of $\Gamma\cup\\{I\_1,I\_2,\ldots I\_m\\}$ for some $m$, and $\Gamma$ has arbitrarily large finite models. By compactness, $\Gamma^\*$ itself has a model $M$. Then $M$ is a model of $\Gamma$, but also a model of $I\_m$ for every $m$, meaning $M$ has size at least $m$ for every $m$, i.e. $M$ is infinite.
> 5 votes

# Answer
The other answers are really quite good, but here is basically another variant. Let's start with the logical mistake you're making, just to get it out of the way. Consider the statement:

> Let $\mathcal{C} = \\{A\_1,A\_2,\ldots\\}$ be a sequence of sets with $\\#A\_i \ge i$. Then one of the $A\_i$ is infinite.

This is not, in general, true. Why? Just take $A\_i = \[i\]$. These are all clearly finite. That $\mathcal{C}$ is infinite doesn't make the statement true.

Here, the idea is that we want $\mathcal{C}$ to be the set of models for $\phi$ and we want to somehow use the infinite sequence of finite models $A\_i$ to find a single infinite model $A$.

Since we've seen that this kind of statement isn't always true, clearly something about $\phi$ and things that are true about models of FO sentences that aren't true of arbitrary sets needs to come in.

This is where your second mistake comes in. What you want to prove doesn't say what you think it does. You say:

> "it basically states that if you can always name a number larger than mine arbitrary natural number then your model is infinite."

This is not what it says at all. You are imagining a game played within one model. That's wrong.

If you want to give the intuition as a game, it's like this: if for every number $n$ that I give you, you will be able to come back with a (different) finite model $A\_n$ of size at least $n$, then there is an infinite model of $\phi$.

Now, we start to see why this might be difficult. Nowhere was it said that any of these $A\_n$ are related to each other in a way that lets you combine them into a larger model. This is the crux of the matter. To get around it, as in the other answer, the compactness theorem comes up, as does the hypothesis about $\phi$.

As a meta point, it is not bad to start with some intuition. But when that either trivializes or clashes with the statement, it's a good idea to try and write a formal proof, using the definitions. Usually, this will make clear what went wrong with the intuition, even if it seemed obvious.
> 3 votes

# Answer
In order to see why the theorem is not obvious, let us take $\varphi$ to be a second-order sentence saying 'my model is finite'. For all $n$, there is a model of $\varphi$ with $\geq n$ elements. Yet there is no infinite model.

Hence the theorem fails for second-order logic. The reason it holds for first-order logic is compactness.
> 2 votes

---
Tags: sets, first-order-logic
---


title: Show that a problem belongs to NP

text:
# Question
Title: Show that a problem belongs to NP
A logistics company has two trucks and has to deliver some packages to some addresses. The manager has to create a plan for every driver.

Input Data: A set of V locations, an array d\[v,u\] for every pair of locations u,v belongs to V. The distance (integer) is also stored between the locations. A starting point and an integer k.

Are there two circles that begin from the starting point so that every location (v belongs to V) that belongs to at least one of the circles and every circle has a maximum length of k?

I have to form this problem in a language and that belongs to NP class. I also have to show if is NP-Complete by reduction to a known NP-complete language. Any ideas to the above questions?

# Answer
Take an instance of “Hamiltonian circle”. Then construct an instance of your problem where one truck can just visit one point, and the other needs to solve the Hamiltonian Circle problem.

It happens quie often when you have a more complicated problem, that you can solve an instance of a simpler NP-complete problem by constructing an instance of the more complicated problem so that a solution forces a solution of the simpler problem.
> 0 votes

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


# Question
Title: How would the use of an external lookup table affect file compression?
It occurred to me that, the way compression essentially works, is that you have a mapping of long patterns to short patterns, which you replace one way to compress and the other to decompress. My understanding of the way compression algorithms work, is that they create this mapping dynamically, with things like huffman coding being used to create the lookup table.

And so I wonder: if a general lookup table was pre-built, and not derived in any way from the input file, how would this affect the compression? My guess would be that if would make the compression slightly less effective (because the ordering of the mappings would not be optimized for the specific case), but would make it much faster to run, since it doesn't need to build the table as it goes.

# Answer
> 3 votes
There are compression programs such as zstd which explicitly allow a separate dictionary text, and stream-based compressors such as LZW can be easily converted to use a dictionary by prepending it on the input. The dictionary appears as a fixed prefix on the output and can be removed, ie $C(xy)=C(x)C(y|x)$.

The benefit of using one text as a dictionary for another is a function of their mutual information, which is based on Kolmogorov Complexity (an incomputable minimum). However a compression algorithm turns out to be a good way to approximate it, using a technique known as Normalized Compression Distance. The texts are compressed separately and together as above, and the difference between $C(y|x)$ and $C(y)$ measures similarity. So, while it's difficult to predict the benefit, measuring it empirically has some uses.

# Answer
> 2 votes
It depends on the algorithm being used. Something like Huffman coding works by assigning variable length codes to the different symbols, so you could absolutely do what you suggest. The effect would be exactly as you say: compression would be a bit faster, but the compressed file would be larger because the code lengths wouldn't be optimized to that specific file.

However, for dictionary-based compression algorithms such as LZW, this approach doesn't really make sense. These work, essentially, by having a list of known sequences, which may as well start as the empty list. Now, start reading the file. Each time you see a sequence that is a known sequence plus one more character, that becomes a new known sequence and is entered into the dictionary. You then compress the file by writing out the indices of the known sequences it contains. This is tied very closely to the actual data that you're trying to compress and it barely makes sense to try to come up with a global dictionary.

---
Tags: efficiency, data-compression
---


# Question
Title: Longest common subsequence with at most one swap
Is there a good algorithm for calculating the longest common subsequence where we consider two sequences identical if they can be transformed to one another with at most 1 swapping of subsequences (i.e. taking two non-overlapping subsequences of the same length and substituting them for each other)? For example `ABCDEFGHIJ` would be considered identical to `EFGHABCDIJ` but not to `ABCDEHFGIJ`. Or is there such an algorithm for subsequences of length one?

# Answer
Swapping two non-overlapping subsequences is same as swapping two non-overlapping substrings of one of the input strings.

A simple algorithm would be to guess the start and end points of the substrings that we want to swap, let them be (s1,t1) and (s2,t2), and run LCS using this swapped string. There are O(m^2\*n^2) such guesses and each one takes O(m\*n).
> 1 votes

---
Tags: longest-common-substring
---


# Question
Title: Number of different increasing binary trees
This is a homework question that I am unable to solve. Any help would be really appreciated.

Given $B$ an increasing binary tree with root $r$ and $n$ nodes labelled $1, 2, . . . , n$ such that on every path from root $r$ to a node, the labelling is increasing.

Prove that there are $n!$ different increasing binary trees.

# Answer
Obviously, the root can only contain the smallest number $1$. Then $2$ can be placed in two positions, either as left or right child. Once this position is fixed, how many positions can $3$ go? Etcetera.
> 1 votes

---
Tags: binary-trees
---


title: Parsing table confusion

text:
# Question
Title: Parsing table confusion
I've been researching the different answers I've been given to this, would somebody just be able to give me a clear answer of the difference between

Shift, reduce and go-to. - In a parsing table.

Of course, reduce is in the same, but how do you know when to shift or go-to?

Thanks.

# Answer
Goto is what you do after a reduce. It's very like a shift, except that it is handlng a non-terminal while shift handles a terminal.

A reduce action removes some items from the stack and uses them to create a non-terminal, which must then be pushed ("shifted") onto the stack. As with a shift action, pushing a non-terminal moves the state machine to a new state, which is why we call these table entries "goto" entries; they specify which state the state machine switches to.

A shift action is looked up in the transitions of the current state. A goto action is looked up in the transitions of the state "revealed" by popping the stack during the reduce action. In both cases, the effect is to move the dot in each of the state's items one position to the right, moving over a terminal (shift) or a non-terminal (goto).
> 1 votes

---
Tags: algorithms, parsers
---


# Question
Title: How to print all pairs of ID numbers such that the corresponding people don't belong to the same socieities
I want to express the following in relational algebra:

Given a table of

```
PEOPLE: ID, SocietyName

```

Where the combination of ID and SocietyName form a key such that we could have the same ID in the table more than once but paired with a different society name.

I would like to be able to output all pairs of people, ID1 and ID2 such that they do not both attend any of the same societies. I am struggling to structure this in my head, I think I will need to rename PEOPLE to p1 and p2 say, then do some kind of join but I am not sure how to refine the output so it is only pairs where none share the same society.

# Answer
Firstly $\Pi\_{i\_1, i\_2}(\sigma\_{i\_1\leq i\_2}{(\rho\_{c\_1(i\_1, s)}People\times \rho\_{c\_2(i\_2, s)}People)})$ gives all possible permutations of ID pairs in the form $(a, b)$ with $a\leq b$.

By $\Pi\_{i\_1, i\_2}(\sigma\_{i\_1\leq i\_2}{(\rho\_{c\_1(i\_1, s)}People\bowtie \rho\_{c\_2(i\_2, s)}People)}$, we can gain all pairs of people who attend a same society.

So the answer is

$$\Pi\_{i\_1, i\_2}\Big(\sigma\_{i\_1\leq i\_2}{(\rho\_{c\_1(i\_1,s)}People\times\rho\_{c\_2(i\_2, s)}People)}-\sigma\_{i\_1\leq i\_2}{(\rho\_{c\_1(i\_1, s)}People\bowtie \rho\_{c\_2(i\_2, s)}People)}\Big)$$
> 1 votes

---
Tags: relational-algebra
---


# Question
Title: what does activation function become in spiking neural network?
In common ANN, nodes are based on a activation function, like a sigmoid or tanh or ReLU. Updates of synaptic weight are based on the derivative of this function.

When node are represented with spiking neurons, what does activation function become ? how updates of synaptic weight are done ?

# Answer
> 1 votes
The activation function would be inherent to the spiking model used.

Each model have a different dynamic which will depend on the proper model and parameters used.

---
Tags: neural-networks
---


# Question
Title: Maximize vertex cover weights with bounded edge weights in a connected subgraph
Similar questions were asked elsewhere, but no satisfying answers occurred yet.

In a graph with weights for both vertices and edges, I want to find a subgraph, whose sum of internal edge weights is bounded and the sum of internal vertex weights is maximum. Is this problem NP-hard? Please note that the subgraph has to be connected, and the sum of internal edge weights is calculated by the weight of Minimal Spanning Tree of this subgraph. An example is shown in  attached.

Attention: previously someone suggested that we can set the bound to 0 to reduce the problem to Maximum Independent Set. However, by setting all the bound to 0, the problem should be reduced to finding the node with maximum weight, for the nodes in the independent set are not connected which would cost infinite cost.

# Answer
This is already NP-hard in the special case that the graph is a tree, since Knapsack can be reduced to such an instance of this problem: Let $v\_i$ be the value of the $i$-th item, and $w\_i$ its weight. Create a vertex of weight $v\_i$ for each item $i$, and a single extra vertex that is connected by an edge of weight $w\_i$ to each item $i$. A capacity-$b$ knapsack can be filled with items of value at least $k$ iff the solution to the constructed instance of your problem with total edge capacity $b$ can achieve a total vertex-value of $k$.
> 2 votes

---
Tags: graphs, optimization, reductions, np, weighted-graphs
---


# Question
Title: What is the difference between Cased-based Reasoning and Rule-based reasoning?
As stated here, Rule-based Reasoning systems are considered to be "old style" AI that uses rules prepared by humans - as opposed to Neural Networks where machine recognizes pattern i.e. acquires new knowledge and takes decision based upon that.

What I understand about Case-based Reasoning (CBR), it looks at the new cases in light of similar past cases, finds suitable reference cases, evaluates their application on the new case and revises it accordingly, applies it on the new case, and finally stores the case and solution as newly acquired knowledge.

Considering this, can I state that Case-based Reasoning should be considered as "new style" AI? Or is there a gap in my understanding?

---

I wanted to add: If anyone can offer a rough spectrum, that puts different AI approaches on different points depending on how independently they can take decision or how much prone they are to learn from experience (i.e. train their mind) instead of being 'pre-configured', that will also be welcome.

# Answer
> 5 votes
As said in the comments, there may be a part of subjectivity in the answers to this question.

Yet, I think it is fair to say that case-based reasoning mostly belongs to what is often called transductive methods, while rule-based (as well as neural networks and most statistical models) models mostly belong more to what is often called inductive approaches.

In short:

* Transductive methods will not try to induce a generic model from your past observations/experiences, but will simply try to predict/find the answer of a new problem by looking at past experiences. This means you have to maintain a memory of past experience, and then select the most adequate one to answer your new problem. The most well-known representative of such approaches is probably K-NN.
* Inductive approaches will try to induce a "compact" model from your past observations/experiences, and to generalise (make an induction) from those. Once this is done, you can forget your past experiences and only use your learned model to make prediction.

The parallel you can make is between looking up a table of stored input/output values (e.g., to get a p-value), which is transductive, and using a mathematical formula to compute a new prediction, which is inductive.

Lastly, it should be noted that the way you build your model when performing induction largely depends on your applications, available knowledge and needs (there are certainly ways to learn rule-based systems from data).

---
Tags: terminology, machine-learning, artificial-intelligence, case-based-reasoning
---


# Question
Title: What are the primal and dual planes in the context of the point-line duality?
In computational geometry, we can define a duality between points and lines. The line is the primal (or dual) object of a point, or a point is the primal (or dual) object of a line. However, the exact definition of the primal and dual planes is often not given in the literature. It's a little bit confusing which one is which. What are exactly the primal and dual planes in this context?

# Answer
In short, *the original $(x, y)$-plane is the primal plane and the new $(a, b)$-plane the dual plane*.

More specifically, in a $(x, y)$-plane (or coordinate system)1, a *non-vertical* line can be represented as $\ell \colon y = ax - b$, where $a \in \mathbb{R}$ is the slope and $b \in \mathbb{R}$ the $y$-intercept. Hence, to describe a line, we just need to scalars, $a$ and $b$. We can state that a line has two degrees of freedom.

The idea of the duality between lines and points is that lines in the $(x, y)$-plane can be thought of or represented as points in a **new** $2$-dimensional space (or coordinate system), in which the coordinate axes are labeled $(a, b)$, rather than $(x, y)$. This new plane is denoted or labeled as $(a, b)$ to emphasize the fact that the values that $a$ and $b$ may assume respectively refer to the slope and $y$-intercept of the line $\ell$ in the original $(x, y)$-plane.

For example, the line $\ell : y = 2x + 1$, in the $(x, y)$-plane, corresponds to the point $\ell^\* = (2, −1)$ in this **new** $(a, b)$-space 2, 3; that is, $\ell^\*$ is a $2$-dimensional point with $2$ as the value of the $a$-coordinate and $-1$ as the value of this $b$-coordinate. A point $p=(5, 2)$ in the $(x, y)$-plane corresponds to the line $p^\* \colon b = 5 a - 2$ in the $(a, b)$-plane 4. Similarly, a point $q = (1, 6)$ in the $(a, b)$-space, corresponds to a non-vertical line, $q^\* \colon y = 1x − 6$ in the "original" plane $(x, y)$. And a line $t \colon \frac{1}{2} a - 5$ in the $(a, b)$-plane corresponds to the point $t^\*=(\frac{1}{2}, 5)$ in the $(x, y)$-plane.

A convention is to call the original $(x, y)$-plane the **primal plane**, and the *new* *(a, b)*-plane the **dual plane**.

Why is $(x, y)$ the "original plane"? What's "original" about it? It's simply the plane where our initial problem is formulated. For example, we may have a problem where we are given a set of points. Then, we say that those points are given in the primal plane. We may convert our points to lines in the dual plane, because maybe we can formulate our problem in terms of lines, and the new problem is easier to solve.

Of course, we could have labeled the "original" plane with other letters, e.g. $(g, h)$, but we often label it $(x, y)$, so the new system is labeled differently, e.g. $(a, b)$. We could have labeled the new plane or coordinate system $(o, z)$: it really does not matter, i.e. it's just notation!

Here's a picture which summarizes all these words

---

**Notes**

1. Note that we *label* this plane $(x, y)$, but could have labeled it $(u, v)$ or any other tuple of two letters: it does not matter (as long as we are consistent).
2. Note the $-$ (i.e. the minus) in front of the $1$ in the point $\ell^\*$.
3. We use an asteristik, $\*$, to denote the dual of some object. For example, $u^\*$ is the dual (in the dual plane) of $u$ (in the $(x, y)$ or primal plane). $u$ can either be a line or a point. If $u$ is a line, then $u^\*$ is a point. If $u$ is a point, then $u^\*$ is a line.
4. Note the $-$ (i.e. the minus) in front of the $-2$ in the equation of the line $p^\*$.
> 8 votes

---
Tags: terminology, computational-geometry
---


title: Reducible and NP Hard

text:
# Question
Title: Reducible and NP Hard
I have been confusing a bit about these relationship:

Given A polynomial reducible to B

1/ If A is NP hard, what is the hardness of B?

2/ If B is NP hard, what is the hardness of A?

3/ If A has polynomial algorithm, how is B?

4/ If B has polynomial algorithm, how is A?

Since "B is as hard as A", then for 1/, we can say B is also NP Hard. However, I'm not sure about the reverse order. In 2/, there is not enough evidence to conclude the hardness of A

Also, for 4/ If B has poly algorithm, then A also has a poly algorithm. I'm thinking 3/ is also similar, since A is reducible to B and B as hard as A, if A has poly algorithm so does B.

Can someone please verify this? Thanks very much

# Answer
> 0 votes
If a problem $A$ is reduced to $B$, this implies that an algorithm $\mathbb{A}$ that solves $B$ can also solve $A$.

If $\mathbb{A}$ is a polynomial-time algorithm, then $B \in \mathbf{PTIME}$ and also $A \in \mathbf{PTIME}$.

If it is the case that when $\mathbb{A}$ is polynomial-time algorithm, this implies that $\mathbf{P} = \mathbf{NP}$, then $B$ is an $\mathbf{NP}\text{-hard}$ problem. Which means $A$ is also an $\mathbf{NP}\text{-hard}$ problem.

These statements answer questions 1, 2, and 4. However, your third question cannot be answered with the information you provided. This is because any problem in PTIME is also in NP, and therefore having a polynomial-time algorithm does not necessarily mean that $B$ has a polynomial-time algorithm. It might or might not have.

---
Tags: complexity-theory
---


title: Why does $W[1] = A[1]$ hold?

text:
# Question
Title: Why does $W[1] = A[1]$ hold?
By definition, a parameterized problem $(Q, \kappa)$ is in $W\[1\]$ if it can be transformed into a combinatorial circuit $\varphi$ in polynomial time, such that the weft of $\varphi$ is 1.

On the other hand, $(Q, \kappa) \in A\[1\]$, if it can be transformed into a parameterized model checking problem $p$ -$MC(\Sigma\_1)$.

Finally, $(Q, \kappa) \in W\[1\] \Leftrightarrow (Q, \kappa) \in A\[1\]$ holds. However, I did not see why a parameterized model checking problem has to have weft 1. It occurs to me as if $W\[1\] \subseteq A\[1\]$.

Why are they the same class?

# Answer
> 2 votes
The proofs can be found in the literature. I'll try to explain the intuition.

The short version is that parameterized independend set is typical for both $W\[1\]$ and $A\[1\]$.

The general intuition about the $W$- and the $A$-hierarchy is that they are about amounts of nondeterminism. In particular, at the first levels, both hierarchies allow existential nondeterminism with $n^k$ possibilities to choose from, followed by universal nondeterminism with $n$ possibilities, followed by existential nondeterminism with a constant number of possibilities. Let us see that for each of the three problems.

1. Independend set is the question:

* Is there a set of $k$ vertices,
    * such that for all edges
    * there is an endpoint not in the set?

The first bullet point is existential ("is there?") with $\binom nk$ possibilities. Up to parameterized reductions there is no difference between $\binom nk$ and $n^k$. The second point is universal ("for all") with as many possibilities as there are edges. Which is bounded by the input size $n$. The last part is existential ("there is") with $2$ possibilities ($2$ endpoints per edge).
2. In the case of $W\[1\]$, that is of parameterized weighted $c$-CNF-SAT, the first existential nondeterminism concern the set of variables to set to true, much like the vertex set above. The universal nondeterminism ranges over the clauses, all of which have to be satisfied. Their number is bounded by $n$. The last part is existential, namely finding an atom in the clause that is satisfied. That part has at most $c$ possibilities.
3. For model checking of $\Sigma\_1$, it is not obvious at first that the above nondeterminism suffices. We will have to do some normalization of $\Sigma\_1$ formulae. First, let us assume that the quantifier-free part is in DNF. Achieving DNF may bring an exponential blow-up, but as the formula is the parameter, any blow-up is fine. Second, let there be a bound $r$ on the arity of relations (I will not go into the details of how to do that). Last, let all atoms be negative (that can be achieved by adding complements for all relations with an $n^r$ blowup.

Now the quantifiers incur existential nondeterminism with $n$ possibilites each, for a total of $n^k$. The disjunctive part of the DNF brings another existential $n$. The resulting $n^{k+1}$ is as well as $n^k$ under parameterized reductions. Then comes a conjunctive clause for universal nontederminism with $k$ possibilities. Then comes a negated relational atom: For all tuples in the relation ($n$ (universal) possibilities, because the relation is part of the input) there is some position ($r$ existential possibilities) at which the tuple differs from the values chosen for the quantifiers. Again, think of independent set, where $r=2$. The universal part totals to $k\cdot n$, which is as well as $n$ under reductions.

---
Tags: complexity-theory, parameterized-complexity
---


# Question
Title: Can we use Operator precedence parsing with this grammar?
This Grammar:

A--\>Bbab|aa

B--\>b

I think we can't because basically there is no relation between terminals? like no relation between a and b! or am i missing something? and the language of this grammar has only 2 members !

can we using Operator precedence parsing with this grammar?

# Answer
> 1 votes
It's an operator grammar since no right-hand side has two consecutive non-terminals. So we then attempt to construct the precedence relations:

$$b \gtrdot b \\ b \doteq a \\ a \doteq b \\ a \doteq a $$

There is no multiple entry, so an operator precedence parser is possible.

---
Tags: formal-languages, automata, compilers, parsers
---


# Question
Title: How to Compute the Fixed Point on a DataFlow Lattice
Wondering the general overview of how to compute the fixed point on a program's dataflow lattice.

A fixed point of a function $f(x)$ is one where the output of the function equals the input, so:

$$f(x) = x$$

Given $f$ is an order preserving (monotonic) function $x ⊑ y \Rightarrow f(x) ⊑ f(y)$, in this presentation, they have $x\_\bot$ be the least fixed point of $f: L \to L$, so $f(x\_\bot) = x\_\bot$, where $L$ is a program lattice. Then they say:

> Now, let $x\_0 = \bot$ \[the end of the lattice\] and $x\_i = f(x\_{i−1})$
>
> * By induction, $x\_i ⊑ x\_\bot$.
> * Also, the chain $x\_i$ is an ascending chain.
> * If $L$ has no infinite ascending chains, sooner or later $x\_i = x\_{i+1} = x\_\bot$

I'm wondering what this means. What happens algorithmically (the high-level steps) when we are iterating toward a fixed point. In the presentation they say "*Do computation by simulating execution of program until reach fixed point*".

This doc says "*In this situation \[data flow\], the mathematical function is the **flow function** \[so $f$\], and the fixed point is a tuple of the dataflow analysis values at each point in the program (up to and including the loop)*". They define *flow function* as a map from the dataflow info immediately before to after the *program point / instruction*.

So essentially, we divide the program into nodes or points where each point is an instruction/statement. We create a function showing the change of values from before and after each point (*in* and *out*, the flow function). We then iterate on the values somehow, that's where I'm unclear about. Wondering if we are iterating through the program points, calling $f$ for each point, or if we stay at one point and iterate on it with some sort of input until we reach a fixed point. Then wondering how that works. Not sure how the iteration works, or how $x\_\bot$ works (if its part of some subset of the program points $L$ for each point (kind of like a neighborhood) or what.

# Answer
You don't compute the least fixpoint of a lattice; you compute the least fixpoint of a function $f$. The standard method is to use a method called chaotic iteration, which is exactly the iterative algorithm described in your quote: set $x\_0 := \bot$, $x\_1 := f(x\_0)$, $x\_2 := f(x\_1)$, etc., and keep iterating until you reach $i$ such that $x\_i = x\_{i+1}$; the resulting $x\_i$ is the least fixpoint of $f$.

In some cases it is possible to speed this up for a particular function $f$, but don't worry about this at this stage.

It's possible to view the process above as in some sense simulating the execution of the program, but I find it likely that this viewpoint is going to lead to confusion, so I'm not sure I would recommend trying to understand it that way. Iteratively evaluating $f$ is not the same as iterating through the program points of the program.

Talk about splitting the program up is largely irrelevant to your question about how to compute a least fixpoint. There are two steps: convert the program to a function $f$; find the least fixpoint of $f$. The business about dividing up the program is relevant to how you convert the program to $f$, but not relevant to how you compute the fixpoint of $f$ (at least, not at the basic level).
> 1 votes

---
Tags: lattices, data-flow-analysis
---


title: Class P is closed under concatenation

text:
# Question
Title: Class P is closed under concatenation
Proving that Class P is closed under concatenation.

The answer is given below:

But I do not know why stage 2 is repeated at most O(n), could anyone explain this for me please?

# Answer
> 2 votes
With $n = |w|$ the length of $w$, step 2 is repeated exactly $n+1$ times.

But they assume implicitly that $n$ is the length of the input (which is canonical in complexity theory), i.e. $|\langle w \rangle|$ with an unspecified encoding $\langle.\rangle$ of strings.
(Why they insist to introduce that encoding here, I don't know.)

The $O$ (which should be a $\Theta$) comes from that encoding as well. While there are exactly $|w| + 1$ ways to cut $w$ in two parts, we don't know the exact figure in terms of $|\langle w \rangle|$.

They forget to mention their assumption that that encoding is reasonable in a certain way, i.e. $|\langle w \rangle| \in \Theta(|w|)$ for all $w$.

---
Tags: complexity-theory, closure-properties, polynomial-time
---


# Question
Title: Prove that L $\in$ NP implies L* $\in$ NP
I have been trying to solve this problem with witness theorem. So the problem is as below: Define $L^\* := \\{x \in \Sigma^\*|$there exists k and $x\_1,...,x\_k\in L$ such that $x=x\_1x\_2...x\_k\\}$. Prove that $L \in NP$ implies $L^\* \in NP$.

So my initial thought is to find a witness language $\in P$ for $L^\*$ from the fact that L has a witness language L1 $\in P$. However, I am not sure how to find the right partition of x such that I can use the witness $(x\_1,y\_1),...,(x\_k,y\_k) \in L1$.

Does anyone have any thought on it? Much appreciated!

# Answer
Lets hop back to the definition of a NP language, there exists a non-deterministic Turing machine NTM that halts when given $x$.

It's not that much work to create a non-deterministic Turing machine that first splits the input string into parts non-deterministically and then simulates running NTM on each of the parts and only halts when all parts make the NTM halt.
> 1 votes

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


# Question
Title: Meaning of the notation Typ := TVar | (Typ → Typ)
In the paper "introduction to type theory" by Herman Geuvers, it states the following definition for the type theory of propositional logic (I've added "convention 2" just for reference):

>

Given that this is an introduction, I'd assume that he would explain the meaning of a statement like $\mathrm {Typ}:=\mathrm {TVar}|(\mathrm {Typ}\to \mathrm {Typ})$, or what a "type variable" is.

My question is twofold:

* What do these two things mean?
* What background knowledge is this introduction assuming, that I would need to study before reading this "introductory" text?

# Answer
Intuitively, a type variable is like a variable in an expression, except that it stands in for a type rather than standing in for a number/bitstring/etc.

Formally, we choose a countably infinite set $\mathsf{TVar}$, and then define a type variable to be a member of $\mathsf{TVar}$.

The notation $\mathsf{Typ}:=\mathsf{TVar}|(\mathsf{Typ}\to \mathsf{Typ})$ is an instance of Backus normal form. It is an inductive definition of $\mathsf{Typ}$. It says that if $\alpha$ is a type variable (i.e., if $\alpha \in \mathsf{TVar}$), then $\alpha$ is an element of $\mathsf{Typ}$; and if $\alpha,\beta$ are type variables (i.e., $\alpha,\beta \in \mathsf{TVar}$), then the term $\alpha \to \beta$ is an element of $\mathsf{Typ}$. $\mathsf{Typ}$ is the set of terms that can be constructed in this way. We call a term a *type* if it is an element of $\mathsf{Typ}$.
> 7 votes

# Answer
More formally, if you are familiar with algebraic data types (sometimes referred to as "generalized enumeration types") as in Haskell, O'Caml, Agda, Swift, Rust, and (thankfully) increasingly more programming languages, it's basically declaring $\mathsf{Typ}$ as:

```
data Typ tv = TVar tv | TArrow (Typ tv) (Typ tv)

```

This is using Haskell's algebraic data type syntax. Here I've decided to make `tv` a parameter because we don't care what the "type variables" actually are as long as we can distinguish them from each other and we can get a "new" one whenever we need to (hence the usual statement that it is a countably infinite set). To be clear, while algebraic data type mechanisms usually incorporate a "tag" to discriminate the options from each other, `TVar` and `TArrow` above, the notation used in the paper does not do a *disjoint* union. This means that we further require elements of $\mathsf{TVar}$ not to be of the form $t\to t'$ for $t,t'\in\mathsf{Typ}$. So $\mathsf{TVar}$ could be a set of natural numbers, a set of strings, a set of rational numbers, a set of finite subsets of natural numbers, or many, many other things.

At any rate, the core idea is the notion of an inductively defined set. Here's just a random book chapter I found googling "inductively defined set": https://www.cl.cam.ac.uk/teaching/1213/DiscMathII/Ch5.pdf As D.W. states, the specific notation used is inspired by Backus-Naur Form (almost always referred to simply as BNF) which is a notation for context-free grammars. Such grammars give rise to inductively defined sets of derivations.
> 6 votes

# Answer
You can read $Typ$ as the least set containing $TVar$, and such that for all $a, b \in Typ$ we have $(a \to b) \in Typ$.
> 5 votes

---
Tags: type-theory, notation
---


# Question
Title: Proof of Lower Bound for Deterministic Distinct Elements Algorithm
There is a proof in this document (page 8, Section 4, Lemma 3: https://inst.eecs.berkeley.edu/~cs170/fa16/lecture-11-29.pdf) that mirrors a proof my professor gave in my algorithms class. The lemma states:

> Suppose that there is a deterministic exact algorithm for counting distinct elements that uses o(min{|$\Sigma$|, $n$}) bits of memory to process a stream of $n$ elements of $\Sigma$.
>
> Then there is a compression algorithm that maps $L$-bit strings to bits strings of length o($L$).

The conclusion is false, therefore the premise is false. The proof is by contradiction. This is proved by constructing a compression algorithm that encodes an $L$-length bit string in fewer than $L$ bits. A decoding method is then given for reconstructing the $L$-length bit string.

What confuses me is that the paragraph above is apparently the contradiction that proves that you cannot transmit an $L$-length bit string using fewer than $L$ bits. And yet it seems to show that this actually can be done.

I understand the counting argument that says you cannot map $2^L$ bit-strings losslessly onto a range of $2^L-1$ outputs. What I need to understand for my class is why the given proof by contradiction is valid. If anyone can help me with the intuition concerning why the proof is valid, I would appreciate it

# Answer
> 0 votes
Consider the following argument:

> If $0 \> 1$ then $1 \> 2$.

Proof: Starting with $0 \> 1$, add $1$ to both sides.

Since it is not true that $1 \> 2$, we can conclude that $0 \> 1$ is also false.

The same is true in your example. Starting with some assumption A, you prove property B. However, property B is clearly false, so assumption A must have been false as well. Don't forget that you can derive everything from False.

---
Tags: algorithms, information-theory, lower-bounds, streaming-algorithm
---


# Question
Title: How come Datagram Packets between same source-destination pair may take different routes?
This might be a rookie question, but I wanted to understand the following line.

My book says, each time a host wants to send a packet, it places the address of the destination host in the packet's header. Okay, I understand this.

Also, packets forwarded using destination address have their address mapped to an outgoing interface. Packets between same source destination pair may take different routes.

Why is that? If packets have the same destination address should they not be mapped to the same outgoing interface?

Is there something I have left out or not understood that is leading to this confusion or is there an explanation to this!

# Answer
Packets are routed individually: each time a router receives a packet, it decides what to do with that packet. It doesn't necessarily make the same decision each time it receives packets for a particular destination. To give a trivial example, somebody might have changed the router's configuration in the time between two packets arriving; a more common example would be a router trying to avoid congested links by sending some packets down a quieter link.
> 4 votes

---
Tags: computer-networks
---


# Question
Title: Why can't we say that NP is closed under complement given that we can say it is closed under intersection
I found online solutions which prove the closure of NP under intersection in the following way: given machines $M\_1,M\_2$ for accepts nondeterministically languages $L\_1,L\_2$, we construct the following machine $M$ which accepts nondeterministically $L\_1 \cap L\_2$:

$M$ = ”On input $w$:

1. Run $M\_1$ on $w$. If $M\_1$ rejected then reject.
2. Else run $M\_2$ on $w$. If $M\_2$ rejected then reject.
3. Else accept."

Is this proof correct? Can't we use similar ideas to show that NP is closed under complementation, which is supposedly an open problem?

# Answer
> 6 votes
There are several ways to describe the semantics of nondeterministic Turing machines. Perhaps the most colorful is the "guess and verify" semantics. We enhance a vanilla Turing machines with a guess tape, whose exact semantics will be explained below. Our Turing machine communicates its computation with the user by means of the state at which it halts. Some states are marked ACCEPT, the rest are marked REJECT. The semantics of the machine are as follows:

> A nondeterministic machine accepts an input $x$ if there exists a string $y$ such that if we run the machine with $x$ on the input tape and $y$ on the guess tape, then it accepts (i.e., halts at a state marked ACCEPT).
>
> Conversely, the machine rejects an input $x$ if whenever we run the machine with $x$ on the input tape and *arbitrary* contents on the guess tape, it always rejects (i.e., halts at a state marked REJECT), whatever we wrote on the guess tape.
>
> A nondeterministic machine accepts a language $L$ if it accepts all $x \in L$ and rejects all $x \notin L$.
>
> A nondeterministic machine *runs in polynomial time* (*polytime* for short) if there is a polynomial $p(n)$ such that whenever we run the machine with $x$ on the input tape and arbitrary contents on the guess tapes, it always halts within $p(|x|)$ steps.

(We are slightly cheating here: the definitions of acceptance and rejection are complementary only if the machine is promised to always halt, which is indeed the case for machines running in polynomial time.)

---

When describing the operation of a nondeterministic machine, we will often use the keywords "guess" and "verify". They have the following meaning:

1. **Guess $w$**: Copy a string $w$ (delimited in some fixed way) from the guess tape to the work tape.
2. **Verify property $A$**: Check whether property $A$ holds. If so, continue with the execution of the algorithm. Otherwise, halt at once at a state marked REJECT.

Another important convention is:

* If the algorithm runs its course without rejecting, then the machine halts at a state marked ACCEPT.

Here is an example, a machine for SAT:

> Input: A formula $\varphi$ in conjunctive normal form.
>
> Operation: Guess an assignment $a$, and verify that it is a satisfying assignment.

A more exact description of the machine would be:

> 1. Copy an assignment $a$ from the guess tape to the work tape.
> 2. Check whether $a$ satisfies $\varphi$.
> 3. If $a$ doesn't satisfy $\varphi$, halt at a state marked REJECT.
> 4. Otherwise, halt at a state marked ACCEPT.

---

Let us now consider the proof that NP is closed under intersection. Let $M\_1,M\_2$ be polytime nondeterministic Turing machines accepting languages $L\_1,L\_2$ (respectively). The following polytime nondeterministic Turing machine $M$ accepts $L\_1 \cap L\_2$:

> 1. Verify that $M\_1$ accepts the input.
> 2. Verify that $M\_2$ accepts the input.

In more detail:

> 1. Decode the contents of the guess tape into two guess words.
> 2. Run $M\_1$ on the inputs and the first guess word. If it halts at a state marked REJECT, enter a state marked REJECT and halt.
> 3. Run $M\_2$ on the inputs and the second guess word. If it halts at a state marked REJECT, enter a state marked REJECT and halt.
> 4. Enter a state marked ACCEPT and halt.

Why does this work? Let $L$ be the language accepted by this machine. We have to show that $L = L\_1 \cap L\_2$.

1. $L\_1 \cap L\_2 \subseteq L$: Suppose that $x \in L\_1 \cap L\_2$. Since $x \in L\_1$, there exists a string $y\_1$ such that $M\_1$ accepts when run on $x$ with $y\_1$ on the guess tape. Similarly, since $x \in L\_2$, there exists a string $y\_2$ such that $M\_2$ accepts when run on $x$ with $y\_2$ on the guess tape. If we run $M$ on $x$ with $(y\_1,y\_2)$ on the guess tape, then it will accept, and so $x \in L$.
2. $L \subseteq L\_1 \cap L\_2$: Suppose that $x \in L$. Thus there is a string $y = (y\_1,y\_2)$ such that when $M$ is run on the input $x$ and $y$ on the guess tape, it accepts. The machine $M$ verifies that $M\_1$ accepts when run on the input $x$ and $y\_1$ on the guess tape, and that $M\_2$ accepts when run on the input $x$ and $y\_2$ on the guess tape. Therefore $x \in L\_1$ and $x \in L\_2$, and so $x \in L\_1 \cap L\_2$.

---

Now let us try to prove that NP is closed under complementation. Let $M$ be a polytime nondeterministic Turing machine accepting a language $L$. We construct the following Turing machine $M'$:

> Run $M$. If $M$ accepts, reject. Otherwise, accept.

Let us see what are the semantics of this machine. The machine $M'$ accepts an input $x$ if there exist a string $y$ such that when running $M$ on $x$ with $y$ on the guess tape, it rejects. Conversely, the machine $M'$ rejects an input $x$ if $M$ accepts $x$ regardless of the contents of the guess tape.

This is not quite what we want, and to demonstrate it, let us consider the machine $M$ accepting SAT described above. Recall that the machine interprets its input as a formula $\varphi$, and the contents of the guess tape as an assignment $a$. The machine $M$ accepts iff $a$ satisfies $\varphi$. The corresponding machine $M^c$ has the following semantics:

1. The machine $M^c$ accepts a formula $\varphi$ if some assignment $a$ doesn't satisfy $\varphi$.
2. The machine $M^c$ rejects a formula $\varphi$ if all assignments $a$ satisfy $\varphi$.

In other words, the machine $M^c$ accepts the language of all formulas which are not tautologies. This is not what we were aiming for: we wanted $M^c$ to accepts the language of all unsatisfiable formulas. As an example, $M^c$ accepts the formula $x\_1 \lor x\_2$ even though it is satisfiable, because it's not a tautology (if $x\_1$ and $x\_2$ are both false then $x\_1 \lor x\_2$ is also false).

# Answer
> 5 votes
Nondeterministic Turing Machines don't technically reject. They accept or run indefinitely. You can also not abort that. It's a very subtle difference with a lot of impact. Otherwise indeed it would be that NP=co-NP

As was noted, this is the in model that I learned. Other models are possible, where the Nondeterministc machine does halt even when rejecting (see Yuval's answer). Also in such models, NP is not closed under complement.

# Answer
> 3 votes
I prefer representing languages by their decision problems, i.e. Boolean functions $2^\*\to 2$, i.e. the language $L = \\{x\in 2^\*\mid \varphi(x)\\}$ and $\varphi(x)\iff x\in L$ converts between these two representations. That given languages $L\_1, L\_2\in\mathbf{NP}$, $L\_1\cap L\_2\in\mathbf{NP}$ looks like: given $\varphi,\psi\in\mathbf{NP}$, $\varphi\land\psi\in\mathbf{NP}$.

By (one) definition, $\varphi\in\mathbf{NP}$ if and only if there is a polynomial-time Turing machine (TM) $M$ and a polynomial $p$ such that for all $x\in2^\*$, $$\varphi(x)\iff\exists u\in 2^{p(|x|)}.M(x,u)=1$$ where $|x|$ is the length of the bitstring $x$. The reason the conjunction of $\varphi\_1$ and $\varphi\_2$ is in $\mathbf{NP}$ is because if for each $x\in 2^\*$, there exist TMs $M\_i$, polynomials $p\_i$, and $u\_i\in 2^{p\_i(|x|)}$ such that $\varphi\_i(x) \iff M\_i(x,u\_i)=1$, then $u\_1u\_2\in 2^{q(|x|)}$ where $q(X) = p\_1(X)+p\_2(X)$ is a polynomial such that $\varphi\_1(x)\land\varphi\_2(x) \iff M(x,u) = 1$ where $M$ is the TM that extracts the first $p\_1(|x|)$ bits of $u$ which is $u\_1$ and simulates $M\_1(x,u\_1)$, then extracts the remaining $p\_2(|x|)$ bits of $u$ which is $u\_2$ and simulates $M\_2(x,u\_2)$ and returns $1$ if each of these return $1$. $M$ runs in polynomial-time if $M\_1$ and $M\_2$ do.

So why doesn't a similar approach work for the complement, i.e. for calculating $\neg\varphi(x)$? Let's logically manipulate the definition of $\mathbf{NP}$ a bit. Negating both sides of the $\iff$ gives $$\neg\varphi(x)\iff\forall u\in 2^{p(|x|)}.M(x,u)=0$$ So the issue is while for $\varphi\in\mathbf{NP}$ there is for every $x\in 2^\*$ some TM $M$, polynomial $p$, and $u\in 2^{p(|x|)}$ such that $M(x,u)=1 \implies \varphi(x)$, for $\neg\varphi$ to be in $\mathbf{NP}$ we'd need $M(x,u) = 1 \implies \varphi(x)$ for ***all*** $u\in 2^{p(|x|)}$ which is to say $M$ would need to decide membership for $x$ without using anything (except perhaps the length) about $u$. This certainly isn't the case for all TMs witnessing membership in $\mathbf{NP}$. Therefore, we can't use an arbitrary witness that $\varphi\in\mathbf{NP}$ to build a witness that $\neg\varphi\in\mathbf{NP}$ simply by simulating $M$ and negating the result. This doesn't rule out that we can't find other TMs to witness $\neg\varphi\in\mathbf{NP}$; just that the TM that simulates $M$ and negates its output doesn't work in general.

# Answer
> 1 votes
The definition of NP is not symmetric.

The definition of a decision problem in NP is: "If the answer for an instance is YES, then there is polynomial time proof that the answer is YES". (Or: There is a hint that can be checked in polynomial time. Or: There is a non-deterministic machine that finds a proof in polynomial time. All equivalent).

The existence of a simple proof if the answer is YES doesn't imply the existence of a a simple proof if the answer is No.

Take the problem "Is there a mouse in my house"? If the answer is YES, there is a very simple proof: Just grab it by its tail. The proof may be hard to find, but once you found it it is easy to check. If the answer is NO, you'll have to search the whole house with all its tiny little corners for the mouse, and then you have to search again because it could have moved to a room that you already searched. So for the answer YES there is a simple proof, for the answer NO there isn't.

Or the Travelling Salesman Problem: Given a set of cities and their distances, is there a way to visit each city once, with a total distance less than 1,000 miles? If the answer is YES, I'll give you a list of cities with total distance less than 1,000 miles, and you have your proof. Easy to check. If there is no such city, then one proof would be to check *all possible cycles* and check that none had a distance less than 1000. The proof is an awful lot harder.

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


# Question
Title: Fractional vertex cover number may not be feasible? Very confusing!
For my project, I try to use **minimum fractional vertex cover number (MFVC)**. (Please find below definition details) MFVC can be formulated as optimal solution of a linear program relaxation.

However I find that every linear program relaxation is either infeasible, unbounded, or has an optimum solution.

Does is mean that MFVC may not exist, or may not be a finite number, but MFVC is less or equal to minimum vertex cover number? Very confusing! :(

Many thanks!

---

*Definitions:*

**K-uniform hypergraph:**

**Minimum fractional vertex cover number (MFVC):** **link** (*on page 8*)

**MFVC as linear programming relaxation:**

The minimum fractionl vertex cover $\tau^\* (G)$ in a k-uniform hypergraph $G=(V,E)$ is $\min \sum\_{v\in V}w (v)$

such that $0 \le w(v) \le 1$,

and for each $e \in E$, we have $\sum\_{v\in e} w(v) \ge 1$.

# Answer
The linear program defining the minimum fractional vertex cover always has an optimal solution. The fact that some linear programs are infeasible or unbounded doesn’t mean that *every* linear program is infeasible or unbounded.

To give another example, sometimes you can’t divide by $x$. But if $x$ is a positive integer, then you can always divide by $x$. This in no way contradicts the fact that there exist $x$ that you can’t divide by - it just means that this complication doesn’t occur for positive integers.

To see that the minimum fractional vertex cover always exists, we have to show that the relaxation is *feasible* and *bounded* (from below). To see that it is feasible, notice that if you assign $w(v) = 1$ for all $v$, then you get a feasible solution. To see that it is bounded from below, notice that $w(v) \geq 0$ guarantees that the objective functions is always non-negative.
> 5 votes

---
Tags: graphs, linear-programming
---


# Question
Title: Introduction to type theory for a beginner?
I'm interested to read about type theory, but I'm quite a beginner. I know what sets are and how to work with them, but I don't have a deep understanding of set theory. I don't really understand the motivation behind type theory, other than that it was first developed to solve the problems with naive set theory.

I'm mainly interested in type theory because I heard it relates to proof theory (which I also don't understand well). I'm also not a mathematician or computer science by education.

**Is there a good resource for beginners that introduces type theory, motivates it, shows how its different from set theory, why that's relevant, and shows how it can be used?** I'd be satisfied if I have a thorough understanding of the general idea without understanding more advanced stuff.

# Answer
Why has no one proposed Benjamin Pierce's *Types and Programming Languages*? That is a good introduction to type theory. Bob (Robert) Harper's *Practical Foundations of Programming Languages* is also a pretty good one.

Both of them introduce type theory from a computing perspective. If you like math better, try Rob Nederpelt and Herman Geuvers' *Type Theory and Formal Proof: An Introduction*. I have not taken a look at *Basic Simple Type Theory* by J. Roger Hindley yet, but I figure it should be good given the author (judging from the table of contents though, it looks hard).
> 4 votes

---
Tags: reference-request, type-theory, sets
---