# Question
Title: Constant-depth threshold circuit for $\mathrm{PP}$
Is it proven that $\mathrm{PP}$ has uniform constant-depth threshold circuit?

# Answer
> 2 votes
Yes, Anuj Dawar and Yuguo He claim in their paper titled "Parameterized Complexity Classes uder Logical Reductions" \[1\] that $\mathrm{SAT}$ is $\mathrm{NP}$-complete, even under quantifier-free first-order projections, which are reductions even weaker than $\mathrm{AC}\_0$ reductions.

The same result also holds true for $\mathrm{PP}$ with $\mathrm{MAJSAT}$.

First-order projection can be done in constant depth.

All that is left to be shown is proving that $\mathrm{MAJSAT}$ can be decided in constant depth. Indeed, our threshold circuit for this language has an overall $\mathrm{MAJ}$ gate as the output gate that receives the result from exponentially many result of every possible assignment to the variables of the given 3-$\mathrm{SAT}$ formula. And for each variable assignment, we can, in constant depth, evaluate the formula with this assignment.

\[1\] Anuj Dawar, Yuguo He, **Parameterized Complexity Classes uder Logical Reductions**, https://www.cl.cam.ac.uk/~ad260/papers/mfcs09.pdf

---
Tags: complexity-theory
---


# Question
Title: Context formal language recognizing even number of 0's and odd number of 1's
I have an assignment, it's asked to write a context free grammar recognising the language $L=\\{ w \mid w\text{ has an even number of }0\text{s and an odd number of }1\text{s}\\}$, over the alphabet $\\{0,1\\}$.

My first guess was:

$$ \begin{align} S &\rightarrow A1A\\ A &\rightarrow A0A0A \mid A1A1A \mid \varepsilon \end{align} $$

But I realized it's wrong, since, for example, it doesn't accept the string $01011$ (I think my CFG forces pairs of $0$s).

Any suggestion?

# Answer
This language is, in fact, regular – it is accepted by an automaton with just four states. I suggest that you first figure out what this automaton is and use what you learn to figure out a grammar. In particular, you don't need any context-free "tricks" or techniques.

If you need to, mouse-over the yellow area below to see a more detailed hint for the automaton.

> Think about what data you need to know when you reach the end of the string, in order to decide if your input is in the language. What is the value of that data when you haven't read any input? How do you update that data as you read the input?
> 2 votes

---
Tags: formal-languages, automata, context-free, formal-grammars
---


# Question
Title: Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$
$\mathrm{NP}$ has not been separated from constant-depth circuits consisting of solely $\mathrm{Mod}\_6$ gates. So, the question is whether current techniques are enough to deduce interestingly unintuitive consequences of that bizarre claim.

# Answer
> 1 votes
Even a weaker claim that $\mathrm{DLogTime}$-$\mathrm{uniform}\\:\mathrm{AC\_2^0}=\mathrm{L}$ readily implies $\mathrm{NP}= \mathrm{PSPACE}$

First, $\mathrm{NP} = \mathrm{EXP}$-$\mathrm{AC\_2^0}$ by using a similar argument in this answer. Here, I mean constant-depth $\mathrm{AC}^0$ circuit of depth at most $2$. And, $\mathrm{PSPACE} = \mathrm{EXP}$-$\mathrm{L}$, if you are willing to abuse the notation.

Second, since the mentioned above answer does not describe in details the uniformity of the first-order reduction. I move on to prove the $\mathrm{\mathrm{DLogTime}}$-$\mathrm{uniformity}$ of the standard Cook proof.

That is we need to establish a $\mathrm{DLogTime}$ constructor that constructs a constant-depth circuit, for each input length. And the constructed constant-depth circuits then receives arbitrary input (of given length) and always output correctly.

Indeed, Cook proves completeness of $\mathrm{SAT}$ by using a big **tableau**.

From the second row of the tableau on, every cell can be computed by a constant-size formula of "nearby" cells of previous row. So, these can be printed as constant output node of the constructed constant-depth circuit. This can be called *hard-coded*. So, **almost all of the constructed constant-depth circuit are merely constant output nodes**.

We only need to deal with the first row. **This part of the constructed circuit needs to take the actual input bits as its own designated input gates**. So, **it requires some more indexing work of the constructor**. It is worthy mentioning that these actual input bits does not contribute to the variable of the formula output by our constructed circuit (the circuit is a *constant-depth reduction, not a decider*). This very first part of the constructed circuit can be constructed by the $\mathrm{DLogTime}$ constructor easily. What really makes it into variables of the formulae that will be reduced to by our constructed circuit are the nondeterministic guess bits (also called the witness if you prefer the verifier-style definition of $\mathrm{NP}$). **This *witness* part can also be printed out as constant output gates of the constructed circuit.**

Back to your question, we can easily adapt the above argument to deduce that the strange consequence of $\mathrm{DLogTime}$-$\mathrm{uniform}$ $\mathrm{Mod}\_6^0 = \mathrm{NP}$ is that $\mathrm{Mod}\_6PH = NEXP$. If someone can prove that $\mathrm{Mod}\_6P$ is low for itself like $\oplus P$ then the consequence can be strengthened to $\mathrm{Mod}\_6P = NEXP$

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


title: Minimum commands to reach an value

text:
# Question
Title: Minimum commands to reach an value
Sorry if I am doing it wrong in some way.

Some days ago I have passed trough an technical test in which I had 3 tasks to complete. The tasks were a problem and I have to write an algorithm to solve it.

One of the 3 tasks I could not complete. Really, I have absolutly no idea how to start.

**I am not asking for ready algorithm here.**

I'll try to reproduce here.

---

```
Command 'X': X = ( 2 * X ) - Y
Command 'Y': Y = ( 2 * Y ) - X
Initial values: X = 0, Y = 1;

```

Given a N number, what's the minimum of commands where X or Y reach N. Each command change it's own value.

If I send the command 'X', the value of X will be '-1', and so on

The exemple was N = -11 Commands: 'X','X','Y','X', this way X will be equal -11.

```
Command 'X', X = ( 2 * 0 ) - 1 = -1  , Y = 1
Command 'X', X = ( 2 * ( -1) )  - 1 = -3  , Y = 1
Command 'Y', X = -3                  , Y = ( 2 * 1 ) - (-3) = 5
Command 'X', X = ( 2 * -3 ) - 5 = -11, Y =5

```

# Answer
Here are some thoughts about the task.

1. Let us start with reducing all power of 2 from N. If $N=2^kM$ then we can first apply $$Y=2Y-0$$ $k$ times.

Now you have new task of reaching smaller number $M$ starting with $X=0$ and $Y=1$.

2. $X\le 0$ and $Y\>0$ holds after every transformation. So if $N$ is positive we will reach it with $Y$ and if $N \le 0$ we reach it with $X$.
3. Replacing $X$ with $X'=-X$ may help thinking. $$ X' \to 2X'+Y $$ $$ Y \to 2Y+X' $$ looks simpler and is equivalent to the original task.
4. Applying one operation $k$ times we get $$ Y \to 2^kY+(2^k-1)X' $$
5. Another nice representation of the operations: $$ X' \to X'+(X'+Y)$$ $$Y \to Y + (X'+Y)$$
6. From 5. after $k$ steps sum of the numbers becomes $2^k$ and we actually add $2^{k-1}$ to one of numbers.
7. **Solution**. There is always only one way to reach $N$. Number of operations is $log\_2N$. Imagine $N=101110001$ in binary form. Then we go from right to left and change X when there is 0 and Y when there is 1 in binary representation. In this way we finally construct $Y=101110001$ and almost inverted X=01000111**1**. There is only one peculiarity. When we start for the first bit Y is already 1 and we need to apply X transformation instead of Y.
> 1 votes

---
Tags: algorithms
---


title: Need help converting machine code

text:
# Question
Title: Need help converting machine code
I would appreciate some help with this question.

The 32 bit numbers below represent a MIPS instruction. identify the different fields and state which instruction it is. give the assembler source code that can be converted into this instruction.

001000|10001|10010|0000000000001111

I separated the bits and I know the first 6 bits are the opcode and given the opcode it means Addi. The last 16 bits are the immediate value which I have converted to 15. I do need help with the registers and converting the binary into the register number. I have looked everywhere and can not find an explanation. Any help would be appreciated. i know the structure takes this format:

Addi, t,s, 15

# Answer
You've basically got the answer already: the *s* register is number `0b10001` = 17, the *t* register is number `0b10010` = 18.

The instruction is not quite the way you've said it: standard MIPS has the registers in the opposite order, so it's `opcode rs rt immediate`. The opcode is `0b001000` = 8 = `ADDI`; `rs` is `0b10001` = 17 = `$s1`; `rt` is `0b10010` = 18 = `$s2`; the immediate value is `0b0000000000001111` = 15.

(The prefix `0b` indicates that the following number is in binary.)
> 0 votes

---
Tags: binary, mips
---


# Question
Title: Are $AC^{0}$ algorithms interesting to research communities?
I have seen many research papers with log space algorithms, but not many with $AC^0$ algorithms. Is there any reason for this.

**Question :** Are $AC^{0}$ algorithms interesting to research communities?

# Answer
$\mathsf{AC^0}$ algorithms are quite weak. For example, $\mathsf{AC^0}$ cannot compute parity or majority. However, it can compute approximate majority, as shown by Ajtai; see Viola, On Approximate Majority and Probabilistic Time, for a better construction and for references to Ajtai's work.

$\mathsf{TC^0}$ is a slightly stronger class, also consisting of polynomial size circuits having constant depth, but allowing threshold gates. Such circuits can compute division, as shown by Hesse, Division is in Uniform $\mathsf{TC^0}$, improving on works of others (starting with Beame, Cook and Hoover). The related problem of iterated integer multiplication is also in $\mathsf{TC^0}$.
> 1 votes

---
Tags: algorithms
---


# Question
Title: VC dimension of finite unions of one-sided intervals
What is the VC dimension of $k$ finite unions of one-sided intervals:

If we take 3 one-sided intervals like $(-\infty, a\_1\] $, $(-\infty, a\_2\] $ and $(-\infty, a\_3\] $, I think union of these intervals can shatter $4 $ points as below, assuming that $a\_1\>a\_2\>a\_3\>a\_4$:

* Point $p\_1$ at interval $(-\infty, a\_1\]$
* Point $p\_2$ at interval $\[a\_1, a\_2\]$
* Point $p\_3$ at interval $\[a\_2,a\_3\]$
* Point $p\_4$ at interval $(-\infty, a\_3\]$

For $k$ finite unions I think answer is $k+1$, am I right?

# Answer
> 1 votes
Finite unions of one-sided intervals can shatter only 2 points, because as said by @YuvalFilmus in comments the union of Finite unions is a single one-sided interval, and a single one-sided interval can shatter only 2 points.

---
Tags: machine-learning, learning-theory, vc-dimension
---


# Question
Title: Is it possible to give a guarantee about the accuracy of the local time?
Assuming there is no attack/bug and I use NTP: Are there any formal guarantees about the accuracy of the local time? Can there be any over the network?

Even if the communication is going directly between the time server (stratum-1) and the client, I have no idea if the devices / protocols on OSI layer 1-4 have time guarantees.

Maybe something like the following can be guaranteed: With a probability of 99% the currently set local time is off by less than 20ms.

