# Question
Title: When scheduling intervals across multiple resources, why sort?
I am reading this book and am at a point when the **Interval Partitioning Problem** is discussed. The pseudocode they provide for it is the following:

```
Sort the intervals by their start times, breaking ties arbitrarily
Let I_1, I_2, ..., I_n denote the intervals in this order
For j = 1, 2, 3, ..., n
    For each interval I_i that precedes I_j in sorted order and overlaps it
        Exclude the label of I_i from consideration for I_j
    Endfor
    If there is any label from {1, 2, ..., d} that has not been excluded then
        Assign a nonexcluded label to I_j
    Else
        Leave I_j unlabeled
    Endif
Endfor

```

Here **n** is the number of intervals and **d** is the depth of the intervals (the maximum number of overlapping intervals)

What I don't understand is why sort the intervals in the first place. I think the algorithm would work even without this step. In other words, it would work no matter the order of I\_1, I\_2, ..., I\_n. Am I correct? Is there something I am missing?

EDIT: Doesn't the algorithm below also produce an interval partitioning, but with the advantage of being faster because no sorting is performed?

```
Let I_1, I_2, ..., I_n be an arbitrary ordering of the intervals.
For j = 1, 2, ..., n
    For each interval I_i where 1 <= i < j which overlaps with I_j
        Exclude the label of I_i from consideration for I_j
    Endfor
    If there is any label from {1, 2, ..., d} that has not been excluded then
        Assign a nonexcluded label to I_j
    Else
        Leave I_j unlabeled
    Endif
Endfor

```

# Answer
> 1 votes
1. **Why sorting?** One reason is efficiency: the algorithm can easily be improved to run in time $O(nd + n \log n)$ instead of $O(n^2)$. The other reason is that it is not immediately clear (at least not to me) what label to assign to intervals when processing them out of order: you may get yourself stuck later on.

**Here is why it's faster**: By iterating over the intervals in order of increasing start time, we can limit the inner for-loop to `d` iterations. Since all intervals that precede `I_j` have already been considered in an iteration of the outer for-loop before the current iteration, we know these intervals are already 'scheduled': they have a label assigned to them. Since there are only `d` labels, there are only `d` intervals (namely the latest for each label) that can possibly overlap with `I_j`. The inner for-loop only needs to look at these `d` intervals for each iteration of the outer for-loop, resulting in a total running time of $O(nd)$ after sorting ($O(n \log n)$ time).

The line `For each interval I_i that precedes I_j in sorted order and overlaps it` does not clearly capture this. Instead the algorithm should keep track of the set of intervals containing for each label the most recently encountered interval labelled as such. The inner for-loop should iterate over this set, containing only $d$ intervals.
2. Your second algorithm in it's current form is **not correct**, in that it does not always find an optimal solution. Consider the three intervals $\\{(1,2),(3,4),(1,4)\\}$ which can be partitioned in two sets of pairwise disjoint intervals: $\\{(1,2),(3,4)\\}$ and $\\{(1,4)\\}$, i.e. the algorithm should find a label for all intervals when $d=2$. When your second algorithm takes these intervals in order $\langle(1,2),(3,4),(1,4)\rangle$ it may do the following:

1. For interval $(1,2)$ labels 1 and 2 are available (none of the preceding intervals overlap, because there are no preceding intervals). We choose label 1.
    2. For interval $(3,4)$ labels 1 and 2 are available (none of the preceding intervals ($\\{(1,2)\\}$) overlap). We choose label 2.
    3. For interval $(1,4)$ all preceding intervals overlap, no labels are available. The algorithm fails to label this interval.

# Answer
> 0 votes
Efficiency considerations. Nested for loop shall traverse overlapping intervals, started earlier, then given one. If you will not pre-sort intervals, you will need traverse whole set to look them up.

---
Tags: algorithms
---


title: Meaning of L* if L is a language

text:
# Question
Title: Meaning of L* if L is a language
I can't find anywhere the meaning of $L^\*$, given that $L$ is a language. I know $^\* $ means repetition, for example $0^\*$ = $\\{ \epsilon, 0, 00, 000, \dots \\}$. Or if $A$ is an alphabet $A^\*$ are all the possible words.

Does $L^\*$ mean the language whose words are the concatenation of the words of $L$?

For example if $L=\\{ 01^n \mid n\>0 \\}$

then is $L^\* = \\{ 01^{n\_1}01^{n\_2} \dots \mid n\_1\>0, n\_2\>0, ... \\} $?

# Answer
Given a language $L$, let $L\_0 = \\{\epsilon\\}$ and, for $i\geq 1$, let $L\_i = \\{w\_1\circ \dots\circ w\_i \mid w\_j\in L \text{ for each } j\\}$, where $\circ$ denotes concatenation. Then the *Kleene closure* of $L$ is the language $L^\* = \bigcup\_{i\geq 0} L\_i$.
> 2 votes

---
Tags: regular-languages, notation, kleene-star
---


# Question
Title: Can constraint satisfaction problems be solved with Prolog?
Is "party attendance" type of problems solvable in Prolog? For example:

> Burdock Muldoon and Carlotta Pinkstone both said they would come if Albus Dumbledore came. Albus Dumbledore and Daisy Dodderidge both said they would come if Carlotta Pinkstone came. Albus Dumbledore, Burdock Muldoon, and Carlotta Pinkstone all said they would come if Elfrida Clagg came. Carlotta Pinkstone and Daisy Dodderidge both said they would come if Falco Aesalon came. Burdock Muldoon, Elfrida Clagg, and Falco Aesalon all said they would come if Carlotta Pinkstone and Daisy Dodderidge both came. Daisy Dodderidge said she would come if Albus Dumbledore and Burdock Muldoon both came. Whom is needs to be persuaded to attend the party in order to ensure that all her invitees attend?

I have tried to express this in GNU Prolog:

```
attend(BM) :- attend(AD).
attend(CP) :- attend(AD).
attend(AD) :- attend(CP).
attend(DD) :- attend(CP).
attend(AD) :- attend(EC).
attend(BM) :- attend(EC).
attend(CP) :- attend(EC).
attend(CP) :- attend(FA).
attend(DD) :- attend(FA).
attend(BM) :- attend(CP),attend(DD).
attend(EC) :- attend(CP),attend(DD).
attend(FA) :- attend(CP),attend(DD).
attend(DD) :- attend(AD),attend(BM).

attend(FA). /* try different seed invitees in order to see if all would attend*/

/* input:
write('invited:'),nl,
  attend(X),write(X),nl,
  fail.*/

```

I'm experiencing stack overflow (no pun), and have no knowledge of prolog evaluation, this is why I'm asking.

Generally speaking, this problem can be cast into Boolean CNF satisfaction formula (with 6 boolean variables). Therefore, does the prolog perspective have any merit?

# Answer
To solve a problem with Prolog, as with any programming language, be it declarative or imperative, you have to think about the representation of the solution and the input.

Since this is a programming question, it would've been popular on StackOverflow.com where programmers solve programming problems. Here I would attempt to be more scientific.

To solve the problem in the OP one has to reverse the relation defined by the dependencies stated in the input. Clauses of the form $Attend(X) \to Attend(Y) \wedge Attend(Z)$ are easy to reverse. The clauses $Attend(AD)\wedge Attend(BM)\to Attend(DD)$ like

> Daisy Dodderidge said she would come if Albus Dumbledore and Burdock Muldoon both came

are more difficult to treat.

With Prolog the first simple approach is to avoid a full reversal of the relationship and be goal directed instead.

Assume an ordering on the list of guests and use a rule

$\qquad \left\\{\begin{align} A(X)\wedge A(Y) &\to A(Z), \\ A(W)&\to A(X), \\ A(W)&\to A(Y), \\ X&\<Z, \\ Y&\<Z\end{align}\right\\}\quad \vdash \quad A(W) \to A(Z)$

(We use $A(X)$ instead of $Attend(X)$ to keep it short)

This rule is easy to implement.

**A rather naive approach**

For readability let `follows` be the relation given as an input, and `brings` be its reverse.

Then the input is given by

```
follows(bm,[ad]).
follows(cp,[ad]).
follows(ad,[cp]).
follows(dd,[cp]).
follows(ad,[ec]).
follows(bm,[ec]).
follows(cp,[ec]).
follows(cp,[fa]).
follows(dd,[fa]).
follows(bm,[cp,dd]).
follows(ec,[cp,dd]).
follows(fa,[cp,dd]).
follows(dd,[ad,bm]).

```

And `brings` can be defined as follows:

```
brings(X,S):-brings(X,S,[]).

brings(_X,[],_S).
brings(X,[X|L],S):-brings(X,L,[X|S]).
brings(X,[Y|L],S):-follows(Y,[X]),brings(X,L,[Y|S]).
brings(X,[Y|L],S):-follows(Y,[A,B]),
          member(A,S),member(B,S),brings(X,L,[Y|S]).

```

Here the third argument in `brings/3(X,L,S)` is the list of guests that were already proven to attend if $X$ attends.

If we define

```
 partymaker(X):-Guests=[ad,bm,cp,dd,ec,fa],member(X,Guests),brings(X,Guests).

```

We get the following unique solutions:

```
 [ad,ec]

```

This is not the complete list, since under the alphabetical ordering the clause

```
 follows(bm,[cp,dd]).

```

is not working.

**A rather involved solution to the original puzzle**

To solve the problem completely you have to actually let the system try to prove attendance for later guests without introducing infinite loops to the search tree. There are multiple ways to accomplish this goal. Each has its advantages and disadvantages.

One way is to redefine `brings/2` as follows:

```
brings(X,S):-brings(X,S,[],[]).

% brings(X,RemainsToBring,AlreadyTaken,AlreadyTried).
%
% Problem solved
brings(_X,[],_S,_N).
% Self
brings(X,[X|L],S,N):-brings(X,L,[X|S],N).
% Follower
brings(X,[Y|L],S,N):-follows(Y,[X]),brings(X,L,[Y|S],N).
% Y is not a follower, but X can bring 2
brings(X,[Y|L],S,N):- \+member(Y,N),\+follows(Y,[X]),
                   follows(Y,[A,B]),
                   try_bring(X,A,L,S,[Y|N]),
                   try_bring(X,B,L,S,[Y|N]),brings(X,L,[Y|S],N).
% Y is not a follower, but X can bring 1
brings(X,[Y|L],S,N):- \+member(Y,N),\+follows(Y,[X]),\+follows(Y,[_A,_B]),
                   follows(Y,[C]),
                   try_bring(X,C,L,S,[Y|N]),brings(X,L,[Y|S],N).

try_bring(_X,A,_L,S,_N):-member(A,S).
try_bring(X,A,L,S,N):- \+member(A,S),sort([A|L],Y),brings(X,Y,S,N).

```

The last argument in `brings/4` is necessary to avoid an infinite loop in `try_bring`.

This gives the following answers: Albus, Carlotta, Elfrida and Falco. However this solution is not the most efficient one since backtracking is introduced where it sometimes can be avoided.

**A general solution**

After the link to the Third International NoCOUG SQL & NoSQL Challenge was added to the original question, it became clear that what we are after is a general reachability checker on the set of subsets of the set of guests, where the transition relation is defined by rules given such that an application of the rule $r(X,S): V \to V'$ is a guarded command:

> if $S \subseteq V$ then $V' = V \cup \\{X\\}$.

