title: Why is left recursion bad?

text:
# Question
Title: Why is left recursion bad?
In compiler design, why should left recursion be eliminated in grammars? I am reading that it is because it can cause an infinite recursion, but is it not true for a right recursive grammar as well?

# Answer
> 15 votes
Left recursive grammars are not necessarily a bad thing. These grammars are easily parsed using a stack to keep track of the already parsed phrases, as it is the case in LR parser.

Recall that a left recursive rule of a CF grammar $G = (V,\Sigma,R,S)$ is of the form:

$\alpha \rightarrow \alpha \beta$

with $\alpha$ an element of $V$ and $\beta$ an element of $V \cup \Sigma$. (See the complete formal definition for the tuple $(V,\Sigma,R,S)$ there).

Usually, $\beta$ is actually a sequence of terminals and non terminals, and there is an other rule for $\alpha$ where $\alpha$ does not appear in the right hand side.

Whenever a new terminal is being received by the grammar parser (from the lexer), this terminal is pushed atop the stack: this operation is called a *shift*.

Each time the right hand side of a rule is matched by a group of consecutive elements at the top of the stack, this group is replaced by a single element representing the phrase newly matched. This replacement is called a *reduction*.

With right recursive grammars, the stack may grow indefinitely until a reduction occurs, thus limiting rather dramatically the parsing possibilities. However, left recursive ones will let the compiler generate reductions earlier (in fact, as soon as possible). See the wikipedia entry for more information.

# Answer
> 14 votes
Consider this rule:

```
example : 'a' | example 'b' ;

```

Now consider a LL parser trying to match a non-matching string like `'b'` to this rule. Since `'a'` doesn't match, it'll try to match `example 'b'`. But in order to do so, it has to match `example`...which is what it was trying to do in the first place. It could get stuck trying forever to see whether it can match, because it's always trying to match the same stream of tokens to the same rule.

In order to prevent that, you'd either have to parse from the right (which is quite uncommon, as far as i've seen, and would make right recursion the problem instead), artificially limit the amount of nesting allowed, or match a token before the recursion starts so there's always a base case (namely, where all the tokens have been consumed and there's still no complete match). Since a right-recursive rule already does the third, it doesn't have the same problem.

