# Question
Title: Mapping several memories to one address space
I am trying to understand deeply how memories work in computers, and I faced the next difficulty.

Let's say we have a device with two memory chips but only one address space (for example, 0x00000000 to 0x10000000 will be memory1 and 0x10000000 to 0x20000000 will be memory2). In case an assembly code does a load/store instruction to memory2 to the address 0x10000004, who's responsible it is to change the address so it will be absolute to the memory chip? I assume that the memory chip doesn't know it's relative address space, and in our example memory2 expects a load/store from/to 0x00000004.

# Answer
> 0 votes
Each RAM chip (e.g., DIMM module) has its own range of physical addresses. The memory controller connects the CPU to the RAM chips via a memory bus.

In its simplest form, each read or write operation sent on the memory bus contains some bits that select which RAM chip it applies to, and some bits that indicate the address to be selected within that RAM chip. So, physical memory is partitioned among the RAM chips. The memory controller is responsible for managing this partition and determining, based on the physical address, which RAM chip to select (what to write on the chip select bits of the memory bus). The specific architectural details have evolved over time and may differ from platform to platform.

Physical addresses are normally not visible to user-level applications. Instead, a virtual memory subsystem (page tables) are used to translate from virtual addresses to physical addresses. The user-level application seems virtual addresses. There need not be any simple way that ranges of virtual memory addresses correspond to RAM chips.

---
Tags: memory-management, memory-hardware, memory-access
---


# Question
Title: Zero-knowledge proof of intractibility of NP-complete problems
I am not an expert in Zero-knowledge proofs and I am interested in its applicability to general mathematical proofs.

Suppose we're willing to assume that NP-complete problems are intractable and require exponential time algorithms.

Can we construct a zero-knowledge proof of the intractability of Hamiltonian cycle problem, under this assumption? Is it possible without assuming the existence of one-way functions?

# Answer
"A zero-knowledge proof of the intractability of the Hamiltonian cycle problem" doesn't make sense. You should refer to the formal definition of a zero-knowledge proof system. When we talk about a zero-knowledge proof system, it is a zero-knowledge proof system *for a family of statements*. For the problem to be interesting, the family needs to be infinite.

"The intractability of the Hamiltonian cycle problem" is not a family of statements; it is a single statement. It doesn't make sense to talk about a zero-knowledge proof in that sense -- you end up with something trivial and degenerate and uninteresting.

In particular, that single statement ("the Hamiltonian cycle problem is intractable") is either true, or it is false. If it's true, there is a trivial zero-knowledge proof system for it: the prover sends nothing, and the verifier outputs "yes, the statement is true". If it's false, there is also a trivial zero-knowledge proof system for it: the prover sends nothing, and the verifier outputs "no, the statement is false". Either way, there exists a zero-knowledge proof system that satisfies the definition. But this is not very interesting or meaningful.

From a formal mathematical perspective, in the phrase "zero-knowledge proof", you shouldn't think about "zero-knowledge" as a modifier to the word "proof". Rather, you should think about the phrase "zero-knowledge proof system" as an indivisible term with a specific mathematical definition. A "zero-knowledge proof system" is not even in the same category as a "proof"; they are like apples and oranges.
> 3 votes

# Answer
Ostrovsky and Wigderson showed that one-way functions are necessary for zero-knowledge proofs for languages beyond BPP. To the extent that your question makes sense at all, this should show that you do need one-way functions.
> 0 votes

---
Tags: complexity-theory, zero-knowledge-proofs
---


# Question
Title: How to find the original coordinates of a point inside an irregular rectangle?
I'm a third year computer science student. I'm working on a project `Data-show touch screen In schools classrooms`.

I'll try to explain my problem as much as I can.

The project has three main components; A computer, a Data-show and a webcam.

The teacher will plug the data-show in the computer and the computer screen will appear on the wall of the classroom to all students.

The main purpose of the project is to turn the image of the screen displayed on the classroom wall into interactive screen; when the teacher tabs with his finger on an image of a Button displayed on the wall, the webcam that is connected to the computer will capture the position of the teacher's finger and find his `(x,y)` coordinates for a reference point on the wall, and raise a click event in the related `(x,y)` position on the screen.

The screen of the computer has two dimensions; `Width->X` and `Height->Y`. And for every point in the screen such as `P`, it could be located on the screen using two numbers `(Px,Py)`, where `Px` is the distance between the point `P` and the left side of the screen, and `Py` is the distance between the point `P` and the top side of the screen. In other words, the reference for all points in the screen is the top left corner of the screen.

The data-show will display an irregular Quadrilateral shape of the screen on the wall. the shapes will not be regular squares or rectangles due to the angle that the teacher puts the data-show in. What I'm asking for are the equations that will calculate the `(x,y)` point on the screen that represents the `(x,y)` tapped point on the wall.

There is mainly four shapes the data-show may display on the wall. For each shape of them the only known things are the coordinates of the four angles(corners) of the quadrilateral shape.

# 1. an optimal rectangle

The displayed image on wall has a very low chance to shape an optimal rectangle, but it's the basic shape that could be formed.

Suppose that the red point `P'(Px',Py')` represents the coordinates of the place the teacher tapped on with his finger.

To get the original `(Px,Py)` coordinates from the point `(Px',Py')` on the wall, I can do the following.

1. Calculate the `width->X'` and the `height->Y'` of the displayed image by the law of distance between two points.

2. find the ratio between `X`&`X'`, and between `Y`&`Y'`. I'll call the first ratio `rx` and the second ratio `ry`.

3. Multiply `Px'` by `rx` to get `Px`, and multiply `Py'` by `ry` to get `Py`.

# 2. an optimal trapezoidal.

The displayed image on wall could also shape an optimal trapezoidal. I asked some of my friends from the applied mathematics college to help me to find the two equations to find the original coordinates of the point, and they did some calculations and came out with these two equations;

In this shape

To find `X`:

and to find `Y` I can use the same way used in the rectangle; finding the ratio between `Y` and the height of the trapezoidal `H`.

# 3. an irregular quadrilateral.

My question is about this shape, the data-show in most times will shape an irregular shape. Imagine this shape like

None of the shape's lines is vertical or horizontal, all lines may have different lengths and they may have different angels from each other.

# My question is

I'm searching for equations that will find the original `P(x,y)` point of the point `P'(X',Y')`. Things I know are the coordinates of the points `P1, P2, P3, P4, P'`

What are those equations? and how are they derived?

# Answer
This is what the concept of a homography was invented for. You know the coordinates of the four corners on your screen and on the wall, and you want to find a transformation that maps from screen coordinates to wall coordinates. There will be a homography that maps between the two coordinate systems. So, your task is: given four points with known mappings, find a homography that is consistent with that.

If you're using OpenCV, see the findHomography() method, as well as warpPerspective().
> 2 votes

# Answer
1. If we look at simple example with rectangle: finding of Y coordinate of point P $\equiv$ finding straight line $L$ parallel to $OX$ to which point $P$ belongs.
2. In case of trapezoidal it's still true except that we can not say "parallel" and we will use more generic definition: we will be looking for some straight line $L$ which satisfy next conditions. $$ P \in L \\ \frac{AI}{AB}=\frac{DJ}{DC}=\alpha, \text{for some }0 \leq \alpha \leq 1 $$
3. In common case such "parallel" lines (actually such lines are parallel, but in 3d space and I think it can be proved by considering quadrangular pyramid cut) is that what we want to find. And actual you need to find such $\alpha$ that $$ F \in AB, \frac{AF}{AB} = \alpha \\ E \in DC, \frac{DE}{DC} = \alpha \\ P \in FE $$
4. One way is to use binary search on $\alpha$. Also I want to explicitly mention that you can find $X$ and $Y$ independently.
5. $O(1)$ solution:

a. Coordinates of points $J$ and $F$ $$ \overline{OJ} = \overline{OD} + \alpha * \overline{DC}\\ \overline{OF} = \overline{OA} + \alpha * \overline{AB}\\ $$ b. By coordinates of $J$ and $F$ line equation can be composed: $$ Ax + By + C = 0$$ c. Suppose in previous equation $x=P\_x, y=P\_y$ and solve relatively to $\alpha$.
> 1 votes

---
Tags: computational-geometry
---


# Question
Title: What is the average degree of a complete graph and why?
Is it correct that the average degree of a complete graph $K\_n$, is $(n-1)/n$? or is it only $(n-1)$?

I have the answer of my professor which is $(n-1)$, but I didn't understand why.

# Answer
> 9 votes
In a complete (undirected) graph with $n$ vertices, every vertex is connected to all other $n-1$ vertices, so the degree of every vertex is $n-1$. In particular, the average degree is $n-1$.

---
Tags: graphs
---


# Question
Title: Can all NP-hard problems be reduced to one another?
I know that all NP-complete problems can be reduced to each other, but how about NP-hard problems? Can all NP-hard problems be reduced to one another?

# Answer
The answer to your question is no. Take for example the $SAT$ problem and Halting problem. Both are NP- Hard but second can't be reduced to first.
> 9 votes

# Answer
Can all NP-hard problems be reduced to one another?: **No**.

But can all NP-complete be reduced to NP-hard problems?: **Yes**

Remember: $L \text{ is NP-hard } \wedge L \in NP \rightarrow L \text{ is NP-complete}$

And NP-hard means, all problems in NP can be reduced to one NP-hard one, but not the other way around, since not all NP-hard problems are also in NP.

---

(Update):

So not all NP-hard problems can be reduced to another, because they aren't all in NP. One could say basically this:

$P \subseteq NP \subseteq \text{\\{decidable problems\\}} \subset \text{\\{decision problems\\}}$

The *halting problem* e.g. is not decidable. But complexity classes like NP are saying how much time it takes to decide/verify a problem. Obviously the *halting problems* takes infinite time aka forever, so $\notin NP$. But since it is defined for **all** programs i.e. input, it could solve all problems in NP like *SAT*, so **the *halting problem* is NP-hard**. So *SAT* is reduce able to the *halting problem*. But you can't reduce the *halting problem* to *SAT*, since *SAT* is decidable (and also NP-complete), while the *halting problem* is not.
> 3 votes

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


# Question
Title: What is the worst case time complexity for intersection tests with BVHs?
This question is in the context of computer graphics. We have a scene with $n$ triangles and a ray. We want to find if the ray intersects any triangle and get the closest one.

There is a datastructure called *Bounding Volume Hierachy* (BVH) which groups triangles and fits a bounding volume (e.g. AABBs - axis-aligned bounding boxes) around it. The idea is that if the ray does not intersect the bounding volume, it does not intersect any of the contained triangles / other bounding volumes.

Now assume a BVH with AABB bounding volumes and a scene of $n$ triangles is given. You can spend arbitrary much time for constructing the BVH, but you don't know which rays will come.

**What is the worst case time complexity for intersecting a ray with such a BVH? What would a worst case scene look like?**

edit: **What is the worst case time complexity if triangles may not cross each other?**

I thought of something like the following, where the bounding volumes intersect with themselves a lot (think of a recursive definition where the scene is continued to the center).

# Answer
Worst time complexity is $O(n)$: If all triangles are identical the bounding boxes are the same as well and every triangle needs to be intersected.

Btw.: The triangles do not need to be identical for the bounding boxes to be the same. The result is still $O(n)$ in that case.
> 2 votes

---
Tags: data-structures, time-complexity, graphics
---


# Question
Title: Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators?
Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only **binary operators**?