We are interested in the minimal subsets $V$ such that the whole set $U$ of guests is reachable from $V$ after a finite sequence of rule applications.

```
add_element(X,V,U):- ( var(V) -> % set difference that works in both modes
                           member(X,U),subtract(U,[X],V);
                      \+member(X,V),sort([X|V],U) ).

support(V,U):- guests(G), % rule application
               member(X,G),
               add_element(X,V,U),
               follows(X,S),
               subset(S,V).

set_support(U,V):- support(V1,U), % sort of a minimal set
               ( support(_V2,V1) ->
                      set_support(V1,V) ;
                 V = V1).

is_duplicate(X,[Y|L]):- ( subset(Y,X) ; is_duplicate(X,L) ).

% purging solutions that are not truly minimal
minimal_support(U,L):-minimal_support(U,[],L).
minimal_support([],L,L).
minimal_support([X|L],L1,L2):-( append(L,L1,U),is_duplicate(X,U) ->
                                    minimal_support(L,L1,L2);
                                minimal_support(L,[X|L1],L2) ).

solution(L):- guests(G),setof(X,set_support(G,X),S),
              minimal_support(S,L).

```

Now if for instance dataset #2 is given as

```
follows(fa,[dd,ec]).
follows(cp,[ad,bm]).
guests([ad,bm,cp,dd,ec,fa]).

```

We get the answer L = \[\[ad, bm, dd, ec\]\]. Which means that all guests but Carlotte and Falco must be invited.

The answers this solution gave me matched the solutions given in the Wicked Witch article with the exception of dataset #6, where more solutions were produced. This seems to be the correct solution.

Finally, I must mention the CLP(FD) library of Prolog that is particularly suitable for this sort of problems.
> 12 votes

# Answer
As spotted by svick, the first issue with the code in the OP is that names beginning with upper-case letters are variables in Prolog. So `admit(CP) :- admit(AD)` is equivalent to `attend(X) :- attend(Y)`, which results in Prolog immediately entering an infinite loop trying to demonstrate that `attend` holds for some term by finding some term for which `attend` holds.

However, if you meant each set of initials to be a concrete distinct term, then you'll still run into a stack overflow because you have cycles, e.g.

```
attend(cp) :- attend(ad).
attend(ad) :- attend(cp).

```

So to work out whether `attend(cp)` holds Prolog will try to determine whether `attend(ad)` holds, which it will do by checking whether `attend(cp)` holds, and so on until stack overflow.

I don't believe vanilla Prolog makes any attempt to determine whether there is such a cycle, and examine *other* ways to make one of `attend(cp)` or `attend(ad)` true rather than get stuck in an infinite loop.

There may or may not be versions of Prolog that support such a feature. I'm more familiar with Mercury, and I think Mercury's "minimal model tabling" is exactly what you need for this case. I've never actually used it, but my understanding is it more-or-less allows a term that implies itself to be considered true if there is some other way of proving it, or false otherwise, without getting caught in an infinite loop. See the relevant section of the Mercury docs, and if you're interested a paper describing the implementation.

Mercury is an enforced-purity logical programming language, with similar syntax to Prolog but strong type and mode systems, and it's compiled rather than interpreted.

I've just re-skimmed the introduction to the paper (which I haven't read in a while), and it mentions tabling having been implemented in several versions of Prologs, so it may be that you can get further by googling for tabling in Prolog.
> 9 votes

# Answer
I found the following paper on SAT solving using prolog:

An implementation of the solver can be found here.

See this stackoverflow answer for details on the code and how to use it.
> 4 votes

# Answer
Putting aside the lowercase/uppercase issue, there is a cycle in the clauses:

```
attend(cp) :- attend(ad).
attend(ad) :- attend(cp).

```

So when you call a top-down interpreter, it will loop. You might have more luck with Answer Set Programming (ASP), which works bottom up. Here is a coding via library(minimal/asp):

```
:- use_module(library(minimal/asp)).

choose([admit(bm)]) <= posted(admit(ad)).
choose([admit(cp)]) <= posted(admit(ad)).
choose([admit(ad)]) <= posted(admit(cp)).
choose([admit(dd)]) <= posted(admit(cp)).
choose([admit(ad)]) <= posted(admit(ec)).
choose([admit(bm)]) <= posted(admit(ec)).
choose([admit(cp)]) <= posted(admit(ec)).
choose([admit(cp)]) <= posted(admit(fa)).
choose([admit(dd)]) <= posted(admit(fa)).
choose([admit(bm)]) <= posted(admit(cp)),posted(admit(dd)).
choose([admit(ec)]) <= posted(admit(cp)),posted(admit(dd)).
choose([admit(fa)]) <= posted(admit(cp)),posted(admit(dd)).
choose([admit(dd)]) <= posted(admit(ad)),posted(admit(bm)).

choose([admit(fa)]) <= posted(init).

```

Here is an example run:

```
Jekejeke Prolog 3, Runtime Library 1.3.8 (23 May 2019)

?- post(init), listing(admit/1).
admit(fa).
admit(cp).
admit(ad).
admit(bm).
admit(dd).
admit(ec).

```
> 0 votes

---
Tags: logic, constraint-programming, prolog, logic-programming
---


# Question
Title: How to prove the language of Turing machines that run at most $4|x|^2$ steps is not recursive?
I am trying to prove that the language

$$ L=\\{M\mid M\text{ is a TM and for all }x\in \Sigma^\*\text{ with }|x|\>2, M\text{ on }x\text{ runs at most }4|x|^2\text{ steps}\\} $$

belongs to **Co-RE** but not **R**.

Showing $\overline{L}\in$ **RE** is pretty much straightforward, but I also want to show that $L\notin$ **R**.

My idea was a reduction $\overline{H\_{\text{TM}}}\le\_mL$ but I struggle to figure out how to do it.

Any help/guidance will be much appreciated.

# Answer
**Preparation**

Since we are talking about the exact number of steps run by a Turing machine (TM), a fixed formal definition of TM is in order. This answer assumes the popular definition of a one-tape Turing machine as in Hopcroft and Ullman (1979, p. 148).

Let $N(w) \downarrow$ denote $N$ on $w$ halts eventually. Let $N(w) \uparrow$ denote $N$ on $w$ never halts.

You have done the initial analysis correctly, pointing out a reasonable solution could be constructing a reduction $\overline{H\_{\text{TM}}}\le\_mL$. That is, for a TM $N$ and a word $w$, we should construct a Turing machine $M\_{N,w}$ such that $$N(w) \uparrow\ \Leftrightarrow\ \langle M\_{N,w}\rangle\in L.$$

For simpler notation, we will write $M$ to mean $M\_{N,w}$.

**Outline of the construction**

Basically, we will let $M$ on input $x$ simulate $N$ on $w$ for $|x|$ steps. In case when $N$ on $w$ halts eventually, we will let $M$ run forever when the input is long enough.

**Detailed explanation**

The basic intuition is that $M$ will have to simulate $N$ on $w$ in some way since the only way to find whether $N$ on $w$ halts eventually is to run $N$ on $w$.

1. The first problem is the input to $M$ can be any word, which has probably nothing to do with $w$. On the other hand, how long $M$ may run depends on the length of the input.

Here is a simple approach. We will let $M$ compute how long the input is but ignore the actual content of the input otherwise. Moreover, $w$ will be encoded in the specification of $M$ so that $M$ will be able to put $w$ on the tape, which can be treated as the input to the simulated $N$.
2. The next problem is how to ensure $\langle M\rangle\in L$ if $N(w) \uparrow$. Assume $N(w)\uparrow$.

1. For short input, $M$ cannot be running too long for $\langle M\rangle$ to be in $L$.

    The idea to prevent $M$ from running too long is simple. $M$ will halt once it has done reading the input if the input is not long. More specifically, let $M$ have state $s\_0$, $s\_1$, $\cdots$, $s\_{t}$ for some $t$ where $s\_0$ is the start state. When $M$ in state $s\_i$ reads a cell, it halts if the cell means the end of input. Otherwise it advances to the next cell, updating its state to $s\_{i+1}$. So, on every input $x$ of length at most $t$, $M$ will halt in $|x|+1$ steps, which is less than $4|x|^2$ steps.

    Note that we can set $t$ to an arbitrary positive integer.

    Also note that the action above will be performed regardless of whether the input is short or not, since $M$ doesn't know whether the input length is less than or equal to $t$ beforehand.
    2. The next problem is how to prepare $M$ for simulating $N$ on $w$ once it has reached state $s\_t$, which will happen if $|x|\>t$.

    $M$ should store the length of input while erasing the input. Here are the details.

    1. First it goes back to the start of the input. We will refer this cell as $S$.
        2. Write 0 to the left of $S$.
        3. Switch direction to erase the first symbol of the input.
        4. Switch direction to change 0 to 1.
        5. Switch direction to erase the first symbol of the remaining input.
        6. Switch direction to change 1 to 10, which is 2 in binary representation.
        7. Switch direction to erase the first symbol of the remaining input.
        8. Switch direction to change 10 to 11, which is 3 in binary representation.
        9. And so on until $M$ passes the end of the input, at which time the non-blank symbols to the left of $S$ is the length of the original input in binary representation.
        10. $M$ goes back to $S$. Switch direction to write $w$ on the tape. Switch direction to go to $S$.

    All 10 items above can be done by $M$ in $c(x)\<|x|^2+O(|x|)$ steps for input $x$. We can set $t$ to be large enough so that $c(x)+|x|+1\<\frac32|x|^2$ for all input $x$ with $|x|\gt t$. The "$|x|+1$" at the left hand side of the inequality comes from the previous item.
    3. How should $M$ simulate $N$ on $w$ as well as maintain the number to the left of $w$ on the tape so that $M$ will not be running too many steps?

    Thanks to the number $|x|$ to the left of $w$ on the tape, we can let $M$ simulate $N$ on $u$ for $|u|$ steps and then halt. Note that at the end of item 2.2.10, $M$ should be in a state that corresponds to the start state of $N$. The head of $M$ is on the top of $S$, which is the first of the cells whose content is $w$. Now we let $M$ loop the following.

    1. Read the current symbol.
        2. If the current symbol is the last binary digit of that number, it means the simulated $N$ is supposed to read a blank symbol. So, let $M$ move all symbols to its right one cell to the right as well as setting $S$ to the blank symbol at last. Now $M$ should be on top of $S$, a blank symbol. Let $M$ read $S$, the (new) current symbol.
        3. Simulate $N$ on the current symbol. Mark the (new) current symbol.
        4. Move to the left of S. Decrease the number by 1.
        5. If the number is 0, break the loop. Otherwise, go back to the marked symbol and start a new round of the loop.

    This stage, stage 3 can be done in at most $\frac52|x|^2$ steps.

In summary, $M$ will run at most $4|x|^2$ steps regardless whether $|x|\le t$ or $|x|\gt t$, as long as $N(w)\uparrow$.
3. The last problem is how to ensure $\langle M\rangle\notin L$ if $N(w) \downarrow$.

$M$ must always be run as specified in item 2 above since $M$ does not know whether $N$ on $w$ will halt eventually or not beforehand. However, what $M$ should do is not specified at the moment when the simulated $N$ on $w$ halts. That will happen when the length of the input to $M$ is larger than the number of steps $N$ will have run before halting. Well, in that case, we will let $M$ just loop forever, which ensures that $\langle M\rangle\notin L$.

