# Question
Title: What does the leading turnstile operator mean?
I know that different authors use different notation to represent programming language semantics. As a matter of fact Guy Steele addresses this problem in an interesting video.

I'd like to know if anyone knows whether the leading turnstile operator has a well recognized meaning. For example I don't understand the leading $\vdash$ operator at the beginning of the denominator of the following:

$$\frac{x:T\_1 \vdash t\_2:T\_2}{\vdash \lambda x:T\_1 . t\_2 ~:~ T\_1 \to T\_2}$$

Can someone help me understand? Thanks.

# Answer
On the left of the turnstile, you can find the local context, a finite list of assumptions on the types of the variables at hand.

$$ x\_1:T\_1, \ldots, x\_n:T\_n \vdash e:T $$

Above, $n$ can be zero, resulting in $\vdash e:T$. This means that no assumptions on variables are made. Usually, this means that $e$ is a closed term (without any free variables) having type $T$.

Often, the rule you mention is written in a more general form, where there can be more hypotheses than the one mentioned in the question.

$$ \dfrac{ \Gamma, x:T\_1 \vdash t : T\_2 }{ \Gamma\vdash (\lambda x:T\_1. t) : T\_1\to T\_2 } $$

Here, $\Gamma$ represents any context, and $\Gamma, x:T\_1$ represents its extension obtained by appending the additional hypothesis $x:T\_1$ to the list $\Gamma$. It is common to require that $x$ did not appear in $\Gamma$, so that the extension does not "conflict" with a previous assumption.
> 19 votes

# Answer
As a complement to the other answers, note that there are three levels of "implication" in typing derivations. And the same remark holds with logical derivations since there is actually a correspondence between the two (called the Curry-Howard's correspondance).

The first implication is the arrow that appears in formulas, and it corresponds to logical implication in a formula (or a function type for the $\lambda$-calculus).

The second implication is materialized by the turnstile symbol, and means "assuming every formula on the left, the formula on the right holds". In particular, the rule you give tells how one should prove an implication: to prove $A \Rightarrow B$, then one must prove $B$ under the assumption that $A$ holds. In terms of the $\lambda$-calculus, to prove that $\lambda x.t$ has type $A \to B$, one must show that $t$ has type $B$, assuming that $x$ is a variable of type $A$ (see the correspondence?).

The third level of implication is materialized by the horizontal bar, and means "if every premise (elements at the top) holds, then the conclusion (the element at the bottom) holds". You can link that to the interpretation of the typing rule for $\lambda$-abstraction that you gave (see the explanation in the previous paragraph).
> 7 votes

# Answer
In type checking systems, the ($\vdash$) represents the ternary relation over type environments, expressions and types: $\vdash \texttt Env \times \texttt Exp \times \texttt Typ$.

In your example, the expression $t\_2$ is typed at type $T\_2$ *wrt* a type environment having a type assumption mapping $T\_1$ to some type variable $x$

In this context, a type environment is a partial function that assigns types to variables, usually denoted with $\Gamma$ where $\Gamma \in \texttt Env : Var \rightharpoonup Typ$

Note that, the operator reserves its functionality regardless of where it appears, either in the premise or the conclusion of the rule.
> 4 votes

# Answer
In every situation that I've seen, $X\vdash Y$ means that there is a proof of $Y$ assuming that $X$ holds. If $X$ is empty, that means that $Y$ is a tautology: it has a proof without needing any assumptions.
> -1 votes

---
Tags: type-theory, denotational-semantics
---


# Question
Title: Why are floats converted from different integers sometimes equal?
I'm trying to understand the following algorithm:

```
int ubnd = Integer.MAX_VALUE
int lbnd = ubnd
while (fload)lbnd == (float)ubnd {
    lbnd = lbnd - 1
}
lbnd = lbnd + 1
print "$lbnd..$ubnd"

```

I don't see why for 63 iterations of the loop, we have `(float)lbnd == (float)ubnd`. It has something to do with the conversion of integers to floats, but I don't know what. I know that integers and floats both have 32 bits, but there must be a different way of storing them. Could someone help me out?

# Answer
"float" and "int" in Java both use 32 bits. "float" can represent some numbers that "int" can't, like 0.5. Since 32 bits let you store exactly $2^{32}$ different values, it should be obvious that there must be "int" values that you cannot store in a "float".

"float" in Java, and "float" in many other language implementations, uses one bit for the sign, 8 bits for an exponent, and 23 bits plus one implicit bit for the mantissa. As numbers get bigger, the distance from one "float" to the next gets bigger. The 23 bit mantissa lets you store exactly the integers in the range $2^{23}≤x\<2^{24}$, all the even integers in the range $2^{24}≤x\<2^{25}$, all multiples of four in the range $2^{25}≤x\<2^{26}$ etc.
> 1 votes

---
Tags: floating-point, integers, number-formats
---


# Question
Title: Exponential averaging for SJF CPU scheduling
> Calculate the exponential averaging with $T\_1 = 10$, $\alpha=0.5$ and the algorithm is SJF with previous runs as $8,7,4,16$.
>
> 1. 9
> 2. 8
> 3. 7.5
> 4. None

I am getting 4. None as the answer.

But it is given that 3. 7.5 is the correct answer. I think I am missing something here.

Because I only used the formula, $S\_{n + 1}{}{}{}{} = a(T\_n) + (1-a)\*S\_n$.

# Answer
A possible interpretation of the problem is that we initially had jobs with actual run times 8, 7, 4, and 16. Assuming no new jobs entered the queue, we'd schedule then in increasing order of their times, namely 4, 7, 8, 16 (since that's what SJF means--shortest job first). Under these assumptions we'd have time slices $$\begin{align} T\_2&=\frac{1}{2}(4+10)=7&\text{after the first job has run}\\ T\_3&=\frac{1}{2}(7+7)=7&\text{after the second job has run}\\ T\_4&=\frac{1}{2}(8+7)=7.5&\text{after the third job has run}\\ \end{align}$$ so the fourth job would be given a slice of 7.5, which is choice (3).

This isn't an entirely satisfactory answer since of course the OS might not know how much time the jobs would actually take before hand, but if the problem assumed they'd be run in that order (4, 7, 8, 16) we'd have what was mentioned as the correct answer, so it's at least a *possible* interpretation.
> 2 votes

# Answer
Rick is right,
Initially tau$(Γ1)=10$ and $\alpha=0.5$ and the run times given are $8,7,4,16$ as it is shortest job first,
So the possible order in which these processes would serve will be $4,7,8,16$ since SJF is a non-preemptive technique.
So, using formula: $Γ 2 $= $\alpha$$\cdot$T1 + (1-$\alpha$)$ Γ 1$
so we have,
$Γ 2$=$0.5\*4+0.5\*10$ = $7$, here $T1=4$ and $Γ 1=10$
$Γ 3=0.5\*7+0.5\*7$ = $7$, here $T2=7$ and $Γ 2=7$
$Γ 4=0.5\*8+0.5\*7 $= $7.5$, here $T3=8$ and $Γ 3=7$

So the future prediction for $4th$ process will be $Γ 4=7.5$ which is the option$(3)$,
This method of exponential averaging to find predicted future service time of a process is actually not in practical use as we can’t find the history of actual burst times before doing all this.
> 0 votes

# Answer
Initially T1 = 10 and α = 0.5 and the run times given are 8, 7, 4, 16

As it is shortest job first, the possible order in which these processes would serve will be 4, 7, 8, 16 since SJF is a non-preemptive technique. So, using formula: T2 = α\*t1 + (1-α)T1

so we have, T2 = 0.5\*4 + 0.5\*10 = 7, here t1 = 4 and T1 = 10 T3 = 0.5\*7 + 0.5\*7 = 7, here t1 = 7 and T1 = 7 T4 = 0.5\*8 + 0.5\*7 = 7.5, here t1 = 8 and T1 = 7

So the future prediction for 4th process will be T4 = 7.5 which is the option(c).
> 0 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Fork() execution and number of processes
If a process executes the following code

```
fork();
fork();
fork();

```

The total number of child processes created is given as 7 by a text book. But how does that happen

fork generates 2 processes right? Are both the processes referred to as child processes? One process is the parent parent and one is the child right? Even if both the processes are referred to as child processes,2\*3=6? The main process is not a child process,how does the number 7 come into the picture.

***Update***:

# Answer
Each fork call duplicate process, so after first call there are two of them. You may call the one with pid = 0, the master process (parent, top, original).

After that two processes are in the second line (second fork), executing it, there are four processes now. I have not seen such distinction, but you may at that point say that two of them are child processes.

After the final fork, there are eight processes altogether, according to your materials, the original process is called parent and the rest are childs.

To draw it properly you should create a tree, with two children after each fork, where in fact one of them is the original caller.
> 3 votes

---
Tags: operating-systems
---


# Question
Title: Can we prove using pumping lemma that language F = {$a^ i b ^j c ^k$ | i, j, k ≥ 0 and if i = 1 then j = k} is not regular?
I am currently solving a problem in which we have to show that we can not prove using pumping lemma that the language mentioned in the question is not regular.Here is the full question

> Consider the language F = {$a^i b^j c^k$ | i, j, k ≥ 0 and if i = 1 then j = k}.
>
> a. Show that F is not regular.
>
> b. Show that F acts like a regular language in the pumping lemma. In other words, give a pumping length p and demonstrate that F satisfies the three conditions of the pumping lemma for this value of p.
>
> c. Explain why parts (a) and (b) do not contradict the pumping lemma.

But, I am able to prove it using pumping lemma that language is not regular. For that I take:

> pumping length as 3
>
> x:a ; y:b ; z:c
>
> $xy^lz$ ∈ F for l = 1
>
> $xy^lz$ ∉ F for l \> 1

Is there some problem with the above shown proof or the question is wrong.

# Answer
> 3 votes
> For that I take:
>
> x:a ; y:b ; z:c

You can't do that. You have to first give a pumping length $p$ and then you have to show that there is *no* decomposition of the word $abc$ into $xyz$ with $|y|\ge 1$ and $|xy| \le p$ for which $xy^n z \in F$. If we take your word $abc$ and decompose as $x=\varepsilon$, $y = a$, $z=bc$ then the pumped words are $a^nbc$ and are all in $F$.

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


# Question
Title: Basic control statements for Turing equivalence?
Apologies ahead of time, I don't fully understand what I'm asking...

But, is it possible to program using only 'while loops' and still be Turing equivalent?

Or more generally, can I do everything with 'while loops' that I could with 'if statements' and 'for loops'?

# Answer
> 0 votes
`for(X; Y; Z) { Body; }` is just syntax sugar for `{X; while (Y) { Body; Z; }}`.

`if` can be simulated easily: rewrite `if (X) { Body; }` as `while (X) { Body; break; }`.

---
Tags: computability, programming-languages
---


title: Array of overlaping ranges

text:
# Question
Title: Array of overlaping ranges
Consider that I have an array of ranges and I want to transform it to the new array that represents the ranges that any range is in.

# Example:

Ranges: \[red: \[1,11\], black: \[15,16\],yellow: \[5,9\], green: \[7,8\]\]

# Result:

* \[1,4\] - red
* \[5,7\] - red & yellow
* \[7,8\] - red & yellow & green
* \[8,9\] - red & yellow
* \[10,11\] - red
* \[15,16\] - black