(I've added the "cryptography" tag as certificates are also only valid for a given time - in this case it would be important to have a guarantee even with a possible attacker)

## What I found

> Clock synchronization at the 10 millisecond level over long distance wide-area networks (WANs) (2000 km), and at the 1 millisecond level for local-area networks (LANs), is routinely achieved.

Source: Cisco, Network Time Protocol: Best Practices White Paper. 2008.

# Answer
> 0 votes
No. No guarantee is possible. The network latency could have arbitrarily high variance, in which case NTP might be arbitrarily inaccurate.

---
Tags: computer-networks, cryptography, communication-protocols
---


title: Weakest reduction for 3-$\mathrm{SAT}$

text:
# Question
Title: Weakest reduction for 3-$\mathrm{SAT}$
Having read all these posts

Constant-depth threshold circuit for $\mathrm{PP}$

Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}\_6}^0=\mathrm{NP}$

I wonder about the weakest possible reduction for 3-$\mathrm{SAT}$ to be complete for $\mathrm{NP}$?

# Answer
Having read all your answers to my questions, I come to the ultimately weakest reduction for 3-$\mathrm{SAT}$

The weakest reduction is $\mathrm{NC}\_0^0$. This reduction does not use even $\mathrm{NOT}$ gate. Absolutely, almost nothing at all.

Consider the very first part of the very first row in your answer here. As you mentioned there, this only needs some indexing work of the $\mathrm{DLogTime}$-constructor. It turns out that all that is needed to be done is to put $\lnot$ symbol to the soon-to-be-reduced-to formula by copying the actual input bits themselves.

In particular, consider the 10th cell $c\_{10}$ of the first row, this cell is equal to $x\_{10}$ i.e. the 10th bit of the actual input.

Depending on whether $x\_{10}$ is 0 or 1, the corresponding clause will be:

$$ \lnot c\_{10} \lor \lnot c\_{10} \lor \lnot c\_{10} $$

or

$$ c\_{10} \lor c\_{10} \lor c\_{10} $$

All the $c\_{10}$'s are hard-coded similarly as the rest of the constructed constant-depth circuit. The $\lnot$ or nothing (actually a dummy symbol in the soon-to-be-reduced-to formula) is copied from the actual input bit $x\_{10}$.

So, the weakest reduction is $\mathrm{NC}\_0^0$. It copies the input bits to some output gates of the constructed **0-depth circuit**. All the other output gates of the constructed **0-depth circuit** are constantly hard-coded.
> 0 votes

---
Tags: reductions
---


title: Computer architecture pipelining

text:
# Question
Title: Computer architecture pipelining
```
LOOP:LW    R1,0(R2)
     ADDI  R1,R1,#1
     SW    R1,0(R2)
     ADDI  R2,R2,#4
     SUB   R4,R3,R2
     BNEZ  R4, LOOP

```

If we want to move an instruction into a branch delay slot what will be that instruction and the schedule of the instructions?

In the solution they have brought `SW R1,0(R2)` into the branch delay slot like this:

```
LOOP:LW    R1,0(R2)
     ADDI  R2,R2,#4
     SUB   R4,R3,R2
     ADDI  R1,R1,#1
     BNEZ  R4, LOOP
     SW    R1,0(R2)

```

But according to me it will change the meaning of the program since `R2` will be incremented by 4 before storing the word. Can anyone clear this?

# Answer
There is an instruction already in the branch delay slot - it's just not displayed. So unless that instruction that isn't displayed is a NOP instruction, it will not be executed anymore if the branch is performed, so the meaning of the program has changed. Unless the question is "here is the code for a processor without branch delay slots, modify it for a processor with branch delay slots". In which case the *obvious* solution is to just move the last instruction before the conditional branch to the branch delay slot.

Independent of branch delay slot, you cannot just move the SW instruction which uses R2 past an instruction that modifies R2. In this case, you can move it if you modify it: R2 is increased by 4, so you can use the address -4(R2) instead of 0(R2).

In general, you initially don't care about branch delay slots and write code as if there were no branch delay slots, and add a NOP after each conditional branch, so you have correct code.

Then you move instructions into the branch delay slots, but carefully: You mustn't move an instruction if there is a branch to the conditional branch (because that instruction would be wrongly executed when branching to the conditional branch). You can't move certain instructions, like branches, returns, calls. And you can't move an instruction that was already moved. Say x = 0, branch if zero, not, branch if not zero, not. You can move the x = 0 into the first branch delay slot, but you mustn't move it into the second one.
> 1 votes

# Answer
Yes, moving an instruction must **not** change the meaning of the program. However, as you correctly identified, the `sw` instruction uses R2 which is later being incremented by 4. Thus unless the instruction is changed to `sw R1, -4(R2)` (as suggested by Sai), the altered program may perform differently.
> -1 votes

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


# Question
Title: When do we need U(n+2) to solve a problem that can be formulated in U(n)?
I understand the need for a universe hierarchy, and that each new level brings additionnal proof-theoretic strength.

In the HoTT book there are examples of proofs that need to use the next level in the Universe hierarchy.

Do we have examples of inhabited types A:U(n), where the construction of the inhabitants/proof a:A requires the use of U(n+2) ?

# Answer
> 3 votes
This question on the theoretical CS stack exchange asks if pentation is implementable on Church numerals in a predicative variant of System F. In the normal, impredicative system, this is quite easy, because we have:

```
ℕ : Type
ℕ = forall (R : Type). (R -> R) -> (R -> R)

1 : ℕ
1 R s z = s z

hyper : (ℕ -> ℕ -> ℕ) -> (ℕ -> ℕ -> ℕ)
hyper op m n = n ℕ (op m) 1

```

So, because a Church numeral can be instantiated to work on the type of Church numerals, we can easily iterate an operation to get to the next hyper operation.

However, in a predicative system, the quantification over types increases the size of the quantifying type to be larger than the size of the types quantified over. So, a Church numeral that can be instantiated to operate on Church numerals must be one that quantifies over a higher universe.

The person asking the question links to a paper on the functions representable in such a stratified system with $\omega$ universe levels (I.E. one for each natural number). The paper shows that the representable functions are the super-elementary functions, which includes tetration, particular *finite* compositions of tetration, and products and sums of those functions. However, the only reason that all these functions are even representable is that they make use of Church numerals for *all* universes. So, for instance, tetration has a type (something) like:

```
_^^_ : Church 0 -> Church 1 -> Church 0

```

That is, to compute tetration for 0-level numerals, you must make use of higher level numerals. And depending on the complexity of the function, you may have to use much higher levels to compute 0-level numerals (arbitrarily high levels).

I showed in the answer there how if you add even more universes, it is possible to give a uniform type for tetration, which then means pentation can be defined. But now the universes involved are indexed by *transfinite* ordinals (if at all), and you still (seem to) need to go up levels to define some functions on lower (but still very high) levels.

---
Tags: type-theory, dependent-types, homotopy-type-theory
---


# Question
Title: Datastructure for a set of axis aligned rectangles that enables querying for point containment
I am trying to find a reasonable data structure for representing a partition of an (axis aligned) rectangular domain into a set of (axis aligned) rectangles.

I need to be able to look up for a given point which (unique) rectangle contains it.

So far I have taken a look at Quadtrees, and this seems reasonable to me - where I recursively subdivide the domain into patches.

People have also mentioned RTrees, but I do not see how these can help me in such single point queries.

# Answer
> 1 votes
Quadtrees sounds like a good choice.

How about the k-d tree of 2 dimension, which is also explained in a course note and at geeksforgeeks?

Each of the 2-dimensional versions of interval tree, range tree and segment tree may have a fair chance to solve the question efficiently.

I have used all above data structures to solve the same or similar or more complex queries. Depending on your situation, you may want to make some adjustment.

If the number of given points is much smaller than the number of possible points in the given rectangle domain, such as 22000 points in a $10^{18}$ by $10^{18}$ square, then some other choice might be even better. I once used a red-black tree, whose leaf nodes is another red-black tree and whose internal nodes of the same parent represent a partition of the contiguous rows represented by their parent into disjoint contiguous set of rows. The red-black tree at each leaf node stores the points in one particular row. In this way (and with a bit more technique), my final answer is able to run the fastest among all solution to the problem. Of course, my example may not be useful to your situation at all. Well, I hope that might encourage you to develop your own data structure that fits your situation more.

# Answer
> 0 votes
As mentioned in the other answer, quadtrees are a good choice.

R-Trees should also work well, they often cope better with clustered data but they tend to be slower to build or update. If you dataset changes, check out the R\*tree, if you can bulk load it (no changes afterwards), check out the STR-Loaded R-Tree. If your R-Tree does not support point queries, just query for a rectangle which represents a point (all corners have the same coordinate).

If you are using Java, check you my PH-Tree. It's a bit like a quadtree, but copes better with clustered data. For containment queries it's speed depends on the average number of rectangles that contain a search-point. If there are usually few (less than 5-10) rectangles that contain your point, then it may be the fastest three you can find. If you expect 100 or 1000 of rectangles to overlap with your point, R-Trees may be better.

If you want to implement the structure yourself, quadtrees and kd-trees are probably simplest, R-Trees are harder, PH-Tree may be even more difficult to get right. Quadtrees are harder to get right than they look, because for large/clustered datasets you may quickly run into precision problems.

