# Question
Title: Hill climbing method searching special polynomial equations
I have system of two polynomial two variables, second order; monomials are {${1,x,y,x^2,xy,y^2}$} I want find special systems of polynomials: two or more roots in specified range, two root close to each other, roots on boundary search range, etc.
I can set one root to specified position by setting first term of polynomial (without x or y) to counterbalance all other terms. But this is only one root. How to search ?
IS 2\*6 parameters, two of them are first terms, next two can be not taken into account because polynomial * constants has the same roots.
Is 8-10 parameters, I try random parameter , change it to be best result (how?), next change parameter, search to best result, etc.. Changing one parameter need one dimensional search : or Brent method,Dekker method or Golden-Section search?

# Answer
If I understand correctly, you want to build two quadratic bivariate polynomials such that the roots of the system they form fulfill some predefined conditions.

Geometrically, this corresponds to the intersection of two conics, which generally come in fours. Consider four arbitrary point P, Q, R, S. They define two pairs of straight lines, let PQ, RS, PR and QS. Writing the implicit equations of two lines and forming their product, you obtain the implicit equation of a degenerate conic. Hence you can write the equation of two distinct conics by the four points.

Finally, form a linear combination of these two equations and you get a pencil of conics by these four points. Take any two members of the pencil.

E.g. let the points $(0, 0), (1,0), (0, 1)$ and $(2, 2)$. The pencil is

$$\lambda y(x-2y+2)+\mu x(y-2x+2)=0.$$

Three arbitrary members are

$$y-y^2+x+xy-x^2=0,$$ $$4x^2-xy-4x-2y^2+2y=0$$ and $$2y-2y^2+4x+3xy-4x^2=0$$.

Using this trick, you have total control on the placement of the roots.
> 3 votes

---
Tags: algorithms, optimization, search-algorithms, numerical-algorithms
---


title: Regular Language to Regular Expression

text:
# Question
Title: Regular Language to Regular Expression
Let's assume I have the following regular language:

L = {1,0}\*{010}{1,0}\*

I would like to convert this to regex for a program. Would the equivalent regular expression for this be:

((0+1)\*(010)(0+1)\*) or ((0+1)\*(010)(0+1)\*)\*

Or is it something else completely?

# Answer
> 1 votes
If I understand correctly, the language is $\\{0,1\\}^\* . \\{010\\} . \\{0,1\\}^\*$ (where $.$ is concatenation of languages). Then the first regular expression, i.e., $(0+1)^\*(010)(0+1)^\*$, is correct.

The second one describes different language. The iteration of the expression (i.e., the outer parentheses) would match the empty string, while language $L$ requires at least $010$.

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


# Question
Title: Is the reversal of a minimal DFA also minimal?
The question is pretty much in the title. Is there ever a time where some language $L$ can be accepted by a minimal DFA with $n$ states, but $L^R$, the reversal of $L$, can be accepted by a DFA with $m$ states, where $m\<n$?

# Answer
The minimal DFA accepting the reversal of the language can be smaller. Consider the finite language $$ L = (0+1)^22+(0+2)^21+(1+2)^20. $$ The words $\epsilon,0,1,2,00,01,02,11,12,22,000,001$ are inequivalent, so any DFA for $L$ requires at least 12 states; in fact there is a DFA with exactly 12 states. The reverse language $$ L^R = 2(0+1)^2 + 1(0+2)^2 + 0(1+2)^2 $$ is accepted by a DFA with only 9 states: an initial state, states corresponding to initial $0,1,2$, states corresponding to initial $0(1+2),1(0+2),2(0+1)$, an accepting state and a fail state; this is also the optimal DFA, since $\epsilon,0,1,2,01,12,20,011,000$ are inequivalent.

Summarizing, the minimal DFA for $L$ requires 12 states, while the one for $L^R$ requires only 9 states.

As jmite mentions in their comment, for NFAs with multiple starting states this phenomenon can't happen, since if you flip the direction of all arrows in a NFA for $L$ then you get a valid NFA for $L^R$.
> 7 votes

# Answer
The "standard" example that shows that the NFA to DFA construction is exponential in size also works for reversal.

The DFA for $\\{0,1\\}^\*1\\{0,1\\}^n$, the $n+1$-st symbol from the right is $1$, must have an exponential number of states as it has to recall all positions with $1$, whereas its reversal $\\{0,1\\}^n 1\\{0,1\\}^\*$ can be accepted with only a linear number of states, just counting to $n$.
> 3 votes

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


title: Is my DFA optimal?

text:
# Question
Title: Is my DFA optimal?
I designed this FSM graph to demonstrate a DFA that would accept any string that

* is of length 5,
* must contain a *d*,
* can only have *a*s and/or *b*s before the *d*, and
* can only have *b*s and/or *c*s after the *d*.

Here is what I came up with:

I was wondering if there is any way to improve the graph, by, for example, using fewer states?

# Answer
> 2 votes
Seems mimimal to me.

You can actually prove that the DFA is minimal by applying the Myhill-Nerode theorem. Two states $p$ and $q$ can not be merged if they can be "distinguished" in the sense that there is a string $w$ such that from exactly one on the two states $w$ leads to a final state. Here you can easily see that all states can be distinguished, and hence must be necessary.

Quick explanation: horizontally the states can be distinguished by their length, vertically by the letter $d$.

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


# Question
Title: Computer Vision algorithm to tell if camera is moving?
I'm looking for a computer vision algorithm or method that can tell if the camera is moving in a video. Or maybe an alternate way of telling if the background is moving. I have a lot of videos and only want to keep the ones where the camera is stationary.

All videos feature a person talking directly to the camera (the person is mostly stationary throughout the video). I want to keep videos where the camera is stationary, but there are a lot of videos where the person is holding the camera and walking or the camera is moving around too much

I plan to run some algorithm one by one on a collection of videos to determine which video IDs have a moving camera in them.

# Answer
> 4 votes
An approach that is fast and seems to work well for me, and does not involve any fancy stuff, is to use the correlation of pixels over time as an indicator of motion:

0. Make your video greyscale (lets call it `video` $\in \mathbb R^{T\times H\times W}$)
1. Spatially Highpass filter video to make `video_shp`
2. Temporally Lowpass the result to make `video_shp_tlp`
3. Sample some pixels in the video (e.g. 1000). Lets call these `indices` $\in \mathbb N^{2 \times N}$. Only do this on the first frame and reuse the sample-indices in subsequent frames.
4. Compute the correlation coefficient between the sampled pixels of the spatially-highpassed `video_shp` and the temporally-lowpassed `video_shp_tlp`: $\rho \in \[0, 1\] = corr($`video_shp[indices]`, `video_shp_tlp[indices]`)
5. Take your `motion_score` $\in \[0, 1\]$ to be $1-\rho$.

Results look like this:

Python Code:

```
@dataclass
class MovementDetector:
    seed: int = 1234
    n_samples: int = 1000
    decay_rate: float = 0.2
    spatial_highpass_filter_width: int = 10

    _ixs: Optional[NDArray] = None
    _lowpass_img: Optional[BGRImageArray] = None

    def get_moving_score(self, image: BGRImageArray) -> float:
        """ Takes the latest image, and outputs a score indicating the
        amount of recent motion.  Score in in [0, 1] interval,
        with 1 being lots of motion and 0 being None.
        """
        im_grey = image.mean(axis=2)
        im_grey_highpass = im_grey - cv2.boxFilter(im_grey, ddepth=None, ksize=(self.spatial_highpass_filter_width, self.spatial_highpass_filter_width))
        im_flat = im_grey_highpass.reshape(-1)
        if self._ixs is None:
            self._ixs = np.random.RandomState(self.seed).choice(len(im_flat), size=min(len(im_flat), self.n_samples), replace=False)
            if self._lowpass_img is None:
                self._lowpass_img = np.zeros_like(im_flat)
        historical_values = self._lowpass_img[self._ixs]
        current_values = im_flat[self._ixs]
        pixel_correlation = np.corrcoef(historical_values, current_values)
        self._lowpass_img = self.decay_rate * im_flat + (1 - self.decay_rate) * self._lowpass_img
        return 1 - pixel_correlation[0, 1]

```

# Answer
> 3 votes
Use background detection algorithm, say Gaussian Mixture-based background detection (present in OpenCv) and then make some assumption - say backround takes more than 60% of image.
Then convert frames to color model which keeps luminance as separate component. Compare consecutive frames with small tolerance per color per pixel and bigger tolerance per light (to take into account shadows). If your camera is not really stationary, check by movement algorithm if frame is shifted by some distance (camera may move slightly even if it stands still), in that case compare it with shifted frame after detecting shift.

Now gather frames with some tolerance, say 95% of frames match background in at least 60% of pixels with slight shifts (it depends on distance from camera to background).
If it matches, camera was still, if not then either parameters were too big or it was moving.
Adjust parameters, done.

# Answer
> 2 votes
This is an experimental area, so expect that you will need to try something, see how well it works, and then adjust to address error cases.

Here is a possible approach, that's a variation on what Evil suggests:

You could use optical flow on the video, to find the direction in which the pixels are moving. Use background detection to detect which pixels are part of the background.

Then if all (or most) of the non-background pixels in the image are moving, and all in basically the same direction (though not necessarily the same amount, as some objects may be near and some far), conclude that the camera is moving. Otherwise, conclude that the camera is still.

This is something you could evaluate, to see how often it gets the right answer, and for the cases that it's wrong, if there are commonalities to the failures.

# Answer
> 1 votes
For a simple solution, take the difference between pairs of successive frames. There will be a significant difference where there is motion.

When the person is moving, motion will be detected essentially in the middle of the screen. When the camera is moving, the whole frame will be affected.

Note that if the background is uniform, it will be impossible to differentiate between a moving person and a moving camera.

---
Tags: algorithms, computer-vision
---


# Question
Title: How to show that the following function $F$ is primitive recursive?
We want to show that the following function $F$ is primitive recursive (using the primitive recursion scheme) :

For all $x,p,a\in \mathbb N$,

$F(p,a,0)=g(\eta^{p}(a))$
$F(p,a,x+1)=h(\eta^{(p-(x+1))}(a),x,F(p,a,x))$

where $\eta, g : \mathbb{N}\to \mathbb{N}$ and $h: \mathbb{N}^3 \to \mathbb{N}$ are primitive recursive functions.

We want to apply the primitive recursion scheme which is defined as follows : if $g',h'$ are primitive recursive functions then the function $f$ defined by : $f(\bar y,0)=g'(\bar y)$ and $f(\bar y,x+1)=h'(\bar y,x,f(\bar y,x))$ is also primitive recursive.

Then I have to find the functions $f,g',h'$.

To build $g'$ let us consider that $\eta^{p}(a)=k(p,a)$ hence $g'(a,p)=g \circ k(p,a)$ which is a primitive recursive function by hypothesis.

To build $h'$ it seems that the difficulty is to get rid of the term in $\eta^{(p-(x+1))}(a)$ which depends of $x$ in particular. In fact we want $h'(p,a,x,F(p,a,x)) = h(-,-,-)$ but I am stuck. Any hints for this step would be very helpful

Thanks in advance !

# Answer
> 1 votes
Note that you can show that $k(p,a) = \eta^{p}(a)$ is primitive recursive. Also addition and subtraction are primitive recursive, thus definiing $h'(p,a,x,...) := h(k(p-(x+1),a),...) = h(\eta^{p-(x+1)}(a),...)$ is not a problem.

