# Question
Title: Random observations of a total ordering, how much they tell us?
Suppose we have a total ordering over elements $a\_1,a\_2, ..., a\_n$, meaning there is permutation $\pi$ such that $a\_{\pi(1)}\<a\_{\pi(2)}\<...\<a\_{\pi(n)}$. But we don't know $\pi$. What we know is a set of random observations from pairwise order of the elements. The observation matrix $B\in\\{0,1\\}^{n\times n}$ is generated randomly as follows: $$B\_{i,j} \sim \begin{cases} \text{Bernoulli}(p)\qquad \text{ if } i\>j \\ 0 \qquad \qquad \qquad \text{ otherwise} \end{cases}$$ in which $p\in\[0,1\]$ is a constant. The formula above means that elements above diagonal are drawn iid from $\text{Bernoulli}(p)$ and the rest of the elements are $0$. Matrix $B$ denotes our observations of the ordering, i.e. if $B\_{i,j}=1$ we know the the the order of $a\_i$ and $a\_j$, and otherwise don't. The reason that elements on the lower triangle of $B$ are zero is because symmetric observations are reduntant.

**Question 1**

Let $K$ denote the number of orderings of $a\_1,..., a\_n$ that are consistent with our partial observations. Since $B$ is a random variable, $K$ is also a random variable. The question is, what the expected value of $K$ and what is its concentration around the mean as a function of $p$? There are two extreme cases: (1) if $p=0$ all orderings are valid and hence $K=n!$ (2) if $p=1$ we have the complete ordering and $K=1$.

For $0\<p\<1$ however $K$ would not be a constant. My guess is that for sufficiently large $n$ if $p\gg \mathcal{O}(\frac{\log n}{n})$ would lead to to $\mathbb{E}\[K\]\to 1$. The rationale behind this is that we would have $\omega(np) = \omega(n \log n)$ comparisons which is an asymptotically larger than the number of comparisons most sorting algorithms make. However, this is far from clear since the observations are taken at random.

The answer is ideally a distribution with parameter $p$ for the number of possibilities. But if that's not possible, tail bounds or the expected value and variance are also acceptable.

**Question 2**

The motivation behind the definition of $K$ was to capture how much uncertainty is left. But it seems to be overestimating it or not express it very well, because if we don't know a few pairs $K$ will grow exponentially with this number. So I was thinking of another natural way to define it.

Let $O\in\\{0,1\\}^{n\times n}$ be the result of our observations, in which $O\_{i,j}=1$ designates that we have observed $a\_i\<a\_j$. From this matrix we can compute the transitive closure $O^\star$, which applies transitive property to find all the "smaller-than" relations in the data. For example if we have $O\_{i,j}=1$ and $O\_{j,k}=1$ we will have $O^\star\_{i,k}=1$. This holds also for a chain of arbitrary length.

Let $S$ be the sum of all elements of $O^\star$. If we can conclude the relations between all pairs, $S$ will attain its maximum value of $S=n(n-1)/2$, and so $I=\frac{S}{(n(n-1)/2)}$ is a value which will show how much we know about the ordering, with $1$ meaning we exactly know the ordering, and $0$ meaning we don't know anything. Now the question is: what is its mean $\mathbb{E}\[I\]$ as a function of $n$ and $p$? And if it's possible to analyze, what is the concentration of $I$ around its mean? Also, what is the threshold for $p$ as a function of $n$ that makes $\mathbb{E}\[I\]$ jump to $0$ or $1$?

By simulations I found that when $n\to\infty$, even for a small value of $p=\frac{\log n}{n}$ leads to $I\to1$ with high probability. The reason for this seeming discrepancy between $I$ and $K$ is that if we have $m$ unknown pairs in $O^\star$, then $K$ will grow exponentially w.r.t $m$ while $S$ will only be affected linearly. Although the $I$ and $\log K$ are related, I don't think there is an exact relationship between them.

# Answer
**Answer to Question 1**

We can assume without loss of generality that the original ordering is the usual one: $a\_1 \< a\_2 \< \cdots \< a\_n$. Some ordering $\pi$ is compatible with our observations if whenever $\pi(i) \< \pi(j)$ for some $i \> j$, this observation is missing. In other words, $\pi$ is compatible with probability $(1-p)^{\operatorname{inv}(\pi)}$, where $\operatorname{inv}(\pi)$ is the number of inversions of $\pi$. Using the generating function of the number of inversions, we get that the expected number of compatible orderings is exactly $$ \mathbb{E}\[K\] = \prod\_{m=2}^n \frac{1-(1-p)^m}{p}. $$ In the same way you might be able to compute larger moments of $K$, and so obtain some concentration bounds. Whether one should expect good concentration, and for which values of $p$, remains to be seen, though perhaps it's best to perform some numerical experiments to get a feel for how this behaves.

---

**Answer to Question 2**

Let $q\_\delta$ be the probability that $O^\*$ contains $(i,i+\delta)$. We can compute by brute force \begin{align\*} q\_1 &= p, \\ q\_2 &= p + p^2 - p^3, \\ q\_3 &= p + 2p^2 - p^3 - 4p^4 + 4p^5 - p^6, \\ q\_4 &= p + 3p^2 - 11p^4 + p^5 + 30p^6 - 42p^7 + 26p^8 - 8p^9 + p^{10}, \end{align\*} and so on. Consulting the OEIS, we find the sequence of coefficients (for $-q\_\delta(-p)$) as A214670.

Given the $q\_\delta$, it is easy to compute the expectation of $I$, though since there isn't a particularly nice formula for $q\_\delta$, this won't result in a reasonable formula for $\mathbb{E}\[I\]$.

You could ask for the threshold behavior of $\mathbb{E}\[I\]$, that is, at what value of $p$ does the expectation jump from 0 to 1, and how quickly. This is a different and interesting question.
> 2 votes

---
Tags: sorting, randomized-algorithms, randomness, order-theory, ordering
---


# Question
Title: Union of a regular and a non-regular language
Let's say we have $L\_1$ which is a regular language and $L\_2$ which is not.

I understand that if $L\_1 \cup L\_2 = \Sigma^\*$ then $L\_1 \cup L\_2$ is a regular language.

Does that implicitly mean that if $L\_1 \cup L\_2 \neq \Sigma^\*$ then $L\_1 \cup L\_2$ is non-regular?

# Answer
> 6 votes
I assume you can already prove that the union, intersection, and complement of regular languages is regular.

Let $L\_1$ be regular and $L\_2$ be non-regular. Then you should also be able to prove:

1. At most one of $L\_1 \cup L\_2$ and $L\_1 \cap L\_2$ is regular.
2. If $L\_1 \subset L\_2$ then their union is irregular. (You should also be able to construct an example).
3. If $L\_2 \subset L\_1$ then their union is regular. (You should also be able to construct an example).
4. If the complement of $L\_1$ contains at least two words, there is a regular language $L\_3$ such that $L\_1 \cap L\_3 = \emptyset$ and $L\_1 \cup L\_3 \subsetneq \Sigma^\*$. Then either $L\_3 \cup L\_2$ is regular or $L\_1$, $L\_3 \cup L\_2$ are an example of a regular and an irregular language whose union is regular but where neither is a subset of the other and their union is not $\Sigma^\*$.

# Answer
> 4 votes
If $P$ implies $Q$ then it doesn't mean that not $P$ implies not $Q$.

In your case, you can take $L\_1 = 0\Sigma^\*$ and $L\_2=\\{0^{n+1}1^n : n \geq 0\\}$.

---
Tags: formal-languages, regular-languages
---


# Question
Title: Finding the cheapest buy order with fixed inflation for each product
Let's say we have a set of products $M$, a total of $|M|=n$ that we want to buy. However, we can only buy one product at a time, so that we need a total of $n$ time-units to buy all items.

Each product $p\in M$ has a base price $b\_p$, as well as an inflation rate $r\_p$.
At time unit $t$, product $p$ therefore has the price $b\_p \cdot {r\_p}^t $.
We can assume $b\_p\in \mathbb{R}$, $r\_p\>1$.

I'm looking for an efficient (i.e. polytime) algorithm that returns the optimal buying order which minimizes the total price.

There's an easier variant of the problem (all $b\_p=1$) which can be solved using the greedy algorithm
"Always buy the one product with the highest inflation".

Given that the base prices can be vastly different, this algorithm can't be directly transferred, but knowing that an easier version of the problem had a linear-time solution, this one probably still isn't $\mathsf{NP}$-complete.

If we view every product as a function of time $p\_i(t) = b\_p \cdot {r\_p}^t$, the greedy algorithm above tells us, that if for $t\_0$ holds $p\_i(t\_0) = p\_j(t\_0)$, then from the point once $t\_0$ has passed we should always pick of $p\_i, p\_j$ the one with the higher inflation.

I'd be open for both hints and solutions.

# Answer
> 3 votes
### What is the problem in the question?

The price of product $p$ at time $t$ is $b\_p{r\_p}^t $, where $p$ and $t$ are integers between 1 and $n$.. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\sum\_{p=1}^nb\_p{r\_p}^{f(p)}$ is minimum.

### A more general problem and polynomial-time algorithms

The price of product $p$ at time $t$ is $c(p,t)$, where $p$ and $t$ are integers between 1 and $n$. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\sum\_{p=1}^nc(p,f(p))$ is minimum.

The problem above is none other than the famous assignment problem. There are various polynomial-time algorithms to solve it. For example, this version of Hungarian algorithm runs in $O(n^4)$ time.

For the problem in the question, it can also be solved in polynomial time since we can compute all $b\_p{r\_p}^t$ for $1\le p, t\le n$ in $O(n^2)$ time.

# Answer
> 0 votes
some thoughts but haven't been mathematically proven. to solve the problems we need to decide the priority to buy each product

1. if $ p\_i(t) = p\_j(t) $ has crossing point at $ t\_{ij} \> 0 $, we have two cases:
2. when $ t \< t\_{ij} $ and $ p\_i(t) \> p\_j(t) $, then we want to buy $ p\_j $ sooner than $ p\_i $
3. the opposite case of 1.

this can partially define the purchase order we want for those have crossing points at $ t \> 0 $

2. to decide the purchase order of those don't have crossing point at $ t \> 0 $, we can rely on their initial price $ p\_i(0) $, e.g. if $ p\_i(0) \> p\_j(0) $, we want to buy $ p\_i $ before $ p\_j $.
3. the above two steps define a partial order of all the products, to finalize an optimal purchase order, we can enumerate all the tsort order of the graph(nodes are products, partial order as edges) to find the optimal purchase order.

time complexity:

solving 1. and 2. takes $ O(n\log(n)) $ (solving each exponential equations takes $ O(\log(n)) $ using binary search)

solving 3. takes $ O(V+E) $ where $ V=n, E\le n^2 $

---
Tags: algorithms, discrete-mathematics
---


# Question
Title: What do the symbols M and N mean in this definition of lambda terms?
I am learning lambda calculus from the book https://www.irif.fr/~mellies/mpri/mpri-ens/biblio/Selinger-Lambda-Calculus-Notes.pdf and do not understand the meaning of the following symbols.

The definition of the lambda terms is:

Lambda terms: $\mathit{M,N} ::= x | (M N) | (λx.M) $

The question is, what do $\mathit{M}$ and $\mathit{N}$ mean?

# Answer
I suggest you read the page following the supposedly cryptic notation:

> The above Backus-Naur Form (BNF) is a convenient abbreviation of the following equivalent, more traditionally mathematical definition:
>
> **Definition.** \[...\]

In said definition, it is stated that $M$ and $N$ are simply arbitrary lambda terms. (In a nutshell, it is an inductive definition.)