If you are using Java, have a look at my implementations of quadtree, R\*Tree, STR-Tree and PH-Tree here (there is also a kd-tree, but it doesn't suppor rectangle entries, only points).

---
Tags: data-structures
---


# Question
Title: How is the formula for calculation in row/column major obtained?
In my book, this formula is given for calculation of address of row major order's element $\[I,J\]$:

Address of $\[I,J\]$th element in row major order $= B + W\[n(I-L\_r)+ \[J-L\_c\]\]$

where B denotes base address, W denotes element size in bytes, n is the number of columns; $L\_r$ is the first row number, $L\_c$ is the first column number.

A similar formula is given for address in column major order.

I would like to know how this formula is obtained.

# Answer
Row-major order stores the rows of the array one after another in memory. That is, the array

```
a d g j
b e h k
c f i l

```

is stored as

```
a d g j b e h k c f i l

```

To determine the address of an element in this list, we need to know how many elements come before it. For element $\[I,J\]$, this is the number of complete rows above row $I$ times the length of a row, which is $(I-L\_r)\times n$, plus the number of elements before it in the current row, which is $J-L\_c$.

Since the first element is at address $B$ and each element takes $W$ bytes, the addresses of the elements are $B$, $B+W$, $B+2W$, ... and, in general, if there are $k$ elements before you, your address is $B+kW$. For element $\[I,J\]$, we have calculated that $k=n(I-L\_r)+(J-L\_c)$.

For column-major, the argument is basically the same. If you understand the above, it should be easy to adapt it.
> 5 votes

# Answer
**B** is the base address where the first element residents. For simplicity, let's assume that the array indexes start at zero, so $L\_r$ and $L\_c$ are both zero.

So the first element $\[0,0\]$, we have I=0 and J=0, you get `address = B +W[n(0-0)+[0-0]] = B`.

In row major arrays, each element of row i is contiguous in memory, followed immediately afterwards with the elements of row i+1, etc.

So element $\[0,1\]$ comes W bytes after element $\[0,0\]$. Its address = `B+W[n(0-0)+ [1-0]] = B+W`. Similar for each element j in the first row, each element is W bytes past the previous one, so the Jth element is `W*J` bytes from the base address `B`. `Address of element [0,j] = B+W[n(0-0)+[J-0]] = B+W*J`

Each row i+1, contains n elements of W bytes, so row i+1 starts in memory nW bytes after the previous row. Element $\[0,0\]$ is at address B, and element $\[1,0\]$ is at address B+W\*n = B+W\[n(1-0)+\[0-0\]\].

Combining those two concepts, you can find any element \[I,J\] using the formula. The first term in the enclosed sum computes where the row starts in memory relative to the start, and the second term computes where the jth element starts relative to that row.

The terms Lr and Lc just generalize things if your indexes do not start with zero. By subtracting these from the indexes, you are treating the indexes as if they did start with base zero.

Here is an example using C. Notice that we can index element in array a2D using indexes, or your formula. Both work and in fact the C compiler treats them the same.

In C, two-D arrays are stored in memory as row-major. Read this post for a good explanation. Arrays are arranged in memory such that the first row appears first, followed by the second and so on. Each row consists of COL elements, so the way to define this would be:

```
typedef int A2D[ROW][COL];
A2D     a2d  = {0}; // Declares 2D array a2d and inits all elements to zero

```

Then to access the element at row i, column j, use:

```
a2d[i][j]

```

Here is a sample C program to demonstate:

```
#include <stdio.h>
#define ROW 5
#define COL 10
#define Lc  0
#define Lr  0
#define W   sizeof(int)
#define n   (COL)
#define ELEMENT_ADDR(B,I,J) (*((int *)(((void *)B)+ (W)*((n)*(I-Lr)+(J-Lc)))))
typedef int A2D[ROW][COL];

int main(int argc, char** argv)
{
  A2D a2d  = {0};
  int r,c;

  /* Access element using indexes */
  a2d[1][2] = 12;

  /* Access elements using address formula */
  ELEMENT_ADDR(a2d,4,5) = 45;

  for(r=0; r<ROW; r++)
  {
    printf("Row %d: ", r);
    for(c=0; c<COL; c++)
       /* Equivalent to: printf("%2d ", a2d[r][c]); */
       printf("%2d ", ELEMENT_ADDR(a2d,r,c));
    printf("\n");
  }
}

```

This produces the following output:

```
Row 0:  0  0  0  0  0  0  0  0  0  0
Row 1:  0  0 12  0  0  0  0  0  0  0
Row 2:  0  0  0  0  0  0  0  0  0  0
Row 3:  0  0  0  0  0  0  0  0  0  0
Row 4:  0  0  0  0  0 45  0  0  0  0

```

Now the best thing is to get out a piece of paper, draw out this array as it is laid out in memory assuming 4 bytes per int, and see if you can reproduce the calculations to find the addresses of some array elements.

Try it again using different size elements, and with $L\_r$ and $L\_c$ set to values other than zero.

I noticed that you included the label Java but I provided an answer in C.

**Why?**

Because Java stores Arrays as objects. Each row is an Array object with an array of `n` Integers. To connect up the rows, there is an Array object that contains the object references to each of the row objects.

Each row object is stored contiguously, but each row will be stored non-contiguously on the heap, so they are not contiguous and this formula will not work.

You still access an array in Java using the notation `A[i][j]`, but the index `i` provides an object reference to the `ith` row object, and `j` provides an index into that Array, but your formula will not work in that case.
> 1 votes

---
Tags: arrays, java, memory-allocation
---


# Question
Title: Priority of symbols in a notation for projections
We define an initial function called projection as $$I^k\_i(n\_1,\ldots,n\_k) = n\_i, \quad i \leq 1 \leq k, \quad k \in \mathbb{N}.$$

Suppose now that we want to define it in some programming language where we have no access to superscripting nor subscripting. Should we call it `Iki` or `Iik`?

My stand point is that it should be `Iki` so that we first describe the nature of function, that it comes from a set of functions that take `k` arguments. But, the other approach is also understandable because it emphasizes the purpose of function, that it returns the `i`-th coordinate.
It may also be that priorities don't go from left to right as I imagine it.

Is there any convention on priority of symbols in this type of notation?

# Answer
> 0 votes
No, there is no convention.

In some languages, there is an idiomatic name for the function that extracts the first element of the tuple (e.g., `fst`, `hd`) and/or the function that extracts the second element (e.g., `snd`).

---
Tags: computability
---


# Question
Title: Is it possible to simulate a fair coin with a finite number of tossing of a biased one?
It is a classic problem to simulate a fair coin with a biased one.

According to Fair Coin (wiki),

> John von Neumann gave the following procedure:
>
> 1. Toss the coin twice.
> 2. If the results match, start over, forgetting both results.
> 3. If the results differ, use the first result, forgetting the second.

In the worst case, the procedure may not terminate.

***Problem:*** Is it possible to design an algorithm which guarantees termination in the worst case? What is the technique to solve such an impossibility problem?

# Answer
No, it's not possible. Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination. Then there would be some $n$ such that this always terminates after $n$ coin flips. Let $S$ denote the set of flip-sequences that causes your algorithm to output 0 (so that $\overline{S}$ is the set of flip-sequences that causes your algorithm to output 1). The probability of your algorithm outputting 0 is equal to the probability of getting a flip-sequence in $S$, which is a sum of the form

$$\sum\_{x \in S} {a\_x \over 3^n}$$

where each $a\_x$ is an integer. Thus the probability of outputting 0 has the form $b/3^n$ where $b$ is an integer. We want this to be $1/2$, for your algorithm to produce an unbiased bit of output. However since $3^n$ is odd, there is no integer $b$ such that $b/3^n = 1/2$. Therefore, no such algorithm can exist.
> 12 votes

---
Tags: proof-techniques, probability-theory, randomized-algorithms, randomness, probabilistic-algorithms
---


# Question
Title: Relationship between Higher Kinded Polymorphism, type inference, and Currying
On Hacker News there is an interesting exchange about the async\await RFC for Rust.

The author of the proposal `withoutboats` is responding to a comment about the usage of async-await construct vs a monadic implementation in Rust. He notes three problems, the first one I am having some trouble parsing:

> Higher kinded polymorphism results in trivially undecidable type inferences without something like currying; the restrictions needed to support it would be arbitrary and weird given that Rust does not have currying (essentially some rules to reconstruct the restrictions of currying in type operator context).

I have a decent understanding of higher-kinded polymorphism, type inference, and currying (*or so I naively assert*), and I even see why currying is useful for higher-kinded polymorphism, i.e. type constructors of the form `* -> * -> *`, a type which takes a type and produces a third.

But what I don't understand is why currying is necessary to avoid "trivially undecideable type inferences." Can someone provide an example of a such an undecideable inference, and why currying helps?

# Answer
I imagine what the comment writer is referring to is this...

Consider type inference in Haskell. At some point, we may be asked to solve the unification problem `f a = Maybe Int`. This is very easy to solve (`f = Maybe, a = Int`), but *only* because we have restricted the allowable solutions. The solution to `f` may only be built out of (partial) applications of type 'constructors' (like `Maybe`) and variables. Another example is `f a = (b, a)` with solution `f = (,) b`. I suspect this partial application is what is meant by "currying". Note that `f Int = (Int, Double)` just fails.

Now consider (until somewhat recently) Scala. For one, there was no inherent notion of left-to-right partial application like the above. To even write a partially applied type required giving it a name via some rather baroque syntax. But more importantly, it made no commitment to the restrictions that made things easy in the last paragraph. This has the 'advantage' that you can make `f Int = (Int, Double)` work. A solution is `f = λa. (a, Double)`. However, note that we had to solve for `f` with a lambda term. This means inference must solve a problem called, "higher-order unification," which is bad, because it's undecidable.

Another (related, I think) problem is that my last solution above wasn't actually unique. Another solution is `f = λ_. (Int, Double)`. Neither of these solutions is more general than the other, they're simply different. So, I suspect it's also the case that higher-order unification doesn't have most-general solutions. This means (I think) that even if it were a solvable problem, the 'right' solution would not be a local property, and would depend on the rest of the program (because some of the multiple possible solutions might not be compatible with other parts of the program where the solution is used).

So, to avoid these problems, it is much easier to restrict the solution space the way Haskell does. It isn't terribly inconvenient to organize things according to this discipline such that you get good inference most of the time. And when unification fails, it's obvious what the problem was, whereas it can get complicated to figure out how to guide the system using higher-order unification with the right annotations.

However, I've heard that newer versions of Scala actually *have* adopted this type inference methodology. But I still don't think their type functions look "curried" exactly like Haskell's do (i.e. they still look like `F[A,B]`). So it's probably not essential to do that. The left-to-right partial application rule is the essential part.
> 5 votes

---
Tags: type-theory, polymorphisms
---


# Question
Title: Determining if a list contains two numbers whose difference is less than k
> Given a list with $n$ positive elements and positive number $k$, determine whether there are two numbers whose difference is less than $k$.
>
> The average time complexity should be $O(n)$, and the memory should be $O(n)$ as well.

My attempt: initialize a hash table, and insert every element from the list to the hash, all of this takes $O(n)$ time on average.

Now, scan the list. Say the the elements are $x\_1,x\_2, \dots, x\_n$.

Assume we scan $x\_i$ then if we have in the list an appropriate element, it should fulfill $|x\_i-x\_j|\<k$, so I have to check $2k$ different elements, which isn't good enough.

Does anybody have any other idea?

# Answer
> 3 votes
Let $f(x) = \lfloor x/k \rfloor$. Create a hash table which stores $f(x\_1),\ldots,f(x\_n)$; furthermore, for each $y \in \\{f(x\_1),\ldots,f(x\_n)\\}$, count how many elements map to $y$, and what is the minimal element mapping to $y$.

If any of the cells contains more than one element, then these two elements are at a distance of less than $k$. Otherwise, go over all elements, and for each $x\_i$, compare $x\_i$ to the minimal element mapping to $f(x\_i)+1$, checking whether the two elements are at distance less than $k$. If no elements at distance less than $k$ have been found in this way, then no such elements exist.

# Answer
> 0 votes
Here is another suggestion. Use radix sort to sort the integers, than check if the difference between any two successive elements is less than k. Its solves your problem if you assume that radix sort is O(n)

---
Tags: algorithms
---


title: Relation of P vs. BPP and P vs. NP

text:
# Question
Title: Relation of P vs. BPP and P vs. NP
What are the consequences of proving some relation ($\subseteq$, $\subset$, $=$, or $\neq$) on one of the following, to the other?

1. $P$ vs. $BPP$
2. $P$ vs. $NP$

# Answer
It is trivial that $P$ is contained in $BPP$ and that $P$ is contained in BPP. There are of course, many consequences of resolving both of these questions (they wouldn't be major open problems if that weren't the case). There is an important relationship between resolving 1 and resolving 2: From the Sipser-Lautemann theorem https://en.wikipedia.org/wiki/Sipser%E2%80%93Lautemann\_theorem it follows that if $P = NP$, then $P=BPP$. Of course, we strongly believe that $P \neq NP$, and that $P = BPP$, so this isn't a direction of reasoning that is likely to be actually useful by itself.
> 2 votes

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


# Question
Title: How a NTM reject an input / How a TM simulates a particular NTM
I understood that a NTM can say only yes but it doesn't know if the input is a NO instance with a single execution. Furthermore, the NTM can diverges and, at the same time, can decide a language (source: Papadimitrou - Computational Complexity, proposition 7.1). While a TM must converges in a "yes" or "no" answer to decide the same language. Now, we know that for a NTM that decides a language L we can create a TM that decides L (theorem 2.6). But suppose that the NTM diverges for some computation. How can the TM treat this case?

\[EDIT\] Definition (source Papadimitrou, pg 45): A non-deterministc Turing Machine decides a language L if for any input x, the following is true: x belongs to L iff there is an acceptance path.

This definition admits machines that, instead of rejecting an input, diverge and at the same time decide a language.

Theorem 2.6 (pg 47): Suppose that language L is decided by a nondeterministic Turing machine N. Then it is decided by a deterministic Turing machine M.

Proposition 7.1 (pg 141): Suppose that a (deterministic or nondeterministic) Turing machine M decides a language L within time (or space) f(n), where f is a proper function. Then there is a precise Tring machine M', which decides the same language in time (or space, respectively). O(f(n)).

This last proposition confirms that there is a Turing machine that decides a language and that diverges for some path.

# Answer
If we're only interested in computability, and not in the resources used by the computation (i.e., complexity), then we can simulate an NTM as follows. First, simulate every possible sequence of nondeterministic choices for one step. Then, start again and do them all for two steps. Then, start again and do them all for three steps, and so on.

There are three possible results of this simulation.

1. If any of the simulated computations accepts (so, in particular, it terminates), then we accept. In this case, it doesn't matter if some other computations would diverge.
2. If no computation accepts but, after some number of steps, all computations have rejected, we reject.
3. If no computation accepts and at least one computation diverges, then the simulation will also diverge.

This is a faithful simulation of the nondeterministic machine. If some computation path accepts, we accept, and this is the definition of acceptance for nondeterministic machines. If every computation path halts and rejects, we reject, as we should. Otherwise, we diverge, as does the nondeterministic machine.

However, the case you're looking at *does* include resource bounds. Papadimitriou is essentially comparing two different notions of the resources used by an NTM and showing that they're both the same. I'll talk about time for concreteness, but the same arguments apply to space. One way of defining $\mathrm{NTIME}(f(n))$ would be to say that *every* possible computation path must run within $f(n)$ steps, and the other would be to say that only the accepting paths need to. However, because we're only interested in constructible functions $f$, we can use the following idea to make the two notions identical. First, the machine deterministically computes $f(n)$ and then it does the nondeterministic computation, counting off the steps. If the step counter reaches $f(n)$, and the machine hasn't accepted, we must be either on a rejecting path or a diverging one. In either case, the path won't accept, so we can reject. Therefore, any language that's *accepted* by an NTM where every accepting path uses at most $f(n)$ steps is also *decided* by an NTM where every path uses at most $f(n)$ steps and no path diverges.

Technically, I've only shown that we can do it in something like $3f(n)$ steps, but the linear speed-up theorem says we can get rid of the constant $3$.
> 2 votes

# Answer
A nondeterministic Turing machine accepts an input iff there is at least one accepting path, that is, one set of guesses for which the machine accepts. A path on which the machine diverges is not an accepting path.

We are often interested in time-constraint nondeterministic Turing machines. Such Turing machines always halt, on every computation path. This is the case for nondeterministic polytime Turing machines, the machine model corresponding to the famous complexity class $\mathsf{NP}$.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Hardness of $2$ edge-disjoint spanning trees decomposition
The question is clear from the title. What is the complexity of the following decision problem:

> **Input**: An undirected graph $G(V, E)$
>
> **Output**: $\mathrm{YES}$ if $G$ can be decomposed into two edge-disjoint spanning trees, $\mathrm{NO}$ otherwise

# Answer
Your problem is in $\mathrm{NP} \cap \mathrm{co}$-$\mathrm{NP}$.

First, it is obviously in $\mathrm{NP}$. The verifier receives the certificate consisting of two edge-disjoint spanning trees that consumes all the edges in $\mathrm{E}$

Second, by Tutte & Nash-Williams theorem \[1\], your problem is also in $\mathrm{co}$-$\mathrm{NP}$. The co-nondeterministic machine guesses any partition $\mathrm{P}$ of $\mathrm{V}$ and check that $|\mathrm{E}\_\mathrm{P}(\mathrm{G})| \geq 2(|\mathrm{P}| - 1)$. Also, it must check that $|\mathrm{E}| = 2(|\mathrm{V}| - 1)$ to be sure that the tree packing of the above theorem is indeed a decomposition by trees.

\[1\] Tomas Kaiser, **A short proof of the tree-packing theorem**, https://arxiv.org/pdf/0911.2809.pdf
> 1 votes

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


# Question
Title: Show that RP is closed under concatenation
I'm trying to prove the following problem:

> Show that $RP$ is closed under concatenation

Now, let's say that the two languages are $L\_{1}$ and $L\_{2}$ (both in $RP$). Then I accept a word iff the TM of $L\_{1}$ accepted the first part of the word (with a probability $\geq\frac{1}{2}$), and the TM of $L\_{2}$ accepted the second part of the word (with a probability $\geq\frac{1}{2}$).

But then each word in the language $L\_{1} \circ L\_{2}$ would be accept with a probability of $\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}$, so the language $L\_{1} \circ L\_{2}$ will not be in $RP$.

