# Question
Title: Winning strategy using Dynamic Programing
Let $G=(V,E)$ be a DAG and let $v\_0\in V$. Alice and Bob are playing a game in which every player has his own turn and Bob is starting. In every turn $i$, the player is picking an edge $e=(v\_i,x)$, then $x$ become $v\_{i+1}$ and then it becomes the other player's turn. The player which doesn't have an edge to choose (the vertex $v\_i$ has no out edges) is losing.

Propose an algorithm which determines if Bob has a winning strategy.

# Answer
> 2 votes
For a vertex $v \in V$, let $W(v)$ be the following predicate: "a player starting at $v$ wins". If $N(v)$ is the set of outward neighbors of $v$, then $$ W(v) = \bigvee\_{u \in N(v)} \lnot W(u), $$ where the empty disjunction is simply false.

This suggests a strategy to compute $W(v\_0)$ using dynamic programming.

---
Tags: graphs, dynamic-programming
---


# Question
Title: Any book for learning to correctly find out complexity of one's algorithm?
Suppose we have designed an Algorithm and we want to find out its complexity. I am looking for a book which mainly focuses on finding out complexity of algorithms rather than introducing me to different search, sort, and ... algorithms.

# Answer
Simply pick up any algorithms book out there, they will all take you through these things. What you are describing is essentially the algorithms (and computational complexity) field.

The most popular books are *Algorithms* by Sedgewick and Wayne, which is free for download, the CLRS Introduction to Algorithms, and the epic Art of Computer Programming by Knuth.
> 2 votes

---
Tags: reference-request
---


# Question
Title: Problems that provably require quadratic time
I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$.

The problem needs to have the following properties:

1. $\Omega(n^2)$ runtime proof for any algorithm - first priority is to have as simple as possible lower bound argument.
2. $O(n^2)$ algorithm, if possible, simple one as well.
3. Output size of $O(n)$ (or smaller). Obviously any problem which requires $\Omega(n^2)$ lengthed output required at least similar run time, but that's not what I'm looking for. Notice that any decision problem fits here.
4. (if possible) a "natural" problem. Without a formal definition, a problem any CS graduate would recognize is preferable.

---

I was recently asked about such problem but couldn't come up with a simple one. The first problem that came to mind was $3SUM$, which was *conjuctured* to be a $\Omega(n^2)$ runtime problem. This was not simple enough and furthermore, the conjucture was recently proven false :o.

Going to an extremely unnatural problem, I believe that the problem that gets as an input a deterministic TM and input $\langle M \rangle,x$, and outputs the position of the tape head after $(|M|+|x|)^2$ steps when it's running on $x$ probably answers the question.

---

If you absolutely need to, lets agree that we're using the single-tape TM model, although I prefer problems whose runtime is independent on the exact model (as long as it's a reasonable one).

---

So, can we find a *simple* (to prove), *natural* (well known) problem whose runtime is $\Theta(n^2)$?

# Answer
Finding an envy-free cake-cutting requires $\Omega(n^2)$ queries. However, this does not directly answer your question as the computational model is different than a Turing machine.

By the way, currently the quickest known algorithm for this problem requires $n^{n^{n^{n^{n^{n}}}}}$ queries, so there is a huge gap from the lower bound - probably one of the largest gaps in computer science.
> 9 votes

# Answer
As in the link provided by Raphael, Peter shows that Input Reversal requires $\Theta(n^2)$ time on vanilla single-tape TMs. For a decision problem, the language $$L = \\{x0^{|x|}x \mid x \in \\{0,1\\}^\ast \\}$$ also *provably* needs $\Theta(n^2)$ time to compute. To see this, use Peter's communication complexity argument , along with a classical result that $EQ\_n$ needs $\Theta(n)$ bits of communication, to show the quadratic lower bound of $L$. The similar approach works for a more natural one $L = \\{xx \mid x \in \\{0,1\\}^\ast \\}$.

By the way, it is worth mentioning that the "crossing sequence method" mentioned by Yuval is (to my best knowledge) mathematically equivalent (or, maybe, inforior) to the communication complexity one.

---

For another candidate that does not directly answer your question, Ryan Williams proved that $\mathsf{SAT}$ cannot be decided in $O(n^{2 \cos(\pi/7)})$ time *and simultaneously* $n^{o(1)}$ space on RAMs. While the constant $2 \cos(\pi/7) \approx 1.8$ seems quite magical, the initial idea that comes from Fortnow, is ingenious but not so involved. Refer to page 101 in the textbook of Barak and Arora for an exposition of the idea.
> 2 votes

---
Tags: complexity-theory, turing-machines, time-complexity, lower-bounds
---


# Question
Title: How to find the Big-O for finding combinations of balanced parentheses?
Given `n` pairs of parentheses, a function which returns the total number of all combinations *well-formed* parentheses could be:

```
def count_parenthesis(n, opened, closed):
  if closed == n:
    return 1

  num_pairs = 0

  if opened < n:
    num_pairs += _count_parenthesis(n, opened + 1, closed)

  if opened > closed:
    num_pairs += _count_parenthesis(n, opened, closed + 1)

  return num_pairs

```

Calling `count_parentheses(3, 0, 0)` results in the following call tree:

```
count_parenthesis(2, 0, 0)
  count_parenthesis(2, 1, 0)
    count_parenthesis(2, 1, 1)
      count_parenthesis(2, 2, 1)
        count_parenthesis(2, 2, 2)
  count_parenthesis(2, 2, 0)
    count_parenthesis(2, 2, 1)
      count_parenthesis(2, 2, 2)

```

**How can the time and space complexity of this algorithm be determined?**

There are a few areas which I'm unsure how to handle:

* The variable that moves towards the base case (`closed == n`) does not get incremented every time.

+ Calls where a brace is opened (`opened + 1`) do not directly move towards the base case.
* There isn't an obvious relationship (IMO) between `n` and the number of well-formed combinations:

```
n = 3, f(n) = 5
n = 4, f(n) = 14
n = 5, f(n) = 42
n = 6, f(n) = 132
n = 7, f(n) = 429
n = 8, f(n) = 1430

```
* I'm unsure how a recurrence relation can be defined when the base-case is not 1 or 0, but `n`?
* Should I approximate based on well-known runtime complexities? I.e. this *looks* like either exponential or factorial.

Note: I'm not looking for just an answer. I'd like to understand the process finding the time/space complexity for this type of recursive algorithm.

# Answer
> 1 votes
Let us start by analyzing the recursion tree of your algorithm. The depth is $2n$. As for the number of nodes, at level $k$ you have all arrangements of $a$ left parentheses and $k-a$ right parentheses such that $a \leq n$ and in each prefix of the word, there are at least as many left parentheses as right parentheses.

Bertrand's formula states that for each $a$, the number of such arrangements is $$ \frac{(a+1)-(k-a)}{k+1} \binom{k+1}{a+1} = \binom{k}{a} - \binom{k}{a+1}. $$ Hence the number of nodes at level $k$ is $$ \sum\_{\lceil k/2 \rceil \leq a \leq \min(k,n)} \left\[\binom{k}{a} - \binom{k}{a+1}\right\] = \binom{k}{\lceil k/2 \rceil} - \binom{k}{\min(k,n)+1}. $$ Summing this for $k$ from $0$ to $2n$, we obtain $$ \sum\_{k=0}^n \binom{k}{\lceil k/2 \rceil} + \sum\_{k=n+1}^{2n} \left\[\binom{k}{\lceil k/2 \rceil} - \binom{k}{n+1}\right\]. $$ It follows from Stirling's approximation that this is $O(4^n/\sqrt{n})$, and conversely, just considering $k = 2n$ (corresponding to Catalan numbers), this is $\Omega(4^n/n^{1.5})$.

We are however not done, since the numbers involves are quite large — on the order of $n$ bits. Therefore arithmetic takes super-constant time. We still get a running time of $\tilde{O}(4^n)$.

Now for space complexity. The recursion tree is $n$ levels deep, and at each level we might be storing up to $n$ bits of information, giving an upper bound of $O(n^2)$ bits. This should be quite tight.

---
Tags: time-complexity, recursion, counting
---


# Question
Title: Why isn't the search space size of TSP $(n-1)!$ instead of $n!$?
I'm just learning about the travelling salesman problem, and I've been playing around with it. I'm not sure if what I've found is just a special case or not. My professor says the search space size is $n!$, where $n$ is the number of cities.

Suppose we have a table with cities $A,B,C,D$ on each axis, and the elements represent the distances between cities:

\begin{array}{|c|c|c|c|} \hline & A & B & C & D \\ \hline A&0 & 2& 3&4\\ \hline B& 2 & 0& 10&5\\ \hline C& 3 &10 &0 &15\\ \hline D& 4 & 5& 15&0\\ \hline \end{array}

From this, I can generate various permutations of possible tours, and their lengths: $$A \to B \to C \to D \to A : 31$$ $$A \to B \to D \to C \to A : 25$$ $$A \to C \to B \to D \to A : 22$$ $$A \to C \to D \to B \to A : 25$$ $$A \to D \to B \to C \to A : 22$$ $$A \to D \to C \to B \to A : 31$$

Now, it seems to me that each of these permutations is cyclical. In this way, $B \to C \to D \to A \to B : 31 $ and $A \to B \to C \to D \to A : 31$ are equivalent, for example.

So in fact, it doesn't matter which city I choose initially, because the resulting shortest tour will be equivalent to one of the tours above.

And clearly, there are $3!$ of these tours, or $(n-1)!$ of them. So why isn't the search space size $(n-1)!$ instead of $n!$? Maybe there is a problem with my understanding of what search space size is, I'm not sure.

# Answer
The search space has size $(n-1)!$. You can see this in many ways, for example:

1. Each tour corresponds to $n$ different permutations, depending on the starting point.
2. If we start describing the tour at some point $P$ fixed ahead of time, then the tour is given (injectively) by an arbtirary permutation of the remaining $n-1$ points.

The reason that sometimes $n!$ is used is that $n!$ is shorter, and the difference between $n!$ and $(n-1)!$ is not always important.
> 3 votes

---
Tags: traveling-salesman
---


# Question
Title: Is F(F(s,x), x) necessarily a PRF if F is?
Given a PRF - F, is $G\_s(x)=F\_{F\_s(x)}(x)$ necessarily a PRF?

First I thought how to tackle this problem. First I tried using a hybrid argument: $|\mathbb P\[F\_{F\_s(x)}(x)\] -\mathbb P\[f(x)\]|\leq |\mathbb P\[F\_{F\_s(x)}(x)\] -\mathbb P\[F\_{f(x)}(x)\]| + |\mathbb P\[F\_{f(x)}(x)\] -\mathbb P\[f(x)\]|$ so I can contradict the possibility that the first part of the is not negligible but the second part of the sum is problematic. Then I tried to think of counter examples. But it seems to me that because I dont know what the key of F will be if I could break G then I could break F with one single query.. So i'm pretty stuck and would appreciate help.

# Answer
> 3 votes
Let $\mathrm{RF}\_n$ be the set of random functions over $\\{0,1\\}^n$. Let $F\_{f,i}$ be an oracle that answers the first $i$ queries with $F\_{f(\cdot)}(\cdot)$ and answers the remaining queries with $f(\cdot)$. Now suppose a polynomial-time distinguisher $D$ can distinguish $\\{f\leftarrow \mathrm{RF}\_n:F\_{f(\cdot)}(\cdot)\\}$ and $\\{f\leftarrow \mathrm{RF}\_n:f(\cdot)\\}$, it can also distinguish $\\{f\leftarrow \mathrm{RF}\_n:F\_{f,k-1}(\cdot)\\}$ and $\\{f\leftarrow \mathrm{RF}\_n:F\_{f,k}(\cdot)\\}$ for some $k$.