---
Tags: computability, primitive-recursion
---


# Question
Title: Time complexity of sorting binary natural numbers
In the comparison sort model of sorting, the fastest possible algorithm is order $n \log(n)$, where $n$ is the number of input numbers. What is the time complexity of sorting a list of natural numbers, each represented as a string of ones and zeros, and separated by commas? For example, the input $11,1,10$ would be sorted as $1,10,11$.

Here is a more precise definition of the function.

Consider the following function:

$f:S\to S$

where $S$ is the set of all finite strings over the alphabet containing three symbols, $0$, $1$ and 'comma', where $f$ is defined by interpreting each substring starting and ending in a comma as an integer. If such a substring starts with some zeros, ignore them. Then $f$ sorts these integers and returns a new string formed by representing each integer in the sorted list as a binary string and inserting commas between them. To further clarify the definition of $f$, here is a Python script which defines $f$.

```
def f(s):
    # if the input is not a string over the alphabet "01," then return an empty output
    if type(s) != str or False in [t in ['0','1',','] for t in s]: return ''
    # convert the string to a list of integers and sort it
    L = sorted([int(t,2) for t in s.split(',')])
    # convert back to a bit string separated by commas and return this
    return ','.join([f"{l:>b}" for l in L])

print(f('111,10,1,01111'))
# this outputs:
#   1,10,111,1111

```

Let $n$ denote the length of the input string, that is, the number of ones, zeros, and commas. I'd like to know the big omega time complexity of this function $f$ in terms of $n$. Please note that I do not mean to ask what the time complexity of the particular implementation of the function I defined above is, but rather the time complexity of the best possible implementation.

# Answer
Assuming there are $n$ numbers, and each number can be represented in $O(\log n)$ bits, you can read in the file and each number in $O(n \log n)$ time, then sort with any standard comparison-based sort algorithm, for a total running time of $O(n \log n)$.

If each number is $m$ bits long, and there are $n$ numbers, then it can take $O(nm)$ time just to read in the input, so if $m \gg \log n$, then there is no hope for a $O(n \log n)$ time algorithm. In such a case, a better measure of running time is to measure the running time in terms of the length of the input. Let $N=nm$ be the length of the input. Then it is easy to read in the input in $O(N)$ time, and then sort it using a comparison-based sort in $O(N \log N)$ time, for a total running time of $O(N \log N)$ time, where $N$ is the length of the input.
> 2 votes

# Answer
If there are N numbers, M is the number of bits in the longest number, and you have enough memory available to hold 2 copies of the data, a radix sort would be of linear order O(M×N).
> 2 votes

---
Tags: sorting
---


# Question
Title: Sort array of 3D points to maximize number of tetrahedra in the array
Let $P$ be a indexable set(array) of points in $\mathbb{R}^3$ s.t. $P = \\{p\_0,p\_1,p\_2,...,p\_n\\}, p\_i \in\mathbb{R}^3$.

I want to sort $P$ so that every 4 consecutive points forms a non-coplanar tetrahedra/3D-simplex/triangular pyramid (whatever you personally call it), I know there will be left over points, so I want to do this maximally, meaning I want to create the maximum number of tetrahedra from the set of points and have them back-to-back in the array as every 4 points. And any left-over points will be at the end of the array (after the tetrahedra) where I will have the starting index stored for those leftover points.

Does anyone know how to accomplish this? (and yes the tetrahedra can be arbitrary with no constraints, meaning they are allowed to intersect, but a point can only be used for a single tetrahedra)

(I know I can find a single simplex by first finding 2 points that are at a distance of $\epsilon$ away from each other (meaning I have 2 distinct points) then find a third point that is not colinear by using the orientation test (cross product not the zero vector of 2 vectors formed from the 3 points) then finding a fourth point by using the plane normal test (now that we have 3 points that form a plane we can create a vector from the plane to a new fourth point and compare the dot product of that point with the plane normal and if it is not zero then we have a valid simplex)). (Some thoughts on where to search is to see if this maximization problem has maybe a dual known minimization problem which I don't know what would be or to figure out if the naive algorithm of just grouping 4 points at a time until you can't anymore achieve the maximum or not).

# Answer
**Hint:**

The naive method will not work. Assume four points forming a non-degenerate tetrahedron plus four coplanar points and no other alignment. Grouping the first four results in a single tetrahedron, while two are otherwise possible.

A heuristic is to first form all possible groups of coplanar points (four or more), and empty the largest groups first (by mating three points to a point of another large group), but I doubt that this is optimal.
> 0 votes

---
Tags: algorithms, computational-geometry, simplex
---


# Question
Title: How do compression algorithms keep track of multiple files?
I noticed that when you compress data they can compress multiple files and since all files are made up of bytes how do these compression algorithms keep track of them? What seperators do they use?

From my understanding it goes like this, for example I have an array \[1,2,3\] and another array \[4,12,6\] and I store them in as a string "1234126" these algorithms can keep track of their original form so when you decompress it still goes "1234126" → "\[1,2,3\]","\[4,12,6\]" how do compression algorithms do these?

My only solution for these is not as efficient → \[1,2,3\] would be converted to `111213` so when I decompress I know the length of the number for example : 111213 → \[0\] = 1 so next number has length of 1 which is \[1\] = 1 and so on.. but I don't think this is efficient as it bloats data, and if it goes beyond **"9"** you'd need to add another number for example the word `"this is a data"` has a length of 14 so before I compress this it would be → `214this is a data` then proceed to compression which would be bloated. Is this how compression algorithms do stuff like this?

steps:

file1 has `this is a data from file1`, file2 has `this is a data from file2` → encode data from both files → `214this is a data from file1214this is a data from file2` → compress → result : `776^&676s` → decompress "776^&676s" → `214this is a data from file1214this is a data from file2` → decode → file1 has `this is a data from file1` and file2 has `this is a data from file2`

I hope this question isn't so confusing :)

# Answer
A simple method: You create an algorithm first that can translate a sequence of bytes into a compressed sequence, and can decompress the compressed sequence into the original file if the length is known.

Then let's say you have ten files: You get their filenames, and a compressed sequence for each file. The output file starts with an array describing the files: First filename, start and length of the first file, second filename, start and length of the second file, and so on, then you append the first compressed file, then the second compressed file, and so on.

If you want to decompress file xyz, you go through the table at the start of the compressed file, find the start and length of the file named xyz, and then you know what to decompress.

You can vary this slightly to make it possible to add, remove or change files without re-writing everything.
> 1 votes

# Answer
There are 2 options,

Zip archive format style, each file is compressed separately. There is a index at the end of the file (can also be at the start) that lists the metadata for each file and where the compressed block for each file exists.

The other option is the tarball style, first the set of files are combined into a non-compressed bytestream with separators and then that full bytestream is compressed.

Both options have their advantages and disadvantages. The zip style means that you can access each file without needing to touch anything other than the index and the block of compressed data for that file and each file can use a different compression algorithm (including none for compressed media formats). With the tarball you can get better compression overall when subsequent files have a similar format.
> 1 votes

---
Tags: data-compression
---


# Question
Title: Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?
I am reading an algorithm book.

Any comparison sort must make $\Omega(n\log(n))$ comparisons in the worst case to sort $n$ elements.

Can we create a decision tree for any comparison sorting algorithm even if it is very complicated for $n$?

# Answer
In general, a decision tree would enumerate all possible permutations $(N!)$ for given input of $N$ elements, out of which only $1$ would be desirable.

A sorting algorithm doesn't generate all possible permutations, it follows a set of predefined steps to reach the desired output. This would be equivalent to taking a path in the decision tree from the root to the leaf which represents the sorted permutation. And if you follow the algorithm, you will always follow the same path.
> 1 votes

# Answer
The procedure below can be used to explicitly build the decision tree of any comparison-based algorithm:

* generate all permutations of the array $\[1, 2, \cdots n\]$.
* for every permutation, run the algorithm and note the outcomes of every comparison, together with the involved element indexes.
* merge the traces so obtained, in the form of a tree.

Below all traces of InsertionSort on four elements:

```
1≥0 2≥1 3≥2
1≥0 2≥1 3<2 3≥1
1≥0 2≥1 3<2 3<1 3≥0
1≥0 2≥1 3<2 3<1 3<0
1≥0 2<1 2≥0 3≥2
1≥0 2<1 2≥0 3<2 3≥1
1≥0 2<1 2≥0 3<2 3<1 3≥0
1≥0 2<1 2≥0 3<2 3<1 3<0
1≥0 2<1 2<0 3≥2
1≥0 2<1 2<0 3<2 3≥1
1≥0 2<1 2<0 3<2 3<1 3≥0
1≥0 2<1 2<0 3<2 3<1 3<0
1<0 2≥1 3≥2
1<0 2≥1 3<2 3≥1
1<0 2≥1 3<2 3<1 3≥0
1<0 2≥1 3<2 3<1 3<0
1<0 2<1 2≥0 3≥2
1<0 2<1 2≥0 3<2 3≥1
1<0 2<1 2≥0 3<2 3<1 3≥0
1<0 2<1 2≥0 3<2 3<1 3<0
1<0 2<1 2<0 3≥2
1<0 2<1 2<0 3<2 3≥1
1<0 2<1 2<0 3<2 3<1 3≥0
1<0 2<1 2<0 3<2 3<1 3<0

```
> 2 votes

# Answer
In theory, yes you should be able to create a decision tree for every comparison based sorting algorithm. You can write a program that will do so (for a fixed comparison-based sorting algorithm of your choice, say quicskort). Do keep in mind that decision trees have n! leaves so (roughly) beyond input sizes of say 11 you will run into storage issues.

Comparison-based sorting is defined rather informally, so to give a complete answer: it may get super complicated to detect whether an algorithm is truly comparison based (even before considering to generate the tree) and there is no formal logic I know of to verify the comparison-based property (would love to find out if someone did it). On the other hand, for most algorithms that are considered in practice the comparison-based property is straightforward to verify, ie quicskort, mergesort and heapsort among several others are easily checked to be comparison based and hence you can produce a decision tree (for small input sizes).
> 1 votes

---
Tags: time-complexity, sorting, comparison, decision-tree
---


# Question
Title: Is it possible to compute an equality hash for nodes in a *cyclic* directed graph in less than quadratic time?
Calculating hashes for nodes in an *acyclic* graph is well known using a Merkle tree.

With some simplifying assumptions, a simple algorithm will also calculate hashes for nodes in a *cyclic* graph... but it runs in quadratic time, making it impractical to use except for very small graphs.

Is it possible to do better?

## Graph characteristics

We have a directed graph, which can be cyclic, where each node contains a value.

Nodes are not labeled, and different nodes can contain the same value.

The outgoing edges of a node are ordered (or labeled 1, 2, 3, ... N, where N is the number of outgoing edges from the node).