So what is the correct proof to the problem?

# Answer
Do the following $poly(|x|)$ times:

> Check for every possible (contiguous) partition of the input string $x = x\_1x\_2$ and apply the $\mathrm{RP}$ machine to each of $x\_i$ if the answer is $\mathrm{YES}\\:\mathrm{YES}$ outputs $\mathrm{YES}$ and halt.

If after polynomially many times, still no **definite** $\mathrm{YES}$ answer has been put down, output $\mathrm{NO}$ *with a little bit of fear* as **it is always like so with** $\mathrm{RP}$ **algorithms**.
> 1 votes

---
Tags: complexity-theory, complexity-classes, closure-properties, randomized-algorithms
---


# Question
Title: Given two sorted arrays check if one is subset of another
Question: Given two sorted arrays A1 and A2, check if A2 is a subset of A1. Also, assume there might be duplicates.
Example:
A1 = \[0,0,0,0,1\], A2 = \[0,1\] // should return true
A1 = \[-1,0,1,2,3,4,5\], A2 = \[1,2,3\] // should return true

Answer: My answer is below and works, but I believe my running time is slow. Not sure if there is another algorithm I can leverage.

FYI: this is not for school or project, just curious with solving problems.

```
function isSubArrayOfAnother(a1, a2) {
        if (!a1 || !a2 || a1.length === 0 || a2.length === 0) {
            return false;
        }

    let loc = a1.indexOf(a2[0]);
    let allIndexes = [];

    while(loc > -1) {
        allIndexes.push(loc);
        loc = a1.indexOf(a2[0], loc + 1);
    }

    for(var i=0; i<allIndexes.length; i++) {
        let isMatch = true;
        let tempIndex = allIndexes[i];
        for (var j = 0; j< a2.length; j++) {
            if (a2[j] !== a1[tempIndex++]) {
                isMatch = false;
                break;
            }
        }
        if (isMatch)
            return isMatch
    }
    return false;

}

```

# Answer
There is a O(n) solution to this.

Finding all possible start index of the subset can be eliminated

```
while(loc > -1) {
    allIndexes.push(loc);
    loc = a1.indexOf(a2[0], loc + 1);
}

```

And, there seems to be an edge case where it will attempt to access element out of the array's bounds. I mean, the input like the one below

```
A1 = [-1, 0, 1, 3, 1, 2], A2 = [1, 2, 3]

```

The below pseudocode-like is a starting point, there is still optimisations left in this algorithm.

```
Given array A, find the presence of sub array B,

matchPointer = 1
for i = 1 to A.length
  if A[i] == B[matchPointer]
    if matchPointer == B.length
      "Subset Found"
    matchPointer = matchPointer + 1
  else
    matchPointer = 1;

```
> 1 votes

# Answer
The algorithm given by @bnu is optimal in time in the general case when you know nothing about the input.

However if you know that one of the arrays is much smaller than the other, you can do a binary search for each value of the small array to check if it is present in the larger array.
In this way (if k is size of smaller and n of bigger array) , the time complexity is$ O(k * \log n)$ which can be orders of magnitude faster if $k\<\<n$.
> 0 votes

---
Tags: algorithms
---


title: Name for data structure

text:
# Question
Title: Name for data structure
I have a data structure that implements the following operations all in $O(1)$:

* $\text{insert(x)}$, inserts a value into the data structure and returns a unique key $k$ to the value
* $\text{delete(k)}$, deletes the value at key $k$ and returns it
* $\text{get(k)}$, returns a reference to the element at key $k$

Internally the storage is simply a contiguous array $A$ of $(x, v)$ tuples. $x$ is either a value or is used to store a freelist. $v$ is a version tag. When $v$ is odd $x$ is a valid item with version $v$. When $v$ is even $x$ is unoccupied and is re-used to store the index of the next unoccupied item after this.

The key $k$ is a tuple of $(i, v)$, an index into the contiguous array and a version. Only when $A\[k\_i\]\_v = k\_v$ is this key valid and contained in the data structure. Finally, on every insert and delete $A\[i\]\_v$ is incremented.

Now this is very similar to a memory allocator (which returns pointers instead of keys), but the difference is that physical memory locations can be safely re-used here without spurious errors where old pointers point to new items. So from the perspective from the user every key that $\text{insert}$ ever gives is unique.

The question is, what is a good name for this data structure? I've seen similar data structures called "slot maps" in game development, but it's not quite the same. They don't use versioning and support dense iteration through using two indirections (one key -\> idx and idx -\> item), whereas this data structure can have a sparse memory layout.

It's also very similar to a slab allocator, but again it has added safety of returning permanently unique keys, even when re-using storage.

# Answer
I ended up settling for Sparse Slot Map. I was wrong to say that slot maps don't do versioning - that depends on the implementation.
> 0 votes

# Answer
I think what you did is very similar to the data structure described here: https://research.swtch.com/sparse
> 0 votes

---
Tags: data-structures, reference-request
---


title: Proving special case of SAT is in P

text:
# Question
Title: Proving special case of SAT is in P
Let *SAT-100* be the following problem:

**Input:** Any boolean logic formula

**Output:** True if there exists a combination of exactly 100 input variables that satisfy the formula.

This is the description of a problem that is apparently in $P$. (old exam question)

I have tried to design an algorithm but I got stuck, so here it goes:

```
Input: boolean logic formula F
    If(count(variables in F)) < 100:
       return false
    else
        # try all combinations of input variables

```

And here is the problem: building and evaluating all combinations of input variables can't seem to be polynomial because:

$$ { n \choose 100} = \frac{n! }{100! \cdot (n-100)!} \in \mathcal{O}(n!) $$

and this nasty factorial can't be bounded with any polynomial that I know of.

I don't think the exam is wrong, so I must have overlooked something.

# Answer
Note that $$\frac{n!}{(n-100)!100!}\<\frac{n!}{(n-100)!}= n \cdot (n-1)\cdot \ldots \cdot (n-99)\< n^{100}.$$

Thus, your algorithm runs in polynomial time
> 6 votes

---
Tags: algorithms, satisfiability, polynomial-time
---