# Answer
> 6 votes
(I know this question's pretty old by now, but in case other people have the same question...)

Are you asking in the context of recursive descent parsers? For example, for the grammar `expr:: = expr + term | term`, why something like this (left recursive):

```
// expr:: = expr + term
expr() {
   expr();
   if (token == '+') {
      getNextToken();
   }
   term();
}

```

is problematic, but not this (right recursive)?

```
// expr:: = term + expr
expr() {
   term();
   if (token == '+') {
      getNextToken();
      expr();
   }
}

```

It looks like both versions of `expr()` call themselves. But the important difference is the context -- i.e. the current token when that recursive call is made.

In the left recursive case, `expr()` continually calls itself with the same token and no progress is made. In the right recursive case, it consumes some of the input in the call to `term()` and the PLUS token before reaching the call to `expr()`. So at this point, the recursive call may call term and then terminate before reaching the if test again.

For example, consider parsing 2 + 3 + 4. The left recursive parser calls `expr()` infinitely while stuck on the first token, while the right recursive parser consumes "2 +" before calling `expr()` again. The second call to `expr()` matches "3 +" and calls `expr()` with only the 4 left. The 4 matches to a term and the parsing terminates without any more calls to `expr()`.

# Answer
> 3 votes
From Bison manual:

*"Any kind of sequence can be defined using either left recursion or right recursion, but **you should always use left recursion**, because it can parse a sequence of any number of elements with bounded stack space. Right recursion uses up space on the Bison stack in proportion to the number of elements in the sequence, because all the elements must be shifted onto the stack before the rule can be applied even once. See The Bison Parser Algorithm, for further explanation of this."*

http://www.gnu.org/software/bison/manual/html\_node/Recursion.html

So it depends on the parser's algorithm, but as stated in other answers, some parsers may simply not work with left recursion

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


# Question
Title: Finite languages are Turing decidable - contradiction
Let's say that I define the language $L$ over the alphabet $\\{0, 1\\}$ to be a language containing only one word, $w$, where:

$$ w = \begin{cases} 1 & \text{if the continuum hypothesis is true}\\ 0 & \text{otherwise.} \end{cases} $$

$L$ is finite, therefore there is a Turing Machine which can decide whether or not the word $1$ is in $L$. On contrary, continuum hypothesis is independent of $ZFC$, which means that it cannot be proven nor disproved from the standard Zermelo–Fraenkel set theory. As a consequence, we cannot know if $1$ or $0$ is in $L$. Then, how can we build a Turing Machine which can decide $L$?

# Answer
> 3 votes
This has been asked before in various guises. The answer is very simple.

If the continuum hypothesis holds, then here is pseudocode for a Turing machine accepting $L$:

* Accept if the input equals 1.

If the continuum hypothesis doesn't hold, then here is pseudocode for a Turing machine accepting $L$:

* Accept if the input equals 0.

In both cases, we have shown that there exists a Turing machine that decides $L$.

---

If you're confused, here is a slightly more formal version of your theorem:

> There exists a Turing machine $T$ such that if CH holds, $L(T) = \\{1\\}$, and if CH doesn't hold, $L(T) = \\{0\\}$.

Since CH either holds or doesn't hold, one of the following machines accepts $L$: the machine accepting only $1$, and the machine accepting only $0$. In particular, there exists a Turing machine whose language satisfies the requirements.

---

Perhaps you're confused about the incompleteness result. It states that there is no proof in ZFC of the continuum hypothesis or of its negation. Nevertheless, the continuum hypothesis is either true or false.

More formally, we can think of it in the following way. We live in a "model" of ZFC (*model* is actually a formal term!), in which every statement (more accurately, every first-order statement in the language of ZFC) has a definite truth value. In particular, in our model either the continuum hypothesis is true or it is false, and we know for sure that one of the possibilities holds, even if we cannot prove either possibility (and so we don't know which one holds).

---

If you don't like this sort of reasoning, I suggest looking into constructive mathematics and intuitionism, which is what logicians who didn't like this kind of reasoning came up with.

---
Tags: formal-languages, turing-machines, finite-automata, undecidability, finite-sets
---


title: reduction technique for undecidability

text:
# Question
Title: reduction technique for undecidability
I have been reading about how to test the undecidability of a problem, and some tests talk about the reduction technique. For what I could understand of this technique is that if I want to prove that problem X is undecidable I can take a problem Y which has already been proven to be undecidable. Then by using logic or mathematical manipulation, I try to reduce or get an instance of problem X by modifying problem X, am I right?

So for example, if I want to test the undecidability of problem X, it would be fair if I pick up, for example, the undecidability of the detection of computer viruses, as stated by Cohen, as an undecidable problem by applying reduction to it, would that be fine?

# Answer
To prove that problem X is undecidable you can reduce a problem Y (which has already been proved to be undecidable) to X. In fact if Y\<mX then we know that X is at least as much hard as Y is. So what you have to do is to show a function f that maps instances of problem Y in instances of problem X, so that if y is an instance of Y with answer "yes" than f(y)=x is an instance of problem X with answer "yes", and if y is an instance of Y with answer "no" than f(y)=x is an instance of problem X with answer "no".
> 1 votes

---
Tags: undecidability
---


title: Deterministic SAT solver

text:
# Question
Title: Deterministic SAT solver
I have the following question. Is the SAT solvers are deterministic?

I mean, for example, about miniSAT and DPLL algorithm. Are they completely deterministic?

If these algorithms will return unSAT it means that certainly the solution does not exist?

# Answer
> 14 votes
Core algorithms like DPLL and its refinements like CDCL are completely deterministic.

Note that non-determinism doesn't necessarily mean that an algorithm may lead to a wrong result. For example we can distinguish between

* **Monte Carlo algorithms**, which are randomised algorithms whose output **may be incorrect** with some probability.
* **Las Vegas algorithms**, which are are randomised algorithms whose output is **always correct**, but the algorithms 'gamble' with the resources used in the computation, e.g. running time on identical inputs may vary.

At the other extreme are probabilistic algorithms for solving $k$-SAT such as Schöning's \[ 1 \] which is Monte-Carlo, and remarkably effective in practise given its utter simplicity. Interestingly Schöning's algorithm can be completely derandomised without losing (much of) its effectiveness \[ 2 \].

In practise, industrial SAT-solvers always employ some degree of randomness, so as to 'escape' from the bad (= exponential) worst-case behaviour of DPLL-based algorithms. MiniSat is a highly configurable and evolving piece of software. That said, MiniSat is not completely deterministic: the choice of branching variable is sometimes randomised, depending on command line options. (The default is that 2% of branching variables are chosen randomly IIRC.) Likewise, MiniSAT has the option of initialising the VSIDS scores randomly. (VSIDS is a heuristic for 'measuring' the influence a variable has.)

---

<sup> 1. U. Schöning, A Probabilistic Algorithm for $k$-SAT Based on Limited Local Search and Restart.
2. R. A. Moser, D. Scheder, A Full Derandomization of Schöning's $k$-SAT Algorithm.

</sup>

# Answer
> 6 votes
That's correct. DPLL exhaustively explores the space. If it returns 'unsat' then certainly no satisfying assignment exists.

More recently, researchers have developed certifying SAT solvers that additionally return a (hopefully short) proof of unsatisfiability, when they return 'unsat'. This proof can be checked by anyone else, which provides a way for others to verify that the formula is unsatisfiable without them having to re-run the SAT algorithm again. This can be useful in some contexts.

MiniSAT is an implementation, rather than an algorithm. Its behavior depends on its code. I can't speak to what the code does.

# Answer
> 5 votes
A keyword you might be missing is *completeness*. In general, a search algorithm is said to be complete if it finds a solution given it exists (given enough time). In particular, DPLL is an example of a deterministic, complete search method.

# Answer
> 3 votes
SAT solvers can be deterministic or not depending on how they are implemented. Note that the nondeterminism here can only affect the generated model not the answer (SAT or UNSAT) of the solver! For diversification purposes and others, SAT solver generally introduce randomness at certain point: for example to initialize variable activities or to make random decisions. In minisat for example, random decisions are made by calling a fonction that always return the same random number when using the same random seed. So at this point when you don't change any configuration of the solver, you will always have the same answer and the same model. Changing the random seed for example will not affect the answer (SAT or UNSAT) but can change the model and the execution time.

---
Tags: algorithms, logic, satisfiability, sat-solvers
---


# Question
Title: Finding median of 2 sorted arrays in O(log n)
If there are given two arrays, A and B, each containing n real numbers in sorted order. How to compute the median of all the numbers in A and B, in O(log n) time. I have to make an algorithm that takes at most logarithmic time.

My idea:

```
A = 1, 3, 6, 8, 10, 15, 20

B = 1, 2, 3, 7, 10, 30

C = sort(A, B)

a = len(A) // 7
b = len(B) // 6
M = (a+b)/2 // 6.5
if M is a fraction:
    Median = C[M+0.5]
else:
    Median = (C[M]+C[M+1])/2

```

How to write `sort` function under complexity O(log n)? I don't even have to sort all the elements of A and B, I only need the first M+1 elements of C because of above method.

# Answer
> 4 votes
There are two arrays: $A, B$ with lengths $n, m$. Finding median in the sorted array takes constant time (just access middle element or take a mean of two center elements).

To find the median of all elements in $\mathcal O(min(\log n, \log m))$ perform the following steps:

1. If $(length(A) \le 2$ or $length(B) \le 2)$ or $(A \_{last} \le B\_{first}$ or $B\_{last} \le A\_{first})$ calculate median and return.
2. Set $A\_m = median(A), B\_m = median(B)$ and compare them. If $A\_m = B\_m$ return result. If $A\_m \< B\_m$ then discard first half of $A$ and the same amount of elements from the second half of $B$. else if $A\_m \> B\_m$ then discard second half of $A$ and the same amount of elements from the first half of $B$.
3. Goto 1

This algorithm runs in logarithmic time. Minimum in the complexity reflects the fact that when the smaller array has length $\le 2$ the procedure terminates. At step 2 the both arrays get halved (or procedure is terminated) so it will be performed at most $\log\_2(min(n, m))$ times.

By calculate median there are two cases: at least one arrays length was $\le 2$, so shift the median of the second array accordingly, or arrays do not overlap (or share the boundary element) then the median is the center element of two arrays concatenated in ascending order. In fact only index is calculated, no actual concatenation takes place.

Why the procedure stops when at least one of lengths is $\le 2$? Consider the corner case, e.g. A = \[2, 9\], B = \[3, 11\], the median is 6, but taking them separately yields 5.5 and 7, which in turn yields incorrect result 6.25.

For example:
$A = \[1, 2, 6, 8, 12, 15\], B = \[2, 5, 8, 15\]$ to keep an overview, the whole sorted array $C = \[1, 2, 2, 5, 6, 8, 8, 12, 15, 15\], C\_m = 7$.
$A\_m = 7, B\_m = 6.5$ now $A\_m \> B\_m$ so we drop \[12, 15\] from $A$ and we drop \[2, 5\] from $B$. Why $8$ is not dropped from $A$? Bacause we cannot drop $8$ from $B$, and in order to preserve median we can only drop the same number of elements ftom the both arrays at the opposite sites of the mean.
So $A = \[1, 2, 6, 8\], B = \[8, 15\]$. Now back to step 1, the arrays do overlap by common element at the end so we take $AB$, the lengths are 4, 2, so it is a mean of 3rd and 4th element $\frac{6 + 8}{2} = 7$.

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


# Question
Title: Worst known case for log rank conjecture
The log rank conjecture states that there is some universal constant $c \> 0$ so that

$$CC(f) = O(\log^c \text{rk}\\,(M\_f))$$

where $f : X \times Y \to \\{0, 1\\}$ is a boolean function, $CC$ denotes the deterministic communication complexity, $M\_f$ is the $|X| \times |Y|$ binary matrix associated to $f$, and $\text{rk}\\,(M\_f)$ is the rank of $M\_f$ calculated over the reals. In the literature, it mentions that this $c$, if it exists, is at least $\log\_3 6 \approx 1.631\ldots$, and attributes this to an unpublished result of Kushilevitz in 1994. Does anyone know what example Kushilevitz uses to achieve this lower bound? I think it would be interesting to see what the worst case might be and it might give insight into how to solve the problem in general.

# Answer
The function is described in a footnote in Nisan and Wigderson's paper On rank vs. communication complexity. It is

$$ E(z\_1 \dots z\_6) = \sum\_i z\_i - \sum\_{ij} z\_{i}z\_{j} + \\z\_1z\_3z\_4 + z\_1z\_2z\_5 + z\_1z\_4z\_5 + z\_2z\_3z\_4 + z\_2z\_3z\_5 + \\ z\_1z\_2z\_6 + z\_1z\_3z\_6 + z\_2z\_4z\_6 + z\_3z\_5z\_6 + z\_4z\_5z\_6. $$
> 4 votes

---
Tags: communication-complexity
---


# Question
Title: Need introductory guide to cellular automata for geographic automata systems
I would like to work on urbanisation and I've read that cellular automata has potential use on model urban sprawl. However I need some kind of introductory to cellular automata in order to tackle an academic paper I have found.

I have a fair background in Computer Science. Moreover I am looking for any tools from CS applied to cities.

# Answer
This here might help you as an introduction to cellular automata, written by Joel L. Schiff: INTRODUCTION

Furthermore, there is a copy of "Modelling Urban Development with Geographical Information Systems and Cellular Automata" by Yan Liu online. I do not know whether I can link it here, but you can easily search for it.
> 0 votes

---
Tags: automata, applied-theory, cellular-automata
---


# Question
Title: Solve using master method $T(n) = n · T(n/2) + n^{\log n}$
$T(n)=n\displaystyle \cdot T\left(\frac{n}{2}\right)+n^{\log\_{2}n}$.

$f(n) = n^{\log\_{2}n}$

Number of leaves = $n^{\log\_{a}b} = n^{\log\_{2}n}$

CASE 2 (All level same)

$f(n) = \Theta(n^{\log\_{b}a} {\log^{k}n}) $

$f(n) = \Theta(n^{\log\_{2}n} {\log^{0}n}), $ because $b = 2$, $a = n$, $k = 0$

Is $T(n) = \Theta(n^{\log\_{2}n} {\log\_{2}n)} $ correct?

# Answer
> 1 votes
This recurrence cannot be solved with the master theorem, since the master theorem only applies to recurrences of the form $T(n) = aT(n/b) + f(n)$ where $a\geq1$ and $b\>1$ are constants. Your recurrence is not of this form, so the theorem doesn't apply.

# Answer
> 0 votes
Let $T(n) = n⋅T(n/2) + n^{log\_2n}$, and let $T(n) = (1 + C(n))·n^{log\_2n}$.

Then $T(n) = n⋅(1 + C(n/2))·(n/2)^{log\_2n - 1} + n^{log\_2n}$

$T(n) = 2⋅(1 + C(n/2))·(n/2)^{log\_2n} + n^{log\_2n}$

$T(n) = (1 + C(n/2)) / 2^{log\_2n - 1} ·n^{log\_2n} + n^{log\_2n}$

$T(n) = (1 + (1 + C(n/2)) / 2^{log\_2n-1}) · n^{log\_2n}$

$C(n) = (1 + C(n/2)) / 2^{log\_2n-1} = (1 + C(n/2)) · (2/n)$

Clearly C(n) -\> 0, therefore $T(n) = \Theta(n^{log\_2n})$. Actually, the limit of $T(n) / n^{log\_2n}$ is 1.

$n^{log\_2n}$ grows so fast that n·T(n/2) cannot keep up with it. For T(n) to grow faster than $O(n^{log\_2n})$, n·T(n/2) would have to grow faster, and it doesn't.

---
Tags: algorithms, complexity-theory, time-complexity, asymptotics
---


# Question
Title: Why there is no FPTAS for multiple knapsack problem for two knapsacks unless P=NP?
The multiple knapsack problem (MKP) is defined in "A PTAS for the Multiple Knapsack Problem" as:

* *Instance*: A pair $(B, S)$ where $B$ is a set of $m$ knapsacks and $S$ is a set of $n$ items. Each bin $j\in B$ has a capacity $c(j)$, and each item has a size $s(i)$ and a profit $p(i)$.
* *Objective*: Find a subset $U\subseteq S$ of maximum profit such that $U$ has a feasible packing in $B$.

To prove that there is no FPTAS for MKP, the authors reduce partition problem (PP) to MKP with $m=2$ as follows:

> Given an instance of PP, $a\_{1},\ldots,a\_{2n}$. We set $c(1)=c(2)=\frac{1}{2}\sum\_{i=1}^{2n}a\_i$. We have $2n$ items, one for each number in the PP: the size of item $i$ is $s(i)=a\_i$ and the profit is $p(i)=1$. If the PP has a solution, the profit of an optimum solution to the corresponding MKP is $2n$; otherwise it is at most $2n-1$.

However, I do not understand why the created instance of MKP is hard. I mean we have a set of $2n$ items where each item $i$ has size $s(i)=a\_i$ and a profit $p(i)=1$. Also, we have $2$ knapsacks with identical capacity $c(1)=c(2)=\frac{1}{2}\sum\_{i=1}^{2n}a\_i$. We would like to maximize the number of assigned items to the two knapsacks such that the capacity of each knapsack is respected. Why we could not do the following?

1. Sort the items in increasing order of their sizes;
2. Pick an arbitrary knapsack, say $1$;
3. Fill it with items until its capacity is attained; and
4. Repeat 2. and 3. for knapsack $2$.

Sure I am missing something here but I do not know where.

# Answer
There is no guarantee that the packing algorithm you suggested will lead to an optimal packing. Say you have two knapsacks of capacity 5, and objects of size 1, 2, 3 and 4. An optimal packing would be putting 1 and 4 into knapsack 1, and 2 and 3 into the other knapsack (switching the indexes on the knapsacks would also be another alternative solution and this is a further complication). The greedy algorithm you have given would not result in this packing.
> 7 votes

---
Tags: algorithms, reductions, knapsack-problems
---


# Question
Title: Minimum number of shopping trips for a group of people to buy presents for each other
We have a group of $n$ people. We are given a list of who must buy presents for whom within the group. Each person might need to buy/receive any number of presents, or possibly none at all. In a shopping trip, a subset of the people travel together to the same store, and buy presents for anyone who is not present at the store. They may not buy presents for someone else on the same shopping trip because then it wouldn't be a surprise. A person may go on multiple shopping trips. We want to minimize the total number of shopping trips required for everyone to buy all the presents they need.

As an example, consider the case where there are 5 people, and each must buy presents for every other person in the group. Let the people be numbered 1 to 5. This can be done in 4 shopping trips, as shown:

* Trip 1: 1, 2, 3 go shopping
* Trip 2: 1, 4, 5 go shopping
* Trip 3: 2, 4 go shopping
* Trip 4: 3, 5 go shopping

How would I go about solving this problem? It is obvious that the input can be represented by a directed graph, but I don't know where to go from there. Someone brought up the biclique cover problem, but while similar, it does not answer this question.

We can think of the input as a directed graph $G$ on $n$ vertices, where the edge $(u,v)$ means that person $u$ must buy a present for person $v$. The goal is to find a set of bicliques $(S\_1,T\_1),\dots,(S\_k,T\_k)$ such that $k$ is minimal and the edge set $E$ of the graph is a subset of $\cup\_i (S\_i \times T\_i)$. Also, in extending the definition of bicliques to a directed graph, a biclique $(S\_i,T\_i)$ only contains edges which map $S\_i$ to $T\_i$. This differs from the biclique cover problem in that we don't require each biclique to be a subgraph of $G$ (we don't require $S\_i \times T\_i \subseteq E$ for each $i$).

Specifically, I will accept an answer that either:

* Demonstrates that this problem is NP-hard *or*
* Presents a polynomial time algorithm that answers this question exactly (no approximants or upper bounds)

For the record, I did not see this problem anywhere, I am just wondering about it for my own curiousity.

# Answer
This problem is *NP-hard*. To show this, I will first reformulate this (optimization) problem into a decision problem. Then, I reformulate that problem into an equivalent one, from which it is fairly simple to get a reduction from the $k$-coloring problem, which is NP-hard for any $k\geq 3$.

A short formulation of the problem is the following:

> Given $n$ persons and a graph $G$ that encodes their 'gift-giving' relations, find the minimum amount of trips required such that all gifts can be bought without ruining any surprises.

However, this is an optimization problem. The class NP is usually defined for descision problems (where the answer to every instance is either YES or NO). A decision variant of this is:

> Given $n$ persons and a graph $G$ that encodes their 'gift-giving' relations and an integer $t$, is making at most $t$ trips sufficient to buy all gifts without ruining any surprises?

I define the problem of finding a *proper directed $t$-multicoloring* of some graph $G=(V,E)$ as finding a *multicolor function* $c:V\rightarrow \mathcal{P}(C)$ which is *proper*, where $C$ is some set of $t$ 'colors' (i.e. $|C|=t$) and $\mathcal{P}(C)$ is the power set of $C$ (i.e. the set of all subsets of $C$). A multicolor function is proper if and only if for every edge $(u\rightarrow v)\in E$, we have that $c(u) \not\subseteq c(v)$.

I claim that the shopping trip problem is equivalent to the problem of deciding the existence of an *directed $t$-multicoloring* of the same graph $G$.

*Proof*: If we have a proper directed $t$-multicoloring $c$ for $G$, where we rename the colors such that $C = \\{1,\ldots, t\\}$ then consider the sequence of $t$ trips $T\_1,\ldots, T\_t$, where a vertex $v$ goes shopping in trip $T\_i$ if and only if $i\in c(v)$. Then, for every edge $(u\rightarrow v)\in E$, we have that there exists a trip $T\_i$ such that $u\in T\_i$ and $v\notin T\_i$, since $c(u) \not\subseteq c(v)$. Therefore, the trips $T\_i$ are sufficient to buy all gifts.

If we have a sequence of trips $T\_1,\ldots, T\_t$, then construct the multi-color function $c$ on color set $C=\\{1,\ldots, t\\}$ such that $c(u) = \\{ i \in \mathbb{N} | u \in T\_i\\}$. Then, for every edge $(u\rightarrow v)\in E$, there exists a trip $T\_i$ such that $u\in T\_i$ and $v\notin T\_i$ (since $u$ can buy a present for $v$ on some trip), which means that $i\in c(u)$ and $i\notin c(v)$, so $c(u) \not\subseteq c(v)$. $\square$

Finding a proper directed $t$-multicoloring is basically a weird reformulation of a specific case of $k$-coloring. Therefore, I can show a polynomial time reduction from the $\binom{t}{\lfloor t/2 \rfloor}$-coloring problem: Given an undirected graph $G' = (V',E')$, first transform this graph into the directed graph $G=(V,E)$, such that $V=V'$ and $(u\rightarrow v)\in E$ if and only if $(u,v)\in E'$ or $(v,u)\in E'$ (in other words, we change undirected edges into two directed edges).

Consider a largest set $K\subset \mathcal{P}(C)$, such that there exist no $a,b\in K$, $a\neq b$, such that $a\subset b$. The set of all subset of $C$ of size $\lfloor t/2\rfloor$, where $t=|C|$, is such a set. Therefore, the maximum size of such a subset is $\binom{t}{\lfloor t/2 \rfloor}$.

If a proper $t$-multicoloring exists for $G$, then there exists a proper coloring that uses no more than $\binom{t}{\lfloor t/2 \rfloor}$ unequal elements from $\mathcal{P}(C)\ $ (\*), so this is a valid $\binom{t}{\lfloor t/2 \rfloor}$-coloring for $G'$.

If a proper $\binom{t}{\lfloor t/2 \rfloor}$-coloring exists for $G'$, then there exists a set $K\subset \mathcal{P}(C)$, $|C|=t$, such that $|K| \geq \binom{t}{\lfloor t/2 \rfloor}$ and there does not exist any $a,b\in K$, $a\neq b$, such that $a\subset b$. So, $G$ has a proper directed $t$-multicoloring.

Therefore, this is a valid polynomial time reduction from $\binom{t}{\lfloor t/2 \rfloor}$-coloring to the present shopping problem with $t$ trips, which means the present shopping problem is NP-hard. Note that the present shopping problem is NP-complete, since we can verify easily if a given list of at most $t$ trips allows us to buy all presents without ruining surprises.

---

(\*): If some multi-coloring $\mathcal{C}$ uses more color-sets than a maximal 'non-subset' multi-coloring $\mathcal{C}^\*$, we can 'rename' $\mathcal{C}$ such that it is a superset of $\mathcal{C}^\*$. $\mathcal C$ remains proper, as none of the elements from $\mathcal{C}^\*$ being adjacent to a different element from $\mathcal{C}^\*$ is a problem and none of the color-set were adjacent to each-other in the original $\mathcal{C}$. So, without loss of generality, we can assume $\mathcal{C}^\* \subset \mathcal{C}$.

Then, note that 'renaming' $\mathcal{C}\setminus \mathcal{C}^\*$ to any subset of $\mathcal{C}^\*$ does not ruin the edges between nodes of color-sets $\mathcal{C}\setminus \mathcal{C}^\*$, since $\mathcal{C}^\*$ contains no elements that are a subset of another. The only thing that is left is to ensure that the edges between $\mathcal{C}\setminus \mathcal{C}^\*$ and $\mathcal{C}^\*$ do not 'ruin' the coloring.

Consider the following relation $R$ on the color-sets in $\mathcal{C}\cup \mathcal{C}^\*$: two color-sets $A$ and $B$ are *connected* if and only if there exists a pair of vertices $a,b$ such that $a$ has color-set $A$ and $b$ color-set $B$ and $(a,b)\in E$. This relation can be represented by the undirected graph $\mathcal G = (\mathcal{C}\cup \mathcal{C}^\*, R)$.

First, we can 'reduce' $\mathcal{C}\setminus \mathcal{C}^\*$ by replacing any pair that does not have an edge in $\mathcal G$ by a single color-set. The coloring remains proper, since changing two colorsets that are not adjacent at all into the same color does not introduce any invalid edges. As a result, we have reduced $\mathcal G$ to a complete graph.

This means that if $\mathcal G$ has a less or equal amount of color-sets as $|\mathcal{C}^\*|$, the required coloring exists. Otherwise, there exists no proper multi-coloring at all, since $\mathcal{C}^\*$ is a largest 'non-subset' set, so we are unable to color this clique. Therefore, the required multi-coloring necessarily exists.

---

As the complete graph on $n$ nodes $K\_n$ is color-able if and only if we have at least $n$ colors, we have that $n$ people can go shopping presents for each other in $t$ trips if and only if $\binom{t}{\lfloor t/2 \rfloor} \geq n$. This means in particular that, if $n\leq 12870$, making only $16$ trips is sufficient. If there are fewer presents to buy, more trips won't be needed, so this is a general upper bound on every solution.

---

Below is my earlier 'answer', which gives a heuristic algorithm that does not guarantee to get the optimum, but can be computed in polynomial time.

Another way to formulate this problem is to find a covering $C = \\{(S\_1,T\_1), \ldots, (S\_m,T\_m)\\} $ of bipartite graphs on the partitions $(S\_i,T\_i)$ for some directed graph $G$ with $n$ nodes, such that the amount of partitions (i.e. trips), here $m$, is minimal.

First, some observations, partially coming from other answers:

* The greedy strategy, where we pick a $(S\_i,T\_i)$ with a bipartite graph where the amount of edges in common with $G$ is maximal, does not lead to an optimal solution (A strong counter-example is the full graph with $6$ nodes, where this strategy fails, no matter which maximum bipartite graph is chosen.).
* The greedy strategy is **not** optimal for arbitrary acyclic graphs, consider the following graph:  Both for $S\_i = \\{3,5,6\\}$ and $S\_i=\\{1,3,6\\}$ the bipartite graph removes $4$ edges, but only $\\{3,5,6\\}$ is optimal.
* Any (optimal) greedy algorithm cannot prefer the size of the partition chosen over the amount of cycles (of *any* size) 'removed' by the partition. To see this, consider the graph with $n+2$ nodes, where there is one cycle of $n$ nodes and every node in the cycle has $2$ additional outgoing edges towards $2$ additional nodes $A,B$, which have no outgoing edges (See figure below for an example where $n=4$). A greedy choice that prefers to maximize the amount of edges over cycles of length $n$ will send all vertices in the cycle on the first trip. This is suboptimal, as this does not remove any edges of the cycle and simply ignoring $A,B$ and removing all edges from the cycle removes all edges towards $A,B$ as well. So any greedy choice that prefers the size of the partition over removing a cycle is not optimal.

Based on these observations, I propose the following greedy choice: Pick $(S\_i, T\_i)$ such, that the amount of cycles that this trip 'removes' from $G$ is maximal and in case of ties, choose a partition with maximum overlap with $G$ among them (i.e. look at the edges not on cycles).

Since this algorithm isn't different from the 'basic' greedy strategy on acyclic graphs (removing a maximum amount of edges on every trip), this greedy algorithm therefore is not optimal. However, the intuition of removing cycles still makes sense and is an improvement over the basic greedy strategy, so it could be a decent heuristic.
> 3 votes

# Answer
I can see how to reduce this problem to Graph Colouring, which gives you a tool for solving the problem (for small instances!), but not yet how to reduce in the other direction (which would establish NP-hardness).

The basic idea is to build a graph that contains a vertex for every *purchase*, and an edge between any two purchases that cannot occur on the same trip; we then look to group the purchases into the smallest possible number of groups ("trips"), such that no two purchases in the same group would conflict. Specifically, if $G = (V, E)$ is the original directed graph in which an edge $uv$ indicates that person $u$ needs to buy person $v$ a gift, then create an undirected graph $H = (X, Y)$ in which there is a vertex $x\_{uv}$ for each edge $uv$ in $G$ and an (undirected) edge $x\_{uv}x\_{vw}$ whenever $uv$ and $vw$ are both (directed) edges in $G$ (if $v$ buys some $w$ a gift during a trip, then no one can buy $v$ a gift during that same trip). A vertex colouring of $H$ is a partition of the necessary purchases (vertices in $H$) into trips (colours) that don't conflict (share an edge), and a vertex colouring of minimum size takes the fewest possible trips.

It might be possible to go in the other direction (reduce Graph Colouring, or some other NP-hard problem, to your problem, and thereby establish its NP-hardness), by adapting a reduction from 3SAT to Graph Colouring (as, e.g., detailed on p. 10 of Jeff Erickson's notes), but I haven't attempted this myself.
> 2 votes

# Answer
It's the kind of problem where I would be very worried if my boss asked my to implement an algorithm that is guaranteed to find an optimal solution in reasonable time.

To find a not necessarily optimal solution: Given any set of people and presents to buy, we can count how many presents a group of people can buy on a shopping trip. So start with an empty group (which can buy 0 presents). For each person not in the group, determine how many presents can be bought if that person is added to the group. If there is any person that we can add without decreasing the number of presents, pick at random one of those that increase the number of presents bought by the maximum amount, until adding any person would reduce the number of presents bought. Then do that shopping trip and start all over until all presents are bought.

I'd repeat a few times, picking different people "at random" in case that finds a better solution.

In the example, five people having to buy a present for each other, this finds a solution in four trips, which is optimal; if we didn't add persons to a trip that leave the number of presents unchanged without improving it, we would have five trips. And 6 people require 5 trips.
> 0 votes

# Answer
Assume that you order the people based on who they are receiving from (parent), and who they are giving to (child). Since everyone gives one present and receives one present, parent-child function is one-to-one.

You never want to put the parent and the child into the same group. You start with a random person $p\_1$ and order everyone accordingly, so $child(p\_1)=p\_2$, etc. You put all $p\_{odd}$ into one group, and all $p\_{even}$ into another group. For the last person $p\_n=parent(p\_1)$, so you don't want this person to be in the same group with $p\_1$. If $n$ is even, it is not a problem. Else, you need one additional group, that can be just $p\_n$ by itself, in the simplest case.

This algorithm assumes everyone is connected. But it does not need to be the case. If there are multiple disconnected cycles, in other words, if at some point, $p\_k=parent(p\_1)$ where $k!=n$, then you finish that circle and start with a new one, following the same algorithm. As long as you don't merge the odds and evens of the same cycle, you can merge disconnected cycles.

This algorithm ends up with at most 2 rounds (for even $n$) and 3 rounds (for odd $n$).
> -1 votes

---
Tags: algorithms, graphs, set-cover
---


# Question
Title: Is maximum matching problem equivalent to maximum independent set problem in its dual graph?
A hypergraph $H = (V,E)$ consists of a set $V = \\{v\_1, v\_2, \cdots, v\_n\\}$ of vertices and a set $E = \\{e\_1, e\_2, \cdots , e\_m\\}$ of edges, each being a subset of $V$.

A subset $M \subseteq E(H)$ is a ***matching*** if every pair of edges from $M$ has an empty intersection.

The *dual* $H^\*$ of $H$ is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by $\\{e\_1, e\_2, \cdots , e\_m\\}$ and whose edges are given by $X = \\{X\_1, X\_2, \cdots, X\_n\\}$ where $X\_j = \\{e\_i | v\_j \in e\_i \\}$, that is $X\_j$ is the collection of all edges containing $v\_j$.

**My question: Is maximum matching problem equivalent to maximum independent set problem in its dual graph?** Are both NP-hard and cannot be approximated to a constant factor in polynomial time (unless P = NP)?

Thank you!

# Answer
To start with possible NP-hardness (where for each problem, we want a matching/independent set of size at least $k$):

* Independent set is NP-hard on "normal" graphs (and also on hypergraphs)
* Maximum matching is polynomial-time solvable on "normal" graphs, see the wikipedia page on matching.
* Maximum matching is NP-hard in hypergraphs (as shown in this wikipedia page, it is even hard for hypergraphs where each edge contains only 3 vertices).

I believe both problems are equivalent in the following sense: set $S \subseteq E(H)$ is a matching in $H$, if and only if $S$ forms an independent set in $H^\*$.

(If you need further explanation or if this is not your definition of equivalance, please clarify)
> 3 votes

---
Tags: complexity-theory, graphs, approximation
---


# Question
Title: Why do i have to show that a problem L $ \in $ NP before i start a polynomial reduction?
i want to do a polynomial reduction from the Independent-Set-Problem which is NP-complete to the AUCTION-Problem, to show that AUCTION $\in$ NP-complete, but why do i always have to show first, that our problem(in this case AUCTION) $ \in $ NP?

# Answer
> 3 votes
Because a problem L is NP-complete if and only if:

* L is in NP
* L is NP-hard: every problem A in NP can be polynomially reduced to L.

So to show that L is NP-complete, you have to demonstrate both the properties.

---
Tags: np-complete, np, decision-problem
---


# Question
Title: How to solve this partial order reduction in $O(n^2)$?
There are two orderings of numbers from the same set. Number $a$ is "immediately before" $b$ **iff** $a$ appears before $b$ in both sequences **and** there is no other number that appears between them in both sequences.

So in this example:

```
Seq 1: 1 2 3 4 5 6
Seq 2: 6 2 1 3 5 4

```
* 1 is not immediately before 2 because they appear in opposite orders.
* 1 is not immediately before 4 because 3 appears between them in both sequences.
* 2 is immediately before 3 and 3 is immediately before 4.

The problem is to find all pairs $a$, $b$ such that $a$ is immediately before $b$ in $O(n^2)$ time. How can this be done?

I understand that the naive solution can work in $O(n^3)$: For each pair in the first sequence ($n^2$ pairs) verify it using the second sequence ($O(n)$ time).

# Answer
I think I am able to solve it.

First, have a lookup array for each sequence where array\[element\] = element's position in sequence *\[O(1)\]*.

Phrased another way, this algorithm will find all "successors" for each of the elements in the first sequence. Finding successors for each element will take O(n) time.

```
For i in range(0,n):
    initialize most_recent_successor to None
    For j in range(i+1, n):
        if pos. of seq_1[j] > pos. of most_recent_successor in both sequences:
            advance j
        else:
            most_recent_successor = seq_1[j]
            add (seq_1[i], seq_1[j]) to result

```

Essentially, if a valid pair `(seq_1[i], seq_1[j])` exists, then any pair `(seq_1[i], seq_1[k])` will not be valid if the position of `seq_1[k]` in comes after the position of `seq_1[j]` in both sequences.

So, for the example in the question, `(1, 3)` is a valid pair. Therefore, `(1,4)` and `(1, 5)` are not valid pairs since `4` and `5` come after `3` in both sequences.

**Edit:** Please look at ruakh's insightful answer on lookup arrays I used here.
> 1 votes

# Answer
Your solution looks good to me, except that your lookup arrays are a bit handwavy: What happens if the set contains negative numbers? Or what if it contains an extremely large number ($\gg n^2$), so that the arrays would need to be massive?

To address this, I'd suggest creating just a single lookup table, that instead of mapping from *values* to *indices*, maps from *indices in one sequence* to *indices in the other*. Thus seq2\[i\] = seq1\[translator\[i\]\]. You can build that table in $\mathcal{O}\left(n^2\right)$ time using nested loops. You can then ignore seq1 and seq2 in all of your logic: the problem becomes, "find all pairs of indices (i, j) such that i \< j, that translator\[i\] \< translator\[j\], and that i \< k \< j precludes translator\[i\] \< translator\[k\] \< translator\[j\]" (which you can solve using basically the same approach as what you've written). The only time you'd refer to seq1 or seq2 again is when you're adding an entry to the result (since for that you want the actual values rather than the indices).
> 1 votes

---
Tags: algorithms, partial-order
---


# Question
Title: Why does this pumping lemma proof not cover every division of xyz?
I am trying to prove $L =$ {${a^k|k=2^n, n \ge 0}$} is not regular. So far I have identifed a string $s = a^{2^p}$, and I've divided $s$ into $xyz$ as follows:

$x = a^l$

$y = a^k$

\*(where $k + l \le p$)

$z = a^{2^p-l-k}$

Now, when I start to look at pumping, I first select $i=0$:

$xy^iz = xy^0z = xz = a^la^{2^p-l-k}=a^{2^p-k}$, which is clearly not equivalent to $a^{2n}$. However, I know that there are mistakes in this proof and I have been told that my division of the string $s$ into $xyz$ does not account for all divisions. Could anyone please help?

# Answer
> 4 votes
For reference, the pumping lemma is (from Introduction to the Theory of Computation by Michael Sipser)

> If $A$ is a regular language, then there is a number $p$ (the pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:
>
> 1. for each $i ≥ 0, xy^i z \in A$,
> 2. $|y| \> 0$, and
> 3. $|xy| \le p$.

When you want to prove that a language is not regular using the pumping lemma, you use a proof by contradiction. You first assume that the given language is regular.

As per the pumping lemma, given a regular language, *there exists* a number $p$ such that *for all* $s$ with length at least $p$, *there exists* a way to partition it in the form $x,y,z$ such that *all* the three conditions hold.

The contrapositive is

*For all* $p\ge1$, *there exists* a string $s$ with length at least $p$, such that *for all* ways to partition $s$ in the form $x,y,z$, *at least* one of the three conditions are false, implies that the language is not regular.

So, to show that $L$ is not regular, you need to show that the appropriate quantifier (existential or universal) for each entity is used correctly.

Initially, you have taken a value $p$, with no assumption. This is in accordance with *for all* $p$.

Then, you have chosen a string $s$ with length at least $p$. This is in accordance with *there exists* a string $s$, i.e., a single instance of a string satisfying the rest of the statement is sufficient.

Now, you need to consider *all ways* of partitioning $s$ in the form $x,y,z$, and show that always, at least one of the three statements of the lemma is false.

So, you have partitioned it into $x=a^l, y=a^k, z=a^{{2^p}-l-k}$. As of now, there are no assumptions on the values $l$ and $k$ can take, except that they are non negative, which is as required. To force a contradiction, you need to try to show that all the statements of the lemma do hold. Statement 2 states that $|y|\gt0$. So, if it were true, we must have $k\gt0$. Statement 3 states that $|yz|\le p$. If it were true, we must have $k+l\le p$.

Finally, Statement 1 must be true if $L$ is regular, so $xy^iz\in L$ for all $i\ge0$ must be true. It is sufficient thus to show that it is false for any one value of $i$. I choose $i=2$. So, we must have $a^la^{2k}a^{{2^p}-l-k}=a^{{2^p}+k}\in L$ for all possible values of $l$ and $k$ except as per the previously imposed restrictions.

Now, we have $$k\gt0\implies k\ge1$$ $$2^p+k\ge 2^p+1\gt 2^p\tag1$$

$$k+l\le p$$ But $l\ge 0$, so we have $$k\le p$$ $$2^p+k\le 2^p+p\tag2$$

But we have $$p\lt 2^p$$

for all $p\ge 1$, which is the set of all allowed values of $p$. So, $(2)$ becomes, $$2^p+k\le 2^p+p\lt 2^p+2^p=2^{p+1}\tag3$$

From $(1)$ and $(3)$,

$$2^p\lt 2^p+k \lt2^{p+1}$$

As $2^p+k$ lies strictly between consecutive powers of $2$, it cannot be a power of $2$ itself. So, $a^{2^p+k}\notin L$, and we have a contradiction as desired.

Thus, $L$ is not regular.

---

In your proof, the initial steps are all correct, all you need to do is to show why the string cannot lie in the language, using an appropriate value of $i$, as shown in this answer. Moreover, choosing $i=0$ is not straightforward. For $i=2$, I argued that $2^p\gt p$. For $i=0$, you will need to use $2^{p-1}\gt p$, which is not true if $p=1$.

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


title: forall a b, a -> b

text:
# Question
Title: forall a b, a -> b
I know for pretty sure that there is a function with the type $f: \forall \alpha, \beta . \alpha \rightarrow \beta$ (at least in a Hindley-Milner type system), but I can't wrap my head over it. ~~Neither could I think of an actual function with this type.~~

I found a function of this type, which in Standard ML would be written as:

```
fun f x = f x

```

But I am not sure of the lambda calculus equivalent of this function.

Moreover, if I'm right about Curry-Howard, the isomorphism of this type is the proposition $\forall A, B . A \implies B$, which does not make sense for me. Is it possible that someone give a function with type $f$ and explain its Curry-Howard equivalent to me?

# Answer
Think of this in terms of the Curry-Howard isomorphism. What would this type look like as a theorem?

* For any propositions $A$ and $B$, $A \implies B$.

Clearly this is not true, if it were, then we could do $A=\top$ and $B = \bot$ and now true implies false! So, if it's not a true theorem, there's no proof of it, so the type is uninhabited.

In a language like Haskell or SML, you write a function of this type, as long as it doesn't terminate or is undefined:

```
myfun x = undefined
> myfun :: t -> t1

```

but in a total language with a sound type system, this should not be possible.
> 5 votes

# Answer
> I know for pretty sure that there is a function with the type $f: \forall \alpha, \beta . \alpha \rightarrow \beta$, but I can't wrap my head over it.

No, that type is not inhabited. There are no functions having that type in a typed lambda calculus, provided it is (weakly) normalizing.

The intuition is that, as you mention, the associated proposition is clearly not a theorem.

More in detail, if we had an inhabitant $f : \forall \alpha, \beta . \alpha \rightarrow \beta$, then we would have $$ \lambda \alpha. f (\alpha\to\alpha)\alpha(\lambda a:\alpha. a) \ :\ \forall\alpha.\alpha $$ hence *every* type would be inhabited, making our system inconsistent -- but we know that's not the case.

---

By the way, what makes you think there should be such an $f$? Even in everyday programming, we can't really convert a value of a type $\alpha$ to any other arbitrary type $\beta$.
> 5 votes

---
Tags: type-theory, curry-howard
---


# Question
Title: What is the generating function for the sequence $\{kH_k\}_{k \geq 1}$
I am trying to answer exercise 3.1 from Sedgewick and Flajolet's "Introduction to the Analysis of Algorithms". That is, I am trying to find the Ordinary Generating Function for the sequence:

$$\\{kH\_k\\}\_{k \geq 1}$$

I think that the generating function for this sequence is:

$$H\_1 + 2H\_2z + 3H\_3z^2 + 4H\_4z^3 + ...$$

which abbreviates to

$$\sum\_{n \geq 0} (n+1)H\_{n+1}z^n $$

By inspection, I see that this has the form of the Index Multiply operation on OGFs. This means that our generating function can be obtained by differentiating the OGF for the sequence

$$\sum\_{n \geq 0}H\_n z^n$$

I know that this

$$\sum\_{n \geq 1}H\_n z^n$$

has a well known OGF. But that is for the range $n \geq 1$, and our sequence has range $n \geq 0$. If I split off the first term $n = 0$, we get the sum:

$$H\_0 + \sum\_{n \geq 1}H\_n z^n$$

And it's now that I've lost my confidence. Is the method I've outlined above the right way to go in finding the desired OGF? If it is OK, it seems to rest on the existence of a zeroth Harmonic number. Is there actually a zeroth Harmonic number $H\_0$?

Thanks.

# Answer
> 3 votes
We know that a generating function for the Harmonic series is:

$$ \sum\_{i =1}^{\infty} H\_i z^i = -\frac{\log(1-z)}{1-z} $$

you may verify it by taking the MacLaurin expansion.

Taking the derivative with respect to $z$:

$$ \frac{d}{dz} \left ( \sum\_{i =1}^{\infty} H\_i z^i \right ) = \frac{d}{dz} \left ( -\frac{\log(1-z)}{1-z} \right ) $$

yields: $$ \sum\_{i = 1}^{\infty} iH\_i z^{i-1} = \frac{1 -\log(1-z)}{(1-z)^2} $$

Notice that LHS is exactly the formal series you mentioned.

---
Tags: algorithm-analysis
---


# Question
Title: Is it Possible to Get Maximum Weighted Input Value in a Neural Network?
Let's say that I have a standard feedforward neural network which has $M$ inputs, some number of hidden layers $N$, and a single neuron in the output.

Is it possible to construct a network such that the output neuron's output value is the maximum weighted input value?

I know that I could easily hard code something to make this happen, but I'd like to limit the construction to "standard" operations where the activation of a neuron is the dot product of the input vector and the weight vector with a bias added, then putting that value through a differentiable activation function.

# Answer
> 0 votes
No, not with standard activation functions, but you might be able to approximate it. For instance, if the activation function is differentiable, then the output of such a network will always be differentiable, but the "max" function is not differentiable.

You're more likely to get a useful answer if you provided some context about what you're trying to accomplish or how you'll use the answer. I suspect an XY problem.

---
Tags: neural-networks, neural-computing
---


# Question
Title: Why is computation of this function numerically unstable?
Why is computing the function at certain ranges of h $$f(x) = \dfrac{\sqrt{-x+a} - \sqrt{2x+a}}{ 4a}$$ unstable? How would I rewrite this function so that it is stable?

# Answer
> 10 votes
The question has been changed since this answer.

---

Another alternative is $$\begin{align}f(x)&=\frac{\sqrt{x+h}-\sqrt{x-h}}{2h}\\ &=\frac{\sqrt{x+h}-\sqrt{x-h}}{2h}\cdot\frac{\sqrt{x+h}+\sqrt{x-h}}{\sqrt{x+h}+\sqrt{x-h}}\\ &=\frac{1}{\sqrt{x+h}+\sqrt{x-h}}\end{align}$$

Now, even if $h$ becomes very small, the value approaches $$\frac{1}{2\sqrt{x}}$$ as it should.

# Answer
> 9 votes
What you are experiencing is called 'loss of significant digits'. As h gets smaller, the two square-root terms become closer and closer together, in the sense that their values start with more and more matching digits. Since floating-point cannot represent more than a finite prefix of the infinite-digit actual value for each term, the result of subtracting the terms eventually loses all meaningful information.

One way to rewrite this is to expand the two terms as Taylor series and subtract them symbolically; some terms will cancel, the rest will yield a useable series for evaluation (probably more stable, not necessarily more accurate).

# Answer
> 3 votes
We can write it as $$f(x) = \dfrac{\sqrt{-x+a} - \sqrt{2x+a}}{ 4a}= \dfrac{\sqrt{-\frac xa+1} - \sqrt{\frac{2x}a+1}}{ 4\sqrt a}$$ If $x \ll a$ both of the square roots will be just about $1$. When you add the $\frac xa$ terms to $1$ you will lose many bits of $\frac xa$, then when you subtract the square roots the $1$s will cancel. If your floats have $53$ bits in the mantissa and $\frac xa$ is about $2^{-30}$ you will only keep about $23$ bits of $\frac xa$. Only the top $23$ bits of the numerator will be accurate. You need to analytically cancel the $1$s to get the accuracy you want. You can do that with the Taylor expansion $$\sqrt {-\frac xa+1} \approx 1-\frac x{2a}, \sqrt {\frac {2a}x+1} \approx 1+\frac xa\\\sqrt{-\frac xa+1} - \sqrt{\frac{2x}a+1}\approx -\frac {3x}{2a}$$ Now you don't lose the precision.

---
Tags: numerical-analysis
---


# Question
Title: What would you call an algorithm that finds $R$ % of the time the optimal solution to an NP-hard problem?
According to Wikipedia,

A $\rho$-approximation algorithm $A$ is defined to be an algorithm for which it has been proven that the value/cost, $f(x)$, of the approximate solution $A(x)$ to an instance $x$ will not be more (or less, depending on the situation) than a factor $\rho$ times the value, $OPT$, of an optimum solution.

I am interested in a situation where we would like to measure the performance of $A$ by how often it finds the optimal solution. For example, the algorithm $A$ finds the optimal value $R$ % of the time and finds a strictly larger (or less) solution $100-R$ % of the time. What would such algorithm be called? Is this notion known in the literature?

# Answer
The idea you mention is covered in complexity theory by probabilistic classes.

The computational model they refer to is the *probabilistic Turing machine*, i.e. a Turing machine equipped with an additional read only tape that at the beginning of the computation contains an infinite sequence of symbols, independently chosen at random with uniform probability from the machine alphabet. Or, equivalently, a Turing machine that can flip a fair coin and read the answer in constant time.

Observe that due to the way that our computational model works, two executions on the same instance may give two different answers; for instance, one could define a machine that flips a coin and returns **YES** on heads and **NO** on tails.

We are interested in both the asymptotic worst-case running time and the probability that the answer given is actually correct. In literature, a vast amount of different classes are analyzed, they differ depending on various constraints that they impose on the solver.

Perhaps the most interesting of such classes, both from a theoretical and practical point of view is $\mathcal{BPP}$, defined as the class of languages decidable in polynomial time by a probabilistic Turing machine that, whether the answer is **YES** or **NO**, is guaranteed to give a correct answer with probability at least $2/3$. Notably, it is an open problem whether or not $\mathcal{P} = \mathcal{BPP}$.

A full discussion of probabilistic complexity theory would be too lengthy for SE, although there are plenty of sources available in both electronic and dead-tree form.
> 3 votes

---
Tags: terminology, reference-request
---


# Question
Title: Number of buckets for bucket sort (most significant bits)
Wikipedia has this pseudocode on bucket sort:

> `function bucketSort(array, n) is
>  buckets ← new array of n empty lists
>  for i = 0 to (length(array)-1) do
>  insert array[i] into buckets[msbits(array[i], k)]
>  for i = 0 to n - 1 do
>  nextSort(buckets[i]);
>  return the concatenation of buckets[0], ...., buckets[n-1]`

It also explains:

> Here `array` is the array to be sorted and `n` is the number of buckets to use. The function `msbits(x,k)` returns the `k` most significant bits of `x (floor(x/2^(size(x)-k)))`; different functions can be used to translate the range of elements in array to n buckets...

What baffles me is: Why would one want to initialize `buckets` with `n` buckets when `2^k` is the maximum number of values that `msbits` can possibly generate, given the way it's defined?

# Answer
> 3 votes
The code you found is unfortunately written and explained in a very confusing way, most notably in a way that, in my humble opinion, misses the entire point of Bucketsort.

Let $A$ be an array of $n$ elements, taken from the ordered set $(S, \le)$. Bucketsort is a sorting algorithm that sorts $A$ in linear time with probability $1$, *subject to the hypothesis that the statistical distribution of the elements of $A$ over $S$ is known in advance*.

For the sake of simplicity, we will assume $S$ to be the real interval $\[0, 1)$ and the distribution of $A$ to be uniform over $\[0, 1)$. Our second assumption is without loss of generality. In fact, should we be provided with a different probability density function $\rho$, we could simply replace each $x \in A$ with:

$$ x' =\int\_{0}^x \rho(z) dz $$

An analogous argument holds for different choices of $S$.

Bucketsort works as follows:

* Split $\[0, 1)$ in $n$ consecutive intervals, where $n = |A|$, such that the $i$-th interval is $\left\[ \frac{i-1}{n}, \frac{i}{n} \right)$
* Create $n$ empty lists $L\_1, L\_2, \dots, L\_n$
* For each element $x$ of $A$, add $x$ to the list corresponding to the interval in which it falls
* Sort each list individually, then return the concatenation $L\_1 \circ L\_2 \circ \dots \circ L\_n$

Correctness is obvious, but complexity isn't. The crucial hypothesis is that, by assumption, we are sorting elements *uniformly distributed* over $\[0, 1)$. Therefore, if $n$ grows large, as it is the case in the usual asymptotic setting, at the end of our third step, each of the lists will contain a constant number of elements with probability $1$; if that weren't the case, the elements wouldn't be uniformly distributed after all. Also observe that "with probability $1$" is not the same as "certainly", although it's as close as it gets.

The choice of exactly $n$ buckets is due to the fact that we want our last step to take *linear* time; but that can only be achieved if each list contains a *constant* amount of elements. We could have chosen just as well to use $n/c$ buckets for any $c \in \Theta(1)$, but we couldn't have started with $ k \in o(n)$ buckets; each of them would have contained $n/k \in \omega(1)$ elements. The total cost of sorting them would have been:

$$ k \left ( \frac{n}{k} \log \frac{n}{k} \right ) = n \log \omega(1) \in \omega(n) $$

# Answer
> 1 votes
Yes, msbits(x, k) can generate up to 2^k values. But this does not mean buckets\[\] array has to be length of 2^k. If buckets\[\] has length 2^k, each bucket has size one, and bucket sort degenerates into counting sort.

So, you want each bucket size to be more than 1. If we have n buckets, and msbits(x, k) returns 2^k values, then each bucket size is 2^k/n.

On the contrary, if we choose n = 1, then we will only have one bucket of 2^k. If we choose another sorting algorithm to this bucket, then our bucket sort will have the same order of growth as the chosen sorting algorithm.

---
Tags: sorting
---


# Question
Title: Simplified big O notation of $O(nm)$ for $n\gg m$
Assume $n$ is much greater than $m$. Would $O(nm)$ simplify to $O(n)$? Is there an explanation?

# Answer
> 4 votes
It depends what "$n$ is much greater than $m$" means but, in general, no. For example, one common definition of "much greater" is that $m=o(n)$. But, in this case, we can still have, e.g., $m=n^\epsilon$ for some $\epsilon\<1$, or $m=\log^c n$ for any $c\geq 0$ and, in both of these cases, $nm\neq O(n)$.

To get $nm=O(n)$, you need $m=O(1)$.

# Answer
> 0 votes
If an algorithm depends on both you cannot. Example can be a matrix operation where the size of a matrix is mxn. Even if you have 1000 rows (n) and only 2 columns (m), it's still a mxn complexity problem, not 2n, because m is not constant, it may vary.

---
Tags: asymptotics
---


# Question
Title: Proof of composition of one way function is not one way in general
In this How to show composition of one way function is not such? question, the accepted answer uses **g(x,y)** as a one way function. But, for a given output of g(x,y) = 0|x| of length l (say), isn't the output of **g(any x of length l, 0l)** the same as the earlier output? Isn't this a possible preimage of 0|x|?

# Answer
"for a given output of g(x,y) = 0|x| of length l (say)," "the output of **g(any x of length l, 0l)**"
is "the same as the earlier output", which means that is "a possible preimage of 0|x|".
Accordingly, for  $g\hspace{-0.04 in}\circ \hspace{-0.03 in}f$  to be one-way, it had better be the case that

$\operatorname{Prob}\_{\langle \hspace{.02 in}x,y\rangle \hspace{.02 in}\leftarrow \hspace{.02 in}\left(\hspace{-0.03 in}\\{\hspace{-0.02 in}0,1\hspace{-0.02 in}\\}^{\hspace{.02 in}L}\hspace{-0.03 in}\right)^{\hspace{.05 in}2}}\hspace{-0.1 in}\left\[g(x,\hspace{-0.04 in}y) = 0^{\hspace{.03 in}L}\hspace{-0.0 in}\right\] \\;\\;\\;$ is negligible.
> 1 votes

---
Tags: cryptography, one-way-functions
---


title: Proof by mathematical induction

text:
# Question
Title: Proof by mathematical induction
Before we start, my textbook declares lgn as base two.

I only have one question, how did log2 become n (both highlighted in yellow in the picture)? Is it because log2 = 1, which is too small to even matter?

# Answer
Since we're using base-$2$ logs, $\log2=1$, so $$n(\log n-\log 2) = n\big((\log n)-1\big)=n\log n -n\\,.$$

All of the stages of the calculation are written as equalities, so nothing should be being discarded as too small to matter (and nothing is).
> 1 votes

---
Tags: induction, mathematical-foundations
---


# Question
Title: NEAT algorithm and dynamic topology neural networks
I have recently been investigating dynamic topology neural networks and there is only one problem I have with understanding them. Because a neuron could be inserted at any point, the neurons are no longer organised into layers, so how is it possible to ensure that all of the inputs for Neuron A at position X have been computed, prior to the computation of Neuron A's output, especially when each neurons output is calculated linearly? I am by no means experienced in the topic, just curious so any information would be helpful, Thank you.

# Answer
Not an expert in neural net. But I recently read and answer a question on NEAT. From there, I would assume that direction of edges are already determined in each gene. Because of the way operations on genome was designed, I could see that you can ensure the genome is always in \`topological order'.

Alternatively, looking at heuristic algorithms that iteratively update graph's weight as it learns (e.g. pagerank and ACO), it should be fine to assume initial weight and just let the iteration stabilise. One could imagine this as every edge being directed both ways --- every link is both input and output.
> 1 votes

---
Tags: neural-networks
---


# Question
Title: Prove the following language is in L (LogSpace)
I'm trying to prove the following language is in $L$ (decided by a TM in $O(\log n)$ space):

$$A = \\{ (C,x) \mid C(x)=1\text{ and $C$ is a Boolean formula with depth }\log(n)\\}\\,,$$ where $n = |(C,x)|$. Equivalently, $C$ can be a Boolean circuit with maximum fan-out of $1$.)

Checking if a word $w$ is in "the right format" (meaning: $w=(C,x)$ for some $C$ Boolean formula/circuit, $x$ – input) takes $O(1)$ space. I'm not sure on how to check the value of the formula (thought of using recursion, but not sure how) such that it will need only $O(\log n)$ space. Also, how can I check that the depth of the circuit is $\log n$?

# Answer
> 3 votes
A Boolean formula is a circuit whose graph is a tree (each node has a single parent). Perform an in-order pass on the tree while remembering the current node and the last value.

When at a $\lor$ gate with a previous value $b$: If $b = 0$ leave the value the same and go to the node's parent. If $b = 1$ check the other (right) son. Same with $\land$ gate, and $\lnot$ gates are easier (check if $b = 0$). Accept $(C, x)$ if the value computed by $C$ (using the in-order search) is $1$.

Saving the current node takes $\log n$ bits, the current value takes $1$ bit and computing the parent also takes $\log n$. Overall there is a TM that uses $O(\log n)$ space that decides $A$, so $A \in L$.

---
Tags: complexity-theory, complexity-classes, space-complexity
---


# Question
Title: Does computability according to Church-Turing thesis include side effects?
To my understanding:

* The Church-Turing thesis means that one could theoretically compute anything that can be computed using either a Turing Machine or the Lambda Calculus.
* The Lambda Calculus is based on mathematical functions. This leads to the inability of "pure" functional programming languages based on Lambda Calculus to have side-effects (in the sense that a language like C would have side effects).

To me that would imply that side-effects are not part of computability, but something in addition to it.

e.g. I would say that real-world memory writes that cause physical side-effects are not of the same nature as the imaginary writes to the tape in a Turing Machine. Or put another way: if I'm writing values to memory whose purpose is to serve as a result in a calculation, Turing completeness would be theoretically relevant; but if I'm writing to a region of memory designed to instruct a robot arm to do things, Turing completeness would be theoretically irrelevant.

Is my understanding correct?

# Answer
The Church-Turing thesis says that Turing machines capture precisely the effectively calculable functions **from natural numbers to natural numbers**. It says little about what happens when we attach a robotic arm to a computer.

Any kind of machine needs to *represent* numbers in some way, obviously since numbers are abstract entities. A Turing machine represents them with 0's and 1's written on a tape. In $\lambda$-calculus we represent them with Church numerals. If we attached a robotic arm to an iPhone, we could represent them with a suitable number of up-down movements by the arm. The question of representation is separate from the question of side effects. In particular, the question of what can be computed is separate from how the results can be communicated. Lamenting about the fact that $\lambda$-calculus has no input/output, for instance, would be misguided.

There is a well understood theory of computational side effects. According to this theory, Turing machine have certain side effects. They carry *state* in their cells, that is a side effect. We can implement *quoting* on Turing machines, that is the side effect which converts a closure to source code. Turing machines with oracles can be seen as having the "input" side effect (known as a reader monad in functional programming).

In summary, the Church-Turing thesis is largely independent of what computational effects might be present in the computational model. This is so because the Church-Turing thesis is about numer-theoretic functions, not about how computers interact with their environment.
> 8 votes

# Answer
As always in computability, you need to consider the model of computation. If your model of computation is the lambda calculus then, as you say, clearly there are no side-effects. If your model of computation is C programs, then clearly there are side-effects. If your model is Turing machines, then "side-effects" doesn't really make sense because there are no functions: the only thing in town is a spaghetti program writing to a tape.

Turing completeness deals with computations that start with some input and compute some function. If your model of computation includes a robot arm then that's absolutely relevant (the state of the arm and the things it manipulates are part of the computation). But even without that, you can use classical computability to determine what things you can computably tell the robot arm to do by writing to its DMA area.
> 2 votes

# Answer
The question is not totally formalizable, so it's hard to answer it in a definite way.

However, you are correct when you say that Turing completeness does not imply the presence of side effects -- its definition only cares about the input-output behavior. The pure lambda calculus does not have side effects, yet it is Turing complete.

> e.g. I would say that real-world memory writes that cause physical side-effects are not of the same nature as the imaginary writes to the tape in a Turing Machine.

I would agree to this.

> \[...\] if I'm writing to a region of memory designed to instruct a robot arm to do things, Turing completeness would be theoretically irrelevant.

Well, it would be still relevant since you need to compute what to write on that memory cell before you can write to it. E.g. assume you have a sensor providing you some reading $x$ (e.g. a webcam image), and you want to move your robotic arm depending on $x$ (grab the ball which is in the image). Then, you need to compute the coordinates at which you want to move the arm. In the example I mentioned, you need image/pattern recognition, so you need to ability to run sophisticated algorithms.

As usual, for any given task, you probably don't need a Turing-complete machine. However, if you want to build a general-purpose robotic arm, it should be equipped with a general-purpose computer.
> 1 votes

---
Tags: computability, turing-machines, church-turing-thesis
---


# Question
Title: A new definition of recursively enumerable set?
Given a Turing machine $M$, we associate a partial function $f\_M : \Sigma^{\ast} \to \Sigma^{\ast}$ to it (this is called the function computed by the machine), where $\Sigma$ denotes the finite input and output alphabet, defined as $$ f(u) = v :\Leftrightarrow \mbox{The machine halts on input $u$ with output $v$}. $$ Then we say an arbitrary partial function $f : \Sigma^{\ast} \to \Sigma^{\ast}$ is called *computable* iff $f = f\_M$ for some Turing machine $M$.

Then we define a language $A \subseteq \Sigma^{\ast}$ to be recursively enumerable iff it is the domain of some computable function. Clearly with the above definition $\operatorname{dom}(f\_M) = \\{ w \in \Sigma^{\ast} \mid \mbox{The machine halts on input $w$.} \\}$, i.e. this is equivalent to say that a language is recursively enumerable iff we can find a machine that halts exactly for the words in the language.

But on other sources I found the following definition, a language $A \subseteq \Sigma^{\ast}$ is recursively enumerable, iff there exists a Turing machine such that $$ A = \\{ w \in \Sigma^{\ast} \mid \mbox{The machine halts in an accepting state} \\} $$ or $$ A = \\{ w \in \Sigma^{\ast} \mid \mbox{The machine halts and outputs a specified output } \\}. $$ Both notions, by special state or special output, are clearly equivalent. But they do not require the machine to run forever if $w \notin A$. This could be fixed, by letting the machine enter an endless loop if it enters a non-accepting state after finishing its computation. But this seems quite unnatural to me.

But I think a better definition, more closely at the definition by acceptance states or special output, in terms of computable functions, would be to call a language $A$ recursively enumerable iff there exists a computable partial function $f : \Sigma^{\ast} \to \Sigma^{\ast}$ such that $A = f^{-1}(B)$ for some $B \subseteq \Sigma^{\ast}$.

Surely with the above definition we can enlarge $B$ always by values not in the range of $f$, so $B$ is not unique, but it would be no problem that the machine halts on some other input $\notin B$ and we would have $A \subseteq \operatorname{dom}(f)$.

So is this definition used anywhere, does it make sense? I could not find it, so I am asking here. Also nobody discusses the two definitions together, either in books they always work with Turing machines, or they work with primitive and $\mu$-recursive functions.

# Answer
Your definition makes no sense because according to it every language is recursively enumerable. Given any $C \subseteq \Sigma^\*$, take $B = C$ and $f(x) = x$, the identity function, which is computable. Then $f^{-1}(C) = C$, therefore $C$ is recursively enumerable.

We can fix your definition by observing that the following theorem holds:

> **Theorem:** A language $A$ is recursively enumerable if, and only if, there is a partial computable $f$ and a *recursive* set $B$ such that $A = f^{-1}(B)$.

You are close to reinventing the notion of many-one reduction, by the way.
> 3 votes

---
Tags: computability, turing-machines, terminology
---


title: Prove REGULAR_TM is undecidable

text:
# Question
Title: Prove REGULAR_TM is undecidable
I am studying the proof of the following theorem:

Given the language

$\mathit{REGULAR}\_\mathit{TM} = \\{\langle M \rangle | M $ is a turing machine and $\mathit{Accept}(M)$ is regular$\\}$

$\mathit{REGULAR}\_\mathit{TM}$ is undecidable.

---

The proof given in Sipser shows that if we already have a machine $R$ that decides $\mathit{REGULAR}\_\mathit{TM}$ then we can make a machine $S$ that decides the halting problem:

$$\mathit{Accept}\_\mathit{TM} = \\{\langle M, w \rangle | M \mbox{ is a turing machine and }w \in \mathit{Accept}(M) \\}$$

I am having trouble understanding the proof. Here's how I understand it:

When $M$ (any turing machine) and $w$ (any string) is fed to the machine $S$, we construct a machine $M\_2$ that takes a string $x$ as input, but first runs machine $M$ on $w$. First case, if $w$ $\in $$\mathit{Accept}(M)$, then $M\_2$ simply accepts x. That is $\mathit{Accept}(M\_2) = \sum^\*$ in this case - i.e a regular language. Otherwise, second case, $M$ rejects $w$, then $M\_2$ checks if the input $x$ is of the form $0^n1^n$, and accepts if it is so - i.e $ \mathit{Accept}(M\_2) $ is not a regular language. Inside $S$, for both these cases if we run $R$ on $M\_2$ returns the appropriate result which $S$ can directly return.

The case I am confused about, the third case, is when $M$ does not halt on $w$. Then $\mathit{Accept}(M\_2) = \\{\\}$, which is a regular language, and $R$ will therefore return *ACCEPT*, which $S$ cannot directly return as $w \notin \mathit{Accept}(M)$. But the description of the solution sounds to me like $S$ returns *ACCEPT* even in this case(pseudocode below). So what am I doing wrong? There's probably a very basic idea I am missing. Here's the pseudo-code for the machine $S$, and inside $S$, as you can see, there's the machine $M\_2$ that $S$ creates.

```
machine S(M, w):
    // Construct an instance of machine M2 which uses M and w
    machine M2(x):
        r := M(w)  // Might hang here
        if r == ACCEPT:
            return ACCEPT
        else:
            if x is of form 0^n.1^n:
                return ACCEPT
            else:
                return REJECT

    // Run R on M2 (always returns, never hangs)
    r1 = R(M2)
    if r1 == ACCEPT:
        return ACCEPT
    else:
        return REJECT

```

# Answer
Look up Rice's teorem. Its proof is quite short and sweet. It says that any non-trivial property of a TM language (i.e., one that not all TM languages share) is undecidable, in the sense that it can't be decided *by looking at the TM* if the language it accepts has the property.

The property of being regular (or a context free language, or the empty language, or the language of all strings, or...) is non-trivial, so if a particular TM accepts a language with the property is undecidable, by Rice's theorem.
> 4 votes

# Answer
Your pseudocode is wrong, the following is the correct one:

```
machine S(M, w):
    // Construct an instance of machine M2 which uses M and w
    machine M2(x):
        if x is of form 0^n.1^n:
            return ACCEPT
        else:
            r := M(w) // If LOOP, M2 accept 0^n.1^n
            if r == ACCEPT:
                return ACCEPT // M2 accept Sigma* (Only this case make M2 accept regular language if only if M(w) accept)
            else if r == REJECT:
                return REJECT // M2 accept 0^n.1^n

    // Run R on M2 (always returns, never hangs)
    r1 = R(M2)
    if r1 == ACCEPT:
        return ACCEPT
    else:
        return REJECT

```

@David Richerby Here is more explanation:

1. vonbrand is right
He used Rice's teorem, it says that any non-trivial property of a TM language is undecidable. That's OK, but...in Sipser's book, this example is to demonstrate Mapping Reducibility.
So we should use reduction to resove this problem instead of Rice's teorem.
2. What is wrong with the proposed answer?
The wrong is:
When M(w) LOOP in M2, R(M2) will return ACCEPT. Why? Because in this case L(M2) is {}, which is a regular language.But when M(w) LOOP, R(M2) must not return ACCEPT.
Imagine:
If R(M2) return ACCEPT, What will happen?
There will be two possibilities for M2 to make R(M2) accept.
(1)M(w) return ACCEPT.
(2)M(w) LOOP.
Obviously,"two possibilities" does not meet the definition of Reduction.
What is the definition of Reduction?

Please note \<=\>, that is "if only if".
3. What does my answer do to correct it?
The key thing is: There is only one possibility to for M2 to make R(M2) accept, that is M(w) return ACCEPT! That meet the definition of Reduction.
4. Another solution for this problem:

```
machine S(M, w):
    // Construct an instance of machine M2 which uses M and w
    machine M2(x):
        r := M(w)
        if r == ACCEPT:
            if x is of form 0^n.1^n:
                return ACCEPT
            else:
                return REJECT
        else if r == REJECT:
            return REJECT

    // Run R on M2 (always returns, never hangs)
    r1 = ComplementOfR(M2) // use Complement Of R
    if r1 == ACCEPT:
        return REJECT
    else:
        return ACCEPT

```

In this solution, I use ComplementOfR instead of R.
The benefits of this is:
Now, in M2 we can run M on w first.
Why we can use ComplementOfR?
If R is decidable, then ComplementOfR is also decidable. Thus we can use ComplementOfR.
> 1 votes

---
Tags: computability, turing-machines, undecidability
---


# Question
Title: How to prove that a language is not recursively enumerable
How does one prove that some arbitrary language $L$ is **not** recursively enumerable?

I know I can prove that the language $L$ is recursively enumerable by constructing a Turing machine $M$ that accepts all words in the language (and the language would be even recursive if $M$ halts on all inputs).

But it is not clear to me how to prove that language in not RE. I was thinking about showing the fact, that such TM could not be constructed for a given language, but proving non-existence is always difficult.

# Answer
> 10 votes
Here are two methods.

# Consider the complement

**Theorem.** If a language $L$ and its complement are both RE, they are both recursive.

*Proof.* Decide whether $w\in L$ by enumerating $L$ and its complement in parallel and accept/reject as soon as $w$ appears in one of the enumerations. $\Box$

So, if you can prove that $L$ is not recursive but its complement is RE, then $L$ is not RE.

# Halting problems

**Theorem.** Let $\mathcal{M}$ be the class of Turing machines equipped with an oracle for the ordinary Turing machine halting problem. The halting problem for $\mathcal{M}$ is not RE.

*Proof.* Essentially the same as the proof that the ordinary Turing machine halting problem is not recursive. $\Box$

So, if you can reduce the halting problem for $\mathcal{M}$ to your problem, your problem is not RE.

# Answer
> 4 votes
Some common techniques include:

We start by picking any $L'$ which is known to be non RE, e.g. we let $L'$ to be the complement of the halting problem. Then we prove the m-reduction $L' \leq\_m L$. If we can do that, we can conclude that $L$ is not RE, since otherwise $L'$ would be RE -- contradiction.

The Rice-Shapiro theorem is a very convenient and widely applicable method to establish "non-RE" properties. It is not a silver bullet which always applies, but many common languages are covered by it.

---
Tags: computability, proof-techniques, semi-decidability
---


title: Streaming parsing algorithms

text:
# Question
Title: Streaming parsing algorithms
A *parser* is a procedure which decides if an input belongs to a certain language and produces a witness in the form of a parse tree.

Let a *streaming parser* be a parser which for any prefix $u$ can produce a *partial* parse tree corresponding to the productions that *must* be expanded to eventually accept any completion $uv$ of the prefix, for some completion $v$.

For example, if parsing the CFG $$ \begin{array}{lcl} S &\to& (a S+ b) \end{array} $$

then upon reading the prefix $aaa$, the streaming parser should report that any parse tree must consist of three top-level expansions of $S$.

**Edit**: I have two motivations for streaming parsing. The first is to provide a best-case constant bound on memory usage in the case where productions can always be resolved by a constant amount of lookahead. The second is to allow the consumer to lazily tear down the parse tree as the result is produced, e.g. by scheduling the execution of semantic actions associated with productions.

I am also interested in streaming parsing based on other foundations than context-free grammars, such as top-down parsing (parsing expression grammars, parser combinators, etc.).

Is there any existing work on such parsing algorithms?

# Answer
I believe that the LR(k) property corresponds to your notion of a grammar which can be parsed in a streaming fashion. It's probably useful to (re)read Donald Knuth's 1965 paper On the Translation of Languages from Left to Right. In that paper, Knuth defines the LR(k) property in terms of the construction of the parse tree; a grammar is LR(k) iff "any handle is always uniquely determined by the string to its left and the $k$ terminal characters to its right." (p. 610) He then proves that every language recognizable by a deterministic push-down automaton is LR(1).

In effect, the stack in an LR(k) parser is essentially the lower-left corner of the final parse tree, which is one way to understand the phrase "the tree starts with". An LR(k) parser's stack will reflect the parser of all but the last $k$ symbols read, so unless $k$ is 0, which would considerably limit the possible languages, the prefix read will be slightly longer than the corresponding parse stack. But that doesn't seem to be excluded by the form of your question.

Unfortunately, it is not decidable whether a particular *language* is LR(k). It is easy enough to figure out if a particular CFG is LR(k) for some given $k$, but I don't believe there is any way to find such a $k$ for a given CFG other than trying all possible values in sequence.

At the end of the paper, Knuth proposes a possible generalization ($LR(k,t)$) in which the $t$th last handle of every parse tree fragment is uniquely-determined (so that $LR(k)$ is $LR(k,1)$). This might still fall into your idea of possible streaming parsers, although it no longer is able to stream in a strictly bounded context. He gives an example of a language which is not $LR(k,1)$ for any $k$ but is $LR(0,2)$; however, he does not propose any algorithm for constructing an $LR(k,t)$ parser for $t\ne 1$.

Given an arbitrary CFG, you can use Tomita's Generalized LR (GLR) parsing algorithm, which, if implemented correctly, will produce all possible parses for a given string in $O(n^3)$ time and space. The GLR parser maintains a data structure from which all viable parse stacks can be derived; in particular, it is easy to find the longest prefix which corresponds to an unambiguous parse stack. However, there is no guarantee that all the parse stacks at a particular point in the parse (before the end) are actually viable; only that all viable stacks are included. So it is possible that there is a longer unambiguous prefix. A Tomita parser would correctly find the longest prefix for Knuth's $LR(0,2)$ example, but I don't know if that result could be generalized.
> 2 votes

# Answer
The first solution coming to mind is an extension of Brzozowski's derivatives as context-free grammars are closed under derivative operation with respect to a letter.

Here that question answered: https://cstheory.stackexchange.com/questions/3280/generalizations-of-brzozowskis-method-of-derivatives-of-regular-expressions-to
> 2 votes

# Answer
As mentioned above LL would allow streaming out of box, since it would have to report the top of the parse tree with all non-terminals before reporting any terminal symbol that is coming from the text being parsed. Like in your example:

# S→ aS + b

Upon reading first 'a' from input string 'aaa' it would have to say first that it is start of rule (non-terminal) S, something like:

* S begins
* a

Now, what if terminal 'a' can appear as beginning of more than one rule reachable from the top? That would require parser to postpone output and read more before the only one possible match found. That requires some lookahead that can be fixed like LL(1) or LL(2) or adaptive like LL(\*) that ANTLR parser generator is using.

LR parser, on the other hand, doesn't tell top of the parse tree first, but kind of does it in reverse order. It first reports terminals and then says what rule (non-terminal) was that. Advantage is that parser can see more tokens before it has to decide what rule that was.

As it turns out, it is also possible to do streaming with LR parser and turn output to that of LL parser, but with advantage of stronger LR parser for the same lookahead than LL. That would mean that parser has to postpone output until place of current subtree is fixed in the parse tree. I was able to make such parser for parsing EDI text documents, like EDIFACT, HL7 and so on. Basically, I precalculated during parse table construction which rule is referenced where and when it is safe to report the beginning of such rule. And extended stack data to hold additional flag if terminal or non-terminal was already reported and also to keep subtrees of folded rules if they were not yet reported.

I didn't find any paper or book that would discuss that anywhere. There could be some neat way to do that with minimum overhead. Overhead that would best happen during parsing table construction once, and keep the parser driver fast. I was able to find two ways of doing it, and then kept the one that does more work at parser table generation. And it is streaming very nicely! From this point of view LR and LL are not so different. I would say that for a nice grammar modified LR(k) with this addition is similar to LL(\*). Both would cache and postpone output if not enough input has been seen to decide what it is. Implementation-wise, one of them is easier than another. Where LL(\*) would use backtracking, in modified LR(k) partial parse trees are just cached before output.
> 1 votes

---
Tags: algorithms, reference-request, parsers, streaming-algorithm
---


# Question
Title: Linear Regression. Why do we take sum of errors to compute the cost?
While calculating the cost in linear regression (for either with multiple features or a single one using gradient descent) we compute the cost by squaring and summing up the cost related to each training set. What is the point of summing up the cost related to each training example is what I do not understand. Why not just calculate the cost for each training example individually ?

( I am following the Machine Learning course taught by Andrew Ng on coursera. )

# Answer
You can usually view the cost function as the average squared error over some dataset with $N$ pairs of data, thus being defined as:

\begin{align} J &= \frac{1}{N} \sum\_{i=1}^{N} \left(f(x\_i,\beta) - y\_i \right)^2 \end{align}

We want the average error of our model (for all data we have) to decrease as we fine tune values for $\beta$, the vector parametrically defining how our model $f(\cdot,\cdot)$ works. So we like to look at all the data at once since it can be used to make changes to $\beta$ that should actually make the model improve as a whole.

If we instead made the cost function based on a subset of the dataset, you would end up with a cost function that may sub-optimally modify the value for $\beta$. This sub-optimal behavior may make us take longer to get to a local minimum of the cost function or even diverge from a good solution if you aren't careful with your hyper parameters.

Stochastic gradient descent or mini-batch gradient descent are methods that use a single piece of data or a subset of data from the dataset to make adjustments. These methods have actually found use for really large datasets where the longer convergence time is more worthwhile than the time it takes to do a whole pass on the data to compute necessary gradients and costs.
> 3 votes

---
Tags: algorithms, machine-learning
---


title: Recursive algorithm - a^(2^n)

text:
# Question
Title: Recursive algorithm - a^(2^n)
The `a^n` was pretty easy:

```
function powN(a, n) {
    if(n == 0) return 1;
    return a * powN(a, n - 1);
};

```

But somehow I got stuck on `a^(2^n)`, any suggestions or even a hint?

I need a recursive algorithm that solves: `a^(2^n)`.

# Answer
Let's look at how many multiplications are necessary to perform $a^{16}$ by your recursive method:

$$a \xrightarrow{SQR} a^2 \xrightarrow{MUL} a^3 \xrightarrow{MUL} \ldots \xrightarrow{MUL} a^{14} \xrightarrow{MUL} a^{15} \xrightarrow{MUL} a^{16}$$

Where:

$SQR$ = Squares a number

$MUL$ = Usual Multiplication

So as Yuval pointed out in the comments, even a small power of $2$ would require $\Theta(n)$ multiplications, which means this would be too slow for practical use.

However, you can the same thing using only $SQR$ with $\Theta(\log{n})$ operations. That is:

$$a \xrightarrow{SQR} a^2 \xrightarrow{SQR} a^4 \xrightarrow{SQR} a^8 \xrightarrow{SQR} a^{16}$$

Of course, since $16$ is a power of $2$ we only need to use $SQR$. But you can alternate between $SQR$ and $MUL$. This is the principle behind Exponentiation by Squaring.

Example:Computing $a^{19}$.

$$a \xrightarrow{SQR} a^2 \xrightarrow{SQR} a^4 \xrightarrow{SQR} a^8 \xrightarrow{MUL} a^{9} \xrightarrow{SQR} a^{18} \xrightarrow{MUL} a^{19} $$
> 1 votes

# Answer
We have $a^{2^n}$ = $a^{2·2^{n-1}}$ = $(a^2)^{2^{n-1}}$. Therefore

```
function pow2powN(a, n) {
    if(n == 0) return a;
    return pow2powN(a*a, n - 1);
};

```

If you use floating-point arithmetic, this runs in O(n). To avoid confusion, for example n = 10 would calculate $a^{1024}$. If you use integer arithmetic, then this will overflow for many values but run in O (n). If you use multi-precision arithmetic where the time grows with the sizes of the numbers, the time is basically the time for the last squaring.
> 0 votes

---
Tags: algorithms, recursion
---


title: NFA to DFA accepting states

text:
# Question
Title: NFA to DFA accepting states
I was working through an NFA to DFA conversion tutorial: where I'm converting the following NFA to a DFA:
I used lazy subset construction which I'm sure the tutorial did as well because we had the same transition table of:

```
delta      |  0        |  1       |
===========+===========+==========+
{a}        |{a,b,c,d,e}|{d,e}
{a,b,c,d,e}|{a,b,c,d,e}|{b,d,e}
{d,e}      |{e}        |{∅}
{b,d,e}    |{c,e}      |{e}
{e}        |{∅}        |{∅}
{c,e}      |{∅}        |{b}
{b}        |{c}        |{e}
{c}        |{∅}        |{b}

```

However, there state diagram for the resulting DFA is this:

I'm confused as to why the set {b,d,e} isn't being labeled as an accepting state.

Also, I don't know if I'm allowed to ask this but if there is a place with more NFA to DFA converting practice I'd love to know, right now I'm just using any old study guide I can find on google.

# Answer
You're right, {b, d, e} should be a final state. Otherwise the DFA would reject 0001 while the "equivalent" NFA accepts it.
> 1 votes

---
Tags: finite-automata
---


title: What is the Pumping Lemma a lemma to?

text:
# Question
Title: What is the Pumping Lemma a lemma to?
This is something I couldn't find - but I always found it interesting that the pumping lemma is just a lemma (especially since it has the same name for regular languages, context free languages, etc...)

What is it a lemma to?

# Answer
> 10 votes
In the foundational paper of Rabin and Scott, Finite automata and their decision problems, the pumping lemma appears as a lemma (Lemma 8) to the following result (Theorem 9):

> The language accepted by an $n$-state DFA is infinite if and only if it accepts some word whose length lies between $n$ and $2n$.

The pumping lemma implies the $\Longrightarrow$ direction.

It also "gives another proof" that the language $\\{0^n 1 0^n : n \geq 0\\}$ isn't regular (the original proof in the paper uses Myhill-Nerode theory).

---
Tags: complexity-theory, regular-languages, finite-automata
---


# Question
Title: Difference between $\beta$-contracts and $\beta$-reduces in Hindley
I brought the book *Lambda-Calculus and Combinators: An Introduction* by J. Roger Hindley and the author explains what is $\beta$-reduction.

Now there is a difference between $\beta$-contracts and $\beta$-reduces: $$ \begin{align\*} P &\rhd\_{1\beta} P^\prime\\ P &\rhd\_{\beta} P^\prime \end{align\*} $$

Could someone please explain me what is the difference?

# Answer
> 5 votes
Notation and terminology varies a little between authors, so you should check the definitions used by the author. When you ask such questions, you should quote the definitions.

The expression “$P$ $\beta$-contracts to $P'$” means that $P$ contains a subterm which is an application and $P'$ is the result of substituting the argument into the abstraction body. That is, there exist $C$, $M$, $N$ and $x$ such that $P = C\[(\lambda x.M) \\, N\]$ and $P' = C\[\[N/x\] M\]$ where $\[N/x\] M$ means the term obtained by substituting $N$ for $x$ in $M$ and $C\[\cdot\]$ is a term with a hole. Thus

* All terms of the form $(\lambda x.M) \\, N \triangleright\_{1,\beta} \[N/x\] M$ are $\beta$-contractions at the top of the term.
* If $P \triangleright\_{1,\beta} P'$ then $M \\, P \triangleright\_{1,\beta} M \\, P'$ and $P \\, M \triangleright\_{1,\beta} P' \\, M$ and $\lambda x. P \triangleright\_{1,\beta} \lambda x. P'$. The contraction is sometimes said to happen “in a context”.

The expression “$P$ $\beta$-reduces to $P'$” means that there is a chain of $\beta$-contractions that goes from $P$ to $P'$. For example:

* For any term, $P \triangleright\_{\beta} P$ (a term reduces to itself in zero steps).
* If $P \triangleright\_{1,\beta} P'$ then $P \triangleright\_{\beta} P'$: a contraction is a reduction in one step.
* If $P \triangleright\_{1,\beta} P'$ and $P \triangleright\_{1,\beta} P'$ then $P' \triangleright\_{\beta} P''$: a contraction in two steps.
* etc.

In a nutshell, a beta contraction is one step, a beta reduction is any number of steps. Note that some authors use different terminology and might call one step a beta reduction and many steps “a chain of beta reductions” or “a $\beta^\*$ reduction”.

---
Tags: lambda-calculus
---


# Question
Title: Given language consisting Turing machines is decidable or not?
$$L=\\{M\mid \text{there exist }x,y\in\Sigma^\* \text{ s.t. }x \in L(M)\text{ and } y \notin L(M)\\}\\,.$$

I think it's not recursively enumerable because this language reduces to complement of the membership problem. $\langle M,w\rangle$ would be input where $y$ would become $w$ and $x$ belongs to $L(M)$.

Please tell me whether I'm correct or not, and help to solve if I'm wrong.

# Answer
In other words, $L=\\{\langle M \rangle:L(M)\notin \\{\phi,\Sigma^\*\\}\\}$. you can show explicit reduction from a language you already know is not in $RE$. for example $\overline{HP}$ (it is a very standard reduction). or you may use the rice theorem to show that.

I did not understand the reduction you suggested. The reduction from the language you suggested could be as follows: $$f(\langle M \rangle,x)=\langle M\_x \rangle$$

$M\_x$ on input w:

1. run $M$ on x for |w| steps.
2. if $M$ accepted then reject, otherwise accept.

Note that $\epsilon \in L(M\_x)$ in anycase, so $L(M\_x)\neq \phi$. and $L(M\_x)\neq\Sigma^{\*}\iff x\in L(M)$. the correctness follows.
> 3 votes

---
Tags: computability, turing-machines, reductions, undecidability, semi-decidability
---


# Question
Title: If 3SAT reduces to its complement then PH=NP
In Chapter 5 of the Arora–Barak complexity theory textbook we are asked to prove the following statement:

> If 3SAT is polynomial-time reducible to its complement then PH=NP. How do I prove this statement?

# Answer
> 3 votes
Show that in that case $\text{NP=coNP}$ which means $\Sigma^p\_1=\Pi\_1^p$, so the hierarchy collapse to the first level.

# Answer
> 2 votes
Here is the sketch for proving this: Suppose that $\mathsf{3SAT}$ is closed under its complement under polynomial-time reductions. Since $\mathsf{3SAT}$ is an $\mathsf{NP}$-complete problem, this implies that $\mathsf{NP}$ is also closed under complement, i.e. $\mathsf{\Sigma\_n^p}=\mathsf{\Pi\_n^p}$ where $n =1$. For $n \geq 1$, and $\mathsf{\Sigma\_n^p}$, define $n$ non-deterministic Turing machines $\mathcal{M\_1} \ldots \mathcal{M\_n}$ each of which is in one-to-one correspondence with the respective oracles of $\mathsf{\Sigma\_n^p}$. Define a non-deterministic Turing machine $\mathcal{M}$, as the concatenation of $\mathcal{M\_1} \ldots \mathcal{M\_n}$. Finally, prove that $\mathsf{\Sigma\_n^p}$ answers yes iff $\mathcal{M}$ does so.

Some insights on why this works: The power of the polynomial hierarchy comes from the fact that one can negate the answer obtained from the oracle. Of course, if $\mathsf{NP}$ is already closed under complement, then one can simply concatenate polynomially many non-deterministic Turing machines and obtain the same computational power with a single non-deterministc Turing machine, which in turn implies that the polynomial hierarchy collapses to the first level.

---
Tags: np-complete
---