# Question
Title: The second Functor law is redundant, but I don't understand the proof
When we defining a `Functor` instance in Haskell, it should satisfy the following two laws:

* `fmap id = id`
* `fmap f . fmap g = fmap (f . g)`

But I found these two articles that say the second Functor law can be derived form the first:

The proof in these articles uses the free theorem for `fmap`. For example, the second article says that:

> Free Theorem:
>
> The free theorem for `fmap :: (a -> b) -> F a -> F b` is that given functions `f`, `g`, `k`, and `h` such that
>
> ```
> g . h = k . f
>
> ```
>
> then
>
> ```
> $map g . fmap h = fmap k . $map f
>
> ```
>
> where `$map` is the "natural map" for the type constructor `F`.
>
> Proof:
>
> This is a free theorem, so it holds for *any* function with the same type signature as `fmap`, regardless of implementation.
>
> You can obtain this theorem employing Philip Wadler's “Theorems for Free” laboriously by hand as is done by Bartosz in the comments below, but we can also obtain this result just by asking `lambdabot` to do it for us on IRC.
>
> ```
> <edwardk> @free fmap :: (a -> b) -> (F a -> F b)
> <lambdabot> g . h = k . f => $map_F g . fmap h = fmap k . $map_F f
>
> ```
>
> Thanks, `lambdabot`!

I cannot find Bartosz's comment, so I found and read Philip Wadler's “Theorems for Free”.

Philip Wadler's “Theorems for Free” basically says that for each type $T$, there is a corresponding relation $\mathcal{T}$, and every closed term $t$ of type $T$ satisfies $(t,t)\in\mathcal{T}$.

The type constructor $F$ of the Functor would also give a function $\mathcal{F}$ from relations to relations. This is the "natural map" `$map` in the article. But the problem is, this `$map` does not always map functions to functions.

When I tried to derive `fmap`'s free theorem by hand, I got this:

> For given functions `f :: A -> B`, `g :: C -> D`, `k :: B -> D`, `h :: A -> C` such that
>
> ```
> g . h = k . f
>
> ```
>
> then for every `x :: F A` and `y :: F C`, if `(x, y)` is in the relation `$map h`, then `(fmap f x, fmap g y)` is in the relation `$map g`.

If we can show that `$map` actually maps functions to functions, this result would be the same as that in the article.

But there are some type constructors that `$map` doesn't maps functions to functions. For example, for `F a = a -> ()`, `$map` would map functions to functions in the inverse direction.

How do I fill this gap of the proof?

# Answer
The same way as in this question, the gap is once again the identity extension property. This means that the relational interpretation of a type operator maps identity relations to identity relations. This property is not mentioned in Wadler's paper, but it is in Reynolds'. It's needed whenever we want to reason about parameterized types.

The assumption of a "natural map" looks like an error to me, for the reasons you mention; arbitrary type operators are not functors.

Let's look at the proof. I write the relational interpretation as `ᴿ` superscripts, so that e.g. `fmapᴿ` denotes the free theorem for `fmap`. We assume `F : * → *` and `fmap : ∀ A B. (A → B) → F A → F B` with `fmap A A id x = x`. The goal is

```
fmap A C (f ∘ g) x = fmap B C f (fmap A B g x)

```

Now, by identity extension for `F`, I know that `Fᴿ (Id C) = Id (F C)`, where `Id A` is the identity relation on `A`. So it's enough to show that the sides are related in `Fᴿ (Id C)`. We apply `fmapᴿ` to get this.

* We have to pick a relation between `A` and `B`: let this be the graph of `g`.
* The relation between `C` and `C` must be the identity relation.
* Now, it's trivial to show that `f ∘ g` and `f` take related inputs to related outputs.

It only remains to show `(x, fmap A B g x) ∈ Fᴿ (Graph g)`. This is equivalent to

```
(fmap A A id x, fmap A B g x) ∈ Fᴿ (Graph g)

```

We use `fmapᴿ` once again.

* We choose the relation between `A` and `A` to be the identity.
* We choose the relation between `A` and `B` to be `Graph g`.
* Once again relatedness of `id` and `g` is trivial.
* We have to show `(x, x) ∈ Fᴿ (Id A)`, but by identity extension that's just `(x, x) ∈ Id (F A)`.
> 2 votes

# Answer
Andras is correct here. In the interest of full disclosure, I'm the original author of lambdabot and the free theorem plugin, and so I'm in a unique position to tell you exactly what's going on.

The way the plugin works is that it assumes that a type constructor with a single argument is a functor, and generates a free theorem using its map operation.

So, for example, suppose that the arity-1 type constructor is `F`, then it calls the map operation `$map_F`. There is a special case for lists; then it just calls it `$map`.

I made this assumption for a simple reason: it's an IRC bot. I didn't want to bother users with having to write this:

```
@free my_function :: (Functor f) => (a -> b) -> (f a -> f b)

```

Instead, they should be able to just write this:

```
@free my_function :: (a -> b) -> (F a -> F b)

```

If you do that, you get an answer like this:

```
g . h = k . f => $map_F g . my_function h = my_function k . $map_F f

```

Note that I called it `my_function` in this example rather than `fmap` to emphasise the fact that this is *not* the `fmap` operation for the functor type `F`. The `fmap` operation for `F` is called `$map_F`.

So, to repeat the important part of the second paragraph of this answer. Lambdabot *assumes* that a type constructor `F` with a single argument is a functor, and gives the `fmap` operation for that functor the name `$map_F`.

And what, might you ask, does it mean to assume that `F` is a functor? Well, it means that it *has* a "natural map" operation, and that this "natural map" operation obeys the functor laws.

So what this theorem is actually stating is that if `F` is a functor, then for any function `my_function :: (a -> b) -> (F a -> F b)` such that `my_function id = id`, then `my_function` is really that type's `fmap` operation. Or, more generally, that `my_function` is completely determined by what it does when you apply it to `id`.

It does *not* prove anything if `F` is not a functor.

It is not difficult to come up with arity-1 type constructors that are not functors. (Exercise: Do this! As a hint, try a cofunctor.) If you ----------have such a constructor, the assumption that lambdabot made is incorrect, and so the free theorem that lambdabot claims isn't true.

I'll try to get this fixed.

**EDIT**

I contacted Edward Kmett, who wrote that article in School of Haskell for fpcomplete (we've known each other for decades), and apparently it's now effectively archived and closed for editing. So there's apparently not much he can do about the mistake in the article.
> 3 votes

---
Tags: type-theory, category-theory, haskell
---


# Question
Title: How can ford fulkerson be explained concisely?
After going through the resource list, is the following a way to explain ford fulkerson concisely ?

Graphs is represent is a 2D matrix with flow capacity as a tuple in each cell.

```
while exists (P_residual = residual graph path from S to T obtained via BFS )
    modify actual and residual graph with P_residual by
    1. getting capacity of P_residual.Its the min of all edges in the path P_residual
    2. transfer this capacity from P_residual in residual graph to actual graph. This would mean subtracting from residual graph matrix and adding to actual graph matrix

```

I am assuming *P\_residual* is the *augmented path* ?

## Resources

# Answer
The title and the body of your question ask different questions.

Ford-Fulkerson cannot be explained more concisely than giving the algorithm, which in turn means you should explain the residual graph.

The pseudo-code snippet you have attached is not very satisfactory. It's certainly concise, but it leaves a lot of necessary details out. For example, you need to at least say that you pick the minimum residual capacity of the path as the value you augment with, and you need also to say how you modify the graph(s?).

You say "modify actual and residual graph", but I don't think that's correct. You either modify the *flow*, and then reconstruct the residual graph, or you modify the residual graph. You probably don't modify the actual graph.
> 1 votes

---
Tags: graphs, graph-traversal
---


title: Loops and Its Time Complexity

text:
# Question
Title: Loops and Its Time Complexity
Back here with some more doubts, i wanted to understand, how can we formally or may be easily calculate time complexity for such question without getting into "DRY RUN", i mean is there any way for it? and for below question i am getting O(loglog(n/2)) which is not right!

Thankyou in advance for sharing your wisdom :)

# Answer
The inner loop executes $\dfrac{n-j}2$ times, and the middle loop processes $j=n,\dfrac n2,\dfrac n4,\cdots$

This makes a total that is very close to $\dfrac{n\lg(n)}2-n$.

The outer loop repeats this $\lg(n)$ times, for a grand total of

$$\left(\dfrac{n\lg(n)}2-n\right)\lg(n)$$

which is asymptotically $O(n\log^2(n)).$
> 0 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: What does arc and chain mean in Ford Fulkerson 1956 paper?
Ford Fulkerson 1956 uses words like "arcs" and "chains". What do they mean ? Arc = path and chain = edge ?

# Answer
> 2 votes
The paper litteraly gives the definition on the first page. An arc is a directed edge, and a chain is a directed simple path (*"does not intersect itself"*).

---
Tags: graphs
---


# Question
Title: What is a witness string in a zero knowledge proof?
I had earlier asked the question What is a witness string? I unable to understand the concept

From the answers I got, it seems that a witness is more or less the answer. For e.g. in the padlock example given in the accepted answer, the witness is the padlock combination which can be easily verified to be true or false.

I assume it (witness == answer) is not the same in Zero Knowledge proof systems because then it wouldn't be a zero knowledge system. Can someone explain witnesses in the context of Zero Knowledge Proof systems?

In the padlock example, if we had to provide a zero knowledge proof, what would be a witness string? Alternately is there some other simple example of ZK proof, where we can understand what a witness string is?

# Answer
A witness $w$ is essentially some extra helping information that you can use to verify something.

In the case of zero-knowledge proofs, $w$ will help you prove that the other party solved the problem, but it may not necessarily *be* the solution (since we need the zero knowledge property).

So there is no real difference between what you already know as a witness and a witness in zero-knowledge proofs, except that witnesses in zero-knowledge proofs are more likely to be more complicated as well.
> 1 votes

---
Tags: complexity-theory, zero-knowledge-proofs
---


# Question
Title: How to represent a point cloud in the pseudocode of an algorithm?
I am writing a scientific paper in which I describe some algorithms (using pseudocode) that have point clouds as inputs. In these algorithms, I need a mathematical structure to represent a point cloud. I need this mathematical structure to permit to access the $i$-th point in a point cloud. I have read some papers that use sets to represent point clouds, but if I use a set I won't be able to access the $i$-th point of that set. On the other hand, I was thinking of using an array of points to represent a point cloud. However, I also need some operations related to sets such as $\in$ and $\subset$.

To make it clear, the algorithms I mentioned are already implemented using the Point Cloud Library (PCL). In this library point clouds are C++ std::vector\<\>. **I am not interested in their implementation but in the correct mathematical structure for a point cloud that include the operations mentioned in the previous paragraph. This with the objective of describing them in a scientific paper.**

Thanks in advance.

# Answer
> -1 votes
You can use both a vector and set at the same time. The vector would provide efficient $i$-th element access, ande the set would provide efficient subset checks and membership tests.