## Exercises

**Exercise 1.** Explain that the reduction above can be algorithmic. In particular, the value of $t$ in item 2.2 can be determined algorithmically.

**Exercise 2.** Explain why $L\_{2019}=\\{M\mid M$ $\text{is a TM and for all}$ $x\in \Sigma^\*$, $M\text{ on }x$ $\text{runs at most}$ $\max(2019,\dfrac{|x|^2}{2019})$ $\text{ steps}\\}$ is also undecidable.

**Exercise 3.** Show that $\\{\langle M\rangle\mid M$ $\text{is a TM that halts in }$ $O(n^2+1)\text{ steps where}$ $n$ $\text{ is the length}$ $\text{ of the input}\\}$ is undecidable.
> 0 votes

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


# Question
Title: Is the certificate for primality testing polynomial in the length of the input?
If we were to assume that primality testing was in NP.

What would the certificate be, so that a polynomial time verifier can check the number X is indeed prime?

# Answer
Before it was proven that primality is in P, it was known that a complete factorisation if n-1 could be used to prove primality of n. Now this also requires a proof that all factors in the claimed factorisation are actually themselves primes; this leads to a O(n^2) size certificate.

Google for “Pratt certificate”.

(When you use a certificate to solve a problem in NP, you cannot just “trust” the certificate. So if I tell you “here is a complete factorisation if n-1”, you can’t just believe that. You’d have to check that the product of the factors is actually n-1, which is easy. But you’d also have to check that each of the numbers that I claim are prime factors are actually prime, so you need a certificate for primality of these smaller numbers as well)..
> 4 votes

# Answer
The $\mathsf{PRIMES}$ problem is in $\mathsf{P}$, so it can be decided by a TM in polynomial time. This means that *any certificate* suffices, in particular even the empty string, since the verifier (which is a poly-time TM) can simply ignore the certificate and check membership directly.
> 2 votes

---
Tags: np
---


# Question
Title: Separating numbers with a minimal difference
Given is a positive integer integer $n$, and integers $a\_1,b\_1,\dots,a\_n,b\_n$ with $ a\_i\leq b\_i$ for each $i$. What is the complexity of deciding whether there exist integers $c\_1,\dots,c\_n$ such that $a\_i\leq c\_i\leq b\_i$ for all $i$ and $|c\_i-c\_j|\geq 2$ for all $i,j$?

What can be observed is that a greedy algorithm, wherein we assume that $a\_1\leq\dots\leq a\_n$ and choose $c\_i$ according to this order, does not necessarily work. For example, we may have $a\_1=1, b\_1=4, a\_2=b\_2=2$. Putting $c\_1=1$ does not work (it leaves no room for $c\_2$), but what works is putting $c\_1=4$ and $c\_2=2$. Is the problem perhaps NP-hard?

# Answer
> 5 votes
As shown in the previous answer, this problem can be modeled as a scheduling problem with release and due dates. However, Schrage's heuristic works only for the case $p\_j=1$ (all processing times are $1$) or when release and due dates agree (i.e. there is an order such that $r\_1\leq\cdots\leq r\_n$ and $d\_1\leq\cdots\leq d\_n$).

For the case $p\_j=p$ polynomial algorithms have been found by Simons (1978), Carlier (1981), and Garey et al. (1981), running in time $O(n^2\log n)$, $O(n^2\log n)$, and $O(n\log n)$, respectively.

The algorithm of Garey et al. schedules unit-time tasks, but allows arbitrary release and due dates. The above problem can be reduced to this setting by dividing all dates and processing times by $p$. The main idea of the algorithm is to find a set of *forbidden regions* where no task is allowed to start. They show that Schrage's heuristic when respecting forbidden regions finds a feasible schedule of minimal makespan. When constructing the forbidden regions their algorithm may also detect infeasibility.