As to why the author prefers this notation, it is stated right after the definition:

> Comparing the two equivalent definitions, we see that the Backus-Naur Form is a convenient notation because: \[...\] the use of distinct meta-symbols for different syntactic classes ($x$, $y$, $z$ for variables and $M$, $N$ for terms) eliminates the need to explicitly quantify over the sets \[of variables and lambda terms\].
> 1 votes

---
Tags: lambda-calculus
---


# Question
Title: Correctness of an algorithm difference between recursive and iteraive
I know that the general strategy to do the correction of an algorithm is as follow :

> * if the algorithm is recursive then prove the correctness using induction
> * if the algorithm is iterative (using a for loop for example) then find an invariant

Finding an invariant is sometimes hard while induction is easy. So since every iterative algorithm can be transformed into a recursive one, why do we bother finding clever invariant while we could do :

> find the recursive equivalent algorithm -\> use induction

Maybe the part : "transform the iterative program into a recursive one" is hard, but for simple programs it's definitely worth it. I mean sometimes it is (at least for me) very hard to find invariant, but when doing induction everything is "easy".

So I guess I am missunderstanding something ?

Thank you !

# Answer
A proof using a loop invariant is also a proof by induction – you prove that the invariant is indeed an invariant by induction. The reason that finding the inductive hypothesis is easier for recursive procedures is that we usually state the semantics of the recursive function – what it is supposed to compute – and this is the "loop invariant" we use to prove its correctness.

Let's consider the following two procedures for summing an array $A\[1\],\ldots,A\[n\]$:

> Iterative:
>
> 1. $sum \gets 0$
> 2. $i \gets 1$
> 3. While $i \leq n$:
>     * $sum \gets sum + A\[i\]$
>     * $i \gets i + 1$
> 4. Return $sum$
>
> Recursive:
>
> $Sum(A\[1\],\ldots,A\[n\])$
>
> 1. If $n = 0$, Return $0$
> 2. If $n \> 0$, Return $Sum(A\[1\],\ldots,A\[n-1\]) + A\[n\]$

The loop invariant for the iterative algorithm is $sum = A\[1\] + \cdots + A\[i-1\]$. This is something we have to come up with. We prove that it holds by induction, and conclude that the function returns $A\[1\] + \cdots + A\[n\]$.

In contrast, it is clear what $Sum$ is supposed to compute: the sum of its input. We still need to argue inductively that $Sum$ works correctly, but the inductive hypothesis $$Sum(A\[1\],\ldots,A\[i\]) = A\[1\] + \cdots + A\[i\]$$ corresponds to the semantics of $Sum$.

We often attach a meaning to recursive procedures, but not so often to loops. If we did attach a semantic meaning to the $i$'th iteration, it would become easy to formulate the loop invariant. An example is the Floyd–Warshall algorithm (or rather, some of its implementations), where the $i$'th iteration computes the shortest path of length at most $i$.
> 4 votes

---
Tags: algorithms, correctness-proof
---


# Question
Title: Identifying the Equivalence Classes of a Language with equal number of 10 and 01 strings
I'm doing a problem where I need to find the equivalence classes of the language below:

Let A = {x ∈ {0, 1}\* | #(01, x) = #(10, x)}, where, for a, b ∈ {0, 1}\*, #(ab, x) is the number of places in x where an a is immediately followed by a b.

So I can start to see some equivalence classes. 1\* and 0\* both are in A, because they both have zero 10's and 01's, so the condition holds. I don't really know how I would describe the other equivalence classes?

Any help would be great!

# Answer
> 1 votes
It's a trick question.

They try to make you think that you have to count how many 01 strings and how many 10 strings there are, but you don't have to.

Say the first letter is 0. So far, no 01 and no 10 strings. This doesn't change if there are more zeroes. But if we find a 1, we now have got a 01 string. Nothing changes until we get a zero, and we have one 01 and one 10 strings. Again, more zeroes don't change this, the next 1 means the number of 01 strings is one higher than 10, and the next 0 after that makes the number equal again.

You can see that if we start with a 0 and process more letters, every time the string ends with a 1 the 01's are one ahead of the 10's, and when the string ends with a 0 their counts are equal.

You do the same for the case that the string starts with a 1. Again the counts are equal every time the last digit is a 1 and unequal every time the last digit is 0. Counts are equal every time the first and last digits are the same.

---
Tags: finite-automata, sets
---


title: Interesting logic problems

text:
# Question
Title: Interesting logic problems
I've just began a course on logic and learned the following :

> * De Morgan's laws
> * Normal forms
> * How to represent a logical formula (using or, and, not operators) using binary trees
> * How to get the conjunctive normal form of a formula

It's obviously not much, but the subject interested me a lot and it was enough to study the 2-SAT and the 3-SAT problems. These two problems were very interesting to study.

I am wondering if there are other classical/interesting algorithms problem in logic (just as 2-SAT, 3-SAT) that can be studied with the little I know about logic?

# Answer
Rather than going to talk about algorithms and more about SAT, this answer tries to show that there is more than just one kind of logic and that there are also different kinds of approaches.

I won't go into detail much but rather provide a list with some topics and keywords that should form a good basis to do some research:

---

### Higher order logic

There are many ways of extending the propositional logic as you know it, for example (first order logic) with the quantifiers $\forall$ and $\exists$ quantifiers.

**Keywords**: First/second order logic (with equality), free/bound variables, Skolem normal form

---

### Type theory

This is basically just another higher order logic, but it's a very rich topic and in my opinion deserves its own category since it plays a special role in CS.

**Keywords**: $\Pi$-/$\Sigma$-types, subtypes, quotient types, Curry-Howard correspondence, (un)typed $\lambda$-calculus, System F, Martin-Löf type theory, $\lambda$-cube

---

### Proof systems

These can vary from classical logic as you know, but can be more abstract working with other syntactical objects than Boolean values or predicates. Generally they define some set $\mathcal{X}$ of objects (formulas/syntax), a truth-assigning function $t: \mathcal{X} \to \\{\texttt{false},\texttt{true}\\}$ (defines semantics), some notion of proofs and a way to (efficiently) check whether a proof is valid.

**Keywords**: Completeness & soundness, Gentzen/Hilbert style proofs, resolution calculus, Sequent calculus, Intuitionistic logic, Formal verification, temporal logic etc.

---

If this was not specific enough, here is one thing I found fascinating when I first learned about logic:

$$ \lnot \exists x . \forall y . \bigl ( F(x,y) \longleftrightarrow \lnot F(y,y) \bigr ) $$

The above formula is a tautology (ie. always true) for any domain $\mathcal{U}$ and predicate $F$. Now usually this is not very interesting, but

* define $\mathcal{U}$ as the set of all sets, $F(x,y) = y \in x$ and we get Russell's paradox, or
* define $\mathcal{U}$ some fixed enumeration of $\\{0,1\\}^\infty$, $F(x,y) = \text{$x$th bit of $y$}$ (now interpreting $\longleftrightarrow$ as equality on $\\{0,1\\}$) and we get Cantor's diagonalisation argument

which I find quite interesting.
> 4 votes

# Answer
Depending on how 2-SAT and 3-SAT were defined, you might have learned that they may be expressed as *decision* or *search problems*. For example, the decision version of 2-SAT is "Given the 2-SAT formula $\varphi$, is $\varphi$ satisfiable?" while the search version asks for a concrete variable assignment under which $\varphi$ is true.

You might have also learned that 2-SAT is efficiently solvable (i.e., there is an algorithm which solves it using a polynomial number of steps in the length of $\varphi$), whereas we do not know whether this is the case for 3-SAT. These observations are related to the open question $\textbf{P} \stackrel{?}= \textbf{NP}$.

Now, to address your question regarding interesting problems. There is a natural generalization of SAT as the *counting problem* #SAT, that is, "Given the formula $\varphi$, under how many different variable assignments is $\varphi$ true?" As far as we know, this problem is much harder than (3-)SAT since, if you are able to solve it efficiently, then you can also solve (3-)SAT efficiently (namely the formula is satisfiable if and only if it is true under at least one variable assignment).

Another generalization possible in the same sense is MajoritySAT: "Given the formula $\varphi$, is $\varphi$ true under the majority of (i.e., more than half the possible) variable assignments?" As it turns out, being able to solve this and being able to solve #SAT are in a certain sense *equivalent*: You can use one of the two problems to solve the other efficiently (by making an appropriate series of "questions"). In complexity-theoretic terms, the two problems are polynomial-time (i.e., efficiently) *Turing reducible* to one another. Solving MajoritySAT using #SAT is relatively straightforward (can you see why?); the other direction is more intricate and an important complexity-theoretic result.

Other generalizations of SAT are *quantified Boolean formulas* (QBFs), that is, formulas with quantifiers (i.e., "$\forall$" and "$\exists$"). And yet another problem is *logical equivalence*: "Given the formulas $\varphi\_1$ and $\varphi\_2$, are they equivalent (i.e., under the same assignment, $\varphi\_1$ is true if and only if $\varphi\_2$ is true)?" You might want to ponder about whether these are harder or easier to solve (in whatever sense) than the other problems I have previously mentioned.

I hope this qualifies as some suggestions of "interesting" problems. As you can see, one can address many topics in complexity theory (even if indirectly) while only referring to SAT and its generalizations.
> 2 votes

---
Tags: logic, decision-problem, search-problem
---


# Question
Title: Can there still be infinite recursion if I remove all left recursion?
I have to transform the following grammar into a non left recursive grammar:

S → aSb | bAS

A → AaA | bAA | AAa | bAb

This is what I came up with:

A → bAAA’| bAbA’

A’ → aAA’| AaA’| ε

S → aSb | bAS

As far as I can tell, there is no more left recursion because none of the leftmost symbols on the RHS are the same as the nonterminal on the left. However, assuming S is the starting symbol, there is still infinite recursion because A calls itself repeatedly. Is this expected? Or did I derive the non left recursive grammar incorrectly?

# Answer
Take a look at the following rule in the original grammar.
$\quad S \to aSb \mid bAS$
If you start generation from $S$, you cannot get rid of $S$.
$\quad A \to AaA \mid bAA \mid AAa \mid bAb $
If you continue applying production rules from a sentential form that contains $A$, you cannot get rid of $A$, either.

These rules are called unproductive rules. Unproductive rules and unreachable rules are called useless rules. You may take a look at this question.

If there are useless rules in the original grammar, there will be useless rules after the transformation by pure left-recursion removal procedure. That is why you see "there is still infinite recursion because $A$ calls itself repeatedly". There is nothing wrong with your transformation to that non-left-recursive grammar.

Those useless production rules can be remove by some algorithms. We can see that the original grammar in the question will become empty after such cleaning. Indeed, the original grammar generates the empty language, the language that contains no words.
> 0 votes

---
Tags: formal-grammars, compilers, left-recursion
---


# Question
Title: Would any continuous model of the universe have/be based on hypercomputational laws?
I've read that when Turing-Church thesis is applied to the universe and physics, one of the three interpretations that we can use and is defended by some important physicists is that:

> "The universe is a hypercomputer and then it is possible to build more powerful machines than Turing machines. For this it would be enough for the universe to be continuous and make use of that continuity (another question is how dense its continuity is), using the results of said supercomputer as input"

Would that mean that every continious (or "continously-enough") model of spacetime and the universe could have fundamentally hypercomputational physics (physics described and based in hypercomputation and hypercomputational processes and laws/rules, describing a hypercomputer-like universe)? Or on the contrary only certain models could do it? In that case, can you think of any in particular?

# Answer
If you are interested in the effect of being able to compute with continuous real numbers, you might enjoy learning about the Blum-Shub-Smale theory of computation with the reals. A good survey is Computing over the Reals: Where Turing Meets Newton by Lenore Blum. Wikipedia states that the set of functions that are computable in this model are incomparable with the set of functions that are computable in the usual model, and gives a citation where you can read more. It's not clear to me exactly how that result should be interpreted, though.
> 3 votes

# Answer
It's a bit vague to talk about "models of universe". Let's stick to models of mathematics, as these are actually well understood. For example, we can ask about a topos (a model of a certain kind of set theory and higher-order logic, sufficient to develop theoretical physics) in which every map is continuous. Does it follow that some of the maps must be non-computable in such a topos?

No. In the realizability topos based on the computable version of Kleene's function realizability all maps are continuous (internally) and there is no non-computable map.

There are other toposes in which every map is continuous *and* there are also non-computable maps, for instance the realizability topos based on Kleene's function realizability.

In fact, the implication goes in the other direction: *computable* implies *continuous*. That is to say, if we allow ourselves some vagueness: in any universe in which all processes are computable, all processes are also continuous. (But not the other way around.)
> 2 votes

---
Tags: computability, undecidability, computation-models, church-turing-thesis, hypercomputation
---


# Question
Title: Look Ahead buffer vs Translation Look aside buffer
I know that **Translation look aside buffer** is used for address translation in paging to achieve better performance.

I came across term called **Look Ahead buffer** in a document which said it implements Temporal locality.

I tried searching for **Look Ahead buffer's** but could not get any significant data.

Please help

# Answer
> 9 votes
I do not know the exact definitions of TLBs and look-ahead buffers, but here is what I understand about them.

TLBs help make translations from virtual to physical addresses quicker via caching. So, you can see how the TLB is implementing temporal locality (any kind of caching is implementing temporal locality) in some sense.

Look ahead buffers on the other hand come into play when while bringing data from disk to memory. Pages that are explicitly requested may be brought into the disk buffer along with other pages (often selected based on spatial locality to the requested page -- but there are other heuristics that the disk can use). The idea is to not have to go to disk too often. Instead the disk will try to predict what pages will be required in the RAM in the future (hence the term "look-ahead").

Note: I have heard people call the TLB the look-aside buffer and the look-ahead buffer. To me it seems like "translation look-aside buffer" is the correct expansion (because I dont see where any "looking ahead" is happening).

# Answer
> 1 votes
As you have already stated that concept of `look-aside buffers` are used in TLAB .Similarly the `look-ahead buffers` have very important usage in data compression techniques ( especially the LZ family of algorithms which are cornerstone of compression techniques ). This algorithm divides the stream into 2 segments. Left segment ( or buffer) is search buffer which contains the symbols already encountered and processed. The right segment is termed look ahead buffer which contains symbols yet to be encoded. An excellent explanation can be found here

# Answer
> -3 votes
yes look-ahead buffer can be implemented by **working set** algorithm to take care of **spatial locality**.

---
Tags: operating-systems, paging, virtual-memory
---


title: Negative simple path NP-Complete

text:
# Question
Title: Negative simple path NP-Complete
Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$

My approach was to reduce this from the Hamiltonian path and I know I should somehow force the solver to go through as many vertices as it can to get a Hamiltonian path but I am not sure how to construct such a reduction

# Answer
> 2 votes
You can reduce from the Hamiltonian path problem. Given an instance of the Hamiltonian path problem with $n$ vertices:

1. Add a start vertex $s$ and an ending vertex $t$.
2. For every vertex $v$ that is not $s$ or $t$, add edges $(s, v)$ and $(v, t)$ with weight $n-1$ and $n-2$ respectively.
3. For every other edge, assign it weight $-2$.

Now the previous graph has an Hamiltonian path if and only if there is a simple path with negative total weight from $s$ to $t$ in the new graph.

# Answer
> 1 votes
Let $G=(V,E)$ be an instance of Hamiltonian $st$-path. Construct an instance of negative $st$-path $G'$ such that $G' = G$ with a new vertex $t'$ and the edge $tt'$ added. Set the weight of $tt'$ to $|V|-2$ and every other edge weight to $-1$.

The claim is that $G$ has a Hamiltonian $st$-path iff $G'$ has a negative $tt'$-path.

* In the first direction, let $P$ be a Hamiltonian $st$-path in $G$. By definition, $P$ visits each vertex exactly once, so $P$ has total weight $1-|V|$ in $G$. So by taking $P \cup \\{t,t'\\}$ we have a path from $s$ to $t'$ in $G'$ with total weight $1-|V|+|V|-2 = -1$, as required.
* In the second direction, suppose that there is a negative $st'$-path $P$ in $G'$. Because $t'$ has degree 1, any such $P$ must use the edge $tt'$ which has weight $|V|-2$. Further, as $P$ has negative total weight and the weight of every other edge is $-1$, it holds that $P$ also uses at least $|V|-1$ edges. In fact, as $P$ is simple, it uses exactly $|V|-1$ edges all of which are in $G$. So by taking $P \setminus \\{t,t'\\}$ we obtain a Hamiltonian $st$-path in $G$.

This completes the proof.

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


# Question
Title: Can you prevent a man in the middle from reading the message?
I have heard about all these Man-In-The-Middle Attack preventions and I am wondering, how this can possibly work if the man in the middle only listens to your stream and does not want to change the message itself.

Can the man in the middle not just take the keys swapped by the opponents, change the keys and then decrypt and encrypt the message again?

How can a certificate prevent this?

Edit:

I have heard that the certificate authority generally says: "Yeah, that is the other ones key". But how can I be certain, that the signature of the certificate is not fudged?

# Answer
> 10 votes
> Can the man in the middle not just take the keys swapped by the opponents, change the keys and then decrypt and encrypt the message again?

**Yes, they can.**

A key exchange protocol like (the "textbook" version of) DH is secure against eavesdropping (i.e., simply observing what is being transmitted on the channel), but completely breaks down against man-in-the-middle (MITM) attacks, as you have stated.

Certificates are an attempt remedy this, but another problem arises: *How can you ensure both parties receive the correct certificate?* Obviously you cannot just send the certificates over the insecure channel since this is again susceptible to a MITM attack.

The solution is the existence of an *alternative, (completely) secure channel*. This would be either the two parties meeting in person and exchanging their certificates physically or over some alternative, trusted channel (e.g., over telephone, if it can be trusted).

In computer networks, the alternative channel is usually a public-key infrastructure (PKI). This means your operating system or browser has a set of preconfigured *root certificates* from which other certificates are signed (and possibly even further certificates using these as *intermediate certificates*). Hence, when you visit some website, it presents a *signed* certificate, which is signed using (a chain of) certificates which you already trust. Then, by using this certificate, an *authenticated* key exchange is possible (e.g., to agree on an ephemeral key to use with ordinary symmetric encryption).

# Answer
> 5 votes
In a man-in-the-middle attack, you ask Bob for his key but Eve intercepts the message and sends you her key instead. She asks Bob for his key and then passes messages between you and Bob, decrypting them, reading and/or changing them in the process.

The problem is that you don't know whether or not you really have Bob's key. Certificates get around this because the certification authority (CA) gives Bob a digitally signed message saying "Bob's key is 12345". You can verify this certificate because there aren't many CAs so your browser just contains a list of valid CA keys. Now, if Eve intercepts your attempt to start encrypted communication with Bob, she has two choices. If she tells you that Bob's key is 67890, then either she doesn't provide a certificate and you say "Sorry, you need to prove that" or she provides a fake certificate and you say "That certificate isn't valid." Alternatively, she tells you that Bob's key is 12345 and provides a valid certificate of that, but this is no use to her because she doesn't know Bob's private key, so she can't decrypt the messages she's relaying between the two of you.

---
Tags: cryptography, security
---


# Question
Title: Is the Shakespeare Programming Language Turing complete?
I was reading about tge Turing machine. I also came across with the `Shakespeare` programming language. After trying to understand the basics of the PL, I thought that it must be non-Turing complete. On some page I found out that I was wrong and `Shakespeare` is actually "turing complete".

I didn't find how can I create while loops or recursive calls in `Shakespeare` so I can't understand why it us Turing complete.

Will be glad for some explanation.

# Answer
> 4 votes
In that page, the snippet

```
Juliet:
 Am I better than you?

Hamlet:
 If so, let us proceed to scene III.

```

essentially means

```
if (Juliet > Hamlet) goto Scene III

```

This can be used to implement `while` loops. In pseudo syntax:

```
Scene II:
if (Juliet > Hamlet) goto Scene III
... some statements here
goto Scene II
Scene III:
... more statements here

```

is essentially equivalent to

```
while (Juliet <= Hamlet) {
   ... some statements here
}
... more statements here

```

---
Tags: turing-machines, programming-languages
---


title: Reduce to Beta Form Verification

text:
# Question
Title: Reduce to Beta Form Verification
What is the normal form of the following lambda term? I'm stuck between two answers and I just wanted to know which one is correct.

$$\lambda y. (\lambda x.x)\ y$$

Possible Answer 1: $\lambda x.x$
Possible Answer 2: $\lambda y.y$

# Answer
The two terms you've come up with are $\alpha$-equivalent – they're thesame except for the names of the variables. Normally, $\alpha$-equivalent terms are considered to be the same thing so, without knowing anything more about the situation, both of your possible answers seem to be correct.
> 2 votes

---
Tags: lambda-calculus
---


title: No Lambda Normal Form

text:
# Question
Title: No Lambda Normal Form
How can we show that the term $\Omega = (\lambda x.x\ x)\ (\lambda x.x\ x)$ does not have a normal form? Building on this, what is an example term different than Omega that is not normalizing (meaning a term that every reduction sequence starting from it is infinite)?

# Answer
> 3 votes
If a term has a normal form then there is a sequence of $\beta$-reductions leading to it. However, $\Omega$ has only one $\beta$-redex, which leads back to $\Omega$. Therefore, because $\Omega$ is not already in normal form it has no normal form.

It is easy to generate other terms that have only infinite chains of reductions. For instance, the related $Y$ combinator $Y = \lambda f . (\lambda x . (f (x x)) (\lambda x . (f (x x))$ gives $$Y \to \lambda f . f Y \to \lambda f . f(f Y) \to \lambda f . f(f(f Y)) \to \cdots$$ Note that by applying $Y$ to a specific $f$ we may get a normalizing term (because for a specific $f$ there will be additional reductions that may lead to a normal form). In fact, $Y$ is quite useful because for any term $g$ we have $Y g = g (Y g)$, so $Y$ computes fixed points.

# Answer
> 2 votes
It's very easy to show that $\Omega$ has no normal form, because there's only one way to reduce it: $\Omega = (\lambda \color{magenta}{x}. \color{magenta}{x} \color{magenta}{x}) \color{magenta}{(\lambda x. x x)} \to\_\beta (\lambda x. x x) (\lambda x. x x) = \Omega$. The set of lambda terms that $\Omega$ reduces to is the singleton $\\{\Omega\\}$. Since $\Omega$ reduces, it is not in normal form, so it does not reduce to any term in normal form.

More generally, a term is non-normalizing iff no sequence of reduction from this term ends in a normal form, i.e. every reduction sequence is infinite. There are two ways a reduction sequence can be infinite: it can either loop back at some point ($M\_0 \to\_\beta M\_1 \to\_\beta \ldots \to\_\beta M\_n \to\_\beta \ldots M\_{n+k} = M\_n $), or it can involve infinitely many different terms (in which case the terms have to grow larger asymptotically, because there are only finitely many distinct terms of any specific finite size). More formally, the sequence of expansions either repeats or doesn't repeat. Of course, from a given term, it's possible to have some sequences that reach a normal form, others that repeat and yet others that reach infinitely many terms, depending on the choice of regex at each stage.

You can build simple examples of looping or growing terms by tweaking $\Omega$. For example, $(\lambda x. I x x) (\lambda x. I x x)$ can loop in various ways: $$ \begin{align\*} (\lambda \color{red}{x}. I \color{red}{x} \color{red}{x}) \color{red}{(\lambda x. I x x)} \to\_\beta & I (\lambda x. I x x) (\lambda x. I x x) \to\_\beta (\lambda x. I x x) (\lambda x. I x x) \\ (\lambda x. I x x) (\lambda x. \color{blue}{I} \color{blue}{x} x) \to\_\beta & (\lambda x. I x x) (\lambda x. x x) \to\_\beta I (\lambda x. x x) (\lambda x. x x) \\ (\lambda x. \color{green}{I} \color{green}{x} x) (\lambda x. I x x) \to\_\beta & (\lambda x. x x) (\lambda x. I x x) \to\_\beta (\lambda x. I x x) (\lambda x. I x x) \\ \end{align\*} $$ And here's a straightforward example of a term that keeps growing: $$ (\lambda x y. x x) (\lambda x y. x x) \to\_\beta \lambda y\_1. (\lambda x y. x x) (\lambda x y. x x) \to\_\beta \lambda y\_2. (\lambda y\_1. (\lambda x y. x x) (\lambda x y. x x)) \to\_\beta \ldots $$

With a programmer's intuition, you get a growing chain with a recursive function that keeps using more and more memory, and a looping chain with a recursive function that works in bounded memory (typically obtained through tail recursion).

The shape of the reductions of a term is captured by its Böhm tree. A term has a normal form iff its Böhm tree is finite; if a term lacks a normal form then at least one of its branches is infinite, either by growing indefinitely or by looping back to a node in the tree.

There are also non-syntactic ways of characterizing terms without normal forms. For example, with intersection types, you can characterize the terms without a normal form: they are terms that lack a type without $\top$ (i.e. a term has a normal form iff it has a type without $\top$). Of course, type checking is undecidable for intersection types.

---
Tags: lambda-calculus
---


# Question
Title: Which word could I use for the Pumping Lemma proof?
I have the language

$ A\_{1} \triangleq\left\\{a w c^{l} d^{m}\mid l \in \mathbb{N} \wedge m \in \mathbb{N}^{+} \wedge w \in\\{a, b\\}^{\*} \wedge |\left.w\right|\_{a}=l+m\right\\} \operatorname{with} \Sigma \triangleq\\{a, b, c, d\\} $

and I have no idea which word I should use to prevent a case distinction.

My first idea was to set $l = 0$ and $w=b^n$ so I would have the word $p=aa^nd^n$. The problem with that is, I have no idea how to proof this because this single "a" makes me crazy. Do you could help me?

# Answer
> 1 votes
If we want to use the usual pumping lemma for regular languages as introduced in most textbooks to prove a given language is not regular, the way to avoid or reduce case distinction in showing a word cannot be pumped is to

* select that word so that its front part is in a very restricted form and at least at long as the pumping length.
* combine all cases into very few or only one case conceptually.

Let me take the language in the question as an example.

To show $A\_{1} \triangleq\left\\{a w c^{l} d^{m}\mid l \in \mathbb{N} \wedge m \in \mathbb{N}^{+} \wedge w \in\\{a, b\\}^{\*} \wedge |\left.w\right|\_{a}=l+m\right\\}$ is not regular, let us suppose our adversary Adriana claims $A$ is regular with pumping length $p$. In order to beat Adriana, we select word $w=aa^pd^p\in A\_1$. Adriana claims that $w=xyz$ for some $x,y,z$ such that $|xy|\le p$, $|y|\ge1$ and for all $n\ge0$, $xy^nz\in A$.

It looks like we have to make a case distinction, because Adriana could decompose the word in many ways. For example, Adriana could have any one of the following decompositions.

1. $ x=\epsilon, y=a^{j}$ and $ z=a^{p+1-j} d^{p}.$
2. $ x=a, y=a^{j}$ and $ z=d^{p-j} d^{p}.$
3. $x=aa^i, y=a^{j}$ and $ z=d^{p-i-j} d^{p}.$
4. $\cdots$.

We have to prove Adriana is wrong in every possible case. **There is no way around that**, as Adrianna is free to choose any one of them.

However, a little dose of abstraction and intelligence will enable us to treat all cases simultaneously.

Since $|xy|\le p$ and all $p$ letters at the front of $w$ are $a$'s, $y$ must contain $a$ only. Suppose $y=a^i$ for some $i\>0$. Then $xz=xy^0z$ contains less number of $a$'s than $w$ but the same number of $c$ and $d$ as $w$. That means $xz\not=A\_1$. We beat Adriana as if she has only one case.

Hopefully this strategy answers your question. Indeed, it should be applicable to almost all similar problems in the course of your study where you want to prove a language is not regular.

---

Here are a few exercises about the languages you have encountered.

**Exercise 1.** Prove the language $C \triangleq\left\\{a^{m} b^{n} c d^{n} d^{m} \mid n, m \in \mathbb{N} \wedge m \leq 3\right\\}$ is not regular "without case distinction".

**Exercise 2.** Prove the language $B \triangleq\left\\{w \in \Sigma^{\*} \mid |\left.w\right|\_{b} \neq|w|\_{c} \right\\}$ is not regular "without case distinction".

**Exercise 3.** Prove the language $A \triangleq\left\\{(a b)^{n} c^{n} | n \in \mathbb{N}\right\\}$ is not regular using two combined cases.

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: All pair shortest path in a tripartite graph
I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination vertex. Also, all vertices in the source set are connected to all vertices in the bridge set, and all the vertices in destination set are connected to all the vertices in the bridge set.

Let $n$ be the cardinality of both the source and the destination set, and $m$ be the cardinality of the bridge set.

A naive algorithm can compute these in $\mathcal{O}(n^{2}m)$ comparisons. On the other hand, since we are computing $n^{2}$ quantities, so the complexity will be at least $\mathcal{O}(n^{2})$.

My guess is that it can be done in $\mathcal{O}(n^{2}\log m)$ using priority-queue. So question is, whether my guess is correct and if not, then what is the complexity of solving this problem?

Edit:

Note that shortest path between a vertex in the source set to any vertex in the bridge set is the direct link, and same holds for the shortest path between the bridge and destination set.

# Answer
> 2 votes
Your problem is essentially $(\min,+)$ matrix multiplication, also known as tropical matrix multiplication. This is because you're computing $$ C\_{ik} = \min\_j (A\_{ij} + B\_{jk}), $$ which is the same formula as usual matrix multiplication, with $\min$ replacing sum and $+$ replacing product.

Usual fast matrix multiplication algorithms cannot be used for this task. Furthermore, the APSP hypothesis in fine-grained complexity states that there is no $O(n^{3-\epsilon})$ algorithm for APSP. Since APSP reduces to logarithmically many tropical matrix multiplications, this implies that the latter also has no $O(n^{3-\epsilon})$ algorithms.

On the other hand, some $n^{o(1)}$ factors can be shaved, so for example a paper of Ryan Williams, Faster all-pairs shortest paths via circuit complexity.

---
Tags: graphs, asymptotics, dynamic-programming, shortest-path
---


title: Bertrand's ballot theorem

text:
# Question
Title: Bertrand's ballot theorem
I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s\_ballot\_theorem theorem. it is this

If i number of people voted for A and j number of people voted for B then dp\[i\]\[j\] counts the number of ways voting can happen.

dp\[ i \] \[ j \] = dp\[ i \] \[ j - 1 \] + dp\[ i - 1 \] \[ j \] .

basically, I want to find the number of ways candidate A is in the winning position throughout. Can anyone explain the logic behind the dp equation ? I think it works like this. We have a sequence of A and B.In which A wins throughout. Now we add one more A to that sequence or add one more B to it.

# Answer
Let $N(p,q)$ be the number of sequences containing $p$ many A's and $q$ many B's, such that in every non-empty prefix, the number of A's strictly exceeds the number of B's. Clearly $N(p,q) = 0$ if $q \geq p$ and $q \> 0$. When $p = q = 0$ there are no non-empty prefixes, and so $N(p,q) = 1$.

Suppose therefore that $p \> q$, and consider any sequence satisfying the condition. If we remove the last element, we still get a sequence satisfying the condition. Conversely, whatever element we add, the resulting sequence will satisfy the condition, since $p \> q$. We conclude that $$ N(p,q) = \begin{cases} 1 & \text{ if } p=q=0, \\ 0 & \text{ if } q \geq p \text{ and } q \> 0, \\ N(p-1,q) + N(p,q-1) & \text{ if } p \> q \> 0, \\ N(p-1,q) & \text{ if } p \> q = 0. \end{cases} $$
> 2 votes

---
Tags: algorithms, dynamic-programming, probability-theory, number-theory, game-theory
---


# Question
Title: Halting Problem, Typed Version: A Headache
After many years, I have been revisiting the venerable old Halting Problem and the self-referential / diagonalization “party trick” that shows that there is no Turing Machine able to solve it.

I was bothered by the fact that it was, and continues to be, stated in an untyped manner, and thus is a bit sloppy for my tastes.

Let's call `HALTP` be the (actually, "an") always-halting Turing Machine (TM) which can decide whether a pair *\[Turing Machine, Input\]* is a combination that halts (the P is coming from the P convention.)

Once typing is considered when one feeds the representation of `HALTP` (actualy, the representation of a slightly modified version of `HALTP`) to the `HALTP` Turing machine itself, things fall a bit apart.

# Preliminaries

(Actually you can just go directly to "typing" as everything here is rather unsurprising)

* All the TMs that we are talking about are ‘a-machines’, as opposed to the (more interesting) ‘o-machines’ which have access to “Oracle Tapes”. They are implementations of functions taking input, running to completion (or not) and yielding output.
* There is an Universal TM called `UTM_L`, able to simulate any other TM, if that TM has been expressed as some finite string of symbols chosen from a finite alphabet $L$ (which is assumed to be possible).
* A string from $L^\*$ representing the Turing Machine with the name `MYTM` is written `<MYTM>`, and thus the "code" of `MYTM`.
* Not every string from $L^\*$ represents an actual TM (some strings have no meaning and cannot be run by `UTM_L`). We mark the subset of valid TMs as $L^\*\_{valid} \subset L^\*$ (I state w/o proof that $L^\*\_{valid}$ this is a decidable language).
* We assume that all the TM are run by `UTM_L`, which also is a multitape machine with disjoint symbol sets for each tape. The following tapes are assumed to exist:
    + ✇I = Input Tape containing elements from a language $TREE$ (see below).
    + ✇P = Program Tape containing a `<TM>` from a $L^\*\_{valid}$ to be emulated.
    + ✇W = Work Tape (not further examined)
    + ✇O = Output Tape containing strings from the 4-element language: { ⊥, ⊤, ⚠, ∅ }. ✇O originally only contains ∅, which is replaced by one of the other three words.
* *With* loss of generality we only consider TMs which accept / reject elements of a given language. The functions they implement are not "constructive".
* Every TM accepts elements of a language $TREE$ on ✇I. $TREE$ is informally defined as: "The bracketed expressions build from comma-separated `<TM>`, strings from a language $W\*$ built from a finite set of symbols disjoint from $L$, the elements of which we denote with `<w>` and elements from the language $TREE$". For example: `[<TM1>, [], <w0>, [<w1>, <w2>]]`.
* Finally, we define:
    + DECIDER TM: The TM is presented with `<w>` on ✇I. It always halts and replaces the ∅ sign on ✇O with:
        - ✇O = ⊤ if TM accepts `<w>`
        - ✇O = ⊥ if TM rejects `<w>`
        - ✇O = ⚠ if there is a type error (see below)
    + RECOGNIZER TM: The TM is presented with `<w>` on ✇I. It may or may not halt.
        - ✇O = ⊤ if TM halts and accepts `<w>`
        - ✇O = ⊥ if TM halts and rejects `<w>`
        - ✇O = ⚠ if there is a type error 8see below)
        - ✇O = ∅ if TM does not halt (a bit of a language abuse as it just means that the original ∅ symbol on ✇O will never be replaced).

# Typing

Now, we implement “typing” in as follows:

We add “type judgements” to our Turing Machine description toolset. Type judgements are not found on tapes, they are part of the specification of TMs.

We need just two type judgements:

* `<tm>: TM` – The word `<tm>` on the ✇I represents a TM from $L^\*\_{valid}$
* `<x>: TREE` – The word `<x>` on the ✇I is an element from $TREE$.

We assume that when a TM is run on input `<w>`, i.e. when we compute `TM(<w>)`, the TM performs a type check and decides whether `<w>` passes all type judgements given in its definition. If `<w>` does not pass, the TM outputs ⚠ on the ✇O and halts.

# Define HALTP

So, we suppose that there is a TM called `HALTP` with obeys the following specification:

---

* `HALTP( [<tm>: TM, <x>: TREE] )` meaning that `UTM_L` implementing it shall expect
    + On ✇P: `<HALTP>`
    + On ✇I: The finite word from $TREE$ represented by `[<tm>, <x>]` where `<tm>` and `<x>` fulfill the type judgements.

If the initial type check on ✇I fails, ✇O = ⚠

Otherwise, we expect flawless performance and halt-in-all cases and:

* ✇O = ⊤ if the TM given by `<tm>` halts and accepts `<x>`
* ✇O = ⊥ if the TM does not accept `<x>` (does not halt or rejects `<x>`)

---

# The Problem

In the diagonalization approach, we feed `<HALTP>` to `HALTP` (actually `<the complement of HALTP>` to `HALTP`, but let’s keep going). So let’s try that here:

**Does `HALTP` halt on input x?**

`HALTP( [<HALTP>: TM, <x>: TREE] )`

But what is `<x>`?

`<x>` must evidently be something that can be given to the TM represented by the first argument i.e. `HALTP`, otherwise this call is entirely meaningless.

`HALTP` expects and argument matching `( [<tm>: TM, <x>: TREE] )`

so we need to actually call `HALTP` like this, as we want to call `HALTP` on `HALTP`:

**Does `HALTP` halt on input itself on input x?**

`HALTP( [<HALTP>: TM, [ <HALTP>: TM, <x’>: TREE]] )`

But what is `<x’>`?

`<x>` must evidently be something that can be given to the TM represented by the second argument i.e. `HALTP`, otherwise this call is entirely meaningless.

so we really need:

**Does `HALTP` halt on input itself on input itself on input x?**

`HALTP( [<HALTP>: TM, [ <HALTP>: TM, [ <HALTP>: TM, <x’’>: TREE]]] )`

and so on ad infinitum.

The effort to build a meaningful argument to `HALTP` seems to fail due to an infinite regress and the question "what happens if we give HALTP to HALTP" does not make sense because giving `HALTP` to `HALTP` is nonsensical.

The textbook proof seems to absolutely ignore this problem, it assumes that calling

`HALTP( <HALTP>, <HALTP> )`

makes sense.

For example, the extract below is from Michael Sipser’s *“Introduction to the Theory of Computation, 2nd Edition”*, 2006, p. 179. In particular, it compares "running `HALTP` on itself" with a compiler in Pascal compiling the compiler for Pascal – but that is not the same thing at all because the argument to the compiler is meaningful **without an additional argument to the compiler-to-be-compiled**.

How to to fix that?

# Answer
> 4 votes
In general, a type system can affect the expressivity of a programming language and make it less expressive -- sometimes to the point of turning a Turing-complete language into a non-Turing-complete language. (In other words, the introduction of a type system can in some cases restrict what can be expressed in the language enough that the halting problem becomes decidable.)

A crucial aspect of Turing machines is that you can build a universal Turing machine. Another way to think of that is that Turing machines are expressive enough that you can construct a Turing machine that acts as an interpreter for Turing machines: if you provide it a description of a Turing machine (as bits), then it will simulate execution of that Turing machine. Another way to describe this is that Turing machines basically can implement `eval`. Moreover, once you can implement `eval`, then the halting problem becomes undecidable.

However, `eval` is incompatible with some static type systems: it takes as input a bit-string, and outputs a value whose type is not statically known. Many static type systems can't handle that. So, if you introduce a static type system without being sufficiently careful, then you might have (without realizing it) restricted expressivity enough that `eval` can no longer be implemented, an interpreter cannot be implemented, etc.

In that case, the standard proof of the halting theorem might no longer apply to such a restricted model of computation -- and that might be because it is so limited that it can no longer model many of the computations we care about. I couldn't understand all the fine details of your proposed type system, but I suspect that might be happening with your proposal. So, it's no surprise if the standard proof of the halting theorem no longer applies to your model of computation. It's possible that the halting problem for your restricted model of computation might be decidable, but that doesn't say anything about the decidability of the halting problem for Turing machines.

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


# Question
Title: Algorithm notation between two functions
I have two functions, $$ f = n^{1.6} $$ $$ g = n^{1.5} $$

I thought this is $ f=\theta(g) $, since $ f $ is asymptotically tight bound of $ g $, if $ n $ goes to infinity.
However, the answer is $ f = \omega(g) $.
Can anyone explain why it is $ f = \omega(g) $ ?
Thanks in advance!

# Answer
> 1 votes
$\frac{f(n)}{g(n)} = \frac{n^{1.6}}{n^{1.5}} = n^{0.1}$ is unbounded. Hence, for any $c \> 0$ there is $n\_0 \in \mathbb{N}$ such that $n^{0.1} \> c$ for all $n \> n\_0$. As a result, for any $c \> 0$, we have $n^{1.6} = n^{0.1} \cdot n^{1.5} \> c n^{1.5}$ for all $n \> n\_0$.

Notice this does not really make use of $1.5$ and $1.6$ other than $1.6 \> 1.5$. In fact, using the same method and the fact that $n^\varepsilon$ is unbounded for any $\varepsilon \> 0$, you can prove the more general bound $n^a \in \omega(n^b)$ for any $a \> b \ge 0$.

---
Tags: algorithms, asymptotics
---


# Question
Title: Simple algorithm to generate a linear extension from partial order set
I usually do it via topological sort and wonder if there is a simpler way to generate a linear extension from partial orders without consider the graph of the relation.

# Answer
> 2 votes
No, there is no simpler way. Topological sorting *is* exactly the problem of generate a linear extension from a partial order. There are several standard algorithms for topological sorting; they are already pretty simple, and there's no reason to expect anything simpler.

---
Tags: algorithms, graphs, data-structures
---


# Question
Title: What is the intuition behind the way of reading off a dual optimal solution from simplex primal tabular in CLRS?
Section 29.4 "Duality" of CLRS (3rd Edition) describes the way of reading off an optimal dual solution from the last slack form of the primal as follows:

> Suppose that the last slack form of the primal is $$ \begin{align} z &= v' + \sum\_{j \in N} c'\_j x\_j \\ x\_i &= b'\_i - \sum\_{j \in N} a'\_{ij} x\_j, \\; i \in B. \end{align} $$ Then, to produce an optimal dual solution, we set $$ \overline{y\_i} = \begin{cases} \- c'\_{n+i} & \text{if } (n + i) \in N, \\ 0 & \text{otherwise}. \end{cases} $$

I am able to follow the proof of a later Theorem (Theorem 29.10: LP Duality) to convince myself that this $\overline{y\_i}$ is indeed an optimal dual solution.

However, what is the intuition behind the way the optimal dual solution is constructed? I notice that each non-zero $\overline{y\_i}$ corresponds to a tight constraint in the optimal primal solution. Is this fact helpful to understand the optimal dual solution?

# Answer
> 2 votes
***Answer My Own Question:***

I found that the interpretation in Section 8.3 of the textbook "Introduction to Linear Algebra; 4th Edition" by Gilbert Strang is quite intuitive and much easier to understand than that in CLRS.

*Note:* The textbook of Gilbert Strang takes the "min" program as the primal and the max program as the dual. I follow this convention. Besides, it adopts the matrix form of linear programs, which, in my opinion, helps a lot in understanding the simplex method and the duality theory.

Quoted from the textbook:

> The $m$ inequalities $Ax \ge b$ were changed to equations by introducing the slack variables $w = Ax - b$: $$\begin{bmatrix} A & -I \end{bmatrix} \begin{bmatrix} x \\ w \end{bmatrix} = b$$ and $$\begin{bmatrix} x \\ w \end{bmatrix} \ge 0.$$ Every simplex step picked $m$ columns of the long matrix $\begin{bmatrix} A & -I \end{bmatrix}$ to be basic, and shifted them (theoretically) to the front. This produce $\begin{bmatrix} B & N \end{bmatrix}$. The same shift reordered the long cost vector $\begin{bmatrix} c & 0 \end{bmatrix}$ into $\begin{bmatrix} c\_{B} & c\_{N} \end{bmatrix}$. The stopping condition, which brought the simplex method to an end, was $r = c\_N - c\_B B^{-1} N \ge 0$. At the stopping moment, the cost was as low as possible: $$cx^{\ast} = \begin{bmatrix} c\_{B} & c\_{N} \end{bmatrix} \begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix} = c\_B B^{-1} b.$$ ***If we can choose $y^{\ast} = c\_B B^{-1}$ in the dual, we certainly have $y^{\ast}b = cx^{\ast}$.*** The minimum and maximum will be equal.

It turns out that $y^{\ast} = c\_B B^{-1}$ is exactly the one read off in the final slack form of the primal program in the way CLRS describes. Its feasibility in the dual is due to the stopping condition $r = c\_N - c\_B B^{-1} N \ge 0$.

---
Tags: algorithms, linear-programming, linear-algebra, duality
---


# Question
Title: How do you prove that $A = \{ x \in \mathbb{N} | W_{x} = [0..x]\}$ is a productive set through functional reduction?
As the title states, how do you prove that $A$ is productive? With $W\_{x}$ I mean the set of points in which the turing machine with index $x$ halts.

The standard approach that I follow is functional reduction: first I construct a partial recursive function $\psi(x,y)$. Then through the s-m-n theorem I build a partial recursive function $\varphi\_{g(x)}(y) = \psi(x,y)$ with $g$ total recursive. Then I proceed to show that $\overline{K}$ reduces to the set I'm studying through $g$. The problem is that in this set the condition includes the index of the partial function ($x$) so I don't know how to construct a suitable $\psi$ function. As you can see from the appendix, I can't reach $g$ in $\psi$, so I can't build $g$ to behave like a member of the $A$ set.

How can I overcome this problem?

**APPENDIX: example of proof with functional reduction**

Let's show that $B = \\{ x\in \mathbb{N} | W\_x = \emptyset \\}$ is productive.

We do this by proving that $\overline{K}$ reduces to $B$, so equivalently we can show that $K$ reduces to $\overline{B} = \\{x\in \mathbb{N} | W\_x \neq \emptyset \\}$. Consider the function: $$ \psi(x,y) = \left\\{\begin{array}{lr} 1, & \text{for } x \in K\\ \uparrow, & \text{otherwise} \\ \end{array}\right\\} $$

(Notice that $\psi$ is computable since $K \in RE$). We can now build $\varphi\_{g(x)}(y) = \psi(x,y)$ with $g$ total recursive (s-m-n theorem). At this point:

$x \in K \implies \forall y\in \mathbb{N}. \varphi\_{g(x)}(y) \downarrow \implies W\_{g(x)} = \mathbb{N} \implies W\_{g(x)} \neq \emptyset\implies g(x) \in \overline{B}$.

$x \notin K \implies \forall y\in \mathbb{N}. \varphi\_{g(x)}(y) \uparrow \implies W\_{g(x)} = \emptyset\implies g(x) \notin \overline{B}$.

So $K$ reduces to $\overline{B}$ thorugh $g$: $B$ is productive. $\square$

# Answer
> 1 votes
You likely need to exploit the second recursion theorem, which states that for any total recursive function $f$ there is some $n$ such that $\varphi\_n = \varphi\_{f(n)}$.

Given any $k$, using s-m-n you can first construct $f\_k$ as follows, where $\\#(\ldots)$ stands for "some index of". $$ f\_k(x) = \\#\left(y \mapsto \begin{cases} 0 & \mbox{if } y \leq x \\ \varphi\_k(k) & \mbox{otherwise} \end{cases} \right) $$

This is recursive total, since it always returns an index (the fact that the index is for a partial function is irrelevant). So, by the second recursion theorem, there must exist $n\_k$ for which $\varphi\_{n\_k} = \varphi\_{f(n\_k)}$.

By examining the proof of the second recursion theorem, we can also note that $n\_k$ is effectively computable from $k$, that is there is a total recursive function $g$ such that $\varphi\_{g(k)} = \varphi\_{f(g(k))}$.

Let's verify that $g$ m-reduces $\bar K$ to your set $A$.

Assume $k \in \bar K$, and let's prove $g(k) \in A$. The latter means $W\_{g(k)} = \[0..g(k)\]$, which is true because $$ \varphi\_{g(k)}(y) = \varphi\_{f(g(k))}(y) = \begin{cases} 0 & \mbox{if } y \leq g(k) \\ \varphi\_k(k) & \mbox{otherwise} \end{cases} = \begin{cases} 0 & \mbox{if } y \leq g(k) \\ \uparrow & \mbox{otherwise} \end{cases} $$

Now, assume $k \notin \bar K$, and let's prove $g(k) \notin A$. The latter means $W\_{g(k)} \neq \[0..g(k)\]$, which is true because

$$ \varphi\_{g(k)}(y) = \varphi\_{f(g(k))}(y) = \begin{cases} 0 & \mbox{if } y \leq g(k) \\ \varphi\_k(k) & \mbox{otherwise} \end{cases} $$ Since $\varphi\_k(k)\downarrow$, we have that $W\_{g(k)} = \mathbb N \neq \[0..g(k)\]$

---

As a thumb rule, when you are defining a recursive function $f=\varphi\_i$ and you need to use its own index $i$ in the definition of the function itself, you need the second recursion theorem.

From a more practical point of view, the second recursion theorem allows one to program in a programming language featuring a function `getMyOwnCode() : String` which returns the whole source code (the index) of the program calling the function.

---
Tags: computability
---


# Question
Title: Merging of two increasing binary trees why do we exchange left and right subtree
We say that a binary tree : $B(l, x, r)$ is increasing if $x$ is smaller than all the nodes of the binary tree and if $l$ and $r$ are also increasing trees.

One way to merge these kind of trees is as follow (we denote by $E$ the empty binary tree) :

> * merge ($E$, $B(l, x, r)$) = $B(l,x,r)$
> * merge ($B(l, x, r)$, $E$) = $B(l,x,r)$
> * merge ($B(l\_1,x\_1, r\_1), B(l\_2,x\_2,r\_2)$) = $B($merge($r\_1, B(l\_2,x\_2,r\_2)$), $x\_1, l\_1$) when $x\_1 \leq x\_2$
> * merge ($B(l\_1,x\_1, r\_1), B(l\_2,x\_2,r\_2)$) = $B($merge($r\_2, B(l\_1,x\_1,r\_1)$), $x\_2, l\_2$) when $x\_1 \> x\_2$

Thus when merging two binary trees we are exchanging the left and right subtrees. I am wondering why it's important to do so ?

I guess this is because we don't want our final binary tree to be pathological like for example a tree with only nodes on it's right (which will cause a big height). If this is the reason why we exchange the left and right subtrees when merging I am wondering what make us believe that with this merging function we will not encounter pathological trees ? I mean how can we be sure that this new merging function will not produce pathlogical binary trees ?

Also it's the first time I see a merging function that exchange the left and right subtree. So is this a common thing to do for some categories of binary trees like increasing trees ?

Thank you !

Some references : Skew heap and min-heap

# Answer
Both leftist heaps and the skew heaps you consider here join two trees by "zipping" the trees along the rightmost path. Then left and right children are swapped to keep the left leaning property. In leftist heaps this in done where necessary, where in skew heaps left and right are *always* swapped. Hence the code.

You ask whether the skew heaps will never deteriorate into trees that have linear behaviour, instead of logarithmic. Well, this can happen.

> One may ask whether amortization is really necessary in the analysis of skew heaps, or whether skew heaps are efficient in a worst-case sense. Indeed they are not: we can construct sequences of operations in which some operations take O(n) time. For example, suppose we insert $n, n + 1, n - 1, n + 2, n - 2, n + 3, \dots , 1, 2n$ into an initially empty heap and then perform delete min. The tree resulting from the insertions has a right path of $n$ nodes, and the delete min takes $\Omega ( n)$ time. (See Fig. 3.)

Quoted from the original reference "self-adjusting heaps" by Sleator and Tarjan, SIAM Journal on Computing, which is linked on the wiki-page for skew heaps.
> 2 votes

---
Tags: algorithms, algorithm-analysis, binary-trees
---


# Question
Title: Having a better complexity / adversary argument for finding if a finite automata accepts a palindrome
> Let $A$ be a DFA over a finite alphabet $ \Sigma$. Find an algorithm that indicates if $A$ accepts a palindrome and give the complexity of this algorithm.

Here is my solution:

If we denote $^t A$ the transpose of the finite automaton then in order to see if $A$ accepts a palindrome we need to look at the product automaton of $A$ and $^t A$ and find if this product automaton accepts a word. If yes then this is word is a palindrome.

Finding the transpose of a finite automaton takes $O(|V|)$ where $V$ is the number of transition of our finite automaton. Take the product of $A$ and its transpose takes $O(|V|^2)$. And looking if an automaton accept a word takes $O(|V|^{|S|})$, where $|S|$ is the number of states of our finite automaton. So the final complexity I get for the algorithm I described above is: $$O(|V|^{3 + 2|S|})$$

Now my question is:

Is it possible to improve the complexity? And is it possible to give a proof (using I guess adversary argument) to prove that there isn't a better algorithm (in the sense of complexity) to find if a finite automaton accepts a palindrome?

# Answer
> 2 votes
You can solve this in $O(n^2)$, where $n$ is the number of states in the original DFA (or NFA), using your idea. Compute the product automaton of the original automaton and its reverse. The new automaton contains $O(n^2)$ states. As to the number of edges, in the original DFA, each state has $|\Sigma|$ outgoing edges, and in its reverse, there are $|\Sigma|n$ transitions overall. Let us denote by $a(q)$ the number of outgoing transitions from $q$ in the original DFA, and by $b(q)$ the number in the reverse DFA. Using $Q$ for the set of states, the total number of transitions in the product automaton is $$ \sum\_{q\_1,q\_2 \in Q} a(q\_1) b(q\_2) = \sum\_{q\_1,q\_2 \in Q} |\Sigma| b(q\_2) = |\Sigma| n \sum\_{q\_2 \in Q} b(q\_2) = |\Sigma|^2 n^2. $$ Assuming $|\Sigma|$ is constant, this is $O(n^2)$. Now check whether some final state is reachable from some initial state, using BFS/DFS, in time $O(n^2)$.

We can prove an essentially matching lower bound given SETH. Recall that SETH states that for every $\epsilon \> 0$ there is $k$ such that $k$-SAT cannot be solved in time $O(2^{(1-\epsilon) n})$, where $n$ is the number of variables. We will show how to reduce $k$-SAT to your problem.

Given a $k$-SAT formula $\phi$ with $n$ variables and $m = O(n^k)$ clauses, consider the following language $L$ of all words of the form $\alpha x \beta \gamma y \delta$, where:

1. $|\alpha| = |\beta| = |\gamma| = |\delta| = n/2$, $|x| = |y| = m$.
2. We think of $\alpha$ as an assignment for the first $n/2$ variables. If $x\_i = 0$ then $\alpha$ must satisfy the $i$th clause.
3. We think of $\beta$ as an assignment for the last $n/2$ variables. If $y^R\_i = y\_{m+1-i} = 1$ then $\beta$ must satisfy the $i$th clause.

Any word in $L \cap L^R$ must be of the form $\alpha x \beta \beta^R x^R \alpha^R$, and so by construction $\alpha\beta$ satisfies $\phi$. Conversely, if $\alpha\beta$ satisfies $\phi$, then we can choose $x$ so that the corresponding word is in $L \cap L^R$, Hence $\phi$ is satisfiable iff $L \cap L^R$ is non-empty.

How many states do we need to accept $L$? We can read and store $\alpha$ using $O(2^{n/2})$ many states. Therefore using $O(2^{n/2} m)$ states, we can verify the second condition (on $\alpha x$). Similarly, we can verify the third condition (on $\beta y$) using $O(2^{n/2} m)$ more states. Verifying the first condition takes $O(n+m)$ more states, for a grand total of $O(2^{n/2} m) = O(2^{n/2 + o(1)})$ states.

If your problem could be solve in time $O(N^{2-\delta})$ (where $N$ is the number of states in the input automaton), then we would get an algorithm for $k$-SAT running in time $O(2^{(1-\delta/2)n + o(1)})$, and so obtain a contradiction if $\delta/2 \geq \epsilon$. This shows that assuming SETH, your problem cannot be solved in $O(N^{2-\delta)}$ for any $\delta \> 0$.

# Answer
> 1 votes
You can solve this problem in polynomial time. For simplicity let's assume the DFA has a single accepting state. If it has multiple you can just run this algorithm for each accepting state until you return $\text{YES}$ or every accepting state has been unsuccessfully tried and we return $\text{NO}$. Let $\text{goto}(x, s) = y$ indicate that there is a transition from state $x$ to state $y$ on symbol $s$.

We use a meet in the middle strategy. We have a tuple $(b, e)$ where $b$ is the state reached from the beginning, and $e$ is the state reached from the end.

We build a list of these tuples. Initially we have only one such tuple $(b, e) = (\text{init}, \text{accept})$. Then as long as our list has a tuple that hasn't been expanded before, we expand tuple $(b, e)$ by adding all $(b', e')$ to the list for each possible symbol $s$ where $\text{goto}(b, s) = b'$ and $\text{goto}(e', s) = e$.

We return $\text{YES}$ if we have added $(x, x)$ to the list, or $(x, y)$ where some $s$ exists such that $\text{goto}(x, s) = y$. The former case indicates an even length palindrome, the latter an odd length palindrome.

Why is this polynomial time? Hint: there are only $|S|^2$ possible tuples $(b, e)$ we ever need to expand.

---
Tags: algorithms, complexity-theory, finite-automata, adversary
---


# Question
Title: Given a total recursive function, can you always compute its fixed-point?
We know from Kleene's recursion theorem that if $f$ is total recursive, there must be an integer $n$ for which $\varphi\_n=\varphi\_{f(n)}$. My question is: for every $f$ total recursive, is there a computable (total) procedure that computes such a point?

ie: $\exists g.\forall f.\varphi\_{g(n)}=\varphi\_{f(g(n))}$.

# Answer
> 6 votes
The proof of the recursion theorem is *constructive*: it gives you an algorithm to compute $n$ from $f$. See for example these notes of Rebecca Weber.

---
Tags: computability
---


# Question
Title: How to understand the notion of boolean query via Immerman's definition
> A *query* is any mapping $I:STRUC\[\sigma\] \to STRUC\[\tau\]$ that is polynomially bounded. A *boolean* query is a map $I\_b: STRUC\[\sigma\] \to \\{0,1\\}$. A boolean query can also be thought as the susbset: $$ \\{ A \in STRUC\[\sigma\] \ \mid \ I\_b(A) = 1 \\} $$

From this definition of query, used by Immerman in his book "Descriptive Complexity", how are boolean queries and general queries related? It seems from the definition that they are two different things entirely. Is there an intuitive way to link the two concepts? Thank you!

# Answer
Boolean queries are a special case of general queries. You can take $\tau$ to be some convenient vocabulary and choose a pair of $\tau$-structures to represent "true" and "false".

FOr a concrete example, take $\tau$ to be the vocabulary with a single nullary relation symbol $T$. Now, associate "true" with the $\tau$-structure $\mathfrak{T}$ that has $|\mathfrak{T}|=\emptyset$ and $T^\mathfrak{T}=\\{\langle\\,\rangle\\}$ (i.e., the nullary relation that contains the empty tuple) and "false" with the structure $\mathfrak{F}$ that has $|\mathfrak{F}|=\emptyset$ and $T^\mathfrak{F}=\emptyset$ (the nullary relation that doesn't contain the empty tuple).

Empty universes are a bit awkward, since they mean that $(\forall x\\,\varphi) \rightarrow \exists x\\,\varphi$ isn't a tautology. If you don't like that and/or you don't like nullary relations, make the relation $T$ unary and use a one-element universe.
> 1 votes

---
Tags: complexity-theory, logic, descriptive-complexity, finite-model-theory
---


# Question
Title: What is space complexity of shrinking one array to increase another?
Say I have an array and I want to add those values to something else. What is the space complexity if I incrementally take one of those values off the first list and add it to the second? For example, I'm trying to convert a list to a string. I know that if I do the following, the space complexity will be O(N):

```
a = [1,2,3,4]
b = set(a)

```

But if instead I incrementally shrunk a, what would the space complexity be?

```
a = [1,2,3,4]
b = set()
for _ in range(len(a)):
    b.add(a.pop())

```

Now `b` has what I want and `a` is empty. Does that make it O(1) in space complexity?

If the language matters, I'm most interested in Python, but I would like to know the most general answer as well.

# Answer
> 1 votes
Space complexity is all very well on something like a Turing machine: you just define the space complexity to be the number of different tape cells that the tape head visits. For real computers, things get much more complicated and very implementation-dependent.

It is possible that the algorithm you describe runs in constant space. If the array `a` is stored earlier in memory than the string `b`, the system could, in principle, delete the last character of `a`, shuffle everything after it back one memory cell, then add a character onto the end of `b`, so no extra memory is used.

In reality, though, it's much more likely that the system doesn't keep moving things around and just allocates new memory each time a character is added to `b`, which is probably linear space. Except it could be worse. Maybe, every time you try to make `b` bigger, the system actually allocates completely new storage for the extended string, which could give quadratic space usage. Or maybe it's not that dumb and, each time you extend the string beyond its current memory allocation, it allocates a new chunk of memory that's double the size, so it can do lots of appends without reallocating memory every time. That would be linear, again.

And in real reality, what actually happens probably depends very much on what else is running on the machine. If there's lots of free memory, the system might be very happy to allocate fresh memory each time you extend the string, and it might only free the memory used by the old versions right at the end. If there is little free memory, it might free up unused memory much more aggressively.

So your code probably uses at least a linear amount of memory, but it's not really possible to be more precise than that.

---
Tags: space-complexity
---


# Question
Title: Can the pumping lemma for context free languages be extended to any subword?
It is known that in the case of a Regular Language $L$ , the pumping lemma can be extended to apply to any sufficiently long subword of the language, ie, if $uwv \in L$ and $|w| \ge p$ then we can perform the usual breakup of $w$ as $w=xyz$ such that $uxy^izv \in L$.

Can we similarly extend the pumping lemma for context-free languages such that it is applicable to any sufficiently long subword? Intuitively I think it should generalize, since the pumping lemma is basically stems from the existence of a repeating non-terminal on some path given a sufficiently deep parse tree, and that should not change if we consider a subword instead of the entire word. But I'm having trouble with formalizing an argument.

If anyone could provide an idea for a formal argument or proof, it would be really appreciated.

# Answer
> 4 votes
The extended form of pumping lemma for regular languages you mentioned is called "the general version of pumping lemma for regular languages".

It is indeed natural to suspect that a similar general version of the usual pumping lemma for context-free languages as said in the title should hold. Unfortunately, it does not. For example, take context-free language $L=\\{a^nb^n\\}$. The initial subword $a^n$ of $a^nb^n$ can be arbitrarily long. However, no part of that subword can be pumped.

There are, however, a few valid generalizations of the usual pumping lemma for context-free languages. You may want to take a close look at them.

# Answer
> 2 votes
As already remarked, it is not possible to directly generalize the pumping lemma based directly on the *length* of the strings in the partition $z = uvwxy$.

Ogden's lemma answers your question. Here it is:

* for every CF language $L$
* there exists a constant $n \ge 1$ such that
* for every $z \in L$ with $\\|z\\| \ge n$
* there exists a decomposition $z = uvwxy$ with $\\|vwx\\| \le n$, $\\|vx\\| \ge 1$ such that
* for all $i \ge 0$, $uv^iwx^iy \in L$.

If one reads $\\|\cdot\\|$ as the length of a string, we have classical pumping. The new Lemma uses "distinguished" or "marked" positions, like we colour some of the letters in the string red. Now $\\|\cdot\\|$ means the number of marked positions (red symbols) in the string. Thus, we can pump a substring that has at most $n$ marked positions, similar to what you suggest. However, there is no way to avoid some unmarked positions.

The result by Ogden was further extended by Bader and Moura to additionally include a relatively tiny number of "forbidden" positions that could not occur in $vx$, thus are not pumped.

Both results follow the reasoning of the original pumping lemma by Bar-Hillel etal (long paths in the derivation tree must have repeated nonterminals) but the combinatorics is more complicated.

---
Tags: context-free, finite-automata, pumping-lemma
---


# Question
Title: Solving the recurrence $T(n) = n^{3/4}(^{1/4})+ n $
I need to solve the following recurrence relation: $T(n) = n^{3/4}(^{1/4})+ n $. Obviously, the master theorem doesn't apply here so I was using the substitution method. I used $x=\log n$ and $F(x)=T(e^x)$. I was able to get to $F(x)= e^{3x/4} \cdot F(x/4)+ e^x$. However, the master theorem still doesn't apply at this stage. How can I proceed?

# Answer
You can just expand it: $$ \begin{align\*} T(n) &= n + n^{3/4} T(n^{1/4}) \\ &= n + n^{3/4}\cdot \[n^{1/4}+ n^{3/16}\cdot T(n^{1/16})\] \\ &= n + n + n^{3/4} \cdot n^{3/16} T(n^{1/16}) \\ &= n + n + n + n^{3/4} \cdot n^{3/16} \cdot n^{3/64} T(n^{1/64}) \\ &= \cdots \end{align\*} $$ We see that $T(n) = C(n) n$, where $C(n)$ is the number of times we need to apply $n \mapsto n^{1/4}$ until the answer drops below some constant.

I'll let you figure out $C(n)$, and so complete this exercise.
> 0 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Generate a random combination in O(k) time and space?
How to generate a random combination of $k$ numbers from $n$ choices in $O(k)$ time and space, if we can generate a random number between 1 and $O(n)$ in $O(1)$ time?

I know only 3 algorithms: with $O(n)$ time and space, $O(k\log k)$ time and $O(k)$ space, $O(k)$ average time and $O(n)$ space. Is it even possible to solve this task on $O(k)$ both?

# Answer
> 2 votes
Suppose that $k \leq n/2$ (the constant $1/2$ is arbitrary) – otherwise you can just use the $O(k)$ time, $O(n)$ space algorithm, which is the second algorithm that you mention.

One way of solving your problem is as follows:

* Start with the empty list.
* Repeat $k$ times:
    1. Generate a random number from $1$ to $n$.
    2. Check if it is already in the list.
    3. If so, go back to step 1.
    4. Otherwise, add it to the list.

The expected number of steps in this algorithm is $$ \frac{1}{1-0/n} + \frac{1}{1-1/n} + \cdots + \frac{1}{1-k/n} = n \left(\frac{1}{n} + \cdots + \frac{1}{n-k}\right) \leq \frac{k}{2}, $$ since $k \leq n/2$.

Using a hash table, use should be able to implement step 2 in $O(1)$ expected time and $O(k)$ space.

---
Tags: algorithms, combinatorics
---


# Question
Title: Computing Nash equilibria in discrete auctions
I am trying to compute the (pure strategy) Nash equilibria of some discrete auctions.

More precisely, let us define the strategy of each player as a function mapping from every valuation that they might have to their bid (i.e. the 'bidding function'). Let us suppose that each player's valuation is drawn from some finite set and that their bid must belong to this same (finite) set. I am interested in finding the set of bidding functions, one for each player, such that each player's bidding function is optimal given the bidding functions of all the other players.

If it makes things easier, we can assume that valuations are symmetric (i.e. each player's valuation is generated by the same probability distribution) and that there are only two bidders. Ideally, however, we would proceed without these simplifications. I am interested in computing the equilibrium for the first price sealed bid and all pay auctions (in the latter, you pay your bid even if you lose; in the former, you don't.)

I have considered writing down the discrete auction game in normal form and finding the equilibria using software like Gambit. However, this would seem tricky since the strategy space is so large. For example, if a player chooses bids from $ \\{1,...,10\\} $ and draws values from $ \\{1,...,10\\} $, then already they have $10^{10}$ pure strategies.

Does anyone have any ideas about how to proceed here?

# Answer
> 1 votes
If there are only two players, you could use integer linear programming.

I'll introduce some zero-or-one integer variables to encode the (unknown) bidding functions (via a one-hot encoding). Let $x\_{v,b}=1$ if player $0$'s bid is $b$ when their valuation is $v$, and $0$ otherwise; and $y\_{w,c}=1$ if player $1$'s bid is $c$ when their valuation is $w$, and $0$ otherwise. In this way, if there are $n$ possible valuations, we obtain $2n^2$ zero-or-one integer variables. We will write down linear inequalities on these variables that characterize the optimality condition, then use an integer programming solver to find a solution that satisfies all of these inequalities.

Note that if player $0$'s valuation is $v$ and player $1$'s valuation is $w$, then player $0$'s payoff (in a first-price auction) is

$$\sum\_{b\>c} x\_{v,b} y\_{w,c} (v-b).$$

Therefore, if player $0$'s valuation is $v$, player $0$'s expected payoff is

$$\sum\_w p\_1(w) \sum\_{b\>c} x\_{v,b} y\_{w,c} (v-b),$$

where $p\_1(w)$ represents the probability that player $1$ gets valuation $w$. Now, we need this to be at least what it would be if player $0$ used any other bid for valuation $v$, i.e., any other choice of $x\_{v,\cdot}$'s. If there are $n$ possible valuations, there are only $n$ possible bids, so we obtain $n$ inequalities

$$\sum\_w p\_1(w) \sum\_{b\>c} x\_{v,b} y\_{w,c} (v-b) \ge \sum\_w p\_1(w) \sum\_{b'\>c} y\_{w,c} (v-b'),$$

where we obtain one such inequality for each possible value of $b'$. (The sum on the left-hand-side is over $w,b,c$ that satisfy the condition $b\>c$; the sum on the right-hand-side is over $w,c$ that satisfy the condition $c\<b'$.)

This is a quadratic inequality. We'll turn it into a linear inequality using the techniques of Express boolean logic operations in zero-one integer linear programming (ILP). In particular, introduce new zero-or-one variables $t\_{v,w,b,c}$, with the intention that $t\_{v,w,b,c}=x\_{v,b} y\_{w,c}$. This can be enforced using the linear inequalities $t\_{v,w,b,c} \ge x\_{v,b} + y\_{w,c} - 1$, $t\_{v,w,b,c} \le x\_{v,b}$, $t\_{v,w,b,c} \le y\_{w,c}$, $0 \le t\_{v,w,b,c} \le 1$. Now the optimality condition becomes

$$\sum\_w p\_1(w) \sum\_{b\>c} t\_{v,w,b,c} (v-b) \ge \sum\_w p\_1(w) \sum{b'\>c} y\_{w,c} (v-b'),$$

for each $v,b'$. We obtain one such inequality for each $v$ and each $b'$. These $n^2$ inequalities ensure that player $0$'s strategy will be optimal (given player $1$'s strategy).

Then, add similar inequalities to require player $1$'s strategy to be optimal (given player $0$'s strategy).

Also add the $n^2+n$ constraints that $0 \le x\_{v,b} \le 1$ and $\sum\_b x\_{v,b}=1$ to require the $x$'s to correspond to a bidding function, and similarly for the $y$'s.

Finally, take all of these inequalities and feed them to an off-the-shelf integer linear programming solver. If it finds a solution, then you have found a Nash equilibrium for your game. ILP is NP-hard, so there is no guarantee that it will terminate in a reasonable amount of time, but in my experience often the solvers can handle surprisingly large systems of inequalities.

The same approach can handle all-pay auctions as well as first-price auctions.

In practice, you might be able to speed up the solver by adding some extra constraints to help it identify a solution faster. In particular, I have a hunch that without loss of generality the optimal bidding function can be assumed to be monotonic: if we increase my valuation, my bid should never decrease. We can add extra inequalities to the system to characterize this additional assumption, and this might narrow the search space and thus help the ILP solver find a solution more rapidly.

One big limitation is that this seems limited to two players (or a very small number of players). If there are multiple players, the number of variables and inequalities will explode, and this might not be an effective approach.

---
Tags: game-theory
---


# Question
Title: Showing that $\lg(n!)$ is or is not $o(\lg(n^n))$ and $\omega(\lg(n^n))$
My instructor assigned a problem that asks us to determine which asymptotic bounds apply to a certain $f(n)$ for a certain $g(n)$, in my case $f(n) = \lg(n!)$ and $g(n) = \lg(n^n)$. For clarity, the convention we use in our class is that $\lg = \log\_2$, the "binary logarithm".

I know that by Stirling's approximation, $\lg(n!)$ grows in $O(n\lg(n))$, and evaluating the limit $\lim\_{n \to \infty} \frac{n\lg(n)}{n\lg(n)} = C$, some constant \> 0, and so $\lg(n!)$ is in $\theta(\lg n^n)$.

$\theta$ also means that my $f(n)$ is is in $O(g(n))$ and $\Omega(g(n))$, but this does not mean that my $f(n)$ is in $o(g(n))$ or $\omega(g(n))$.

For that, I believe I would need to evaluate $\lim\_{n \to \infty} \frac{\lg(n!)}{\lg(n^n)}$, but I am not certain.

What strategy would I use to show that $f(n)$ is in $o(g(n))$ or $\omega(g(n))$? Would I evaluate $\lim\_{n \to \infty} \frac{\lg(n!)}{\lg(n^n)}$?

# Answer
> 2 votes
You seem tot be trying to prove something that is false. If $f=O(g)$ then $\lim\_{n\to\infty}g/f \> 0$ so $f\neq \omega(g)$. Similarly, if $f=\Omega(g)$ then $f\neq o(g)$.

Since you already have that $\lg n! = \Theta(\ln n^n)$, that gives you big-$O$ and big-$\Omega$, which preclude little-$\omega$ and little-$o$, respectively.

# Answer
> 0 votes
You can use Stirling’s formula.

Or you observe that $n!$ Is the product of $n$ numbers, and of these $n/2$ are at least $\sqrt{n}$, so $\log n! \geq (n/2) \log(n) / 2 = (n \log n) / 4$, which shows it is not $o(n \log n)$.

---
Tags: asymptotics
---


# Question
Title: Blind sorting an array with a singular sort function?
I am doing some interview prep, and I came across a question that really stumped me, and it didn't provide an answer.

The premise of the question was as follows:

You are given some unsorted array A of size n. You are not allowed to access the array, read values, or compare the values.

The only manner in which you may interact with said array is with a BlockSort() functions, such that calling BlockSort(index) will automatically sort the elements within the inclusive bounds of \[i,i+u\] for some arbitrary but fixed u, such that u≥1.

Sort A with O((n/u)^2) calls to BlockSort.

My initial approach to this question was to mimic Bubble Sort, except stagger the calls to BlockSort, such that each successive call overlaps with one element of the previous call, (i.e. BlockSort(0,u), BlockSort(u,2u)...etc.) and then after iterating like that through the array once, you are left with the global maximum at the end of the array, and an unsorted array of size n-1, and then you can recursively solve the problem.

This has a time complexity of O((n^2)/u) though.

I have thrown an hour or 2 at the problem, and I can't quite see how they achieved O((n/u)^2).

Is there anything I could think about to get to the answer?

# Answer
> 1 votes
Your approach by mimicking Bubble Sort is pretty good.

Here is a hint. Since we can sort a block, we can raise half a block of the largest elements so far like a bubble each time. For example, when $u=5$, if we have done BlockSort on \[0,5\], \[3,8\] and \[6,11\] successively, we will have placed the largest 6/2=3 elements among the first 12 elements at index 9,10 and 11, the end of subarray so far.

---
Tags: algorithms
---


# Question
Title: What time complexity (big o) is this specific web crawler implementation?
> Note: this question was marked as a duplicate in favor of this question/answer which attempts to provide a generic formula for translating code to mathematics.
>
> Unfortunately I didn't find that response useful as I don't have a good understanding of maths and so all I see is complex symbols that don't mean anything to me. I require a more lay person explanation of how to break down an algorithm into time complexity.

I've built a simple 'web crawler' and was interested to know what the time complexity of the core 'processing' logic was.

Here is a diagram of the architecture:

https://github.com/integralist/go-web-crawler

Specifically the algorithm portion I'm interested in is the `Crawler` which:

1. defines a worker pool size
2. pushes tasks into a channel
3. processes tasks concurrently within the boundary of the pool

In the crawler code we:

* accept a list of n items
* each item in the list has a nested list of x items
* we look at each item and decide whether to process the item or not

> Note the `Parser` and `Mapper` portions of the code are all the same underlying design, but *how* the 'task' is processed is slightly different and so although I could imagine the time complexity for those possibly being different depending on what those processing steps are, the principle is still the same: we're still looping over all items and deciding on something to do.

What is this BigO time complexity?

Initially it might seem that this is just `O(n)` as we're visiting each item in the list as well as each item in the nested list.

Is that it? or am I missing something else entirely obvious.

I don't think it's `O(n Log n)` as it's not reducing the number of looping operations in the nested lists. Similarly for `O(n*n)` as the nested loop isn't necessarily the same length as the parent list. I also don't think it's `O(2^n)` as the nested lists aren't growing exponentially (they're just an unknown number of items).

---

## Update

I was asked to provide a precise definition of the algorithm, and so I'll attempt to do that below by way of a bullet list along with some pseudo code...

* loop over collection (collection: array of structs)
    + pass each struct within the collection to `crawl` function

breakdown of `crawl` function...

* get length of collectionItem Urls (collectionItem: struct with field containing urls)
* create worker pool of set size, or size of collectionItem.Urls (if smaller)
* each worker stays open (blocked) waiting for a task to process
* when a task is received:
    + make a http network request (task is a url)
    + track the task (a url) in a hash table
    + append network response in an array
* loop over collectionItem.Urls
    + if url already tracked in hash table:
        - do nothing
    + else:
        - push url into task queue

```
for item in collection {
    crawl(item)
}

func crawl(collectionItem) {
    collectionLength = length(collectionItem.Urls)

    if (collectionLength < 1) {
        return
    }

    poolSize = 20

    if (collectionLength < poolSize) {
        poolSize = collectionLength
    }

    for i=0; i<poolSize; i++ {
        // we spin up multiple threads...
        waitForATask(
            // this function is executed concurrently on individual thread/process
            // it contains the following logic...

            for t in tasks {
                // tasks is a blocking channel
                // so as tasks are pushed in the channel
                // it means the tasks are distributed across the pool

                page = netRequestFor(t)
                trackInHashTable(t)
                appendToArray(page) // this is ultimately what process returns
            }
        )
    }

    for url in collectionItem.Urls {
        if not trackedAlready(url) {
            pushTaskIntoQueue(url) // queue is the 'tasks' variable we loop over within our threads
        }
    }
}

```

*Additionally!* the steps described above (i.e. looping a collection, and then passing each item to a `crawl` function) is something that will be recursively executed. The actual implementation is...

```
func process(mappedPages []mapper.Page) {
    for _, page := range mappedPages {
        crawledPages := crawler.Crawl(page) // this is what I described above
        tokenizedNestedPages := parser.ParseCollection(crawledPages)
        mappedNestedPages := mapper.MapCollection(tokenizedNestedPages)

        for _, mnp := range mappedNestedPages {
            results = append(results, mnp)
        }

        process(mappedNestedPages)
    }
}

```

...The idea being that the top level loop will not only pass each item to the `crawl` function, but that the results (a list of requested pages) will itself then be passed to a `parser` function (tokenizing the page, and which is designed with an algorithm exactly the same as the `crawl` function), then that tokenization result is passed to a `mapper` (again, the mapper is designed the same as the `crawl`).

So I guess when considering the time complexity, we would need to take into account the *whole* algorithm (not just the `crawl` function segment).

# Answer
I didn't read your code, but based on the overview, the running time to handle a list of size $n$ containing nested sublists of size $x$ appears to be $O(nx)$. Here's my reasoning:

* You iterate over each list (there are $n$ of them), and each contains $x$ items, so you iterate over $nx$ items in all.
* The amount of work per item appears to be constant, i.e., $O(1)$ (it doesn't appear to depend on $n$ or $x$; here I'm using that the running time for insert or lookup operations in a hashtable are $O(1)$, in practice).
* Multiplying those together, we see that the total time to handle that list is $O(nx)$.

That said, beware that big-O analysis is of dubious utility for systems code like yours. I'm pretty skeptical whether this is useful at all. Big-O analysis ignores the constant factors, but for systems code, we often care about the constant factors a lot.

And these constant factors can be enormous. Big-O analysis treats executing a single ADD instruction the same as fetching a web page at some URL; they both take $O(1)$ time. However, in practice, the latter takes are longer: a single instruction might take 1ns, and fetching a URL might take 100ms. That's a difference of $100,000,000\times$, i.e., 8 orders of magnitude. Counting both operations equally, as big-O analysis does, is simply not helpful for understanding the performance of the system in practice.

So, I would exercise caution in your use of big-O analysis (i.e., asymptotic running time) in systems like these.
> 1 votes

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