title: Find least connected sub-graphs

text:
# Question
Title: Find least connected sub-graphs
For example the nodes in this graph should be separated into two groups (A,B,C) and (D,E,F,G).

By looking at a graph of citations, assuming that most citations are papers from the same field, can we separate papers into fields?

# Answer
You could define what "least connected" means (precisely) in a variety of ways, where the precise definition chosen may affect the output of the algorithm (and there is no unique correct definition for this). But you may wish to look into Community Detection algorithms. The general intuition of Community Detection is to find a set of sub-graphs that maximises the ratio of edges within the sub-graphs versus edges between sub-graphs. Depending on the precise definition, this may be a difficult (NP-complete) problem, and so various algorithms rather use approximate (heuristic or greedy) approaches.

Five popular Community Detection algorithms are described here and should be a good starting point for your work.
> 2 votes

---
Tags: graphs
---


title: Solving problems that DTM can't solve

text:
# Question
Title: Solving problems that DTM can't solve
Let L be a problem that DTM can't solve. Can we prove that there is an abstract machine that can solve this problem?

Here, L is not Halting problem or Hilbert's tenth problem (because we proved that algorithms for these don't exist).

In other words, is there an abstract machine more powerful than DTM? If not, how do we prove it?

# Answer
We define computable functions to be those computable by a (deterministic) Turing machine, and we identify algorithms with computable functions. Therefore, *by fiat*, any algorithm can be implemented on a Turing machine.

Whether this is the correct definition of the intuitive concept of algorithm is the subject of the Church–Turing thesis. The fact that many models of computation are known to be equivalent strengthens the thesis, but since it's not a mathematical statement, it is impossible to prove.
> 3 votes

---
Tags: computability, undecidability
---


# Question
Title: Proving parametricity for Gallina functions
I have the following definitions

```
Definition nat'' {X : Type} := (X -> X) -> X -> X.
Definition nat' := forall (X : Type), @nat'' X.

```

And when I wanted to prove a certain property I ended up in the following situation:

```
  m : nat'
  H : 0 = m nat S 0
  X : Type
  s : X -> X
  z : X
  ============================
  m X s z = z

```

which should be some kind of free theorem! Specifically, `m: (forall X : Type), (X -> X) -> X -> X` is a function that should behave parametrically for any instantiation of `X`, so by knowing that `0 = m nat S 0` I should be able to deduce that `x = m X f x` for any `x : X` and `f : X -> X`.

But I haven't seen such free theorems stated in Coq for Gallina terms. Is there an easy way to go about proving such a result without some deep embedding of a language and proving parametricity for this language?

# Answer
My belief has always been that you cannot prove such free theorems from within Gallina about Gallina terms, but I don't have a definite reason why. I certainly can't imagine how this proof would work, given that there's no way to analyze functions like instances of `nat'` other than applying them.

As you mentioned, you can (in principle) do a parametricity proof for a deeply-embedded language.
> 4 votes

# Answer
There are plugins for Coq to prove such parametricity theorems. E.g. https://github.com/parametricity-coq/paramcoq which has been superseded by https://template-coq.github.io/template-coq/
> 2 votes

---
Tags: functional-programming, semantics, coq
---


title: Question about mapping reducibility

text:
# Question
Title: Question about mapping reducibility
I am working on an assignment where one of the sub questions is:

> Let $A$ and $B$ be languages. Suppose $A$ is context free and $A ≤\_m B$, which means that there is a computable function $f\colon \Sigma^\* \to \Sigma^\*$ such that for all $w \in \Sigma^\*$, $w \in A$ iff $f(w) \in B$. Is it possible that $B$ is regular?

My take on this is that since context-free languages are on a 'higher' level than regular languages this is not possible. Apparently this is not the case, but I do not understand why. Does anyone have a good explanation?

# Answer
> 4 votes
If $A$ is computable and $B$ is any nontrivial language (that is, $B \neq \emptyset,\Sigma^\*$) then $A \leq\_m B$. Indeed, pick $x \in B$ and $y \notin B$, and construct a computable reduction which decides whether its input is in $A$ or not, and outputs $x$ or $y$ accordingly.

Another issue you seem to be confused about is the meaning of *context-free*. **The fact that a language is context-free doesn't preclude it from being regular.** On the contrary, *all* regular languages are context-free.

# Answer
> 1 votes
You're correct that context-free languages are at a higher level than regular ones; or, rather, are at at least as high a level, since every regular language is also context-free.

However, what you're missing is that you're being allowed to use any computable function as a reduction, which is an even higher level still! This means you can solve the problem entirely in the reduction, as Yuval explains.

---
Tags: automata, regular-languages, context-free, reductions
---


title: MST for a finite number of weights

text:
# Question
Title: MST for a finite number of weights
Let $F$ be a finite set of real numbers say $\\{w\_1,\dots,w\_k\\}$.

Let $G=(V,E)$ be an undirected connected graph and let $w\colon E\to F$ be a weight function.

Describe a **linear time** algorithm that will find a Minimum spanning tree in $G$.

Assume that $|V|\gg k$, i.e. the number of vertices is much larger than k.

I know that in such a case we can sort the edges in linear time and then use Kruskal's algorithm, but that will be slightly worse than linear time — $O(|E|\alpha(|V|))$.

I have heard about an approach that uses $|F|$ queue's but I couldn't figure it out, please help.

# Answer
> 2 votes
*Summary: An algorithm of linear time in $|E|$ can be given by an implementation of Prim's algorithm where its priority queue is $|F|$ queues of equal-weight edges, assuming $|F|$ is a constant.*

---

**We will explicitly let $k=|F|$ be a constant.** This constantness is indicated by "in such a case we can sort the edges in linear time.". It is then superfluous to "assume that |V|\>\>k, i.e. the number of vertices is much larger than k", since the complexity analysis by the big $O$-notations is about the behaviour of the algorithm when the input size increases to infinity, skipping the cases when the input size is not big enough.

Let us sort $F$ by constant time. To each edge with weight $w$ that is the $i$-th smallest in $F$ for some $1\le i\le k$, we will reassign weight $i$. Since comparison compatible weights of edges will lead to the same set of MSTs, this weight reassignment, which is done in linear time of $|E|$, does not affect the correctness of all later arguments. So, **we will assume, furthermore, $F=\\{1, 2, \cdots, k\\}$**. (We can, alternatively, add this step to the algorithm below.)

**Here is the description of a wanted algorithm in detail** (given an undirected connected graph $G=(V,E)$ and a weight function $w:E→F=\\{1, 2, \cdots, k\\}$). For brevity let us call the algorithm Prim's algorithm with constant queues (PAWCQ). PAWCQ is, most probably, more or less the "approach that uses $|F|$ queues" that is mentioned by the OP.

1. Create $R$ as an empty list of edges.
2. Mark all vertices as unvisited.
3. Create $k$ empty lists of edges $L\_1, L\_2, \cdots, L\_k$.
4. Select an arbitrary vertex $v\_0$. Iterate through all edges incident to $v\_0$, putting an edge in $L\_i$ if its weight is $i$. Mark $v\_0$ as visited.
5. Repeat the following steps until all $k$ lists are empty:
    1. Find the non-empty list with lowest subscript.
    2. Remove an element from the list just found. Name that element $e$.
    3. If both vertices of $e$ are marked visited, do nothing. Otherwise, let $u$ be the vertex marked unvisited. (The other vertex must be marked visited). Iterate through all edges incident to $u$, putting an edge in $L\_i$ if its weight is $i$. Mark $u$ as visited. Add $e$ to $R$.
6. return $R$.

We can see that PAWCQ is indeed a variation of Prim's algorithm. In particular, it will always terminate in finitely many steps to return an MST of $G$.

**The time complexity of PAWCQ is asymptotically linear in $|E|$ when $G$ is given by its adjacency list** (in the usual computation models), since both the insertion of an edge into the constant queues and the removal of an edge from the contant queues take constant time and each edge is inserted once and removed once.

Note that the order in which we remove an element in step $5.2$ does not affect the correctness of the algorithm. We can implement each list as, for example, a FIFO queue or a FILO stack.

Note that we can speedup the algorithm in several places for better performance, such as ending the algorithm as soon as we have collected $|V|-1$ edges. However, none of them will improve the big $O$ complexity since $O(|E|)$ is the best possible.

---
Tags: algorithms, graphs, minimum-spanning-tree, prims-algorithm
---


# Question
Title: P=NP giving a deterministic algorithm for SAT
I'm trying to prove the following problem:

> Prove that if $P=NP$ then there is a polynomial time algorithm for the following problem:
>
> **INPUT:** A boolean formula $\phi$.
> **OUTPUT:** A satisfying assignment of $\phi$ if $\phi$ is satisfiable. If $\phi$ is unsatisfiable, return $false$.

### My proof:

If $P=NP$ then $SAT$ can be decided in polynomial time. Run $SAT$ on $\phi$. If it returns $false$, reject. Else, nondeterministically select a boolean assignment. If it satisfies $\phi$, return it.
The algorithm is in $NP$, but because $P=NP$, it is also in $P$.

Is my proof correct? I'm asking because the textbook gave a different answer, and I want to know if my proof is correct, and if not, where does it fall?

# Answer
I like the way you think, but there's a gap in your attempt.

$\mathrm{P}$ and $\mathrm{NP}$ are classes of decision problems, i.e., computational tasks where the answer is either "yes" or "no". Nondeterministically generating a satisfying assignment isn't a decision problem, so it isn't in $\mathrm{NP}$, so the assumption that $\mathrm{P}=\mathrm{NP}$ doesn't give you a deterministic algorithm for it. It feels like it ought to, but that's not a proof.
> 5 votes

---
Tags: complexity-theory, time-complexity, satisfiability, complexity-classes
---


# Question
Title: Find shortest path that visits all nodes in a given set of nodes
Suppose I have a graph $G$ and a set of target nodes $S = \\{A\_1, ..., A\_n\\}$. I'm attempting to find the shortest path that visits each target node, in order, without visiting the same node twice.

For example, consider the following:

I have attempted to solve this by first performing a breadth-first search to find the shortest path from A to B, then from B to C, and so on, taking care to exclude any paths already found at each iteration.

This greedy solution works for most inputs, but in some case it will fail to find a solution, as the shortest path between two target nodes may end up blocking the complete path.

Aside from a brute-force approach, is it possible to find the shortest path that visits all of the target nodes, and is guaranteed to find such a path if one exists? Any suggestions on how to proceed?

# Answer
I answered a more general problem a couple days ago. You simply want the destination pairs to be (a, b), (b, c), (c,d ),etc.

The gist is to translate the problem into a minimum-cost integer multi-commodity flow problem with a maximum capacity of $1$ per node, and one commodity between each pair of destinations.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Problems that feel exponential but are P
I'm trying to build a list of algorithms/problems that are "exceptionally useful", as in, solving problems that 'seem' very exponential in nature, but have some particularly clever algorithm that ultimately solves them. Examples of what I mean:

* Linear Programming (The simplex algorithm is exponential time; it took a long time to find a polynomial time solution!)
* More generally, Semidefinite Programming
* Primality testing
* 2-SAT and HORNSAT
* Computing determinants (if this doesn't sound difficult, consider the permanent)
* Finding perfect matchings
* A variety of hard group theoretic problems that can be accomplished using the Classification of Finite Simple Groups
* A variety of hard graph problems that can be accomplished using complicated Forbidden Minor characterizations (embeddability on an arbitrary surface; bounding of treewidth and branchwidth; Delta-Wye reducible graphs)
* Computing exponentials in a bounded group (i.e. computing $a^b \mod k$ in $\log b$ steps, as accomplished by repeated squaring)
* Computations relying on the LLL algorithm. (As a special case: Euclidean algorithm. As a more general case: PSLQ or HJLS algorithms.)
* Constraint problems without Taylor terms (?). I admit I don't fully understand this, but it sounds like it probably subsumes the 2-SAT / HORNSAT cases above, and any linear algebra over finite fields. See here for a longer post
* Problems computable via holographic reductions.

As a honorable mention, I would also mention Graph Isomorphism, because it's still awfully easy ($n^{\log^2 n}$), and equivalent to so many other isomorphism problems:

* Digraphs/multigraphs/hypergraphs (a sort of 'harder' problem)
* Finite automata/CFGs

Obviously there's a range of difficulty in these, but all leave at least some people with some sense of 'surprise' in the sense that the problem can sound difficult but turn out tractable. LP might sound relatively straightforward, but took people quite a while to build an actual solution to. Repeated squaring or solving 2-SAT is something an undergraduate could possibly come up with on their own, but if you had only learned about NP-Complete problems without having seen HORNSAT, it might sound like a natural candidate for NP-Completeness. Solving the CFSG or having a polynomial way to check for Delta-Wye reducability are no mean feats.

I hope this makes sense; there are obviously lots of subjective attributes here, but I'm curious to hear what other people find to be efficient solutions to "obviously hard" problems.

# Answer
For me one of the most efficient algorithms is the Blossom V algorithm that finds maximum weight perfect matching in a general graph:

https://en.m.wikipedia.org/wiki/Blossom\_algorithm
> 6 votes

# Answer
For me all classic and the more recent more efficient **algorithms to verify or find a minimum spanning tree (MST) of a connected edge-weighted graph** are good candidates. Many of these algorithms are listed in wikipedia.

At the first sight, this problem looks like the travelling salesman problem, one of the few most famous NP-hard problems. Most amazingly, there are **linear algorithms to verify an MST and many near-linear algorithms to find an MST!** In fact, one of the most famous open problems in algorithms is whether there is a deterministic linear algorithm to find an MST in general graphs. It turns out there are rich math and graph structures and properties as well as a multitude of practical applications that are associated to MST, making it one of the more enjoyable and expandable topics in computer science course. For a slightly outdated but very well-written comprehensive introduction, please check the tutorial by Jason Eisner.
> 5 votes

---
Tags: complexity-theory, polynomial-time, efficiency
---


# Question
Title: How to prove even with structural induction, for expression
E::= zero|two|expression + expression|expression\*expression, E element of expression how do i prove E to be even.

I have no clue on how to go about tackling this.

# Answer
> 3 votes
To prove a property `p` by structural induction on your `E`, one has to prove

1. `p(zero)`
2. `p(two)`
3. for all `e1,e2` we have `p(e1) && p(e2) ==> p(e1 + e2)`
4. for all `e1,e2` we have `p(e1) && p(e2) ==> p(e1 * e2)`

That is, we have to prove that it holds for each term in the inductive definition, assuming `p` holds for the immediate subterms (induction hypothesis).

In your case, `p(e)` is "the evaluation of `e` yields an even result".

You should be able to check all the conditions above.

---
Tags: induction
---


# Question
Title: Encoding (binary) trees using lambda calculus
I'm new to lambda calculus, and I read all kinds of interesting stuff about encoding data types as functions. Church booleans, numbers and lists. https://en.wikipedia.org/wiki/Church\_encoding

Is there a way to encode (binary) trees?

# Answer
I'll choose to encode binary trees with data in the internal nodes. Intuitively, a tree is either empty leaf, or a triple (data,left subtree,right subtree).

The corresponding Church encoding is:

$$ \begin{array}{l} {\sf Empty} = \lambda e b. e \\ {\sf Branch}\ x\ l\ r = \lambda e b. b x (l e b) (r e b) \end{array} $$

For instance, ${\sf Branch}\ 1\ {\sf Empty}\ ({\sf Branch}\ 2\ {\sf Empty}\ {\sf Empty})$ is an encoded tree. You can easily reduce it to a normal form, if wanted, resulting in $\lambda e b. b \ 1\ e\ (b\ 2\ e\ e)$.

Indeed, the normal form of a tree obtained from the above "constructors" will always start with $\lambda e b.$ and then proceed with the tree where the variable $b$ denotes a "branch" and variable $e$ denotes the empty tree.

To use an encoded tree, you can simply apply it as in $t\ E\ B$, providing two suitable terms $E,B$. This will compute a so-called "fold" of the tree, using constant $E$ and ternary function $B$ over the tree $t$.

For instance, $t\ 0\ (\lambda x l r. x+l+r)$ will result in the sum of all the numbers in the tree $t$, assuming $t$ only contains numbers as data.

It takes a while to convince oneself that this encoding indeed lets us do "whatever we want" with the tree, i.e. run any algorithm over a tree. For primitive recursive algorithms, we can use the encoding itself, directly. For more general algorithms, we can use a fixed point combinator on top of that.

This encoding can be generalized to *all* the algebraic data types defined through (positive) recursion. Moreover, the encoding can be typed in System F. It is really general.

If you are familiar with some typed functional languages (such as Ocaml or Haskell), I'd recommend you try to implement a "fold" function on trees (with data in the nodes, or in the leaves), or on other algebraic data types. It's a nice exercise which I believe can help a lot in understanding the encoding in its generality.
> 5 votes

# Answer
Sure: take the same idea as a list. Once you can encode a pair a node of a binary tree is either a leaf, represented as `(false, value)`, or a branch, represented as `(true, (left-child, right-child))`.
> 2 votes

---
Tags: trees, lambda-calculus
---


# Question
Title: Proving Postorder Traversal's Time Complexity
I am looking at the following algorithm for performing a **Postorder Traversal of a binary tree**

```
POSTORDER(root):
if root != nullthen
    POSTORDER(root.left);
    POSTORDER(root.right);
    visit root;