In order to maintain that the vector and set have the same elements, write operations need to be performed on both the vector and the set, so the time complexities are added together. But read operations can be performed on the more efficient of the two data structures, so the minimum of the two time complexities is taken.

The following table gives a summary of the desired operations and their time complexities for each data structure.

| Operation | Vector | Set | Vector and set together |
| --- | --- | --- | --- |
| Insert/Delete | $O(1)$ amortized | $O(\log n)$ | $O(1) + O(\log n) = O(\log n)$ |
| $\subset$ | $O(n \log n)$ | $O(n)$ | $\min(O(n \log n), O(n)) = O(n)$ |
| $\in$ | $O(n)$ | $O(\log n)$ | $\min(O(n), O(\log n) = O(\log n)$ |
| Access $i$th element | $O(1)$ | $O(n)$ | $\min(O(1), O(n)) = O(1)$ |

# Answer
> -1 votes
What about $$C:=\\{i\in \[1,n\]: P\_i\\}$$

---
Tags: type-theory, discrete-mathematics, mathematical-foundations
---


title: NP-hardness and Turing reducibility

text:
# Question
Title: NP-hardness and Turing reducibility
I understand that if $A$ is NP-hard, and $A \leq\_{T} B$, then $B$ is NP-hard. Is the converse also true? So if $B$ is NP-hard, and $A \leq\_{T} B$, then $A$ is NP-hard? Why (not)?

# Answer
> 0 votes
No. Take for example $A = \emptyset$ and let $B$ be any NP-hard problem. Clearly $A \le\_T B$ but $A$ is not NP-hard.

# Answer
> 0 votes
The Turing reduction $A\leqslant\_T B$ can be explained as: "If I have a black box solving $B$, can I use it to solve $A$?".

Since such a definition does not have any constraint of time complexity, any computable set is reducible to any other. That means that even if $A$ is a problem $\mathsf{NP}$-complete, then $\emptyset\leqslant\_T A$ (but $A$ is not $\mathsf{NP}$-hard). Note that the converse is also true: $A\leqslant\_T \emptyset$, so your first affirmation is wrong.

If you find the last reduction odd, you can add a condition on complexity, for example "I cannot use the black box solving $B$ more than a polynomial number of times".

Even if you limit the number of uses to a polynomial number of times, your first affirmation is not necessarily true, because if $A$ is any problem, then $A\leqslant\_T^p \text{co}A$. If your affirmation was true, that would prove $\mathsf{NP} = \text{co}\mathsf{NP}$.

See here for some details.

---
Tags: np-hard
---


# Question
Title: Can you solve the "kinds of TMs" problem?
there are 3 kinds of TMs

1. a Halting TM on all inputs prints finitely many symbols on it's output tape and halts
2. a Circle-free TM on all inputs prints infinitely many symbols on it's output tape
3. a Crashy TM is neither Circle-free nor Halting (if a TM reject any input it's Crashy)

"the kinds of TMs" problem is to find a Crashy TM that computes the following function that uses crashing as a way to signal when the function is "undefined"

$$ \begin{align\*} k(m) &= \begin{cases} 1 & \text{if $m$ is a Halting TM} \\ 0 & \text{if $m$ is a Circle-free TM} \\ undefined & \text{if $m$ is a Crashy or invalid TM} \end{cases} \end{align\*} $$

I hope the implication of having a solution to this problem is obvious to everybody, it makes programming a lot more fun and easier

can you solve this problem?

to be clear this problem is different than Halting problem and Satisfactoriness problem

* Halting problem ask for a Halting TM to see whether $m$ is a Halting TM or Non-Halting TM
* Satisfactoriness problem ask for a Halting TM to see whether $m$ is Circular or Circle-free
* Kinds of TMs problem ask for a **Crashy TM** to see whether $m$ is Halting or Crashy or Circle-free

and you can NOT solve them by each other

it worth mentioning that there are 13 different kinds of Crashy TMs, I'm looking for a Hashi TM

1. a Crashi TM on all inputs after some times crash (stop moving the tape or tapes)
2. a Loopy TM on all inputs loops without printing infinitely many symbols on it's output tape
3. a Loopi TM is a Loopy TM that on some inputs crash
4. a Hashi TM is a Halting TM that on some inputs crash
5. ...

# Answer
> 1 votes
If there was a crashy-TM that computed $k$ we could use it to decide this version of the halting problem, which is known to be undecidable: given a Turing machine $T$, does $T$ halt on empty input?

You can see this by noticing that, given any Turing machine $T$, you can construct a new Turing machine $T'$ that 1) halts if and only if $T$ halts, 2) if $T$ does not halt, then $T'$ prints infinitely many symbols. In your nomenclature, either $T'$ halts (iff $T$ halts) or it is circle free.

To build $T'$ from $T$ we will simulate $T$ while ensuring that each transition of $T$ writes at least a new non-blank tape symbol. To guarantee this, we will make use of an additional tape symbol $\bot$. This symbol is not the blank tape symbol (which will be denoted as $\varepsilon$), but will behave similarly to $\varepsilon$ for the sake of simulating the tranistions of $T$. We will also allow symbols on the tape to be "marked", which can be done by duplicating the tape alphabet (i.e., each symbol has a "marked" and a "unmarked" variant). There will be at most one marked symbol at each point in time, and it will be used to remember the head position in the simulation of $T$. We proceed as follows:

1. Clear the tape (i.e., replace all input symbols with $\varepsilon$).
2. Simulate a transition of $T$ interpreting any read $\bot$\< as $\varepsilon$. If the transition of $T$ would cause $\varepsilon$ to be written on the tape, then write $\bot$ instead.
3. Mark the current tape location.
4. Move right until you find the first blank symbol $\varepsilon$, replace it with $\bot$.
5. Move left until you locate the marked tape location and unmark it.
6. Repeat from step 2 until $T$ halts (possibly forever).

# Answer
> 0 votes
Firstly I should mention that your picture is not correct. Probably the correct picture is as follows:

Secondly, the answer to your question about whether we can find a TM that computes the $k(m)$ functions is negative. Before giving the reason and proof let's fix some expressions. By the language of a TM $T$ I mean the following set:

$$\mathcal{L}(T) = \\{s\in \Sigma^\*\mid \text{when we run Turing machine } T \text{ given input } s \text{ it goes into accept state and halts.}\\}$$

where $\Sigma$ is a set of input symbols.

The reason is the following reduction:

First, consider Turing Machine $M'$ that acts as follows:

1. Turing Machine $M'$ takes two inputs $m, w'$.
2. Check if $w=w'$ ($w$ is a fixed string in its memory for Machine $M'$)

if $w\neq w'$ it go into reject state and halts.

if $w=w'$ it run TM with coding $m$ with input $w'$ and go into accept state and halt, if $m$ goes into accept state and halt.

It is obvious that the *language* of TM $M'$ is $\\{w\\}$ if TM with coding $m$ accepts $w$, and otherwise, it is empty (Since in this case $M'$ went into a loop, or crashed or ...)

Now, assume that there is a Turing machine $K$ that computes $k(m)$ you have defined in your question that is

$$k(m)=\left\lbrace\begin{array}{ll} 1 & \text{m is halting}\\ 0 & \text{m is circle free}\\undefined & \text{m is crashy or invalid} \end{array}\right.$$