To see how the algorithm works, first look at a simpler problem: schedule $n$ unit-time tasks between a release date $r$ and a deadline $d$ respecting forbidden regions $F=\bigcup\_i (a\_i,b\_i)$, where each region $(a\_i,b\_i)$ is an open interval. (Note here we're not concerned with release and due dates of individual tasks.)

This problem can be solved by *Backscheduling*: define a sentinel starting time $s\_{n+1}=d$, and for $i=n,n-1,\ldots,1$ set starting time $s\_i$ to the latest time not later than $s\_{i+1}-1$ that is not forbidden.

Write $B(r,d,n,F)$ for an application of Backscheduling for the above inputs, and define the return value as $s\_1$, the latest possible starting date for scheduling the $n$ tasks. Now, if $B(r,d,n,F)\<r$ there is no feasible schedule for the $n$ tasks. Further, if $r\leq B(r,d,n,F)\<r+1$ no other task can start in $(B(r,d,n,F)-1,r)$ since otherwise there is again no feasible schedule for the $n$ tasks, and thus $(B(r,d,n,F)-1,r)$ can be declared a forbidden region.

It turns out that this logic is sufficient to find all forbidden regions that are required to make Schrage's heuristic work. Assume that tasks are ordered such that $r\_1\leq r\_2\leq\cdots\leq r\_n$ and write $n(r,d)$ for the number of tasks which are released and due in the closed interval $\[r,d\]$.

1. set $F=\emptyset$
2. for tasks $i=n,n-1,\ldots,1$:
3. $c=\min \\{ B(r\_i,d\_j,n(r\_i,d\_j),F) \mid \forall j: d\_j\geq d\_i\\}$
4. if $c\<r\_i$: return "no feasible schedule"
5. else if $r\_i\leq c\<r\_i+1$: set $F=F\cup\\{(c-1,r\_i)\\}$

A straightforward implementation as above would take time $O(n^4)$. Garey et al. show (besides correctness) that by updating the times obtained by Backscheduling, joining overlapping forbidden regions, and making "forbidden" queries $O(1)$ time can be brought down to $O(n^2)$, and by using even better datastructures to $O(n\log n)$.

# Answer
> 0 votes
Your problem is known as non-preemptive single-machine scheduling with release times and deadlines, with tasks of identical length, and can be solved efficiently using Schrage's greedy heuristic.

Let us first describe the problem more formally. We are given a sequence of time intervals $\[r\_i,d\_i\]$ and a sequence of job lengths $p\_i$. We want to schedule each job within its interval, so that no two jobs intersect.

In our case $r\_i = a\_i$, $d\_i = b\_i + 2$, and $p\_i = 2$. The starting time of each job $c\_i$ thus satisfies $a\_i \leq c\_i \leq b\_i$, and two jobs conflict if $(c\_i,c\_i+2)$ intersects $(c\_j,c\_j+2)$, which is the same as $|c\_i - c\_j| \< 2$. (Without loss of generality, all jobs are scheduled at integer times.)

Schrage's heuristic is a common heuristic which is optimal in some cases, though not necessarily this one. However, other algorithms exist in the literature which do solve this problem efficiently.

# Answer
> 0 votes
Let A be the smallest of the $a\_i$. Then there are two choices for the first $c\_i$ to pick that cannot obviously be improved: One, find the i such that $a\_i = A$ and $b\_i$ is as small as possible, then let $c\_i = a\_i$. Two, pick j such that $a\_j = A+1$, $b\_j\<b\_i$, and $b\_j$ as small as possible, then let $c\_j=b\_j$ (this may not be possible). Then remove that item from the list of intervals, update all $a\_i$ to be greater by two than the $c\_i$ that was picked, and check that no $b\_i$ is too small. Depth first search and backtracking will find a solution.

There is a good chance that this is fast, since the first choice is not bad as a heuristic.

If there are exactly k intervals with $a\_i \< A$ for some A, and we find k values $c\_i \<= A-2$ then these $c\_i$ are optimal and backtracking for these k items cannot help and will never be needed. On the other hand, if there are too many values $b\_i$ too close together, that can be used to prove there is no solution.

Finally, the problem can be approached from the smallest $a\_i$, or equally well from the largest $b\_i$.

---
Tags: algorithms, np-hard
---


# Question
Title: L(M)=L where M is a TM that can move right or stay, so L is decidable
Suppose that L(M)=L where M is a one tape TM that can move right or stay.

I need to Show that L is decidable.

I thought of reducing a PDA to this TM, since moving to the right is equivalent to popping and pushing some new symbol to the stack. and staying is the same as not touching the automata at all. but im not sure this is correct.

# Answer
As dkaeae indicated in his comment, a right-moving or staying Turing machine (TM) is essentially a finite deterministic automaton (FDA). Here's a proof.

Let $M$ be such a machine, whose transition rules is in the form of $\delta(q, \gamma)=(t, \beta, d)$ where $q$ is the current state, $\gamma$ is the contents of the current cell, $t$ is the new state, $\beta$ is the symbol that replaces $\gamma$ in the current cell, and $d$ is the direction to move the head, which is either $R$ or $S$, meaning moving right or staying put respectively.

Let us check the behavior of $M$ when it has just applied a transition rule of the form $\delta(q, \gamma)=(t, \beta, S)$. Now $M$ is in state $t$ on top of $\beta$. In the next step, $M$ will read the symbol $\beta$, applying the unique rule on the pair $(t,\beta)$.

1. Suppose that rule is $\delta(t, \beta)=(u, \alpha, d)$.

Then $M$ will change state to $u$, rewrite the current cell to $\alpha$ and move in the direction of $d$.

We have found that once $M$ was in state $q$ on top of $\gamma$, it will change state to $u$, rewrite the current cell to $\alpha$ and move in the direction of $d$.

So we can replace the transition rule $\delta(q, \gamma)=(p, \beta, S)$ by $\delta(q, \gamma)=(u, \alpha, d)$ in the specification of $M$ without changing the language accepted by $M$.
2. Suppose that rule is not defined.

Then $M$ will halt. We can remove the transition rule $\delta(q, \gamma)=(p, \beta, S)$ in the specification of $M$ without changing the language accepted by $M$.

Applying the replacement or removal above repeatedly until there is no rule in $M$ that tells $M$ to stay in the same cell, we find that $L(M)$ is the language accepted by a right-moving only TM.

This question and answer tells us a right-moving only TM is essentially a DFA. Basically, a rule in a right-moving only TM, $\delta(q, \gamma)=(t, \beta, R)$ corresponds to $\delta(q, \gamma)=(t)$, a rule in the corresponding DFA. Since the language of a DFA is decidable, so is $L(M)$.
> 0 votes

# Answer
This inherently depends on your exact model of a TM, I'm assuming the following: A left-bounded tape, the head starts at position 0 and the word to decide is written at the tape. Furthermore, the TM has finitely many states.

Now the TM can only look at the first symbol at a time, can do finite computation (i.e. can have finitely many transitions to different states (\*)) and move its head to the right once. Then it can repeat itself (\**). In that, this TM is quit limited in what it can do, it can do as much as an DFA (like pointed out in the comments), that is: Look at a symbol, do some state-transitions and look at the next symbol.

(\*) What happens, if the TM loops in the inner states without moving its head? Well, since there are only finitely many states, the Universal Turing Machine UTM can simulate the TM and just count how many transitions the TM has made since the last head movement to the right. If this number exceeds the number of states of the TM, the TM will not terminate, so the UTM can answer 'no'.

(\**) What happens if the TM just goes to the right indefinitely? Well, at some point it will exceed the word to decide and move its head to a blank cell. An easy argument is to just count from there on the number of transitions (moving right or staying with the head at the current cell). If this number is greater than the number of states of the TM, it is caught in a loop and the UTM can answer 'no'.

To sum it up: The TM in question cannot decide its language, but the UTM can, so it is decidable in the usual sense.
> 1 votes

---
Tags: formal-languages, turing-machines, computability, pushdown-automata
---


# Question
Title: The role of asymptotic notation in $e^x=1++Θ(^2)$?
I'm reading CLRS and there is the following:

> When x→0, the approximation of $e^x$ by $1+x$ is quite good: $$e^x=1++Θ(^2)$$

I suppose I understand what means this equation from math perspective and, also, there is an answer in another cs question. But I don't understand some things, so have a few questions.

1. Why do they use $Θ$ here and why do they use $=$ sign?
2. Is it possible to explain how the notation here is related to the author's conclusion that $e^x$ is very close to $1 + x$ when $x \rightarrow 0 $?
3. Also, how is it important here that $x$ tends to $0$ rather than to $\infty$ as we usually use asymptotic notations?

I'm sorry if there are a lot of questions and if they are stupid, I'm just trying to master this topic.

# Answer
What the equation means is that there exist constant $A\>0$ and $B,C$ such that $$ |x| \leq A \Longrightarrow Bx^2 \leq e^x-1-x \leq Cx^2. $$ In particular, for small $x$, $e^x$ is very close to $1+x$, since the error is only $O(x^2)$ (when $x$ is small, $x^2$ is much smaller than $x$).

The same estimate doesn't hold for large $x$ — indeed, $e^x$ grows faster than $x^2$, indeed faster than any fixed power of $x$. So the quoted estimate only holds for small $x$.

---

Here is a graphic example. Below is the plot of $\frac{e^x-1-x}{x^2}$ for $|x| \leq 0.1$. You can see that it is very close to $0.5$. This is consistent with the Taylor expansion of $e^x$, which is $1 + x + x^2/2 + O(x^3)$.

In contrast, here is the same plot for $10 \leq x \leq 20$. You can see that the ratio shoots up to infinity.

*Credit: plots executed using Desmos.*
> 5 votes

---
Tags: asymptotics
---


# Question
Title: It is decidable whether a pushdown automaton will accept a word?
I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable.

I would say that you can simulate a push down automaton with a Turing Machine and, if it doesn't loop forever, accept the word when the automaton accepts, or reject when it does. In this case, the problem of decide if a push down automaton accept a word would be semi-decidable. But I'm not sure if that is correct and also, I can't find a way to prove if it is decidable or not.

Any ideas here?

# Answer
Pushdown automata are nondeterministic, and there is no a priori bound on the length of computation (imagine $\epsilon$-transitions that add and remove the same element from the stack). Therefore it's not clear how to perform your simulation.

Fortunately, we know how to convert a pushdown automaton to an equivalent context-free grammar, and the latter have parsing algorithms such as CYK. Using these algorithms, we can dedice whether a given pushdown automaton accepts a word by first converting the automaton into a context-free grammar.
> 0 votes

---
Tags: computability, proof-techniques, pushdown-automata
---


title: Why is EXPTIME in EXPSPACE?

text:
# Question
Title: Why is EXPTIME in EXPSPACE?
What is the intuition behind EXPTIME being inside EXPSPACE?

When space complexity is usually smaller than time complexity or in the worse case, they are equal

# Answer
> 2 votes
As Yuval Filmus states in the comments, any TM (with one tape and one read-write head) whose time complexity is bounded by a function $t$ also has its space complexity bounded by $t$ since, in $t$ steps, the TM can only scan as most as $t$ many tape positions. In terms of complexity classes: $$\textsf{TIME}(t) \subseteq \textsf{SPACE}(t)$$ $\textsf{P} \subseteq \textsf{PSPACE}$ and $\textsf{EXPTIME} \subseteq \textsf{EXPSPACE}$ is immediate from this. One of the greatest concerns of complexity theory (most of which are yet unsolved questions) is determining under which conditions this is a proper inclusion or not.

# Answer
> 0 votes
Think about it this way: Consider an algorithm that executes $n$ steps, and then stops. To make that happen - to execute exactly those $n$ steps - you first need some way to store the number $n$, *and* you also need some way to store every number from $1$ to $n$, as you will need to know either how many steps you've already taken, or how many steps you have left over, in order to say you need to stop.

It doesn't matter if the algorithm is or isn't *literally* a counter - for it to run that many steps, which can be thought of as somehow "encoded" within the input, it has to thus also *somehow* encode the same *information* that such a counter would within it *somewhere*, and thus it must demand at least $\lg n$ bits of storage.

Likewise, if you are only given $N$ bits of storage, you cannot have an algorithm that takes more than $n = 2^N$ steps and still terminate upon reaching that step, as it won't be able to "know", so to speak, how much further to run.

If you want to take *more* than $2^N$ steps and terminate, you must then need more storage. If you have storage that is exponential, i.e. $N = 2^M$, then you can now take *doubly-exponential* steps, i.e. $n = 2^{2^M}$. If your minimum running time is doubly-exponential, then it follows your minimum space *must* be exponential, just to store the information equivalent to that "counter".

Of course, the unresolved question is whether or not any problems which have solutions using exponentially growing amounts of space, can *only* have solutions which take super-exponential amounts of time, while the above only shows that if you have at least a doubly-exponential amount of time, you need an exponential amount of space, i.e. it's a sort of converse.

---
Tags: complexity-theory
---


# Question
Title: The law of excluded middle and decidability
I will divide my question in two parts. The first part I am sure that there is a objective answer, but I am not sure about the second part.

First part: Is it all (decisions) problems trivial to prove decidable after assuming the Law of Excluded Middle (LEM)? e.g. There is no problem hard to prove decidable after assuming LEM.

Second part: Does make any sense to agree with a non-constructive proof that a problem is decidable?

Edit:

I will give an example of what I meant in the first part.

Consider the problem of deciding the eveness of a number. If I assume LEM, this problem can be easily proved decidable. There was no need to do the "hard" proof of building the decider.

Here is the demonstration in Coq of that:

```
Inductive even : nat -> Prop :=
| ev_0 : even 0
| ev_SS : forall n, even n -> even (S (S n)).

Axiom LEM : forall P : Prop, P \/ ~ P.

Lemma even_dec : forall (n : nat), even n \/ ~ even n.
  intros.
  apply LEM.
Qed.

```

The first part of my question was basically asking if this is always the case.

# Answer
You are conflating *computationally* decidable with *logically* decidable.

A (closed) formula, $\varphi$, is **logically decidable** iff $\vdash\varphi$ or $\vdash\neg\varphi$, i.e. if $\varphi$ is derivable or $\neg\varphi$ is derivable (with respect to some given logical system). This is the sense we mean when we say something like the Continuum Hypothesis is undecidable.

A unary predicate on naturals, $P$, is **computationally decidable** iff there is a Turing machine $M$ which terminates on all inputs with output either $1$ or $0$, and $P(n)$ holds if and only if $M$ terminates with output $1$ on input $n$. This is the sense we mean when we say something like the Halting Problem is undecidable.

(There are other ways we use the term "decidable" such as when we say a(n entire) logic or theory is decidable which, more or less, means something like $\vdash\varphi\_n$ is computationally decidable where $\varphi\_n$ is a formula encoded by $n$ via some suitable surjective encoding.)

Assuming the Law of the Excluded Middle (LEM) doesn't automatically make every unary predicate on the naturals computationally decidable. Indeed, usually computational decidability is formulated within a classical logic where LEM holds.

Intuitionistic logic connects logical decidability to LEM because it satisfies the disjunction property which states $\vdash\varphi\lor\psi$ if and only if $\vdash\varphi$ or $\vdash\psi$. This means $\varphi$ being logically decidable is equivalent to $\vdash\varphi\lor\neg\varphi$.

Now, there's a *model* of intuitionistic first-order logic such that $\forall n:\mathbb N.P(n)\lor\neg P(n)$ is modeled by a *computable* function taking a natural and producing a witness of (the interpretation of) either $P(n)$ or $\neg P(n)$. This means (the interpretation of) $\forall n:\mathbb N.P(n)\lor\neg P(n)$ is true in this model if and only if $P$ is computationally decidable. LEM, in this context, would imply the statement that all decision problems are computationally decidable. LEM is, of course, false in this model. Therefore, if you assume LEM, this interpretation ceases to be a model.

The fact that certain formulas are derivable in intuitionistic first-order logic implies that corresponding predicates are computationally decidable. This implication itself, though, is demonstrated in the meta-logic where the definition of "computationally decidable" resides, and this is usually a classical logic.

For an informal (meta-)logic in which you define "computationally decidable", it's up to you whether you want to accept non-constructive proofs or not. However, there is a big difference between proving a formula in constructive logic which can be *interpreted* as a witness to the computational decidability of a predicate, and proving a formula which *states in the constructive logic* that a predicate is computationally decidable which would involve constructive definitions of Turing machine and so forth. As an analogy, the circle *as a (higher inductive) type* in Homotopy Type Theory is very different from the construction of cirles, e.g. $\mathbb R/\mathbb Z$ *within* Homotopy Type Theory. As a more contrived example, let's say I interpret the theory of abelian groups into $3\mathbb Z$, i.e. $1$ is interpreted as $3$. Then it is still the case that the "internal" notion of $3$, i.e. $1+1+1$, is different from $1$.
> 8 votes

---
Tags: logic, proof-techniques
---


# Question
Title: What's the difference between a type and a kind?
I am learning the programming langauge Haskell, and I'm trying to wrap my head around what the difference between a `type` and a `kind` is.

As I understand it, `a kind is a type of type`. For instance, `a ford is a type of car` and `a car is a kind of vehicle`.

Is this a good way to think about this?

Because, the way my brain is currently wired, a `ford is a **type** of car`, but also a `car is a **type** of vehicle` whilst at the same time a `car is a **kind** of vehicle`. I.e. the terms `type` and `kind` are interchangeable.

Could anyone shed some light on this?

# Answer
Here, "values", "types", and "kinds" have formal meanings, so considering their common English usage or analogies to classifying automobiles will only get you so far.

My answer pertains to the formal meanings of these terms in the context of Haskell specifically; these meanings are based on (though are not really identical to) the meanings used in mathematical/CS "type theory". So, this won't be a very good "computer science" answer, but it should serve as a pretty good Haskell answer.

In Haskell (and other languages), it ends up being helpful to assign a **type** to a program expression that describes the class of **values** the expression is permitted to have. I assume here that you've seen enough examples to understand why it would be useful to know that in the expression `sqrt (a**2 + b**2)`, the variables `a` and `b` will always be values of type `Double` and not, say, `String` and `Bool` respectively. Basically, having **types** assists us in writing expressions/programs that will work correctly over a wide range of **values**.

Now, something you may not have realized is that Haskell types, like those that appear in type signatures:

```
fmap :: Functor f => (a -> b) -> f a -> f b

```

are actually themselves written in a type-level Haskell sublanguage. The program text `Functor f => (a -> b) -> f a -> f b` is -- quite literally -- a *type expression* written in this sublanguage. The sublanguage includes operators (e.g., `->` is a right associative infix operator in this language), variables (e.g., `f`, `a`, and `b`), and "application" of one type expression to another (e.g., `f a` is `f` applied to `a`).

Did I mention how it was helpful in many languages to assign types to program expressions to describe classes of expression values? Well, in this type-level sublanguage, expressions evaluate to **types** (rather than **values**) and it ends up being helpful to assign **kinds** to type expressions to describe the classes of **types** they are permitted to represent. Basically, having **kinds** assists us in writing type expressions that will work correctly over a wide range of **types**.

So, **values** are to **types** as **types** are to **kinds**, and **types** help us write **value**-level programs while **kinds** help us write **type**-level programs.

What do these **kinds** look like? Well, consider the type signature:

```
id :: a -> a

```

If the type expression `a -> a` is to be valid, what **kind** of **types** should we permit variable `a` to be? Well, the type expressions:

```
Int -> Int
Bool -> Bool

```

look valid, so the **types** `Int` and `Bool` are obviously of the right **kind**. But even more complicated types like:

```
[Double] -> [Double]
Maybe [(Double,Int)] -> Maybe [(Double,Int)]

```

look valid. In fact, since we ought to be able to call `id` on functions, even:

```
(a -> a) -> (a -> a)

```

looks fine. So, `Int`, `Bool`, `[Double]`, `Maybe [(Double,Int)]`, and `a -> a` all look like **types** of the right **kind**.

In other words, it looks like there's only one **kind**, let's call it `*` like a Unix wildcard, and every **type** has the same **kind** `*`, end of story.

Right?

Well, not quite. It turns out that `Maybe`, all by itself, is just as valid a type expression as `Maybe Int` (in much the same way `sqrt`, all by itself, is just as valid a value expression as `sqrt 25`). *However*, the following type expression is not valid:

```
Maybe -> Maybe

```

Because, while `Maybe` is a type expression, it doesn't represent the **kind** of **type** that can have values. So, *that's* how we should define `*` -- it's the **kind** of **types** that have values; it includes "complete" types like `Double` or `Maybe [(Double,Int)]` but excludes incomplete, valueless types like `Either String`. For simplicity, I'll call these complete types of kind `*` "concrete types", though this terminology isn't universal, and "concrete types" might mean something very different to, say, a C++ programmer.

Now, in the type expression `a -> a`, as long as type `a` has **kind** `*` (the kind of concrete types), the result of the type expression `a -> a` will *also* have **kind** `*` (i.e., the kind of concrete types).

So, what **kind** of **type** is `Maybe`? Well, `Maybe` can be applied to a concrete type to yield another concrete type. So, `Maybe` looks like a little like a type-level function that takes a **type** of **kind** `*` and returns a **type** of **kind** `*`. If we had a value level function that took a **value** of **type** `Int` and returned a **value** of **type** `Int`, we'd give it a **type** signature `Int -> Int`, so by analogy we should give `Maybe` a **kind** signature `* -> *`. GHCi agrees:

```
> :kind Maybe
Maybe :: * -> *

```

Going back to:

```
fmap :: Functor f => (a -> b) -> f a -> f b

```

In this type signature, variable `f` has kind `* -> *` and variables `a` and `b` have kind `*`; the built-in operator `->` has kind `* -> * -> *` (it takes a type of kind `*` on the left and one on the right and returns a type also of kind `*`). From this and the rules of kind inference, you can deduce that `a -> b` is a valid type with kind `*`, `f a` and `f b` are also valid types with kind `*`, and `(a -> b) -> f a -> f b` is valid type of kind `*`.

In other words, the compiler can "kind check" the type expression `(a -> b) -> f a -> f b` to verify it's valid for type variables of the right kind the same way it "type checks" `sqrt (a**2 + b**2)` to verify it's valid for variables of the right type.

The reason for using separate terms for "types" versus "kinds" (i.e., not talking about the "types of types") is mostly just to avoid confusion. The **kinds** above look very different from **types** and, at least at first, seem to behave quite differently. (For example, it takes some time to wrap your head around the idea that every "normal" type has the same kind `*` and the kind of `a -> b` is `*` not `* -> *`.)

Some of this is also historical. As GHC Haskell has evolved, the distinctions between values, types, and kinds have started to blur. These days, values can be "promoted" into types, and types and kinds are really the same thing. So, in modern Haskell, values both have types and **ARE** types (almost), and the kinds of types are just more types.

@user21820 asked for some additional explanation of "types and kinds are really the same thing". To be a little clearer, in modern GHC Haskell (since version 8.0.1, I think), types and kinds are treated uniformly in most of the compiler code. The compiler makes some effort in error messages to distinguish between "types" and "kinds", depending on whether it's complaining about the type of a value or the type of a type, respectively.

Also, *if no extensions are enabled,* they are easily distinguishable in the surface language. For example, types (of values) have a representation in the syntax (e.g., in type signatures), but kinds (of types) are -- I think -- completely implicit, and there's no explicit syntax where they appear.

But, if you turn on the appropriate extensions, the distinction between types and kinds largely disappears. For example:

```
{-# LANGUAGE GADTs, TypeInType #-}
data Foo where
  Bar :: Bool -> * -> Foo

```

Here, `Bar` is (both a value and) a type. As a type, its kind is `Bool -> * -> Foo`, which is a type-level function that takes a type of kind `Bool` (which is a type, but also a kind) and a type of kind `*` and produces a type of kind `Foo`. So:

```
type MyBar = Bar True Int

```

correctly kind-checks.

As @AndrejBauer explains in his answer, this failure to distinguish between types and kinds is unsafe -- having a type/kind `*` whose type/kind is itself (which is the case in modern Haskell) leads to paradoxes. However, Haskell's type system is already full of paradoxes because of non-termination, so it's not considered a big deal.
> 38 votes

# Answer
If you know about the difference between sets and classes in set theory, then it may help to think about the matter as $$\mathrm{type} : \mathrm{kind} = \mathrm{set} : \mathrm{class}.$$ If not, you can think of kinds as "large" or "higher" types whose elements may be types, or may involve types in some fashion. For example:

* `Bool` is a type
* `Type` is a kind because its elements are types
* `Bool -> Int` is a type
* `Bool -> Type` is a kind because its elements are functions that return types
* `Bool * Int` is a type
* `Bool * Type` is a kind because its elements are pairs with one component a type

In type theory it is usually undesirable to have the type of all types (it leads to pardoxes). Instead, we can have *universes*, which are types that contain other, smaller types. For instance, we might have a series of universes $U\_0$, $U\_1$, $U\_2$, ... where $U\_0$ contains basic stuff like $\mathtt{Bool}$, $\mathtt{Nat}$, $\mathtt{Nat} \to \mathtt{Nat}$, while $U\_1$ contains $U\_0$ and $\mathtt{Bool} \to U\_0$ and $U\_0 \to U\_0$ etc. In general, $U\_{n+1}$ contains $U\_n$ as an element, as well as anything else we can build from $U\_n$ and all the things that came before it, using the basic operations $\times$, $\to$, etc.

I am explaining all of this because often one only needs $U\_0$ and $U\_1$, in which case the elements of $U\_0$ are usually called *types* and the elements of $U\_1$ are called *kinds*. In Haskell terminology, the smallest univese $U\_0$ is written as `*`. Thus `*` is an element of `U_1`, which Haskell does not name explicitly.
> 21 votes

# Answer
A *value* is like the specific red 2011 Ford Mustang with 19,206 miles on it that you have sitting in your driveway.

That specific value, informally, could have many *types*: it is a Mustang, and it is a Ford, and it is a car, and it is a vehicle, among many many other types that you could make up (the type of "things belonging to you", or the type of "things that are red", or...).

(In Haskell, to a first order approximation (GADTs break this property, and the magic around number literals and the OverloadedStrings extension obscure it a little), values have one principal type instead of the plethora of informal "types" you can give your 'stang. `42` is, for purposes of this explanation, an `Int`; there is no type in Haskell for "numbers" or "even integers"—or rather, you could make one, but it would be a disjoint type from `Int`.)

Now, "Mustang" may be a *subtype* of "car"—every value that is a Mustang is also a car. But the *type*—or, to use Haskell's terminology, the *kind* of "Mustang" is not "car". "Mustang" the type is not a thing you can park in your driveway or drive around in. "Mustang" is a noun, or a category, or just a type. Those are, informally, the *kinds* of "Mustang".

(Again, Haskell only recognises one kind for each type-level thing. So `Int` has kind `*`, and no other kinds. `Maybe` has kind `* -> *`, and no other kinds. But the intuition should still hold: `42` is an `Int`, and you can do `Int`y things with it like adding and subtracting. `Int` itself is not an `Int`; there is no such number as `Int + Int`. You may informally hear people say that `Int` is a `Num`, by which they mean that there is an *instance* of the `Num` type class for the type `Int`—this is not the same thing as saying that `Int` has *kind* `Num`. `Int` has kind "type", which in Haskell is spelled `*`.)

So isn't every informal "type" just a noun or a category? Do all types have the same kind? Why talk about kinds at all if they're so boring?

This is where the English analogy will get a little rocky, but bear with me: pretend that the word "owner" in English made no sense in isolation, without a description of the thing being owned. Pretend that if someone called you an "owner", that would make no sense to you at all; but if someone called you a "car owner", you could understand what they meant.

"Owner" does *not* have the same kind as "car", because you can talk about a car, but you can't talk about an owner in this made-up version of English. You can only talk about a "car owner". "Owner" only creates something of kind "noun" when it's applied to something that already has kind "noun", like "car". We would say that the kind of "owner" is "noun -\> noun". "Owner" is like a function that takes a noun and produces from that a different noun; but it's not a noun itself.

Note that "car owner" is not a subtype of "car"! It's not a function that accepts or returns cars! It's just a completely separate type from "car". It describes values with two arms and two legs who at one point had a certain amount of money, and took that money to a dealership. It does not describe values that have four wheels and a paint job. Also note that "car owner" and "dog owner" are different types, and things you might want to do with one may not be applicable to the other.

(Likewise, when we say that `Maybe` has kind `* -> *` in Haskell, we mean that it's nonsensical (formally; informally we do it all the time) to talk about having "a `Maybe`". Instead, we can have a `Maybe Int` or a `Maybe String`, since those are things of kind `*`.)

So the whole point of talking about kinds at all is so that we can formalize our reasoning around words like "owner" and enforce that we only ever take values of types that have been "fully constructed" and aren't nonsensical.
> 6 votes

# Answer
> As I understand it, a kind is a type of type.

That's right - so let's explore what that means. `Int` or `Text` are concrete types, but `Maybe a` is an *abstract* type. It won't become a concrete type until you decide what specific value you want for `a` for a particular variable (or value / expression / whatever) eg `Maybe Text`.

We say that `Maybe a` is a *type constructor* because it is like a function that takes a single concrete type (eg `Text`) and returns a concrete type (`Maybe Text` in this case). But other type constructors might take even more "input params" before they return a concrete type. eg `Map k v` needs to take two concrete types (eg `Int` and `Text`) before it can construct a concrete type (`Map Int Text`).

So, the `Maybe a` and `List a` type constructors have the same "signature" which we denote as `* -> *` (similarly to the Haskell function signature) because if you give them one concrete type they will spit out a concrete type. We call this the "kind" of the type and `Maybe` and `List` have the same kind.

The concrete types are said to have kind `*`, and our Map example is kind `* -> * -> *` because it takes two concrete types as input before it can output a concrete type.

You can see it is *mostly* just about the number of "parameters" that we pass in to the type constructor - but realise that we might also get type constructors nested inside type constructors, so we can end up with a kind that looks like `* -> (* -> *) -> *` for example.

If you are a Scala/Java dev, you may also find this explanation helpful: https://www.atlassian.com/blog/archives/scala-types-of-a-higher-kind
> 1 votes

---
Tags: type-theory
---


# Question
Title: Is the halting problem undecidable or unrecognizable?
Is the Halting problem in the class of undecidable problems, or it is just in the set of unrecognizable problems?

I understand that if it is undecidable, then it is also unrecognizable. I have seen the two being used interchangeably, however I believe it is possible for a language to be recognizable but not decidable, so was hoping for clarification

# Answer
Encode a Turing machine $M$ and an input string $I$ into a single string $(M,I)$. Create a Turing machine $U$ that behaves as follows:

* $U$ rejects any input that is not a valid encoding
* When given valid input $(M,I)$, $U$ emulates the behavior of $M$ with input $I$
* If $M$ eventually halts when given input $I$ then $U$ halts and accepts input $(M,I)$

If $M$ eventually halts when given input $I$ then $U$ will (eventually) accept input $(M,I)$. So $U$ *recognizes* the language

$L=\\{(M,I) : M \text{ eventually halts when given input } I \\}$

Note, however, that $U$ does not *decide* $L$ because it does not explicitly reject $(M,I)$ if $M$ never halts given input $I$ \- in this case $U$ will also never halt when given input $(M,I)$.

The Halting Theorem tells us that $L$ is undecideable (over Turing machines) but we have just shown that $L$ is recognizeable.
> 0 votes

---
Tags: undecidability, semi-decidability
---


# Question
Title: Minimum cost max flow network problem with an alternative flow cost
Is there a standard name or a reference for the network flow problem that looks very similar to the minimum cost maximum flow problem, only the flow cost that I wish to minimize isn't sum of edge.flow * edge.weight over edges, but rather sum of \[edge.flow \> 0\] * edge.weight over edges, where \[edge.flow \> 0\] equals one if the flow is greater than zero, and zero otherwise? Is it intractable, as I suspect?

I'll tell you about the original problem that I believe reduces to this problem. A bunch of friends have a dinner, and agree to split the bill evenly. But not everyone has enough money to cover their share at that moment, so some pay more than their share, some less, with the intent to settle later. Later on, they want to settle with a minimum number of transactions, where one transaction is money changing hands between a pair of friends.

This clearly maps to a bipartite network with edges of unlimited capacity from all the ones who underpaid going to all of those who overpaid, and edges of capacity equal to the amount underpaid going from source to the underpaid nodes, and edges of capacity equal to the amount overpaid going from overpaid nodes to the sink. To minimize the number of transactions we need to minimize the number of nonzero flow edges between the under- and overpaid.

# Answer
> 2 votes
This is sometimes called the *minimum edge-cost flow problem* or *fixed-cost flow problem*. As you suspected, it is indeed **NP-hard**, even when the network is bipartite. It is listed as problem **ND32** in the list of NP-hard problems by Garey and Johnson:

M.R. Garey, D.S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. Freeman, New York, 1979.

An approximation algorithm is discussed here:

S.O. Krumke, H. Noltemeier, S. Schwarz, H.-C. Wirth, R. Ravi. Flow Improvement and Network Flows with Fixed Costs. In *Operations Research Proceedings 1998: Selected Papers of the International Conference on Operations Research Zurich*, p. 158--167, Springer, Berlin, 1998.

The idea is to solve a standard linear-cost flow problem in which edge capacities are unchanged, but the cost of one unit of flow along edge $e$ is defined to be the edge weight divided by the edge capacity. This will give a solution that may weigh up to $F$ times the weight of the optimal solution, where $F$ is the flow value; but it will not weigh more than that.

If the approximate solution is not good enough, you might want to resort to an ILP solver.

---
Tags: network-flow
---


# Question
Title: Is the capacity achieving input of a discrete memoryless channel unique?
Consider a classical discrete memoryless channel (DMC). Let $p$ be an input probability distribution and $Q$ be the channel's transition matrix. $q = Qp$ is a valid output probability distribution. The components of $p$ and $q$ are given as $p\_i$ and $q\_i$ respectively.

The capacity of this channel is given by maximizing the mutual information.

$$I = \max\_{p}\left\[\sum\_ip\_i\left(\sum\_{j}Q\_{ij}\log(Q\_{ij})\right) - \sum\_{j}q\_j\log q\_j\right\]$$

But, we know (Theorem 2.7.4 in Cover and Thomas, 2006) that $I(p)$ is concave in $p$.

If $I(p)$ is not simply a linear function (i.e. $q = Qp$ is not a trivial relationship) and is differentiable everywhere (seems like a reasonable assumption), does this not imply that the capacity achieving $p$ is unique?

# Answer
I believe the answer is "yes", when $Q$ is square and nonsingular, and "not necessarily", otherwise. See "On the Capacity of a Discrete Channel. I", by Saburo Muroga, Journal of the Physical Society of Japan, Vol. 8, No. 4, July - August 1953, pp 484-494.

You might also be interested in my note on Muroga's paper, in which I attempt to provide an alternate proof of the feasibility of the optimal input probability distribution, in the special case of a binary channel, and to correct what I think is a trivial error in Muroga's paper (although this might simply have been Muroga being too polite to point out a trivial mistake by Shannon), and I also try to simplify a part of Muroga's argument:

"On the Computation of the Shannon Capacity of a Discrete Channel with Noise", S. Cowell, arXiv:1701.08731v2 \[cs.IT\] \[here\]
> 2 votes

---
Tags: information-theory, communication-protocols
---


# Question
Title: What is the underlying pattern/rule in this question?
I can't find a concise algorithm for the following coding problem:

*Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded. For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.You can assume that the messages are decodable. For example, '001' is not allowed.*

I've recognized that any number `<=26` can be represented 2 ways. I've tried to observe what happens when I add a number like `2`, which can later form another 2-digit number with the one after it (e.g. `22` \- 2 combinations, `222` \- 3, `2222` \- 5, `22222` \- 8). But I can't seem to find a robust pattern.

This was a coding interview question that was supposed to last 30min, so I'm embarrassed I can't see the latent rule.

# Answer
I believe the pattern you are looking for is dynamic programming. In the case at hand, the answer for a message can be based on answers for prefixes of the message. This leads to a linear time and linear space algorithm that computes answers for all prefixes in order of increasing length.
> 1 votes

---
Tags: algorithms, pattern-recognition
---


# Question
Title: How can instruction fetch and decode pipeline stages run simultaneously in a CPU with dynamic branch prediction?
I have recently been investigating CPU pipelining and branch prediction and have a question about how exactly these fit together.

If, for example, instructions are meant to be fetched in one stage of the pipeline and decoded in the next while the next instruction is fetched simultaneously, how is it possible for the pipeline to proceed without a stall when dynamic branch prediction is in operation?

As an instruction must be decoded before branch prediction can occur or be deemed unneeded, and as any prediction must be made before the next instruction can be fetched, how can an instruction be decoded while the next instruction is fetched in the same clock cycle?

# Answer
> 3 votes
> As an instruction must be decoded before branch prediction can occur or be deemed unneeded,

That can be avoided. The fetch stage can do prediction based purely on the current PC, without looking at the instruction. Branch Target Prediction also enters the picture here, otherwise without decoding the branch target would be unavailable. Accidentally applying branch prediction to an instruction that turns out not to be a branch is not a disaster, just something to detect and signal a misprediction if necessary.

So this can be done with no bubble.

As an example, here is a diagram of the pipeline of the RISC-V BOOM processor (source), showing PC going to next-line predictor and the I\\$ in parallel

> any prediction must be made before the next instruction can be fetched

Why stop? Just keep predicting, it doesn't matter that the next instruction(s) have been fetched, flush them out if one of the later predictions "changes its mind". This gives you a lot of time to run slow but high quality predictors after the fast predictors. You could even do away with the fast predictors, but then there really would be a bubble for every "taken" prediction - an unconditional stall is overkill though, there's no reason to not at least fetch the next address (effectively predicting "not-taken").

As a practical example, AMD Bobcat takes several shots at branch prediction, some in parallel with decoding (Fetch3 through Fetch5):

In the BOOM diagram there are also several forms of branch prediction, but the Backing Predictor (the more complex predictor with higher accuracy) there is before decode rather than parallel with it.

# Answer
> -1 votes
It is called branch *prediction*. The whole point is that you can *predict* whether a branch will be taken or not before you actually know. Sometimes you are wrong.

So the processor reads and decodes the instruction that it *predicts* will be executed. If the prediction is found to be wrong, the processor has to start all over again, this time reading and decoding the right instructions.

---
Tags: computer-architecture, cpu, cpu-pipelines
---


# Question
Title: What is the name of this sorting algorithm?
I have typeset in a Wikipedia draft this sorting algorithm. It is a comparison sort, yet can handle only numeric arrays.

Basically, it marches through the input array and for each new array component it inserts it into a sorted doubly-linked list. It has two optimizations:

1. each list node has a count; instead of adding a new node with the same key, existing node is reused by incrementing its counter,
2. the sort maintains a reference to the most recently accessed list node. This allows faster search for the next list node in case the two relevant keys are "close" to each other.

My question is: what is the name of that sort? (I believe I am not the first one to conceive it.)

# Answer
**What is the name of that sort?**

There is no existing name for it, I would believe.

If I had to name it, its name could be "caching and counting insertion sort". Here are the considerations.

* It is a kind of insertion sort since it maintains a single ordered linked-list all the way by inserting elements one by one into that ordered linked-list.
* "Caching" and "counting" are the basic two features of that insertion sort. Caching tries to make it faster to find the right location to insert by taking advantage of possible locality coherence. Counting is a common strategy to deal with the situation when duplicates happen often. Both caching and counting are standard terms that are easily recognizable.
* It happens that both words start with "c", which is helpful for reading and memorizing.
* "caching" is put before "counting" since "caching" is a more distinguishing feature of the algorithm. It is better to make the name less similar to the existing counting sort.
* This is not a very cohesive name, since there is no strong coupling between the two techniques used in that sort. The technique of caching could be applied to almost all kinds of sort. The technique of counting could be applied to almost all kinds of sort as well independently. The only meaningful connection between them is that if this caching technique improves the speed a lot, it is more likely that there are lots of duplicates, then the counting technique might be even more useful.
* "Caching and counting insertion sort" or "caching-counting insertion sort" is, in fact, more like a description instead of a proper name.

I would not recommend a name like "curve sort" unless you can show me some direct or obvious connection between "curve" and that sort.

**Should we name that sort?**

Is that sort distinctive and cohesive enough to deserve a distinctive short name?

The combination of caching and counting might be distinctive enough. However, those two optimizations are not cohesive. In fact, it is reasonable to see the two as independent. Caching deals with locality while counting deals with duplicates. Each one of them can be removed or applied without affecting the other's usefulness or functionality. It is preferable to study either one of them separately. It is not preferred to give a name to a simple combination of two abstract features.

As said by Bulat, there could be dozens of variations we can make to each of the algorithms listed on this page or this Wikipedia article. In particular, the counting technique can be applied to most if not all of them. In most cases the variations don't get individual names. To be clear, not every variation get individual names that have become established or standardized. Of course, if you write an article to expound that sort, you can certainly give it a fancy cool name such as "curve sort" or "Rodionsort".

**What else could be done?**

In fact, it looks like more interesting to name a simplified version of your algorithm that does not use the counting technique "caching insertion sort" or simply "caching sort", since caching makes sense mostly with insertion sort.

There have been many discussions/articles about whether or how much certain sorting algorithms are cache-friendly. However, I have not seen a simple sorting algorithm that takes an explicit separate step in order to take advantage of the "smoothness" of the data, although it might be a simple step. The most similar step I have seen is the checking whether the given data have been sorted before or during sorting. Some complex sorting algorithms such as Timsort search for ascending or descending subarrays during sorting, which also use many other techniques. A simple algorithm called "caching sort" sounds attractive and pedagogical to me.

A slight generalization could be caching two elements instead of just one element. When a new element comes along, we could start searching the position for the new element from the cached element that is nearer to the new element. Then the sorting would be efficient for data stream that comes from two "smooth" sources that are mixed irregularly.

A further generalization could be caching even more elements with more involved caching policy. Or even layers of caches. Let me stop my brainstorming here.
> 4 votes

# Answer
Basically, it's insertion sort, but implemented in very unusual way - with `O(n)` extra memory, `O(n)` search for best place instead of `O(n)` moving elements around, extra per-node counter, and pointer to last element.

I personally find it interesting for moderate-sized arrays with groups of close values, but overhead of list maintenance may kill the performance compared to qsort.

And it's applicable to any values (not only numbers).
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: Turing Machine equivalence in MinTM proof
The proof with contradiction that **$MIN\_{\mathrm{TM}}$ is not Turing-recognizable** from Michael Sipser's textbook "Introduction to the Theory of Computation" (Theorem 6.7) is as follows:

> $C=$ "On input $w$:
>
> 1. Obtain, via the recursion theorem, own description $\langle C \rangle$.
> 2. Run the enumerator $E$ until a machine $D$ appears with a longer description than that of $C$.
> 3. Simulate $D$ on input $w$."

$MIN\_{\mathrm{TM}}$ is infinite, so at least one $D$ occurence will be observed.

**Because $C$ is shorter than $D$ and is equivalent to it, $D$ cannot be minimal.**

I would like to understand three things from this proof:

1. How do we know that $MIN\_{\mathrm{TM}}$ is inifinite?
2. Why $C$ is equivalent to $D$?
3. Why "Because $C$ is shorter than $D$ and is equivalent to it, $D$ cannot be minimal"?. Why do we expect $D$ to be minimal?

Edit : I have some opinions (I want to verify) about my questions. Please correct me If I am wrong.

2. Equivalence is based only on ability to construct same language recognizers or to say $L(M\_1) = L(M\_2)$

# Answer
> 1 votes
> How do we know that $MIN\_{\mathrm{TM}}$ is inifinite?

There are infinitely many partial recursive functions (i.e., functions which are computed by TMs) and to each such function there is at least one TM which computes it and has minimal description.

> Why $C$ is equivalent to $D$?

Because of point 3., which essentially forces $C$ and $D$ to have the same behavior. In this case, yes, equivalence is used in the sense that $L(C) = L(D)$.

> Why "Because $C$ is shorter than $D$ and is equivalent to it, $D$ cannot be minimal"?. Why do we expect $D$ to be minimal?

$D$ is minimal because $\langle D \rangle \in MIN\_{\textrm{TM}}$. Recall that, by assumption, the enumerator $E$ only outputs descriptions in $MIN\_{\textrm{TM}}$. The point is that $\langle C \rangle$ is fixed (because we have just provided a description for it), but $E$ gives us descriptions of TMs of arbitrary length indefinitely; hence, $E$ will eventually output some description which is longer than $\langle C \rangle$.

---
Tags: turing-machines, recursion, semi-decidability
---


# Question
Title: Introduction to Algorithms (CLRS) Ex 5.2-5 solution
The following is Ex 5.2-5 from Introduction to Algorithms (CLRS), 2nd Edition.

> Let $A\[1...n\]$ be an array of n distinct numbers. If $i\<j$ and $A\[i\]\>A\[j\]$, then the pair $(i, j)$ is called an inversion of $A$. Suppose that the elements of $A$ form a uniform random permutation of $\<1,...,n\>$. Use indicator random variables to compute the expected number of inversions.

The solution from https://walkccc.github.io/CLRS/Chap05/5.2/ says:

> Let $X\_{ij}$ be an indicator random variable for the event where the pair $A\[i\], A\[j\]$ for $i \< j$ is inverted. We have $\Pr\\{X\_{ij} = 1\\} = \frac{1}{2} $, because given two distinct random numbers, the probability that the first is bigger than the second is $\frac{1}{2}$.

I would like to ask what is the rationale for $\Pr\\{X\_{ij} = 1\\} = \frac{1}{2}$. I know that there can be only 2 outcomes, either be $X\_{ij} =1$ or $X\_{ij}=0$. Also, $\Pr\\{X\_{ij} = 1\\}+\Pr\\{X\_{ij} = 0\\}=1$.

After looking at the answer, it kind of make sense, but I would like to ask if there is a more "systematic" way to derive/justify this probability. Note that I am being very vague about the meaning of systematic because I simply would like to have a more reliable way of deriving this probability rather than only relying on intuition.

# Answer
For a permutation $\pi$, let $\pi(i\\;j)$ be the permutation obtained by switching the places of elements $i$ and $j$. Since $\pi(i\\;j)(i\\;j) = \pi$, we can partition the set of all permutations over the elements of $A$, into $n!/2$ pairs $\\{\pi,\pi(i\\;j)\\}$.

Consider what happens to $A$ after permuting by $\pi$ and by $\pi(i\\;j)$. In exactly one of these cases, the pair $(i,j)$ is an inversion. Therefore the pair $(i,j)$ is an inversion for exactly $n!/2$ of the permutations, i.e., with probability exactly $1/2$.
> 2 votes

---
Tags: probability-theory, randomized-algorithms
---


# Question
Title: Term for a graph decomposition based on a maximum matching
Let $M$ be a maximum cardinality matching in a bipartite graph $G(X+Y,E)$. Let $X\_0$ be the subset of $X$ unmatched by $M$. Define the following sequence:

* $Y\_1 = $ the neighbors of $X\_0$ using edges in $E\setminus M$.
* $X\_1 = $ the neighbors of $Y\_1$ using edges in $M$.
* $Y\_2 = $ the new neighbors of $X\_1$ ("new" = not in $Y\_1$) using edges in $E\setminus M$.
* etc...

Since the graph is finite, at some point we stop finding new vertices, so the process stops and we have a maximal sequence.

Let $X\_S,Y\_S$ be the vertices contained in the sequence, and $X\_L,Y\_L$ the leftover vertices:

We have a decomposition of $X$ and $Y$ into two subsets. This decompositionhas some nice properties (for example, $X\_L$ and $X\_S$ are the same regardless of what maximum matching $M$ we start from).

Such a nice decomposition must have a name... what is its name? And what is a standard reference for the decomposition and its properties?

# Answer
> 0 votes
Looking at the image in the question, I get the impression that $X\_L\cup Y\_S$ is a minimal vertex cover of the graph $G$. (This is not fully true: If $X$ contains isolated vertices, then those would be part of $X\_L$, but not of a minimal vertex cover.) Good, but there can be many vertex covers of a graph, so this does not yet fully characterize that specific decomposition. So let us look at the construction in more detail: Any minimal vertex cover must contain at least one vertex from every matched edge. Since the vertices in $X\_0$ don't belong to any matched edge, covering the edges incident to $X\_0$ by vertices (from $Y$) belonging to matched edges is the best we can do. So $Y\_S$ turns out to be the biggest subset of $Y$ belonging to every mimimal vertex cover of $G$. (So it is the intersection of the $Y$ part of all minimal vertex covers). And $X\_L$ is the unique subset of $X$ covering the remaining edges (+ the isolated vertices of $X$).

OK, so how is this related to the Dulmage-Mendelsohn decomposition? (set $U=X$ and $V=Y$).

> ..., let $D$ be the set of vertices in $G$ that are not matched in at least one maximum matching

I guess the neighbors of $D\cap X$ belong to any minimal vertex cover, and the neighbors of $D\cap Y$ also belong to any minimal vertex cover. So $Y\_S$ is also part of (or at least easily defined) for the Dulmage-Mendelsohn decomposition. Can we also define $X\_L$ in terms of the Dulmage-Mendelsohn decomposition? Well, it is easier to define $X\_S$, it should be just $D\cap X$.

This all sounds much more complicated than it actually is. If you look at the possible alternating paths for the given maximum matching, it should be easy to see the relation between the minimal vertex cover and the set $D$ used to define the Dulmage-Mendelsohn decomposition.

---
Tags: terminology, reference-request, matching, bipartite-matching, decomposition
---


# Question
Title: Minimum number of comparision to find the third largest element in an array of distinct integers?
For the second largest element, I know that the formula is $n+ \lceil\log n \rceil -2 $

Is there any formula for the third largest element? and if so, what is the derivation?

# Answer
> 1 votes
For the problem of computing the $k$-th rank element, a lower bound of $n-k+\log \binom{n}{k-1}$ can be proven with decision trees.

For simplicity this proof assumes that the element set $X$ is of size $n$ and its elements are distinct (which makes the problem harder). Moreover, the algorithm may only compare any two elements, and conclude one is either smaller or greater than the other.

---

First, let us claim the following:

> For computing the $k$-th rank element (denoted $x\_k$) (using comparisons only), every other element $x\_i$ must be involved in a comparison that sets it lesser or greater than the $k$-th rank element.
>
> Formally: for any $x\_i$ lesser than $x\_k$, $x\_i$ must be involved in a comparison of the sort $x\_i \< x\_j \leq x\_k$. For any $x\_i$ greater than $x\_k$, it must be involved in the comparison $x\_i \> x\_j \geq x\_k$

The proof by contradiction: Suppose $x$ was not involved in either those comparisons. Then $x$ can be either greater or smaller than $x\_k$, which means the $k$-th rank element can change depending on $x$.

---

Let $\mathcal{T}$ be a decision tree that finds the $k$-th rank element. We will show $\mathcal{T}$ has at least $2^{n-k} \binom{n}{k-1}$ leaves.

Now, suppose $T\_1$ is another decision tree, that *knows* the set of elements greater than $x\_k$, denoted by $K\_1$. It means $T\_1$ does not need to compare any elements of $K\_1$, and thus performs $n-k$ comparisons, or has $2^{n-k}$ leaves.

Because of the claim we made earlier, we **know** $\mathcal{T}$ must have performed the comparisons in $T\_1$, hence for each leaf in $T\_1$ there is a corresponding leaf in $\mathcal{T}$. Moreover, in each of these leaves, the element $x\_k$ defines the set $K\_1$, which are all the elements greater than $x\_k$.

How many trees like $T\_1$ are there? As many as the different choices you can make for the set $K\_1$, which is selecting $k-1$ elements out of $n$, which is exactly $\binom{n}{k-1}$. And for each of these trees, there are at least $2^{n-k}$ leaves in $\mathcal{T}$, which are essentially distinct, since they define distinct sets $K\_i$.

It follows that $\mathcal{T}$ has at least $2^{n-k} \binom{n}{k-1}$ leaves, therefore the lower bound is $\log$ of the same:

$$n-k+\log \binom{n}{k-1}$$

---
Tags: selection-problem, comparison
---


# Question
Title: Does any algorithm exist for computing the state of a non-trivial cellular automaton after an arbitrary number of time steps?
If have a cellular automaton, can I see the state of the board after something like $10^{{10}^{10}}$ time steps? For trivial cases, this is possible - for example, a cellular automaton where the state of the board is known to repeat after some finite period.

But are there any cellular automata (or perhaps even similar computational structures) that display chaotic behavior but can also be very quickly evaluated to extreme time steps into the future?

# Answer
> 1 votes
Two answers...

* There is a trivial algorithm to do it: "Just" run the automaton for the required steps.
* No, there is no *general* way to compress the computation. *If* you can prove that the automaton enters a periodic configuration, you certainly can. You can also precompute the result of a certain number of steps, and use that to skip ahead (doing several steps in one round). That is one of the ideas used to speed up finding Busy Beavers. But in general, as cellular automata are Turing-complete, to find out if you are in one of the cases where it stops or repeats is easily seen to be undecidable.

---
Tags: algorithms, cellular-automata
---


# Question
Title: Problem class of assigning N persons to N tasks, zero costs with prefs
I am looking for the general problem class / computational complexity / algorithms for the following problem:

*N tasks must be accomplished by N persons. 1 task to be done by exactly 1 person and vice versa. There is a binary preferences matrix whose (i,j) entry is 0 if person i can not do task j, and 1 if it can.*

There are no costs involved, no weights and the number of tasks equals the number of people.

I was searching for it but all I could find was the Assignment Problem which has costs/weights associated with each assignment.

As a last resort, perhaps I can transform my preferences matrix to a cost matrix if person can not do job then cost is infinite else cost is zero?

# Answer
> 1 votes
This problem is known as *maximum matching* of a bipartite graph. Basically let vertex $p\_i$ (resp., $q\_i$) represent the $i$th person (resp., task). And we connect $p\_i$ and $q\_j$ with an undirected edge iff person $i$ can do task $j$. The answer of the original problem is exactly the maximum matching of the new graph.

For algorithms, the classical *Hungarian algorithm*, of complexity $O(n^3)$, is a nice choice. Certainly you can reduce this problem to network flow, and then apply any max-flow algorithm. If you are looking for some "advanced" choices, refer to Wikipedia.

---
Tags: complexity-classes, assignment-problem, resource-allocation
---


title: Average case analysis of linear search

text:
# Question
Title: Average case analysis of linear search
Based on CLRS question 2.2:

**Consider linear search again. How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in $\theta$-notation? Justify your answers.**

I have a question regarding the average case.

*"assuming that the element being searched for is equally likely to be any element in the array"* \- what does that exactly mean? Does it mean that the probability for each to happen is $\frac{1}{n}$?

Or could it also be that the element is not in the array at all - is that a case is this probability the same as the rest (and then they are all $\frac{1}{n+1}$)?

Does it matter for the average case how many duplicated are there? Are we assumming that there are no duplicates?

A good explanation about what exactly is the average case would be helpful.

Thanks a lot!!!

# Answer
The phrase "the element being searched for is equally likely to be any element in the array" is ambiguous. It might mean two different things:

* The element is at a uniformly random *position* in the array.
* The element is chosen uniformly at random from the *set* of elements in the array.

This ambiguity suggests that the authors are making the hidden assumption that all elements are distinct, in which case both meanings coincide. Moreover, without this assumption it is impossible to determine the average-case complexity (consider what happens if all elements in the array are identical).
> 3 votes

# Answer
I wouldn't overthink it: With $n$ distinct elements you have a $1/n$ chance of a match. On average you will have to look at $n/2$ elements. That's because $\sum\_{i=1}^{n/2} 1/n = 1/2$.

Worst case of course being that you match on the last thing you look at, so have to look at all $n$ of them.
> 3 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: Is is possible to determine if a given number is xor combination of some numbers?
I have been given a number Y which is ($a$ **xor** $b$ **xor** $c$ **xor** $d$ **xor** $e$ ) of some numbers ($a$,$b$,$c$,$d$,$e$) and another no X. Now i have to determine if X is a xor combination of ($a$,$b$,$c$,$d$,$e$)

e.g - ($a$ **xor** $d$) , ($b$ **xor** $c$ **xor** $e$) , ( $a$ **xor** $e$ )

What i know clearly is that lets say X= ($b$ **xor** $d$) , Now if I xor X and Y i get ($a$ **xor** $c$ **xor** $e$), as ( $b$ **xor** $b$=0 ) and if it was some number not a xor combination (say $p$ ) then i would have got ($a$ **xor** $b$ **xor** $c$ **xor** $d$ **xor** $e$ **xor** $p$)

How should i approach this question?

# Answer
Suppose that your numbers are $n$-bit long. Then you can think of them as elements of the vector space $\mathbb{F}\_2^n$. The number $X$ can be written as an XOR of $a\_1,\ldots,a\_m$ if $X$ is in the linear span of $a\_1,\ldots,a\_m$. In order to determine whether $X$ is in the linear span of $a\_1,\ldots,a\_m$, you can use Gaussian elimination.
> 4 votes

---
Tags: discrete-mathematics, boolean-algebra, binary, bit-manipulation, xor
---


# Question
Title: Slowdown when accessing data at page boundaries?
Hi I have a program which accesses memory words that are located X bytes apart in virtual address space. For instance, `for (int i=0;<some stop condition>;i+=X){array[i]=4;}`.

I measure the execution time with a varying value of `X`. Interestingly, when `X` is the power of `2` and is about page size, e.g., `X=1024,2048,4096,8192...`, I get to huge performance slowdown. But on all other values of `X`, like `1023` and `1025`, there is no slowdown. The performance results are attached in the figure below.

I test my program on several personal machines, all are running Linux with x86\_64 on Intel CPU.

What could be the cause of this slowdown? We have tried row buffer in DRAM, L3 cache, etc. which do not seem make sense...

# Answer
> 3 votes
Go to Agner manuals page and download them all, you will find tons of interesting info there. In particular, microarchitecture.pdf says

> There is a false dependence between memory addresses with the same set and offset, i.e. with a distance that is a multiple of 4 Kbytes:

```
;Example 9.6. Sandy bridge false memory dependence
mov [rsi],eax
mov ebx,[rsi+1000H] ;False memory dependence

```

I.e. the access becomes slower because cpu thinks that it may be the same address, so the load in the second line may depend on the store in the first line and thus cpu serializes execution of these operations.

AFAIR, it wasn't changed in latest Intel cpus.

---
Tags: computer-architecture, cpu-cache, memory-hardware, virtual-memory, performance
---


# Question
Title: Language which is recursively enumerable but not recursive
Can someone provide me with some examples of languages which are recursively enumerable but are not recursive. I know that there exist some languages which are not Recursive but recursively enumerable but couldn't find such examples anywhere.. :(

# Answer
> 4 votes
The standard example is the halting problem – the language of all descriptions of Turing machines which halt on the empty input.

---
Tags: turing-machines, automata
---


# Question
Title: Constraint propagation using Projection rule
I've found this example of constraint propagation using projection rule

We have

```
C = { x1 ≠ x2, x1 ≥ x2 }

< C; x1 ∈ {1,2,3}, x2 ∈ {1,2,3} >

```

They say that applying propagation rule, does not give any simplification.

**I'm not sure why this is the case. Shouldn't we get?**

```
< C; x1 ∈ {2,3}, x2 ∈ {1,2} >

```

Other steps in the example, make sense that to me, e.g.

```
< C; x1 ∈ {2}, x2 ∈ {1,2,3} >

```

produces

```
< C; x1 ∈ {2}, x2 ∈ {1} >

```

# Answer
You apply the propagation rule to a *single* constraint.

The rules are defined in such a way that they can be applied efficiently. Otherwise, by applying the "generalized propagation rule" you could declare that a SAT instance is unsatisfiable in a single step.
> 0 votes

---
Tags: constraint-satisfaction, constraint-programming
---


# Question
Title: Does the concept of subtype require dynamic method binding?
https://en.wikipedia.org/wiki/Subtyping says

> In programming language theory, subtyping (also subtype polymorphism or inclusion polymorphism) is a form of type polymorphism in which **a subtype** is a datatype that is related to another datatype (the supertype) by some notion of **substitutability**, meaning that program elements, typically subroutines or functions, written to operate on elements of the supertype can also operate on elements of the subtype.

In the concept of "subtype", when explaining "substitutability" as "program elements, typically subroutines or functions, written to operate on elements of the supertype can also operate on elements of the subtype", does it assume/require dynamic method binding (e.g. the one specified as virtual functions in C++)?

Specifically, given a type `B` with a method `m()`, a function

```
void f(B b){
    b.m();
}

```

and a subtype `S` of `B` which redefines `m()` method, which does `S` being a subtype of `B` according to the meaning of "substitutability" in the wikipedia article mean:

1. either if calling `f()` with an instance `s` of `S`, then `b.m()` in `f()` will invoke `S.m()` instead of invoking `B.m()`, (this case requires dynamic method binding.)
2. or if replace `B` with `S` in the definition of `f()`,

```
void f(S s){
    S.m();
}

```

still work, i.e. `f()` can operate with both `B` and `S`, i.e. "subtype" only requires that`S` also has a method `m()` with the same signature as `B.m()`? (This case doesn't require dynamic method binding.)

Thanks.

# Answer
No. It doesn't even require a notion of "method" at all. Even if you have objects and methods, it doesn't necessarily require a notion of dynamic dispatch. Indeed, dynamic dispatch is only relevant if you can "override" methods (where, here, I'm \[atypically\] including implementing an interface as "overriding" \[abstract\] methods).

All subtyping states is if $t$ is a term of type $S$ then $t$ is also a term of type $T$ if $S\operatorname{\mathtt{\<:}}T$. There are a variety of ways to implement this. For structural subtyping, usually the idea is that the sub-type is representationally compatible with the super-type so that their common interface literally refers to the same code. For example, if the 3-tuple $(A,B,C)$ is represented by contiguously storing a representation of $A$, $B$, and $C$, and similarly for a 2-tuple, then a 3-tuple literally is a 2-tuple that just happens to have a representation of $C$ following it. This is represented by $(A,B,C)\operatorname{\mathtt{\<:}}(A,B)$. As another example, a sum/variant type $A+B+C$ could be represented as a tag indicating the variant and a representation of $A$, $B$, or $C$ as appropriate. If the tags are compatible, then a value of type $A+B$ literally is a value of $A+B+C$ leading to $A+B\operatorname{\mathtt{\<:}}A+B+C$. Something like dynamic dispatch could be used internally to avoid relying on representational compatibility if desired by the language implementer.

Another approach would be to have subtyping imply the *implicit* insertion of coercions from sub-types to super-types. Dynamic dispatch is just completely irrelevant to subtyping in this context.

Common object oriented languages tend to conflate subtyping and subclassing, but they are fairly different concepts. Many (most?) programming languages that have some degree of "subtyping" fail to satisfy various notions of "substitutability", so the baseline is usually just that using a sub-type as a super-type typechecks and (usually) doesn't crash. (Even that low bar fails to be met by e.g. Java and C# and certainly C++.)

You could have a language that supports dynamic dispatch which doesn't have a notion of subtyping. For example, conversions to "super-types" could be explicit.
> 3 votes

---
Tags: programming-languages, object-oriented
---