Now construct a new distinguisher $D'$. Given an oracle $\mathcal{O}(\cdot)$, it selects a random function $f$, then calls $D$. Each time $D$ gives a query $x$ (suppose it is the $i$th query), $D'$ returns

* $F\_{f(x)}(x)$ if $i\<k$, or
* $\mathcal{O}(x)$ if $i=k$, or
* $f(x)$ if $i\>k$.

We can see if $\mathcal{O}$ is $\\{f\leftarrow \mathrm{RF}\_n:f(\cdot)\\}$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $\\{f\leftarrow \mathrm{RF}\_n:F\_{f,k}(\cdot)\\}$. If $\mathcal{O}$ is $\\{s\leftarrow\\{0,1\\}^n:F\_s(\cdot)\\}$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $\\{f\leftarrow \mathrm{RF}\_n:F\_{f,k-1}(\cdot)\\}$. Since $D$ can distinguish $\\{f\leftarrow \mathrm{RF}\_n:F\_{f,k-1}(\cdot)\\}$ and $\\{f\leftarrow \mathrm{RF}\_n:F\_{f,k}(\cdot)\\}$, our distinguisher $D'$ can distinguish $\\{f\leftarrow \mathrm{RF}\_n:f(\cdot)\\}$ and $\\{s\leftarrow\\{0,1\\}^n:F\_s\\}$, which contradicts to the fact that $F$ is a PRF.

So $\\{f\leftarrow \mathrm{RF}\_n:F\_{f(\cdot)}(\cdot)\\}$ and $\\{f\leftarrow \mathrm{RF}\_n:f(\cdot)\\}$ cannot be distinguished by any polynomial-time distinguisher. Your second part of the sum is negligible.

---
Tags: cryptography
---


title: numerically stable log1pexp calculation

text:
# Question
Title: numerically stable log1pexp calculation
What are good approximations for computing `log1pexp` for single precision and double precision floating point numbers?

**Note:** `log1pexp(x)` is `log(1 + exp(x))`

I have found few implementations of `log1pexp` for double precision but they don't provide an explanation on how they arrived at the approximations. Hence, I am not able to implement `log1exp` for single precision numbers (without converting to double precision intermediates of course).

Reference implementation: https://github.com/davisking/dlib/blob/master/dlib/dnn/utilities.h#L16-L29

# Answer
> 6 votes
Let $0 \< \varepsilon \lll 1$ be the relative error bound of the floating-point system—$2^{-53}$ in IEEE 754 binary64 arithmetic.

First, the naive formula `log1p(exp(x))` always gives a good approximation unless `exp(x)` overflows: If `exp(x)` computes $(1 + \delta\_1) e^x$, and if `log1p(y)` computes $(1 + \delta\_2) \log(1 + y)$, where $|\delta\_1|, |\delta\_2| \leq \varepsilon$, then `log1p(exp(x))` yields