end if;

```

I am supposed to be able to demonstrate that this algorithm runs in Θ(n) time complexity when the input is a n-vertex tree. But I am not even sure where to begin with doing that.

I have looked at the following sources:

I understand ***WHAT*** PostOrder traversal does, and I understand ***WHAT*** a binary tree is, but I don't know how I can prove that time complexity.

Could anybody help me on this?

# Answer
> 1 votes
In order to prove the complexity of n-vertex tree, you must first understand how to analyze the time for a binary tree. So i am explaining it for a binary tree so that you can generalize it.

In postorder traversal each node in binary tree is visited:

a) 1 time if it is a leaf node.

b) 1 time if it is a node with only one child (either left or right)

c) 2 times if the node has both left and right children. 2 times because when we have to process the right child once we have finished with processing of its left child we need to check whether the node has right child or not. If it has a right child we process right child deferring the parent node so that it could be revisited again once we are finished with processing of right child as well.

So, any node in the tree is not visited more than two times. If n is the number of nodes then the worst case complexity is $O(2n)$ (in case of complete binary tree) and best case is $O(n)$ (in case of skew tree). Ignoring the constants:

**Best case time** : $O(n)$

**Worst case time** : $O(n)$

Hence, we can say algorithm is $Θ(n)$.

# Answer
> 1 votes
Show that `POSTORDER(v)` will at most be called exactly once for each vertex `v`.

This can be done via Induction by depth:

* First show that `POSTORDER(root)` will only be called once (depth 0). This is easy, since there doesn't exist a parent of `root`, therefore there exists no node `v` with `v.left == root` or `v.right == root`.
* Then assume that `POSTORDER(v)` will be called exactly once for every node at depth $n$, and show that this is also true for every vertex at depth $n + 1$. This should be straightforward to prove.

Since, other than the recursive calls (which we already understand), we do only constant stuff in a call of `POSTORDER(v)`, the time complexity is $\Theta(n) \cdot \Theta(1) = \Theta(n)$.

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


# Question
Title: Algorithm to Assign Values Based on Constraints
I have variables x y and z, and I have the values that they can be assigned to, I.E. x can be assigned 1,2, or 3, y can be 1, and z can be 2. The problem is a constraint that says once a value has been taken by a variable, no other variables can have that value.

The issue that I am running into is if I start with x, how can I efficiently tell that it's value should be 3?

# Answer
The problem you are describing amounts to constraint programming and the specific constraint you are talking about is the alldifferent constraint. I'm not offering a purely algorithmic solution, but reading a bit on constraint programming could give you some ideas on how to construct a search tree where you make a decision (i.e., assign a value to a variable) at each node, and how to backtrack to a feasible node when you reach an infeasible node.
> 1 votes

---
Tags: algorithms, constraint-satisfaction
---


# Question
Title: Relations between different time complexities of an algorithm
If I have an algorithm A that, in the worst case, has a lower bound of $Ω(n\log n)$ and an upper bound of $O(n²)$, how can I go about determining possible time complexities for best and average cases?

For instance, only one of the following is possible:

a. Best case $\Theta(n)$

b. Worst case $\Theta(n\sqrt{n})$

c. Average case $\Theta(n^3)$

d. Worst case $\Theta(n)$

Now right off the bat I know we can eliminate (d) since it’s also dealing with the worst case, and being that $n$ is out of the given bounds, falling below $n\log n$.

What I’m stuck on is how to approach the other worst case option since it falls in the range and am even more confused about how to deal with the two choices that aren’t even worst case.

# Answer
> 0 votes
Let us use the following notations:

* $L$ is any lower bound on the running time.
* $U$ is any upper bound on the running time.
* $B$ is the best case running time.
* $W$ is the worst case running time.
* $A$ is the average case running time.

These parameters are related in the following way:

$$ L \leq B \leq A \leq W \leq U. $$

You can solve the question using these relations.

Make sure that you understand why they hold.

---
Tags: algorithm-analysis, time-complexity
---


title: Counting Minimum Spanning Trees

text:
# Question
Title: Counting Minimum Spanning Trees
I understand how Kruskal's algorithm works. However, I am not sure how to determine the number of minimum spanning trees that a given graph has. For example say graph $G=(V,E)$ given by

When running Kruskal's you can end up with:

However, as you might note, there are several other minimum spanning trees that are still valid. An example would be getting rid of edge $BD$ and adding edge $AB$ or $CB$. So how can you determine the total number of different minimum spanning trees that exist in the graph, without having to inspect for all the different possibilities?

# Answer
> 3 votes
The best exposition on how to count the number of minimum spanning trees is, as far as I have seen, a stackoverflow answer by j\_random\_hacker.

In the course to answer a different question, that answer explains very well an algorithm that counts the number of MSTs.

1. It establishes that Kruskal's algorithm can find every MST.
2. It breaks up the Kruskal's algorithm into a series of blocks, each of which consists of a sequence of adding the edges of the same weight into a component multigraph that has been built in the previous block of operation.
3. It proves that the number of MSTs is the product of the number of spanning forests in the multigraph for each block-defining weight.
4. Finally, the number of spanning forests for a multigraph can be computed by Kirchhoff's theorem.

# Answer
> 1 votes
It needs to be noted that there could be an exponential number of MSTs in a graph. For example, consider a complete undirected graph, where the weight of every edge is 1. The number of minimum spanning trees in such graph is exponential (equal to the number of spanning trees of the network).

The following paper proposes an algorithm for enumerating and generating all minimum spanning trees of the network:

*Yamada, Takeo, Seiji Kataoka, and Kohtaro Watanabe. "Listing all the minimum spanning trees in an undirected graph." International Journal of Computer Mathematics 87.14 (2010): 3175-3185.*

Be careful, there are plenty of codes for enumerating spanning trees, but not minimum spanning trees. However, the algorithm to do so is very similar.

---
Tags: algorithms, graphs, weighted-graphs, minimum-spanning-tree
---


title: Is this problem NP-complete?

text:
# Question
Title: Is this problem NP-complete?
Let there be a set of cardinality $n\in \mathbb{N}$. Let there also be $n$ subsets of that set. What is the smallest k such that union of some $n-k$ of those subsets is of cardinality at most $k$? The problem is very similar to minimal $k$ union problem, but is more specific, how can I prove it is NP-complete?

# Answer
> 1 votes
Our problem is NP-complete by a reduction from **MAXIMUM BALANCED BICLIQUE PROBLEM** (**MBBP**).

> **MBBP** problem:
>
> **Input**: A bipartite graph $G(U, V, E)$ and an integer $k$
>
> **Output**: YES if there exists $A\subseteq U$ and $B\subseteq V$ with $|A|=|B|=k$ and $G\[A, B\]$ is a biclique, NO otherwise

Given an **MBBP** instance $G, k$, output the following instance of our problem: $(\bar G, n-k)$ where $\bar G$ is the *complement bipartite* graph of $G$, namely $\bar G = (U, V, U\times V - E)$.

First, requirement that $|U| = |V|$ in our problem can be easily obtained by adding dummy vertices without harming the hardness of **MBBP**.

Second, we will show that $(G, k)$ is a **YES** instance of **MBBP** *iff*. $(\bar G, n-k)$ is a **YES** instance of our problem.

**If $(G, k)$ is a YES instance of MBBP**, then there exist $A\subseteq U$ and $B\subseteq V$ such that $|A| = k$ and $|B| = k$ and $G\[A, B\]$ is a biclique. It follows that in $\bar G$ the neighborhood of $A$ is a subset of $V - B$ (all the edges in the biclique are removed). And $|A| = k = n - (n - k)$ and $|V - B| = n - k$. Thus, $(\bar G, n - k)$ is a **YES** instance of our problem.

Conversely, if **$(\bar G, n - k)$ is a YES instance of our problem**, then there exist $A\subseteq U$ such that $|\cup\_{v\in A}N\_{\bar G}(v)| \leq n - k$. By complementing this, we have $|\cap\_{v\in A}N\_G(v)| \geq k$. So by arbitrarily choose $k$ vertices in $\cap\_{v\in A}N\_G(v)$ to form $B\subseteq V$. We have shown the existence of a biclique in $G$ satisfying requirement of the original **MBBP** instance. Hence, $(G, k)$ is a **YES** instance of **MBBP**.

---
Tags: time-complexity, np-complete, sets, finite-sets
---


title: Paxos Consensus

text:
# Question
Title: Paxos Consensus
how does Paxos Consensus algorithm behave in an **asynchronous environment**? Because as far as I know Paxos only work in synchronous environment. Correct me if I am wrong :)

Sorry for the noob question, started learning about Paxos yesterday only.

# Answer
> 2 votes
The basic Paxos protocol (that is, without leader election) is totally asynchronous. In Lamport's paper, the basic protocol is derived from a consistency lemma in section 2.2.

However, it does not guarantee progress (section 2):

> A restricted version of the preliminary protocol provided the basic protocol that guaranteed consistency, but not progress.

(While not *guaranteeing* progress, the basic protocol never *deadlocks*. Progress is always *possible* but cannot be guaranteed in any finite amount of time)

In fact, the FLP Impossibility Result tells us that *no* asynchronous protocol can guarantee progress and be correct in the presence of failures.

Paxos adds a limited amount of dependence on time to choose *presidents*. If there is exactly one president that can communicate with enough nodes for enough time to complete the protocol, then progress is guaranteed.

However, having multiple presidents does *not* lead to inconsistency--it simply means that progress is not guaranteed.

> However, in the Paxon Synod, having multiple presidents could only impede progress; it could not cause inconsistency. For the complete protocol to satisfy the progress condition, the method for choosing the president needed only to satisfy the following presidential selection requirement (section 2.4):
>
> If no one entered or left the Chamber, then after T minutes exactly one priest in the Chamber would consider himself to be the president.

---
Tags: computer-networks, consensus
---


# Question
Title: Why not polynomial-space reductions for $PSPACE$-hardness?
A language $L'$ is $PSPACE$-hard if for every $L \in PSPACE$ we have $L \le\_p L'$.

Here $L \le\_p L'$ means that $L$ is polynomial-*time* reducible to $L'$.

Why does we use time reductions instead of space reductions in this situation?

# Answer
> 5 votes
It's never interesting to use reductions that are as powerful as the complexity class you're talking about. With the exception of $\emptyset$ and $\Sigma^\*$, every problem in $\mathbf{PSPACE}$ is $\mathbf{PSPACE}$-complete under poly-space reductions.

To see this, let $X\in \mathbf{PSPACE}\setminus\\{\emptyset,\Sigma^\*\\}$, and choose any fixed pair of strings strings $y\in X$ and $n\notin X$. Now, for any language $L\in\mathbf{PSPACE}$, we can reduce $L$ to $X$ using the function $$f(w)=\begin{cases}\ y&\text{if }w\in L\\ \ n&\text{if }w\notin L.\end{cases}$$ Since $L\in\mathbf{PSPACE}$, we can compute $f$ in polynomial space.

This argument applies for any reasonable complexity class and it's the reason why, for example, we don't talk about problems being $\mathbf{P}$-complete under poly-time reductions: instead, we use something like log-space reductions, there.

In general, hardness or completeness results are "more impressive" using weaker reductions, since the reduction is able to do less of the work. In the case of $\mathbf{PSPACE}$-completeness under poly-space reductions, the reduction is actually doing *all* the work.

---
Tags: complexity-theory, time-complexity, space-complexity
---


# Question
Title: How can average queuing delay exceed 1 if the $La/R \leq 1$?
Consider a router with a packet arrival rate of $a$ where each packet has $L$ bits, and a transmission rate (in bits/s) of $R$. My textbook describes the traffic intensity as $\frac{La}{R}$ and states that as $\frac{La}{R} \to 1$, the average queueing delay approaches $\infty$. I'm just struggling to understand why this is the case. Is it because this increases the chance that $La$ exceeds $R$ during periods of time, and that long queues can accumulate?

# Answer
> 3 votes
It depends on the r.v's of the arrival the service process.

For example, suppose the arrival and service process are all deterministic process. For example, a packet of one bit ($L=1$) arrives in every second ($a=1$), and the router transmits a bit in every second ($R=1$). Of course that in such case the average queuing delay equals to 1.

However, if for example in a system where the packet arrivals are determined by a Poisson process with parameter of $\lambda=a$ seconds and job service times have an exponential distribution (M/M/1) with average of $1/\mu=\frac{L}{R}$ seconds (which describes a system with packet length $L$ and average transmission rate of $R$), i.e., $\mu=\frac{R}{L}$ the service time equals to $\frac{1}{\mu-\lambda}- \frac{1}{\mu}$. As $\frac{La}{R}$ approaches $1$, then $\mu-\lambda$ approaches $\infty$ the service time approaches infinity.

Now for the strange behavior of $\frac{La}{R}=1$ for M/M/1 queue: When $\frac{La}{R}=1$ that means that the probability a packet enters the router equals the probability that a packet exits the router. That means, the probability that the router contains $i$ packets equals the probability that the router contains $j$ packets, for every $i$ and $j$. Thus, the number of packets in router approaches $\infty$, as well as the queuing delay.

---
Tags: computer-networks
---


title: sha256 computability class

text:
# Question
Title: sha256 computability class
Is it correct to say that since the SHA256 function domain is finite (as reported here) we can build a DFA that calculates this function (i.e. trivially a giant lookup table)?

Furthermore, if we eliminate the limitation on the length of the input, is it correct to say that SHA256 function belongs to the class of $\mathcal{PR}$ primitive recursive functions?

# Answer
> Is it correct to say that since the SHA256 function domain is finite we can build a DFA that calculates this function (i.e. trivially a giant lookup table)?

Theoretically, yes, that's correct. It would require a lookup table of $2^{2^{64}}$ entries, roughly, encoded as a DFA.

To be more picky, it depends on the notion of "DFA calculating a partial function". In particular, on what we require the DFA to do outside the domain of the function.

If we require non-termination, as we do for TMs, then a DFA can never implement a non-total function since it can not diverge. So, no DFA can compute SHA256.

If we instead only require to reach an "error" state outside the domain (or no requirement at all), then a DFA can compute SHA256.

I'd lean towards the latter interpretation, but here we need indeed to be a little careful with words.

> Furthermore, if we eliminate the limitation on the length of the input, is it correct to say that SHA256 function belongs to the class of $\mathcal{PR}$ primitive recursive functions?

That's correct.

As a general "cannon" result, if an algorithm $A$ has a complexity function which is bounded above by some $\mathcal{PR}$ function $f$, then $A$ implements a function which belongs to $\mathcal{PR}$.

This is because in $\mathcal{PR}$ we can realize the single-step function for TM, mapping a TM configuration to its next one. Then we can recurse on the single-stepping function $f(n)$ times, and read the result in the final configuration.

Corollary: $TIME(O(2^{2^{2^{2^n}}})) \subseteq \mathcal{PR}$.

The unlimited SHA256 surely falls in that obscene time bound.
> 1 votes

---
Tags: computability
---


# Question
Title: Does $\mathrm{SUBEXP}\subset \mathrm{P}/\mathrm{poly}$ imply anything?
The assumption $\mathrm{SUBEXP}\subset \mathrm{P}/\mathrm{poly}$ seems to yield nothing interesting at all. Is that true?

# Answer
**Yes**, **we have to admit so**. For other normal complexity class $\mathcal{C}$,

**either** $\mathcal{C}\subseteq \mathrm{PSPACE}$ then we have an interactive protocol with the prover to be replaced by the circuit,

**or** $\mathcal{C} = \mathrm{EXP}$ in this case, we utilize Meyer's to put $\mathcal{C}$ in $\Sigma\_2^p\cap \Pi\_2^p \subseteq \mathrm{PSPACE}$ to get back to the previous case.

But in the case of $\mathrm{SUBEXP}$, nothing above applies.

---

Note that in Meyer's, we have to simulate the machine deciding $\mathrm{L}\in \mathcal{C}$. But as every particular machine $\mathrm{M}$ deciding $\mathrm{L}$ runs in exponential time ($\mathrm{L}$ has infinitely many machines with ever decreasing running time bounds), we cannot have a *multi-output circuit* for it.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: Where can we put primitive recursive functions in Chomsky hierarchy?
I am currently studying recursion theory, but I cannot really understand where to put the Primitive Recursive functions in the Chomsky hierarchy.

In my understanding, Primitive Recursive functions contain all finite languages but are not contained in Regular expressions. For instance, I think that $\\{a^nb^n | n \in \mathbb{N}\\}$ can be computed by a partial recursive function but not by a DFA. But DFA can express the always undefined function, while the primitive recursive function cannot, because they are total.

Am I completely wrong?

# Answer
> 6 votes
The Chomsky hierarchy concerns *languages*. Languages are total functions from $\Sigma^\*$ to $\\{0,1\\}$, where $\Sigma$ is some non-empty finite set.

A language can be computed by a primitive recursive function if it can be computed by a total Turing machine which has a primitive recursive time upper bound. In particular, every language accepted by an LBA is primitive recursive, since we can simulate an LBA by a deterministic Turing machine running in double exponential time, and $2^{2^n}$ is primitive recursive.

In contrast, it is known that the Ackermann $A(n)$ function is decidable but not primitive recursive. Hence the language $\\{ \langle n, A(n) \rangle : n \in \mathbb{N} \\}$ is decidable but not primitive recursive.

Consequently, we find that primitive recursive languages sit between Type 0 and Type 1. In other words, every Type 1 language is primitive recursive, and every primitive recursive language is Type 0. Moreover, there are primitive recursive languages which are not Type 1 (for example, any EXPSPACE-complete language), and there are Type 0 languages which are not primitive recursive (for example, the graph of the Ackermann function).

---
Tags: chomsky-hierarchy
---


# Question
Title: Detect non existence of a cycle in a graph using Datalog : SMTLIB Format for Z3
I want to detect the non existence of a cycle in a graph using Datalog (which is a declarative logic programming language).

The proposed solution was:

```
(set-option :fixedpoint.engine datalog)
(define-sort s () Int)