(That is, it's a k-ary tree, if such a term can be used for a cyclic structure).

## Equal nodes

We define an equivalence relation this way: two nodes are equal if they contain the same value, they have the same number of outgoing edges, and, recursively, the subgraphs reachable from the two nodes following the outgoing edges in order are equal.

As I explain further below, it's also OK but not a requirement for nodes to be equal if following their edges produces the same sequence of values.

Note that this isn't an isomorphism problem for labeled graphs. We're not trying to find out if two *graphs* are equal. (Even with a cheap O(1) test available to see if two nodes are equal, worst case we'd still need to check many combinations of nodes between the two graphs to find out if the graphs are equal).

And, since edges are ordered, we don't need to perform an exponential search of alternatives to find out if two nodes are equal. We can tell if two nodes are equal by inspection, performing a breadth-first search from the two nodes in edge order.

## Equal hashes

For nodes in the graph, we wish to calculate a cryptographic hash such as SHA-256 for each node.

A minimal requirement is that given a hash for a node from a trusted source, we can query an untrusted server with the hash, the server replies with the node and subgraph reachable from the node, and we can verify that the data we've received matches the hash. (That's not very hard to do).

It would also be *very convenient* if equal nodes produce equal hashes, which the Merkle tree does for acyclic graphs, and the simple quadratic algorithm described below does for cyclic graphs.

However, the quadratic algorithm is too slow to be practical.

Thus my question as to whether it's possible to do better than the quadratic algorithm.

If not, we can give up on having equal nodes produce equal hashes.

But it would also be nice to know if it *is* impossible before giving up!

## Value unfolding equality option

It's OK (but not a requirement) if nodes end up being considered equal (have the same hash) if following the edges from the nodes produce the same values.

For example,

and

produce (if for example we start with the leftmost node) the same (infinite) unfolding of values: A, B, A, B, A, B...

These nodes are considered different by the simple quadratic algorithm I describe below, and they don't have to be considered equal, but if it would help a heuristic is free to give them the same hash.

https://www.cs.indiana.edu/~dyb/pubs/equal.pdf describes some algorithms for detecting equality by the unfolding of values... and I don't know if these algorithms are more or less efficient than testing for structural equality or if the algorithms could be modified to generate a hash... but maybe something like that would be an option.

## Annotating the graph

We're also free to *add* information to the graph (to annotate the graph with additional information), if that would help in some way.

We could, for example, take the hash for the node, add additional useful information about the graph, and hash *that*.

## Acyclic algorithm

For an acyclic graph, we can use a linear algorithm such as the Merkle tree: visit the nodes in post order. Calculate the hash based on the node's value, and in edge order, the previously calculated hashes of the node's successors.

(For example, in Git, the hash of a commit is based on the contents of the commit and the hashes of its parent commits).

## Cyclic quadratic algorithm

For a cyclic graph, here's the simple quadratic algorithm. For each node in the graph:

1. Number the nodes in the subgraph reachable from the node, which I can do in a specific order (such as breadth-first, ignoring nodes already numbered) because the outgoing edges of a node are ordered.
2. Describe the subgraph reachable from the node by listing the nodes in the subgraph in order by the assigned number, and for each node in the list include the node's value and for each outgoing edge for the node (in label order), include the number assigned to the tail node of the edge.
3. Hash the description to produce the hash for the node.

(This algorithm is quadratic because for each node, it visits all the nodes reachable from that node).

For example, for a tree with nodes containing values A, B, C, and D:

We describe A by assigning 0, 1, 2, 3 to the nodes containing A, B, C, D, and enumerate the values and edges this way:

```
0: A [1 2 3]
1: B []
2: C [0]
3: D []

```

Note in particular the outgoing edges from the node containing "A" are ordered (B, C, D), which makes this a unique description of the subgraph (which it wouldn't be if edges were unordered).

And similarly, to calculate the description for C:

```
0: C [1]
1: A [2 0 3]
2: B []
3: D []

```

As another example:

both nodes get the same hash, since the algorithm produces the same description when run for each node.

To reduce the number of such cyclic hash calculations we need to do, we can compute the strongly connected components of the graph, and then we only need to do the cyclic calculation for the nodes within each component.

However, within each strongly connected component, the simple algorithm is still quadratic.

Is it possible to do better?

## Typical graph structure

In my graphs, most nodes only have one direct predecessor, and usually only have a few direct successors. A small number of nodes ("central" nodes) have many direct predecessors and many direct successors.

(I'm modeling code modules, where modules, the "central" nodes, contain references to code and code contains references to modules).

It is these central nodes which are involved in large cycles that makes the quadratic algorithm impractical. Remove the central nodes, and the graph becomes acyclic, or the remaining cycles are small and can be handled by the quadratic algorithm.

Given this structure, is there an algorithm which, not worrying about worst case performance, would usually be better?

Thanks!

# Answer
Directed Graph Hashing (Helbling 2020) described a method of structural hashing cyclic directed graphs.

If I understand it correctly, first it reduces the graph to the condensation graph in which cycles are collapsed into single nodes. The condensation graph is acyclic and hence is easy to structurally hashing. Then, if I understand correctly, it assigned each node in a cycle the same hash.

> This means that vertices in the same orbit have the same hash value. Since an orbit contains nodes that are symmetrically identical, this is the desired behaviour.

If this is acceptable behavior, Helbling 2020 should be an adequate solution. Have a look at the computation complexity section to see if it looks reasonable given your structure of graph.
> 0 votes

---
Tags: graphs, time-complexity, hash
---


title: Understanding Levin's Universal Search

text:
# Question
Title: Understanding Levin's Universal Search
I am having troubles understanding Levin's universal search method. In Scholarpedia, http://www.scholarpedia.org/article/Universal\_search, it is claimed that “If there exists a program $p$, of length $l(p)$, that can solve the problem in time $t$, then Universal Search will solve the problem in a time $2^{l(p)+1}t$ at most.” How do they arrive at this number? Here is what I tried.

If we put all programs in a list, it looks like $e,0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000,\ldots$ Generally, the first occurence of a program of length $l$ is at the $n$th position, with $n=2^l-1$.

Now, I have encountered two different dovetailing procedures in the literature. The first describes executing program 1 every second step, program 2 every second of the remaining steps, program 3 every second of the remaining steps etc. This leads to the following execution sequence of the programs $n=1,2,3,4,5,6,\ldots$: $1213121412131215121312141213121612\ldots$ At step $i$ then $n$th program will have been run for $i/2^n$ steps. In the example above $i=34$. Thus, for $n=1,2,3,4,5,6$ we get $17,8,4,2,1,1$ (rounded) which is roughly correct.

Now, suppose there exists a program $p$ that computes a string $x$ in time $t$, whose position is $n$ in the lexicographic enumeration. This means that it will be the value of our time step $i$: $t=i/2^n=i/2^{2^{l(p)}}$. Therefore, $i=2^{2^{l(p)}}t$, which doesn't match the claim $2^{l(p)+1}t$.

In a different description, the execution is done in phases such that the first $i$ programs are run for 1 step at phase $i$. Therefore, before phase $i$, the $n$th program will have been executed $i-n$ times. We require the $n$th program to be executed $t=i-n$ times. Then, we get $i=2^{l(p)}+t$, which is the number of phases. The number of time steps to get to phase $i$ is $i^{2}/2$ (the area of the triangle). Hence we get $\left(2^{l(p)}+t\right)^{2}/2$, which is much larger than $2^{l(p)+1}t$.

Looking at the expression $2^{l(p)+1}t$ it looks like every program up to length $l(p)$ is executed for exactly $t$ time steps. But I thought, Levin search allocates execution time such that shorter programs are favoured?

Where is my mistake? Any help is greatly appreciated.

# Answer
You do not need dovetailing when $t(n)$ can be quickly computed. Also, note that $l$ is an absolute **CONSTANT**. The only function is $t$ but the variable is the input string length $n$, hence we write $t(n)$.

So when you are given an input string $x$ of length $|x|=n$, Levin search just does as follows:

Knowing an upperbound for the fixed length of $p$ (i.e. $l$), quickly compute the upperbound for runtime $t(n)$, for each program represented by a tring $M$ of length $|M|=\leq l$, simulate $M$ on input $x$.

Here is the part that is TOTALLY missing from your post: If some $M$ outputs a result $s$, use the verifier for the language to see if $s$ is the string being searched for.

This is only possible if the language is in $NP$.
> 1 votes

# Answer
Consider the following schedule:

```
for k = 1, 2, 3, 4...:
  T_k = 2^k
  for all programs p ordered by increasing length:
    if floor(T_k 2^{-l(p)}) > 0:  # equiv to: if l(p) ≤ k
      run p for T_k 2^{-l(p)} steps  # = 2^{k-l(p)}
      if p has halted (on its own) and the output string matches the target:
        return p
    else:
      break # no longer program will run either

```

By Kraft's inequality, we know that $\sum\_p 2^{-\ell(p)} \leq 1$. Thus, at each phase $k$, the total amount of computation for this phase is $\sum\_p \lfloor T\_k 2^{-\ell(p)}\rfloor \leq T\_k$. (Note that $\lfloor T\_K 2^{-\ell(q)}\rfloor = T\_K 2^{-\ell(q)}$ when $\lfloor T\_K 2^{-\ell(q)}\rfloor \> 0$.)

Now, suppose that a program $q$ requires $\tau$ steps to produce the target output. Then the first phase $K$ where $q$ receives sufficient allocated time, that is, at which $T\_K 2^{-\ell(q)} \geq \tau$ such that $q$ halts is $K = \min \\{K : 2^{K}2^{-\ell(q)}\geq \tau\\} = \lceil \ell(q)+\log\_2 \tau \rceil$. It follows that $T\_K \leq 2\tau 2^{\ell(q)}$.

Finally, the total amount of computation spent until $q$ halts is at most $\sum\_{k=1}^K T\_k = 2 T\_K -2 \leq 4\tau2^{\ell(q)}$.
> 1 votes

---
Tags: complexity-theory, turing-machines, searching, search
---


# Question
Title: Time complexity when implementing uniform family of circuits
It is known that the complexity class P is equivalent to the class of problems decided by polynomial-time uniform familiy of circuits. When stating the complexity of algorithms as this family of circuits, this complexity is usually stated in terms of the depth and size of the circuit. What I have not understood well is why the authors don't include the complexity of the Turing machine constructing the circuits as well. This seems an important part of the overall algorithm. Could somebody clear this up for me?

In particular im interested in this question in the context of quantum circuits. When implementing a quantum algorithm usually this is expressed as a quantum circuit, and quantum algorithms papers report the complexity in terms of the depth. Why not consider the complexity of the classical computer that has to construct the circuit in the first place? Can the complexity of contructing the circuit be bigger than that of running the circuit itself?

# Answer
> 1 votes
At one level, the answer to "why not" is "because that's not the definition". In mathematics, we define certain concepts and then explore them.

At another level, it's because such a variation would not add any new knowledge or create any new concepts. In particular, consider the following two versions of what you wrote:

1. There is a single Turing machine $T$ for all input sizes. In particular, on input $x$, we let $n$ be the length of the input, run $T(1^n)$, let $C\_n$ be its output, and feed $x$ as input to the circuit $C\_n$.

Then this model is exactly a uniform model of circuit complexity. It is polynomially equivalent to other standard uniform models of computation (e.g., Turing machines).
2. There is one Turing machine $T\_n$ for each input size $n$. In particular, on input $x$, we let $n$ be the length of the input, run $T\_n(1^n)$, let $C\_n$ be its output, and feed $x$ as input to the circuit $C\_n$.

Then this model is polynomially equivalent to non-uniform circuit models, i.e., to standard non-uniform models of computation.

So either way, we don't obtain something new; we obtain something that is equivalent to existing definitions and concepts.

Related: What is the difference between a collection of Turing Machines and a family of Circuits?, Proof that uniform circuit families can efficiently simulate a Turing Machine, Circuits vs Turing Machines in the "nonuniform model of computation", https://cs.stackexchange.com/a/110787/755, https://en.wikipedia.org/wiki/Advice\_(complexity), https://en.wikipedia.org/wiki/Circuit\_complexity#Uniformity, https://en.wikipedia.org/wiki/P/poly

---
Tags: complexity-theory, circuits
---


# Question
Title: Algorithm to optimise the cost to choose a subset of array
I have been on this problem for very long time, Lets assume we have a shopping list eg:`{milk,bread,coke,orange,apple,..}` and the shop only sells pack of thing and not individual things eg: `[{milk, bread}, {bread,orange} , {orange,apple} ...]`. Given the cost of each package. Is there any algorithm to minimize the cost such that we get all items from our list. I have not able to find a better algorithm than bruteforce.

# Answer
This is the (weighted) set cover problem. It is NP-hard, so there is not likely to be any efficient algorithm that works on all problem instances. There are various methods to deal with this: e.g., heuristic algorithms whose worst-case running time is exponential (e.g., using integer linear programming), approximation algorithms, and so on.
> 1 votes

---
Tags: time-complexity, dynamic-programming
---


# Question
Title: How to convert the regular expression $\emptyset^*$ to an NFA?
The question is to convert the following regular expression to an NFA: $\emptyset^\*$.

I know that the symbol phi in Theory Of Computation means an empty set. But what does phi^\* mean?

# Answer
That's not a phi symbol (phi is written either $\phi$ or $\varphi$, and the uppercase version is $\Phi$), but you are right that $\emptyset$ denotes the empty set.

The star symbol is known as the Kleene Star and $A^\*$ is the set containing the empty word (denoted by $\varepsilon$) and all the words that can be obtained by concatenating any finite number of words from $A$. Formally, $A^0=\\{\varepsilon\\}$, $A^i=\\{xy \mid x \in A^{i−1},y \in A\\}$ for any integer $i\>0$, and $$A^\*=\bigcup\_{i=0}^\infty A^i.$$

This should be all you need to solve the exercise. As a hint: can you figure out what $\emptyset^i$ is when $i \> 0$?
> 2 votes

---
Tags: automata, finite-automata, regular-expressions
---


# Question
Title: Is there a faster than O(n^2) way to compute a vector of length n from another vector and an n by n matrix?
$A$ is an array of length $n$
$B$ is an $n\times n$ matrix \

I want to return an array C of size n such that:
$$C\_{i} = \sum\_{j=1}^{n} \max(0, a\_i - b\_{ij}) $$

In pseudocode it could be like below

```
for i = 1 to n:
   C[i] = 0
   for j = 1 to n:
      C[i] += max(0, a[i] - b[i,j])

```

this runs on O(n^2) but it is possible to lower that.

# Answer
> 30 votes
That's not possible. You have to read in the entire $B$ matrix to determine the correct answer, which fundamentally requires $O(n^2)$ time.

# Answer
> 10 votes
A key observation is that if $i$-problems are completely independent, you need to compute $n$ sums of the form

$$s=\sum\_{j=1}^n\max(0,a-b\_j).$$

With $a=0$ and all $b\_j\<0$, we get the even simpler form

$$-s=\sum\_{j=1}^nb\_j$$ which is a sum of $n$ terms and takes $\Omega(n)$ additions. (If parallelized, this can be lowered to $\Omega(\lg(n))$ using $n$ processors.) In the general case, you need the same amount of comparisons.

---

If you know *a priori* that only few terms are such that $b\_j\<a$ and you can efficiently determine which ones, then you can avoid accumulating the zeroes.

---

More interesting question is when $b$ is a sparse matrix. Then, two cases: if

* $a\le0$, just add the terms $\max(0, a\_i-b\_{ij})$ for all $i$. But if
* $a\>0$, add $na\_i$ and the terms $\max(-a\_i,-b\_{ij})$ or $-\min(a, b\_{ij})$.

# Answer
> 1 votes
While the worst-case complexity is $O(n^2)$, the following special case might be of interest for some applications of this algorithm:

If:

* $B$ does not contain negative values

and:

* $a\_i = 0$

Then $C\_i = 0$, with no need to consider the matrix entries $b\_{i1}$ to $b\_{in}$.

This short circuit may make the algorithm behave linear in practice if $A$ is rather sparse and the condition of $B$ containing no negative numbers holds.

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


# Question
Title: Reinforcement Learning Reward Function for Optimizing Golf Aim?
I read this article, mentioning that either here, or StackOverflow would be the best places to ask generic machine learning questions, however, if the question isn't programming specific with a minimal reproducible example, the mod's at S.O. can't wait to shut you down pretty quick, so figured I'd try here first.

I'm developing a small RL environment for a school project that plays a 2D golf game, and I need confirmation that my idea makes sense for a reward function.

To keep things simple, I believe that working with the "distance from the pin" makes the most sense, in that the agent should be able to drain the ball in as few shots as possible. Read that again as "distance from the hole", not "distance TO the hole" as these would be two different calculations.

It's my understanding that to find the quickest path, you should assign negative rewards so that it learns to make decisions to minimize those punishments. With that in mind, I'm thinking that whatever your previous shot's distance from the hole is, the negative value of that would be the reward for that shot.

For example, you're in the tee box with your driver out, and the pin is 400 yards away. You whack the ball straight at the pin for 250 yards. Your reward for that shot would be -150 as you're now 150 yards from the pin. You hit your second shot onto the green where you're now just 10 yards from the pin. Your reward for that shot would be -10. You birdie this par 4 hole, so your putt reward would be 0 (summing to a "reward" of -160 for the hole). Conceptually this should make it so that if the agent hits the ball too far AWAY from the pin on any shot, the reward would be even more negative than it should be, so it should learn to make shots that minimize those punishments.

Am I correct that this would be a good way to implement a simple reward function for the problem of finding the quickest path to the target? I think for golf specifically, one COULD factor in what shot it is, like if it's a par 3 and you sink it on your first shot from the tee box, the reward for that should be greater than the sum of any 2 or 3 or more shot's reward, but we can keep it simple for now.

# Answer
It seems like a plausible thing to try. Give it a try and see how it works.

An even better metric might be some estimate of (the negation of) the expected number of strokes needed, given the remaining distance to the hole. This is not a purely linear function, so might give a better reward function.
> 1 votes

---
Tags: machine-learning, reinforcement-learning
---


# Question
Title: Can we skip an input in push down automata
I'm giving a language $L=\\{0^m 1^n 2^m \mid m,n ∈ N\\}$. I designed this stack machine in order to accept $L$. Here, I'm skipping $1$s (no matter how many $1$s there are). Is it acceptable to skip the input this way?

# Answer
Yes, we can skip or ignore an input without pushing it into the stack. In my case (a^i b^j c^k d^j e^i) where i & j \>=0 while k \>0. 'abcde'is an accepted string so I ll make following PDA so that it will accept my string. In this case I am ignoring C so that I can make a perfect machine. So, It is possible to skip an input.
> 1 votes

---
Tags: finite-automata, pushdown-automata
---


# Question
Title: Recursive enumerable class or its complement?
If `K = {<<M>> | L(M) has at least 1 word}`, then does K belong to the class of recursive enumerable (RE) languages or its complement?

I'm a bit confused, because if it is RE, then we'd have a TM W that semidecides it, but even for some language, `L(M)`, that does halt for at least a word, we don't know which word it is and may require a word with length tending to infinity.

# Answer
Let $\\{M\_n\\}$ and $\\{W\_n\\}$ be recursive enumerations of the machines and the words. Now for each $n$ run $M\_1\ldots M\_n$ on $W\_1\ldots W\_n$ for $n$ steps, and output the code of the machines that stopped at some point. That produces a recursive enumeration of $K$.
> 1 votes

---
Tags: turing-machines, recursively-enumerable
---


# Question
Title: 3SAT solvable in polynomial time...but with exponential tuning?
Suppose there exists an algorithm that solves 3SAT in a polynomial number of steps. However, this algorithm requires some 'tuning' parameters, and the value of these tuning parameters take an exponential number of steps(given the input) to determine.

Would this place 3SAT in P? (since it can be solved in polynomial time given the appropriate parameters)

Or would 3SAT remain in NP? (since it still takes an exponential number of steps to ultimately solve)

Edit: just to clarify, the question is about whether or not 3SAT would 'move' to P or 'remain' where it currently is...NP. If 3SAT 'moves' to P it obviously would still be contained in NP.

# Answer
> 35 votes
If the tuning parameters depend on the entire input, then it's not a self-contained algorithm, so it says nothing about whether 3SAT is in P.

After all, I can give you an algorithm that has that property: in my algorithm, the 'tuning parameter' for a 3SAT formula $\varphi$ is 0 or 1, according to whether the formula $\varphi$ is satisfiable or not. My algorithm ignores the formula on its input and just outputs its tuning parameter. Sure, it may take exponential time to find the right tuning parameter for any particular formula, but once you've got it, my algorithm can output the right solution in polynomial time -- in fact, in just $O(1)$ time. Yet this says nothing about whether 3SAT is in P or not.

# Answer
> 14 votes
Such an algorithm, assuming that the parameters depend only on the input length, would put 3SAT in the class $\mathsf{P/poly}$ (even without any bound on the running time needed to find the parameters). This is considered unlikely, however.

# Answer
> 1 votes
P, you may recall, is the class of problems for which there exists a *deterministic Turing machine* which solves the problem and the number of steps taken by that Turing machine is polynomial in the size of the input on the tape. NP is defined similarly, only the Turing machine is nondeterministic.

That the "complexity zoo" is defined in terms of Turing machines is a point that is often forgotten.

If there is additional information that needs to be supplied on the tape, then this is additional required input, and it's not the same problem. Similarly, you can't cheat by padding the input tape with an exponential number of symbols, or using a less-compressed representation of the input. Hell, prime factoring would trivially be in P were the input represented in unary.

There are known polynomial-time algorithms for solving 3SAT on other models of computation, such as analog computers. This cannot be simulated in polynomial time on a Turing machine because the "voltages" can become exponential in size.

# Answer
> 0 votes
If your solution takes an exponential number of steps to accomplish any component of the computation it is at least exponential in time. Hence, not P.

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


# Question
Title: Prove or Disprove, 3SAT ≤p 2SAT, then P = NP
I know that 3SAT is in NP and 2SAT is in P. And 2SAT can reduce to 3SAT just says 3SAT is strictly harder than 2SAT, so I don't think this proves P = NP, but it doesn't seem to disprove it either.

# Answer
2SAT can be solved in linear (!) time, so your reduction would certainly prove $P = NP$.
> 0 votes

# Answer
Unfortunately it has been shown that 3SAT is not reducible to 2SAT. However, 3SAT is in P where any algorithm solves the general case in P time and space. For such an algorithm see linked paper below.

https://arxiv.org/abs/cs/0205064
> -2 votes

---
Tags: satisfiability, discrete-mathematics, p-vs-np
---


# Question
Title: Automatic differentiation - Upper bound time
Is there any proof or reference or intuition for the following theorem related to AAD:

Any function f of n variables f(x1,...,xn) can be differentiated with respect to every variable xi at a computational cost that does not exceed 4 times the complexity of one computation of f.

Thank you

# Answer
Proof can be found in section 4.4 and 4.5 of "evaluating derivatives and principles of algorithmic differentiation" from Griewank&Walther
> -1 votes

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


# Question
Title: Node weighted Steiner Tree Problem where all Nodes have the same Weight
The node weighted Steiner Tree Problem as found in this compendium:

$\textbf{Instance}: \text{Graph } G = (V, E)\text{, set of terminals } S \subseteq V \text{ and a node weight function } w:V \to \mathbb{R}^+$
$\textbf{Solution}: \text{A tree } T = (V\_T,E\_T) \text{ in } G \text{, such that } S\subseteq V\_T \subseteq V,~E\_T \subseteq E.$
$\textbf{Objective}: \text{Minimize the sum of the vertices weight}$

Is NP hard. But what if all nodes have the same weight? So the weight function $w$ is just a constant function that maps to 1 for all Vertices: $\forall v \in V:w(v) = 1$

Is there a name for this Problem? Is it NP hard? If yes what algorithms can I use for approximation?

Please note that this problem is not equals MST, ShortestPath or TSP

# Answer
Since all vertex weights are equal, minimizing $\sum\_{v \in V\_T} w(v)$ is equivalent to minimizing $|V\_T|$, and since a tree on $x$ vertices has exactly $x-1$, edges, this is equivalent to minimizing $|E\_T|$.

Therefore your problem is NP-hard.

Moreover, any $\alpha$-approximation algorithm for the classical Steiner tree problem, where $\alpha$ is a constant, can also be used to provide a $\alpha$-approximation for your version. Let $v$ be a terminal and let $\overline{w}$ be the (constant) vertex weight. Add a new vertex $v'$ and the edge $(v, v')$. Then drop all vertex weights, and set all edge weights to $\overline{w}$.

You are left with an instance of Steiner tree such that any solution to this instance can be converted to a solution for your version of the problem having the same cost (by simply deleting $(v,v')$ from $T\_V$), and vice-versa (by adding $(v,v')$ to $T\_V$).
> 2 votes

---
Tags: graphs, trees, np
---


title: Halting problem logic must be wrong

text:
# Question
Title: Halting problem logic must be wrong
I think that I have found an issue with the proof of the halting problem, which would cause the entire proof to be invalid.

To ensure I understand, here is Turing's proof of the halting problem being unsolvable.

## Proof:

Assume the function $h(x,y)$ determines whether the function $y(x)$ halts on input x, $h(x,y)$ returns True, or 1 if $y(x)$ halts, otherwise it returns False or 0.

Given that the function $h(x,y)$ exists, it must be possible to create a new function, $h'(x)$, which is just $h(x,x)$. In essence, $h'(x)$ determines if the program $x()$ halts when run with itself (encoded in the form of a number).

If $h'(x)$ also exists, then again, a new function $H(x)$ can be created. $H(x)$ in pseudo code is:

```
Def H(x)

    If h'(x) == True:

Loop forever

    Otherwise:

Return()

```

Now when $H$ is run with itself as an input – $H(H)$ \- a paradox is created:

If $H(H)$ will halt, then $H$ run with itself as an input must loop, but that is the original statement

Otherwise if $H(H)$ loops, then $H$ run on itself must halt, which is a contradiction.

Hence $H(x)$ cannot exist, and by extension $h(x)$ cannot exist

## Disproof of the proof:

If we assume that the logic in Turing's proof is correct, then we can do this:

Assume the function $l(x,y)$ determines whether $y(x)$ takes more than n, where n is any number, seconds to compute.

Symmetrically to $h(x,y)$ going to $h'(x)$, $l'(x)$ can also be created from $l(x,y)$, where $l'(x)$ = $l(x,x)$.

Finally, exactly the same as in Turing's proof, $L(x)$ can also exist. $L(x)$ will take more than n seconds to compute if $l'(x)$ returns False, and otherwise will take less than n seconds. $L(x)$ does the opposite of $x(x)$.

If $L(x)$ does exist, then $L(L)$ can be run, and results in a paradox the same way that $H(H)$ does.

But the function $l(x,y)$ is possible to create, by simply timing the function $y(x)$. It may be that some adjustments are needed to fix the way $l(x,y)$ works, e.g there is an inherent time associated with the function so you need to subtract a number, but the function should work.

Edit: Because it is confusing as to exactly what $l(x,y)$ is, I should clarify. What the function $l(x,y)$ is is completely irrelevant to whether the proof works. I chose the steps taken or the time taken because it is similar to the original problem, but an easy function might be something like if the first character of x and y are both in the first half of the alphabet. That would still work with the proof.

Not only this, but the logic can be extended to any meta-program, and because most programs could be divided into 2 programs, the same way that $x^2 + 8x + 16$ can be divided into $f(g(x))$ where $f(x) = x^2$ and $g(x) = x + 4$. Turing's proof, if correct, would also prove that any program is not able to be created, which is evidently false, hence the proof must be false. Is this incorrect?

# Answer
> 4 votes
Your analysis of $L(L)$ is not complete.

Indeed, if we assume $L(L)$ loops this implies that $L(L)$ runs in less that $n$ steps, thus $L(L)$ does not loop. Hence *our assumption* $L(L)$ loops is false. We conclude $L(L)$ must halt. Now if we assume $L(L)$ halts in $\<n$ steps, we again get a contradiction (because $L(L)$ loops). Thus $L(L)$ can not halt in $\<n$ steps.

Our results is that $L(L)$ halts in $\geq n$ steps. This is entirely consistent with the definition of $L$. Math is not yet broken.

# Answer
> 1 votes
Using "seconds" is not very well defined, so I'll use the usual "steps" instead.

The typical strategy creating a machine for $l$ is to have it simulate $y(x)$ for up to $n$ steps. If the simulation finishes, then it returns true, otherwise it returns false. If you try to diagonalize against this in the same way as the halting problem, you then get:

```
L(x) =
  if l(L,x)
  then <take more than n steps>
  else halt

```

This does not work, though. The way that $l$ works takes steps (or time, if you prefer) itself. In fact, simulation of one step takes *more* than one step, generally (it could just waste $n$ steps, too). So what happens is that $l(x,L)$ simulates $L(x)$ (which runs $l(x,L)$ ...) for $n$ steps. By doing this, it has used *more* than $n$ steps, so $L$ has, too, and the logic can no longer do anything to use fewer than $n$ steps, because halting immediately *still* results in a running time of more than $n$ steps.

Incidentally, it still doesn't work if you try to make it more like the halting problem: can a machine decide $l(x,y)$ in fewer than $n$ steps? If you try to diagonalize, then you can't rule out the possibility that the machine for $l$ takes $n-1$ steps to decide $L(L)$ fails, which ensures that $L(L)$ takes $n$ or more steps. The difference is that you can approximate $n$ very closely by a smaller finite number. But no halting computation, no matter how lengthy, approximates not-halting this way, so that just one or two more steps tips over into not-halting.

This doesn't mean that a machine *can* decide in fewer than $n$ steps if arbitrary other machines complete in fewer than $n$ steps. but it means that the diagonal argument doesn't work to rule it out.

# Answer
> 1 votes
If $l'(x)$ returns false (meaning $x(x)$ does not halt within $n$ seconds) - by running $x(x)$ for $n$ seconds and observing whether it halted - then it necessarily takes more than $n$ seconds to do so.

It's impossible to make a program that runs $l'(x)$ and then halts in less than $n$ seconds if $l'(x)$ returns false, because $l'(x)$ already takes more than $n$ seconds, and the computer which runs this program is not equipped with a time machine.

Your program $L(anything)$ **always** takes longer than $n$ seconds.

If you had a time machine you might be able to make this work, but then again, if you had a time machine you could also solve Turing's halting problem and become world-famous.

# Answer
> 0 votes
In Turing's proof, $H$ is a function that is obviously computable if $h$ (The putative halting decider function) is computable. The fact that $H$ causes a halting decider to "trip up" is a fundamental aspect of the proof – but conversely, that $H$ uses a putative halting decider is a fundamental aspect of the proof. You do not create the same paradox with arbitrary other functions.

Importantly, Turing's proof of the undecidability of the Halting problem is a proof by contradiction. He demonstrated a situation where the assumption of an universal halting decider does not have a correct answer. If you intend to use the same proof to demonstrate other functions are uncomputable – or as in your case, that the proof itself is flawed and that the Church-Turing thesis is wrong in that there exist intuitively computable functions that cannot be represented by Turing Machines – you must preserve the contradiction.

For a very simple example to contrast with the Halting problem plugged in the same proof frame, let $fastHalt(M)$ determining whether the Turing Machine $M$ immediately halts when run on an empty tape. (This is a special case of your function $l$, incidentally)

Now, $fastHalt$ is intuitively computable and hence there is a Turing Machine that is capable of it. If we create a function $F$ that uses $fastHalt$ similarly to Turing's proof, do we get a contradiction? As pseudocode:

```
def F(x):
    if fastHalt(x):
        loop forever
    else:
        halt

```

Is there a contradiction? Only if $fastHalt(F) = \mathsf{TRUE}$ . In that case, $F(F)$ would indeed loop forever, so we can conclude that $fastHalt(F) = \mathsf{FALSE}$ which makes sense, given $F$ cannot be represented as an immediately halting Turing Machine.

Let us fix an $n$ and return to your original function: $l'(x) = \mathsf{TRUE}$ if $x$ takes more than $n$ steps (preferable in analysis over the more chaos-dependent seconds!) to compute before halting or diverging, $\mathsf{FALSE}$ otherwise. Thereby you get this program:

```
def L(x):
    if l'(x):  //program finishes slow or never
        loop forever
    else:  //program finishes fast
        halt

```

. Does $L(L)$ force a contradiction? No: if $l'(L) = \mathsf{TRUE}$ this is entirely consistent with the outcome of the computation not halting. If $l\`(L) = \mathsf{FALSE}$, this is likewise consistent with the outcome of the computation halting. It gets more interesting if you reverse the logic:

```
def L'(x):
    if NOT l'(x):  //program finishes fast
        loop forever
    else:  //program finishes slow or never
        halt

```

This gets us closer to the type of contradiction Turing's proof uses, but falls short of disproving the existence of $l'$: similarly to $fastHalt$, the outcome of $l'(L) = \mathsf{FALSE}$ ($L'(L')$ taking $n$ or fewer steps to compute) is the only case that creates a contradiction, while the outcome where $l'(L') = \mathsf{TRUE}$ creates no contradiction. In essence, what your example proves is the impossibility of a decider that determines whether a Turing Machine halts in $n$ or fewer steps without itself requiring more than $n$ steps to compute.

For one final demonstration, let's try something that doesn't use machines's running time at all and instead does something more tangible. Let $sign(M) = \mathsf{TRUE}$ iff $M$ halts with a single $1$ on the tape when $M$ is run on an empty tape.

Can we spin $sign(M)$ into a contradiction? Let's try:

```
def S(x):
    if sign(x):
        replace the 1 on the tape with a 0
        halt
    else:
        output 1 on the tape
        halt

```

Does running $S(S)$ on the tape create a contradiction similarly to Turing's halting proof? Turns out it does! If $sign(S)$ is $\mathsf{TRUE}$, $S(S)$ should halt with a $1$ on the tape, but the $1$ is replaced by a $0$. if $sign(S)$ is $\mathsf{FALSE}$, $S(S)$ should end without a $1$ on a tape but $1$ is output before halting. It follows that $sign(M)$ is not computable – a result that should not surprise a reader familiar with Rice's theorem.

# Answer
> 0 votes
Your proof of the halting problem is missing an essential assumption, which may be confusing you: it is essential to assume that $h$ *always halts*, i.e., that $h(x, y)$ does not have to run $x(y)$ in order to return. If you remove this assumption, the proof no longer works. If you can find the exact spot and reason that the proof breaks if you remove this assumption, I expect you'll also see why your modifications don't work.

---
Tags: turing-machines, proof-techniques, halting-problem
---


# Question
Title: Can an algorithm decide whether any DFA accepts an infinite language? What is its time complexity?
Given a DFA with m number of input alphabet and n number of states. What is time complexity to check DFA accepts infinite language (i.e infinite length of strings)?

# Answer
In addition to the answers linked by Rinkesh P. in a comment, here is an approach that directly translates into an efficient algorithm.

The DFA accept an infinite language if and only if there is a walk from the starting state to a final state that contains a cycle.

To obtain an algorithm consider the directed subgraph of the DFA that is induced by the states $q$ such that 1) the initial state $s$ can reach $q$, and 2) $q$ can reach a final state. Let $G$ be the resulting graph, and notice that all such states $q$ can be found in linear time by running, e.g., two BFS searches (one from $s$, and the other from the set of final states on the graph obtained by reversing the DFA's edges).

Then the problem is equivalent to deciding whether $G$ contains a cycle. Which can be done using a DFS search from $s$. The overall time complexity is linear in $n+m$ where $n$ (resp. $m$) is the number of states (resp. transition) of the DFA.
> 2 votes

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


# Question
Title: Why is the type ∀t.t un-inhabited in System F?
How do you prove that there exists no term with the type $\forall t. t$ in System F?

I tried searching through Pierce's TAPL and Reynold's ToPL, but could not find anything. I suspect that the proof may involve some kind of model theoritic argument, but I fail to see where to start.

# Answer
> 4 votes
The simplest proof is giving a model where types are interpreted as propositions, and terms as proofs, then observing that $\forall \alpha.\alpha$ is interpreted as the false proposition, so any $\cdot \vdash t : \forall \alpha.\alpha$ would be a proof of falsehood. It is important to remember that $\forall \alpha.\alpha$ is only uninhabited for sure in the empty context $\cdot$, in other contexts it may be trivially inhabited.

Concretely, first interpret each $A$ type with $n$ free type variables in the following way:

$$ \begin{alignat\*}{2} & \[\\!\[ A \]\\!\] && : \mathsf{Bool}^n \to \mathsf{Bool}\\ & \[\\!\[ \alpha \]\\!\]\\,\gamma && := \text{$\alpha$-th component of $\gamma$}\\ & \[\\!\[ A \to B \]\\!\]\\,\gamma && := \[\\!\[ A \]\\!\]\\,\gamma \Rightarrow \[\\!\[ B \]\\!\]\\,\gamma\\ & \[\\!\[ \forall \alpha.\\,B\]\\!\]\\,\gamma && := \[\\!\[B\]\\!\]\\,(\mathsf{true},\\,\gamma)\\,\land\\,\[\\!\[B\]\\!\]\\,(\mathsf{false},\\,\gamma) \end{alignat\*} $$

Interpret every typing context $\Gamma$ with $n$ free type variables as:

$$ \begin{alignat\*}{2} & \[\\!\[\Gamma\]\\!\] : \mathsf{Bool}^n\to \mathsf{Bool}\\ & \[\\!\[\Gamma\]\\!\]\\,\gamma := \bigwedge\limits\_{A\\,\in\\,\Gamma}\\,\[\\!\[A\]\\!\]\\,\gamma \end{alignat\*} $$

Then show for each $\Gamma \vdash t : A$ term, that for each truth valuation $\gamma : \mathsf{Bool}^n$, if $\[\\!\[\Gamma\]\\!\]\\,\gamma = \mathsf{true}$, then $\[\\!\[A\]\\!\]\\,\gamma = \mathsf{true}$. This can be done by induction on terms.

Now, $\[\\!\[\forall \alpha.\alpha\]\\!\]$ with no free type variables evaluates to $\mathsf{false}$, since it's $\mathsf{true}$ when $\alpha$ is instantiated to $\mathsf{true}$, and $\mathsf{false}$ when it's instantiated to $\mathsf{false}$, and the conjunction of these is $\mathsf{false}$. Assuming $\cdot\vdash t : \forall \alpha.\alpha$, we have by the previous result that $\[\\!\[\forall \alpha.\alpha\]\\!\]$ is $\mathsf{true}$, a contradiction, hence there is no $\cdot\vdash t : \forall \alpha.\alpha$.

# Answer
> 1 votes
There is a proof by using parametricity/logical relations framework or free theorems as mentioned in Zhao et al.\[1\]

> For instance, we can conclude that there is no closed inhabitant of type ∀α.α in a pure setting. If there were such a term, it must yield a value of any type at which it is instantiated, but there is no uniform algorithm to compute a value at any type. Therefore, ∀α.α is an empty type.

\[1\]: Zhao J., Zhang Q., Zdancewic S. (2010) Relational Parametricity for a Polymorphic Linear Lambda Calculus. In: Ueda K. (eds) Programming Languages and Systems. APLAS 2010. Lecture Notes in Computer Science, vol 6461. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17164-2\_24

# Answer
> 1 votes
Here is a simple answer. If we have a lambda-term $x : \forall t.\\,t$ then we should be able to apply the term $x$ to any type $t$ and obtain a *value* of type $t$. Denote type application by $x t$ and find that $x t$ is a value of any given type $t$. Let us apply this ability to the void type $0$. Then $x 0$ is a value of type $0$. But there are no values of type $0$. So, we could not have had a value $x$ either.

Another proof is based on using naturality laws. If you have a pure lambda-term of type $\forall t.\\,t$ in System F, you can conclude by parametricity theorems that this term satisfies the law of natural transformations of type $\forall t.\\,\underline 1 \to t$ (where I denote the unit type by $\underline1$).

Then you write the naturality law: for an arbitrary function $f: a\to b$, a function $\phi: \forall t.\\,\underline1\to t$ satisfies the equation:

$$ f \circ \phi = \phi $$

We can derive from this equation that there can't be any function $\phi$. For an $x: \underline1$ (there is only one such value $x$) we will have some value $a\_1=\phi(x)$ of type $a$ and also some value $b\_1=\phi(x)$ of type $b$. However, the value $b\_1$ must be at the same time equal to $f(a\_1)$ for *all* functions $f: a\to b$. This is impossible. So, we conclude that $\phi$ cannot exist, and the type $\forall t.\\,t$ is void.

---
Tags: programming-languages, type-theory, types-and-programming-languages
---


# Question
Title: Rigorous proof that parametric polymorphism implies naturality using parametricity?
This question asks for an informal explanation of why all polymorphic functions between functors are natural transformations (This is a claim made by Bartosz Milewski). One answer to that question refers to the Theorems for free! paper. However, after reading it I'm not seeing how it implies the result.

The parametricity theorem from "Theorems for free!" can be applied to a function that has the "natural transformation type signature": $\eta:\forall X,F (X) \to G (X)$ for some $F, G : \text{Type} \to \text{Type}$. Basically parametricity gives us (applying it to a functional relation): For any types $A\_1,A\_2$ and function $f:A\_1\to A\_2$, the following equation holds:

$$f\_G\circ \eta\_{A\_1}=\eta \_{A\_2}\circ f\_{F}$$

where I define $f\_G$ and $f\_F$ as the relations that Wadler would write as $\[\[F(X)\]\]\mathcal A\[f\setminus X\]$ and $\[\[G(X)\]\]\mathcal A\[f\setminus X\]$ respectively (I can't write the double square bracket symbol \llbracket).

This *looks* like the right equation for $\eta$ to be a natural transformation, but the problem is that $f\_G$ and $f\_F$ aren't necessarily equal to the functions $G(f)$ and $F(f)$. In fact, we haven't even defined $F$ and $G$ as functors. Instead, $f\_G$ and $f\_F$ are the specific functions that you get when you apply Wadler's definition of the relation that belongs to each type.

Therefore I don't see how you would use the parametricity theorem to show that polymorphic functions between functors are natural transformations, because as far as I can tell, the parametricity theorem doesn't even allow you to specify the morphism part of the functors $F,G$. It only takes them as type constructors.

Is there something I'm missing? Is there a formal proof? It would be nice to have a self-contained proof that "parametric polymorphism implies naturality", that requires minimal background knowledge.

# Answer
> 12 votes
The missing part is the "identity extension lemma", which is mentioned in Reynolds' original paper but not in Wadler's.

For $F : \text{Type} \to \text{Type}$, this says that if the relational interpretation of $F$ is instantiated with a type $A$ and the identity relation on $A$, we get the identity relation on $F\\,A$.

For System F, identity extension can be proven for types-in-contexts, but note that there is no $F : \text{Type} \to \text{Type}$ in System F. To gracefully handle identity extension for type operators in general, it's better to switch to reflexive graph models, where identity extension is given mutually with the rest of the model.

Let's use the reflexive graph model of some type theory. This means that for every closed $F : \text{Type} \to \text{Type}$, we get a semantic $F^S : \text{Set} \to \text{Set}$, together with $F^R : (A, B : \text{Set}) \to \text{Rel}\\,A\\,B \to \text{Rel}\\,(F\\,A)\\,(F\\,B)$ where $\text{Rel}\\,A\\,B$ denotes a set of proof-irrelevant relations. We also get identity extension: $F^R\\,A\\,A\\,(\text{Id}\\,A) = \text{Id}\\,(F\\,A)$, where $\text{Id}\\,A$ is the identity relation. In the following, let's omit all $^S$-es and don't talk about syntactic things, only about semantic things, so that we may write $F : \text{Set} \to \text{Set}$.

Assume $F, G : \text{Set} \to \text{Set}$ are functors, and $\eta : (A : \text{Set}) \to F\\,A \to G\\,A$. Let's write $\text{map}$ for functorial mapping. We assume that everything is parametric. This means that we get $F^R$, $G^R$, $\eta^R$ and ${\text{map}\_F}^R$ and ${\text{map}\_G}^R$. Assume $f : A \to B$ and $x : F\\,A$.

To show:

$$ \text{map}\_G\\,f\\,(\eta\_A\\,x) = \eta\_B\\,(\text{map}\_F\\,f\\,x) $$

By identity extension for $G$, this is equivalent to

$$ G^R\\,B\\,B\\,(\text{Id}\\,B)\\,(\text{map}\_G\\,f\\,(\eta\_A\\,x))\\,(\eta\_B\\,(\text{map}\_F\\,f\\,x)) $$

Category law:

$$ G^R\\,B\\,B\\,(\text{Id}\\,B)\\,(\text{map}\_G\\,f\\,(\eta\_A\\,x))\\,(\text{map}\_G\\,id\\,(\eta\_B\\,(\text{map}\_F\\,f\\,x))) $$

To show the above, we use ${\text{map}\_G}^R$, i.e. that $\text{map}\_G$ preserves all relations. We have to pick two relations, one in $\text{Rel}\\,A\\,B$ and one in $\text{Rel}\\,B\\,B$ and show that $f : A \to B$ and $id : B \to B$ are pointwise related. We pick the graph of $f$ and $\text{Id}\\,B$, and the functions are clearly pointwise related. It remains to show:

$$ G^R\\,A\\,B\\,(\text{Graph}\\,f)\\,(\eta\_A\\,x)\\,(\eta\_B\\,(\text{map}\_F\\,f\\,x)) $$

We know that $\eta$ preserves all relations, so it's enough to show:

$$ F^R\\,A\\,B\\,(\text{Graph}\\,f)\\,x\\,(\text{map}\_F\\,f\\,x) $$

Category law:

$$ F^R\\,A\\,B\\,(\text{Graph}\\,f)\\,(\text{map}\_F\\,id\\,x)\\,(\text{map}\_F\\,f\\,x)$$

We instantiate ${\text{map}\_F}^R$ with $\text{Id}\\,A$ and $\text{Graph}\\,f$ and it remains to show:

$$ F^R\\,A\\,A\\,(\text{Id}\\,A)\\,x\\,x $$

By identity extension for $F$, this is equivalent to:

$$ x = x $$

---

The same thing in Agda:

```
-- Agda 2.6.1, stdlib 1.5

open import Relation.Binary.PropositionalEquality
  renaming (sym to infix 6 _⁻¹; cong to ap; trans to infixr 5 _◾_; subst to tr)
open import Function

coe : ∀{i}{A B : Set i} → A ≡ B → A → B
coe refl a = a

Rel : Set → Set → Set₁
Rel A B = A → B → Set

Id : (A : Set) → Rel A A
Id A x y = x ≡ y

Graph : {A B : Set} → (A → B) → Rel A B
Graph f a b = f a ≡ b

happly : ∀{i j}{A : Set i}{B : Set j}{f g : A → B} → f ≡ g → ∀ x → f x ≡ g x
happly refl x = refl

record Functor : Set₁ where
  field
    !      : Set → Set
    map    : {A B : Set} → (A → B) → ! A → ! B
    map-id : ∀ {A} → map {A} id ≡ id
    map-∘  : ∀ {A B C}(f : B → C)(g : A → B) → map (f ∘ g) ≡ map f ∘ map g

record Functorᴿ (F : Functor) : Set₁ where
  private module F = Functor F
  field
    !     : ∀{A₀ A₁} → Rel A₀ A₁ → Rel (F.! A₀) (F.! A₁)
    map   : ∀ {A₀ A₁}(Aᴿ : Rel A₀ A₁){B₀ B₁}(Bᴿ : Rel B₀ B₁)
            (f₀ : A₀ → B₀)(f₁ : A₁ → B₁)(fᴿ : ∀ {a₀ a₁} → Aᴿ a₀ a₁ → Bᴿ (f₀ a₀) (f₁ a₁))
            {fa₀ fa₁} → ! Aᴿ fa₀ fa₁ → ! Bᴿ (F.map f₀ fa₀) (F.map f₁ fa₁)

    idext : ∀ {A} → ! (Id A) ≡ Id (F.! A)

  reflexive : ∀ {A x} → ! (Id A) x x
  reflexive {A} {x} = tr (λ f →  f x x) (idext ⁻¹) refl

module _
  (F G : Functor) (Fᴿ : Functorᴿ F) (Gᴿ : Functorᴿ G) where

  module F  = Functor F   ; module G  = Functor G
  module Fᴿ = Functorᴿ Fᴿ ; module Gᴿ = Functorᴿ Gᴿ

  module _ (η  : ∀ {A} → F.! A → G.! A)
           (ηᴿ : ∀ {A₀ A₁}(Aᴿ : Rel A₀ A₁){fa₀ fa₁}
                 → Fᴿ.! Aᴿ fa₀ fa₁ → Gᴿ.! Aᴿ (η fa₀) (η fa₁)) where

    η-is-natural : ∀ {A B}(f : A → B) x → G.map f (η x) ≡ η (F.map f x)
    η-is-natural {A} {B} f x =
      let lem1 : Fᴿ.! (Graph f) (F.map id x) (F.map f x)
          lem1 = Fᴿ.map (Id A) (Graph f) id f (ap f) {x} {x} Fᴿ.reflexive

          lem2 : Fᴿ.! (Graph f) x (F.map f x)
          lem2 = tr (λ y → Fᴿ.! (Graph f) y (F.map f x)) (happly F.map-id x) lem1

          lem3 : Gᴿ.! (Graph f) (η x) (η (F.map f x))
          lem3 = ηᴿ (Graph f) lem2

          lem4 : Gᴿ.! (Id B) (G.map f (η x)) (G.map id (η (F.map f x)))
          lem4 = Gᴿ.map (Graph f) (Id B) f id id lem3

          lem5 : Gᴿ.! (Id B) (G.map f (η x)) (η (F.map f x))
          lem5 = tr (λ y → Gᴿ.! (Id B) (G.map f (η x)) y) (happly G.map-id _) lem4

      in coe (happly (happly Gᴿ.idext (G.map f (η x))) (η (F.map f x))) lem5

```

# Answer
> 2 votes
$\newcommand{\Type}{\text{Type}}\newcommand{\llb}{\[\\!\[}\newcommand{\rrb}{\]\\!\]}\newcommand{\map}{\text{map}}$

***Note:** This answer is not a standalone answer, but an incomplete attempt to give some intuition for András Kovács's answer.*

One important thing to point out is that is that type constructors are not always functors. In particular, the type constructor

$$F : \Type\to\Type\\ X\mapsto (X\to X)$$ is not functorial because there is no way to map a morphism $$f : A \to B \quad \overset{?}{\mapsto} \quad Ff : (A\to A)\to(B\to B).$$ So the theorem you mention only makes sense when $F$ is a functor. An attempt to generalize this statement to arbitrary type constructors requires generalizing categories, functors, and natural transformations to reflexive graph categories, relational functors, and parametric transformations (see section 6).

---

The parametricity translation is given for types as follows: $$\text{Rel} := \llb \Type \rrb^R = \Type \to \Type \to \Type$$ where it is then a (meta)-theorem of the parametricity translation that whenever $t : A$, then $$\llb t\rrb^R : \llb A \rrb^R(t,t)$$ where $\llb A\rrb^R(t,t)$ is the "free theorem", and $\llb t\rrb^R$ is the proof of this theorem.

In particular this means $$\llb A\to B\rrb^R: \text{Rel} (A\to B,A\to B)\\ \llb A\times B\rrb^R : \text{Rel}(A\times B,A\times B)$$ and we define $$\llb A\to B\rrb^R(f,g) = (x\_0,x\_1:A) \to \llb A\rrb^R(x\_0,x\_1)\to\llb B\rrb^R(f x\_0,gx\_1)$$ $$\llb A\times B\rrb^R(p,q) = \llb A\rrb^R(\pi\_1 p,\pi\_1 q) \times \llb B\rrb^R(\pi\_2 p,\pi\_2 q).$$

A similar definition can be given for dependent function, sum, and equality types, which I use below but I won't define them here. You additionally need to define $\llb\cdot\rrb^R$ for contexts and for terms. If you prefer, The Girard–Reynolds isomorphism (second edition) gives a more mathematical presentation of this translation.

---

So given a functor $F = (F\_!,F\_{\text{map}},F\_{\text{id}},F\_{\circ}) : \text{Functor}$ (as defined by András), we can apply the parametricity translation to get $$\llb F\rrb^R : \llb\text{Functor}\rrb^R(F,F)$$ In particular this means \begin{align\*} \llb F\_!\rrb^R &: \llb\Type\to\Type\rrb^R(F\_!,F\_!)\\ &= (A\_0,A\_1 : \Type)\to \text{Rel}(A\_0,A\_1)\to \text{Rel}(F\_! A\_0,F\_! A\_1) \end{align\*} \begin{align\*} \llb F\_{\map}\rrb^R &: \llb (A,B:\Type)\to(A\to B)\to(F\_! A \to F\_! B)\rrb^R(F\_\map,F\_\map)\\ &=(A\_0,A\_1: \Type)\to(A^R :\text{Rel}(A\_0,A\_1))\to (B\_0,B\_1:\Type)\to(B^R :\text{Rel}(B\_0,B\_1))\\ &\quad\to\llb(A\to B)\to(F\_! A \to F\_! B)\rrb^R(F\_\map (A\_0,B\_0),F\_\map (A\_1,B\_1))\\ &=(A\_0,A\_1: \Type)\to(A^R:\text{Rel}(A\_0,A\_1))\to (B\_0,B\_1:\Type)\to(B^R:\text{Rel}(B\_0,B\_1))\\ &\quad\to(f\_0 :A\_0\to B\_0)\to(f\_1 : A\_1\to B\_1)\to \llb A\to B\rrb^R(f\_0,f\_1)\\ &\quad\to\llb (F\_! A \to F\_! B)\rrb^R(F\_\map (A\_0,B\_0,f\_0),F\_\map (A\_1,B\_1,f\_1))\\ &=(A\_0,A\_1: \Type)\to(A^R:\text{Rel}(A\_0,A\_1))\to (B\_0,B\_1:\Type)\to(B^R:\text{Rel}(B\_0,B\_1))\\ &\quad\to(f\_0:A\_0\to B\_0)\to(f\_1 : A\_1\to B\_1)\to \llb A\to B\rrb^R(f\_0,f\_1)\\ &\quad\to(x\_0,x\_1 : F\_! A)\to \llb F\_! A\rrb^R(x\_0,x\_1) \\ &\quad\to\llb F\_! B \rrb^R(F\_\map (A\_0,B\_0,f\_0,x\_0),F\_\map (A\_1,B\_1,f\_1,x\_1)) \end{align\*}

Where application is defined so that $$\llb F\_! A\rrb^R(x\_0,x\_1) = \llb F\_! \rrb^R(A\_0,A\_1,A^R, x\_0,x\_1)$$

This gives precisely the fields `!,map` for the `Functorᴿ` that András described. My **guess** is that applying this translation to $F\_\text{id}$ should give a generalization of `idext`, *but I have not yet figured out how to do this*. Note that we could do the same for $F\_\circ$, but it is not needed.

---

So now, given *functors* (actually they don't even need to respect composition, since $F\_\circ,G\_\circ$ are never used in the proof) $F,G : \text{Functor}$, and a map $\eta:(A :\Type)\to F\_! A\to G\_! A$, we obtain the following "free theorems": $$\llb F\rrb^R : \llb \text{Functor}\rrb^R(F,F)$$ $$\llb G\rrb^R : \llb \text{Functor}\rrb^R(G,G)$$ and $$\llb\eta\rrb^R : \llb (A :\Type)\to F\_! A\to G\_! A \rrb^R(\eta,\eta)$$

Since the formal construction of these terms is very messy, András instead assumes the existence of $F^R, G^R$, and $\eta^R$ of the appropriate type, and then derives that $\eta$ is a natural transformation, that is

$$A, B : \Type, f: A\to B, x:A\vdash G\_\map(f,\eta(A,x)) = \eta(B,F\_\map(f,x)).$$

# Answer
> 1 votes
You say "as far as I can tell, the parametricity theorem doesn't even allow you to specify the morphism part of the functors ,. It only takes them as type constructors."

What you are missing is the fact that the morphism part of the functors is uniquely fixed by their type, at least in System F (and in many other lambda calculi) where each type constructor can be straightforwardly analyzed to see whether it is covariant, contravariant, or neither. For example, `F a = a -> Int` is contravariant in `a` while `F a = Int -> a` is covariant in `a`.

It is not necessary to specify the morphism part of the functors because it follows automatically from their type.

But Wadler's paper does not talk explicitly about what to do with arbitrary type constructors. Neither Wadler nor Reynolds explain how to define the relations you denote by $f\_F$ and $f\_G$. But the definition of those relations is neither obvious nor always simple.

Wadler also doesn't point out the cases when his "free theorems" are naturality laws of the kind you are writing, and the cases when they are not. It turns out that the "free theorem" for a function $\eta$ of type $\forall A. F\\,A \to G\\,A$ can be written as the naturality law only when $F$ and $G$ are "sufficiently simple" type constructors. Examples are $F$ and $G$ that are purely covariant or purely contravariant. For more complicated types, the "free theorem" can be understood as a more complicated law, which sometimes cannot even be written as a single equation for the function $\eta$.

The main construction you need is a "lifting" of a given relation $r$ between values of types $A$ and $B$, to a relation between values of types $F\\,A$ and $F\\,B$, where $F$ is an arbitrary type constructor. I denote relation types by $r: a \leftrightarrow b$. Then we can write the requirement that we want to have a function "rmap" with the type signature:

$$ \textrm{rmap}\_F : \forall a,b.\\, (a \leftrightarrow b) \to (F\\,a \leftrightarrow F\\,b) $$

This will be a generalization of the "fmap" function whose type signature is:

$$ \textrm{fmap}\_F : \forall a,b.\\, (a \to b) \to (F\\,a \to F\\,b) $$

The "fmap" function is defined only if $F$ is covariant. But the "rmap" function is defined for any $F$ that is defined in System F. However, the technical details of the definition of "rmap" are not easy. Wadler's paper does not write out an adequately detailed definition of "rmap" that you can use for arbitrary $F$. But this can be done.

I don't know if there is any paper or book today that writes out the details and defines everything from the beginning to the end, proving the parametricity theorems and the naturality laws and other laws.

I'm writing such a book but it's not yet ready and is not even about parametricity, so it's probably not what you are looking for. But here's a link anyway: https://github.com/winitzki/sofp \- see Appendix D.

If you take a function $f: a \to b$ and convert it to a relation of type $a\leftrightarrow b$. I denote that relation by $\langle f\rangle$. You can then lift $\langle f\rangle$ via "rmap" to a relation of type $F \\,a\leftrightarrow F\\,b$. But that relation will not always be a function-like relation.

If $F$ is a covariant functor, you *will* obtain a function-like relation that corresponds to lifting $f$ to $F$ via "fmap":

$$ \textrm{rmap}\_F \\,\langle f\rangle = \langle \textrm{fmap}\_F\\,f\rangle $$

This can be proved by induction on the type structure of $F$ although it's not very easy. One can also prove a similar result for contravariant $F$.

Then you can prove, from the relational parametricity theorem, that the function $\eta$ satisfies the equation for its naturality law as you wrote it.

For more complicated types, you will obtain a relation that is many-to-many and is not equivalent to a function. Then it may or may not be possible to write the resulting law as a single equation.

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


# Question
Title: How can we prove that "extract almost minimum" operation in a priority queue cannot be done in o(log n)?
Suppose we want to create a priority queue with 2 operations: insert and extract almost min. Extract almost min operation selects either the first minimum or a second minimum item from the structure randomly, removes that item from the structure and outputs that item.

How can we prove that both of these operations cannot be done in $o(\log n)$?.

My approach: If you could prove that you can sort a list with a comparison based algorithm in $O(n)$ you could prove it by contradiction.

But to sort a list we will need $n$ calls of extract almost min and with $o(log n)$ time which would be $o(n\log n) +$ swaps to fix the elements that are 2nd largest. Would that be enough to prove this contradiction that this is faster than $O(\log n)$?

Or is there a way to sort it in $O(n)$ or prove this?

# Answer
> 1 votes
What you have thought is not a bad start. However, more arguments are needed to establish the proposition.

---

Given $n$ items, we can insert all of them into the priority queue and then extract almost min $n$ times to obtain a list of all items. Unfortunately, the obtained list is not sorted unless the minimum is extracted every time.

#### A mix of heapsort and insertion sort

Here is the adjusted procedure such that the obtained list right before the next extraction is sorted always.

1. Insert all $n$ items into a priority queue $pq$.
2. Initialize an empty list $answer$.
3. While $pq$ is not empty:
    1. Extract almost min to get an "almost minimum" $\alpha$.
    2. Append $\alpha$ to $answer$.
    3. While $\alpha$ is smaller than the item right before it, swap the two.
4. Return $answer$, which is a sorted list of the given $n$ items.

The outer step 3 is just insertion sort but with the next item provided by "extract almost min" operation on $pq$. It is much faster than usual insertion sort, since an item will not be moved any more after it has been moved backwards once as "the item right before" some "$\alpha$". This fact will be proved below in detail.

#### The number of swaps and comparisons at step 3.3

Suppose we executed the procedure. Consider an item $\beta$ in $answer$ that was swapped with some $\alpha$ at some moment when step 3.3 was executed. That means $\alpha$ was extracted later than $\beta$ and $\alpha$ is smaller than $\beta$.

Consider the moment when $\beta$ was output by "extract almost min" on $pq$. Every item in $pq$ other than the minimum was not smaller than $\beta$. Hence, $\alpha$ must be that minimum.

So the same $\beta$ can be swapped with one $\alpha$ only. The swap between the same pair of $\alpha$ and $\beta$ cannot happen more than once, since $\alpha$ moves to the front always and $\beta$ moves to the back always. Hence at most $n-1$ swaps are made at step 3.3 during the whole execution of the procedure.

For each execution of the while loop of step 3.3, every comparison is followed by a swap except the last comparison. So the number of comparisons at step 3.3 during the whole execution of the procedure is $n-1$ more than the number of swaps, i.e., at most $2(n-1)$.

#### Conclusion

Towards a contradiction assume both insertion and extraction can be done in $o(\log n)$ time.

The running time of the procedure above is $$o(n\log n)+o(n\log n)+ O(n)+ O(n) + O(n)=o(n\log n).$$

Note that both big $O$-notation and little $O$-natation are used. However, it is known there is no comparison sort that uses $o(n\log n)$ comparisons. This contradiction means it is not true that both insertion and extraction can be done in $o(\log n)$.

#### An exercise

Prove the same proposition if "almost min" is defined as any one of the $m$ minimum items for some constant $m$ instead.

# Answer
> 0 votes
It's not enough yet, because you haven't described how to sort in $o(n \log n)$ time -- in particular, you haven't described how to do the swaps in $o(n \log n)$ time. But yes, if you could figure out how to do that, then that *would* be enough.

---
Tags: algorithms, data-structures, algorithm-analysis, runtime-analysis, priority-queues
---


# Question
Title: Efficiently find the distance from a point to the decision boundary for assigning points to a particular $k$-means cluster
I have run $k$-means on a large set of high-dimensional data, and now I want to find the distance from a point $x$ to the Voronoi cell associated with one of the $k$ centroids. (In a previous version of the question, I called this cell a "cluster", but that terminology might be confusing since one might think of a cluster as simply a set of points in the dataset.)

Can this be done efficiently? If not, can I efficiently approximate it? If I actually need the distance from the point to all $k$ Voronoi cells, is there anything faster than just running the point-to-cell distance computation $k$ times?

Also, I am not wedded to $k$-means. Actually, the question could be interesting for many types of clustering, and I would love to know about others too!

# Answer
> 1 votes
If you want to compute distance to the closest (different) cluster, then problem is $\Theta(kd)$ as you just need to compute distance to $k$ hyperplanes. However, if you want to compute distance (of a point $p$) to a general cluster, you need to solve a Quadratic program (QP). Voronoi cell is a solution to a set of linear inequalities, say $\\{x | Ax \leq b\\}$. Then the quadratic program is: $$ \min ||x-p||^2$$ $$ s.t. Ax \leq b.$$

It is a convex quadratic program in a general form. Generally, they are all different and solving one does not help with solving the others. If you implement this yourself, you can however benefit from warm restarts. When you know the closest point in one Voronoi cell, the closest point in the neighbouringcell is likely to be very close (or even the same point.)

In 2d I'm pretty sure it can be done in an efficient way using some smart data structure and algorithm, but I would be very surprised if there is an easier solution than I described in dimension d \> 3 (for d = 3 I have no opinion).

---
Tags: algorithms, computational-geometry, clustering
---


title: Dijkstra as a greedy algorithm

text:
# Question
Title: Dijkstra as a greedy algorithm
I'm preparing some material for students about greedy algorithms, and there is one point that confuses me: how Dijkstra's algorithm fits into the greedy framework.

I would like to say that we have some optimization problem $\min\_{S \in D} f(S)$. E.g.:

* For MST, $S$ is a spanning tree and $f(S) = \sum\_{e \in S} w(e)$
* For the shortest path problem, $S$ is a path $s \to \ldots \to t$ and $f(S) = \sum\_{e \in S} w(e)$

Now, I want to say that we construct $S$ one element at a time, selecting the "best" "available" element at every step. E.g. for MST, we select the shortest edge which doesn't create a cycle.

This approach doesn't seem to work for Dijkstra: we don't construct a path to $t$ one element at a time. For a lot of Dikstra's iterations, we process elements that are not on the shortest path. Exactly which nodes should be used for the shortest path, we'll know only when we reach $t$.

I do see a way to argue that Dijkstra is a greedy algorithm: instead of the shortest path problem, we should consider the **all** shortest path problem: finding shortest paths from $s$ to all vertices. However, in this case, the objective function $f$ is not clear: we have $|V|$ objectives (one for each vertex), not a single objective (for this problem, we can consider a sum of these functions, but this will only confuse the students). Since we don't have a single objective, an explanation of what we mean by "locally optimal" choice also becomes complicated.

So, what's my problem? Did I narrow the greedy algorithms too much by considering only optimization problems? In this case, what is a proper framework? Or is Dijkstra not a greedy algorithm?

# Answer
Yes, instead of the shortest path problem, we should consider the all shortest path problem or, more precisely, single-source shortest-paths (SSSP) problem. For SSSP, given node $s$, the objectives are $\min\_{S\_v} f(S\_v)$ for all $v\in V$, where $S\_v$ is a path $s \to \ldots \to v$ and $f(S\_v) = \sum\_{e \in S\_v} w(e)$.

That must be a correct approach to introduce Dijkstra's algorithm since finding all shortest paths from one source *could have been* the given problem. You would not even have a choice then.

A basic idea illustrated by Dijkstra's algorithm is it is often easier to solve many related problems together instead of solving one isolated problem. It is of great educational value to instill and emphasize that idea early on.

Once we have a bunch of related problems, the next natural step is to find which one of them might be the easiest to attack. Or what is the easiest computation that can be done to solve one of those problems.

In the case of SSSP, the node that is nearest to the source can be computed easily. Knowing the source and that node, can we compute "next shortest path"? And so on to extend the frontier of our knowledge (pun intended). That seems the natural way to introduce Dijkstra's algorithm.

We can say that we will construct $S\_v$'s that reach the respective objectives one edge at a time, selecting the "best" "available" element at every step, i.e., selecting the "unsettled" node that is "nearest" to the source at every step. So, the algorithm is greedy. A twist here is that we will end up with a different destination node $v$ at each step. It happens that the algorithm will find the optimal solutions to all objectives, producing a shortest-path tree.

Explaining a greedy algorithm using a single quantitative object to newcomers is a laudable idea. It might not be the best approach for this case, though.
> 2 votes

---
Tags: optimization, greedy-algorithms, dijkstras-algorithm
---