Whenever we give coding of Turing machine $M'$ (assume it is $m'$) then we expect that $K$ return $0$ if $L(M')=\\{w\\}$ and return $1$ or $undefined$ otherwise..

So where is the problem? consider the following language:

$$\mathcal{A}\_{TM} = \\{(m,w)\mid \text{When we run Turing machine } m \text{ on input } w \text{ it goes to accept state and halt.}\\}$$

By having Turing machine $K$, we can decide the above language which is undecideable! How? We simply on input $(m,w)$ devise the coding of Turing machine $M'$ defined in above, give this encoding $m'$ to the Turing machine $K$ and Hey! We decide whether $m$ accept $w$ or not!

You can check the proof of undecidability of $\mathcal{A}\_{TM}$ in the book with title: \`\`Introduction to Theory of computation" page 202 Theorem 4.11.

What we have did? We have the reduction $\mathcal{A}\_{TM}\leq L(K)$ (Check corollary 5.23 in the above book.)

By the way, can you tell humans characteristics from their outfit and appearance? It seems not. The same is here for Turing machines. You are not able to tell that a Turing machine $m$ can halt or crash or stuck into infinity just by its syntax! you need to look at its behaviour, and so if it goes into infinity, you probably stuck into infinity too.

---
Tags: turing-machines
---


# Question
Title: Alternate definition of recursively enumerable languages
Exercise 9.2.3(c) of the book by Hoffman, Motwani, Ullman states

> In fact a definition of the RE-but-not-recursive languages is that they can be enumerated but not in numerical order

How do we show this equivalent to the following definition? RE-but-not-recursive languages are those, that are accepted by a TM, but do not halt on at least one input.

My take:
If enumeration in order is possible, then it is implied (?) that the TM halts on all inputs. So, it is recursive.

I am not sure on how to show the "it is implied" part in the above statement.

# Answer
A language $L$ is recursively enumerable but not recursive if:

1. There is a Turing machine that halts on an input $x$ if and only if $x \in L$.
2. There is no Turing machine that on $x \in L$ halts and prints Yes, and on $x \notin L$ halts and prints No. We say that such a machine *decides* $L$.

In order to show that this is equivalent to "can be enumerated but not in numerical order", it suffices to prove that a language is recursive iff it can be enumerated in numerical order (since we already know, presumably, that a language is recursively enumerable iff it can be enumerated).

If a language is recursive then it can be enumerated in numerical order: just go over all inputs in order, and for each one, determine if it belongs to the language, and if so, add it to the enumeration.

The crux of the proof of Exercise 9.2.3(c) is the opposite direction: if a language can be enumerated in numerical order then it is recursive. This means that if there is a Turing machine that enumerates $L$ in numerical order, then there is a (possibly different) Turing machines that decides $L$.

Enumerators and deciders are different types of beasts:

* An enumerator has no input, and generates a (possibly infinite) output.
* A decider gets an input, and outputs either Yes or No.

In particular, an enumerator will usually not be a decider. Therefore your proof strategy, as stated, cannot work. Instead, you need to show how to construct a decider using an enumerator.
> 2 votes

# Answer
If a language $L$ can be enumerated in numerical order, that means that you can construct an algorithm that enumerates positive instances in numerical order, for example $1, 5, 9, 129, 238, 387846, …$.

If that's the case, then $L$ is recursive. Indeed, to solve any instance $x$, you just have to enumerate positives instances of $L$ until a number is greater or equal than $x$. If this number is equal to $x$, then $x$ is a positive instance, otherwise $x$ is a negative instance.

Conversely, if $L$ is recursive, then there exists an algorithm $A$ solving $L$, and then you can enumerate all positive instances in numerical order:

```
n ← 0
while true:
   if A(n):
      print(n)
   n ← n + 1

```
> 0 votes

---
Tags: definitions, recursively-enumerable
---


# Question
Title: How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?
As shown in this post @ stackoverflow, ANTLR4 *seems* able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "`'if' expr 'then' stat`" alternative to "`'if' expr 'then' stat 'else' stat`". But I have some difficulty

```
stat : 'if' expr 'then' stat
     | 'if' expr 'then' stat 'else' stat
     | expr
     ;

```

Is this the correct way to resolve this ambiguity using ANTLR4? If so, how to prove that this "priority" works for all valid if/then/else statements?

# Answer
ANTLR4 matches grammar alternatives against the input in the order you specify them. That production says (assuming "else" cannot be parsed as an *expr*) to bind the `else` to the most recent `if` \- parsing this:

```
if a=b then if c=d then something else some_other_thing

```

as

```
if a=b then {
   if c=d then {
      something
   } else {
      some_other_thing
   }
}

```

If you want the opposite behavior - binding the `else` to the earliest possible `if` \- then reverse the order of the first two alternatives.
> 0 votes

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


# Question
Title: Number of inputs in undecidability proof of halting problem
So first, just to make sure that I understand the proof, here is the proof as I understand it:

Take a program $H(x,y)$, which determines whether $x(y)$ will halt or not halt: if $x(y)$ halts then $H$ returns true, and otherwise it returns false. If $H$ exists, we can construct a new program $H'$ which has one input $x$, defined by $H'(x) = H(x,x)$. Using $H'$ we create a final function $H^+$, which loops forever if $H'$ returns true, and halts otherwise.

With this information, we can feed $H^+$ into itself — $H^+(H^+)$. If the inside halts, then the outside must loop, but due to the definition of $H'$, $H^+(H^+)$ is the same as $H^+(H^+,H^+)$. The outside is the same as the inside, and so must halt. This is a contradiction, so $H(x,y)$ cannot exist.

The thing I find confusing about this, is that it assumes that the interior $H^+$ is the same as the exterior $H^+$, whereas to me it seems that they would be different by virtue of one being the input to the other.

Another question is what is the input for the interior $H^+$? by un-nesting the $H^+$’s, and unrolling the definition of $H'$, we get $H^+(H^+,H^+)$, then $H^+(H^+(H^+))$, then $H^+(H^+(H^+(H^+)))$, and so on, so what is the first input? If there is no input then the question of whether $H^+(H^+)$ halts, that is, whether $H^+$ halts with input $H^+$, makes no sense for the same reason that the question what is the number answer to $x^2$ doesn't make sense – the function requires an input and if the input is just a function, you are asking if a function halts without knowing the input. An example of this is $H^+(x)$, where $x$ is

```
If input = 1
    Halt
Else
    Loop

```

Will this program halt? The answer is obviously that it depends on the input, so why is it not the same with the function $H^+(H^+)$?

# Answer
> 1 votes
First of all, Turing machines have no input specification per se. They have an "input convention" which allows us to interpret them as accepting inputs. However, this makes little difference for the argument, so below I will assume that Turing machines do have a specified number of inputs.

The starting assumption is that there is a two-input Turing machine $H(x,y)$ which return whether the one-input Turing machine encoded by $x$ halts on the input $y$. From it, we construct a one-input Turing machine $H'(x)$ which computes $H(x,x)$. Finally, we construct a one-input Turing machine $H^+(x)$ which computes $H'(x)$, enters an infinite loop if $H'$ returned true, and halts otherwise.

We then consider what happens whether $H^+$ halts when run on $\\# H^+$, which is the encoding of $H^+$. There are two possibilities:

1. Suppose that $H^+$ halts when run on $\\# H^+$. Then $H'(\\#H^+) = H(\\#H^+,\\#H^+)=\text{True}$, and so $H^+$ enters an infinite loop when run on $\\#H^+$, contradiction.
2. Suppose that $H^+$ does not halt when run on $\\# H^+$. Then $H'(\\#H^+) = H(\\#H^+,\\#H^+)=\text{False}$, and so $H^+$ halts when run on $\\#H^+$, contradiction.

In both cases we reach a contradiction, and so we conclude that $H$ cannot exist.

# Answer
> 0 votes
Let H (x, y) be a Turing machine that returns true if the Turing machine with encoding x halts on input y, and returns false if that machine doesn't halt on input y. If H (x, y) exists then the halting problem is solved. If H (x, y) doesn't exist then the halting problem cannot be solved.

H' (x) returns true if the Turing machine with encoding x halts on input x, and returns false if the machine doesn't halt on input x.

$H^+$ (x) loops forever if the Turing machine with encoding x halts on input x, and halts if the machine doesn't halt on input x.

Let #$H^+$ be the encoding of the Turing machine $H+$. We try what happens if we use #$H^+$ as the x in the previous part: $H^+$ (#$H^+$) loops forever if the Turing machine with encoding #$H^+$ halts on input #$H^+$, and halts if the machine doesn't halt on input #$H^+$.

In other words, $H^+$ (#$H^+$) loops forever if $H^+$ halts on input #$H^+$, and halts if $H^+$ loops forever on input #$H^+$. $H^+$ (#$H^+$) loops forever if $H^+$ (#$H^+$) halts, and $H^+$ (#$H^+$) halts if $H^+$ (#$H^+$) loops forever.

In the last line, we had one calculation which loops forever if it halts, and halts if it loops forever. That's not possible. Therefore H doesn't exist.

---
Tags: halting-problem
---


title: Reversible hash function (?)

text:
# Question
Title: Reversible hash function (?)
I am looking at a problem where I have an assembly/collection of items, `V`, and my goal is to issue an `ID` to this collection, such that:

1. this `ID` uniquely identifies `V`, aka a change in `V` results in a change in the `ID` of `V` (much like a hash function),
2. given `V`, I can generate the `ID` and,
3. given the `ID` I can work out which items are in the collection (what the corresponding `V` looks like)

Is there a good way to do this apart from the obvious one1? Am I practically looking for a reversible hash function?

*1. by obvious I mean like an enumeration of sorts, not sure what it is formally called; like a 1 in the thousands means X, a 2 means Y and so on*

---

**Example**

Imaging running a supermarket and wanting to assign an `ID` to the receipts (`V`) you issue based on the items that were purchased. Your input is a collection of serial numbers that represent the purchased products. This `ID` is generated at check-out and printed on the receipt. The customer could then, by providing only this one `ID` communicate to you the entire list of purchased items since you can then decode the `ID` they provided.

*This is just a silly example aimed at helping you understand my end goal and has nothing to do with the application I am working on*

# Answer
There are three interesting cases:

* The keys to be stored in the hash table are known in advance. In this case, it is possible to construct a hash function that is injective over the set of stored keys; this is, essentially, perfect hashing. Perfect hashing doesn't give you a direct way to reconstruct the key from the hash value, but at least it's possible in principle.
* The set of possible queries to be performed on the hash table is known in advance. This is, if you like, the converse of perfect hashing, but instead of building a hash function that is surjective over the *stored* keys, you build one that is surjective over the *queried* keys. I don't know if this has a standard name, but the ideas (and the construction algorithms) are the same.
* The set of all possible keys is finite and has the same (or lesser) cardinality as the codomain of the hash function. If it's the same, you can in principle construct a hash function that is *bijective*, or a permutation of the key space.

An important example of this third case is hashing fixed-length bit strings (e.g. integers, pointers, network addresses, fixed-length DNA sequences). What's interesting about this is that any cryptographic block cipher is a hash function! But even if you don't need cryptographic-level security, using a Feistel network is a popular choice for building hash functions of this type.

If the set of possible keys is unbounded (e.g. strings) but the set of possible hash values is not, then it's clearly not possible to have an invertible hash function.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Asked to write a regular expression for a language but I am confused about the teachers given solution. (all strings NOT ending in 01)
The problem reads as follows:

Write a regular expression for the following language on {0, 1}:

$\bullet$ all strings not ending in 01.

The solution my teacher gave is

(0+1)$^{\*}$(00+10+11)+0+1+$\lambda$

So if I understand this correctly I could produce a string like

0001 right? Which ends in 01 which is what we DON'T want.

Can someone please explain if I've misunderstood or if the solution is actually incorrect.

Edit: Fixed the teacher's given solution so that it is accurate/correct but still looking for an explanation as to why it is correct.

# Answer
> 0 votes
It is more likely that the solution is $\underbrace{(0+1)^\*(00+10+11)}\_{\text{words of two or more letters not ending with }01} + \underbrace{0 + 1 + \lambda}\_{\text{words of 0 or 1 letter}}$.

Notice that the $(00 + 01 + 11)$ part has been transformed into $(00 + 10+11)$. Also the Kleene star on the last $1$ is useless (since a word $1^k$ with $k\geqslant 2$ can be obtained with the first part).

---
Tags: regular-expressions
---


# Question
Title: λ -calculus : What is the most efficient in memory representation of functions?
I would like to compare performance of function encoded (Church's / Scott's) vs classically encoded (assembler / C) data structures.

But before I do that I need to know how efficient is / can be function representation in memory. The function can be of course partially applied (aka closure).

I am interested in both the current encoding algorithm popular functional languages (Haskell, ML) use **and also** in the most efficient one that can be achieved.

---

Bonus point : Is there such encoding that maps function encoded integers to native integers (`short`, `int` etc in C). Is it even possible?

---

I value efficiency based on performance. In other words the more efficient the encoding is the less it influences performance of computation with functional data structures.

# Answer
The thing is, there's really not much leeway in terms of function encoding. Here are the main options:

* Term rewriting: you store functions as their abstract syntax trees (or some encoding thereof. When you call a function, you manually traverse the syntax tree to replace its parameters with the argument. This is easy, but terribly inefficient in terms of time and space.
* Closures: you have some way of representing a function, maybe a syntax tree, more likely machine code. And in these functions, you refer to your arguments by reference in some way. It could be a pointer-offset, it could be an integer or De Bruijn index, it could be a name. Then you represent a function as a *closure*: the function "instructions" (tree, code, etc.) paired with a data structure containing all free variables of the function. When a function is actually applied, it somehow knows how to look up the free variables in its data structure, using environments, pointer arithmetic, etc.

I'm sure there are other options, but these are the basic ones, and I suspect almost every other option will be a variant of or optimization of the basic closure structure.

So, in terms of performance, closures almost universally perform better than term rewriting. Of the variations, which is better? That depends heavily on your language and architecture, but I suspect the "machine-code with a struct containing free vars" is the most efficient. It has everything the function needs (instructions and values) and nothing more, and calling doesn't end up doing large term traversals.

> I am interested in both the current encoding algorithm popular functional languages (Haskell, ML) use

I'm not an expert, but I'm 99% most ML flavours use some variation of the closures I describe, albeit with some optimizations likely. See this for a (possibly out of date) perspective.

Haskell does something a bit more complicated because of lazy evaluation: it uses Spineless Tagless Graph Rewriting.

> and also in the most efficient one that can be achieved.

What is most efficient? There is no implementation that will be most efficient across all inputs, so you get implementations that are efficient on average, but each will excel in different scenarios. So there's no definite ranking of most or least efficient.

There's no magic here. To store a function, you *need* to store its free values somehow, otherwise you're encoding less information than the function itself has. Maybe you can optimize away some of the free values with partial evaluation but that's risky for performance, and you have to be careful to ensure that this always halts.

And, maybe you can use some sort of compression, or clever algorithm to gain space efficiency. But then you're either trading time for space, or you're in the situation where you've optimized for some cases and slowed down for others.

You can optimize for the common case, but what the common case *is* can change on the language, area of application, etc. The type of code that's fast for a video game (number crunching, tight loops with large input) is probably different than what's fast for a compiler (tree traversals, worklists, etc.).

> Bonus point : Is there such encoding that maps function encoded integers to native integers (short, int etc in C). Is it even possible?

No, this is not possible. The problem is that the lambda calculus does not let you introspect terms. When a function takes an argument with the same type as a Church-numeral, it needs to be able to call it, without examining the exact definition of that numeral. That's the thing with Church encodings: the *only* thing you can do with them is call them, and you can simulate everything useful with this, but not without a cost.

More importantly, the integers occupy every possible binary encoding. So if lambdas were represented as their integers, you'd have no way of representing non-church-numberal lambdas! Or, you'd introduce a flag to denote whether a lambda is a numeral or not, but then any efficiency you want is probably gone out the window.

EDIT: Since writing this, I've become aware of a third option for implementing higher-order functions: defunctionalization. Here, every function call turns into a big `switch` statement, depending on which lambda abstraction was given as the function. The tradeoff here is that it's a whole program transformation: you can't compile parts separately and then link together this way, since you need to have the complete set of lambda abstractions ahead of time.
> 12 votes

# Answer
**Bonus point**

You can map lambda functions to digits (as opposed to integers), which will speed up arithmetic *immensely*. Here is an example that implements base-16 arithmetic (it functions kind of like an odometer). Numbers are cons-lists of digits, least significant first. You can use a (much more verbose) base-256 version to map to byte values. I'm only providing support for adding. The other operations are left as an exercise for the reader.

It's handy if your LC interpreter / compiler maintains function identity like mine does (mine uses closures by default, which helps with this). The UI prints function names for known functions when "pretty" is checked.

You can compile and run this in my evaluator (I'll fix the SSL certificate soon) http://lambdamechanics.com/lcPresentation/evaluator.html by saving the source to a file, clicking "Choose File", and then clicking "Run" on example `ex3`, `ex4`, and/or `ex5`. Sorry for the rough UI, I haven't worked on this for quite a while.

Source:

```
# add hex numbers represented as lists of hex digits, least significant first

# booleans
t   = λa b . a
f   = λa b . b
and = λa b . a b f
or  = λa b . a t b

# Y combinator
Y = λg . (λx . g (x x)) λx . g (x x)
# use recursion
rec = λf . f (Y f)

#lists -- the evaluator pretty prints lists if these defs are present
cons    = λa b . λfun . fun a b
head    = λl . l λa b . a
tail    = λl . l λa b . b
nil     = λa b . b
null    = λl . l (λa b D . f) t
append  = rec λappend l1 l2 . l1 (λh t D . cons h (append t l2)) l2
reverse = λl . rec (λrev l res . l (λh t D . rev t (cons h res)) res) l nil

# hex digits. A number is a list of digits in least-significant-first order
0 = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . d0
1 = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . d1
2 = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . d2
3 = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . d3
4 = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . d4
5 = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . d5
6 = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . d6
7 = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . d7
8 = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . d8
9 = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . d9
A = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . dA
B = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . dB
C = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . dC
D = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . dD
E = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . dE
F = λd0 d1 d2 d3 d4 d5 d6 d7 d8 d9 dA dB dC dD dE dF . dF

is0 = λz . z t f f f f f f f f f f f f f f f
isF = λz . z f f f f f f f f f f f f f f f t

inc = λn . cons (n 1 2 3 4 5 6 7 8 9 A B C D E F 0) (is0 n)
dec = λn . cons (n F 0 1 2 3 4 5 6 7 8 9 A B C D E) (isF n)

# an addition table that returns the result plus overflow
#baseadd = λx y . x
#  (y (cons 0 f) (cons 1 f) (cons 2 f) (cons 3 f) (cons 4 f) (cons 5 f) (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f))
#  (y (cons 1 f) (cons 2 f) (cons 3 f) (cons 4 f) (cons 5 f) (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t))
#  (y (cons 2 f) (cons 3 f) (cons 4 f) (cons 5 f) (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t))
#  (y (cons 3 f) (cons 4 f) (cons 5 f) (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t))
#  (y (cons 4 f) (cons 5 f) (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t))
#  (y (cons 5 f) (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t))
#  (y (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t))
#  (y (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t))
#  (y (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t))
#  (y (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t))
#  (y (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t) (cons 9 t))
#  (y (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t) (cons 9 t) (cons A t))
#  (y (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t) (cons 9 t) (cons A t) (cons B t))
#  (y (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t) (cons 9 t) (cons A t) (cons B t) (cons C t))
#  (y (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t) (cons 9 t) (cons A t) (cons B t) (cons C t) (cons D t))
#  (y (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t) (cons 9 t) (cons A t) (cons B t) (cons C t) (cons D t) (cons E t))
#
# condensed form below:

baseadd = λx y . x (y (cons 0 f) (cons 1 f) (cons 2 f) (cons 3 f) (cons 4 f) (cons 5 f) (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f)) (y (cons 1 f) (cons 2 f) (cons 3 f) (cons 4 f) (cons 5 f) (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t)) (y (cons 2 f) (cons 3 f) (cons 4 f) (cons 5 f) (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t)) (y (cons 3 f) (cons 4 f) (cons 5 f) (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t)) (y (cons 4 f) (cons 5 f) (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t)) (y (cons 5 f) (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t)) (y (cons 6 f) (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t)) (y (cons 7 f) (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t)) (y (cons 8 f) (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t)) (y (cons 9 f) (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t)) (y (cons A f) (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t) (cons 9 t)) (y (cons B f) (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t) (cons 9 t) (cons A t)) (y (cons C f) (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t) (cons 9 t) (cons A t) (cons B t)) (y (cons D f) (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t) (cons 9 t) (cons A t) (cons B t) (cons C t)) (y (cons E f) (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t) (cons 9 t) (cons A t) (cons B t) (cons C t) (cons D t)) (y (cons F f) (cons 0 t) (cons 1 t) (cons 2 t) (cons 3 t) (cons 4 t) (cons 6 t) (cons 7 t) (cons 7 t) (cons 8 t) (cons 9 t) (cons A t) (cons B t) (cons C t) (cons D t) (cons E t))

fmt = λn . cons (head n) (cons (tail n) nil)
ex1 = fmt (baseadd 8 9)
ex2 = fmt (baseadd 3 4)

# add two numbers
#addc = rec λaddc a b ovf .
#  (null b)
#    ((null a)
#      # both are nil
#      nil
#      # only b is nil, reverse and recall
#      (addc b a ovf))
#    ((null a)
#      # only a is nil, account for overflow
#      (ovf
#        # overflow adds 1
#        ((baseadd (head b) 1)
#          # destructure result of baseadd
#          λdigit ovf2 .
#            ovf2
#              # secondary overflow adds 10, return [digit , 1]
#              (cons digit (cons 1 nil))
#              # no secondary overflow, return [digit]
#              (cons digit nil))
#        # no overflow, return b
#        b)
#      # neither a nor b is nil, optionally increment (head a) and add result to (head b)
#      ((ovf
#        # overflow, inc (head a)
#        (baseadd (head a) 1)
#        # no overflow, use (head a), f
#        (cons (head a) f))
#        # destructure result of optional inc
#        λnewA ovf1 .
#          (baseadd newA (head b))
#            # destructure result
#            λresult ovf2 .
#              (cons result (addc (tail a) (tail b) (or ovf1 ovf2)))))
#
# condensed form below:

addc = rec λaddc a b ovf . (null b) ((null a) nil (addc b a ovf)) ((null a) (ovf ((baseadd (head b) 1) λdigit ovf2 . ovf2 (cons digit (cons 1 nil)) (cons digit nil)) b) ((ovf (baseadd (head a) 1) (cons (head a) f)) λnewA ovf1 . (baseadd newA (head b)) λresult ovf2 . (cons result (addc (tail a) (tail b) (or ovf1 ovf2)))))

add = λa b . addc a b f

# friendlier reversed add for more human-redable input/output
# this lets you use (cons 1 (cons 0)) to represent 10.
radd = λa b . reverse (add (reverse a) (reverse b))

# 1 + 2
ex3   = radd (cons 1 nil) (cons 2 nil)

# 13 + 2
ex4   = radd (cons 1 (cons 3 nil)) (cons 2 nil)

# 1F + 2
ex5   = radd (cons 1 (cons F nil)) (cons 2 nil)

```
> 0 votes

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


title: Is GNFS quasi-polynomial-time?

text:
# Question
Title: Is GNFS quasi-polynomial-time?
Wikipedia states that the time complexity of the General Number Field Sieve (GNFS) is $$\exp\left( \left(\sqrt\[3\]{\frac{64}{9}} + o(1)\right)(\log N)^{\frac{1}{3}}(\log \log N)^{\frac{2}{3}}\right),$$ where $N$ is the number to be factored.

The same site also mentions that quasi-polynomial time is $$\mbox{QP} = \bigcup\_{c \in \mathbb{N}} \mbox{DTIME} \left(2^{\log^c n}\right),$$ where $n$ is the length of the input, in other words, $n=\log N$.

Now my question is whether GNFS is quasi-polynomial-time. It appears not, because of the existence of the $(\log N)^{1/3}$ exponent.

How about sub-exponential? Wikipedia says $$\text{SUBEXP}=\bigcap\_{\varepsilon\>0} \text{DTIME}\left(2^{n^\varepsilon}\right).$$ I think the answer is still negative, because $\varepsilon=1/3$ in this case and it can’t be smaller as the intersection requires.

So the running time is exponential. Am I right?

**Update**

In the table of contents of the book *Prime Numbers: A Computational Perspective*, NFS and Quadratic Sieve (QS) are both listed in Chapter 6 Subexponential Factoring Algorithms.

# Answer
Using the same variable $n$ to mean two different things in two places is confusing. In the context of your question, I think it is better to describe the running time of GNFS as $$\exp\left( (c+o(1)) \\, n^{\frac{1}{3}}(\log n)^{\frac{2}{3}}\right),$$ where $n$ is the number of bits in the number being factored, and $c$ is a constant.

With this formulation, it is clear that it is not in QP ($n^{1/3}$ is not in $O(\log^c n)$ for any $c$), and not in SUBEXP ($n^{1/3}$ is not in $O(n^{\varepsilon})$ when $0\<\varepsilon\<1/3$). Yet as Wikipedia explains, there are multiple different definitions of sub-exponential; by some of them, GNFS runs in sub-exponential time, and by others, it does not. See also Are there subexponential-time algorithms for NP-complete problems?.
> 2 votes

---
Tags: time-complexity, number-theory, factoring
---


title: Treewidth of a subdivision of a graph

text:
# Question
Title: Treewidth of a subdivision of a graph
Let $G$ be a graph and $G\_s$ its $s$-subdivision, i.e. the graph obtained from $G$ by subdividing each edge $s$ times.

Why is the treewidth of $G$ the same as the treewidth of $G\_s$?

(Subdividing an edge $s$ times means that we replace $e = (u,v)$ with a path from $u$ to $v$ of length $s+1$, i.e. $u, x\_1, x\_2, x\_3, ..., x\_s, v$.)

# Answer
> 2 votes
If $G$ is a forest, then clearly the statement is true.

Suppose that $G$ is not a forest, which means that its treewidth is at least 2. This means that we are allowed to construct bags of three vertices.

Let $e = uv$ be an edge in $G$ and construct $G'$ where we have the path $u, x\_1, x\_2, x\_3, v$ in the place of $e$. Let $\cal T$ be a tree decomposition of $G$ and let $B$ be any bag that contains $u$ and $v$ (such a bag must exist since $uv$ is an edge).

Add bags $B\_1, B\_2, B\_3$ connected as a path from $B$: $B, B\_1, B\_2, B\_3$.

The new bags are defined as follows:

* $B\_1 = \\{u, x\_1, v\\}$
* $B\_2 = \\{x\_1, x\_2, v\\}$
* $B\_3 = \\{x\_2, x\_3, v\\}$

It can be confirmed that $\cal T'$ is indeed a valid tree decomposition of the graph $G'$, and the width of $\cal T'$ is the same as the width of $\cal T$.

---
Tags: treewidth
---


# Question
Title: Divide-and-Conquer Algorithms: What exactly is $a$ and $b$ here?
Chapter **2.3.2 Analysing divide-and-conquer algorithms** of *Introduction to Algorithms*, fourth edition, by CLRS, says the following:

> A recurrence for the running time of a divide-and-conquer algorithm falls out from the three steps of the basic method. As we did for insertion sort, let $T(n)$ be the worst-case running time on a problem of size $n$. If the problem size is small enough, say $n \< n\_0$ for some constant $n\_0 \> 0$, the straightforward solution takes constant time, which we write as $\Theta(1)$. Suppose that the division of the problem yields $a$ subproblems, each with size $n/b$, that is, $1/b$ the size of the original. For merge sort, both $a$ and $b$ are $2$, but we'll see other divide-and-conquer algorithms in which $a \not= b$. It takes $T(n/b)$ time to solve one subproblem of size $n/b$, and so it takes $aT(n/b)$ time to solve all $a$ of them. If it takes $D(n)$ time to divide the problem into subproblems and $C(n)$ time to combine the solutions to the subproblems into the solution to the original problem, we get the recurrence $$T(n) = \begin{cases} \Theta(1) & \text{if} \ n \< n\_0, \\ D(n) + aT(n / b) + C(n) & \text{otherwise} \end{cases}$$

What exactly is $a$ and $b$ here? Based on this description, it seems to me that $b$ might be the branching factor, and $a$ might be something like the depth, but I'm not really sure.

# Answer
In fact, $a$ is the branching factor (the number of subproblems) and $n/b$ means that each subproblem has size $n/b$.

For example, if you do matrix multiplication with a recurrence relation of $T(n) \leq 7T(n/2) + n$, then you branch into 7 subproblems, each of size half.

Meaning that at depth $j$ in the recursion, you have $a^j$ many subproblems, each of size $n/b^j$.
> 0 votes

---
Tags: algorithms, mergesort
---


# Question
Title: Complexity of right-to-left Knuth-Morris-Pratt algorithm
Suppose we modify the Knuth-Morris-Pratt string-matching algorithm to scan the pattern right-to-left a la Boyer-Moore, and consequently apply the shift rule on the right side of the cursor instead of the left side. The quantity $\text{sp}\_i(P)$ is now defined as the length of the longest proper prefix-suffix of $P\[i\dots n\]$ instead of $P\[1\dots i\]$. We also keep two extra indices $a,b$ to remember where the last shift occurred:

```
text |---------------------------------------------------|
                          <<<<<<<<<<<<<<< scan
    pattern |-------------|_α_|-----|_α_|
                          ^         |   |
                          fail      |   |
      shift >>>>>>>>> |-------------|_α_|-----|_α_|
                                    ^   ^
                                    a   b

```

So we may skip $P\[a,b\]$ during the next scan. Do we still achieve a linear time complexity? Can you provide a counter-example?

---

For context, I was trying to see the limitations of Knuth-Morris-Pratt when going right-to-left wrt. Boyer-Moore. I now realize that right-to-left Knuth-Morris-Pratt's shift rule ($\alpha$) can probably be seen as a weaker version of Boyer-Moore's good suffix rule ($\beta$):

```
                          <<<<<<<<<<<<<<< scan
    pattern |-------------|_α_|-----|_α_|
                          |______β______|
                |______β______|
                          ^
                          fail

```

So a better question would probably be whether Boyer-Moore without the bad character rule becomes linear if we keep two extra indices $a,b$:

```
text |---------------------------------------------------|
                          <<<<<<<<<<<<<<< scan
    pattern |-------------|______β______|
                |______β__|___|         |
                          ^             |
                          fail          |
      shift >>>>>>>>> |---|---------|___|__β______|
                          |______β______|
                          ^             ^
                          a             b

```

So we may again skip $P\[a,b\]$ during the next scan.

I understand this is getting somewhat confusing so I'll consider deleting the question altogether.

# Answer
Of course, thanks to symmetry, we still achieve a linear time complexity using the modified Knuth-Morris-Pratt algorithm.

In general, we can apply symmetries to lots of situations.

* For example, you could switch the source and the sink of a flow network with the direction of all edges reversed.
* For example, you can switch the source and destination in Dijkstra's algorithm, which might boost performance if the branching factor is smaller around the original destination.
* For example, instead of selecting the next interval with earliest ending time at each iteration on the problem of scheduling the most number of nonoverlapping intervals, you can also selecting the next interval with latest starting time at each iteration.
* Many more ...
> 1 votes

---
Tags: runtime-analysis, string-matching
---


title: Logical equivalence priority

text:
# Question
Title: Logical equivalence priority
I have the logical formula $$ A \Leftrightarrow B \Leftrightarrow C $$ In order to make the truth table I'm not sure wheither I should interpret it as $A \Leftrightarrow B \Leftrightarrow C$ or $A \Leftrightarrow (B \Leftrightarrow C)$

Here is my first truth table:

| $A$ | $B$ | $C$ | $A \Leftrightarrow B \Leftrightarrow C$ |
| --- | --- | --- | --- |
| 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 |

I interpret $A \Leftrightarrow B \Leftrightarrow C$ true when all three are truth or all three are false

Here is my second truth table:

| $A$ | $B$ | $C$ | $A \Leftrightarrow (B \Leftrightarrow C)$ |
| --- | --- | --- | --- |
| 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 |

So is either one of theses forms the right one or am i all wrong ?

# Answer
The symbol $\Leftrightarrow$ is generaly defined as a binary operator. That means that $A\Leftrightarrow B\Leftrightarrow C$ is not defined without a priority between both $\Leftrightarrow$'s.

However, since $A\Leftrightarrow (B\Leftrightarrow C)$ and $(A\Leftrightarrow B)\Leftrightarrow C$ have the same truth tables, you can consider either of them. Another way to say it is that $\Leftrightarrow$ is associative.
> 0 votes

# Answer
There is no meaning in $A \Leftrightarrow B \Leftrightarrow C$ seen as a ternary operator. (By the way, how did you compute that truth table ??)

After placing parenthesis, the expression can be understood as "one variable is true and the other two equal, or that variable is false and the other two different". In all cases, an odd number of ones makes a true.

As this property is invariant to a permutation of the variables, associativity holds.

---

You can check by induction that this generalizes to more variables, and an expression like

$$ A \Leftrightarrow B \Leftrightarrow C \Leftrightarrow\cdots Z $$

is associative and corresponds to the parity of the number of true.
> 0 votes

---
Tags: logic, arithmetic, propositional-logic, relational-calculus
---


# Question
Title: Is the combined set of halting and circle-free Turing machines recursively enumerable?
this question is related to this question but it's different

there are 3 kinds of TMs

1. a Halting TM on all inputs prints finitely many symbols on it's output tape and halts
2. a Circle-free TM on all inputs prints infinitely many symbols on it's output tape
3. a Crashy TM is neither Circle-free nor Halting (if a TM reject any input it's Crashy)

"the Crashy TMs" problem is to find a **Crashy TM** that computes the following function

$$ \begin{align\*} c(m) &= \begin{cases} 0 & \text{if $m$ is a Halting or Circle-free TM} \\ undefined & \text{if $m$ is a Crashy or invalid TM} \end{cases} \end{align\*} $$

I hope the implication of having a solution to this problem is obvious to everybody, it makes programming a lot more fun and easier

can you solve this problem?

it worth mentioning that there are 13 different kinds of Crashy TMs, I'm looking for a Hashi TM

1. a Crashi TM on all inputs after some times crash (stop moving the tape or tapes)
2. a Loopy TM on all inputs loops without printing infinitely many symbols on it's output tape
3. a Loopi TM is a Loopy TM that on some inputs crash
4. a Hashi TM is a Halting TM that on some inputs crash
5. ...

# Answer
Consider this version of the halting problem: given an input Turing machine $T$, decide whether $T$ halts on empty input. You can assume that $T$ is a valid description of a TM. This problem is known to be undecidable.

My answer in your other question, provides a way to build a Turing machine $T'$ from $T$ such that 1) $T'$is either halting or circle-free, and 2) $T'$ halts if and only if $T$ halts (on empty input). For the sake of keeping this answer self-contained, the idea of $T'$ is that of simulating $T$ while making sure that a new symbol (that will be treated as a blank for the sake of the simulation) is appended at the end of the tape after each step.

Construct a Turing machine $T''$ that ignores its input, simulates $T'$, and then (if the simulation ever ends) enters in a loop without printing any new symbol.

There are two cases:

* If $T$ halts (on empty input) then $T'$ also halts. Therefore $T''$ is crashy since it does not halt and only prints finitely many symbols, hence $c(T'')=1$.
* If $T$ does not halt, then $T'$ is circle-free and so is $T''$. Therefore $c(T'')=0$.

This means that $c(\cdot)$ is not computable, since it would allow us to decide whether $T$ halts (on empty input) and solve the above version of the halting problem.
> 0 votes

# Answer
Your question is similar to the previous one if you had pondered about it. I wonder if you paid attention to my last comment about Rice's theorem and my last sentences in the answer or not, but to help you I rewrite Rice's theorem statement from here (Also you can read about this theorem in almost all computability books):

> In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a syntactic property (for instance, does the program contain an if-then-else statement). A property is non-trivial if it is neither true for every partial computable function nor false for every partial computable function.

So simply by Rice's theorem the function $c(m)$ you have defined in this question and also the $k(m)$ you have defined in the previous question which tries to find the semantic behavior of Turing machine is uncomputable.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: What does h indicate in this diagram of avl trees?
Looking at the tree on the left it seems that the triangles represent leaves of the avl tree. To arrive at the balancing of -2 besides the node y the right subtree must have 2 nodes while the left subtree has a maximum of 4 nodes. Thus 2-4 = -2. However what does the h indicate?

# Answer
It is probably the height of the subtrees, i.e. the length of a longest path from the root to a leaf. Doing the balancing leaves us with a tree of height $h+2$ where we started with height $h+3$.
> 1 votes

---
Tags: avl-trees
---


# Question
Title: Relationship between the parameters tree width and the maximum degree
I am working on parameterized complexity and started exploring on various structural parameters. The problem I am working on is known to be W\[1\]-hard parameterized by treewidth of the input graph and I am wondering if there is any known relationship between treewidth and maximum degree of the input graph. Could anyone provide the information containing the relationship between all the structural parameters. TIA.

# Answer
> 6 votes
There are no direct relation.

* The $n$-star (vertices $\\{0,\dots,n\\}$ and edges $(0,i)$ for $i\>0$) has maximum degree $n$ and treewidth $1$.
* The $n \times n$-grid has maximal degree $4$ and treewidth $n$.

Granted, if your maximal degree is $2$ then the graph is a union of trees and cycles and hence has treewidth at most $2$. But starting from maximal degree $3$, you may have unbounded treewidth (for example, an expander of degree $3$ or the triangle grid).

What you have however is that for every $G = (V,E)$, $tw(G) \geq \min\\{deg(v)\mid v \in V\\}$. Indeed, let $T$ be a tree decomposition of $G$ of width $k$. We claim that there is a vertex of degree less than $k$ in $G$. For this, consider a leaf $l$ of $T$ and let $t$ be its father. If $B(l) \subseteq B(t)$, then you can remove $l$ from $T$ and still have a tree decomposition of $G$ of width $k$. Proceed until no more leaves of the tree decomposition can be removed.

Now you necessarily have a leaf $l$ such that $B(l) \not \subseteq B(t)$ where $t$ is the father of $l$. Hence, there exists $x \in B(l)$ that is not in $B(t)$. By connectivity, $x$ does not appear any other bag of $T$. Hence, every edges of $G$ having $x$ as an endpoint is covered in $B(l)$. In other words, $x$ has at most $k$ neighbors in $G$.

# Answer
> 4 votes
The parameters are independent. However, combining both parameters yield some interesting more restrictive parameters, where some hard problems become FPT.

First note that Graphs of bounded path width and bounded degree have bounded **cutwidth**. The other direction is clearly true, since both parameters are (up to a constant factor) a lower-bound for cutwidth.

There are a couple of generalizations of cutwidth that aim to avoid the restriction implied by the linear structure of the layout. The most prominent one is **tree-cut width**, which is more restrictive than treewidth (and hence, more problems are FPT parameterized by this parameter), but more general than $tw+d$, and hence, bounded when both are bounded.

However, in this case you might be more interested in **ede-treewidth**, since this parameter is bounded if and only if both treewidth and maximum degree are bounded in each biconnected component of the graph.

On a side note, another interesting generalization of cutwidth (that is also a restriction of treewidth) is the **edge-cut width**.

---
Tags: graphs, np-hard, parameterized-complexity
---


# Question
Title: Is there any Algorithm to check a vertex\node's partial order in terms of other vertices\nodes for a given graph?
For the given figure, let's consider vertex v3. For v3, v0 has a higher partial order,v1 & v2 has the same partial order, and v4 & v5 have lower order than v3, e.g., higher: {v0}, same: {v1,v2} and lower: {v4, v5}. I am looking for an algorithm to recognize these three sets. Is there any proven algorithm to find them?

\**Note: \** I have looked into topological sorting. However, it is hard to recognize these three set from topological sorting. This graph can have the following topological sorting:

v0 v1 v2 v3 v4 v5

v0 v1 v3 v2 v4 v5

v0 v1 v3 v4 v2 v5

v0 v3 v1 v2 v4 v5

v0 v3 v1 v4 v2 v5

Looking at all those topological sorts, you can see recognizing if v2 belongs to the same order as v3 or lower order than v3 would be tough, as v2 can appear both before and after v3.

I looked into DFS, BFS, and Kahn's algorithm. But I couldn't figure out if I could manipulate one of them to get my desired result. It seems like if I get a sort like the first one(v0 v1 v2 v3 v4 v5 ), I can get my desired set. However, given a random graph structure, I wonder can I generate a specific partial ordering to recognize those three sets?

# Answer
> 1 votes
I am assuming that you're graph $G$ is a DAG. Let $v$ be your reference vertex. Perform a DFS starting at $v$ to find all vertices reachable from $v$. These vertices must have a lower order from $v$. Then reverse the graph, and perform another DFS in this reversed graph starting at $v$. All vertices reachable from $v$ must have a higher order. Finally, all vertices that was not reached in both DFS must have the same order as $v$.

---
Tags: algorithms, graphs, partial-order, topological-ordering
---


# Question
Title: Determining class of language with pumping lemma?
I have the language $L = \\{ 0^{2l} 1^m | l,m \>= 0 \\} \ where \ \Sigma= \\{0,1\\} $ which I am trying to find the class of language for, e.g. not context-free, context-free, regular.

By this notion I assume $L$ is context-free and has some pumping length $p$, and I will use the pumping lemma.

$w = 0^{2p}1^p$ and can be split into $w = uv^ixy^iz, i \>= 0.$

$|w| \> p$

I know that $vxy$ can only be in 3 places as it is of length at most $p$, these scenarios are:

-all 0's

-A mix of 0's and 1's.

-All 1's.

My thinking is that scenario 1 is invalid as it must always be an even length, and pumping up may break this. Scenarios 2 I am unsure although I think it follows the same logic as the first scenario, and scenario 3 could be pumped and still be in the language.

Does this mean $L$ is context-free? Can I also infer if $L$ is regular?

# Answer
> 0 votes
Your language is regular. A regular expression is e.g. $(00)^\ast1^\ast$. The numbers $l$ and $m$ are not in any relation to each other. You just have an even number of $0$s followed by an arbitrary number of $1$s.

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


# Question
Title: Find the shortest path from a set of source points to the nearest source/destination point
I have a graph data structure that has some source points (the red ones) and some destination points (the blue ones). I want to find the shortest path from every source point to its nearest destination point, **or to its nearest source point that is already connected to a destination point by a shortest path**.

Please see the image below

I can find the shortest path from multiple sources to multiple destinations, but the problem is in the **bold** part above.

The output of the algorithm should be a list of shortest paths that satisfy the above criteria, plus that the sum of all paths length is minimum.

The sequence of the algorithm should be something like this:

1. Start by a source point, and find the shortest path to its nearest destination point.
2. Take another source point, and find the shortest path to either the nearest destination point or to the source point that has been connected in step 1.
3. Repeat step 2 until all source points are connected.

How can I do that? What is the name of this type of algorithm that can solve this problem?

# Answer
You can solve this in three stages, using a shortest-path algorithm followed by a minimum spanning arborescence algorithm.

Notation: Let $G$ be the original graph, with one vertex per point and the weight of each edge is the length of the path between those edges. Let $d(u,v)$ denote the length of the shortest path from $u$ to $v$ in $G$. The algorithm is as follows:

* Stage 1: form a new directed graph $G'$, with one vertex per source vertex from $G$, plus one more vertex $r$. For each pair of sources $s\_1,s\_2$ from $G$, add to $G'$ an edge $s\_2 \to s\_1$ with weight $d(s\_1,s\_2)$. Also, for each source $s$, add an edge $r \to s$ with weight $\min\_v d(s,v)$ where $v$ ranges over all destinations. Note that all of these distances can be computed using an appropriate shortest-path algorithm: e.g., by running Dijkstra's algorithm once per source.
* Stage 2: find a minimum spanning arborescence for $G'$, with $r$ as the root. This can be done using Edmonds' algorithm, or more modern optimized versions of it.
* Stage 3: do a pre-order traversal of the arborescence. Convert each edge $u \to v$ in the arborescence into the corresponding shortest path $v \leadsto u$ in $G$. Output these paths in the order given by the pre-order traversal.

The result of these three stages gives an optimal solution to your problem. The total running time is $O(|V| |E| + |V|^2 \log |V|)$, if you use Dijkstra's algorithm and Edmonds' algorithm in stages 1 and 2 respectively.
> 2 votes

# Answer
This problem can be solved by minimum spanning tree (in time $O(n\log n + m)$).

Let $S$ be the set of sources and $T$ the set of destinations. Start by adding a vertex $u$ and make it adjacent to all destination vertices (with zero weight). Compute a minimum spanning tree of the resulting graph. You can choose the tree such that all edges between $u$ and $T$ are chosen (assuming no negative weights). We claim that by removing the edges between $u$ and $T$ we get an optimal solution of your problem.

Clearly in an optimal MST, each source vertex will have a path to $u$ that goes through some vertex of $T$. Hence, is a valid solution for your problem. On the other hand, given an optimal solution to your problem, clearly, no two paths overlap, since we can cut the overlapping part of some path and connect a source of one path to an endpoint of the other path. We also assume that no two destinations are connected in this solution, since we can remove an edge of the maximum height in the corresponding connected component getting a better solution. So by adding the vertex $u$ and packing all edges incident to it, we get a minimum spanning tree of the resulting graphs.
> 0 votes

---
Tags: graph-traversal
---


# Question
Title: If the heuristic $h(n)$ is the estimated cost from node $n$ to the goal, then why would we want a heuristic that has a greater cost?
I am currently studying the concept of **heuristics** in search algorithms. I recently asked this question about the so-called "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$, and how it is useful. The user Pål GD commented with the following:

> The heuristic will be monotone, and furthermore the higher value (as long as it's admissible) the better. Meaning that if the heuristic value $(f + g)$ actually drops from one node to the next, we can just keep the higher value.

Furthermore, I am told the following:

> We say that $h\_2$ dominates $h\_1$ iff they are both admissible, and $h\_2(n) \ge h\_1(n)$, for all nodes $n$.
>
> * i.e., $h^\*(n) \ge h\_2(n) \ge h\_1(n)$
>
> If $h\_2$ dominates $h\_1$, then $A^\*$ with $h\_2$ will usually visit fewer nodes than $A^\*$ with $h\_1$.
>
> The "proof" is obvious:
>
> * $A^\*$ visits all nodes $n$ with $f(n) \< f^\*$.
> * i.e., it visits all nodes with $h(n) \< f^\* - g(n)$.
> * $f^\*$ and $g(n)$ are fixed. So if $h(n)$ is bigger, $n$ is less likely to be below-the-line.

$g(n) =$ ***actual** cost from start to $n$*.
$h(n) =$ ***estimated** cost from $n$ to goal*.
$f(n) =$ *estimated total cost from start to goal **via n***.
$f^\*$ is the actual cost of the optimal solution.

After studying this, and especially the proof, and then reading Pål GD's comment, it is clear to me that I am not understanding the concept of heuristics.

Clearly, the concept of a *dominant* heuristic says that the greater heuristic is "superior." And then, in the proof, it says that, since $f^\*$ and $g(n)$ are fixed, for $h(n) \< f^\* - g(n)$, if $h(n)$ is bigger, then $n$ is less likely to be "below-the-line." But none of this makes sense to me. If the heuristic $h(n)$ is the estimated cost from node $n$ to the goal, then **why would we want a heuristic that has a *greater* cost**? For search problems, aren't we looking for the *lowest* cost path to the goal? And **why would the heuristic that has the *greater* cost be more likely to visit fewer nodes**? Doesn't the fact that it has a *greater* cost mean that it has taken a more unfavourable path to the goal, thereby leading to greater cost? It seems to me that this misunderstanding is at the core of why I wasn't understanding the usefulness of the "pathmax modification."

# Answer
Remember that the heuristic is always *under-estimating* the cost from a node to the target, which means that a higher cost (closer to the true value) is always a more accurate cost.

For example, suppose that your landscape is a grid (like Manhattan) with some potential road-blocks. Then you can let the heuristic for node $n$ to the target $t$ be the $\ell\_2$ distance, i.e. $$h\_2(n) = \sqrt{ (n\_x - t\_x)^2 + (n\_y - t\_y)^2},$$ but a better heuristic would be the $\ell\_1$ distance (the Manhattan distance), i.e. $h\_1(n) = (n\_x - t\_x) + (n\_y - t\_y)$.

Notice that $h\_1$ is always at least as high as $h\_2$, both are under-estimating, which means that $h\_1$ is a more accurate cost.
> 1 votes

---
Tags: algorithms, search-algorithms, heuristics
---


title: Tractability w.r.t. multiple parameters

text:
# Question
Title: Tractability w.r.t. multiple parameters
I am working on the decision version of an NP-complete problem. The problem is known to be fixed parameter tractable(FPT) with respect to the solution size $k$ as the parameter.

If I consider another parameter (e.g. $p$), then which among the two following statements holds true?

1. if $p \leq f(k)$, since the problem is FPT with respect to $k$ it will also be FPT with respect to to $p$.
2. if $k \leq f(p)$, since the problem is FPT with respect to $k$ it will also be FPT with respect to to $p$.

And another query is that, if a problem is FPT with respect to $m$, then it is also known to be FPT with respect to $n$, given that $m \leq n$. Can someone elaborate on the reason behind this. For example, any problem known to be FPT w.r.t the parameter Treewidth is also FPT w.r.t to another parameter Vertex cover as Treewidth $\leq$ Vertex cover?

# Answer
Generally, **if**

1. you can solve a problem in time $f(k) \cdot n^{O(1)}$, for a monotone $f$,
2. and you know that $g(p) \geq k$

**then** certainly you can solve the problem in time $f(g(p)) \cdot n^{O(1)}$.

If $\text{VC} \geq \text{TW}$ and you can solve a problem in time $f(\text{TW}) \cdot n^{O(1)}$ time, then clearly you can solve the problem in time $f(\text{VC}) \cdot n^{O(1)}$ time, since this is just more time available.
> 1 votes

---
Tags: np-hard, parameterized-complexity
---


# Question
Title: Finding all "basic" cycles in an undirected graph?
Say you have a graph like

```
a — b — c
|   |   |
e — f — g

```

and you would like to find the cycles c1, {a,b,f,e}, and c2, {b, c, g, f}, but not c3, {a, b, c, g, f, e}, because c3 is not "basic" in the sense that c3 = c1 + c2 where the plus operator means to join two cycles along some edge *e* and then drop *e* from the graph.

I invented my own terminology in the above but basically I want to find all cycles in a graph that cannot be decomposed into smaller cycles. Does this problem have a name? Is there a known best algorithm for solving it?

I understand that enumerating *all* cycles runs in exponential time because there may be an exponential number of cycles but my intuition is that the number of basic cycles as defined above is related only polynomially to the number of edges in the graph.

# Answer
You might be interested in a cycle basis, especially a fundamental cycle basis (which actually consists of cycles).
> 5 votes

# Answer
Suppose that ${a}={1}$, ${b}=2$, ${c}=3$, ${e}=4$, ${f}=5$, ${g}=6$ $\implies$ we will have:

```
a — b — c       1 — 2 — 3
|   |   |  <=>  |   |   |
e — f — g       4 — 5 — 6

```

I can provide a solution of this problem, based on using of the algorithm **Depth first search:**

```
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int maximumSize=40;
vector<vector<int>> visited(maximumSize, vector<int>(maximumSize, 0));
vector<int> graph[maximumSize], closedContour, temporary;
int vertices, edges;
set<vector<int>> contours;
void showContentSetVector(set<vector<int>> input)
{
    for(auto iterator=input.begin(); iterator!=input.end(); ++iterator)
    {
        for(auto item : *iterator)
        {
            cout<<item<<", ";
        }
        cout<<endl;
    }
    return;
}
bool compare(int i,int j)
{
    return (i<j);
}
void createGraph()
{
    cin>>vertices>>edges;
    int vertex0, vertex1;
    for(int i=1; i<=edges; ++i)
    {
        cin>>vertex0>>vertex1;
        graph[vertex0].push_back(vertex1);
        graph[vertex1].push_back(vertex0);
    }
    return;
}
void depthFirstSearch(int initial, int current, int previous)
{
    if(visited[initial][current]==1)
    {
        for(int i=0; i<temporary.size(); ++i)
        {
            if(temporary[i]==current)
            {
                for(int j=i; j<temporary.size(); ++j)
                {
                    closedContour.push_back(temporary[j]);
                }
            }
        }
        sort(closedContour.begin(), closedContour.end(), compare);
        contours.insert(closedContour);
        closedContour.clear();
        return;
    }
    visited[initial][current]=1;
    temporary.push_back(current);
    for(int next : graph[current])
    {
        if(next==previous)
        {
            continue;
        }
        depthFirstSearch(initial, next, current);
    }
    temporary.pop_back();
    return;
}
void solve()
{
    createGraph();
    for(int vertex=1; vertex<=vertices; ++vertex)
    {
        temporary.clear();
        depthFirstSearch(vertex, vertex, -1);
    }
    cout<<"contours <- ";
    showContentSetVector(contours);
    return;
}
int main()
{
    solve();
    return 0;
}

```

Here is the result:

```
contours <-
1: 1, 2, 3, 4, 5, 6,
2: 1, 2, 4, 5,
3: 2, 3, 5, 6,

```
> 0 votes

# Answer
I suggest you take a look at the concepts of "Cycle Basis" and "Minimum Cycle Basis". Each is described in simple terms by NetworkX's documentation as below:

**Cycle Basis.** A basis for cycles of a network is a minimal collection of cycles such that any cycle in the network can be written as a sum of cycles in the basis.

**Minimum Cycle Basis.** Cycle basis for which the total weight (length for unweighted graphs) of all the cycles is minimum.

In order to be able to distinguish between the two quickly, assume that you have a undirected graph $G$ like below:

```
 A - B - C - D
 |   |   |   |
 E - F - G - H
 |   |   |   |
 H - I - J - K

```

Just trying to extract the cycle basis may lead to any of the results below, as both cases form a basis for the cycle space of $G$:

```
 1: A, B, F, E     |     1: A, B, F, E
 2: B, C, G, F     |     2: B, C, G, F
 3: C, D, G, H     |     3: C, D, G, H
 4: E, F, I, H     |     4: E, F, I, H
 5: F, G, J, I     |     5: I, J, K, H, D, C, B, F
 6: G, H, K, J     |     6: G, H, K, J

```

Based on your description, I assume your intention is to prevent cases such as cycle #5 of the right-hand side. To do so, you should rather extract *Minimum Cycle Basis* instead of *Cycle Basis*.

Here, are some references to delve deeper into the topic, if you are interested:

* Paton, K., 1969. An algorithm for finding a fundamental set of cycles of a graph. Communications of the ACM, 12(9), pp.514-518.
* Kavitha, T., Mehlhorn, K., Michail, D. and Paluch, K.E., AnO (m 2 n) Algorithm for Minimum Cycle Basis of Graphs.
> 0 votes

---
Tags: graphs
---


# Question
Title: How to prove that for any words $w_1, ..., w_n$ of alphabet $\{0,1\}$ regular expression $w_1^*w_2^*...w_n^*$ doesn't represent language $\{0,1\}^*$?
How to prove that for any words $w\_1, ..., w\_n$ on alphabet $\\{0,1\\}$ the regular expression $w\_1^\*w\_2^\*...w\_n^\*$ doesn't represent language $\\{0,1\\}^\*$?

# Answer
> 1 votes
Suppose there exist such $w\_1, ..., w\_n$ (without loss of generality all words have length more than $0$). There exist such $k$, that $2^k\>k^n$. There are $2^k$ words of length $k$ in language $\\{0,1\\}$ and not more than $k^n$ words of length $k$ in language represented by given regular expression.

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


# Question
Title: Understanding why this upper bound is tight
Consider an algorithm with the following recursion $$ T(n) \leq T(n/3) + T(2n/3) + \mathcal O(n)$$ for its running time. I understand that $T(n) = \mathcal O(n \log n)$ by drawing the recursion tree and seeing that every level takes time $n$, and that the depth of the tree is $\log\_{3/2} n$. But, why is this upper bound tight?

# Answer
What you write is tight in the sense that if you have no additional information than the recurrence you wrote, then you cannot hope to prove any better asymptotic upper bound.

To see this consider: $$ T'(n) = T'(n/3) + T'(2n/3 ) + n, $$ and notice that this could be the case in your recurrence.

The associate recursion tree will have at least $\Omega(\log\_3 n)$ full levels, and, since $\frac{n}{3} + \frac{2n}{3}= n$, the overall time spent on each of these levels is $n$. This shows that $T'(n) = \Omega(n \log n)$.

Notice however that there are choices of $T$ for which $O(n \log n)$ is not asymptotically tight. For example: $$ T''(n) = T''(n/3) + T''(2n/3) + 1, $$ which has solution $T''(n)=\Theta(n)$, or even just $T(n) = c$ for any positive constant $c$.
> 1 votes

---
Tags: algorithm-analysis, asymptotics, big-o-notation
---


title: Find a Global Sink in a graph

text:
# Question
Title: Find a Global Sink in a graph
There is a class exercise question asking about global sink in a directed graph. Finding normal sink is not difficult but the conditions of the question have made me stuck on this question.

> Let $G=(V,E)$ be a directed graph for which you have an adjacency list. A vertex $v$ is called a *global sink* if and only if it meets the following two conditions:
>
> 1. $v$ has no outgoing edges
> 2. for every vertex $u$, there is a path from $u$ to $v$

The question wants an algorithm that runs linearly. Can you please provide a hint? Thank you.

# Answer
There is a path from every vertex $u$ to some vertex $v$ in graph $G$ if and only if there is a path from $v$ to all vertices $u$ in the reversed graph $G^{R}$.
> 0 votes

---
Tags: graphs, depth-first-search
---


# Question
Title: What is the proper way to approach a competitive coding problem?
*\***Climbing Stairs Problem: https://leetcode.com/problems/climbing-stairs/*

**1) Take the **"\***Climbing Stairs" Problem** for instance:** If I was given a problem like this on a test after mastering "Fibbionacci Series" and "Factorial Implementation", I would not be able to solve it, despite the fact that "Climbing Stairs" problem boils down to "Fibbionacci Series"; I would not know that it resembles the Fibbionacci Series until I actually solve the first *6 OR MORE* instances of this problem, by hand (before recognizing the (Fibbionacci) pattern).

Problem with solving things manually: I personally think that for some problems (other than those, that are similar to the "Climbing Stairs" problem), it only feels like you have found a pattern, but in reality, that is the case only for the first couple instances; and as you continue to solve the following instances, you will realize that there is no pattern or it is a completely different pattern. **So, how is solving problems manually, by hand, to find patterns ideal?**

**2) Now, lets take the "Bubble Sort" Algorithm for instance**: In order to understand that *one iteration is not enough*, you have to manually solve it. How do you even get the idea of sorting things this way? I would never be able to come up with an idea like "Bubble Sort" on my own.

**So my question essentially is:**

1. How do you deal with situations where you are given a problem which you have never seen before?
2. To what extent does practice help? I thought that in Computer Science/FAANG people started refraining from giving students/interviewees "Tricky" programming questions where, once you get to know the solution (logic part), you go "ohhhh, I get it now".
3. In what situations is it ideal to manually solve instances (iterations) to find a pattern or to see if the logic actually works that way you think it works?
4. And in what situations is it ideal to let the computer solve everything? (For instance, in the "Climbing Stairs" problem: *letting the computer figure out everything* instead of *telling it the pattern that we found, like everyone else is doing on the leetcode platform*).

# Answer
> 1. How do you deal with situations where you are given a problem which you have never seen before?

You sit down with a pen and a paper and draw out examples and counter-examples. Then you recognize patterns. There are many algorithmic techniques that you can use or try first. Does greedy work? Does the problem have nice non-overlapping subproblems, does divide and conquer work? Does the problem have somewhat less nice overlapping subproblems, can you do dynamic programming on the subproblems? Is it a matching-type problem?

Furthermore, you have a bunch of algorithms available, such as

* linear search, binary search, sorting
* sliding window, prefix sum
* path finding (weighted, unweighted, with or without negative weights, with or without negative cycles)
* minimum spanning tree
* network flow
* brute force (subsets, permutations)

and also a bunch of data structures

* lists, stacks, queues,
* trees, graphs,
* tries
* segment trees, sqrt decomposition
* hash maps, hash sets, skip lists
* union-find

All of this, and more, you will learn in a couple of algorithms classes.

> 2. To what extent does practice help? I thought that in Computer Science/FAANG people started refraining from giving students/interviewees "Tricky" programming questions where, once you get to know the solution (logic part), you go "ohhhh, I get it now".

Practice helps a lot. If you want to learn, for example, dynamic programming, I believe that most students need to do tens if not hundreds of exercises on dynamic programming. Only then they *start seeing it*. When you *get* dynamic programming, very many problems go from impossible to doable.

> 3. In what situations is it ideal to manually solve instances (iterations) to find a pattern or to see if the logic actually works that way you think it works?

I'd say this is an integral part of solving a problem. The way you usually come up with algorithms is by coming up with a stupid idea, and then find an instance where it fails. Now you must ask yourself: why does it fail? Then you need to fix it.

Many, but not all, problems can be solved in this incremental manner, by coming up with a sequence of algorithms that solve larger and larger parts of the problem.

> 4. And in what situations is it ideal to let the computer solve everything? (For instance, in the "Climbing Stairs" problem: letting the computer figure out everything instead of telling it the pattern that we found, like everyone else is doing on the leetcode platform).

In the *climbing stairs* problem, an experienced algorithmician will immediately realize that the solution for $n$ *only depends on* the solution for $n-1$ and $n-2$, hence they will simply write down the equation $f(n) = f(n-1) + f(n-2)$. Most will immediately recognize this as Fibonacci, and then the actual algorithm is trivial, e.g.

```
def f(n):
    stairs = [1, 1]
    for i in range(2, n):
        stairs.append(stairs[i - 1] + stairs[i - 2])
    return stairs[-1]

```
> 4 votes

---
Tags: algorithms, data-structures, dynamic-programming
---


# Question
Title: Query on distance to parameter in parameterized complexity
I am a research scholar working in parameterized algorithms. For more information on parameterized complexity please refer to this. Recently, I have come across a problem which is known to be NP-complete on split graphs. Now, it has come to my attention that the problem will not be tractable parameterized by the parameter distance to split, which means that there is no FPT algorithm w.r.t the given parameter. Hence, the problem becomes hard in terms of parameterized complexity. I have got some intuition why it might be true, but couldn't convince myself completely. Can someone elaborate on why this must be true? TIA

# Answer
> 1 votes
This feels like homework, so I'll just give a hint.

Let $G$ be a split graph. What is the value of your parameter $d$ then? What is then the meaning of $f(d) \cdot n^{O(1)}$?

# Answer
> 1 votes
It is a common way to prove that a problem is para-NP-hard for some parameter by proving it is NP-hard on a class with constant value of the parameter. Indeed an $O(f(k)n^c)$ algorithm would imply an $O(f(c’)n^c)$ algorithm for this problem on the given class which is impossible assuming NP not equal P.

An example would be CLIQUE\[mimw\]. This problem is hard on H-graphs, which has constant mimw. That means it is para-NP-hard parameterized by mimw.

Note that the exsistence of an XP algorithm for a para-NP-hard problem is also excluded assuming NP is not equal to P.

---
Tags: np-hard, parameterized-complexity
---


# Question
Title: Directed graph of bank balances and transactions, how to process transactions?
I'm working on a game where there are several different entities represented by nodes. Each node has a starting balance, and directed edges show where money is owed from one account to another.

One problem I'm trying to figure out is which order to process transactions in, take this example below:

If you start by processing node 'B', because there is no balance, the \\$30 is not transferred to node C. Node A only receives \\$20 instead of \\$50, bringing the balance to \\$50. 'A' can't afford to pay both D and B, so depending on which is paid first the result is different. If D is paid first the balance goes up to \\$80. The remaining \\$20 goes to B. Then B also receives \\$80. The final graph is:

Is there an algorithm for solving situations like this? Is this related to network flow graphs or is that something different? I'm trying to figure out what problem class this is.

# Answer
Depending on your rules, here's a greedy algorithm:

Maintain a priority queue of all nodes where the value in the queue is *how many debts they are able to pay down*. Let the debt for each player be sorted by value.

Pop off a player $X$. If $X$ can pay, pop off the first debt. Then update the recipient's balance, and the number of debts they can pay off (binary search), and update the PQ. Then you push $X$ back onto the PQ with its updated count.

All in all, this should take $O(m \log m)$ time where $m$ is the number of debts.
> 2 votes

---
Tags: algorithms, graphs, directed-graphs
---


# Question
Title: Compute sum of moduli for a stream of integer numbers
We receive a stream of $n$ integer numbers: $x\_1, x\_2,\dots, x\_n$. Assume that each $x\_i$ is a constant and can be stored with $O(1)$ bits.

Whenever a new number $x\_i, i \geq 2$ is inputted, we need to evaluate and output the sum: $$ S\_i := \sum\_{j=1}^{i-1} |x\_i - x\_j|$$ After outputting it we receive $x\_{i+1}$ etc.

My question is: can we do this using no more than $O(\log n)$ memory per input/output? A solution using $O(\text{polylog}(n))$ memory per iteration would also be good enough for me.

**Observation**: Let's say we would have defined: $$ S\_i := \sum\_{j=1}^{i-1} (x\_i - x\_j)^2$$ instead. Then it's clear we can compute each new $S\_i$ using only $O(\log n)$ memory per input/output pair by always storing (and updating) the partial sums: $$s^1\_{i} := \sum\_{j=1}^{i-1} x\_j, \ \ s^2\_{i} := \sum\_{j=1}^{i-1} x^2\_j$$

and using the fact that: $$S\_i = n x^2\_i- 2x\_i s^1\_i + s^2\_i$$

The motivation behind this post is that I am wondering whether this can be done for the sum of moduli too.

# Answer
The function

$$\sum(x\_i-x)^2$$ is quadratic in $x$ and can be represented by a constant number of parameters. It has $3$ degrees of freedom.

But the function

$$\sum|x\_i-x|$$ is piecewise linear and requires the knowledge of all $x\_i$'s. It has $n$ degrees of freedom.

So the answer is negative.
> 2 votes

---
Tags: streaming-algorithm, summation, metrics
---


# Question
Title: What are the definitions of countable and measurable colourings of a graph?
In this paper, the author discusses colourings of the plane, or in other words, of the underlying graph. I suppose a finite colouring is a colouring using at most $k$ colours for some natural number $k$. However, what do countable and measurable colourings mean? Does the former perhaps mean that any vertex of the graph can get associated with a (potentially unbounded) natural number representing its colour? I have no clue what measurable colourings may be though.

# Answer
> 2 votes
A countable colouring of the plane $\mathbb{R}^2$ is just a function $c : \mathbb{R}^2 \to \mathbb{N}$, meaning we have countably many distinct colours available to us.

The notion of measurable colouring is a bit ambiguous, it could mean either Borel-measurable or Lebesgue-measurable. A colouring $c : \mathbb{R}^2 \to \mathbf{k}$ or $c : \mathbb{R}^2 \to \mathbb{N}$ is called Borel/Lebesgue-measurable, if each fibre $c^{-1}(n)$ is a Borel respectively Lebesgue-measurable subset of $\mathbb{R}^2$.

An example of a Borel-measurable colouring is taking finitely many lines in $\mathbb{R}^2$, and giving a distinct colour to each resulting component, while giving yet another colour to the lines itself.

Examples for non-Borel-measurable colouring will be weird. For example, take the Cantor middle third set $C$, and give everything in $\mathbb{R}^2 \setminus C \times \\{0\\}$ colour $0$. Identify each $x \in C \times \\{0\\}$ first with the corresponding $x' \in 2^\mathbb{N}$, and then view $x'$ as coding a tree $T\_x \subseteq \mathbb{N}^{\<\omega}$. Now colour $x$ by $1$ iff $T\_x$ is well-founded, and by $2$ otherwise.

# Answer
> 1 votes
I suppose those are mathematics terms (since the considered graph is infinite).

Countable means you can count those colorings with integers (there is a bijection with $\mathbb{N}$).

Measurable means you can quantify those with a certain notion.

---
Tags: graphs, counting, colorings, uncountability
---