(declare-rel edge (s s))
(declare-rel path (s s))

(declare-var a s)
(declare-var b s)
(declare-var c s)

(rule (=> (edge a b) (path a b)) P-1)
(rule (=> (and (path a b) (path b c)) (path a c)) P-2)

(rule (edge 1 2) E-1)
(rule (edge 2 3) E-2)
(rule (edge 3 1) E-3)

(declare-rel cycle (s))
(rule (=> (path a a) (cycle a)))
(query cycle :print-answer true)

```

But my question is how can i get SAT when there is no cycle in the graph and UNSAT when there exists a cycle.

One suggestion (but that does not meet my need) is:

```
(set-option :fixedpoint.engine datalog)
(define-sort s () Int)

(declare-rel edge (s s))
(declare-rel path (s s))

(declare-var a s)
(declare-var b s)
(declare-var c s)

(rule (=> (edge a b) (path a b)))
(rule (=> (and (path a b) (path b c)) (path a c)))

(rule (edge 1 2) r-1)
(rule (edge 2 3) r-2)
(rule (edge 3 1) r-3)

(assert (not (path a a)))

(check-sat)
(get-model)

```

which returns as result:

```
> z3 test.txt
sat
(model
  (define-fun a () Int
    0)
  (define-fun path ((x!0 Int) (x!1 Int)) Bool
    (ite (and (= x!0 0) (= x!1 0)) false
      false))
)