This question seems very trivial, but I don't know if the statement is necessarily true for all N \> 1 where N is the number of values. It seems intuitively true because any expression with more than one binary operator can be expressed as a combination of two different expressions through induction, but I'm not very confident.

# Answer
> 3 votes
RPN expressions have stack semantics: a **value** pushes a number onto the stack, whereas a binary **operator** pops two values and pushes one back, for a net loss of one element. At the start of an expression the stack is empty, and at the end there is exactly one value – the result.

Now let $V$ be the number of values in the expression, and $B$ be the number of binary operators. Then at the end of the expression, the stack contains $V-B$ values. Since there should be exactly one value remaining, we conclude that $V-B = 1$, or $B = V-1$.

---

Another way to see this is using structural induction. As you mention, every expression is either a value or is obtained from two expressions combined using a binary operator. Let's prove by induction on the number of values and operators appearing in the expression that $V = B+1$ (in the terminology of the preceding section).

When the expression consists of just a value, $B=0$ and $V=1$, so $V = B+1$. When the expression consists of a binary operator together with two other expressions $E\_1,E\_2$, we have $V = V(E\_1)+V(E\_2)$ and $B = B(E\_1)+B(E\_2)+1$ (I hope the notation is clear). By induction, $V(E\_1) = B(E\_1)+1$ and $V(E\_2) = B(E\_2)+1$, so $$ V = V(E\_1) + V(E\_2) = B(E\_1) + 1 + B(E\_2) + 1 = B + 1. $$

# Answer
> 1 votes
A simple inductive argument will work here. Expressions in RPN can be defined recursively by using the grammar:

```
E: operand
E: E E operator

```

Where `E` is an expression, `operand` is a number and `operator` is a binary operator.

The base case is when the expression is just a number. In this case the number of operators is clearly one less than the number of operands.

Let E be an expression of length `n > 1` and assume that the statement is true for expressions of length `< n` (`n` here is the number of operands). The expression is of the form `E1 E2 operator`. The first two expressions have smaller lengths and so we have:

```
o1 = n1 - 1.
o2 = n2 - 1.
o = o1 + o2 + 1 = n1 + n2 - 2 + 1 = n - 1 (we add 1 for the `operator` in `E1 E2 operator`).

```

`o` stands for number of operators. `n` stands for number of operands.

---
Tags: parsers, arithmetic
---


title: Minimize a sum with a weight constraint

text:
# Question
Title: Minimize a sum with a weight constraint
We are given `N` sets, each of which has a finite number of pairs $(x\_i,y\_i)$.

$M\_1=\\{(0,0), (x\_{1,1},y\_{1,1}), ...\\}$

...

$M\_N=\\{(0,0), (x\_{1,N},y\_{1,N}), ...\\}$

The problem is to select one and only one item from each set such that

$Min \\{\displaystyle\sum\_{j=1...N}(x\_{i,j})\\}$

s.t. $\displaystyle\sum\_{j=1..N}(y\_{i,j}) \> R$

where $R$ is a given constant.

Is there any classic problem similar to this? or what is known about this class of problems?

# Answer
The problem you have given is similar to KNAPSACK as Yuval Filmus mentioned.

KNAPSACK problem is defined as:

maximize $\sum\_{i=1}^n v\_i x\_i$
subject to $\sum\_{i=1}^n w\_i x\_i \leq W$ and $x\_i \in \\{0,1\\}. $

I assume the pair (0,0) is used so that you may not choose pairs for some of the $M\_j$'s. Otherwise (0,0) pair is irrelevant in the problem.

If this is so, then your problem can be easily shown to be NP-complete. We can reduce KNAPSACK to your problem by taking $N=n$ and have each $M\_j$ as a copy to the KNAPSACK instance (after negating $v\_i$'s and $w\_i$'s of course).

If pair (0,0) is not used in a way that I described above, then too you can circumvent the issue by adding $N$ pairs $(x\_{N+i,j},y\_{N+i,j})$, for $1\leq i \leq N$ in set $M\_j$ for $1 \leq j \leq N$, so that each $M\_j$ has now additional $N$ pairs (total of $2N+1$). Each $x\_{N+i,j} = y\_{N+i,j} = 0$ for all $i$'s and $j$'s.

If you say that each pair need to be distinct, then we can take $x\_{N+i,j} = y\_{N+i,j} = \epsilon\_{i}$ to make each pair distinct, where $\epsilon\_{i} \ll 1$ is an arbitrarily very small quantity. We also replace $R$ by $R+\Sigma\_i \epsilon\_i$.
> 5 votes

# Answer
As Shreesh mentioned, you can reduce 0-1 knapsack to this problem in this way: In each set, only keep the (0, 0) pair and the pair with the most y to x ratio. the (0, 0) corresponds to setting $x\_i$ in knapsack to be zero. Considering that each $y\_i$ corresponds to $ w\_i $ in knapsack, and considering each $x\_i$ in your problem as $v\_i$ in knapsack, by setting $ R $ as $ (\displaystyle\sum\_{j=1...N}y\_j\ )- W $, you can solve knapsack by solving this problem and giving the opposite answer as the answer to 0-1 knapsack.
> 2 votes

---
Tags: algorithms, optimization, dynamic-programming, knapsack-problems
---


# Question
Title: Reference introductory books or articles to Game Semantics
Where can I find *introductory* books, articles, notes or slides on Game Semantics?

I have searched a lot on the internet but I'm not satisfied by the material I found. It either is too informal, or it assumes too much knowledge of/attitude to other kind of semantics, and it's hard to follow for a beginner.

Ideally the material shouldn't have any prerequisites, except a little of game theory and few concepts of semantics.

Examples of the material that I've found are:

# Answer
I know three introductions that may satisfy your criteria. All of them will use some Category Theory, but the first one (by Jürjens) is actually quite light on that side -- he actually defines what categories and morphisms are in the context of game semantics, on page 111 (11th page of the article). You may want to read this one first, and then the others.
> 2 votes

---
Tags: reference-request, semantics, game-theory
---


# Question
Title: How do I go about constructing a game tree that does not duplicate any states?
Many games have states that can be reached via multiple paths in their gametree.

For concreteness, consider the game of tinychess (with the obvious(I hope) rules inherited from chess), which looks like this:

```
   /---V---V---\
   |   |<K>|   |
   D---+---+---C
   |   |   |   |
   D---+---+---C
   |   | K |   |
   \---A---A---/

```

When both your own and your opponent's King move left and right (or vice versa) the game has returned to the same state (there is no castling).

The state space of this game is rather small (even if we ignore symmetry) and amounts to only 9\*8 + 9 + 9 = 90 states. But a game may last an infinite number of turns given that the kings can keep moving back and forth.

How do I go about constructing a game tree that does not duplicate any states, for this game, and more generally?

# Answer
Instead of a tree you use a game graph. You maintain a set of nodes (your game states) and, if you need them, a set of edges you already explored. Each time you want to explore a new edge you check whether it leads to a node in your set of nodes. If it doesn't you just found a new node and have to add it to the set.

Your programming language of choice probably provides an efficient data structure for sets already. If it doesn't, you can use a Hash Map or a Search Tree.

However, for non-toy games (a strange concept, games that are not toys...) I don't think that this will buy you anything. The state space is huge and you can't store any significant part. A small cache of some $k$ states might still work though.
> 3 votes

---
Tags: trees, board-games
---


# Question
Title: Is Applicative-order and Normal-order evaluation model's definition contradictory as per sicp text book?
As per this explaination, it defines applicative and normal order evaluation in one form saying:

> This alternative "fully expand and then reduce" evaluation method is known as normal-order evaluation, in contrast to the "evaluate the arguments and then apply" method that the interpreter actually uses, which is called applicative-order evaluation.

while this explanation defines the other way around

> applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed

They seem to contradict each other. Do these definitions mean the same thing?

# Answer
> 8 votes
Those definitions are saying the same thing (at the level of precision of the English description).

## An example from the book

Normal-order evaluation goes “fully expand and then reduce”, meaning that function calls are expanded before reducing the arguments, and the reduction only happens when the value is needed. Let's take one of the examples in the book: start from `(sum-of-squares (+ 5 1) (* 5 2))`. First, we fully expand the definition of `sum-of-squares`:

```
(sum-of-squares (+ 5 1) (* 5 2)) → (+ (square (+ 5 1)) (square (* 5 2)))

```

Since `+` is a primitive, we can't expand it. It requires integers as arguments, so here we have no choice: we must reduce the arguments. To reduce `(square (+ 5 1))` in normal order, we start by expanding:

```
(square (+ 5 1)) → (* (+ 5 1) (+ 5 1))

```

Then we have the primitive `*`, also requiring integers as arguments, so we must reduce the arguments.

```
(+ 5 1) → 6
(+ 5 1) → 6

```

and so

```
(* (+ 5 1) (+ 5 1)) →→ (* 6 6) → 36

```

and likewise for `(square (* 5 2))`, so the original expression finally evaluates thus

```
(+ (square (+ 5 1)) (square (* 5 2))) →→ (+ 36 100) → 136

```

In contrast, applicative-order evaluates the arguments when the function is applied, before expanding the function call. So to evaluate `(sum-of-squares (+ 5 1) (* 5 2))`, we first need to evaluate the arguments:

```
(+ 5 1) → 6
(* 5 2) → 10

```

and then we can expand the function call:

```
(sum-of-squares (+ 5 1) (* 5 2)) →→ (sum-of-squares 6 10)
                                 → (+ (square 6 6) (square 10 10))

```

The next step is to evaluate the arguments of `+`; they're function calls, and in each case the arguments are already fully evaluated so we can perform the function call right away:

```
(square 6 6) → (* 6 6) → 36
(square 10 10) → (* 10 10) → 100

```

and finally

```
(+ (square 6 6) (square 10 10)) →→ (+ 36 100) → 136

```

## An example with side effects

The order of evaluation doesn't make any difference when the expressions have no side effect. (Except with respect to termination, if you don't consider non-termination a side effect: an expression may terminate in some evaluation orders and loop forever in others.) Side effects change the deal. Let's define a function with a

```
(define (tracing x)
  (write x)
  x)

```

If we evaluate `(square (tracing 2))` in applicative order then the argument is evaluated only once:

```
(tracing 2) → 2 [write 2]
(square (tracing 2)) → (square 2) [write 2]
                     → (* 2 2)
                     → 4

```

In normal order, the argument is evaluated twice, so the trace is shown twice.

```
(square (tracing 2)) → (* (tracing 2) (tracing 2))
(tracing 2) → 2 [write 2]
(tracing 2) → 2 [write 2]
(* (tracing 2) (tracing 2)) →→ (* 2 2) [write 2, write 2]

```

You can observe this in Scheme. Scheme applies applicative order to function evaluation, but also has a macro facility. Macro calls use normal order.

```
(define-syntax normal-order-square
  (syntax-rules () ((normal-order-square x) (* x x))))

```

At a Scheme prompt, you can see that `(square (tracing 2))` prints `2` once whereas `(normal-order-square (tracing 2))` prints `2` twice.

## Towards theory

Let's present the rules of evaluation in a more formal way (with small-step semantics). I'm going to use a notation that's closer to what is commonly used in theory:

* $(\lambda x y. A)$ is `(lambda (x y) A)`, where $A$ is an expression.
* $B\[x\leftarrow A\]$ means to take the expression $B$ and replace all occurrences of $x$ by $A$.
* $\[\\!\[ \ldots \]\\!\]$ is an integer obtained by some mathematical computation, e.g. $\[\\!\[ 2+2 \]\\!\] = 4$.
* $A \xrightarrow{\\;t\\;} B$ means that the expression $A$ evaluates to the expression $B$, and in doing so prints the trace $t$.