My first thought was to use interval tree but the most implementations I found want to ask tree by range and I want to explicitly list groups as shown in example.

# Answer
> 2 votes
Sort all coordinates of intervals (annotated with their significance), and scan them in order.

As an example, in your case you would get $$ 1^{+red},5^{+yellow},7^{+green},8^{-green},9^{-yellow},11^{-red},15^{+black},16^{-black} $$ This immediately gives the decomposition into intervals $$(1,5),(5,7),(7,8),(8,9),(9,11),(11,15),(15,16)$$ with associated colors.

Note that this list differs from your output, since you sometimes move the endpoint back by 1 point for some unspecified reason.

---
Tags: algorithms, trees, intervals
---


# Question
Title: How would you create a Turing machine that copies a string and prints it to the tape?
For example, if I have a start state of $i$ and a string $w$, how could I create a Turing machine that would halt when the tape content is $w \Box w$? The language is $\\{a,b\\}$.

My initial idea was a machine that:

On $i$, moves right and changes to $p$.

On $p$, if letter read is $a$, move $n+1$ cells to the right and change to $x$.

On $p$, if letter read is $b$, move $n+1$ cells to the right and change to $y$.

On $p$, if $\Box$, change to $h$.

On $x$, write $a$, move $n$ cells to the left and change to $p$.

On $y$, write $b$, move $n$ cells to the left and change to $p$.

On $h$, halt.

However, I don't think it'll work because Turing machines aren't allowed to move more than 1 cell at a time. Any help would be appreciated.

# Answer
> 1 votes
You are pretty close, here is a TM deciding the language (pseudocode):

1. Check the input contains a single $\Box$,

* If false, reject.
2. Zig-zag across the tape, check identical letters, and replace them by $X$.
    * If not identical, reject.
3. When all the letters left of $\Box$ are marked $X$, check for remaining letters right of $\Box$
    * If there are remaining letters, reject.
    * Otherwise, accept

# Answer
> 0 votes
How can you move exactly $n+1$ squares? Put a special mark at the end before you leave, then move back to the mark.

How can you remember which character to copy? You have a finite alphabet, so duplicate the states you use for each character. For example, you'll be in $p\_a$ when copying character $a$ and in $p\_b$ when copying character $b$.

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


# Question
Title: Name of algorithm: When looking for an optimal element in a list, contionusly adapt the acceptance threshhold
I'm looking for one of two closely related algorithms. In both, you have a list of elements, of which you have to choose one by some scoring method. In the first variation, the list is infinite and you can't go trough it all, but you can choose any item. In the second, you must choose to accept or reject an item permanently, so if you get to the end, and the last item is a dud, you're stuck with it.

You have no prior knowledge of the range of scores found in the list. As you look at elements of the list, continuously adapt your threshold for acceptance, until you are able to choose an item without having exhausted the list.

For the second variation (finite list), I've seen it in some semi-joking context about dating, where you spend up until age 35 dating people as "samples" and rejecting them all in due time, then past age 35, take the first person who is above the threshold learned from the previous samples.

# Answer
These problems are in the field of optimal stopping theory. There are a large number of approaches to the problem, which can be found using this term.

The example about dating appears in Hannah Fry's Ted Talk "The Mathematics of Love"
> 2 votes

---
Tags: algorithms, search-problem, selection-problem
---


title: Show that $\log n = o(n^\epsilon)$

text:
# Question
Title: Show that $\log n = o(n^\epsilon)$
I am trying to understand how to prove that a polynomial will always grow faster than a logarithm.

$\log n = o(n^\epsilon), \epsilon\>0$

Intuitively, it is obvious, and plugging in a few numbers always yields true, but how can I prove this?

Maybe this can be done inductively (I would prefer this method if someone would explain it), but I attempted to prove through the use of derivatives and L'Hôpital's rule, namely:

$\lim\_{n\rightarrow\infty}\frac{\log n}{n^\epsilon} = \lim\_{n\rightarrow\infty}\frac{\frac{1}{n}}{\epsilon n^{\epsilon-1}}$ = 0

Is this getting me in the right direction to prove that the upper bound of $\log n$ it is strictly less than $n^\epsilon$?

# Answer
Here is a simple proof which avoids L'Hôpital's rule.

We start with the observation $$ \log n = \int\_1^n \frac{dx}{x} \leq \int\_1^n dx \leq n, $$ and so $$ \frac{\log n}{n^2} \leq \frac{1}{n} \xrightarrow{n\to\infty} 0. $$

Given $\epsilon \> 0$, using the fact that $\lim\_{n\to\infty} n^{\epsilon/2} = \infty$, we see that $$ 0 = \lim\_{n\to\infty} \frac{\log (n^{\epsilon/2})}{(n^{\epsilon/2})^2} = \lim\_{n\to\infty} \frac{\frac{\epsilon}{2} \log n}{n^\epsilon}. $$ It follows that $$ \lim\_{n\to\infty} \frac{\log n}{n^\epsilon} = 0. $$
> 3 votes

# Answer
Let us first prove the probably more common fact, any growing exponential function grows faster than a monomial. (You can just skip this part if it is known to you.)

For any $\alpha\>0$, $\beta \> 1$, we can choose an integer $c\gt \alpha$. Applying L'Hôpital's rule $c$ times we get

$$0\le\lim\_{x\to\infty}\frac{x^\alpha}{\beta^x}\le\lim\_{x\to\infty}\frac{x^c}{\beta^x} 0=\lim\_{x\to\infty}\frac{cx^{c-1}}{(\log\beta)\beta^x}\\ =\lim\_{x\to\infty}\frac{cx^{c-1}}{(\log\beta)\beta^x}=\lim\_{x\to\infty}\frac{c(c-1)x^{c-2}}{(\log\beta)^2\beta^x}\\ =\cdots=\lim\_{x\to\infty}\frac{c(c-1)\cdots2\cdot1}{(\log\beta)^c\beta^x}=0$$ where the last equality holds since $\beta^x = (1+(1-\beta))^x\gt1+x(1-\beta)\to\infty$ as $x\to\infty$.

So, $x^\alpha = o(\beta^x)$ for any $\alpha\>0$, $\beta \> 1$.

---

Let $\alpha = 1, \beta=e^\epsilon$. By a change of variable $x=\log n$, we can see that $$\log n = o(e^{\epsilon\log n})=o(n^\epsilon)$$ Similarly, we have $$\log\log n = o((\log n)^\epsilon) \quad\text{ for any }\epsilon\gt 0 $$ $$e^n = o(\lambda^{e^n}) \quad\text{ for any }\lambda\gt 1 $$
> 1 votes

# Answer
Your solution is one tiny step away from proving that the limit is zero.

But obviously log n has no upper limit. And if eps is small, it will take a very large n to make n^eps \< log n.

I recommend that you use a spreadsheet and try this. If eps = 0.001 then n must be as large as 10^1000 just to make n^eps = 10.
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Data structure for a tree of points moving in space
I'm trying to come up with a data structure for a following model: Nodes representing points in space are structured in a tree (general rooted tree with no restrictions). Let's call these nodes "joints". Joints contain information about their position and their axis of rotation: Whole subtrees may rotate around their parent joint's axis by any given angle.

The described tree can be treated as the input. I need to store this data in some data structure, that would provide these two operations as efficient as possible:

* `rotate(id, angle)`: Rotate a given joint with its subtree by a given `angle` around its parent's axis.
* `get_position(id)`: Retrieve the current position of a joint (including leaves) by its `id`.

(The `id` may be the original coordinates, some arbitrary integer stored inside the joint etc.)

There are no strict limits on the time complexities of these operations. But obviously I'm looking for a complexity better than linear (logarithmic would be ideal), as that could be achieved with a straightforward approach. Neither there are any strict limits on space complexity. This structure doesn't have to be dynamic necessarily: I don't need `insert` or `delete` operations, I only need to store the information about the joints once.

The input tree is not balanced, and there is no way to balance it, as it would loose information about the subtrees' dependencies. So I thought the natural approach would be to construct a different tree structure with some relation other than simply `parent node -> subtree` as `joint -> joints dependent on its rotation`. But what relation could give me some good results?

# Answer
You can solve this with a heavy-light decomposition of the tree. This will give you a data structure where the "rotate" operation runs in $O(\log n)$ time and the "retrieve position of leaf" operation runs in $O(\log^2 n)$ time, where $n$ is the number of nodes in the tree. Heavy-light decomposition is a big cannon, so it's possible there might be some simpler solution, but this should work. Let me explain the ideas in several steps.

# Closure property of affine transformations

If $T$ is a a rotation around some point in space, note that it can be represented as an affine transformation. Also, the set $\mathcal{T}$ of affine transformations is closed under composition. In particular, if $T\_1,T\_2$ are two affine transformations, let $T\_2 \circ T\_1$ denote the result of first applying transformation $T\_1$, then applying transformation $T\_2$; then $T\_2 \circ T\_1$ is itself an affine transformation, and its parameters can be efficiently computed from the parameters of $T\_1,T\_2$. So, if we have a sequence of transformations that should be applied to a point, we can concisely represent the composition of the sequence of transformations by $O(1)$ parameters (namely, the parameters of their composition). This will be useful in a moment.

In particular, rather than updating the position of individual nodes, we will store information to help us recover the transformation that should be applied to any particular node. When we want to retrieve up the location of a node, we first look up this transformation, then apply it to the original location of that node to obtain its current location, and output that.

# Warm-up: a path

As a warm-up, let's consider the most extreme special case of your situation: where the tree is a path of length $n$, i.e., each node has exactly one child, and there is a single leaf. I'll assume each node in this original tree may have a position associated with it.

**Data structure.** We can build a data structure for this case where all operations run in $O(\log n)$ time. Build a complete binary tree (of height $\lceil \lg n \rceil$) over these $n$ nodes; to give it a name distinct from your original tree, call this the "index tree". Each node of the original tree is a leaf in the index tree. Each node $w$ of the index tree corresponds to a consecutive subpath of the original tree/path (namely, the ones corresponding to the leaves of the index tree that are descendants in the index tree of $w$).

Now each node $v$ of the original tree has a transformation $T\_v$ associated with it. Suppose a node $w$ of the index tree corresponds to the subpath of nodes $v\_1,\dots,v\_k$ in the original tree. Then we will label $w$ with the transformation $T\_{v\_k} \circ \cdots \circ T\_{v\_1}$. This will help us to retrieve the position of points in the original tree.

**Rotation operations.** To support rotation operations, if we want to rotate node $v$ in the original tree and all its descendents, then we follow the path (in the index tree) from $v$ to the root of the index tree. By construction, there are only $\lg n$ such nodes to visit. We'll need to update the label on each of these nodes in the index tree. That is easy. In particular, the label $T\_w$ on each node $w$ in the index tree can be computed from the labels $T\_{w\_1},T\_{w\_2}$ on its two children $w\_1,w\_2$ as $T\_w = T\_{w\_2} \circ T\_{w\_1}$. So, to handle a rotation operation on node $v$ in the original tree, we update the the label on $v$ in the index tree, then follow the path (in the index tree) from $v$ to the root of the index tree and recompute the label of each such node in the index tree. All of this can be done in $O(\log n)$ time.