\begin{equation} (1 + \delta\_2) \log\bigl\[1 + (1 + \delta\_1) e^x\bigr\] = (1 + \delta\_2) (1 + \delta\_1') \log(1 + e^x) \end{equation}

where $|\delta\_1'|$ is bounded by a constant multiple of $\delta\_1$ since $(1 + \delta\_1) e^x$ is positive and $y \mapsto \log(1 + y)$ has small condition number on the positive real axis. Thus the relative error is bounded by $|\delta\_2| + |\delta\_1'| + |\delta\_2 \delta\_1'|$ which in turn is bounded by small polynomial function of $\varepsilon$.

> Exercise: Compute a bound on $|\delta\_1'/\delta\_1|$.

But you can do better, with less computation (only one transcendental evaluation, not two), in some special cases:

1. If $x \lll 0$, then $e^x$ is near 0 so $\log(1 + e^x) \approx e^x$. Specifically, $0 \< e^x \< 1$, so:

* $\log(1 + e^x) \geq e^x/2$, since $y \mapsto \log(1 + y)$ is a concave function with derivative $y \mapsto 1/(1 + y)$ bounded below by $1/2$ for $y \< 1$; and
    * the Taylor expansion of $y \mapsto \log(1 + y)$ converges absolutely at $e^x$.

Thus the relative error of $e^x$ from $\log(1 + e^x)$ is:

\begin{align} \frac{|e^x - \log(1 + e^x)|}{\left|\log(1 + e^x)\right|} &\leq 2 e^{-x} |e^x - \log(1 + e^x)| \\ &= 2 e^{-x} |e^x - (e^x - e^{2x}/2 + e^{3x}/3 - \cdots)| \\ &= 2 e^{-x} |e^{2x}/2 - e^{3x}/3 + e^{4x}/4 - \cdots| \\ &= 2 |e^x/2 - e^{2x}/3 + e^{3x}/4 - \cdots| \\ &\< 2 |e^x/2| \\ &= e^x. \end{align}

For $x \leq \log \varepsilon$, this relative error is bounded by $\varepsilon$, which justifies the formula `exp(x)`.

In IEEE 754 binary64 arithmetic, $\log \varepsilon \approx -37$.
2. If $x \gg 0$, we can use the identity

\begin{equation} \log(1 + e^x) = \log\bigl\[e^x (1 + e^{-x})\bigr\] = x + \log(1 + e^{-x}) \end{equation}

to rewrite $\log(1 + e^x)$ in terms of $\log(1 + y)$ for $0 \< y \< 1$, with $y = e^{-x}$, as in case (1). The value of $\log(1 + e^x)$ lies between $x + e^{-x}$ and $x + e^{-x} - e^{-2x}/2$, so the relative error of $x + e^{-x}$ from $\log(1 + e^x)$ is below the relative error of $x + e^{-x}$ from $x + e^{-x} - e^{-2x}/2$, which is

\begin{equation} \frac{|x + e^{-x} - (x + e^{-x} - e^{-2x}/2)|}{|x + e^{-x} - e^{-2x}/2|} = \frac{e^{-2x}/2}{|x + e^{-x} - e^{-2x}/2|} \leq e^{-2x}/2. \end{equation}

For $x \geq \log(1/\sqrt{2\varepsilon})$, this is bounded by $\varepsilon$, which justifies the formula `x + exp(-x)`.

In IEEE 754 binary64 arithmetic, $\log(1/\sqrt{2\varepsilon}) \approx 18$.
3. If $x \ggg 0$, then $x + \log(1 + e^{-x})$ may simply be rounded to $x$. Specifically, the relative error of $x$ from $\log(1 + e^x) = x + \log(1 + e^{-x})$ is

\begin{equation} \frac{\bigl|x - \bigl\[x + \log(1 + e^{-x})\bigr\]\bigr|}{\left|\log(1 + e^x)\right|} = \frac{\log(1 + e^{-x})}{\log(1 + e^x)} \< \log(1 + e^{-x}), \end{equation}

as long as $e^x \geq e - 1$ so that the denominator $\log(1 + e^x)$ is at least $1$.

For $x \geq \log\[1/(e^\varepsilon - 1)\]$, then this error is below $\varepsilon$, which justifies the formula `x`.

In IEEE 754 binary64 arithmetic, $\log\[1/(e^\varepsilon - 1)\] \approx 37$.

> Exercise: Find a nice formula for a bound on $x$ that corresponds to the cutoff $33.3$ in the source you cited, by taking the denominator $\log(1 + e^x)$ into account.

---
Tags: floating-point, numerical-algorithms, numerical-analysis, c++
---


# Question
Title: Can a Turing Machine be defined over many languages?
What does it mean, if possible, for a Turing machine to be defined over many languages?

# Answer
> 2 votes
A Turing machine isn't defined over a language.

Given a Turing machine $M$, we can define the language of inputs on which $M$ halts; or the language of inputs which $M$ accepts; or the language of inputs which $M$ either accepts or doesn't halt on; and so on.

Usually we are interested in either the language of all inputs on which $M$ halts, or (for a machine halting on all inputs), in the language of all inputs which $M$ accepts.

---
Tags: turing-machines
---


title: Is scanner and Lexical analyzer same?

text:
# Question
Title: Is scanner and Lexical analyzer same?
Today I read that

> The scanner is a subroutine which is frequently called by an application program like a compiler. The primary function of a scanner is to combine characters from the input stream into recognizable units called tokens.

But isn't it the job of lexical analyzer? Are they both the same?

# Answer
Yes. These are two different words for the same thing. I've also heard it called a lexer sometimes.
> 2 votes

---
Tags: compilers, lexical-analysis
---


# Question
Title: What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements?
What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements?

I.e. What is the link between the language and the algorithm

# Answer
A Turing Machine implements an algorithm.

The algorithm will either accept, reject or loop forever on certain inputs.

If we collect all of the inputs that the Turing Machine halts and accepts on. This is the associated language *recognised* by the Turing Machine.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Turing Machines: What is the difference between the language realised by a problem and the language for which the TM accepts on?
A decision problem A corresponds to the language L1 if L1 contains all of the solutions to A.

A language L2 is defined as the set of all inputs to which a TM halts and accepts.

What is the link between these two languages?

# Answer
> 1 votes
An algorithm solves a problem. Let’s assume that our algorithm is made to solve problem A.

The TM which implements this algorithm should halt and accept on all solutions to problem A. Due to the fact that the algorithm solves A.

Let’s now define L2 as the set of all inputs that the TM halts and accepts on. This will be the set of solutions to problem A.

If we define L1 as the set of all solutions to problem A.

Then in this sense, L1 and L2 should be the same.

I imagine that your confusion is when to use one or the other when defining the language. I am not sure when you should use each one, however I usually note that if the Turing Machine recognises a language L which is the solution set to a problem A, then this TM can solve problem A.

Remember recognises means it halts and accepts on L.

---
Tags: turing-machines
---


# Question
Title: Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting?
I have seen a remark saying "we usually say that a turing machine accepts/rejects a string, while it decides a language" Is this correct?

As I have also seen places where we mention a Turing machine "accepting a language"

See comment on OP's answer here, then the answer by Jan Hudec : What is the difference between a TM accepting and deciding a language?

I have also seen the definition of total/decider to mean, the Turing machine halts on all inputs. Is this all inputs in the language the Turing Machine is defined over?

# Answer
> 20 votes
A Turing Machine cannot accept a language.

A Turing Machine will either accept or reject a string or loop forever. We know it accepts the string because it will halt in an accepting state. It is said to reject a string, if it halts in a rejecting state.

A TM *recognises* a language, if it halts and accepts all strings in that language and no others.

A TM *decides* a language, if it halts and accepts on all strings in that language, and halts and rejects for any string not in that language.

A total Turing machine or a *decider* is a machine that always halts regardless of the input. If a TM decides a language, then it is decider by definition or a total Turing Machine.

Edit:

To answer some of the questions in the OP's comments:

* A language does not define a Turing Machine. The TM defines the language; this language is set of all inputs that the TM halts and accepts on.
* All finite languages are decidable which means that there is a corresponding Turing machine which is a *decider*.

# Answer
> 4 votes
One considers two different types of Turing machines:

* Total Turing machines: these are machines that are guaranteed to halt on all inputs. Sometimes known as deciders. If they halt in an accepting state, then the input is accepted; otherwise it is rejected. When interested in this kind of machine, we generally define the language accepted by the machine as the set of all inputs accepted by it.
* General Turing machines: these are machines that are not guaranteed to halt on all inputs (but may). When we are interested in this kind of machine, we generally associate with them the language of all inputs on which the machine halts.

---
Tags: turing-machines
---


# Question
Title: Sorting an array of strings by length in linear complexity
I am trying to find an algorithm to sort an array of strings by length in O(n) time complexity, and O(1) space complexity. The max length of the strings is known. Because of that, I tried using counting sort, but I failed to do in O(1) space complexity. Because multiple strings might have the same length, I need to store the strings in some kind of 2D array for each possible length, and that is O(n) space in the worst case of all strings having the same length. How would I go about solving this problem?

# Answer
> 2 votes
Assume the maximum length of strings is $k$, which is less than some constant.

Here is a simple algorithm that runs in linear time and $O(1)$ space complexity. The strategy is simply counting strings by length followed by in-place rearrangement.

Assume the input is an array $s\[0\], s\[1\], \cdots, s\[n-1\].$

1. Count the number of strings of length $i$. Store it in $a\[i\]$. We can imagine that $s$ is split into $k+1$ blocks of size $a\[0\], a\[1\], a\[2\], \cdots$. In the following steps, the $i$-th block will store the strings of length $i$.
2. Let $b$ be the partial sums of $a$, i.e., $b\[0\]=0$, $b\[i+1\]=b\[i\]+a\[i\]$ for all $0\le i\le k-1$. Note that $b\[i\]$ is the index of the first string in the $i$-th block.
3. Let $t\[0\], t\[1\], t\[2\],\cdots,$ be an array of $k$ numbers. We will use $t\[i\]$ to track the next available position to settle the next string of length $i$. Initially, $t$ is a clone of $b$.
4. Let $j=0$, the index of the first unsettled string. Loop the following.

Suppose the length of $s\[j\]$ is $i$.

* If $j\neq t\[i\]$, switch $s\[j\]$ and $s\[t\[i\]\]$. Now $s\[t\[i\]\]$ is a settled string. Increase $t\[i\]$ by 1.
    * If $j= t\[i\]$, increase $t\[i\]$ by 1. Keep increasing $j$ until either we find the next unsettled string or we have passed all strings, in which case we return $s$ and stop the algorithm.

    How can we increase $j$ efficiently and correctly? We can keep another integer that tracks which block $j$ is in. Note that all strings from index $b\[i\]$ to $t\[i\]-1$ inclusive are settled while all strings from index $t\[i\]$ to $b\[i+1\]-1$ inclusive are not settled.

It is clear the algorithm runs in linear time. The spaces used besides the original array $s$ are arrays $a,$ $b$ and $t,$ several looping variables, one temporary place needed to switch two strings. In total, the working memory is less than $3(k+1)+c+k=O(1)$.

**Exercise.** Improve the memory usage of the algorithm by reusing array $a$ for $b$.

---
Tags: time-complexity, sorting, strings, space-complexity
---


# Question
Title: What does it mean for a TM to solve a problem?
When we say a TM solves a problem, what does this mean?

# Answer
To simplify, let’s only speak about decision problems.

Decision problems have yes or no answers.

For example; Is X prime? Is a decision problem.

We can re-formulate the following question to be a set membership problem.

We define a language L to be the set of all prime numbers, ie the set of all strings that would make the decision problem return yes. To clarify, if X is a prime number, then the answer to the above would be yes.

We now change our question from “is X prime” to “is X in L”.

Since L is a language, we can associate a TM which decides L. This means a Turing machine which will accept on all strings in L and reject on all strings not in L.

This TM can now answer the problem of “is X prime” , if it accepts then X is prime, if it rejects then X is not prime.

We can say a TM solves a problem, if it decides the corresponding language L to that problem.

*minor note: WLOG I did not mention the encoding of X for simplicity. This however does not change the overall message*
> 2 votes

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


# Question
Title: Select K columns from matrix and one element from each row that has maximum sum
Given matrix of size N x M (N- rows, M - columns), given integer value K(K \< N and K \< M). Select arbitrary K columns and create new matrix of size N x K after that select max element from each row and calculate sum - S. Task is to find such K columns, so that this sum S will be maximum for given matrix N x M and value K.

Example:

K: 2 Matrix: \begin{bmatrix}1&2&3&4\\4&3&2&1\\3&1&4&5\end{bmatrix}

Select column 1 and 4: \begin{bmatrix}1&4\\4&1\\3&5\end{bmatrix}

Select maximum values from rows: \begin{bmatrix}4\\4\\5\end{bmatrix}

We got sum 13, this is maximum sum for given matrix and for given K.

It looks similar weighted assignment problem or weighted bipartite matching, but I don't know how to reduce this task to them.

Thank you!

# Answer
> 2 votes
There is trivial reduction from set cover. Consider 0-1 matrix where columns are subsets, rows are set elements and 1 means that subset contains element. Algorithm for your problem then can find K subsets to cover (sum max elements to n) set.

So your problem is NP-hard, no chances.

---
Tags: algorithms, matrix
---


# Question
Title: Difference between logic, fuzzy logic, probabilistic logic, quantum logic?
I am not sure if the names of these logics are right, but I saw that you can generalize logic with probability theory. Then I found 3 ways of reasoning with probabilistic/smooth logic, Fuzzy, Bayes/probabilistic and quantum. Can someone explain what are the major differences and expressiveness of such logics? Are they useful in normal logic?

# Answer
> 1 votes
Russell and Norvig catalogue a few formal languages in the following table\[\*\]:

\begin{array} {lll} \hline \text{Language} & \text{Ontological Commitment} & \text{Epistemological Commitment} \\ & \text{(What exists in the world)} & \text{(What an agent believes about facts)} \\ \hline \text{Propositional logic} & \text{facts} & \text{true/false/unknown} \\ \text{First-order logic} & \text{facts, objects, relations} & \text{true/false/unknown} \\ \text{Temporal logic} & \text{facts, objects, relations, times} & \text{true/false/unknown} \\ \text{Probability theory} & \text{facts} & \text{degree of belief $\in \[0, 1\]$} \\ \text{Fuzzy logic} & \text{facts with degree of truth $\in \[0, 1\]$} & \text{known interval value} \\ \hline \end{array}

(Note this is within the context of artificial intelligence.)

So the most important difference between fuzzy logic and probabilistic logic seems to be that in probabilistic logic you do not deal with *degrees of truth*, only *degrees of belief*.

I couldn't tell you very much about quantum logic other than that it appears to have originated in this paper by Birkhoff and von Neumann.

\[\*\] Russell, S. and Norvig, P. (2009). *Artificial Intelligence: A Modern Approach* (third edition). Pearson. Chapter 8, First-Order Logic.

# Answer
> 1 votes
This is a good way to understand quantum probability theory and how it relates to classical probability theory: https://arxiv.org/abs/quant-ph/0101012

---
Tags: logic
---


# Question
Title: How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?
I have proved the decision version of my problem to be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just compare the obtained minimum (or maximum) with target value in decision version. Thus, the decision version can be solved in poly-time as well. Since, the decision version is $\mathcal{NP}$-hard, so is the optimization version, i.e., the optimization version is $\mathcal{NP}$-hard.

My question is how to prove the converse direction: if the decision version can be solved in poly-time, can the optimization version be solved in poly-time as well?

I in advance thank you for any suggestions!

# Answer
> 0 votes
> If the decision version can be solved in poly-time, can the optimization version be solved in poly-time as well?

This depends on how technically precise you want to be.

The most correct answer is "No". Consider an optimisation problem $OP$ for which the encoded length of the output is superpolynomial in the encoded length of the input. Clearly no algorithm can produce the output in time polynomial in the encoded length of the input, so $OP \not\in \mathcal{P}$. However, the decision version $DP$ takes as input both the input of $OP$ and the guessed answer, so it is allowed time polynomial in the sum of the two, and in particular does not need to execute in time polynomial in the length of the problem per se.

However, if you're guaranteed that the output of $OP$ has (asymtoptically) an encoded length which is polynomial in the encoded length of the input (say $O(n^a)$ for input length $n$ and unknown $a$), then you can do a binary search, starting at any reasonable guess, doubling unless you get high enough, and then searching back down. The number of calls of the decision problem is $O(n^a)$, each call of the decision problem takes time polynomial in $n$, and the product of two polynomials is a polynomial.

---
Tags: complexity-theory, time-complexity, optimization, np-complete, np-hard
---


# Question
Title: What is the difference between transition function (delta) and extended transition function (delta hat) in finite automata?
What is the difference between transition function delta ($\delta$) and extended transition function delta hat ($\hat{\delta}$) in finite automata?

Both of them, when started at a state $q$ for a string $w$, will lead to the same state $p$. So what is the difference?

See, for example, page 15 of the third edition of Dexter Kozen's *Automata and Computability* (https://doi.org/10.1007/978-3-642-85706-5)

# Answer
I read some references in order to answer your question.

* **Transition function:** takes as arguments a state and an input symbol and returns a state, denoted by $\delta$.
* ***Extended* transition function:** Describes what happens when we start in any state and follow any sequence of inputs. It is a function that takes a state $q$ and a string $w$ and returns a state $p$ (the state that the automaton reaches when starting in state $q$ and processing the sequence of inputs $w$). It is denoted by $\hat{\delta}$.

**In simple terms:** transition function takes two parameters: a state and a *symbol*, while extended transition function takes a state and a *string*.

## Example of transition function

## Example of *extended* transition function
> 4 votes

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


# Question
Title: Analyze time series data to get min max over past period of time
The algorithm should analyze measured time series data in **realtime** and should check if all values of the specified last period lay inside a specified range. The range is calculated with max-min over the specified time period.

## Input data

```
t        | 10:00 | 10:01 | 10:02 | 10:03 | ... | 19:00 |
Temp [°C]| 40    | 41.3  | 39    | 43    |     | 45    |

```

## Algorithm parameters

1. Duration D: Past time to check for min/max
2. Max range R: (max-min) \< R

e.g: Check if the temperature was steady within 2 °C for the last hour. D=1hour, R=2°C

The algorithm should check periodically during data acquisition if the condition (all values of the last hour have been inside a range of 2°C) is true.

## Other requirements

* The sampling time can be from 10Hz to 50kHz.
* The time will always be increasing.
* Since this algorithm should run in an realtime environment there should be no memory allocations during run time

## Possible solutions

At the moment I have two possible solutions but do not like both of them:

1. Store all values within the duration in a bounded fifo-buffer and perform a min/max check from start to end periodically. I expect this to be the worst solution
2. Store the tuples in two B-Trees:

There are two indexes

1. TimeIndex t-\>(t,v): Index from time to tuple,
    2. ValueIndex v-\>list(t,v): Index from the value to a list of tuples with this value.

The algorithm will first get all tuples that are outside the time range and remove them in the value index.

Then the value index is updated with the newly measured tuples.

The range can then be determined by looking up the minimum and maximum key in the value index.

I think the second approach is faster but will allocate memory during runtime. Since it should run in a realtime environment I like to avoid allocations.

Is there another possibility with O(log n) and no allocations?

# Answer
The following paper provides a O(1) algorithm:

D. Lemire, Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element, Nordic Journal of Computing, 13 (4), 2006 (https://arxiv.org/abs/cs/0610046).

An implementation of this algorithm is provided in the GNU Scientific Library (see https://www.gnu.org/software/gsl/doc/html/movstat.html).
> 2 votes

---
Tags: algorithms
---


# Question
Title: Show that there are infinitely more problems than we will ever be able to compute
I was looking at this reading of MIT on computational complexity and on minute *15:00* Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot follow his reasoning, in practice what he says is this:
we can state a decision problem as string of $0$ and $1$ which in practice is the truth table of the function.
He goes on to say that a decision problem is an infinite string of bits while a program is a finite string of bits and up to here no problem. What I don't understand is the continuation of the proof from this point on: Decision problems are in $\mathbb{R}$ cause you can put a decimal point before the string representing the problem, thus obtaining the decimal part of a real

```
 for example if you have 0111011010101010101... it could become x.0111011010101010101...

```

A program is "just" an integer in $\mathbb{N}$ cause it is a finite string of bits. The point that I fail to understand is how it is possible that a decision problem is comparable to a real number instead of an integer ... I mean, if we use the argument of "put a dot in front of the number" could not the same reasoning also be applied to the number of possible algorithms that can ever be produced?

# Answer
> 11 votes
If I understand you correctly, your question is — why a solution can be encoded by a natural number and a problem with a real number. (I assume that you understand the next phase of the proof which is based on the difference between sets of cardinality $\mathfrak c$ and $\aleph\_0$.)

The reason lies in set theory, more specifically in the cardinality of different sets. Count the number of programs — it is the size of the different strings of a specific language or set of characters (ASCII for example). This size is equivalent to the size of the set $\mathbb{N}$ (natural numbers). (Each string can be represented as its value that is calculated by its binary represantation.)

But, counting the number of functions from the natural numbers (or strings that represents them) to $\\{0,1\\}$, well that is a whole different story, and here we are dealing with differences in size between two infinite sets; the size of this set is larger. There is a nice proof that is based on the fact that the functions from $\mathbb N$ to all of the mentioned above sets cannot be "onto", which leads to the cardinality difference conclusion. You can read the proof here.

# Answer
> 13 votes
Reformulating in a more mathematically precise way, what the lecturer is trying to say is this: Any algorithm can be (uniquely) encoded as a finite string of bits, and any finite string of bits (uniquely) encodes a program; hence, there is a bijection between $\mathbb{N}$ and the set of algorithms, so both are countable sets. Conversely, having fixed an ordering of strings, any decision problem $P$ can be (uniquely) encoded as an infinite string of bits, where the $i$-th bit represents whether the $i$-th string is in $P$ or not, and any infinite string of bits (uniquely) encodes a decision problem (in the same fashion); hence, $\mathbb{R}$ and the set of decision problems are both uncountable sets.

# Answer
> 6 votes
Every algorithm can be described by a finite string, and so there are only countably many algorithms. In contrast, we can describe every decision problem as an infinite decimal in base 2, and moreover this is a *surjective* mapping: every number in $\[0,1\]$ can be "decoded" into a decision problem. Therefore there are uncountably many decision problems.

The decoding argument doesn't work for algorithms — while every algorithm corresponds to a finite decimal, this doesn't cover all of $\[0,1\]$, but only a countable subset of it.

---
Tags: computability, proof-techniques, decision-problem, uncountability
---


title: NP-hardness even with perturbations

text:
# Question
Title: NP-hardness even with perturbations
Consider the following problem, which can be called "2-SET-PARTITION":

> Given two sets of positive numbers, $a\_1,\ldots,a\_n$ and $b\_1,\ldots,b\_n$, where $\sum\_{i\in\[n\]}a\_i = \sum\_{i\in\[n\]}b\_i = 2 S$, decide whether there exists a subset of indices $I\subseteq \[n\]$ such that: $\sum\_{i\in I} b\_i \geq S \geq \sum\_{i\in I} a\_i$.

It is easy to prove that this problem is NP-hard by reduction from PARTITION:

> Given an instance $p\_1,\ldots,p\_n$ of PARTITION, create an instance of 2-SET-PARTITION with: $\forall i\in\[n\]: a\_i = b\_i = p\_i$. Obviously the answer to the first problem is "yes" if and only if the answer to the second problem is "yes".

But, this proof considers only a small subset of the 2-SET-PARTITION --- the subset in which the two sets of integers are equal. Theoretically, it could be that a "typical" instance of the problem is easy: it could be that there is a subset of instances, which includes all instances except a subset of measure zero, in which 2-SET-PARTITION can be decided in polynomial time. There are similar problems in which this is the case.

To prove that this is not the case with 2-SET-PARTITION, one can use the following reduction:

> Fix some vector of perturbations, $e\_1,\ldots,e\_n$, such that $\sum\_{i\in \[n\]} e\_i \< 1/2$. Given an instance $p\_1,\ldots,p\_n$ of PARTITION, create an instance of 2-SET-PARTITION with: $\forall i\in\[n\]: a\_i = p\_i, b\_i = p\_i + e\_i$. Here, too, it is possible to show that the answer to the first problem is "yes" if and only if the answer to the second problem is "yes".

Intuitively, the second proof is much stronger than the first, because it shows that even arbitrary perturbations cannot make the problem easy.

MY QUESTIONS:

* What is a term for this stronger NP-hardness concept, that is robust to perturbations?
* What are some references showing proof techniques for this hardness concept?

# Answer
If you allow arbitrary $e\_i$, you are in muddy ground. Are your numbers real? No way to express them finitely, NP-whatever right out the window. Rational? The input size can blow up almost arbitrarily, again nothing relevant to prove.

Note that (for very good reasons) NP-hard and its ilk talk about the *worst* case complexity of the problem (that is well-defined, opposed to say avergage complexity; best-case essentially tells nothing in most interesting cases). That some proof gives just one particular hard case for particular sizes, while another gives a bevy of them, is irrelevant.
> 1 votes

---
Tags: reductions, np-hard, partitions
---


# Question
Title: Why isn't an edge-map graph implementation used in practice?
Wikipedia states that three different graph implementations are used in practice:

* Adjacency Lists
* Adjacency Matrix
* Incidence Matrix

While I was learning about these structures, another option occurred to me that seems to have better asymptotic properties than Wikipedia's. My idea is to create a hash map where the keys are `(vertex, vertex)` pairs and the values are the weight of the edge.

Given that inserting into and querying from a hash map is $O(1)$, I believe the time complexity would be the following:

* Store graph: $O(|E|)$ space
* Add vertex: $O(1)$ time
* Add edge: $O(1)$ time
* Remove vertex: $O(|V|)$ time
* Remove edge: $O(1)$ time
* Query edge existence: $O(1)$ time

This structure has strictly better time and space complexities than all three options listed. **So why isn't this implementation used in practice?**

# Answer
> 6 votes
Assume we are dealing with the representation of a weighted graph. I will use Python as the programming language to illustrate the points, which will remain true largely if another programming language is used.

Let us call the graph representation raised in the question "hashmap from edges to their weights" or "**edge-weight hashmap**". I would agree that an edge-weight hashmap is seldom used to represent a weighted graph.

One overwhelming reason is that compared to edge-weigh hashmap, it is usually preferred to use the following popular variation of adjacency list, which I will call "adjacent hashmaps" or "**nested hashmaps**". The entire graph is represented by a big hashmap $g$, a.k.a. the outer hashmap, which is a collection of $(v, g\[v\])$ pairs, where $v$ is a vertex and $g\[v\]$ is a smaller hashmap, a.k.a. the inner hashmap. $g\[v\]$ is a collection of of $(u, w)$ pairs, where each vertex $u$ is a vertex that is adjacent to $v$ and $w$ is the weight of edge $(v,u)$.

**An example**

$\begin{array}{c|c} \text{Nested Hashmap} & \text{Edge-weight Hashmap} \\\hline \begin{array}{l@{}l@{}l@{}lll} \\{\\ \quad1: &\\{2:2,&4:5\\},\\ \quad2: &\\{1:2, &3:14, &4:5, &5:4\\},\\ \quad3: &\\{2:14,&5:34\\},\\ \quad 4: &\\{1:5, &2:5, &5:58\\},\\ \quad 5: &\\{2:4, &3:34, &4:58\\}\\ \\}\end{array} & \begin{array}{lllll} \\{\\ \quad(1,2):2, &(1,4):5,\\ \quad(2,1):2, &(2,3):14,&(2,4):5,&(2,5):5,\\ \quad(3,2):14,&(3,5):34,\\ \quad(4,1):5, &(4,2):5, &(4,5):58,\\ \quad(5,2):4, &(5,3):34,&(5,4):58\\ \\}\end{array} \\ \end{array}$

The alignment of data entries above is meant for easy reading of Python code. By the general nature of hashmap, the actual storage locations of the entries in a hashmap are sort of unpredictable.

**Comparison of complexity between nested hashmaps and edge-weight hashmap**

$\begin{array}{|l|c|c|}\hline &\text{Nested Hashmap} & \text{Edge-weight Hashmap}\\\hline \text{Store graph} &O(|E|) &O(|E|)\\\hline \text{Add vertex} &O(1) &O(1)\\\hline \text{Add edge} &O(1) &O(1)\\\hline \text{Remove vertex} &O(|V|)&O(|V|)\\\hline \text{Remove edge} &O(1) &O(1)\\\hline \text{Check if two vertices are adjacent} &O(1) &O(1)\\\hline \text{List neighborhood of a vertex }&O(|V|) &?\ O(|E| )\ ?\\\hline \end{array}$

The entry "$?\ O(|E| )\ ?$" entry on the column of "edge-weight hashmap" means that it is not clear how to list neighborhood of a given vertex $v$ efficiently. $O(|E|)$ refers to the time-complexity of the natural way, which goes over all the edges, keeping only the edges that contain $v$.

So both implementations have the same asymptotic time-complexity and space-complexity for all operations, except for listing the neighborhood of a vertex, arguably the most popular iteration on a graph, for which nested hashmaps are significantly faster. In practice, nested hashmaps should also exhibit better cache-friendliness.

**Comparison of programming friendliness**

Here are the code that does the basic iterations over a graph represented in variable $g$ using nested hashmap or edge-weight hashmap.

$\begin{array}{|l|l|c|}\hline &\text{Nested Hashmap} & \text{Edge-weight Hashmap}\\\hline \text{Iterate over all vertices} &\text{for v in g:} &???\\\hline \text{Iterate over the neighborhood of vertex u} &\text{for v in g\[u\]:} &???\\\hline \text{Iterate over all edges} &\begin{array}{c}\text{for u in g:}\quad\quad\\\text{ for v in g\[u\]:}\end{array} &\text{for e in g:}\\\hline \end{array}$

The "???" entries on the column of "edge-weight hashmap" means that it seems rather clumsy to write that piece of code in Python or other programming languages, assuming their generally-available implementations of hashmap.

Nested hashmaps are far more programmer-friendly than edge-weight hashmap.

**Summary**

Although the time-complexity of the most basic operations using edge-weight hashmap are very good, it does not support the basic iterations well. It should be replaced by nested hashmaps in general.

## Exercises

**Exercise 1.** Verify that this answer is applicable for weighted directed graph after slight adaptation. Verify that this answer is applicable for (unweighted) directed or undirected graph as well.

**Exercise 2.** Compare edge-weight hashmap with adjacent-weight list in detail. An adjacent-weight list for the graph above in Python can be $g=\[\[\], \[(2,2), (4,2)\],$ $\[(1,2), (3,14), (4,5), (5,5)\],$ $\[(2,14), (5, 34)\],$ $\[(1,5), (2,5), (5,58)\],$ $\[(2,4), (3,34), (4,58)\]\]$, where $g\[v\]$ is a list of $(u,w)$ pairs for vertex $v=1,2,3,4,5$ (g\[0\] is ignored since 0 is not a vertex), where $w$ is the weight of edge $(v,u)$.

# Answer
> 2 votes
There's at least two points that should be raised here:

* Insert and query for a hash table are not in general constant time operations in the worst case.
* There is typically no implementation that would be suitable for every possible case (i.e., different algorithms might benefit from different implementations of the graph). As an example, it doesn't seem clear how you would efficiently iterate over the neighbors of a vertex which several graph algorithms need.

---
Tags: graphs, time-complexity, data-structures, space-complexity, hash-tables
---


title: How does a=2 twice in this code sample?

text:
# Question
Title: How does a=2 twice in this code sample?
I am just starting out learning code.

The output of the following code is OOOXOXOO, but I don't see how X can be printed twice. How does a=2 more than once?

```
a = 1
while a < 3:
    b = 1
    while b < 3:
        if a == 2:
            print ("X"),
        print ("O"),
        b = b + 1
    print ("O"),
    a = a + 1

```

# Answer
> 2 votes
Think carefully about the flow.

Your innermost While loop runs through b = 1, 2, each time it hits.

It does this for EACH value of a in the outermost loop.

So when a == 2, we progress inward and run through that loop twice. a == 2 both times.

---
Tags: python, iteration
---


# Question
Title: D has polynomial verifyer, the certificate for any word $w \in D$ is at most O(|log w|) space. Prove $D \in P$
Given that a language D has a polynomial verifier,

and given that for every word $w \in D$, the length of the certificate $c$ is $O(\log|w|)$ space.

How can I prove that $D\in P$ ?

My idea was to create a TM that takes a word w and runs the verifier on all the strings that are potentially a certificate but I don't know how to claim that such a machine will stop? How can I limit the number of certificates my machine will generate?

# Answer
Suppose language $D \in NP$ and for every input $w \in D$, the certificate $y\_w$ is of logarithmic length; $|y\_w| = O(\log|w|)$, and a polynomial verifier $V(w,y)$ exists for $D$.

We can also say: a constant $c$ exists s.t for any $w \in D$ whose certificate is $y\_w$, $|y\_w| \leq c \log |w|$

Consider the following algorithm $A$:

Given input $x$, for every possible certificate $y\_i$ of length at most $c \log |x|$, run $V(x,y\_i)$

$\bullet$ If $V(x,y\_i) = 1$, then $x$ has a provable witness and $x \in D$

$\bullet$ If $V(x,y\_i) = 0$, continue to the next certificate. If all certificates are exhausted, then no $y\_x$ exists, and $x \notin D$.

$A$ checks at most $2^{c \log |x|}$ certificates, and $2^{c \log |x|} = |x|^c$. $V$ verifies each certificate at polynomial time (say $|x|^k$), so in total $A$ runs in $O(|x|^{k+c})$ which is polynomial in $|x|$

We get that $D$ can be decided in polynomial time $\Rightarrow D \in P$
> 1 votes

---
Tags: complexity-theory, turing-machines, np
---


# Question
Title: Why $P$ cannot have NULL string in Arden's Theorem?
Arden's Theorem says that in the equation $R=Q+RP$, the $P$ cannot have NULL string. In this respect,the theorem will not be valid for the expression $R=Q+R(NULL+01)$. Am I correct? If so, then what will be the justification?

# Answer
> 2 votes
Here is the version of Arden's theorem on Wikipedia:

> One solution of the language equation $R = Q+RP$ is $R = QP^\*$.
>
> If $\epsilon \notin P$, then this is the only solution.

When $\epsilon \in P$, there are more solutions. In fact, we can prove the following result:

> The solutions of the language equation $R = Q+RP$, where $\epsilon \in P$, are $R=SP^\*$ for all $S \supseteq Q$.

**Proof.** Let us first show that $SP^\*$ is always a solution. Since $\epsilon \in P$, $RP = SP^+ = SP^\*$. Since $SP^\* \supseteq S \supseteq Q$, $Q + RP = Q + SP^\* = SP^\* = R$.

Let us now show that all solutions are of this form. Suppose that $R$ is a solution. Clearly $R \supseteq Q$. Since $\epsilon \in P$, this implies that $RP \supseteq R \supseteq Q$, and so $RP = Q + RP = R$. Induction shows that $RP^n = R$ for all $n \in \mathbb{N}$, and so $RP^\* = R$. Since $R \supseteq Q$, this is a solution of the required form. $\square$

---
Tags: formal-grammars, regular-expressions
---


# Question
Title: Prove completeness of a language with Turing Machine
I'm trying to prove that a simple computer language is Turing Complete. For that, I did some researches about Turing Machine and I found (if I understand correctly), that we can prove that by simuling a Turing Machine with this language. Like Turing Machine has completeness, the fact to simulate it shows the language has completeness too.

So, to prepare this, I program in Java a class Turing that takes the transitions table, the input value (to be calculated) and the initial state and simulate a Turing Machine. If I do a similar program in my computer language, is that enough to prove the completeness of this latter?

# Answer
> I program in Java a class Turing that takes the transitions table, the input value (to be calculated) and the initial state and simulate a Turing Machine

This is not enough. You still need to prove, that your class can simulate ANY Turing machine.

Normally to show Turing completness one will

1. Implement Universal Turing Machine in this language and
2. Show how unlimited tape is possible.

Of course unlimited tape is impossible in realistic hardware, but even for idealized translation model for languages like C, there are problems

Also I want to add one more clause: make sure that your language well-defined enough. It shall either have mathematical definition or clear formal translation model in language standard.
> 2 votes

---
Tags: turing-machines, turing-completeness
---


# Question
Title: Estimation of the number of solutions by Counting
This is a question from a quantum computation textbook.

Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times from the Search Space of size $N$ for solutions using an Oracle that outputs 1 or 0, and let $X\_1,X\_2,X\_3,...X\_k$ be the results of the Oracle calls. So $X\_j=1$ if the $jth$ Oracle call found a solution and $X\_j=0$ otherwise. This algorithm estimates the number of solutions $S$:

> $$S=N * \sum\_{j}\frac{X\_j}{k}$$

Assuming the number of solutions is $M$ and this is not known in advance. The Standard Deviation of $S$ is stated and found to be:

> $$\Delta S=\sqrt{\frac{M(N-M)}{k}}$$

**The question is:**
Prove that to obtain a probability at least $\frac{3}{4}$ of estimating $M$ correctly to within an accuracy $\sqrt{M}$ for all values of $M$, we must have $k=\Omega(N)$.

I know how to get the 2nd equation from the 1st, which is by moving $N$ and $k$ to the left, thus treating $kS/N$ as a Binomial Distribution $B(k,\frac{M}{N})$. Then finding the variance of the Binomial Distribution and some algebraic manipulation will lead to the 2nd equation. I'm clueless in proving of $k=\Omega(N)$. Only thing I tried writing is:

> $$P\Big(\sqrt{\frac{M(N-M)}{k}}\leq \sqrt{M}\Big)\geq \frac{3}{4}$$

Can someone help me with this?

# Answer
> 1 votes
Consider a binomial random variable $X \sim \mathrm{bin}(n,p)$, and let $Y = (X - pn)^2$. A straightforward but long calculation shows that $$ \frac{\mathbb{E}\[Y\]^2}{\mathbb{E}\[Y^2\]} = \frac{np(1-p)}{p^3 + (1-p)^3 + 3(n-1)p(1-p)} = \frac{1}{3} + o(1). $$ (This is to be expected, since a binomial random variable has roughly Gaussian distribution, and for Gaussian distributions the ratio is exactly $1/3$.)

Now let $Z = (S - M)^2$. It is still the case that $$ \frac{\mathbb{E}\[Z\]^2}{\mathbb{E}\[Z^2\]} = \frac{1}{3} + o(1), $$ since $Z$ is just a scalar multiple of $Y$ above, for an appropriate choice of parameters.

In view of applying the Paley–Zygmund inequality, let us estimate $$ \theta = \frac{M}{\mathbb{E}\[Z\]} = \frac{M}{M(N-M)/k} = \frac{k}{N-M}. $$ It follows that $$ \Pr\[|S-M| \> \sqrt{M}\] = \Pr\[Z \> M\] \geq (1-\theta)^2 \left(\frac{1}{3} + o(1)\right). $$ If we want the right-hand side to be bounded by some constant (in your case, $1/4$) then we need $\theta$ to be bounded from below by some constant $c$ (in your case, roughly $1-\sqrt{3/4}$). In other words, we need $$ k = \theta (N-M) = \Omega(N-M). $$ As long as $M$ is not very close to $N$, this is $\Omega(N)$.

(When $M$ is very close to $N$, less samples are needed. For example, only one sample is needed when $M = N$.)

---
Tags: complexity-theory, quantum-computing, counting, mathematical-programming, statistics
---


title: Min cut of at most k edges

text:
# Question
Title: Min cut of at most k edges
I have been studying for my algorithms exam and whilst doing previous exams found this question for which I am not sure how to handle.

Given a graph $G=(V,E)$ with integer capacities $C:E \rightarrow \mathbb{N}$, find an efficient algorithm to determine whether the graph has a min cut of at most $k$ edges (assume $k=100$).

My thinking was computing a min cut, then for every edge on that cut, increase it by 1 and compute the min cut again - if the max flow has risen, that means that that edge exists in every single min cut. And If I found there to be over 100 of these edges, then there is no min cut of at most $k$ edges.

However, I don't think that if I found there to be less 100 of these edges, there's necessarily a min cut of at most 100 edges.

# Answer
Apply the transformation $w \mapsto (m+1)w + 1$ to all weights (where $m$ is the number of edges in the graph), and find the minimum weight cut in the new graph. This will give you the minimum weight cut with the minimum number of edges. By computing the value modulo $m+1$, you can determine the number of edges.
> 2 votes

---
Tags: algorithms, network-flow
---


# Question
Title: Are there any "complete" languages in $coNP -NP$?
Suppose $coNP \neq NP$

language B would be called "complete" in $coNP-NP$ if:

1. $B\in coNP - NP$
2. $A\in coNP-NP \implies A\leq\_pB$

Are there any "complete" languages in $coNP - NP$?

# Answer
If we are assuming that $coNP≠$,

we can conclude that every language that is $co NP$ complete is **not in** $NP$ (a contradiction to your given assumption).

Thus, every language we already know of that is $coNP$ complete, is complete as well in $coNP -NP$.
> 3 votes

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


# Question
Title: How do we guess the recurrence relation from the given equation
In this book introduction to algorithms , i have been reading about a method named substitution method to solve the recurrence, the recurrence equation is \begin{equation} T(n)=2 T(\lfloor n / 2\rfloor)+n \end{equation}

the author guessed the solution was $O(n \log n)$ and proved it below, my question is how to make the guess? I wanted to know why it cant be $O(n^2)$? How do you guess them correctly at first?

\begin{aligned} T(n) & \leq 2(c\lfloor n / 2\rfloor \lg (\lfloor n / 2\rfloor))+n \\ & \leq c n \lg (n / 2)+n \\ &=c n \lg n-c n \lg 2+n \\ &=c n \lg n-c n+n \\ & \leq c n \lg n \end{aligned}

# Answer
> 2 votes
To guess simple recurrences most useful step is to study basic intuition beyond so-called master theorem that looks at any recursion as if it is implicit tree.

Your case is admissible for it and thus easy: on each step you have half of task (peek one branch down in tree), and $O(n)$ work. Multiply tree height and amount of work on each step and you will get your guess. But you will probably never guess any inadmissible case.

# Answer
> 1 votes
The guess $O(n^2)$ also works: $$ T(n) \leq 2c\lfloor n/2\rfloor^2 + n \leq \frac{c}{2} n^2 + n \leq cn^2, $$ as long as $c \geq 2$.

The author did not *guess* the answer. Presumably the author already *knew* the answer.

In practice, for most recurrences you would encounter one of the following methods will work:

* Open up the recurrence (also known as repeated substitution).
* Appeal to a standard result such as the master theorem.
* Use a computer experiment (could be deceiving).

In this case, the recurrence is so well-known and commonplace that the author must have seen it worked out somewhere. It can also be "solved" (i.e., the asymptotic behavior of $T(n)$ determined) using the master theorem, which is how you could do it.

---
Tags: algorithms, recurrence-relation
---


# Question
Title: Is this a syntax error or a semantic error?
I came across the following question

> The error in the expression " **if x\>y x=2;** " is detected by
>
> a. Syntax analyzer b. Lexical analyzer c. semantic analyzer

I know that the parentheses of x\>y are missing, but it is not syntax error right? as all the syntaxes are correct, but we are missing a pair of parenthesis.. so is this a semantic error?

The correct answer is given as a.

# Answer
As vonbrand points out, the lexical/syntactic/semantic division is artificial. We use it because it's convenient, but languages can easily blur the lines.

The most substantial division in the set is between lexical/syntactic errors and semantic errors. Lexical and syntactic errors can be identified by logical operations on the text of your program itself, while semantic errors are cases where the program doesn't do what you meant it to do. For example:

```
if (x);
    y();

```

In C++, that is a perfectly valid program. It will check to see if `x` is true. If it is, it does the statement which follows... which is the empty statement ending in the first semicolon. Then, regardless of the value of `x`, it runs the next line, which is `y()`. The result is a valid program, but you almost certainly intended to write

```
if (x)
    y();

```

Which only executes `y()` if `x` is true. Given how I indented my lines in both cases, it's pretty clear that I intended the second case. If I intended the first case, I'd write something like

```
if (x)
    ; // do nothing - this is a placeholder to fill in later
y();

```

Which has the *exact* same semantic meaning as the first example, I just wrote it in a way that makes it clear what I meant.

The lexical error vs. syntactic error is a bit more difficult. Long story short, lexers (which have lexical errors) turn a stream of characters into a stream of tokens, while parsers (which have syntax errors) turn a stream of tokens into a syntax tree. The difference is almost always along the lines of Chomsky's language hierarchy. Lexers are typically Type 3 (regular languages) while parsers are typically Type 2 (context-free).

Why divide it this way? Well it turns out that it's easy to write a regular language (Type 3) and have it do what you want, but they aren't all that expressive. It's much harder to write a context-free language (Type 2), but they have the expressiveness we need. When you're writing a context-free language, it's a pain to have to include all the fiddly-bits needed to build the language up character by character. For example, context-free languages often need to look ahead a bit to figure out the next step. Done right, most languages can be parsed by looking no more than one token ahead. However, if we did things by characters, rather than tokens, we may have to look an arbitrary number of characters ahead (such as if the next token would have been a string literal).

The solution is that we bootstrap the context-free language with a regular language. We use a regular language to turn a stream of characters into a stream of tokens, and then we build our context-free language around those tokens. We have found that this generally does a good job of managing the languages we care about.

So in your case, the program in question is if `x>y x=2;`. The first thing I'd do is see whether there's a lexical error here. To do that, I'd chop it up into tokens. Now I'm assuming this language is similar to most languages I know, so the lexing would break this up as:

```
if  KEYWORD_IF
    (space)
x   IDENTIFIER
>   GREATER_THAN
y   IDENTIFIER
    (space)
x   IDENTIFIER
=   ASSIGNMENT
2   INTEGER
;   SEMICOLON

```

There's no issues with lexing here. The lexer was able to tokenize the string without any issue (assuming this is a garden variety lexer which "does what I think it should do").

A lexer error might be something like `if x<y x="Dangling string literal...`. That particular program has a lexer error because the regular expression that matches string literals expects to see a closing quote, but there was none.

So now we have a string of tokens. But can we make it into a syntax tree without a syntax error?

Once again, assuming something about the language, it looks C like. In C, the construction for an `if` block is

```
KEYWORD_IF OPEN_PAREN expression CLOSE_PAREN statement

```

There's no way to match the string of tokens against that grammar rule, because there's no `OPEN_PAREN` following `KEYWORD_IF` in the token stream. Thus, there's a syntax error.

If this is a language that doesn't need parenthesis (e.g. Python), then there will also almost certainly be a syntax error at "if x\<**y x**=2;" Very few languages include a language rule which has two identifiers back to back like `y x`. So there would be a syntax error there.

At this point, we can stop. If there's an error at one level, we cannot continue on, so we can't have errors at the next level. Since there is a syntax error, it is meaningless to address the question of whether there is a semantic error or not. Thus, as your answer key states, the correct answer is (a)
> 1 votes

# Answer
The classification as lexical/syntax/semantic error is largely artificial, governed by separate parts of your compiler: it the "lexical analysis" phase detects the error, it is deemed lexical; if the parsing (syntax analysis) phase does, it is classified as "syntax error", others are reported as "semantic errors" (or just pass through without detection, giving rise to a runtime error). This is more am implementation detail than a firm distinction. It is e.g. possible to do away with separate lexical analysis and do all as parsing, some "syntax errors" aren't really parsing errors, but undefined variables, some semantic problems can be detected when parsing. Some languages (infamously C++) are complex enough that checking syntax requires checking much beyond context free grammar aspects to catch "syntax errors".
> 2 votes

---
Tags: compilers
---


title: Turing Machines proof notations

text:
# Question
Title: Turing Machines proof notations
In context of "Computability", I have went over some proofs for Recursion Theorem using Turing Machine description. A TM $M$ stands for a single tape Turing machine and $\langle M \rangle$ is the description of TM $M$. Even some semi-decidable machines such as $A\_{\mathrm{TM}} = \\{ \langle M, w \rangle \mid \text{TM $M$ accepts $w$} \\}$. My question is simple:

**What is difference between using $\langle M \rangle,\langle w \rangle$ vs $\langle M , w \rangle$ for a TM description?**

A simplistic answer I assume is that it is being a convention in writing formal proof that books follows standard of combining all inputs as a single description (all inputs comes under single brackets as opposed to multiple descriptions)?

My question c

If $M\_1 = \\{ \langle M , w \rangle \mid \text{TM $M$ accepts $w$} \\}$ and $M\_2 = \\{ \langle M \rangle , \langle w \rangle \mid \text{TM $M$ accepts $w$} \\}$

**What's the difference between $M\_1$ and $M\_2$?**

# Answer
$\langle x \rangle$ simply denotes the encoding of some object $x$. $x$ can be a TM (e.g., its Gödel number), a string, some combination thereof (properly separated), or even other objects like a graph, etc.

This serves, for instance, to distinguish between $\\{ \langle M \rangle \mid \text{$M$ is a TM} \\}$, which contains *encodings* of TMs (e.g., their Gödel numbers or representations in binary), and $\\{ M \mid \text{$M$ is a TM} \\}$, which is the set of *Turing machines themselves* (as mathematical objects). The underlying motivation is that it is not clear how a TM (as an object) can be passed as an input; what you do is provide its "program", that is, its states and transition function.

When multiple objects are encoded together as a single string (i.e., to be seen as a single object), it is usual practice to denote it as $\langle x\_1, \ldots, x\_m \rangle$. Again, it is not immediate what the encoding is. It *could* be simply concatenating the encodings of each $x\_i$ and separating them (e.g., $\langle x\_1, \ldots, x\_m \rangle = \langle x\_1 \rangle \\# \cdots \\# \langle x\_m \rangle$); it could also be that the encoding of $x\_i$ is altered in some way (e.g., each $0$ or $1$ in $\langle x\_i \rangle$ is doubled and each such representation is separated by $01$); it could even be that the entirety of the representation is compressed (so as to reduce its length) or that it is subject to some predetermined enumeration (e.g., as a vector over some countable space).

Generally, if they are relevant to the context at all, these descriptions should be made precise beforehand, as most textbooks do. In computability theory, except when covering Gödelization, they usually are not; this is because the actual length of the input is irrelevant to computability questions. Things are different in complexity theory—though it usually does not get much attention there either (besides coming up in a preface or similar); most objects are encoded in binary anyway, and multiple objects with only a constant stretch, which suffices for almost all complexity-theoretical topics.
> 2 votes

---
Tags: algorithms, formal-languages, turing-machines
---


# Question
Title: Express a number with a combination of arithmetic operations and a single number
Today I ran into a this relatively simple (At least from my perspective ) problem. Basically the task is to be able to express any number **using only a single number an any combination of arithmetic operations, square roots, exponentiation or factorials**. To further elaborate I will make an example.

The input of the program would be a number 57 and a 8. The solution would be expressing the number 57 using only 8s and any of the defined operations.

In this case the number 57 could be expressed as 57 = (8+8+8+8+8+8+8)+8/8 Alternatively if we had the number 25 and 3 as an input, we could also do 25 = 3^3 - 3/3 - 3/3

**The task is to define the input number with a similar method mentioned above, using the least amount of operations.**

The person who created this problem defined it as difficult and no matter how hard I think about it, I just can not find a reason why. In most cases the problem will spin around simple integer factorization and in special cases, using factorials (With big numbers) or exponentiation will yield a less lengthy result.

What I am asking for is if there is any better, more efficient method to solve this problem and whether I am missing something obvious which would make this problem look as "Difficult" as it was defined.

Thanks for the answers in advance.

# Answer
If you have any number at all, say $N$, then you can write it as $\frac 8 8$ followed by $N-1$ occurrences of $+\frac 8 8$.

The difficulty of the problem lies in finding **short** sequences of 8s that will work. The best known way is to enumerate all the possibilities.

For instance, with six 8s, write them out in a row and then insert operators between them and after them, to generate all valid reverse-Polish notation expressions which lead to a single result.

As well as the usual arithmetic operators, include a “concatenate” one which, immediately following two 8s, produces 88.

Enumerating all conceivable RPN strings is not hard: there can only ever be five dyadic operators. Filtering them to select just the valid ones is not hard either: probably the best way is to include that process in the process of evaluating each one.
> 1 votes

---
Tags: algorithms, number-theory
---


# Question
Title: Finding rainbow cycle in digraph colored with $\log n$ colors
> Given a directed graph with $n$ vertices, and $k=\log n$, we are given a coloring of the vertices with $k$ colors.
>
> Describe an algorithm determining if there exists a simple cycle in $G$ of length $k$ visiting exactly one vertex of each color.
>
> Time complexity should be $O(n^3)$.

I couldn't think of any efficient solution.

# Answer
> 0 votes
The idea is to use dynamic programming. For each vertex $v$ and color subset $S$, calculate whether there is a simple path, ending at $v$, and including exactly the colors in $S$. Details left to you.

The main trick here is that we can be sure that the path being constructed is simple since all vertices in it have different colors. We can apply the same idea to *uncolored* graphs by choosing a random coloring. This is known as color-coding, an idea of Alon, Yuster and Zwick with wide applicability.

---
Tags: graphs, colorings
---


title: Techniques for proving NP-completeness

text:
# Question
Title: Techniques for proving NP-completeness
I've been reading Garey-Johnson book Computers and Intractability and I am focusin on Section 3.2, *Techniques for proving NP-completeness*. In these definitions and explanations nothing is formally defined. I was wondering, how would someone define those techniques formally?

The techniques mentioned are restriction, local replacement, and component design. Here are some relevant excerpts:

> Proof by **restriction** is the simplest, and perhaps the most frequently applicable, of our three proof types. An NP-completeness proof by restriction for a given problem $\Pi \in \mathrm{NP}$ consists of simply showing that $\Pi$ contains a known NP-complete problem $\Pi'$ as a special case.
>
> In proofs by **local replacement**, the transformations are sufficiently nontrivial to warrant spelling out in the standard proof format, but they still tend to be relatively uncomplicated. All we do is pick some aspect of the known NP-complete problem instance to make up a collection of *basic units*, and we obtain the corresponding instance of the target problem by replacing each basic unit, in a uniform way, with a different structure. The transformation from SAT to 3SAT is of this type.
>
> Our last type of proof, and the one that tends to be the most complicated, is **component design**. The NP-completeness proofs for 3-DIMENSIONAL MATCHING, VERTEX COVER, and HAMILTONIAN CIRCUIT are typical examples of this type of proof. The basic idea is to use the constituents of the target problem instance to design certain "components" that can be combined to "realize" instances of the known NP-complete problem.

What exactly are those "basic units" and "components"? I was trying to find some literature about those strict and formal definitions, but couldn't find any.

For restriction, can it be defined as a bijection from instance of one problem to another?

# Answer
A basic misconception about mathematics is that it is a purely formal game. Promulgated by the formalist school, we are taught that all that matters in mathematics are formal proofs. Yet in practice, completely formal proofs almost never get written; and mathematical thought has a strong informal component. In order to get further in mathematics, you need to understand mathematical concepts intuitively rather than just formally. A formal proof might be the end result, but the thought process is more liberal.

Furthermore, mathematicians are interested in things beyond definitions, theorems and proofs: key insights are sometimes more interesting than the proof itself or the result being proved. The philosophy behind the proof uncovers a deep truth which reaches much beyond the proof itself.

Such is the case here. Garey and Johnson are explaining how they conceive of NP-completeness proofs. They describe three basic types:

1. Proofs by *special case*: If a special case of a problem is NP-hard, then so is the original problem. For example, if 3-coloring is NP-hard, then the $k$-coloring problem (with $k$ a parameter) is also NP-hard. This can in principle be modeled formally by using very weak reductions — in this case, to reduce 3-coloring to $k$-coloring, it might suffice to use an $\mathsf{NC^0}$-reduction.

In contrast to what you write, this is certainly not a *bijection*, since when $k \> 3$, the correspondence is less direct.
2. Proofs by *gadget reduction*: These are proofs in which each "basic unit" of the original instance is replaced by a "gadget" in the new instance. For example, when reducing SAT to 3SAT, we replace a clause $\ell\_1 \lor \cdots \lor \ell\_n$ by the clauses $\ell\_1 \lor \ell\_2 \lor x\_2$, $\lnot x\_2 \lor \ell\_3 \lor x\_3$, ..., $\lnot x\_{n-2} \lor \ell\_{n-1} \lor \ell\_n$.

*Basic unit* is a completely informal concept. It doesn't have a formal definition. It is supposed to help you conceptualize this kind of proof. Garey and Johnson give several examples, which might help you in constructing similar NP-hardness proofs.
3. Proofs by *indirect gadget reduction*: These are proofs in which several "components" of the original instance are replaced by several kinds of gadgets. For example, when reducing from SAT, we might have different gadgets representing variables and clauses, which are connected together in an appropriate way.

Once again, *component* is a completely informal concept. The difference between direct gadget reduction and indirect gadget reduction is significant in our mind, but cannot necessarily be described formally.

This description is useful since it covers many NP-hardness proofs, and even other hardness proofs such as PSPACE-hardness. Understanding these techniques is helpful for coming up with new hardness proofs. However, in no way is this case distinction supposed to be formal. It is just a mental aid.
> 6 votes

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


title: using 2 short CRC(s) VS one longer CRC

text:
# Question
Title: using 2 short CRC(s) VS one longer CRC
I'm doing some research on the CRCs, but i can't find informations about the use of two (or more) short CRCs compared to the use of a longer CRC:

Suppose that i have a dataword A of some length and 3 different generator polynomials, 2 of degree 8 and one of degree 16. These polynomials are used respectively by CRC1, CRC2 and CRC3 algorithms, where CRC1 and CRC2 generate 8-bit codes while CRC3 generates 16-bit codes.

Suppose also that the three CRC have the same Hamming Distance for datawords of the same size.

now consider these 2 options:

1. Compute CRC1(A)=x1 and CRC2(A)=x2 and use codeword A|x1|x2 (where '|' means concatenation);
2. Compute CRC3(A)=y and use codeword A|y;

what are the eventual advantages and disadvantages of the first approach in respect to the second considering **error detection capabilities**?

Please provide also some references if you have them!

# Answer
> 1 votes
Ok, i found what i was searching in a paper "Selection of Cyclic Redundancy Code and Checksum Algorithms to Ensure Critical Data Integrity" https://www.faa.gov/aircraft/air\_cert/design\_approvals/air\_software/media/TC-14-49.pdf

in Section 5.7 we can read that: "*\[...\] Based on the results of this study and a literature review, there is no evidence that multiple error codes on the same dataword increase HD. However, adding more bits of error-detection code does tend to increase the coverage at that HD by creating more bits that must be randomly matched to form a valid codeword. Quantifying such a gain requires careful analysis of common-mode undetected error patterns for the multiple error coding schemes used, with a caution that pure mathematical analysis is prone to subtle errors and should always be validated via Monte Carlo simulation.*"

So the answer to my question is that it's impossible to select the best option unless they have been evaluated through mathematical analysis and subsequent experimental validation :(

---
Tags: coding-theory, crc
---


# Question
Title: Converse of pumping lemma for regular expressions
I want to come up with a language that satisfies the pumping lemma while not being a regular expression.

I thought of $\\{0^i1^j: i \> j \> 0\\} $. The pumping seems to work just fine, and this is not a regular expression, as it would not be possible to create an automata that recognizes it. This last part is where I'm having a bit of trouble, as I think I have the right idea, but can't formalize it. This language is just a regular expression $\big(\\{0^i : i \in \mathbb{N}\\}\big)$ concatenated with something that is not a regular expression $\big(\\{0^i1^i: i \in \mathbb{N}\\}\big)$.

Is my thought process correct? Can this be generalized? If $L$ is a RE and $L'$ is not, then $LL'$ is also not a RE? I believe so, because we know that if $L$ is a RE then so is $L^r$. And so we end up with $(L')^rL^r$, and we can use the contrapositive of the pumping lemma to prove this language is not regular. Any insight would be helpful!

# Answer
Yes, $L\_\>=\\{0^i1^j: i \> j \> 0\\} $ is a non-regular language.

However, it does not satisfy the pumping lemma for regular languages. Assume for the sake of contradiction that $p$ is a pumping length for $L\_\>$. Consider $w=0^{p+1}1^p$. Let $w=xyz$ with $|y|\>1$ and $|xy|\<p$. Then $y$ contains 0 only. There is no more 0's than 1's in $xy^0z=xz$. That contradicts that $p$ is a pumping length.

The most we can say is that all words in $L\_\>$ can be pumped up.

> If $L$ is a RE and $L'$ is not, then $LL'$ is also not a RE?

No. A simple counterexample is $L=\Sigma^\*$, the language of all words while $L'$ is any non-regular language that contains the empty word such as $\\{a^{n^2}\mid n\in \Bbb N\_0\\}$. $LL'$ is still the language of all words, which is regular.

**Exercise 1.** Find two languages $A$ and $B$ such that

* $A$ is regular
* $B$ is not regular
* $A\subsetneq B$
* $AB$ is regular.

**Exercise 2.** Find a non-regular language that satisfies the pumping lemma for regular languages.
> 3 votes

# Answer
For a language that isn't regular, but satisfies the pumping lemma, take:

$$ L = \\{a b^r c^r \colon r \ge 1\\} \cup \\{a^r b^s c^t \colon r \ne 1 \wedge s, t \ge 1\\} $$

Given $\sigma = a b^r c^r$, you can pump the starting $a$, the result is always in $L$. Given a string that starts with no $a$, you can pump some starting $b$s; if it starts with 2 or more $a$, you can repeat the first two $a$s at will.

Suppose $L$ is regular. Then $L \cap \mathcal{L}(a b^\* c^\*) = \\{a b^r c^r \colon r \ge 1\\}$ is regular, but an easy use of the pumping lemma shows this not to be the case.
> 1 votes

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


# Question
Title: On which stage (lexical analysis, syntax analysys, and so on) is most of the compilation time spent?
I know that during compilation we need to undergo several stages like lexical analysis, syntax analysis and so on. Which of them takes the most time?

# Answer
For a few compilers I've seen compilation times was reduced 3+ fold when optimization was disabled, so otherwise they spent most time on optimization passes.
> 1 votes

---
Tags: compilers
---


title: Relaxation of the knapsack constraints

text:
# Question
Title: Relaxation of the knapsack constraints
A set $\mathcal{A}$ is the relaxation of another set $\mathcal{B}$, if $\mathcal{B} \subseteq \mathcal{A}$.

I have a set of points defined as the knapsack constraint

$$ \mathcal{X} = \\{x \in \mathcal{Z}^n: w^{\top}x \leq b \\} $$ where $\mathcal{Z}^n$ is the n-dimensional 0-1 vectors and $w \in \Re^n\_+$ and $b \in \Re\_+$.

I read that one possible relaxation of the above set is $$ \mathcal{X} = \\{x \in \mathcal{Z}^n: \lfloor w\rfloor ^{\top}x \leq \lfloor b\rfloor \\} $$

where $\lfloor \rfloor$ represents the floor function.

It is very counter-intuitive to me. $w^\top x \leq b$ represents a half space with left or lower space of the hyperplane defined by $w^\top x = b$. By taking the floor function, we are in fact moving the hyperplane lower and shrinking the size of the set.

Can anyone explain to me why the floor function terms represent a relaxed set ?

# Answer
> 2 votes
Let me call $ \mathcal{X}\_1 = \\{x \in \mathcal{Z}^n: w^{\top}x \leq b \\} $ and $ \mathcal{X}\_2 = \\{x \in \mathcal{Z}^n: \lfloor w\rfloor ^{\top}x \leq \lfloor b\rfloor \\} $ to avoid confusion.

Let $x \in \mathcal{X}\_1$. Then: $$b \ge w^T x = \sum\_{i : x\_i = 1} w\_i$$ which implies: $$\lfloor b \rfloor \ge \left\lfloor \sum\_{i : x\_i = 1} w\_i \right\rfloor \ge \sum\_{i : x\_i = 1} \lfloor w\_i \rfloor = \lfloor w \rfloor^T x.$$

Therefore $x \in \mathcal{X}\_2$, and this shows that $\mathcal{X}\_1 \subseteq \mathcal{X}\_2$.

---
Tags: linear-programming, knapsack-problems
---


# Question
Title: Overlaying Two Matrices So That Sum Of Squared Differences Is Minimized
I have a question about my solution to a problem from Hackerrank. The problem is, given $R,C,H,W$ with

* $1\le R,C\le 100$,
* $1\le H\le R$,
* $1\le W\le C$,

an $R\times C$-matrix $L$ and an $H\times W$-matrix $S$, to find $i,j$ with $0\le i\le R-H$ and $0\le j\le C-W$ which minimize the sum $$\sum\_{0\le k\< H,0\le l\< W}(L\_{i+k,j+l}-S\_{k,l})^2$$ (where I use 0-based indexing).

My first attempt, which performed best, was to try out all $i,j$, store the best result so far in a variable, and stop calculating each sum as soon as it exceeds the best result from the previous runs.

Then I thought of something else (which unfortunately didn't perform that well): I want to run all the sums in parallel and advance those first which look most promising for returning a small result. So I make a list containing $\[i,j,c,m,p\]$ for all $i,j$, where $c$ stores how many indices I already calculated of the sum, $m$ stores the intermediate value of the sum and $p$ stores the interpolated value of the finished sum (scaled by $HW$), which I set as $m/c$ for $c\>0$ and some arbitrary $x$ else. So in the beginning all elements will look like $\[i,j,0,0,x\]$. I will then advance the first element of the list, which means I increment $c$ by one, $m$ by a new square and then recalculate $p$. Afterwards I move the first element upwards so that the list is always sorted by $p$. I also keep track of the best finished sum so far together with its $i,j$-indices. If the new first element is a finished sum ($c=HW$) then I throw it away (and possibly update the best result). After the list is empty, the indices of the best result get returned.

I guess the resorting process takes too much time for this to perform well. I also tried using for $p$ a different function $f(m,c)$ which puts more emphasis on $c$ so that less resorting takes place. If $f(m,c)=1/c$ and $x\>1$, this gives roughly the first algorithm I described, with the good performance.

My question: Is this idea any reasonable? If yes, what values for $f(m,c)$ (and possibly $x$) could yield better performance than $1/c$?

# Answer
> 0 votes
I try to summarize the results of the discussion in the comments:

* Using a heap instead of a list would be better suited for the proposed idea since all operations to be performed on the list are sorting, returning the smallest element and changing an element followed by resorting the list. These are almost exactly the operations supported by heaps, which will deliver better performance.
* The sums $\sum\_{k,l} (L\_{i+k,j+l}-S\_{k,l})^2$ can be expressed as $A\_{i,j}+B\_{i,j}-2C\_{i,j}$ where $A\_{i,j}:=\sum\_{k,l} L^2\_{i+k,j+l}$, $B\_{i,j}:=\sum\_{k,l} S^2\_{k,l}$ and $C\_{i,j}:=\sum\_{k,l}L\_{i+k,j+l}S\_{k,l}$. Here $B\_{i,j}$ does not depend on $i,j$ and $A\_{i,j}$ can obtained from its predecessor $A\_{i',j'}$ by only updating two rows or columns, if the order in which the $i,j$ are perused is chosen wisely. Most importantly, $C\_{i,j}$ describes a convolution, which can be calculated very fast by FFTs, convolution in the frequency domain corresponds to (pointwise) multiplication in the time domain! But even without implementation of FFT, this algorithm scores better than the naive approach, as it only performs one operation (multiplication) instead of two (subtraction and squaring) in the large (size $HW$) sums.

---
Tags: algorithms, algorithm-analysis, matrices
---


# Question
Title: Minimization of idle time with two kinds of actors
Let's say I have 2 different types of machines responsible for 2 different duties.

I have the PRODUCTION\_MACHINES that EACH are able to produce a single unit of goods within 2 hours.

Then I have TRANSPORTER\_MACHINES which are EACH able to collect and package away a single unit of goods from the production line at 95 seconds per TRANSPORTER\_MACHINE.

QUESTION:

Assuming there are 5 PRODUCTION\_MACHINES working, and they are operated at different starting times, how many TRANSPORTER\_MACHINES do you need in order to MINIMIZE the IDLE\_TIME incurred in the production process ?

(Whereby "IDLE\_TIME" is defined as the time expended by EITHER the PRODUCTION\_MACHINE or a TRANSPORTER\_MACHINE waiting to have its good collected or produced.

HINT: Too many TRANSPORTER\_MACHINES will add to the idle time as there are prone to be extra TRANSPORTER\_MACHINES idly waiting for struggling PRODUCTION\_UNITS to produce quickly enough to keep up with DEMAND.

... and vice-versa, too few TRANSPORTER\_UNITS will also increase the idle time, this time for the PRODUCTION\_MACHINES as some of them will have to wait for the struggling TRANSPORTER\_MACHINES to keep up with their SUPPLY.)

Thank you very much !

# Answer
Observe that it takes a PM about 75 times as long to produce a widget as it takes a TM to clear that widget and let it start producing the next widget. And we have only 5 PMs.

Intuitively, it seems like we should have only one TM. It will be idle almost all the time, waiting for one of the PMs to finish. The PMs will be busy almost all the time, except right after they finish a widget and have to wait for the output to be cleared away.

Adding more TMs would simply add more idle time for them, while reducing the PM idle time by very little at best. Removing the sole TM would leave all of the PMs idle as soon as each of them finishes the first widget.

If the times were more similar, or the number of PMs were closer to 75, finding the answer would be more complex. This problem seems to be designed for a simple, intuitive answer.
> 1 votes

---
Tags: optimization
---


# Question
Title: What is the intuition behind the relationship between space and time for an algorithm?
I believe I have heard that you can never have more space than the algorithms running time. I could be wrong, maybe other way around. What is the intuition behind this?

# Answer
A Turing machine moves the tape by one space per time unit. Worst case, if all moves were in the same direction, the space used would be exactly the same as the time used.
> 0 votes

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


title: Which is the correct XOR Gate Symbol

text:
# Question
Title: Which is the correct XOR Gate Symbol
I'm confused between 2 XOR gate symbols, they have a minor difference but I'd still like to know if they truly are identical.

One looks like -

The other, like

Notice, how for one of them the input lines are connected all the way and for the other, it's not. Are they both identical, as I suspect or is there something I'm not aware about?

# Answer
> 3 votes
There is a standard for this, ANSI/IEEE Std 91a-1991. The second version is what that standard gives for the "distinctive shape symbol" (5.1-11). So if you want to know what one is "correct", it's arguably that.

The other version is not the standard, but it's extremely common and everyone knows what you mean by it. But it's not distinct.

# Answer
> 0 votes
This is akin to asking if $B$ and $\mathcal{B}$ are really the same letter and, if not, which is correct. It makes no difference.

---
Tags: boolean-algebra
---


title: What is a trivial language?

text:
# Question
Title: What is a trivial language?
I have heard the quote "L is a trivial language" What does this mean and how do we relate this to Turing machines and complexity theory?

# Answer
A trivial language is one that has no strings, or one that has every string in some alphabet.

In terms of models of computation, a trivial language is one that can be decided by a Turing Machine or lambda function that completely ignores its input.
> 4 votes

---
Tags: turing-machines
---


title: Böhm-Jacopini theorem

text:
# Question
Title: Böhm-Jacopini theorem
I had a discussion with a friend developer and teacher. He told me about the Structured program theorem arguing that this theorem is one of the most important to know about. However, I have never heard about it and I don't understand how it may have deeply contributed to the computer theory. It seems quite cited in academic papers though.

# Answer
> 4 votes
I had never heard about it before, but taking a quick look at it I can understand why it is considered so important.

Basically, being able to prove that any program can be implemented via three basic operations (sequence, seletion, iteration) allows for simpler formalization when designing a new programming language.

It's basically a one-to-one correspondance to a Turing machine programme, therefore you can easily prove your programming language to be Turing complete.

---
Tags: algorithms, turing-machines
---


# Question
Title: Why is subarray $A[p..k-1]$ empty when $k=p$?
I'm working through a proof of correctness for merge sort.

I'm given a loop invariant for a for loop, which makes reference to a subarray $A\[p..k-1\]$. During the initialization step of the correctness proof, my textbook says "Prior to the ﬁrst iteration of the loop, we have $k=p$, so that the subarray $A\[p..k-1\]$ is empty".

In other words we're saying $A\[p..p-1\]$ is empty. Suppose $p=1$, then it's saying $A\[1..0\]$ is empty. Why is this considered empty? Is it just an axiom that subarray $A\[a..b\]$ is empty if $a\>b$?

# Answer
It's a convention. One reason for the convention is that the length of an array $A\[i..j\]$ is $j-i+1$, so if $j=i-1$, we should get an array of length zero. Due to this reason, we sometime consider $A\[i..j\]$ to be undefined when $j \< i-1$; in other cases, the issue does not arise, and $A\[i..j\]$ is just the empty array whenever $j \< i$. In yet other cases, we do not want to allow empty arrays, and then $A\[i..i-1\]$ is undefined as well.

Since these conventions are not standard (indeed, they are conflicting), if one of them is used, it should be announced beforehand, or when it occurs.
> 2 votes

# Answer
Yes, you may consider this as axiom. Or try to make a definition that still works for `a > b` case - most probably it will give you an empty array in this case. For example, "all elements with indexes `i >= a` and `i < b`".
> 1 votes

# Answer
A\[i..j\] is a convention. We could define it any way we like, but we define it in a way that gives useful results.

One property is that if we reduce the right index by 1, then we lose the rightmost element. For example, going from A\[5..10\] to A\[5..9\] we lose element 10. So what is A\[i..i\] and what would you expect going from A\[i..i\] to A\[i..i-1\]?
> 1 votes

---
Tags: algorithm-analysis, arrays, correctness-proof, notation, mergesort
---


# Question
Title: Difference between encoding and modulation in transmission
What is the difference between encoding and modulation?

I have seen these terms used sometimes inter-changeably and sometimes differently (the ratio is 50:50).

Can somebody clearly explain this with some non-technical and technical examples both? I have searched this a lot on net and in the end I end up scratching my head.

# Answer
> 3 votes
Modulation: Way to send signals (information) from one place to another. exanmple: you have a carrier wave like a sine wave and your Information signal 10101010 or any analog signal you want to transmit. You simply just change the properties of carrier wave with respect to your signal. Like: AM, FM, ASK, PSK, QAM

Encoding: Somthing else than modulation. It is representation of data. Example: 5Volts could be 1 or 0 according to logic (examples are Unipolar encoding, Bipolar Encoding).

# Answer
> 3 votes
Encoding is about assigning different binary codes according to a particular algorithm.

Modulation is about changing the properties of one signal value according to a certain properties (Amplitude, Phase, or Frequency) of another signal.

# Answer
> 2 votes
In *Fourier analysis* we realized that we could represent any kind of periodic functions with sine and cosine functions.
Signals are functions that represent a variable with respect to another variable that is usually time.
So instead of sending different signals (data) over and over again we could think of them all as sine functions with some differences, so we define a sine signal called *carrier* and when we want to send data that could be represented as periodic signals and therefore as sine waves, we would change some properties of the carrier signal so that it is equivalent to our signal. on the other end the carrier signal would be created and they compare the incoming changed (modulated) signal with the carrier one and so extract or detect the main signal thus the data.
The representation of the data using different kind of signals is called encoding, but mounting signals on sine waves known as carrier signals in order to transmit them in a better way is called *modulation* as *modulate* itself means mounting.

---
Tags: terminology, computer-networks
---


# Question
Title: need for an example of synchronous but non periodic interrupt
I know that synchronous interrupts are interrupts that occur with a clock tick (after finishing an instruction) and I think that periodic if they happen in every n ticks of the clock. To get a better grasp of understanding periodic interrupts I tried without success to find a synchronous but non periodic interrupt. would appreciate your help :)

# Answer
> 0 votes
I think that if a process makes itself sleep then the interrupt when the alarm will wake him up will be such an interrupt.

---
Tags: os-kernel
---