I'll simplify away everything that's related to variable binding: a variable is considered equivalent to its definition.

Evaluation rules come in two flavors. There are head rules, that explain how to make progress on the evaluation of an expression by looking at the topmost node in the syntax tree.

$$ \begin{align} ((\lambda x. B) \\: A) &\longrightarrow B\[x \leftarrow A\] && (\beta) \\ ((\lambda x\_1 x\_2. B) \\: A\_1 \\: A\_2) &\longrightarrow B\[x\_1 \leftarrow A\_1, x\_2 \leftarrow A\_2\] && (\beta\_2) \\ (\* \\: i \\: j) &\longrightarrow \[\\!\[ i \times j \]\\!\] && (\delta\_\*) \\ (\texttt{tracing} \\: x) &\xrightarrow{\\;x\\;} x && (\delta\_{\texttt{tracing}}) \\ \end{align} $$

$(\beta)$ is the rule the application of a user-defined function. I've defined a variant for two arguments (there are other, better ways to treat functions with multiple arguments but that's a topic for another day). The $(\delta)$ rules are for the evaluation of primitives (I'm treating `tracing` as a primitive because expressing it in terms of `progn` and `write` would unnecessarily complicate this presentation).

There are context rules, that explain how to look for things to evaluate deeper inside the evaluation syntax tree. The notation $\dfrac{P}{C}$ means “if there's a way to do the reduction $P$ according to the rules, then $C$ is also a valid reduction”. In other words, assuming that the premise above the line holds, the conclusion below the line holds.

$$ \dfrac{A \xrightarrow{t} A'}{(F \\, A \xrightarrow{t} F \\, A')} (\texttt{App}^1\_1) \qquad \dfrac{A\_1 \xrightarrow{t} A\_1'}{(F \\, A\_1 \\, A\_2 \xrightarrow{t} F \\, A\_1' \\, A\_2)} (\texttt{App}^2\_1) \qquad \dfrac{A\_2 \xrightarrow{t} A'\_2}{(F \\, A\_1 \\, A\_2 \xrightarrow{t} F \\, A\_1 \\, A\_2')} (\texttt{App}^2\_2) $$

For example the rule $(\texttt{App}^1\_1)$ means that to evaluate a function call, we can evaluate the argument. In a full treatment, there would be a similar rule for the function part, but we don't need it here.

The arrow $\longrightarrow$ means “evaluates in a single step to”. We can derive the notion of “evaluates to” (in any number of steps): $$ \dfrac{}{A \xrightarrow{} A} \qquad \dfrac{A \xrightarrow{\\;t\\;}^\* B \text{ and } B \xrightarrow{\\;t'\\;} C}{A \xrightarrow{\\;t,t'\\;}^\* C} $$ The first rule means that an expression evaluates to itself (in zero steps). The second rule allows adding one more step to a sequence of evaluations.

These rules are non-deterministic: there can be more than one applicable rule for a given expression, and thus there are multiple possibilities to evaluate an expression. This is where evaluation strategies come into play. An evaluation strategy defines a priority on the rules.