**Retrieval operations.** If we want to retrieve the location of the point associated with node $v$ in the original tree, we can do that in $O(\log n)$ time, too. Consider the path in the original tree from its root to $v$. This is a subpath of the original tree. It turns out that it can be expressed as the disjoint union of $O(\lg n)$ subpaths, where each subpath corresponds to a node in the index tree. Let $w\_1,\dots,w\_k$ be those nodes in the index tree. Then the transformation that needs to be applied is $T\_{w\_k} \circ \cdots T\_{w\_1}$; we apply this to the original location of $v$, and output that. This can all be done in $O(\log n)$ time.

So this handles the case of a path, i.e., a tree of depth $n$. This shows that it is possible to handle imbalanced trees. But how do we handle the general case? I'll show that next.

# General case: an arbitrary tree

To handle an arbitrary tree, we will first build a heavy-light decomposition of the tree. This expresses the edges of the tree as a union of (disjoint) heavy paths, plus some light edges; with the property that any path from the root to some leaf visits at most $O(\log n)$ light edges. We'll treat each individual heavy path as a case of the warmup above, i.e., we'll build one index tree per heavy path, to keep track of the transformations associated with the nodes in the heavy path. Also, we'll have a path tree that stores the light edges, and we'll store the transformation associated with the head of a light edge in that node of the path tree.

**Rotation operations.** To handle a rotation operation, we update the associated node in the path tree (if it is the head of a light edge) or do the appropriate update operation on the corresponding index tree (if it is the head of a heavy edge). This can be takes $O(\log n)$ time at worst.

**Retrieval operations.** To retrieve the location of a node $v$ in the original tree, we follow the path in the path tree from the root to $v$. This will involve traversing at most $O(\log n)$ light edges. It also traverses at most $O(\log n)$ heavy paths. In each heavy path, we might potentially traverse many vertices of the heavy path (possibly much more than $O(\log n)$ of them), but we don't need to visit all of them; since that is a consecutive subpath of the heavy path, we can quickly retrieve the transformation associated with that subpath (i.e., the composition of the transformations of the nodes in that heavy path) using the index tree for that subpath. This takes $O(\log n)$ time per heavy path, and there are at most $O(\log n)$ heavy paths to visit. Finally, we compose all of these transformations and apply it to the original location of $v$.

Naively, the running time seems to be $O(\log n)$ time for the light edges, plus $O(\log n) \times O(\log n)$ time for the heavy paths, for a total of $O(\log^2 n)$ time.

This achieves all of your goals, and gives a guaranteed worst-case running time of $O(\log n)$ for the rotate operation and $O(\log^2 n)$ time for the lookup operation, no matter what shape the original tree has.
> 2 votes

# Answer
As far as I understand your requirements,

1. You want to store a set of points in a tree, not necessarily balanced.
2. You want to be able to rotate any sub-tree about its root point, by any angle
3. You want to find the final coordinates of any point after after a set of rotation operations as specified above.

Since we'll be storing 2D points in a tree structure, I'll be using a point QuadTree approach to store the points. Let the structure of a node of the tree be as follows: $ Node := (x,y,\theta,q1,q2,q3,q4,parent)$. Where

* $x,y$ is the co-ordinate of a point.
* $\theta$ is the resultant angle by which the point's tree has been rotated to after an arbitrary number of rotation operations.
* $q1,q2,q3,q4$ are pointers to the quadrants with respect to $(x,y)$.
* $parent$ is a pointer to the parent node.

**Functions for the QuadTree**

1. $insertPoint(x,y)$
This would be a standard QuadTree insertion algorithm while setting $\theta=0$ for the newly inserted node.
2. $searchPoint(x,y)$
This would search the QuadTree for a node representing $(x,y)$ and return a pointer to it. This will be used ahead.
3. $rotatePoint(x,y,\theta)$
This would be a standard QuadTree search for $(x,y)$. Then upon finding the particular node, set $node.\theta = node.\theta + \theta$ i.e. add and store the rotation angle into the $\theta$ value already in the node.
4. $calculateResultantCoordinates(x,y)$
This is where the magic happens.
This function will return a $(x',y')$ pair consisting of the resultant co-ordinates of the $(x,y)$ passed to the function.
**pseudo-code**

```
calculateResultantCoordinates(x,y)
 {
  n = searchFor(x,y)
  if (n is null)
   // error handling

  (x,y)=(n.x,n.y)

  while ( n.parent != null )
    {
     if ( n.parent.theta == 0 )
       continue

     x = x - n.parent.x
     y = y - n.parent.y
     // (x,y) now represent a complex number (x + j*y)
     // rotating a complex number can be done by multiplying it with $e^{j*\theta}$ = $cos(\theta) + j*sin(\theta)$

     // the resultant point is
     // $(x*cos(\theta)-y*sin(\theta),x*sin(\theta)+y*cos(\theta))$
     p = x*cos(p.theta) - y*sin(p.theta)
     q = x*sin(p.theta) - y*cos(p.theta)

     (x,y) = (p,q)
     n = n.parent
     // traverse the path from leaf to the root node
    }

  return (x,y)
 }

```
> 2 votes

---
Tags: data-structures, trees
---


# Question
Title: Count numbers less than $x$ co-prime to $p$
We have given two numbers $x$ and $p$. We want to count how many numbers are less than $x$ and are co-prime with $p$.

I know that we can solve the problem in $O(x\log x)$ with iterating over all numbers less than $x$ and check if their greatest common divisor is $1$.

Is there any way to solve this faster, because I think that we can reduce this somehow. Please give some hints on where to start working.

# Answer
> 5 votes
There's a very fast method if p has few prime factors. Say p is a prime. Then the numbers co-prime with p are all numbers other than p, 2p, 3p, 4p etc. There are x-1 numbers less than x, and of those floor ((x-1) / p) are divisible by p, so exactly (x-1) - floor ((x-1) / p) are co-prime with p. For simplicity, let f(n) = floor ((x - 1) / n), then for a prime p the result is f (1) - f (p).

If p has two prime factors a, b, then we would start with f(1) - f(a) - f(b) - take all numbers, except those divisible by a, except those divisible by b. But here is a mistake: Numbers divisible by ab have been removed twice, so we add them back: f(1) - f(a) - f(b) + f(ab).

For three prime factors a, b, and c, we use the same scheme and start with f(1) - f(a) - f(b) - f(c) + f(ab) + f(ac) + f(bc). Numbers divisible by abc have been removed three times, added back three times, and therefore need to be subtracted once, giving f(1) - f(a) - f(b) - f(c) + f(ab) + f(ac) + f(bc) - f(abc).

You can continue this. You'll have to figure out yourself what exactly to add or subtract. With k different prime factors, you have 2^k terms - but clearly with 10 different prime factors, and say x = 1,000,000, you have only 1024 different terms. Also, as soon as a product is greater than x, you can ignore it. For example, all prime factors ≥ x of p can be completely ignored. And all duplicate prime factors can be ignored.

Actually, the number of different prime factors grows very slowly, so this method is quite good unless x is small.

How many numbers less than a billion are co-prime with $10^{100}$? Prime factors of $10^{100}$ are 2 and 5, so the answer is 999,999,999 - 499,999,999 - 199,999,999 + 99,999,999 = 400 million.

# Answer
> 3 votes
Are you familiar with the Sieve of Eratosthenes? Play around with how it might be used in this case. Your answer likely lies there.

---
Tags: number-theory, counting
---


title: Reduce Dominating Set to Minesweeper

text:
# Question
Title: Reduce Dominating Set to Minesweeper
So, I have two problems:

1. *Minesweeper:* given an undirected graph where some vertices have a whole number associated with them, check if there is a way to mark some of the non-numbered vertices such that the number in each numbered vertex is equal to the amount of its marked neighbours.
2. *Dominating set:* given an undirected graph and an integer $k$, check if there is a way to mark exactly $k$ vertices such that each non-marked vertex has at least one marked neighbour.

I need to construct a polynomial reduction from the second problem to the first (that is, using the solution to the first problem, construct a polynomial solution to the second).

I do understand that I will need to add some additional numbered vertices to the graph (because numbering any of the existing vertices will prevent it from being marked). I've tried to add a support vertex for all of the original ones and connect each support vertex to the same vertices, and after that brute-force my way through numbers in each support vertex. The problem is --- that's $O(n^n)$ and definitely not a polynomial.

How can I do this in polynomial time?

# Answer
Given an instance $(G, k)$ of **DOMINATING SET**, we construct our instance of **MINESWEEPER** as follows.

* Add a new vertex $s$, connect $s$ with all the vertices of $V(G)$. **Label** $s$ with $k$.
* For each $v\in V(G)$, add a new vertex $s\_v$. Connect $s\_v$ to all the vertices of $N(v)\cup\\{v\\}$ (the neighborhood of $v$ and $v$ itself). Connect $s\_v$ to $|N(v)| - 1$ new *dummy vertices*. **Label** $s\_v$ with $|N(v)|$.

Call the constructed graph $G'$. The produced **MINESWEEPER** instance is $G'$ itself.

We claim that $(G, k)$ is a **YES** instance of **DOMINATING SET** iff. $G'$ is a **YES** instance of **MINESWEEPER**.

*Proof*: If $(G, k)$ is a **YES** instance of **DOMINATING SET**, we have a dominating set $S\subseteq V(G)$ with $|S| = k$. By simply marking all the vertices of $S$, we satisfy the label of $s$ in $G'$. Then, for each $s\_v\in V(G')$, according to the number of marked vertices (up to now) in $N(v)\cup\\{v\\}$, we mark some of the dummy vertices connected with $s\_v$. Note that, since $S$ is dominating, $N(v)\cup\\{v\\}\cap S\neq\emptyset$, so at most $|N(v)|-1$ dummy vertices needs to be marked to satisfy the label of $s\_v$, so we always have enough number of dummy vertices connected to $s\_v$.

Conversely, if $G'$ is a **YES** instance of **MINESWEEPER**, we denote by $S$ the non-dummy vertices (which also means that these are in $V(G)$) in the solution to this instance. We now show that $S$ is a dominating set of $G$ and $|S|=k$, which concludes our proof. Indeed, to satisfy the label of $s$, we have that $|S|=k$. For each vertex $s\_v$, at most $|N(v)|-1$ dummy vertices connected to it are marked. So in order to satisfy its label, namely $|N(v)|$, either $v$ or some vertex in $N(v)$ is marked. So, in particular, if $v$ is not marked, i.e. $v\not\in S$, there must be some marked vertex in $N(v)$, i.e. $N(v)\cap S\neq\emptyset$. This suffices to prove that $S$ is a dominating set of $G$.$\square$
> 2 votes

---
Tags: complexity-theory, graphs, reductions
---


# Question
Title: There are parsimonious reductions between all NP-Complete problems: Well-known conjecture?
The reduction from SAT to Clique shows a way to construct a graph with cliques from a Boolean formula. A closer look at that reduction even yields a simple algorithm which finds a large clique in the graph from a given satisfying assignment to the variables. That mapping is bijective: each satisfying assignment is mapped to a different large clique, and the number of large cliques is the same as the number of satisfying assignments.

A reduction which preserves the number of solutions is called a *parsimonious* reduction (technical definition below). It is a stronger notion of reduction than the usual Karp reductions, because not all reductions have that property. NP-Completeness is usually defined in terms of Karp-reductions, but since parsimonious reductions are clearly more beautiful, it is natural to conjecture:

**Conjecture:** All NP-Complete problems can be reduced to one another via parsimonious reductions.

But I can't find this in the literature.

**Question:** Does the literature contain the conjecture that all NP-Complete languages can be reduced to eachother via parsimonious reductions?

This is different from the Bertman-Hartmanis conjecture that all NP-Complete problems can be reduced to eachother via polynomial-time invertible bijections. That conjecture is about *instances* of the language, whereas I talk about *certificates* to the NP machine. Of course the most beautiful thing would be a parsimonious bijection! References to that are greatly appreciated.

**Definition** If $L,K\subseteq\\{0,1\\}^\ast$ are languages and $f\colon\\{0,1\\}^\ast\to\\{0,1\\}^\ast$ is a reduction from $L$ to $K$, then we say that $f$ is *parsimonious* if there are polynomial-time nondeterministic Turing Machines $N, M$ accepting $L$ and $K$, respectively such that for all $x\in\\{0,1\\}^\ast$, $\\#N(x)=\\#M(f(x))$, where $\\#N(x)$ denotes the number of certificates accepted by a non-deterministic Turing Machine on input $x$.

(The motivation for the question is that, for my thesis, I found that the reduction in the *quantum* Cook-Levin theorem is parsimonious. Beautiful! I want to conjecture that all quantum NP complete problems have parsimonious reductions, so I am looking for the classical reference)

# Answer
Yes, it is well known conjecture. Oded Goldreich states the fact that "all known reductions among **natural** $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich).
> 2 votes

# Answer
1. **This is an easy consequence of Berman-Hartmanis**.

Assuming that Berman-Hartmanis holds, for every pair of $NP$-complete problems $L, K$, we show that it is possible to parsimoniously reduce $L$ to $K$. In fact, *every* **poly-time invertible bijective reduction** will be parsimonious then.

Indeed, fix some NTM $N$ that decides $L$ and a *poly-time invertible bijective reduction* $f$ from $L$ to $K$ (which always exists by Berman-Hartmanis), consider the following NTM $M$ that decides $K$: on an input $y\in\Sigma^\*$, compute the preimage $x=f^{-1}(y)$ (which is poly-time computable since $f$ is poly-time invertible by assumption), then run $N(x)$.

Clearly, $M$ is a non-deterministic polynomial-time Turing machine accepting $K$. And, for every $x\in L$, denote $y=f(x)$, we have that every certificate $c$ for $x$ according to $N$ is also a certificate for $y$ according to $M$, and vice versa. So, $\\#N(x)=\\#M(y)$. For every $x\not\in L$, $\\#N(x)=\\#M(y)=0$.

2. *If $NP=UP$ (which is considered unlikely) including the subcase of $NP=P$*

Every reduction is then parsimonious without the requirement of being poly-time invertible (or even being bijective) at all.
> 1 votes

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


# Question
Title: Proof of value discovery in complete graphs
I have an assignment

* There are n \> 2 finite processors, two registers for each processor.
* Register s\_i is not readable by the processor p\_i but any other processor can read it.
* Register r\_i is readable and writable by the processor p\_i and any other processor can read it.

I have to solve the problem to let p\_i discover the secret s\_i value by reading r\_i value. I don't have to (probably) come up with something super-scientific a somewhat simple proof will do just fine. I've been reading through various publications (leader election, complete graphs, uniform, etc) but wasn't able to find a point to start from.

# Answer
> 1 votes
If I understand correctly, a rough approach could be as follows.

Each processor $p\_i$ can read $s\_{i+1\ {\sf mod}\ n}$ and write its content to $r\_i$.

Then each processor $p\_i$ can read the wanted value by reading $r\_{i-1\ {\sf mod}\ n}$.

The main issue of this naive algorithm is that some synchronization is needed between the two steps: $p\_i$ must not read $r\_{i-1\ {\sf mod}\ n}$ too soon, before it is written by $p\_{i-1\ {\sf mod}\ n}$.

---
Tags: algorithms, graphs
---


title: Class of given language

text:
# Question
Title: Class of given language
The language given is: $$L = \\{\langle M\rangle \mid M \text{ accepts all strings of length at most 5} \\}$$

I have to find the class to which this language belongs.

Now according to my intuition, recursive enumerable languages are those which have verifiers i.e for any string $w \in L$, there is a way to prove that $w \in L$ and for recursive languages, along with the above condition, for any string $w \notin L$, there is a way to prove that $w \notin L$.

Now, there will be finitely many strings which are of length less than or equal to five. We can make a TM which accepts all of these finitely many strings, and hence, the given language is recursively enumerable.

However, it is not recursive because to prove a string $w \notin L$, the only way to do that would be to "run" the TM on the string to prove that none of the strings greater than length five are accepted and since there are infinitely many such strings, we will never finish checking.

Is this approach correct?

# Answer
> 2 votes
Your approach is slightly incorrect in the sense you have to built a Turing machine that given an input $M$ has to check whether $M$ accepts those strings and not build a Turing machine that itself accepts all those string. Note the difference here. And L is recursively enumerable because you can clearly build a Turing machine $M\_1$ that on input $\<M\>$, constructs the corresponding Turing machine $M$, runs $M$ on all strings y of length at most 5. If $\<M\> \in L$, $M$ would accept all those strings and hence $M\_1$ would accept $\<M\>$, verifying the construction. You can show its undecidable by reducing the Membership problem of Turing machines to L, i.e, $MP \leq\_m L$.

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


title: Weakest reduction for P-completeness

text:
# Question
Title: Weakest reduction for P-completeness
It is common to define $P$-completeness with respect to logspace many-one reductions. I am looking for a complexity class $C$ such that if $C=P$ then all problems in $P$ are $P$-complete under many-one $C$-reductions.

> What is the weakest many-one reduction (computable in class $C$) for which the class of P-complete problems remains unchanged?

Note that $C$ is contained in $P$.

# Answer
There is first-order reductions.

See Immerman's book, Chapter 3, Theorem 3.26 which states that $\mathrm{REACH}\_a$ **is complete for** $\mathrm{P}$ **via first-order reductions**.

Also, see my question, for related information on $\mathrm{NP}$.
> 1 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: Complexity of covering subset of the monoid $(\{0,1\}^n, \text{OR})$
(At the very bottom of this, I will shortly describe the motivation for this question.)

Assume we have a commutative monoid $(G,\circ)$, i.e. a set $G$ with a commutative binary operation $\circ$ that satisfies associativity and the existence of a neutral element. The task is as follows: given some $X \subseteq G$, find a smallest $U \subseteq G$ such that $X \subseteq \langle U \rangle$, where $\langle U \rangle$ is the submonoid generated by the elements of $U$.

Now, if instead of a monoid we had a vector space, the task would be simple: determine the subspace spanned by $X$, and find a base for it. However, this relies on vectors having inverses, which we can't assume to exist in our monoid.

The monoid can be assumed to be fixed, i.e. we don't have to receive it as input, and the only input we receive is $X$. To be more precise, the set $G$ can implicitly be assumed to be $\\{0,1\\}^n$ for some $n$, and $\circ$ is the component-wise $\max$ operation, which is the same as $\\{\text{true}, \text{false}\\}^n$ with component-wise $\text{OR}$.

As an example, assume $n=4$ and we want to cover $$X= \\{(0,1,0,1), (1,1,0,0),(1,0,1,0),(1,1,0,1),(1,1,1,1)\\}$$

then one optimal solution would be $\\{(0,1,0,1), (1,0,1,0), (1,1,0,0)\\}$.

Question: what is the complexity of this problem? I have a feeling it's somewhere between a covering problem and a hull problem, but I can't quite put my finger on whether I've come across a variant of this before or not.

---

The problem arose when a colleague of mine played around with a building block used in LED clocks. They have the structure

```
 _
|_|
|_|

```

and each of those seven lines has its own control wire. We only want to use $10$ of the possible $2^7$ configurations of those control wires, so we tried to figure out whether we can build all $10$ configurations using less than $7$ primitives via OR-ing. Since OR over binary vectors doesn't come with inverses, we only have a monoid.

# Answer
> 1 votes
L. J. Stockmeyer proves that **SET BASIS** is $\mathrm{NP}$-complete.

Reference: *L.J. Stockmeyer*, **The set basis problem is** $\mathrm{NP}$-**complete**, Tech. Report RC-5431, IBM, 1975

Each vector of your problem can be seen as subset of $\\{1, 2, \dots, n\\}$. And the component-wise **OR** operation is corresponding to set union. So a **basis** for a collection of Boolean vector in your problem is exactly a **set basis**.

---
Tags: complexity-theory, optimization, algebra
---


title: Adleman's theorem to $\mathsf{P=BPP}$

text:
# Question
Title: Adleman's theorem to $\mathsf{P=BPP}$
Adleman's theorem gives $$\mathsf{BPP\subseteq P/Poly}.$$

Why is this theorem considered progenitor to derandomization conjecture that $\mathsf{P=BPP}$?

> Does it mean Adleman's result could be considered as evidence $$\mathsf{BPP\subseteq P/Log}$$ is a realistic possibility?
>
> Anaalogously, does it mean $$\mathsf{NP\subseteq P/Poly}$$ could be considered as evidence $$\mathsf{NP\subseteq P/Log}$$ is a realistic possibility?

Is there a satifactory answer without considering Impagliazzo-Wigderson's conditional $\mathsf{P=BPP}$ result?

# Answer
> 2 votes
First of all, $\mathrm{NP}\subset\mathrm{P}/log$ would imply that $\mathrm{NP}=\mathrm{P}$ (try all possible *log*-long **advice** to search for a satisfying assignment in **SAT** problem).

Second, the situation for $\mathrm{BPP}$ is more complicated. Since $\mathrm{BPP}$ languages do not have short certificate, one cannot hope to deduce that $\mathrm{BPP}=\mathrm{P}$ from $\mathsf{BPP\subset P/}log$.

What we can deduce from $\mathsf{BPP\subset P/}log$ is that $\mathsf{BPP\cap NP=BPP\cap co}$-$\mathsf{NP=RP=co}$-$\mathsf{RP=P}$. That is, the part of $\mathsf{BPP}$ inside $\mathsf{NP\cup co}$-$\mathrm{NP}$ is just $\mathrm{P}$.

---
Tags: complexity-theory
---


# Question
Title: Is it possible that the universe of types could be closed?
I asked a pretty vague question. I wasn't able to make it precise, but I can now. It seems to be out of the scope of the previous question, so I open another one.

In dependently-typed languages such as Agda or Idris, it's possible to define a universe inductive-recursively. However, W-types are known to have bad computational characteristics in traditional intensional type theories. Therefore, you need to be able to add new definitions of inductive data types anytime.

My question is, will HoTT improve this situation? That is, to have a closed universe. I know the general formulation of HIT is yet to be discovered, and that people seem not to be able to figure out induction-recursion, so I kind of suspect an definitive answer in the status quo. Still going to give it a chance though.

# Answer
I'm uncertain what you're referring to exactly, but I can remark on a few things.

The first is that the usual problem with W-types is that encoding inductive types with them does not necessarily give you the right induction principles. For instance, we can try to define the natural numbers like so:

```
F : 2 → Type
F 0 = ⊥
F 1 = ⊤

ℕ : Type
ℕ = W 2 F

zero : ℕ
zero = sup 0 absurd

suc : ℕ → ℕ
suc n = sup 1 (const n)

induction : (P : ℕ → Type) → P zero → (∀ n. P n → P (suc n)) → ∀ n. P n
induction pz ps n = ???

```

The problem we'll run into is that induction on $W$ and $2$ allows us to observe the case $n = {\tt sup}\ 0\ f$, but we only have a proof of $P\ ({\tt sup}\ 0\ {\tt absurd})$. So we'll need a way to prove that $f = {\tt absurd}$, but there is no such principle in normal intensional type theory.

The answer to your question in this regard is that homotopy type theory *does* help in this regard, because e.g. univalence implies extensional equality of functions (and cubical type theory also includes this, for instance). So we should not have as many problems recovering the 'right' induction principles for $W$ based encodings.

However, another answer is that we didn't actually need this to begin with. This problem is somewhat particular to the specifics of $W$. Instead, we could use a more complex type of 'descriptions' of inductive definitions together with a decoding to a more 'first-order' representation of the container functor used in the $W$ definition. This approach is used in The Gentle Art of Levitation, which says it does not require extensional equality of functions (I believe).

This technique is also detailed in Ambrus Kaposi's thesis, which shows what sort of codes you need for inductive-recursive and inductive-inductive definitions.

The (I think) counter-intuitive bit about these systems is that they seem to actually be capable of describing themselves, and that this is not (it seems) contradictory.

So, it seems like we are relatively close to knowing how to to include most (commonly desired) definitions in type theory as a universe of descriptions with a 'decoding' function, instead of taking some universes to be open with respect to special definition forms. And this fact is somewhat independent of any features that homotopy type theory would have. I don't know of any system like Agda or Idris has this methodology on their roadmap, though.

I should say, there are potential traps, still. For instance, each universe `Set i` in Agda is called "Mahlo," because it admits inductive-recursive definitions. There are stronger universes known than Mahlo universes, too, which will in turn have (many) Mahlo universes within them. But the sort of 'universe' you define with induction-recursion *cannot* be Mahlo, because it is inconsistent for a Mahlo universe to have an induction principle. So any theory incorporating strong-than-Mahlo universes would at least need a different sort of 'description' system for those.
> 1 votes

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


# Question
Title: does there exist for each program that produces a sequence, a program that returns true or false if a number is in the sequence?
let S be the set of all programs that take a natural number as input and return another natural as output. let M be the set of all programs that take a natural number as input and return true or false. In both cases for a program to be in S or M it must halt.

Consider programs P in S, I will say the integer n is "in" P if there is some integer m such that P(m)=n

Consider a program P in M, I will say the integer n is "in" P if P(n)=true

Consider 2 programs P1 in S and P2 in M. I will say P1 and P2 are equivalent if for each integer n in P1, n is also in P2 and for each integer n in P2, n is also in P1.

I believe I have managed to prove the following:
There doesn't exist a program P such that P takes as input a program in S and returns an equivalent program in M.

However what I'd actually like to know is if for each program in S there is an equivalent program in M.

I figure this question can be answered in one of two ways. An explicit function in S could be given such that it has no equivalent function in M (this would require a proof that there is no equivalent function in M). Or it must be proven that for each program in S there is an equivalent program in M.

If there is another way to resolve this question other than one of the two ways I mentioned above I'd be interested to hear it. Also if you feel that simply proving there is no function P such that P takes inputs from S and returns equivalent programs in M is sufficient, please give an argument as to why this is.

I have chosen not to include the proof I mentioned above as its not strictly essential to the question however you think it would be relavent let me know and I can include it.

If any clarifications need to be made let me know.

Also please note that I might have gotten the tags wrong, I'm fairly new to the CS stack exchange, if I should change them let me know.

Thanks

# Answer
> 2 votes
Let us denote by $L\_S(P)$ the set of numbers in $P$ for $P \in S$, and similarly by $L\_M(P)$ the set of numbers in $P$ for $P \in M$.

Consider the following program $P \in S$. It interprets as input as a pair of integers $(x,y)$, runs the $x$'th Turing machine on the empty input for $y$ steps, returns $x$ if the machine halts, and returns some fixed $C$ if $x$ doesn't halt, where $C$ is the index of a halting Turing machine. Thus $L\_S(P)$ is the set of indices of Turing machines which halt on the empty input. It is well-known that this language cannot be computed by an $M$-program, that is, $L\_S(P) \neq L\_M(Q)$ for all $Q \in M$.

More generally, a non-empty language is of the form $L\_S(P)$ iff it is r.e., whereas a language is of the form $L\_M(Q)$ iff it is recursive.

---
Tags: computability, halting-problem
---


title: Symmetry of IP complexity class

text:
# Question
Title: Symmetry of IP complexity class
Wikipedia defines the IP complexity class as follows:

> A language $L$ belongs to IP if there exists $V,P$ such that for all $Q$, $w$, $$w\in L\Rightarrow Pr\[V\leftrightarrow P\text{ accepts }w\]\geq2/3$$ $$w\notin L\Rightarrow Pr\[V\leftrightarrow Q\text{ accepts }w\]\leq1/3$$

Note that this definition is asymmetric; it says (if we are polynomial-bound) we can be convinced $w\in L$, but says nothing about convincing us that $w\notin L$. We could define a class coIP containing the complements of languages in IP; that is

> A language $L$ belongs to coIP if there exists $V,P$ such that for all $Q$, $w$, $$w\notin L\Rightarrow Pr\[V\leftrightarrow P\text{ accepts }w\]\geq2/3$$ $$w\in L\Rightarrow Pr\[V\leftrightarrow Q\text{ accepts }w\]\leq1/3$$

It turns out IP=PSPACE and clearly PSPACE is symmetric under taking complement. Thus IP=coIP. Is there a direct way to see this? That is,

> Given a proof system $(V,P)$ for proving membership in $L$, can we use it to construct a proof system $(V',P')$ for proving membership in $\bar L$?

# Answer
> 2 votes
There is no relativizing technique to show that $\mathrm{IP}$ is closed under complement.

Clearly, $\mathrm{NP}\subseteq\mathrm{IP}$.

Fortnow and Sipser gave an **oracle** relative to which $\mathrm{co}$-$\mathrm{NP}$ does *not* have *interactive proof system*.

So, you have to study the **arithmetization technique** that settles down this conjecture (long ago).

Are there interactive protocols for CO-NP

---
Tags: interactive-proof-systems
---


# Question
Title: Can we get a better time hierarchy theorem?
The time hierarchy theorem states that

$DTIME(f(n)) \neq DTIME(f(n)\log(f(n)))$

(Let me acknowledge that this statement isn't 100 percent accurate because f must be "time constructible" and potentially other things that I'm missing)

If we were to take some function f, we can consider

$DTIME(f(n)) \subset DTIME(f(n)\sqrt{\log(f(n))})\subset DTIME(f(n)\log(f(n)))$

Where we know that at least one of these inclusions is strict. Do we know of examples where one of these inclusions isn't?

In general we might want to prove that $DTIME(f(n)) \neq DTIME(f(n)g(f(n)))$ for a function $g$ which is as small as possible. Do we have better upper bounds on $g$ (like $g(n) = \log\log n$)? do we have non-trivial lower bounds on $g$ in the form of some (time constructible) $f$ for which $DTIME(f(n) = DTIME(f(n)g(f(n)))$?

# Answer
> 1 votes
IMHO, there cannot be better, stricter *Time Hierarchy Theorem* **everywhere**.

To improve this theorem, you need faster **Universal Turing Machine**. The $log(n)$ overhead of the currently fastest simulation technique seems to be unavoidable, especially for large enough time bounds, since with more time resource the **simulated TM** can do *crazy* things that the **UTM** cannot assume some *regular property* to do the simulation faster.

With small time bounds, there may be some improvements. But, its consequences are negligible.

---
Tags: complexity-theory
---


# Question
Title: Complete problem for $\mathrm{QP}$ (quasipolynomial-time solvable languages)
**Question 1**: Is it known that $\mathrm{QP}=\cup\_{k}\mathrm{TIME}(2^{\mathrm{log}^k(n)})$ has any complete problem?

**Question 2**: Can this be used to simplify the **computational complexity theory** at all?

# Answer
> 3 votes
Question 1: **NO**

Question 2: **NO**

**Question 1**: Assume to the contrary that $\mathrm{QP}$ has a complete problem $\mathrm{L}\in\mathrm{QP}$.

Then, there exists $k$ such that $\mathrm{L}\in\mathrm{TIME}(2^{\mathrm{log}^k(n)})$. Consider an arbitrary problem $\mathrm{L}'\in\mathrm{QP}$, by completeness of $\mathrm{L}$, we have that $\mathrm{L}'\leq\_p\mathrm{L}$, i.e there exists a many-one polynomial-time reduction $f$ from $\mathrm{L}$ to $\mathrm{L}'$. So, given any instance $x\in\Sigma^\*$ with $|x|=n$, we first reduce $x$ to $f(x)$. Since $f$ is polynomial-time computable, we have that $|f(x)|=n^{O(1)}$. Now, we run the $2^{\mathrm{log}^k(n)}$ time-bounded TM deciding $\mathrm{L}$, and accept or refute accordingly.

We now estimate the time complexity of this TM for $\mathrm{L}'$. We have: $$2^{\mathrm{log}^k(n^{O(1)})}=2^{O(1).\mathrm{log}^k(n)}=2^{O(\mathrm{log}^k(n))}$$

So, the whole class $\mathrm{QP}$ collapse to $\mathrm{TIME}(2^{O(\mathrm{log}^k(n))})$ violating the Time Hierachy Theorem.

Thus, $\mathrm{QP}$ does not have any complete problem.

**Question 2**: The unconditional lack of complete problem of $\mathrm{QP}$ unconditionally separates it from $\mathrm{NP}$, $\mathrm{co}$-$\mathrm{NP}$, $\mathrm{PP}$, $\oplus P$, $\mathrm{US}$, $\mathrm{PSPACE}$. But that is **of no help** for computational complexity theory, since the interesting **nasty**, **stubborn** classes such as $\mathrm{ZPP}$, $\mathrm{RP}$, $\mathrm{co}$-$\mathrm{RP}$, $\mathrm{BPP}$, $\mathrm{MA}$, $\mathrm{AM}$ all remain elusive to whether any of them has a complete problem.

---
Tags: complexity-theory
---


# Question
Title: No. of subsets whose element multiply to give a square number
I have been given an array whose elements lie between \[1,70\] and the size of array \[1,10^5\].

I have to find the total number of subsets whose all elements multiply to give a perfect square number.

Since, count of subsets can be very large, I have to give the ans mod (10^9 + 7).

How should go on to solve this problem ?

One hint given to me is to utilise the range of value that every array element hold which is \[1,70\] and total no. of prime numbers between these \[1,70\] are 19.

# Answer
Factor each element $x\_i$ to produce a vector $v\_i$ of the powers of all primes which are at most 70. The product $\prod\_{i \in S} x\_i$ is a perfect square if every prime appears in an even power, that is, if $\sum\_{i \in S} v\_i = \mathbf0 \pmod{2}$. This suggests considering $v\_i$ as a vector over $\mathbb{Z}\_2$ (the integers mod 2). You are now given a matrix, and wish to know how many subsets of rows sum to the zero vector. This is a problem in linear algebra, and the answer depends on the rank of the matrix: if the matrix has $n$ rows, $m$ columns, and rank $r$, then the answer is $2^{n-r}$.

Here is a worked out example for $1,2,4,5,8$. In this case there are two relevant primes: $2,5$. The full matrix (before reducing modulo 2) is $$ \begin{bmatrix} 0 & 0 \\ 1 & 0 \\ 2 & 0 \\ 0 & 1 \\ 3 & 0 \end{bmatrix} $$ After reducing modulo 2, the matrix becomes $$ \begin{bmatrix} 0 & 0 \\ 1 & 0 \\ 0 & 0 \\ 0 & 1 \\ 1 & 0 \end{bmatrix} $$ This matrix has full rank (rank 2), and so the answer is $2^{5-2} = 8$.

Here are the 8 subsets: $$ \emptyset \\ \\{1\\} \\ \\{4\\} \\ \\{1,4\\} \\ \\{2,8\\} \\ \\{1,2,8\\} \\ \\{2,4,8\\} \\ \\{1,2,4,8\\} $$

As noted in the comments, you might want to disallow the empty set (which multiplies to 1). In this case, the formula becomes $2^{n-r}-1$.
> 3 votes

---
Tags: algorithms, dynamic-programming, combinatorics
---


# Question
Title: Original literature on adversary argument
I want to know about the early invention/use of the adversary argument (see the lecture note by Jeff Erickson) which is a technique for establishing lower bounds of problems.

I cannot find the original papers which invented/advocated adversary argument or the first problems whose lower bounds are obtained by adversary argument. (In particular, I am quite surprised that there are no wiki pages on adversary argument.)

Do you know some original literature on adversary argument?

# Answer
> 1 votes
The oldest literature can be traced back to Andrew Yao's min-max principle, which inturns has its elder root from von Neumann's.

History of game theory is not continuous in time. At least, there was some rise and then fall in the intensity of mathematicians' attention to this theory.

---
Tags: reference-request, lower-bounds
---


# Question
Title: Circuit satisfiability problem : SAT-C to SAT-2C
I have the following language : $L=\\{\langle C\_1,C\_2\rangle \text{ | } C\_1 \text{ and } C\_2 \text{ are two circuits that calculate different function}\\}$. We can call this language SAT-2C.

Prove that $L$ is NP-complete.

1) Proving that $L \in$ NP is pretty simple : given the values of $C\_1$, $C\_2$, it is possible to verify if the result is true or false. The time required to do so is probably linear to the size of the circuits.