```

I don't understand why z3 assign 0 to the variables while I only have 1, 2 and 3 as vertices?

Another suggestion was :

```
(set-option :fixedpoint.engine datalog)
(define-sort s () Int)

(declare-rel edge (s s))
(declare-rel path (s s))

(declare-var a s)
(declare-var b s)
(declare-var c s)

(rule (=> (edge a b) (path a b)))
(rule (=> (and (path a b) (path b c)) (path a c)))

(rule (edge 1 2) r-1)
(rule (edge 2 3) r-2)
(rule (edge 3 1) r-3)

(assert
         (=> (path a a)
            false
            )

 )

(check-sat)
(get-model)

```

Which returns the result:

```
> z3 test2.txt
sat
(model
  (define-fun a () Int
    0)
  (define-fun path ((x!0 Int) (x!1 Int)) Bool
    (ite (and (= x!0 0) (= x!1 0)) false
      false))
)

```

Any idea to resolve this problem?

Note: I need to use Datalog for reasons of complexity.

# Answer
> 1 votes
I don't think you can do it in plain Datalog, but you can do it in Datalog plus negation.

I suggest you define a relation $R$, so that $R(x,y)$ is true if vertex $y$ is reachable from vertex $x$ in one or more steps. You can define $R$ recursively, namely,

$$R(x,y) = E(x,y) \lor \exists w . E(x,w) \land R(w,y),$$

where $E$ is a relation that represents the edges in the graph ($E(x,y)$ is true iff $(x,y)$ is an edge in the graph). Now the graph has a cycle iff $\exists x . R(x,x)$ is true. I think you should be able to translate this in Datalog.

From this you can get a Datalog instance that is satisfiable if there is a cycle in the graph, or unsatisfiable if there is no cycle.

If you want the reverse (an instance that is satisfiable iff there is *no* cycle), I think you need negation.

The details of how to express that in Z3 code seem off-topic here.

---
Tags: graphs, logic, sat-solvers, datalog
---


# Question
Title: What is the optimal algorithm for finding all sets of overlapping ranges?
I have a set of (integer) ranges and want to compute the (possibly non-disjoint) set of all subsets of overlapping ranges. The data structure used for the output is not of particular importance to me; if a linked list can be used to reduce the run time, for example, then that's alright with me.

## Formal problem

Consider a set of integer ranges $R$. Find the largest set $O = \\{ R\_i \subset R \\}$ where each (non-empty, unique) $R\_i$ satisfies $\forall r, r' \in R : r \ \text{overlaps}\ r' \iff r, r' \in R\_i$.

What is the algorithm with the lowest known time complexity for solving this problem?

# Answer
Sort the ranges by their start points. Then your overlapping ranges can be found in $O(k + n)$ where $k$ is the number of overlapping pairs and $n$ is the input size simply by a double loop. In C:

```
int i, j;
for (i = 0; i < n; ++i) {
    int start = start_points[i];
    for (j = i + 1; j < n && start_points[j] < end_points[i]; ++j) {
        output(i, j);
    }
}

```
> 1 votes

---
Tags: algorithms, sets, enumeration
---


# Question
Title: Median of medians: bound on pivot position
If I understand correctly (from reading Wikipedia), median-of-medians pivot selection makes quickselect $O(n)$ because the pivot is guaranteed to be in between the 30th and 70th percentiles and so at least 30% of elements will be removed in each selection pass.

But I have tried to prove this percentage inductively but failed. In fact, I have found what I thought is a counterexample (where $\vec{v} \times n$ repeats $\vec{v}$'s elements $n$ times and $+$ is concatenation, as in Python lists):

\begin{align} \begin{bmatrix} 1 & 2 & 3 & \infty &\infty \end{bmatrix} \times 3 + \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2 \\\+ \begin{bmatrix} 4 & 5 & 6 & \infty &\infty \end{bmatrix} \times 3 + \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2\\ \+ \begin{bmatrix} 7 & 8 & 9 & \infty &\infty \end{bmatrix} \times 3 + \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2\\ \+ \begin{bmatrix} 10 & 11 & 12 & \infty &\infty \end{bmatrix} \times 3 + \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2\\ \+ \begin{bmatrix} 13 & 14 & 15 & \infty &\infty \end{bmatrix} \times 3 + \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2 \end{align}

In place of $\infty$ we can just put any large number.

After the first step, we have: \begin{bmatrix}3&3&3&\infty&\infty&6&\cdots&9&\cdots&12&\cdots &15&15&15&\infty&\infty\end{bmatrix} Second step: \begin{bmatrix}3&6&9&12&15\end{bmatrix} Finally we get the median-of-medians $9$. However in the initial array only $3\cdot 3\times 3 = 27$ of $5 \cdot (2+3) \cdot 5 = 125$ elements ($21.6\\%$) are $\le 9$. Which seems to violate the 30% bound.

I doubt the algorithm is incorrect so what am I getting wrong? A proof would be much appreciated.

# Answer
> 2 votes
You missed **the recursive step of this recursive algorithm**.

For the sake of discussion, **assume you want to find the 99th smallest element of the initial 125 elements**. Here 99 is just an arbitrary number between 1 and 125.

After you have got the first batch of medians below, $$\[3\\,\\,3\\,\\,3\\,\\,\infty\\,\\,\infty,\\,\\,6\\,\\,6\\,\\,6\\,\\,\infty\\,\\,\infty,\\,\\,9\\,\\,9\\,\\,9\\,\\,\infty\\,\\,\infty,\\,\\,12\\,\\,12\\,\\,12\\,\\,\infty\\,\\,\infty,\\,\\,15\\,\\,15\\,\\,15\\,\\,\infty\\,\\,\infty\]$$ you are supposed to **apply the same algorithm to find its median,** $m\_1$, its actual real median instead of an approximate median.

When you get the second batch of medians, $$\begin{bmatrix}3&6&9&12&15\end{bmatrix}$$ you are supposed to **apply the same algorithm to find its median,** $m\_2$. In fact, we have reached the base case of the recursion. So we just use some simple routine to get its median, $m\_2=9$.

Using 9 as the pivot, we will find in the second batch of medians, two elements that are smaller than 9, 3 and 6. Going back to the first batch of medians, we will then skip three 3's and three 6's and two 9's, 3+3+2=8 elements in total. That is where the 30% comes from: $8 \ge 25 * 30\\%$. We also find $12\gt9$ and $15\gt9$. Going back to the first batch of medians again, we will skip $\[\infty,\infty\]$, $\[12,\infty,\infty\]$ and $\[15,\infty,\infty\]$, another 8 element in total. That is where the 70% comes from. Now it is time to run the same algorithm again to find the median $m\_1$ as the median of the remaining $25-8-8=9$ elements, $$\[\infty\\,\\,\infty\\,\\,\infty\\,\\,\infty\\,\\,9\\,\\,12\\,\\,12\\,\\,15\\,\\,15\]$$

$\cdots, \cdots, \cdots$ (rounds of recursions omitted)

Finally, we find that $m\_1=15$ (the first 15). Using 15 as the pivot, we will find in the first batch of medians, $3\<15$, $6\<15$, $9\<15$ and $12 \< 15$. Going back to the initial 125 elements, we will skip three \[1,2,3\], three \[4,5,6\], three \[7,8,9\], three \[10,11,12\] and one \[15, 15\], 3\*3\*4+2=38 elements in total. That is again where the 30% comes from: $38 \ge 125 * 30\\%$. We will apply the same algorithm to find the ultimately wanted element as the $99-38=61$-th smallest element of the remaining $125-38=87$ elements. Why can we skip those 38 elements? Because each of one of them is not greater than $m\_1$, which is no greater than the 38 elements on the big side. Together with the fact $38 + 99 \ge 125$, we know the 99-th smallest element must be one of the remaining elements.

Hopefully, I have given enough explanation to show where you have gone wrong. Hopefully, you will appreciate the ingenuity and subtlety of this algorithm of median of medians more.

For more analysis, you may want to check the beautiful visualization page of the algorithm. You may want to read wikipedia. You can also read CLRS, edition 4, section 9.3, "Selection in worst-case linear time" and its accompanying exercises, whose analysis on the pivot and the recurrence relation is more rigorous and comprehensive.

---
Tags: algorithms, complexity-theory, algorithm-analysis, sorting, selection-problem
---