* In normal order, $(\beta)$ (the application rule) is applied before context rules that would affect the arguments. This is what the first quote means by “fully expand \[apply head rules\] and then reduce \[in context\]”, and what the second quote means by “delay the evaluation of procedure arguments until the actual argument values are needed” (don't apply context rules until forced by a $\delta$ rule). (In the first quote, the use of the word “expand” is somewhat jarring — applying $(\beta)$ is a reduction too!)
* In applicative order, the context rules are applied first, and $(\beta)$ is only applied if the arguments can't be evaluated anymore. This is what the first quote means by “evaluate the arguments \[in context\] and then apply \[head rules\]”, and what the second quote means by “all the arguments (…) are evaluated when the procedure is applied \[before performing the actual application\]”.

Let's look at `(square (tracing 2))` in this model. In the notation I've presented, that's $((\lambda x. (\* \\: x \\: x)) (\texttt{tracing} \\: 2))$. In normal order: $$ \begin{align} ((\lambda x. (\* \\: x \\: x)) \\: (\texttt{tracing} \\: 2)) &\longrightarrow (\* \\: (\texttt{tracing} \\: 2) \\: (\texttt{tracing} \\: 2)) && \text{by \\((\beta)\\)} \\ &\xrightarrow{\\;2\\;} (\* \\: 2 \\: (\texttt{tracing} \\: 2)) && \text{by \\((\delta\_{\texttt{tracing}})\\) and \\(\text{App}^2\_1\\)} \\ &\xrightarrow{\\;2\\;} (\* \\: 2 \\: 2) && \text{by \\((\delta\_{\texttt{tracing}})\\) and \\(\text{App}^2\_2\\)} \\ &\longrightarrow 4 && \text{by \\((\delta\_\*)\\)} \end{align} $$ In applicative order: $$ \begin{align} ((\lambda x. (\* \\: x \\: x))\\: (\texttt{tracing} \\: 2)) &\xrightarrow{\\;2\\;} ((\lambda x. (\* \\: x \\: x)) \\: 2) && \text{by \\((\delta\_{\texttt{tracing}})\\) and \\(\text{App}^1\_1\\)} \\ &\longrightarrow (\* \\: 2 \\: 2) && \text{by \\((\beta)\\)} \\ &\longrightarrow 4 && \text{by \\((\delta\_\*)\\)} \end{align} $$ (I used left-to-right evaluation for function arguments; specifying this is necessary to get a fully deterministic evaluation order.) This shows how $((\lambda x. (\* \\: x \\: x)) \\: (\texttt{tracing} \\: 2))$ evaluates to $4$ with the trace $2,2$ under normal order, but to $4$ with the trace $2$ under applicative order.

# Answer
> 1 votes
Notice that the first quote contains a definition of normal-order *evaluation*, but the second one treats normal-order *languages*, i.e. languages that *use* normal-order evaluation.

The nice answer by @Gilles explains in detail the difference between the applicative-order and normal-order evaluations, and shows that normal-order evaluation delays evaluation of arguments until they are needed.

I also want to note that normal-order evaluation is not the only way of delaying arguments' evaluation, as the book also mentions as lazy evaluation.

Deferring evaluation of the arguments doesn't necessarily mean one has to "fully expand", since one can use a kind of memoization to avoid repeating evaluations (in case of programming without side effects).

Let's repeat the example just above the definition for the normal-order evaluation. First the "fully expand" version:

```
(sum-of-squares (+ 5 1) (* 5 2))
(+    (square (+ 5 1))      (square (* 5 2))   )
(+    (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2)))

```

In this case the interpreter has to evaluate `(+ 5 1)` and `(* 5 2)` twice.

Instead we can remember the expressions `(+ 5 1)` and `(* 5 2)` as thunks e1 = `(lambda () (+ 5 1))` and e2 = `(lambda () (* 5 2))`. Please bear in mind that I'm relying on the built-in facilities (of our imaginary lazy interpreter) to save the results of `(e1)` and `(e2)`, after they evaluated the very *first time* to avoid recalculations. It's a nice exercise to actually realize that kind of behavior in plain Scheme.

```
(sum-of-squares (e1) (e2))
(+    (square (e1)    (square e2)  )
(+    (* (e1) (e1))   (* (e2) (e2)))

```

In this last expression the built-in memoization mechanism will evaluate (e1), remember its result (which is 6), so the second (e1) invocation won't redo the computation and will immediately return 6. The part with (e2) is handled in the same way. So the amount of operations is roughly the same as under applicative-order evaluation.

# Answer
> -1 votes
Yes, it seems to me they are in contradiction.

I think you're reading it correctly, and it's just one of those errors that make it into text books from time to time.

I searched, and found this errata page, but it seems to be more focused on code errata, and not on conceptual errors.

Hope this helps, -john

---
Tags: lambda-calculus, functional-programming, evaluation-strategies
---


# Question
Title: Reference needed: lower bound on sample size for determining which side of coin is biased with high probability
I am looking for a reference to see if the following problem has been addressed before. Suppose we know that a coin is biased with probability $p\>\frac{1}{2}$, but we are unsure if the coin is biased for heads or tails. I want to know a lower bound on a sample size $n$ needed to determine with high probability which side the bias is in favor of i.e. with probability at least $1-\delta$ so the answer would be $n=\Omega(g(p,\delta))$ or something like that.

Thanks for any help!

# Answer
Yes. You need approximately $\sim 1/|p - 1/2|^2$ observations (that many are necessary and sufficient), assuming $p$ is close to $1/2$. I've omitted constant factors, but the constant is small. The exact constant will depend on the degree of confidence you want, but it will vary as something like $\log (1/\delta)$ (or lower): $\delta$ drops exponentially fast in the number of observations.

For more details and analysis, see https://cstheory.stackexchange.com/q/22328/5038. You might also be interested in https://cstheory.stackexchange.com/a/30938/5038.
> 0 votes

---
Tags: complexity-theory, algorithm-analysis
---


# Question
Title: What are the key differences between Spiking Neural Network and Deep Learning
Deep Learning, now one of the most popular fields in Artificial Neural Network, has shown great promise in terms of its accuracies on data sets. How does it compare to Spiking Neural Network. Recently Qualcomm unveils its zeroth processor on SNN, so I was thinking if there are any difference if deep learning is used instead.

# Answer
> 11 votes
**Short answer:**

Strictly speaking, "Deep" and "Spiking" refer to two different aspects of a neural network: "Spiking" refers to the activation of individual neurons, while "Deep" refers to the overall network architecture. Thus in principle there is nothing contradictory about a spiking, deep neural network (in fact, the brain is arguably such a system).

However, in practice the current approaches to DL and SNN don't work well together. Specifically, Deep Learning as currently practiced typically relies on a differentiable activation function and thus doesn't handle discrete spike trains well.

**Further details:**

Real neurons communicate via discrete spikes of voltage. When building hardware, spiking has some advantages in power consumption, and you can route spikes like data packets (Address Event Representation or AER) to emulate the connectivity found in the brain. However, spiking is a noisy process; generally a single spike doesn't mean much, so it is common in software to abstract away the spiking details and model a single scalar spike rate. This simplifies a lot of things , especially if your goal is machine learning and not biological modeling.

The key idea of Deep Learning is to have multiple layers of neurons, with each layer learning increasingly-complex features based on the previous layer. For example, in a vision setting, the lowest level learns simple patterns like lines and edges, the next layer may learn compositions of the lines and edges (corners and curves), the next layer may learn simple shapes, and so on up the hierarchy. Upper levels then learn complex categories (people, cats, cars) or even specific instances (your boss, your cat, the batmobile). One advantage of this is that the lowest-level features are generic enough to apply to lots of situations while the upper levels can get very specific.

The canonical way to train spiking networks is some form of Spike Timing Dependent Plasticity (STDP), which locally reinforces connections based on correlated activity. The canonical way to train a Deep Neural Network is some form of gradient descent back-propagation, which adjusts all weights based on the global behavior of the network. Gradient descent has problems with non-differentiable activation functions (like discrete stochastic spikes).

If you don't care about learning, it should be easier to combine the approaches. One could presumably take a pre-trained deep network and implement just the feed-forward part (no further learning) as a spiking neural net (perhaps to put it on a chip). The resulting chip would not learn from new data but should implement whatever function the original network had been trained to do.

# Answer
> 5 votes
The largest application of SNNs that I know of is Spaun, whose neural networks were built using the Neural Engineering Framework and the Nengo neural simulator.

The distinction between SNNs and Deep Learning, especially in Spaun, is a gray area. Spaun uses modified Deep Learning techniques in it's vision system for digit recognition. Essentially, it uses a spiking version of a Constitutional Neural Network.

More recently, the same technique of converting Deep Learning approaches to spiking neurons for use in neuromorphic hardware (such as Spinnaker and Brainstorm for lower latency and greater power efficiency) have been applied to Convolutional Neural Networks.

The differences go a lot deeper than what I've mentioned here (like how SNNs can approximate dynamic systems and other non-linear functions without training), but unfortunately there's no easy way to summarize them. If you want more details, check out "How to Build a Brain" by Chris Eliasmith for a greater overview of how SNNs are being used to create Artificial Intelligence.

---
Tags: machine-learning, neural-networks
---


# Question
Title: Is it possible to use a space-filling curve to index a 2D grid which is not $2^x$ by $2^y$?
I am working on a project which needs to traverse a 2d spatial grid, and would like to use a space-filling curve indexing scheme. Unfortunately, I have no guarantee that the input grid will be a power of two along either dimension. In fact, it may be just barely over a power of two in some cases. Virtually extending the grid to be a power of two in size may use too much memory (it is a very large grid). Is it still possible to use a space-filling curve, such as a Morton curve, to index this grid?

# Answer
> 2 votes
What kind of indexing do you need? If it is just a lookup, your can interleave the bits of you coordinates to get a z-ordered Morton value. These could be stored in binary trie (critbit-tree) that uses prefix sharing. Traversing the tree gives you Morton-order, and the possible prefix sharing should reduce memory consumption. I implemented one in Java: critbit

If you also need geometric queries (kNN, window queries, range queries), you could try the PH-Tree, it's like a bit like quadtree, but uses prefix sharing like a trie and some other things to be much more efficient (memory and speed) than a quadtree. The tree uses internally a Morton ordering so a full traversal or Window queries will always return Morton-ordered results.

---
Tags: data-structures
---


# Question
Title: What are the major differences between row polymorphism and subtyping
I hear often that row-polymorphism is a better approach than subtyping, but I have difficulty finding anything comparing them in detail. I'm especially interested in the perspective of a user of the system.

I did come across this blog post, but it leaves me with more questions than before. For example, it makes a claim that a system with subtyping will assign one type, whereas a system with row typing will assign another; does that mean that if a system that purportedly has subtyping assigns the "row typing" type, that it purports incorrectly?

The one major difference I do see is that row typing makes it possible to align the types of arguments (that is, write a two argument function that concerns itself only with the `a` field of its arguments, but requires that its arguments have the same fields).

# Answer
> 12 votes
Subtyping says given an expression of one type we can give it also another type. We say the former is a subtype of the latter and this subtyping relationship induces many other relationships. In symbols, $$\frac{\Gamma\vdash E:S\qquad S\<:T}{\Gamma\vdash E : T}$$

The key thing here (and the reason I reviewed it) is that the *same* expression is given two different types. In parametrically polymorphic languages with *implicit* type instantiation we have the following subtyping relationship: $(\forall \alpha.\tau) \<: \tau\[T/\alpha\]$ for all types $T$. If type instantiation is explicit like in System F, this subtyping relationship doesn't hold.

As a bit of an aside, we could say a language with row types (usually) has subtyping relationships of the form $\\{\ell\_1:A,\ell\_2:B\\} \<: \\{\ell\_2:B,\ell\_1:A\\}$ giving rise to $\\{\ell\_1:A,\ell\_2:B\\} \cong \\{\ell\_2:B,\ell\_1:A\\}$ where $S \cong T \iff S \<: T \land T \<: S$. However, the way this is actually handled is by changing the notion of equality of types (i.e. unification) so that $\\{\ell\_1:A,\ell\_2:B\\} = \\{\ell\_2:B,\ell\_1:A\\}$, i.e. they unify. In this case, the subtype relationship is the trivial $T \<: T$ one.

Usually when we talk about a language with subtyping we mean one with a non-trivial subtyping relationship on *ground* types, i.e. types without free variables (which, of course, can and will generate subtyping relationships for non-ground types). So a system with row polymorphism like Roy's is not a language with subtyping in this sense, though it does have the non-trivial subtype relationship that comes from any implicitly instantiated parametric polymorphic language. Structural subtyping, on the other hand, explicitly states non-trivial subtyping relationships for ground types.

By **row types**, I'll mean having a non-trivial unification as described above or an equivalent. Without this, row types are little more than nested tuples. Note, row types are independent of parametric polymorphism; I do not mean to imply row variables. From the argument about $(\cong)$ above, structural subtyping implies row types but not vice versa. Parametric polymorphism is orthogonal (in the sense the you can have or not have it, there are definitely interactions) to row types or structural subtyping. A system with structural subtyping + parametric polymorphism subsumes row type + parametric polymorphism (assuming some kind of "record union") in the sense that every term in the latter can be typed with the same type in the former. The former is just able to type with additional types as well. Using Brian's example, in a system with structural subtyping and parametric polymorphism `answer` would have the same type as in the row typing version, but it would also have the subtyping version's type *as well*.

So you presumably want to compare row type + parametric polymorphism with structural subtyping without parametric polymorphism. The key benefit of the former (and sometimes drawback) is that it allows you to propagate information *globally*. When $\rho$ gets instantiated to `{ c : Number }`, everything that ever unified with it gets instantiated as well. This may percolate up to the root of your application. Carrying around row variables through large sections of code is not uncommon. Subtyping's approach is to *forget* information: going from a subtype to a supertype loses (type) information. This can often be what you want: there's a common type you care about and everything else is irrelevant details. My bias is toward maintaining as much type information as possible and only discarding it explicitly. The downsides of subtyping's approach is often evidenced by programs that are type correct but only because types were pushed to a(n informationless) "top" type, e.g. the empty record. Reiterating, parametric polymorphism (in general) preserves type information, subtyping intentionally loses it.

---
Tags: typing
---


# Question
Title: State machine that multiplies a binary number with a constant
I'm trying to create a FSM that multiplies a bitstream with a constant value (e.g 3).

I don't have a clue how to design such a FSM. Any hints?

# Answer
> 0 votes
Let $x\_1 x\_2 x\_3 \cdots x\_n$ denote the input string ($x\_i$ is the $i$th bit of the input). Let $y\_1 y\_2 y\_3 \cdots y\_n y\_{n+1} y\_{n+2}$ denote the desired output string ($y\_i$ is the $i$th bit of the output).

You want a finite-state transducer that, on input $x\_1 \cdots x\_n$, outputs $y\_1 \cdots y\_{n+2}$.

This is equivalent to asking for a deterministic finite-state machine (DFA) that accepts all strings of the form

$$x\_1 y\_1 x\_2 y\_2 x\_3 y\_3 \cdots x\_{n-1} y\_{n-1} x\_n y\_n E y\_{n+1} E y\_{n+2}$$

where $E$ is some special symbol that indicates "there's no more input" (end of the input).

There are lots of resources on how to design a deterministic finite-state automaton (DFA) that accepts a particular language. So, go use those resources to find a DFA that accepts that language. Once you've done that, you will be able to translate it back to a finite-state transducer as required.

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


title: NP-completeness proof via reduction

text:
# Question
Title: NP-completeness proof via reduction
I'm aware that 0-1 integer programming problem is NP-complete, where the problem is stated as: Given some integer matrix A and some integer vector b, determine whether there exists a vector x consisting of 0's and 1's such that Ax \>= b. I've seen that 3-CNF SAT is reducible to this problem.

However, here's a slight variant: Given some integer matrix A and some integer vector b, determine whether there exists a vector x consisting of 0's and 2's such that Ax \>= b.

The fact that vector x must consist of 0's and 2's kind of throws me off here. For the original problem, we just could reduce from 3-SAT by adding the inequalities 0 \<= xi \<= 1 for each boolean variable. But here, I can't just add the following inequalities:

0 \<= xi \<= 2

because x cannot equal 1.

Am I allowed to add an inequality, such as xi != 1? If not, what reduction can I use to show that the given problem is NP-complete? Thanks for any help.

# Answer
> 2 votes
Suppose you are given a 0-1-Integer-Programming instance. You need to substitute $x\_i$'s, $x\_i \in \\{0,1\\}$, with new variables $y\_i$'s as G. Bach mentioned. The substitution is $x\_i = y\_i/2$, $y\_i \in \\{0,2\\}$.

By this substitution, you get
0-1-Integer-Programming $\leq\_P$ 0-2-Integer-Programming
and also 0-2-Integer-Programming $\leq\_P$ 0-1-Integer-Programming by reverse substitution.
(This is because the polynomial reduction function in this case is invertible).

Therefore 0-2-Integer-Programming is also NP-complete
(from 0-1-Integer-Programming $\leq\_P$ 0-2-Integer-Programming).

By the way, you are not allowed to add $x\_i \neq 1$ in canonical integer programming problem. Basically it means $x\_i \leq 0$ OR $x\_i \geq 2$. We can't have OR constraints, all we can have is AND constraints.

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


title: CNF-SAT reduction problem variant

text:
# Question
Title: CNF-SAT reduction problem variant
I'm aware of the Cook-Levin theorem. I've also seen how to reduce SAT to 3-CNF SAT to show that the latter is also NP-Complete. The following problem is a variant, though, and I'm not sure how to proceed:

Define 1/3-CNFSAT as follows: given a set of boolean variables and clauses in Conjunctive Normal Form, (this isn't 3-CNF SAT, as each clause may contain an arbitrary number of variables), does there exist a set of assignments to each variable such that exactly one-third of the clauses are satisfied?

Prove via reduction that 1/3-CNFSAT is NP-complete.

My initial thought process: Reduce CNF-SAT to 1/3-CNFSAT (Given: since any SAT formula can be reduced to CNF form, CNF-SAT is NP-complete).

So I was thinking, given some formula in CNF form, which contains C number of clauses, I was thinking we could add to it an additional 2C clauses, all of which are unsatisfiable. Then CNF-SAT would be satisfiable IFF 1/3-CNFSAT would be satisfiable.

Please let me know if my thoughts thus far are incorrect.

My problem now is how to come up with an additional 2C clauses all of which are false, and express each of them in CNF form. Obviously, something like the following clause would be inherently false:

(x1 AND ~x1)

But if I were to express it in CNF form, I'd have to do something like the following:

(x1 OR x1) AND (~x1 OR ~x1)

Or, even more simply:

(x1) AND (~x1)

But the problem is, only one of the above clauses is false for some given boolean assignment to x1. So, how do I come up with 2C false clauses and express them all in CNF form?

I hope this question makes sense. Thanks for help.

# Answer
1/3-CNFSAT is very much similar to HALF-SAT, where instead of satisfying exactly half of the total number of clauses you are satisfying exactly one third of it. So the reduction from 3SAT is also quite similar. We reduce 3SAT instance, $\phi$, to a 1/3-CNFSAT instance as follows.

Let $z$ be a new variable not in $\phi$. Let there be $m$ clauses in $\phi$. We add $(z \lor \lnot z)$ and $2m+2$ copies of $(z)$ to $\phi$. In every exactly 1/3-satisfying assignment $z$ must be false.

Let $\phi \land (z \lor \lnot z) \land (z) \land (z) \land ... (2m+2) $ copies $...\land (z) = \phi'$. The following claim is easy to prove.

Claim: $\phi$ is satisfiable iff $\phi'$ has exactly 1/3rd satisfiable clauses.

Therfore 3SAT $\leq\_P$ 1/3-CNFSAT, and hence 1/3-CNFSAT is NP-complete.
> 1 votes

---
Tags: np-complete, reductions, satisfiability, constraint-satisfaction
---


# Question
Title: NP-complete reduction proof -- graph problem
While studying proofs of NP-completeness via reduction, I saw a seemingly challenging problem:

You are given some undirected graph $G = (V, E)$, along with a set $S$ which consists of 0 or more pairs of $G$'s edges.

As an example, a complete graph on 3 vertices would be described as follows: $G = (V, E)$ = ({$v\_1, v\_2, v\_3$}, {$v\_1v\_2, v\_2v\_3, v\_1v\_3$}). And you could be given a set $S$ which could consist of, say, two elements. E.g. $S$ = {$(v\_1v\_2, v\_2v\_3), (v\_1v\_2, v\_1v\_3)$}.

Now, we'll define $M$ as a subset of edges that has AT MOST one edge incident to each vertex in $G$, and AT MOST one edge from each pair in $S$. So for the example given above, $M$ could be any one of the following: {$v\_1v\_2$}, {$v\_1v\_3$}, or {$v\_2v\_3$}. $M$ cannot contain two (or more) edges for this example, though; if $M$ contained two edges, then there would be two edges that are incident to a single vertex in $G$, which is not allowed.

Here is the overarching problem statement: Given some graph $G$, some subset of edge-pairs $S$, and some integer $k \>= 1$, determine whether $G$ contains a subset of edges, $M$, such that $|M| \>= k$.

Your task: show that this problem is NP-complete.

I know I'm supposed to use reduction of a known NP-complete problem to show that the above problem is NP-complete, but I'm quite lost as to where to start, and even which known NP-complete problem to use for the reduction. Since it's a graph problem, I'm thinking perhaps something like vertex cover, independent set, clique, etc. might be used for reduction, but have no idea which or how. I also have a sneaking suspicion that some variant of 3-CNF SAT might be used here, but racking my brain hasn't helped thus far. Thank you for any assistance.

# Answer
We can reduce independent set ($IS$) problem to the overarching ($OVERARCHING$) problem as follows. We reduce the instance $\langle G, k \rangle$ of IS to an instance $\langle G',S,k\rangle$ of OVERARCHING by the following reduction.

Each vertex $v\_i \in V(G)$ becomes an edge $v^1\_iv^2\_i = e\_{v\_i} \in E(G')$. $G'$ will be a disconnected graph containing $|V(G)|$ edges and $2|V(G)|$ vertices. For every $v\_iv\_j \in E(G)$ we will add pair $(v^1\_iv^2\_i, v^1\_jv^2\_j) = (e\_{v\_i}, e\_{v\_j})$ in $S.$ If we select one of the vertices which are neighbor then we select one of the edge in the corresponding pair in the set $S$. Since all edges are disjoint in $G'$ we have absolute freedom there in selecting any edge we want.

Then $\langle G, k \rangle$ has a $k$-size independent set if and only if $\langle G',S,k\rangle$ has a $k$-size *"overarching"* set $M$.

Thus $IS \leq\_P OVERARCHING$, and hence $OVERARCHING$ is NP-complete.
> 4 votes

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


# Question
Title: Under what condition is P/poly equal to the class of languages having Turing machines running in polynomial length with polynomial advice?
Sanjeev Arora and Boaz Barak show the following :

> $P/poly = \cup\_{c,d} DTIME (n^c)/n^d$

where $DTIME(n^c)/n^d$ is a Turing machine which is given an advice of length $O(n^d)$ and runs in $O(n^c)$ time. I do follow the proof. But I feel the proof only holds if we assume that $\forall n$ the advice given to any two $n$ length strings $x$ and $y$ is same.

But I am unable to see if the theorem still holds if the above condition if not applicable ?

# Answer
> 2 votes
Since $P/Poly$ talks about circuit families for languages (different circuit $C\_n$ for length $n$ inputs), it is natural to talk about an advice which is a function of the input's length alone. Different advice for each string will make the class too big. For any $L\subseteq \Sigma^\*$, your advice for some $x\in\Sigma ^\*$ can be 1 if $x\in L$ and 0 otherwise.

---
Tags: complexity-theory, circuits
---


# Question
Title: Frigo's cache-oblivious algorithms paper
I am reading Frigo's "Cache-Oblivious Algorithms" paper and I need help understanding his cache complexity expressions for the base cases.

He starts on page 3 with "An $s \times s$ submatrix is stored on $\Theta (s + s^2/ \mathcal{B})$ cache lines. I can see the reason for $s^2/ \mathcal{B}$ is because we have $s^2$ numbers in total and we can fit $\mathcal{B}$ worlds per line. But where is the other $s$ coming from? Is this because we need to store $s$ pointers to each of the $s$ rows of the matrix?

**Matrix Multiplication**

Next, we have the matrix multiplication algorithm. First, I like to confirm when do we actually get a cache miss.

1. If the matrix is small, does that mean it is **already** in cache and we never miss?
2. If divide and conquer is needed, then is the matrix brought into cache **when it is small enough** so that is why we have cache misses at that point?

Here, in the base case (Case I), it says we need $\Theta ( (mn + np +mp)/\mathcal{B})$. I can see the reason here being we just have the total number of entries in each matrix, divided by how many can fit in one cache line.

But after that, I don't see how the other cases come about. For example, in Case II, if $n, p \in \[\alpha \sqrt{ \mathcal{M}}, \sqrt{ \mathcal{M}}\]$, then the $n \times p$ size matrix B can be brought into cache and it will occupy $np/\mathcal{B}$ cache lines, but what are the $n$, $m$, and 1 in the expression of equation (5) 's base case for?

In Case III, equation 6 shows the base case if $m \in \[\alpha \sqrt{ \mathcal{M}}, \sqrt{ \mathcal{M}}\]$ then the base case cache complexity is $\Theta (1 +m)$. Is this $m$ the $m$ cache lines for this matrix? What happened to the $n \times p$ matrix B? Is it already in cache. If so, didn't we also incur cache misses before loading it?

Then finally, isn't Case IV the same as Case I's base case? Why is there a 1 in the $\Theta$?.

**Matrix Transpose**

Next, the paper discusses matrix transpose. Here, in Case I, I can see $2mn/\mathcal{B}$ is the number of lines in cache needed to store a total of $m \times n$ entries in the matrix. But what is the 1 overhead for?

Then, for Case II, it says "The output array consists of nm elements in $m$ rows"...However, I thought the output matrix $B$ defined above has **$n$ rows**!? Where is the $m$ rows coming from?

Then a bit later in the paragraph, we get that since $n \geq \alpha \mathcal{B} /2$, the cache complexity is $O(1+m)$. Is this because

\begin{align\*} n \geq \alpha \mathcal{B}/2 \to m + nm/\mathcal{B} \geq m + \alpha /\mathcal{B} =O(1+m) ? \end{align\*}

Finally, in Case III, equation (8), when the matrix A is small, it is $m \times n$, so it will take $mn/\mathcal{B}$ cache lines...but again, why this $m$ and $n$ in $O(m +n + mn/\mathcal{B})$?

# Answer
The version of the paper I am reading does not contain that statement on page 3 that you quote, "An $s \times s$ submatrix is stored in $\Theta(s+s^2/B)$ cache lines." However, it does state that the authors are going to consider matrix multiplication **in the case the matrix is stored in row-major order**.

In that layout, matrix location $(i,j)$ is stored at memory location $m\*i + j$, where $m$ is the number of columns in the matrix. **If $m \geq B$ where $B$ is the cache line size, successive rows of an $s \times s$ submatrix will occupy distinct cache lines.**

As such, there are at least $s$ lines occupied. As you noted, there are at least $s^2/B$ cache lines occupied, since there are $s^2$ elements and only $B$ fit in a cache line. So, the value is $\Theta(\max(s, s^2/B))$ when $m \geq B$, and in Landau notation, maximum and sum are interchangeable.
> 1 votes

---
Tags: algorithms, algorithm-analysis, cpu-cache
---


title: When is bidirectional search unusable?

text:
# Question
Title: When is bidirectional search unusable?
Is there any situation that bidirectional search on a graph is not applicable? for example is there any classes of graph that we can only use ordinary Dijkstra's algorithm, and can not use its bidirectional variant.

The graph may be a dynamic graph.

# Answer
> 3 votes
Yes, a simple one is coming to my mind, a dynamic graph where the **search operators are not reversible**, i.e. both predecessors and successors of a node in the graph can not be calculated.

# Answer
> 2 votes
There are no such graphs.
If you have directed tree-like graph - it would make no sense to go from leaves, but... from the root it will work as intended, and from the leaves - it will stop there and wait to meet the previous.
It will be wasteful, but working. In given example, the same applies - it will produce output from one side, from the second it will stop on single vertex, so it will degrade to one-directional, therefore nothing makes bidirectional search unusable.
When you cannot perform search - it does not matter whether it was bidirectional or not, it will not wirk anyway.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: How different is the working of SNN (Spiking Neural Network) as compared to a real Neuron System in biological systems?
Assuming its one step closer to realism as compared to ANN, DNNs and other Neural Network models, what are the primary differences between a real neuron system and SNN?

# Answer
There are different types of spiking neural network models:

* **Hodgkin-Huxley**: models the processes within a neuron with electrical parts. This results in differential equations with 4 variables (capacity of the membrane, resistance of the ion channels, balance potentials, openings of the ion channels).
* **Leaky integrate and Fire** (LIF): Probably the simplest SNN; it is only an ordinary first order differential equation
* **Spike Response Model**: models refraction time. It tries only to model the phenomena. Although it is simple, it is still more accurate than LIF.

I don't have a biology background, but I would say the Hodgkin-Huxley model is probably the closest to real neurons. However, as far as I know (which is very little), there is no (effective, plausible) **training algorithm**. So this is probably *the* key difference to the brain. Also the topology will certainly be different.

And, of course, we can model much less spiking neurons than we have natural neurons in a human. So the **number of neurons** is a key difference, too. I've heard SNNs have a few dozend neurons, probably up to several hundred neurons. The biggest MLP (CNN) models I've seen so far have about 150 000 neurons (see Deep Residual Learning for Image Recognition). The human brain has about 86,000,000,000 neurons (see Wikipedia).
> 1 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks, bioinformatics
---


title: Queue implemented using stacks

text:
# Question
Title: Queue implemented using stacks
I have this problem I'm trying to solve: Implement a queue with a constant number of stacks so that each queue operation takes a constant (worst-case) number of stack operations.

**I don't want assistance with the answer**, but i do need help understanding the last part of requirements - *"so that each queue operation takes a constant (worst-case) number of stack operations"*.

Does this mean that, given such a queue with n elements and another with n+1 elements, the number of stack operations will be the same, when enqueueing or dequeueing either one? What does "worst-case" mean when dealing with a queue?

Also, with a question like this, is it implied that queues are the only data-structures needed and one would not need to introduce any additional data structures to reach a solution?

# Answer
> 2 votes
I believe the question is asking you to implement the queue so that every time you perform a queue operation (enqueue or dequeue) your implementation does O(1) total operations on the stacks used to implement this. For example, an implementation that performed at most 137 total pushes and pops per time that the client calls enqueue or dequeue would satisfy this requirement, but an implementation that requires, say, $n$ stack operations per enqueue would not meet this requirement.

---
Tags: data-structures, stacks, queues
---


# Question
Title: Is a computer without RAM, but with a disk, equivalent to one with RAM?
Memory is used for many things, as I understand. It serves as a disk-cache, and contains the programs' instructions, and their stack & heap. Here's a thought experiment. If one doesn't care about the speed or time it takes for a computer to do the crunching, what is the bare minimum amount of memory one can have, assuming one has a very large disk? Is it possible to do away with memory, and just have a disk?

Disk-caching is obviously not required. If we set up swap space on the disk, program stack and heap also don't require memory. Is there anything that does require memory to be present?

# Answer
Sure. In principle, given appropriate hardware, you could have just a disk, with everything stored on disk. Any time the CPU did a load or store instruction, there could be some hardware that turns that into a disk read or write. It'd be extremely slow: on a magnetic disk, each seek takes about 10ms, so you could do about 100 random-access reads and writes per second.

Some systems have flash memory-mapped into their address space. Flash memory provides non-volatile (persistent) storage. So, in some ways this resembles what you mention -- though those systems usually also have RAM as well.
> 25 votes

# Answer
In terms of computability, it is known that every modern day computer can be simulated by a Turing Machine whose only storage is a single, linear tape cells that can be written. Assuming you can keep adding unlimited amounts of disk storage, a computer having only hard drives is just as powerful. So certainly you could make a computer without memory.

Of course, there are not "unlimited space" hard drives, but neither is there unlimited RAM.

There are a number of practical issues, for example, you would need conventions for mapping different areas and addresses on the disk, an operating system which wrote to the disk for intermediate storage and managed disk addresses. In reality, you would end up closely simulating RAM on your hard drive.
> 16 votes

# Answer
The question is not purely academic. It is a matter of historical record that one of the earliest commercially-produced computers \[sorry, I don't recall which offhand\] did not have any RAM - all programs were executed by fetching instructions directly off of a magnetic drum \[a rotating cylinder with outer surface magnetizable (disks came later)\]. It was comparatively slow, but much cheaper than a lot of the competition. \[this was way back in the 'tube' days\]

Interestingly, it came with a now-obsolete tool known as an 'optimizing assembler' - i.e the assembler not only generated machine instructions, it wrote them out onto the drum non-consecutively so as to minimize, for each instruction, the amount of time waiting for the drum to rotate to the next.
> 14 votes

# Answer
No. Disk drives are not Random Addressable like RAM. Instead they're block storage devices. You can't read or write a byte from them. And your CPU cannot read a whole sector at once, they need that random access. Operating systems hide this level of detail from you, but they do so by reading a whole sctor into RAM, modifying it, and writing it back.

As a result, you need one block of random-access storage. This *could* be the CPU cache, though, which is made out of SRAM (a fast type of RAM).

It's not only disks. Flash memory is by design built out of blocks, which is key to its low price. It even has blocks far bigger than normal disk sectors, but it uses RAM internally to hide that from the OS.

You can make persistent storage that's directly usable by a CPU. EEPROM storage would fall in this category (Electronically Erasable Programmable "Read-Only" Memory - although "Read-Optimized" would be a factually better description).
> 7 votes

# Answer
It is conceptually possible. RAM is just a caching level. There are many caching levels in a modern computer (see the CPU's L1,L2,L3.. caches, of course Ram, the swap area -which is a logical section of the disk used as RAM...-), if you put or add one, the machine will work. For example, an Ubuntu live cd may not use the caching level of the HDD. However, i don't think there are any OS that can support the absence of a RAM level.
> 1 votes

# Answer
When you use virtual memory and need to handle page faults, then at the very least the exception handler handling the page fault, the disk driver that reads the data from the hard drive and first writes dirty pages to the disk, and the page tables need to be in RAM all the time. Because if they are not in RAM, you can't swap them back into RAM. Plus you need space for at least one page of RAM.

If you had a CPU like a massive 12 core Xeon with 30 MB of cache memory, it might be possible to have a system with neither RAM nor hard drive, but use just the cache memory. (Not sure if that actually works or if for some reason RAM is required).
> 1 votes

# Answer
Technically, RAM is a primary volatile memory that is used to improve the processing speed. Once the power is gone, the data in primary memory is lost. If we use a disk, ie as you say, only disk and not RAM, we could still run our computer but there would be more read write overhead thereby considerably slowing down the system . Hence, we use RAM.
> -1 votes

---
Tags: computability, memory-management, memory-hardware
---


# Question
Title: Would a polynomial-time algorithm for an NP-hard problem implies that P=NP?
An NP-hard problem is not in NP. (If it was in NP, it would be an NP-complete problem not NP-hard.)

So my question is: if someone can find a polynomial-time algorithm for an NP-hard problem, would that means that P=NP?

I think yes (I am almost sure) but I can't find the reason why?

# Answer
Your conclusion is correct: Since an NP-complete problem exists that can be reduced to your NP-hard problem, if you should be able to solve your NP-hard problem in polynomial time the NP-complete problem would be in P, hence P=NP.
> 1 votes

---
Tags: np-complete, np-hard, np
---


title: What is the file system of ram?

text:
# Question
Title: What is the file system of ram?
As much I know about a memory and storing data there would always be a managing type feature in every memory which manages all the data and its location. So, what is the **file system of a RAM**. I also like to know the format or type (mp3, pdf, png, txt, jpg or binary) of data stored in.

# Answer
Think of the file system and its files as a big cabinet with lots of physical folders in an office of bureaucrats. The sheets in the folders are arranged in fixed ways such that every bureaucrat knows exactly where to expect which information before taking the folder out of the cabinet.

Not let us assume that a bureaucrat (a program) performs a certain operation on a folder/file. It will take the folder to the desk, spread the sheets on the desk, cut certain things out, glue them together, paint marking son certain sheets, translates the text of a sheet to a new one, discards sheets entirely, add sheets, and do all kinds of crazy stuff on the data on the desk in the way that the bureaucrat wants it to do. After all that, the bureaucrat puts the relevant sheets nicely back into the folder such that everything is orderly, puts the folder back into the cabinet and then throw everything that is left on the desk back into the trash bin.

Note that the bureaucrat's desk is the RAM in this analogy. Now how are things stored on the desk? Well, that depends on what precise step the bureaucrat performs at a time instant. Even more, different bureaucrats doing essentially the same task may do things in a different order. So we can't really say *anything* about the organization of a bureaucrat's/program's desk/RAM other than whatever is put back into the cabinet/file system is put there orderly. In between, it is up to the bureaucrat how things are stored and in which encoding.

For most data in the RAM, the question how it is **encoded** does however make sense. However, this encoding can change frequently. For example, when a web browser receives text from a server, it may change the encoding multiple times before the data is actually displayed.

---

I hope that this analogy helps clearing things up. It has its limits, though, as in a computer, folders are not taken out of the cabinet, but they are rather copied and later overwritten, as this is cheaper in a computer than it is in real life. Also, because the memory sizes of the processes in a computer are not fixed, there is memory management going on, and one *can* say something about where memory allocation information is stored and how that information is encoded.
> 3 votes

# Answer
The equivalent to a file system for RAM would be the MMU (memory management unit)

Back in the day many systems didn't have one and poorly written programs would crash each other or the OS by violating each others address space. As technology progressed some processors offered additional MMU chips and eventually they were integrated into the processors that we have today. The MMU with the OS work to give programs an address block to load and run in. They keep track of the address blocks programs use via paging tables. They also handle fragmentation of memory blocks that have been freed.

As for how data is handled inside a programs memory space, that is left up to the programmer, though high level languages have developed best practices on how to handle memory.
> 1 votes

---
Tags: memory-management, filesystems
---


# Question
Title: Finding the $k$-smallest elements in a min-heap
Given a min-heap $H$, I am interested in finding the $k$ smallest elements efficiently. The simplest solution would be to call delete-min $k$ times which would give us the solution in $O(k \log n)$ time. This can be improved to $O(k \log k)$ time by maintaining a separate heap $H'$ as follows. Start by inserting the root of $H$ in $H'$. Then when performing a delete-min operation, you add both children of that node in $H'$, and repeat until you have all $k$ elements. Is there a way to do better? I have a feeling that $O(k)$ should be possible, but I can't come up with an algorithm - though certainly you cannot hope to do better than $\Omega(k)$.

Edit: I would just like a hint please.

# Answer
If you mean the usual binary heap represented in an array, this is answered in "An Optimal Algorithm for Selection in a Min-Heap", by Frederickson. It is pretty complex.

Other priority queues have easier algorithms. For instance, if you use a threaded AVL tree as priority queue, you can just follow right neighbor pointers from the minimum value.
> 4 votes

---
Tags: algorithms, data-structures, heaps
---


title: Advice for statistics/ML problem

text:
# Question
Title: Advice for statistics/ML problem
I've been studying a particular problem recently, and it seems like there might be techniques from statistics or ML that could be applied. Any advice or comments would be appreciated.

We're given some set of values sampled from a particular distribution. The values themselves are hidden to us, but their frequencies are known. We don't know the *exact* distribution the hidden values are drawn from, but using other information we've developed a model/approximation of it that probably has some errors, both in terms of missing elements and the frequency of a particular element. Our eventual goal is to map elements of our approximate distribution to their hidden counterparts in our target distribution.

For some small number of hidden values, we're also given the actual member of the distribution this value corresponds to. In a sense, a few of the hidden things are 'revealed' to us, but most of them remain hidden.

Is there any way for us to take the information we get from the revelation of the small number of values from our 'real' distribution and use it to refine our approximation of the entire target distribution, and not just the values that were revealed?

Obviously we know with certainty which elements of our approximate distribution correspond to the hidden values that were revealed, but can we use the fact that we also know 'how far off' our approximation was for *those* values to make our approximation more accurate for *other* values?

# Answer
> 1 votes
I would suggest using bipartite matching. Have one vertex on the left side for each hidden value you observed. Have one vertex on the right side for each value in your approximate distribution (your model for the underlying distribution). Draw an edge between each pair of vertices $(u,v)$, with a weight based on how similar their counts (frequencies) are. Look for a matching of maximal weight.

This will work if you have no other information about the hidden values, other than their frequencies. If you also have some information about their order or other side information, I don't know how to use bipartite matching for that.

---
Tags: machine-learning, statistics
---


# Question
Title: A greedy approximation algorithm for max k-cut
The max k-cut problem is: Given an undirected graph G= (V;E) with nonnegative edge costs, and an integer k, find a partition of V into sets $S\_1,\cdots,S\_k$ so that the total cost of edges running between these sets is maximized. The aim is to find a greedy algorithm for this problem that achieves a factor of $(1-\frac{1}{k})$.

My algorithm is: at the beginning, all the vertices of V is seperated in to $S\_1,S\_2,\cdots,S\_n$. Once we have $S\_1,\cdots,S\_{t+1}$, we find $S\_p,S\_q$ s.t. $c(S\_p,S\_q)=min\_{\\{i,j\\}}c(S\_i,S\_j)$ and merge $S\_p,S\_q$ together to get $t$ parts until $t=k$.
Let $ALG\_t$ be the solution given by this algorithm for $t$ parts. $OPT\_t$ is the optimum value for $t$ parts.
By induction, $ALG\_n=OPT\_n\ge(1-\frac{1}{n})OPT\_n$.
Since there are $\binom{t+1}{2}$ sets of edges between $S\_1,\cdots,S\_{t+1}$, at least one of these sets with cost $\le\frac{1}{\binom{t+1}{2}}ALG\_{t+1}$.
By the construction of the algorithm, we merge these two sets of vertices together, then we have $ALG\_t\ge ALG\_{t+1}-\frac{1}{\binom{t+1}{2}}ALG\_{t+1}=(1-\frac{1}{\binom{t+1}{2}})ALG\_{t+1}\ge(1-\frac{1}{\binom{t+1}{2}})(1-\frac{1}{t+1})OPT\_{t+1}\ge(1-\frac{1}{\binom{t+1}{2}})(1-\frac{1}{t+1})OPT\_{t}$
But it's not true that $(1-\frac{1}{\binom{t+1}{2}})(1-\frac{1}{t+1})\ge(1-\frac{1}{t})$.
Therefore I wonder if there is some other arguments or algorithm?

# Answer
The natural greedy approach goes roughly like this:

> Go over the vertices one by one. For each one, allocate it to a part in a way maximizing the total cost of edges cut.

There are at least two natural ways of defining *total cost of edges cut*:

1. Total cost of edges between the vertex and vertices already allocated to different partitions.
2. Same as 1, together with the expected cost of cut edges to vertices not already allocated.

In this case both ways are the same, but the second shows the connection between the greedy algorithm and the trivial randomized algorithm, which allocates the vertices completely randomly.
> 2 votes

---
Tags: algorithms, approximation, greedy-algorithms
---


# Question
Title: Prove that the depth function of a Binary Search Tree is $O(\log n)$ on average
I am struggling with this question because I am not sure how to see that a depth function is $\mathcal{O}(\log n)$ on average when it clearly traverses through the whole tree which should make it $\mathcal{O}(n)$:

```
depth(tree):
    if tree is a leaf:
        return 0
    else:
        return 1 + max(depth(tree.left_subtree), depth(tree.right_subtree))

```

It goes through each and every node. Could someone explain to me how finding the depth of a BST can be done is $\mathcal{O}(\log n)$ on average?

# Answer
If your input binary search tree is like the one given below then no matter what the program does, the depth function will return $n-1$ (because the depth ***is*** $n-1$, in this case). And it will take $n$ operations if the program does not know the depth beforehand or by some trickery, or the depth is not stored, say, in nodes.

You are confusing three things in your question:
(1) depth function returns $d$, the depth of the tree, which is fixed for a given tree.
(2) depth function the way it is defined will always run in $O(n)$ time for any tree, skewed or balanced.
(3) the average depth $E(d)$ of a random binary search tree (which is got by randomly inserting $n$ uniform random values) is $O(\log n)$.
> 4 votes

---
Tags: time-complexity, binary-trees, binary-search
---


# Question
Title: Why is not possible to defragment ubuntu's disk?
Someone can explain me why we can't defragment ubuntu's disk? Or generally linux machines

# Answer
> 4 votes
*"why we can't defragment ubuntu's disk?"*

Who said you couldn't?

https://askubuntu.com/questions/221079/how-to-defrag-an-ext4-filesystem

---
Tags: data-structures
---


# Question
Title: How is $a^nb^nc^{2n}$ not a context free language, where as $a^nb^mc^{n+m}$ is?
$L\_1 = \\{a^mb^nc^{m+n}: n,m\>1\\}$

I know $L\_1$ is CFL and works with a pushdown automata.

$L\_2 = \\{a^nb^nc^{2n}: n\>1\\}$

The language $L\_2$ should also be a CFL because it looks similar, but in my book $L\_2$ is not a context-free language. I just can't figure out how.

Why is the language $L\_2$ not context-free and what is it then? How can it be represented?

# Answer
Have a look at the proof at the link: Is $a^n b^n c^n$ context-free?. Though the language $L\_2$ is little bit different, the proof is (almost) same. There is a proof of this language in wikipedia too.

$L\_1$ is a context-free language.

$L\_2$ language is a context-sensitive-language. It is also in P, Recursive, RE, PSPACE, NP, and all the superclasses of CSL. Every language belongs to the class of all languages $\mathscr{P}({\Sigma^\*})$.

The context sensitive grammar for the language $L\_2$ similar to as given in the wiki is as following:

$S \rightarrow a b C$
$S \rightarrow a S B C$
$C B \rightarrow W B$
$W B \rightarrow W X$
$W X \rightarrow B X$
$B X \rightarrow B C$
$b B \rightarrow b b$
$C \rightarrow cc$

$L\_2$ has also tree-adjoining grammar whose language class is a proper subset of context sensitive languages. Since $L\_2$ has a context-sensitive grammar, it is accepted by some linear bounded automata.

As to why $L\_2$ is not context-free where as $L\_1$ is context free, CFL's are not closed under subset operation. Consider the following:

$\\{a^p\ |\ p $ is prime $\\}$ is not a CFL, where as $\\{a^n\ |\ n \> 1\\}$ is a CFL. This is because there is an additional condition on $n$ and the pushdown automata cannot check this additional condition.

Here, $L\_2$ can be written as shown here:

> $L\_2 = \\{a^nb^mc^{n+m}\ | \ n,m \>1$ and $n=m \\}$ is not a CFL where as $L\_1$ is, because of additional condition $n=m$ and a pushdown automata will not be able to check this additional condition.

The language $L\_2$ is accepted by Linear Bounded Automaton or Two-Stack PDA.

The question, "which class a language belongs?" is meaningless, because you can construct any number of language classes to which a particular language belongs. Heck, it will belong to its own language class too. The question "which class among the known hierarchy of language classes a language belongs?" might be more meaningful. But probably you meant this only when you asked the question.
> 5 votes

# Answer
Here is a simpler example: $$ \begin{align\*} L\_1 &= \\{ a^n b^m : n,m \geq 0\\} & \text{is regular}, \\ L\_2 &= \\{ a^n b^n : n \geq 0\\} & \text{isn't regular}. \end{align\*} $$

More generally, if a language $L$ is regular (or context-free), we are not guaranteed that any sublanguage is regular (or context-free). Indeed, any language over an alphabet $\Sigma$ is a subset of the regular language $\Sigma^\*$, but not all of them are regular (or even context-free).

You can say, however, that if $L$ is regular (or context-free) and $M$ is a *regular* language, then $L \cap M$ is regular (or context-free). For example, $L\_3 = \\{ w : \\#\_a(w) = \\#\_b(w) \\}$ is context-free and $a^\*b^\*$ is regular, and so $L\_3 \cap a^\*b^\* = \\{a^nb^n : n \geq 0\\}$ is context-free.
> 2 votes

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


# Question
Title: Is there constraint on reducibility while defining $\Sigma_i^p$?
Sanjeev Arora and Boaz Barak define $\Sigma\_i^p$ to be the set of languages such that if $L\in \Sigma\_i^p$ then for every $x \in L \Longleftrightarrow \exists u\_1 \forall u\_2\ldots Qu\_i M(x,u\_1,u\_2,\ldots,u\_i) = 1 $ where $Q\_i$ is $\exists$ or $\forall$ depending on whether $i$ is odd or even and $M$ is a Turing machine that runs in polynomial time. But there is no mention whether the reduction of membership of $x$ to the truth value of the statement $\exists u\_1 \forall u\_2\ldots Qu\_i M(x,u\_1,u\_2,\ldots,u\_i) = 1 $ takes place in polynomial amount of time. Am I misunderstanding something ?

# Answer
> 1 votes
In this definition, $M$ is constrained only to be a polytime relation, that is, you can compute $M$ in polynomial time. Note that there is no *reduction* here. The concept of reduction only comes up when you try to deduce that one problem is in a certain level of the hierarchy (or hard for a certain level of the hierarchy) given that another one is in some level of the hierarchy (hard for a certain level of the hierarchy).

For example, if $A \in \Sigma\_i^P$ and $B$ polytime many-one reduces to $A$, then $B \in \Sigma\_i^P$. If $A$ is $\Sigma\_i^P$-hard and $A$ polytime many-one reduces to $B$ then $B$ is $\Sigma\_i^P$-hard. If we consider reduction that are not polytime but are still in the polynomial hierarchy, we still get meaningful results that I encourage you to work out.

---
Tags: complexity-theory
---


# Question
Title: how to prove that nlogn is not Θ(n) without using limits?
i'm studying an algorithms designing and analysis , and i've question about Big-theta

how can i prove that **nlogn is not Θ(n)** without using limits ?

# Answer
> 8 votes
Remember that $f \in \Theta(g) \iff f \in O(g) \land g \in O(f)$, so $f \notin \Theta(g) \iff f \notin O(g) \lor g \notin O(f)$.

One definition of big-O notation that doesn't use limits is

$$ f \in O(g) \triangleq \exists c, N, \forall n \> N, f(n) \< c \cdot g(n) $$

The negation is logically equivalent to

$$ \lnot (\exists c, N, \forall n, n \> N \implies f(n) \< c \cdot g(n))\\ \lnot (\exists c, N, \forall n, \lnot (n \> N) \lor f(n) \< c \cdot g(n))\\ \forall c, N, \lnot (\forall n, \lnot (n \> N) \lor f(n) \< c \cdot g(n))\\ \forall c, N, \exists n, \lnot (\lnot (n \> N) \lor f(n) \< c \cdot g(n))\\ \forall c, N, \exists n, \lnot \lnot (n \> N) \land \lnot (f(n) \< c \cdot g(n))\\ \forall c, N, \exists n \> N, \lnot (f(n) \< c \cdot g(n))\\ \forall c, N, \exists n \> N, f(n) \geq c \cdot g(n)\\ $$

So, to show that $n \log n \notin \Theta(n)$, you'll want to find a *witness* $n$ that will be based on a $c$ and $N$ that are abstract, and show that $n \log n \geq c \cdot n$.

Here is an example with some other functions:

**Claim**: $n^2 \notin O(n)$.

**Proof**: Given $c$ and $N$ as above, let

$$n \triangleq \begin{cases} c & N \< 1\\ N c & N \geq 1. \end{cases}$$

In the first case, $n^2 = c^2 \geq c \cdot c = c \cdot n$.

In the second, $n^2 = N^2 c^2 = N (N c^2) \geq N c^2 = c (c N) = c \cdot n$.

I won't do the example with $n \log n$, because I'd like you to see the principle and I don't want to accidentally do you homework.

# Answer
> 0 votes
There should be a $C$ such that $n\log(n)\<Cn$, or $\log(n)\<C$ for $n\>N$. This is not possible as the logarithm function is unbounded. \[If there was such a $C$, then $n\<e^C$ ?!\]

---
Tags: algorithms, complexity-theory, algorithm-analysis, asymptotics
---


# Question
Title: Relational query for universally quantified formula
My university is participating in the implementation of a library borrowing managing system at Richelieu National Library in France.

I received the order to formulate the query: "find all users having borrowed every book" in relational Algebra, in relational Calculus and in SQL (which would probably not happen, probably librarians want to test the limits of the database).

The database has the following pattern (the primary keys are in bold):

Borrowing(**People, Book, DateBorrowing**, ExpectedReturnDate, EffectiveReturnDate)
Lateness(**People, Book, DateBorrowing**, LatenessFee)

I tried

$$\Pi\_{People}(Borrowing)\div\Pi\_{People}(\sigma\_{Book} (Borrowing))$$

But It seemed to be wrong as far as to do $r\div s$, $S\subseteq R$ is needed, which seems not to be the case, but why? I'm still talking about people, isn't it?

I then tried the following relational calculus formula:

$$\\{t.People|Borrowing(t)\wedge(\forall u Borrowing(u)\Rightarrow t.DateBorrowing)\\}$$

To find every books that have a borrowing date. I know this calcuation is false but I don't know how to do better...

Then in SQL:

```
SELECT People FROM Borrowing
    WHERE FORALL Books EXISTS DateBorrowing

```

That is what I tried and I know that is not the right way to "find all users having borrowed every book". Can you help me expressing correctely such a querry?

# Answer
> 3 votes
SQL does not have a universal quantifier, but an equivalent can be constructed from the existential one, through a normalization process similar to Skolemization: $$\forall x P(x) \iff \nexists x \neg P(x)$$

In your case, you want the users for which there does not exist a book that they have not borrowed:

```
select * from people p
where not exists
  (select * from books b
   where b.id not in
     (select book_id
      from borrowings
      where people_id=p.id)
  )

```

(Note that I have assumed tables for people and books to represent their existence separately from the borrowings table, which, for instance, may be empty at the inception of the system.)

# Answer
> 1 votes
For the SQL part:

First, you want to determine how many books there are:

```
SELECT COUNT(DISTINCT book) FROM Borrowing)

```

Next, you want to `SELECT` those people who have Borrowed every different book - so one way to do this is by checking that the `COUNT` of `DISTINCT` books for each person is the same as the `COUNT` of all `DISTINCT` books:

```
 SELECT people
 FROM Borrowing
 GROUP BY people
 HAVING COUNT(DISTINCT Book) = (SELECT COUNT(DISTINCT Book) FROM Borrowing);

```

# Answer
> -3 votes
select distinct people from borrowing group by people having count(book) in (select count(book) from borrowing);

---
Tags: database-theory, relational-algebra
---


# Question
Title: About a universal (functionally complete) function producing a constant
I read in a note the following:

Suppose we have a boolean function $f(x,y,z,w)$, if $f(a,a,a,a)=1$ then $f$ can't be functionally complete.

Why is that? how does it imply that $f$ can't produce nand or nor?

# Answer
The claim is false if you're allowed to use constants. Take $f(x,y,0,0) = f(x,y,1,1) = 1$ and $f(x,y,0,1) = f(x,y,1,0) = x \text{ NAND } y$. If you're not allowed to use constants, then every function that you can get by composing $f$ with itself will have the property that if all inputs are 1, then so is the output. NAND doesn't have that property.
> 2 votes

---
Tags: logic, boolean-algebra
---


# Question
Title: Boolean algebra truths with more than one digit
I understand that when you 0 AND 0 it will result in 0 and that 1 AND 1 will result in 1 etc but what I don't understand is if the question was 01 AND 11. How would I work this out?

# Answer
> 2 votes
Since these operations are defined per pair of boolean values, you should apply them for each boolean pairwise. In your example this will be:
b0 b1  AND  b2 b3    =    (b0 AND b2)  (b1 AND b3)

# Answer
> 3 votes
This notation is usually used for *bitwise* operations. You compute the operation bit by bit – the $i$th bit of the answer is (in this case) the AND of the $i$th bits of the inputs.

---

From a more theoretical side of things, this bitwise rule does turn $k$-bit numbers into a Boolean algebra. Boolean algebras are sets together with several operations that satisfy certain axioms (there are several equivalent versions which are easy to find online). Stone's representation theorem states that every Boolean algebra is a field of sets, which in the finite case just means that it consists of $k$-bit numbers for some $k$.

Boolean algebras have found deep applications in set theory, though the relevant Boolean algebras are always infinite. In this application at least, it is certainly possible to think of the values of the Boolean algebra as truth values. One can then obtain a more conventional truth value by using an ultrafilter.

---
Tags: boolean-algebra
---


# Question
Title: What does the "principle of deferred decisions" formally mean
I have encountered the phrase "Principle of deferred decisions" in Mitzenmacher and Upfal's book on Randomized Algorithms and several other courses online. Isn't it just conditional probability? In my understanding, it seems to be an intuitive way of using conditional probability:

$\Pr(\bigcap\_{i = 1}^{n} E\_i) = \prod\_{i = 1}^{n} \Pr(E\_i | E\_{i-1},\dots,E\_{0})$ where $E\_0 = \emptyset$.

Is my understanding right?

# Answer
The principle of deferred decisions is the concept that we have two ways to make a random choice both of which are equivalent.

One way is that you can toss a coin yourself at the exact step when you need a random input in some algorithm. In the other way you can imagine that there is an oracle who has already tossed a coin infinitely many times and has some sequence of the form $HTHTHH\dots$, and we query this oracle to tell us the next randomized outcome.

Basically we can defer the act of actually using a randomized input for as long as we have to and this won't affect the *randomness* of this input.
> 7 votes

---
Tags: algorithm-analysis, probability-theory, randomized-algorithms, probabilistic-algorithms
---


# Question
Title: Why does a satisfiable formula have a model?
I am studying Satisfiability of CNF formulas, and my lecture says that if for a certain formula there is a set of assignments such that formula is true then there is a model. My question is: Why does it say that there is a model? What is the relation between assignment and model?

# Answer
A set of formulas has a *model* if there is a truth assignment satisfying all the formulas. That's the definition. So if a formula is satisfiable, by definition it has a model.

What is this definition trying to capture? Your set of formulas defines an abstract situation, that may or may not be contradictory. A *model* is a "physical incarnation" of this set of formulas, that shows that the set of formulas is consistent.

Also, you might have derived some other formulas from the set of formulas. For example, given the axioms of a group, you might have derived Lagrange's theorem. Every model of the axioms will also satisfy the conclusions – every group satisfies Lagrange's theorem.
> 3 votes

---
Tags: satisfiability
---


# Question
Title: MST: Prim's algorithm complexity, why not $O(EV \lg V)$?
According to CLRS, the Prim's algorithms is implemented as below --

> $\mathtt{\text{MST-PRIM}}(G,w,r)$
>
> * for each $u \in V\[G\]$ do
> + $\mathtt{\text{key}}\[u\] \leftarrow \infty$
>     + $\pi\[u\] \leftarrow \mathtt{\text{NIL}}$
> * $\mathtt{\text{key}}\[r\] \leftarrow 0$
> * $Q \leftarrow V\[G\]$
> * while $Q \ne \emptyset$ do // ... $O(V)$
>     + $u$ $\leftarrow$ $\mathtt{\text{EXTRACT-MIN}}(u)$ // ... $O(\lg V)$
>     - for each $v \in \mathtt{\text{adj}}\[u\]$ do // ... $O(E)$
>         * if $v \in Q$ and $w(u,v) \gt \mathtt{\text{key}}\[v\]$
>                 + then $\pi\[v\] \leftarrow u$
>                     - $\mathtt{\text{key}} \leftarrow w(u,v)$ // $\mathtt{\text{DECREASE-KEY}}$ ... $O(\lg V)$

The book says the total complexity is $O(V \lg V + E \lg V) \approx O(E \lg V)$. However, what I understood is that the inner `for` loop with the `DECREASE-KEY` operation will cost $O(E \lg V)$, and the outer `while` loop encloses both the `EXTRACT-MIN` and the inner `for` loop, so the total complexity should be $O(V (\lg V + E \lg V)) = O(V \lg V + EV \lg V) \approx O(EV \lg V)$.

Why the complexity analysis is not performed as such? and What is wrong with my formulation?

# Answer
> 9 votes
The complexity is derived as follows. The initialization phase costs $O(V)$. The $while$ loop is executed $\left| V \right|$ times. The $for$ loop nested within the $while$ loop is executed $degree(u)$ times. Finally, the handshaking lemma implies that there are $\Theta(E)$ implicit DECREASE-KEY’s. Therefore, the complexity is: $\Theta(V)\* T\_{EXTRACT-MIN} + \Theta(E) * T\_{DECREASE-KEY}$.

The actual complexity depends on the data structure actually used in the algorithm. Using an array, $T\_{EXTRACT-MIN} = O(V), T\_{DECREASE-KEY} = O(1)$, complexity is $O(V^2)$ in the worst case.

Using a binary heap, $T\_{EXTRACT-MIN} = O(\log V), T\_{DECREASE-KEY} = O(\log V)$, complexity is $O(E \log V)$ in the worst case. Here is why: since the graph is connected, then $\left| E \right| \ge \left| V \right| - 1$, and $E$ is at most $V^2$ (worst case, for a dense graph) . Probably, you missed this point.

Using a Fibonacci Heap, $T\_{EXTRACT-MIN} = O(\log V)$ amortized, $T\_{DECREASE-KEY} = O(1)$ amortized, complexity is $O(E + V \log V)$ in the worst case.

# Answer
> 1 votes
Your idea seems correct. Let's take the complexity as $V(\lg v + E\lg v)$. Then notice that in the inner for loop, we are actually going through all the vertices, and not the edges, so let's modify a little to $V(\lg v + V\lg v)$, which means $V\lg v + V^2\lg v$. But for worst case analysis (dense graphs), $V^2$ is roughly equal to number of edges, $E$, giving $V\lg v + E\lg v = (V+E)\lg v$ but since $V \ll E$, hence $E\lg v$.

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


# Question
Title: Show that the Halting problem is reducible to its complement
> HALT$\_{TM}$ is the set of all machine-input pairs $\<M,w\> $ where $M$ halts on input $w$
>
> The complement of HALT$\_{TM}$ is the set of all machine-input pairs $\<M,w\> $ where $M$ doesn't halt on input $w$
>
> Show that HALT$\_{TM}$ is turing reducible to its complement, and explain why it's impossible for it to me many-one reducible.

Regarding the Turing reduction, I've made reduction proofs using using A$\_{TM}$ and HALT$\_{TM}$ but this doesn't make sense to me intuitively.

I understand the concept of many-one reduction using the Oracle, but have difficulty applying it, not being given any examples to work with.

I'd hugely appreciate it if someone could help me approach the above question, I'm more concerned with the approach rather than the answer, as I've an exam tomorrow!

Thanks a lot.

# Answer
> 6 votes
Suppose $HALT$ was many one reducible to $\overline{HALT}$. Let the mapping function be $f$. We construct a machine $D$. It takes input $\langle M,w \rangle$ obtains the string $f(\langle M,w \rangle)=\langle M^{'},w^{'} \rangle$. $D$ simulates $ M$ on $w$ and $M^{'}$ on $w^{'}$. If the first simulation ends $D$ accepts if second simulation ends/halts it rejects. $D$ is a decider for $HALT$ which is not possible.

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


# Question
Title: Optimal way to join pieces when the cost of joining two pieces is $|x-y|$
There are $N$ pieces each having size $A\_i$. The cost of joining a piece of size $x$ and a piece of size $y$ is $|x-y|$. What is the most optimal way to join all the pieces? Can it be solved using the max-flow algorithm?

# Answer
> 1 votes
I assume you have to join the pieces in a sequence of $(N-1)$ joins to make a connected sequence. I also assume if you join two subsequences then the cost of joining is size difference between the size of the last element of the first subsequence and the size of the first element of the second subsequence.

Sort all the pieces and join them in the order of increasing or decreasing sizes. Total cost will be $\max\_i A\_i - \min\_i A\_i$. The time complexity of this algorithm will be $O(N \log N + NT)$ where $O(T)$ is the time complexity of joining two pieces.

---
Tags: algorithms, greedy-algorithms
---