I'm stuck at step (2) of my proof :(

2) Since we know that SAT-C is a NP-Complete, we can try the following reduction : **SAT-C $\le\_p$ SAT-2C**.

So if we have a circuit $\langle c \rangle \in \text{SAT-C}$, there must be a function $f$ that turns it into two circuits (if we want to prove that the reduction is possible)

$f(c) \rightarrow (c\_1,c\_2)$.

For example, if our circuit is $(a \land b)$ (logical AND).

The first circuit could be the same as c --- $c\_1 = c = (a \land b)$.

But what about the second circuit? How can $c\_2$ calculate a different function than $c\_1$ BUT at the same time, allow a reduction from the other way (SAT-2C to SAT-C)?

Any helps or suggestions would be greatly appreciated!

# Answer
As suggested by Yuval Filmus in the comment, you can try a circuit that always evaluates to False.
> 1 votes

# Answer
You can use a reduction from $\text{3-SAT}$.

$\text{3-SAT}$ is the language of $\text{CNF}$ formulas where each clause has at most three literals, and they are satisfiable, meaning - given a formula $\phi$ in the correct form, it is in $\text{3-SAT}$ iff there exists $x$ for which $\phi(x)=1$.

Now, you want to show that the language of two circuits that calculate two different functions is $\text{NPC}$, therefore, given a formula $\phi$ which is satisfiable, you want to create a reduction that transform this formula into two circuits, that calculate different functions.

First, transforming a $\text{3CNF}$ formula into a circuit can be done in polynomial time. So - you can construct one circuit. You now need to think of the other circuit. As Yuval Filmus mentioned, think of a circuit of constant size. What circuit will guarantee that if $\phi$ is satsfiable, than that circuit will calculate a different function than $\phi$, but if $\phi$ is not satisfiable, it will calculate the same function exactly?

Most of the answer is given, you are only left to think of that circuit. If you want, ask in the comments and I'll edit it in.
> 0 votes

---
Tags: complexity-theory, np-complete, reductions, satisfiability, circuits
---


# Question
Title: What is the consequence of $\oplus P\neq PP$?
From $P\subseteq \oplus P \subseteq PSPACE$ and $P\subseteq PP \subseteq PSPACE$ we infer $\oplus P\neq PP$ gives that $$P\neq PSPACE.$$

Are there any other consequences?

# Answer
Turns out, you are immediately able to separate $\mathrm{P}$ from $\mathrm{PP}$.

Assuming that $\oplus\mathrm{P\neq PP}$ but also assume to the contradiction that $\mathrm{P=PP}$, then $\mathrm{P^{PP}=P}$. But $\oplus\mathrm{P\subseteq P^{\\#P\[1\]}=P^{PP}=P}$. So, $\oplus\mathrm{P=P=PP}$ violating our assumption and concluding our proof by contradiction.
> 1 votes

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


# Question
Title: Why do we take null closure two times while converting from Epsilon-NFA to NFA?
I am studying Theory of Automata. I was studying conversion of Epsilon-NFA to NFA. I had to take null closures of states two times, before and after the specific input.

Could someone explain, what is the reason behind this?

# Answer
> 2 votes
You might need to do some $\varepsilon$-transitions before reading the first character of the input, and after reading the last character. It's probably easier to just consider them before and after every character, so every character is treated the same way, than to make a special case of the first or last character.

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


title: Dangling else problem

text:
# Question
Title: Dangling else problem
I was reading a book about compiler design, then in the CFG section, they introduced the dangling-else problem. They offered to match the the `else` with the last `if`. I still don't see how this solves the problem. Can somebody give me an explanation?

I searched before I put the question and none answered my question

# Answer
The problem is that the code is ambiguous. You can interpret it either as

```
If C1 then
   If C2 then
     S1
   else
     S2

```

or as

```
If C1 then
   If C2 then
     S1
else
   S2

```

The compiler needs to choose one way and covert it into machine language. The solution of "choose the last if" means the compiler will choose solution number 1 -- will attribute the "else" to the last (open, non-matched) "if" statement.
> 3 votes

# Answer
The language in question uses a grammar. The grammar is ambigous. However, the language can have rules that are not represented in the grammar (which means the actual language is not the language implied by the grammar but slightly different), and the compiler may implement other rules than just those represented by the grammar.

In this case, there is an additional rule: "If an else could match two if's according to the grammar, then it matches the last if". That solves the problem.

The alternative is to modify the grammar, as you saw. The alternative is the preferred solution in simple cases.
> 0 votes

# Answer
I think this can be a possible answer:

\[After left factoring and making it unambiguous\]

Let other = a

S -\> iEtT | a

T -\> S | aeS

I am generating all ***if's*** first and associating the ***else*** with the recent unassociated ***if*** . If I have to get an ***else***, I should be eliminating the possibility of getting a new ***if*** between the current unassociated ***if*** and corresponding ***else***.
However I am allowing the possibility of getting an ***if*** after generating the corresponding ***else***.

Point out if there are any errors.

Thank you.
> 0 votes

---
Tags: compilers, parsers
---


# Question
Title: Graph isomorphism and the automorphism group
A common approach to decide whether two given graphs are isomorphic is to compute the so-called canonical label (alternatively, canonical graph) of each graph and to check whether those match or not.

Tools such as Nauty compute the canonical graph via search trees that are pruned using some clever ideas that rely, among other, on graph automorphisms. Because of this, Nauty allows one to compute a generator of the graph automorphism group. However, as far as I understood the idea behind Nauty, the computation of the canonical graph does not require one to compute a generator of the graph automorphism group in general.

My question is therefore: is there a formal complexity-theoretical relation between GI and the computation of a generator set of the graph automorphism group?

Many thanks.

# Answer
As the comments suggest there can be confusion over what you call "GI". But the idea here is correct. It is polynomial-time equivalent to find generators of an automorphism group as it is to find an isomorphism between two groups. The idea is "classical" in that it appears in early work such as Luks' Group Isomorphism in bounded valence is in polynomial-time, and even there I think the idea was considered "well-known".

**Claim.** Let $G$ and $H$ be **connected** graphs. Then $G\cong H$ if, and only if, every generating set $S$ of $\mathrm{Aut}(G\sqcup H)$ contains an element $g\in S$ such that $G^g=H$.

*Remark* Important here is that every generating set exchange the graphs as otherwise you would sometimes compute generators that don't solve the problem. So for example, isomorphism of two groups does not so easily yield in this way. That is because not all generating sets of $\mathrm{Aut}(G\times H)$ will interchange $G$ and $H$ when $G\cong H$. instead they can go to diagonal copies. That situation can be fixed, but it requires a stronger argument. So the approach here is not one that applies in all categories.

Proof. For the converse if every (or even if one) generating set of $\mathrm{Aut}(G\sqcup H)$ interchanges $G$ and $H$ then $G\cong H$ by the restriction of that function to $G$. So this is all about the forward direction. (But I mention this because the proof is by contrapositive so it can look like I'm about to go the same direction.)

Suppose $\mathrm{Aut}(G\sqcup H)$ is generated by a set $S$ all of whose elements send $G$ to $G$, and $H$ to $H$, (note by connectivity assumption if one vertex of $G$ is sent to one vertex of $H$ then the entire graph $G$ is sent to $H$ and so by pigeon hole some vertex in $H$ will be sent to $G$ and so $|G|=|H|$ and we will have interchanged the two graphs). Since $S$ sends $G$ to $G$, then every composition of functions in $S$ sends $G$ to $G$, and so do inverses of these functions. So every word in $S$ sends $G$ to $G$ (and also $H$ to $H$). So no element of $\mathrm{Aut}(G\sqcup H)$ interchanges $G$ and $H$.

Finally if $G\cong H$ then an isomorphism $\phi:G\to H$ affords an automorphism $\phi\sqcup \phi^{-1}$ of $G\sqcup H$. So the absence of elements in $\mathrm{Aut}(G\sqcup H)$ to interchange $G$ and $H$ implies $G\not\cong H$. The result follows. $\Box$

But now the point to be clear on is that going from decision (Is $G\cong H$?) to search (Give me $\phi:G\to H$ or a certificate that $G\not\cong H$) has still to be argued (and can be). Also from one isomorphism to generators of automorphisms is another argument (individualize the graphs and repeat the isomorphism test). So all told you have a couple pages of argument to make these equivalences. None will show canonical labeling though. That is much harder (NP-hard if I recall). Even though NAutY and Traces handle many examples quickly.
> 3 votes

---
Tags: complexity-theory, graph-isomorphism
---


# Question
Title: What is the Big-O runtime of this algorithm?
Can anyone explain why the runtime of this is in O(N^3)?

Additionally, what would the run-time be in Big-OH if the *else* statement was removed.

```
    for(int i = 0; i < n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            sum = sum * sum;
        }
        for (int k = 0; k < i * i; ++k)
        {
            if (i % 2 == 0)
            {
                y = i + 1 * 3;
            }
            else
            {
                y = i * 3;
            }
        }
    }

```

# Answer
> 0 votes
A couple of things: Big Oh, or O(x) notation, is a notation that implies the upper bound in asymptotic notation, meaning more generically, what is typically considered the "guaranteed run time", meaning that the algorithm can never exceed this value.

So when it is written that the solution to this equation is O(n^3), let's examine why:

```
for(int i = 0; i < n; ++i)
    {

```

The above statement is looping through every item in n, meaning that the algorithm can never exceed n: giving us O(n).

Within that loop, meaning for every n:

```
 for (int j = 0; j < i; ++j)

```

We are ***also*** looping through i, so we are now effectively looping n twice.
If n is a simple array n = {1, 2, 3, 4} then array\[0\] = 1, array \[1\] = 2, etc.
So as we loop through n in the first for loop, array\[i\] = 1, then i increments, and then array\[i\] = 2, etc.
However, the second for loop is now looping through i, so for every time i does anything, the second for loop kicks off. If i is going to loop through n, and j will loop through i, then we can effectively say j is also going to loop through n. So that is another case of O(n), since we are guaranteed the second for loop will iterate no more than n times.

This is the exact same case with the third for loop

```
for (int k = 0; k < i * i; ++k)

```

For the reasons listed above, k is looping through i as well, and we know that i will iterate no more than n times, and that k will iterate no more than i times, so transitively, k will iterate no more than n times, giving us another O(n)

Just like basic arithmetic, O(n) * O(n) * O(n) = O(n^3)

Hopefully this helps.

# Answer
> 0 votes
It’s O(1) (constant time) because you set n = 10.

It’s also important to distinguish between runtime of code and time complexity of an algorithm. Assuming arbitrary values of n, sum and j can be calculated in constant time.

Sum is zero. If n \<= 1 then y = 0. Otherwise if n is odd then y = (n-1)\*3, If n is even then y = (n-1) + 1\*3..

---
Tags: asymptotics, runtime-analysis
---


title: Is UNIQUE-X3C a US-complete problem?

text:
# Question
Title: Is UNIQUE-X3C a US-complete problem?
The problem: Exact Cover by 3-Sets (X3C)

The definition: Given a set X, with |X| = 3q (so, the size of X is a multiple of 3), and a collection C of 3-element subsets of X. Can we find a subset C’ of C where every element of X occurs in exactly one member of C’? (So, C’ is an “exact cover” of X).

The class US (Unique Polynomial-Time) is the class of decision problems solvable by an NP machine such that the answer is 'yes' if and only if exactly one computation path accepts.

UNIQUE-3SAT is the problem of deciding whether the 3CNF Boolean formulas have a unique solution. UNIQUE-3SAT is a known US-complete problem.

Is the version of problem Exact Cover by 3-Sets(UNIQUE-X3C) when the instances have a unique solution a US-complete problem? (which means there is a unique subset C’ as solution)

Thanks in advance!!!

# Answer
> 1 votes
Yes, it is.

This scanned chapter 3 from Garey-Johnson classic book describe a parsimonious reduction from **3SAT** to **3DM**. And **X3C** is a generalization of **3DM**. So, the same reduction can be used to **parsimoniously reduce** **3SAT** to **3DM**.

Thus, $\mathrm{UNIQUE-3SAT}$ many-one reduces to $\mathrm{UNIQUE-X3C}$. As a consequence, $\mathrm{UNIQUE-X3C}$ is $\mathrm{US}$-complete.

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


# Question
Title: Why are there no complete problems for NP ∩ coNP?
The fact that PPAD is a subclass of TFNP seems to be taken as evidence that PPAD cannot be shown complete (or hard) for classes of independent interest like NP ∩ coNP. Slightly confusing, it even seems to excuse that it has not yet been shown complete for PPA, in which it is contained and which has complete problems.

A hint why this is expected is given at the end of Megiddo and Papadimitriou. A Note on Total Functions, Existence Theorems and Computational Complexity (1989):

> Finally can we hope to have TFNP complete problems? As with other classes (such as NP ∩ coNP, R, BPP etc.) whose machine based definition is *semantic* instead of syntactic (i.e., depends on a property that the machine exhibits when computing on any input), we do not expect such problems to exist.

I had a similar experience with R (or rather RP) that I started to settle for completeness of smaller classes, until I suddenly realized that the lower end (first the compressed word problem for monoids, then the compressed word problem for free groups) was actually P-complete, i.e. I had wrongly believed that those would be hard problems.

How valid are such excuses really for failing to show completeness (or hardness) of "believed to be difficult" problems with respect to complexity classes of independent interest?

# Answer
It is still open whether $\mathrm{NP\cap coNP=QP}$, where $\mathrm{QP=\cup\_k2^{log^k(n)}}$.

And in this answer, we have shown that $\mathrm{QP}$ has no complete problem.

If now someone shows that $\mathrm{NP\cap coNP}$ has some complete problem, that would imply $\mathrm{NP\cap coNP\neq QP}$.
> 3 votes

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


# Question
Title: How to evaluate the learned prototypes for multivariate time-series (e.g. motion)?
Consider a method which finds prototypes for **multivariate time-series** (MTS) data, and is designed to find prototypes for each class of data. For example, the {walking} class consists of some slightly different types of {walking} sub-classes, but they are not annotated. So i want to check if my prototypes can adequately represent the variations within each class and to measure the quality of the estimated prototypes.

In fact, I can calculate the distance of the prototype to the data points, but since it is possible to have more than one prototype per class/cluster, i cannot decide to which data point i should calculate this distance.

If the data is related to motion data, it is possible to watch the resulted prototypes to check how sensible they are. However, i'm not sure how to measure their quality in a numerical way?

# Answer
> 1 votes
You note " but with more than one prototype per class/cluster."

We often call this a *polymorphic* class. Consider the analogue in text..

C1 = { dpacekfjklwalkflwalkklpacedalyutekwalksfj} C2 = { jhjhleapashljumpokdjklleaphfleapfjjumpacgd}

Here the class 1 prototypes are polymorphic {walk OR pace}, and so is class 2 {leap or jump}.

You can learn these prototypes with a dictionary building method, and "measure their quality in a numerical way" with just classic accuracy (or precision recall etc).

Using nearest neighbor, the distance between and unknown item, say 'balk' is just defined as:

dist('balk', C1) = min(dist('balk','walk'),dist('balk','pace')) and dist('balk', C2) = min(dist('balk','leap'),dist('balk','jump'))

Paper \[a\] explains one nice dictionary building method, but there are other ways.

\[a\] http://www.cs.ucr.edu/~eamonn/SDM\_RealisticTSClassifcation\_cameraReady.pdf

---
Tags: modelling, evaluation-strategies, time-series-analysis
---


# Question
Title: Raft algorithm: What's the meaning of concept `index`?
When reading the description of Raft algorithm from Wikipedia, I noticed there is a special word `index`.

For web developer, index usually refers to `database index`.

* When it comes to Raft algorithm, what does `index` mean? Is it similar with database index? e.g. B+ tree.
* What is `raft index` used for?

Wikipedia: Raft

> Log Matching: if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.

https://en.wikipedia.org/wiki/Raft\_(computer\_science)#Safety\_rules\_in\_Raft

# Answer
TL;DR Just as said by Yuval Filmus, **a log index in Raft algorithm is just an integer that tells the position of a log entry in a series of log entries.**

---

Here is a figure that show clearly the meaning of an index of a log entry in Raft algorithm. The figure is taken from the award-winning paper In Search of an Understandable Consensus Algorithm by the creaters of Raft algorithm.

This usage of index is in accordance with the most common usage of index as in mathematics and computer programming, which is "**a value that identifies and is used to locate a particular element within a data array or table**" as said in its entry in dictionary.com. You can also check index notation.

Specifically, a log index in Raft algorithm is used by each server to identify the log entry that is numbered with that index in that server's log. All (indices for) committed log entries will always be consistent across all servers having those entries. Non-consistent (indices for) log entries across servers will be replicated or repaired, depending on the situations.

"For web developer, index usually refers to database index." It looks like that you come with a training in computer databases. As a web developer myself, I would not agree with you readily at all. Indices are used much more frequently to access array elements in everyday programming in just about every programming language. For example, in JavaScript, if there is an array `persons=["alice", "bob", "Diego"]`, then we can use index 1 to access its second element "bob", `persons[1]`. You will find the same or similar usage that are also abundant in Java, C, C++, C#, Python, Ruby, Go, etc.

If you want to understand Raft algorithm, one of the best introductory material is the video presented by Diego Ongaro.
> 5 votes

---
Tags: algorithms
---


# Question
Title: Why SAT Requires A Non-determinstic Algorithm?
I am getting started to understand the probelm of Satisfiability and i am reading (*Computers and Intractability: A Guide to the Theory of NP-Completeness*).

I do understand the difference between a Deterministic and Non-Deterministic Algorithm, however i don't understand why SAT requires a Non-Determinsitic Algorithm ? Why not a Deterministic Algorithm ?

How do we know for sure that a problem requires a Deterministic or Non-Deterministic Algorith that solves it ? (if it was solvable, i,e. not undecidable problem).

# Answer
It is not true that it *requires* a non-deterministic algorithm.

You are right; if it is solvable, it should be solvable by a deterministic algorithm. **And it is.** This deterministic algorithm needs exponential number of steps (with respect to number of propositional variables $n$) because only known general case approach so far is to test all combinations of truth values of propositional variables, and we have $2^n$ possible combinations (rows of a truth table).

However, we can (theoretically) solve it with a non-deterministic algorithm in polynomial time which is how a class of *NP* problems is defined. This is where your confusion, and maybe a bad choice of words in the literature, probably comes from.

---

All non-deterministic algorithms can be simulated by a deterministic algorithm. In fact, all that is computable can be computed with a deterministic algorithm. It is just the time complexity that varies.
> 3 votes

# Answer
Any decidable problem can be solved by a deterministic algorithm. The thing about SAT (and any other **NP**-complete problem) is that we don't know any *efficient* deterministic algorithm that solves it, and we think there might not even be one.
> 3 votes

---
Tags: satisfiability, decision-problem, nondeterminism
---


# Question
Title: Is Rectilinear Steiner Tree still NP-complete when points have integral coordinates?
Garey proved that the Rectilinear Steiner Tree problem is (strongly) NP-hard. I wonder if it is still true when we retrict the points to have **integral** coordinates and lie on a square of side lenght n^O(1) where n denotes the number of points.

# Answer
> 2 votes
Yes.

I suspect that you have not read the paper *The Rectilinear Steiner Tree Problem is NP-complete*, by M. R. Garey and D. S. Johnson, SIAM Journal on Applied Mathematics, Vol. 32 (1977), pp. 826-834. Well, if you have, I am sorry. Well, if you have, please indicate that critical information in your question. In fact, whenever your question is based on one big theorem/one paper, it is always a good idea to inform readers here whether you have no access to or have read or are familiar with a proof or proofs of the theorem/that paper. People, or at least I, will then be able to exchange ideas with you more efficiently in a way that suit you better.

I just browsed through the proof by Garey and Johnson. It is clear that, in fact, they build their proof on the rectilinear stree problem with integral coordinates within a square of side length $n^{O(1)}$, where $n$ denotes the number of points.

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


title: Bounded occurrence 3D matching problem

text:
# Question
Title: Bounded occurrence 3D matching problem
It is NP-hard to approximate maximum 3D matching problem even if each element occurs exactly in two triples. I'm interested in the following decision version of 3D matching.

Informally, Given a set of triples $F$ of elements such that each element occurs exactly in two triples, Is there a subset of $F$ such that each element occurs in exactly one triple?

> Is this decision problem solvable in polynomial time? Is it $NP$-complete?

# Answer
> 3 votes
It is solvable in polynomial time.

Convert an instance of Bounded Occurrence 3DM to a cubic graph.

For each triple, create a vertex

For each element, there are exactly two triple containing it. So, there are exactly two vertices corresponding to these two triples. Connect these two vertices by an edge.

Now, a solution to your problem is an **independent vertex cover**.

A graph has an independent vertex cover iff. it is **bipartite**. Checking for bipartiteness can be done in polynomial time.

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


# Question
Title: Is there any sort of formal definition of terms like 'data type', 'abstract data type', etc?
If not (because I assume not) is there some kind of reference or book that provides some theoretical foundation to these concepts? I've been learning about data structures and abstract data types for a while now but all these concepts seem very hazy and I would like some sort of rigorous grounding to stand on.

I hear type theory is used to found a lot of theoretical computer science (or all of it). So where could I read about type theory and how it is used to formalize CS?

# Answer
I good starting point is Benjamin Pierce's Types and programming languages (popularly referred to as "TAPL").
> 4 votes

---
Tags: data-structures, terminology, type-theory, abstract-data-types
---


# Question
Title: How do I solve a maze using velocity and acceleration?
I need to solve a maze. I can move an object around in a 2D maze by giving it 1 acceleration in any 8 of its 8 directions. The object starts at rest at 0 velocity. By only adding an acceleration at each step, I need it to be able to solve the maze and finish at the end position with a final velocity of 0. This maze is shaped with big open areas and not narrow corridors of tight corners. It should also take the least amount of steps possible to get to its destination.

This as you can imagine, would look different than simply finding the shortest path.

# Answer
> 1 votes
At any point, the state of the system is a pair $(p,v)$ where $p$ is the current position and $v$ is the current velocity vector. At any state, there are 8 possible actions (transitions out of that state, to another state). Search over this state space using any algorithm for searching state spaces to find the lowest-cost path from the start state to the desired end state; for example, you could use BFS, A\*, etc. This should solve the problem in a clean, straightforward, and efficient way.

---
Tags: shortest-path
---


# Question
Title: Why can’t a qbit be both entangled and in a pure state?
Not sure if I should ask this on CS or physics SE, but here goes.

I’m reading on quantum computing, and one thing that keeps confusing me is the following basic fact about QM:

Say we have a qbit A, and a qbit B, then two possible quantum states for $A$ are:

$$|+\rangle=\frac {|0\rangle + |1\rangle}{\sqrt 2}$$

$$\frac {|00\rangle + |11\rangle}{\sqrt 2}$$

In the first case, the qbit $A$ is in a quantum superposition between $0$ and $1$. In the second case, the qbits $A$ and $B$ are ALSO in a quantum superposition, but they are now entangled. I understand that there is a difference between these states, in the sense that the second is an entangled state, whereas the first one is not.

However, what I don’t understand, is why, solely from the perspective of $A$, there is a difference between these states. I read that in the second, entangled state, $A$ (taken as an individual qbit) is not in a superposition state, but in a mixed state. I know that this is a very important basic fact about QM but I still don’t really get it.

* why is it not possible for $A$ to be both in an entangled state, AND in a superposition “with itself” (i.e. a pure state, rather than a mixed state). I.e. by what principle of quantum mechanics do we know this, and from what does this principle follow?
* Is there an intuition behind this? I.e. how would quantum mechanics no longer make sense if it weren’t the case.

# Answer
First, let's look at the density matrix for A in the two cases. When A is in the pure state $|+\rangle$, we have \begin{align} \rho\_+ = |+\rangle\langle+| = \frac{1}{2}\left(|0\rangle + |1\rangle\right)\left(\langle0| + \langle1|\right) \end{align} As a matrix, we'd write this \begin{align} \rho\_{+} = \frac{1}{2} \begin{pmatrix} 1 & 1\\1& 1 \end{pmatrix}. \end{align} When A is entangled with B, we can obtain the (reduced) density matrix for A by tracing over all B states: \begin{align} \rho\_A &= \frac{1}{2}\text{Tr}\_B\left\[\left(|0\rangle\otimes|0\rangle + |1\rangle\otimes|1\rangle\right)\left(\langle0|\otimes\langle0| + \langle1|\otimes\langle1|\right)\right\]\\ &= \frac{1}{2}\left(|0\rangle\langle0| + |1\rangle\langle1|\right), \end{align} or, as a matrix, \begin{align} \rho\_{A} = \frac{1}{2} \begin{pmatrix} 1 & 0\\0& 1 \end{pmatrix}. \end{align} Ok, you say, the density matrices are different. Who cares? Well, we don't really care about states, because we can't measure states directly. But we can measure observables, and we can find the expectation value for those measurements using our states. Specifically, we can find the expectation value of $\mathcal{O}$ by taking $\langle\mathcal{O}\rangle = \text{Tr}\\,(\rho\mathcal{O})$. Let's look at the example of the $X$ operator. We have \begin{align} \langle X\rangle\_+ &= \frac{1}{2}\text{Tr}\\,(\rho\_+ X)\\ &= \frac{1}{2}\text{Tr}\\,\left\[ \begin{pmatrix}1&1\\1&1\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}\right\]\\ &=\frac{1}{2}\text{Tr}\\,\begin{pmatrix}1&1\\1&1\end{pmatrix} = 1. \end{align} In the state $\rho\_A$, however, we have \begin{align} \langle X\rangle\_A &= \frac{1}{2}\text{Tr}\\,(\rho\_A X)\\ &= \frac{1}{2}\text{Tr}\\,\left\[ \begin{pmatrix}1&0\\0&1\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}\right\]\\ &=\frac{1}{2}\text{Tr}\\,\begin{pmatrix}0&1\\1&0\end{pmatrix} = 0. \end{align} We obtain different experimental predictions for the outcome of measurements in these two states, and so we can distinguish between them.

**Edit:** I didn't really answer your question beyond showing how states in the example you gave lead to different predictions. I would say the more broad lesson to draw is that when system A is entangled with system B, *measurements on B can change the outcome of measurements on A*. This leads to an additional, classical uncertainty in our measurements that is not present when A is in a pure, unentangled state.
> 3 votes

# Answer
Let $A$ and $B$ be prepared and then put apart.

**First case:** $A$ is in $|+\rangle$ state and $B$ is in $|0\rangle$. Now let's apply Hadamard gate to $A$ (I'll omit normalization): $$H\_A(|00\rangle+|10\rangle) = |00\rangle$$ Then if we look at $A$ we'll observe it in $|0\rangle$, which is expected for such a superposition being hadamarded.

**Second case:** $A$ and $B$ are entangled. Again, we apply Hadamard gate to $A$ only: $$H\_A(|00\rangle+|11\rangle) = |00\rangle+|01\rangle+|10\rangle-|11\rangle$$ This means that if we look at $A$, we'll observe it either in $|0\rangle$ or $|1\rangle$ equiprobably.

The difference is caused by positive and negative amplitudes contributing to the same $|10\rangle$ outcome in the first case (giving zero probability), while in the second case they go into different $|10\rangle$ and $|11\rangle$.

Despite the fact that we didn't do anything to $B$ (not even measured it), there's detectable difference caused by the entanglement. That's what entanglement means: talking about individual qubits doesn't make sense anymore.
> 3 votes

---
Tags: quantum-computing
---


title: Page Replacement optimal verses MRU

text:
# Question
Title: Page Replacement optimal verses MRU
A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?

(A) Least-recently-used

(B) First-in-first-out

(C) Last-in-first-out

(D) Most-recently-used

=============================================================

First of all how many Page Faults are there in optimal PRA?

I'm getting as following -

100 PF in 1st access of 100 pages.

80 PF in 2nd access of 100 pages.

80 PF in 3rd access of 100 pages.

Totally = 100+80+80 = 260 PF are there out of total 300 references of 100 pages.

Is that correct? whereas some people are having like -

100+(100-19)+(100-19) PF and some are going for 4th round. why the need to go to 4th access of 100 pages?

# Answer
As far as number of sequences are concerned, it depends on how you read the problem statement.

> Now a program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE.

From this line, I perceive that program has accessed this sequence once and again repeats this sequence thrice. So, total four times.

But, I think here number of sequence is not that important. We just need to find page replacement pattern of the given policies in the options, which is similar to Optimal Page Replacement policy.

For the above sequence, which is

> 1 2 3 4 .... 99 100 1 2 3 4 .... 99 100 1 2 3 4 .... 99 100 1 2 3 4 .... 99 100

Both First-In-First-Out and Least-Recently-Used policies perform the same way and give same number of page faults. (Not always, but for this sequence)

For both of these policies, the number of page faults are 400. A program will make a replacement for every new page. For the first 20 pages from sequence, program replace the older pages 101 to 120. Then for every new page, a replacement is made in similar fashion.

21st page in place of 1st page

22nd page in place of 2nd page and so on.

After every 20 iteration, a frame will contain entire new set of pages.

Similarly, Last-In-First-Out performs the same way as Most-Recently-Used for this sequence and gives same number of page faults as Most-Recently-Used policy.

Here every time the last page is replaced by the new one.

So, 120th page is replaced by 1st page

1st page is replaced by 2 and so on.

So, here also 400 page faults occurs.

But, I don't think any of the given policy performs the same way as Optimal PR.

In Optimal PR, we'll have 100 + (100-19) + (100-19) + (100-20) = 342 page faults.
> 1 votes

---
Tags: operating-systems, paging
---


title: Can a distributed algorithm be serial?

text:
# Question
Title: Can a distributed algorithm be serial?
Can a distributed algorithm be serial? For example if I have 3 distinct agents in a network would an algorithm that looks like this be considered a distributed algorithm?

```
    Process ABC
       If (you are agentA) then
           Do stuff
       Else if (you are agent B) then
           Wait until agent A has finished doing stuff
           Do other stuff
       Else if (you are agentC) then
           Wait until agent B has finished doing stuff
           Do your own thing
       EndIf
    EndProcess

```

To my understanding it should be considered as distributed as long as the agents don't share memory. Wouldn't being serial defeat the purpose of having a distributed algorithm though?

# Answer
Distributed algorithms are sub-type of parallel algorithm. Different parts of algorithm executes simultaneously on different processors with minimum information sharing and minimum dependency among them. Although the difference between parallel algorithm and distributed algorithm is not very clear but in general parallel algorithm is used for speed-up and increase data handling capacity while distributed algorithm is mainly implemented for fault tolerance, scalability. But in your case, may be you are just storing data in different places (distributed) but the algorithm you are using is not a distributed algorithm.
> 0 votes

---
Tags: algorithms, distributed-systems
---