title: Why is NP-hard not necessarily NP?

text:
# Question
Title: Why is NP-hard not necessarily NP?
A problem X is NP-hard if every problem in NP can be reduced to X. But every problem in NP has a polynomial time verification algorithm, so then does that not mean that I can also verify X in polynomial time because every NP problem is reducible to X? Can someone please explain or give an example.

# Answer
> 7 votes
Here is an abstract definition of the concepts NP-hard and NP-complete. If $A,B$ are two decision problems, say that $A \leq B$ if there is a polytime reduction from $A$ to $B$, that is, if there exists a polytime function $f$ such that $x \in A$ iff $f(x) \in B$. Then: $$ \begin{align\*} &\mathsf{NP\text{-}hard} = \\{ B : A \leq B \text{ for all } A \in \mathsf{NP} \\}, \\ &\mathsf{NP\text{-}complete} = \mathsf{NP\text{-}hard} \cap \mathsf{NP}. \end{align\*} $$

Here is a different example. Consider the universe of all subsets of $\mathbb{N}$, ordered under $A \leq B$ if $A \subseteq B$. Let $\mathsf{X}$ consist of all subsets of some fixed set $X$. Define $\mathsf{X\text{-}hard}$ and $\mathsf{X\text{-}complete}$ just as above. You can check that $$ \begin{align\*} &\mathsf{X\text{-}hard} = \\{ S : S \supseteq X \\}, \\ &\mathsf{X\text{-}complete} = \\{ X \\}. \end{align\*} $$ In a similar way, NP-hardness is a lower bound on the difficulty, whereas NP-completeness is both a lower bound and an upper bound. In contrast to the second example above, there are many NP-complete problems, all of them having the same level of difficulty (two problems $A,B$ have the same level of difficulty if $A \leq B \leq A$).

Finally, here is a concrete problem which is NP-hard but not NP-complete: the halting problem.

**The halting problem is NP-hard.** Let $A$ be any computable decision problem, say computed by a Turing machine $M$ which always halts. Let $M'$ be the Turing machine which simulates $M$, halts if $M$ accepts, and runs into an infinite loop if $M$ rejects. Define a polytime function $f$ by $f(x) = (\langle M' \rangle,x)$. Then $x \in A$ iff $M$ accepts $x$ iff $M'$ halts on $x$ iff $f(x) \in \mathsf{HALT}$.

**The halting problem is not in NP.** The halting problem is not computable, and in particular not in NP.

# Answer
> 3 votes
> But every problem in NP has a polynomial time verification algorithm, so then does that not mean that I can also verify X in polynomial time because every NP problem is reducible to X?

No. If a problem $P$ is **polynomial-time** reducible to $X$, it means that a solution for $X$ can be used to solve problem $P$ (in no more time that is required to find the solution for $X$), and not necessarily that a solution for $P$ may be used to solve problem $X$ (unless $X$ is also polynomial-time reducible to $P$). Provided, clearly, that those problems require at least a polynomial-time algorithm to find their solution. In other words, $X$ is at least as hard as $P$, that is we have an upper bound of the hardness of $P$.

You need to think about the reduction as a mapping: whenever you have a solution for $X$, you also have a solution for $P$. A more accurate definition of what a reduction is can be found here.

# Answer
> 2 votes
An *NP-hard* problem can be beyond NP. The polynomial-time reduction from your X to any problem in NP does not necessarily have a polynomial-time inverse. If the inverse is harder, then the verification is harder.

An **NP-complete** problem, on the other hand, is one that is NP-hard and itself in NP. For these, of course, there exist polynomial time verifications.

# Answer
> 0 votes
> Can someone please explain or give an example?

I'll give an example.

The *Clique* *Problem*:

> A **clique** in an undirected graph $G=(V,E)$ is a subset $V' \subseteq V$ of vertices, each pair of which is connected by an edge in $E$. In other words, a clique is a complete subgraph of $G$. The **size** of a clique is the number of vertices it contains.
>
> The **clique optimization problem** is the problem of finding a clique of maximum size in a graph.
>
> The **clique decision problem** is simply whether or not a clique of size $k$ (given input) exists in the graph.

The clique *decision* problem is in **NP-complete**, although the clique *optimization* problem is in **NP-hard**.

We **can** reduce from the clique *decision* problem to the clique *optimization* problem in polynomial time. This is easier, we simply solve the optimization problem, then check that the size of the maximum clique is greater than or equal to $k$. This is because of a simple relation: any clique of size $n$ contains a clique of size $n-1$.

We **cannot** verify the clique *optimization* problem in polynomial time. If the optimization problem is given a certificate, we can verify that the certificate *is* a clique in polynomial time (similar to the decision problem), but we cannot verify that the certificate is a *maximum* clique in polynomial time. Thus it is only in **NP-hard**, not in **NP**.

Generally speaking, a lot of problems in **NP-hard** are optimization problems because it is difficult to verify that a certificate for the problem is in fact optimal.

# Answer
> 0 votes
It is actually enough if *one* NP complete problem X can be reduced in polynomial time to a problem Y to make Y NP-hard. (Because every problem in NP can be reduced to any NP complete problem).

Most problems can be viewed as special cases of a harder problem. If problem A is a special case of a harder problem B, then there is a reduction from problem A to problem B that isn't just polynomial time, but zero time.

Think about the consequence of what you are saying: If Y had to be in NP, then it would be impossible to have an NP-complete problem that is a special case of a more general problem that is not in NP.

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


title: Rotations in a treap

text:
# Question
Title: Rotations in a treap
I have a treap like the first image and I want to reach the second image to restore min heap order property. I can't understand which kinds of rotations have been done.

Image 1

Image 2

# Answer
Initially, node `F` is violating the heap invariant. Its priority is too small, and it needs to be moved up the treap. The only operation needed is a *single rotation*. If you are not already familiar, please read this Wikipedia entry. Here are some illustrative diagrams:

I've drawn snapshots of the rotation process below. In each diagram, I've marked where the rotation is about to happen with stars (e.g. `*E:14*`). The direction of rotation should be obvious: the goal is to get `F` up the tree! Notice that as long as `F` is violating the heap invariant, we're rotating the parent of `F`.

```
       G:3
      /   \
    B:6   K:8
   /   \     \
A:11   D:9   L:12
      /   \
    C:16  *E:14*
             \
             F:2

       G:3
      /   \
    B:6   K:8
   /   \     \
A:11  *D:9*  L:12
      /   \
    C:16  F:2
          /
        E:14

       G:3
      /   \
   *B:6*  K:8
   /   \     \
A:11   F:2   L:12
      /
    D:9
   /   \
 C:16  E:14

       *G:3*
       /   \
     F:2    K:8
     /        \
   B:6         L:12
  /   \
A:11   D:9
      /   \
    C:16  E:14

      F:2
     /   \
   B:6    G:3
  /   \     \
A:11   D:9   K:8
      /   \    \
    C:16  E:14  L:12

```

There are some really nice properties of rotations which make this work. Obviously rotations preserve the in-order traversal of the tree. But also notice that, whenever a subtree is detached/reattached during a rotation, there is never a priority inversion (i.e. you never attach a subtree as a child of a node with a larger priority).
> 1 votes

---
Tags: trees, heaps, binary-search-trees
---


# Question
Title: Problem easy for humans and hard for general purpose machine learning, not needing external context?
There are many problems that people can solve more easily than a machine learning algorithm. Often this is attributed to the extra context we have access to.

Image segmentation is an example of a problem that people are good at, but algorithms are not good at, probably because people have lots of external contextual knowledge they bring to bear on the problem. To date, the best techniques use a human in the loop, such as this technique called click carving from HCOMP 2016.

Are there problems that people can solve more easily than most or all machine learning algorithms, where people do not need to depend on access to external context?

Here is another example that is easy for people but hard for a particular algorithm implementation called XGBoost. A human can easily fill in the missing shapes with 100% accuracy, but XGBoost cannot score above 50% accuracy, and its accuracy drops as it gets more training data. Neural networks also seem to have difficulty with this problem.

Note that the person does not need external knowledge about the problem that the algorithm does not have, in order to perform better. All the person needs to see is the configuration of shapes, and they can guess from that what the missing shapes are. The only information the human needs is that the simplest description of the data is most likely the best description, and that the training data is randomly sampled. Both items of information are used in designing XGBoost, and most ML algorithms for that matter.

Are there other concrete examples like this? Historically, the XOR problem showed that single node perceptrons were inadequate, leading to today's neural network. Besides that, I do not know of any other historical examples.

# Answer
> 0 votes
This answer is an ongoing catalogue of instances I find.

1. "A Deep Belief Net Learning Problem" explains why shallow networks cannot learn XOR problems, stating that deep networks can. However, empirically deep networks are not good at learning XOR problems, suggesting the XOR problem is one that is easy for humans but hard for neural networks.

---
Tags: machine-learning, computer-vs-human
---


# Question
Title: Total functional computable real numbers
Is there any computable real number which can not be computed by a higher order primitive recursive algorithm?

For computable real number I mean those that can be computed by a Turing machine to any desired precision in finite time. For higher order primitive recursive algorithm I mean common primitive recursive functions theory extended with first-class functions (as in Ackermann function).

Turing machines are more powerful than higher order primitive recursive functions so there exists the possibility that some computable reals numbers are not expressible by them.

# Answer
> 4 votes
The set of higher-order primitive recursive reals is *essentially* the class of functions $\mathbb{N}\rightarrow\mathbb{N}$ which can be represented by a term $\mathrm{Nat}\rightarrow\mathrm{Nat}$ in Gödel's system T.

Since every such function is total, and every well-typed term in the system can be enumerated effectively, there is a relatively easy proof by diagonalization that there is some computable real which cannot be represented.

---
Tags: computability, primitive-recursion, real-numbers
---


# Question
Title: small size and small depth circuit for set intersections
**Input:** Given sets $S\_i \subseteq \\{1,2,3,4,\cdots,n\\}$ for $1 \leq i \leq n$.

**Output:** sets intersection with restriction (pick first set $S\_1$. If $a \in S\_1$ such that $a$ is the least element then do $S\_1\cap S\_a$. Next go to least element (say $b$) in $S\_1\cap S\_a$ and do $S\_1\cap S\_a \cap S\_b$)

Finally I want to find the $S\_1\cap S\_{i\_1}\cap S\_{i\_2}\cdots \cap S\_{i\_{k-1}}$ where $i\_1$ least element in $S\_1$ and $i\_2$ least element in $S\_1\cap S\_{i\_1}$, $i\_3$ least element in $S\_1\cap S\_{i\_1} \cap S\_{i\_2}$, $\cdots$, $i\_{k-1}$ least element in $S\_1\cap S\_{i\_1}\cap S\_{i\_2}\cdots \cap S\_{i\_{k-2}}$.

Can we build circuit for this above problem?

What happens if $k$ is fixed? what happens if $k$ is $\log n$?

Can we have logspace algorithm for this problem?

I am familiar with circuits and logics and please help out.

**I tried as follows:**

first construct a matrix $A$ with $n \times n$ with entries zero's and one's. Find the entry $(i,j)$ is one if $S\_i$ have element $j$. other wise zero.

Now we need to find the first non zero entry (say a) in $S\_1$ row in $A$ and do or gate $S\_1$ row with $S\_a$ row in $A$.
Again find the first non zero entry (say b) in $S\_1 \vee S\_a$ row and do $S\_1\vee S\_a \vee S\_b$.

Now this process I can not able to find the depth and size of circuit. Please let me know what is the circuit size and depth in this process.

# Answer
You are asking many different questions. The usual rule is one question per post. To help you get started, here is how to compute $S\_1 \cap S\_{\min S\_1}$ (defined as $\emptyset$ if $S\_1 = \emptyset$).

The input to the circuit is the $n^2$ variables $x\_{i,j}$, indicating $i \in S\_j$ (this means that they are TRUE if the condition holds, and FALSE if it doesn't hold). The output to the circuit are $n$ variables $y\_i$, indicating whether $i \in S\_1 \cap S\_{\min A}$.

Let $f\_a$ indicate $\min S\_1 = a$. Then $$ f\_a = \lnot x\_{1,1} \land \cdots \land \lnot x\_{a-1,1} \land x\_a. $$ Given these, we can calculate $$ y\_i = x\_{i,1} \land \bigvee\_{a=1}^n (f\_a \land x\_{i,a}). $$ We can implement each $f\_a$ as a depth 2 circuit with unbounded fan in of size $O(a)$, and each $y\_i$ as a depth 2 circuit (with inputs $f\_a$ and $x\_{i,j}$) with unbounded fan in of size $O(n)$. The circuits for $f\_a$ take $O(n^2)$ in total and the circuits for $y\_i$ take $O(n^2)$ in total, so altogether we get a depth 4 circuit of size $O(n^2)$.

This circuit is equivalent to a depth $O(\log n)$ circuit of size $O(n^2)$ with bounded fan-in, by replacing each large fan-in gate by a balanced binary tree.
> 1 votes

---
Tags: algorithms, complexity-theory, circuits, linear-algebra, sequential-circuit
---


# Question
Title: A data structure for holding numbers in 2 sets, using BST?
Design a data structure for holding numbers in two sets:

**Init** \- initiate the DS with two empty sets. `O(1)`

**Insert(a,S)** \- insert number `a` to set `S` (`S` could be `X` or `Y`). `O(log(n))`. (n is the total number of numbers in the DS)

**Find** \- find a number `a` in the DS such that the number of numbers in `X` that are smaller than `a` equals the number of numbers in `Y` that are bigger than `a`, if exists such number. `O(1)`

---

My attempt is using 2 augmented balanced binary search trees, each one presents set `X` or `Y`, insert into it the new number and saving in each node information for finding what is the number of numbers in `X` that are smaller than this node and the number of numbers on `Y` that are bigger than that node.

But given that information how could I implement the `Find` procedure in `O(1)`? Or maybe someone have better design (preferably using augmented BST)?

# Answer
> 1 votes
Since it's your exercise, I don't want to prevent you from finding the solution on your own, but I'll give you some possible hints:

Big hint:

> You can do some work during the Insert operation to make any subsequent Find run fast.

Think about that one for a while.

---

If you're still stuck, here are some more specific hints. I recommend you think about each one for 15 minutes or more before moving on to the next one.

Hint #2:

> Suppose you wanted to implement an operation InsertAndFind(a,S), that effectively does Insert(a,S) followed by Find(). Could you make that run in O(log n) time?

Hint #3:

> It would also be possible to have a single data structure (e.g., a single augmented balanced binary search tree), with some information in each node.

Hint #4:

> What information would you want to keep in a node, to determine whether that node is something that could be returned in response to a future Find query?

---
Tags: data-structures, binary-search-trees
---


# Question
Title: how to express the performance of a policy in policy parameters
Suppose a leauge of tic-tac-toe playing agents. As the league proceeds, the bad players are kicked out, and better players come in. The problem resides on how to at least approximate the *better* player.

One way to think of is an evolutionary approach. By random mutation possibly followed by crossovers, you may expect that slowly the players will converge to the optimum.

But I want something more deterministic. Assuming the policy function of each agent is differentiable, there are many methods to speed up the optimization. I will use the term *policy* as a function that takes the current board as input and ouputs the best move to play. Whatever method I choose, they need the performance as input. One obvious performance metric is the winrate, which usually works fine to approximate the performance itself, but it doesn't contain any parameter from the policy function. To optimize the policy to maximize the performance, things work best when the performance can be expressed in the parameters defining the policy, so that I can take the gradient of the performance with respect to the policy parameters, and update the policy following the gradient; that is, gradient ascent.

So back to the title, what is a good way to express the performance of a policy in policy parameters?

# Answer
> 1 votes
I suggest you study reinforcement learning, and possibly Q-learning. They are aimed at dealing with this kind of situation.

The short answer is that we almost never have a way to give a closed-form formula that measures how good a policy is, as a function of the policy parameters. Rather, we use simulations: we conduct a bunch of simulations using that policy, measure how well it performs in simulation, and use that our estimate of the quality of the policy. Then we apply stochastic gradient descent or other optimization methods to find parameter values that maximize the quality of the policy.

# Answer
> 1 votes
Your best bet to find something you want would be to start at some Reinforcement Learning reference, especially since tic-tac-toe agents should be fairly commonplace among introductory RL stuff. A reference I recommend is Reinforcement Learning: An Introduction

For more advanced/general references to learn policies for a variety of problems, I recommend the following:

1. Volume I & II of Dynamic Programming and Optimal Control
2. Approximate Dynamic Programming: Solving the Curses of Dimensionality
3. Neuro-Dynamic Programming

Creating/learning policies can be a challenging area for real world problems, but very exciting when things work out. Good luck!

---
Tags: machine-learning, artificial-intelligence
---


title: Counters in Turing machines

text:
# Question
Title: Counters in Turing machines
I know how a Turing machine works, how it accepts a language but in some.

In some scenarios we would like to use counters. For example, I want to develop a machine that accepts $\\{0^{2n} : n \geq 0\\}$. How can I count the number of zeroes?

If some one of you could solve the following problem for me it would help my understanding of these matters:

> Design a Turing machine for $L = \\{1^{3^n} : n \geq 1\\}$.

# Answer
> 0 votes
I know this question has quite a few months already, but I'd like to share here the Turing Machine for $\\{0^{2^n} : n \geq 0\\}$ found in Michael Sipser's Introduction to the Theory of Computation, 3rd edition (Example 3.7).

The idea behind this machine is as follows, everything after this line is a direct quote of the book:

“On input string w:

1. Sweep left to right across the tape, crossing off every other 0.
2. If in stage 1 the tape contained a single 0, accept .
3. If in stage 1 the tape contained more than a single 0 and the number of 0s was odd, reject .
4. Return the head to the left-hand end of the tape.
5. Go to stage 1.”

Each iteration of stage 1 cuts the number of 0s in half. As the machine sweeps across the tape in stage 1, it keeps track of whether the number of 0s seen is even or odd. If that number is odd and greater than 1, the original number of 0s in the input could not have been a power of 2. Therefore, the machine rejects in this instance. However, if the number of 0s seen is 1, the original number must have been a power of 2. So in this case, the machine accepts.

# Answer
> 2 votes
Well, you could just implement a counter. I'll assume that the tape alphabet is $\\{0,1,\\#\\}$.

First, scan to the end of the input, and write $\\#0$ to the tape after the last character. The string of zeroes and ones after the $\\#$ will be a binary counter.

Second, convince yourself that a Turing machine can add one to a number in binary.

Third, peform the following until you run out of input. Scan back to the first $1$ on the tape, replace it with a $\\#$, scan back to the counter and add one to it.

Finally, when you've run out of input, check that the value of the counter is a number of the required type. For example, it has the value $2^k$ for some $k$ precisely if it matches the regular expression $10^\*$. For $3^k$, you can either convince yourself that Turing machines can divide a binary number by $3$ or – easier! – keep your counter in ternary instead of binary.

---
Tags: turing-machines
---


# Question
Title: Swap elements using integer addition and multiplication gates
I need to swap two integers using only integer addition and multiplication gates. I can't subtract them. I'm dealing with a sorting network, so I need to compare and swap. The compare and swap operation swaps only if the integers being compared are in wrong order. I've to implement this operation using just integer addition and multiplication as the atomic operations. I've figured out the comparing bit, but I need to efficiently swap integers. Is there an efficient solution (minimum multiplication gates) to this problem?

P.S: I have integers in the form of binary vectors, but I can't apply mod 2 operations on them. I can only use integer addition and multiplication.

# Answer
> 3 votes
Let's say we have inputs $x, y$ and $c$, where $c$ is either 0 or 1, 0 = no swap, 1 = swap. We can make a conditional swap function like this:

```
notc = 1 + (-1)*c
x' = notc*x + c*y
y' = c*x + notc*y

```

Even if you have no negative integers, as long as your integers are modulo $2^n$, you can use $-1 \equiv 2^n - 1 \mod 2^n$ and everything works out.

---
Tags: sorting, integers, multiplication
---


title: Show $f(n)\log f(n)^c=O(g(n)\log g(n))$

text:
# Question
Title: Show $f(n)\log f(n)^c=O(g(n)\log g(n))$
> You are given functions $f$ and $g$ such that $f(n)=O(g(n))$. Show that $f(n)\log\_2(f(n)^c)=O(g(n)\log\_2(g(n)))$. (Here $c$ is some positive constant.) You should assume that $f$ and $g$ are nondecreasing and always bigger than 1.

My solution: There exists $c\_1$ such that $f \leq c\_1 g$. Note that all $\log$ functions are base 2 throughout.

We have that $f \log(f^c) \le c\_1 c g \log(c\_1g) = c\_1 c g \log(c\_1) + c\_1 c g \log(g)$.

Let expression $(\*)$ be as follows:

$(\*) \quad c\_1 c g \log(c\_1) + c\_1 c g \log(g) \le c\_2 g \log(g)$ for some $c\_2 \> 0$.

Then $(\*)$ holds iff $c\_1 c g \log(c\_1) \< 0$ iff $0 \leq c\_1 \leq 1$.

Now put $c\_2 = c\_1 c$, then:

$c\_2 g \log(c\_2 / c) + c\_2 g \log(g) \le c\_2 g \log(g)$ iff $c\_2 / c \> 1$.

Therefore, we require than $c\_2 \> c$, which we cannot guarantee as we have already fixed $c\_2 = c\_1 c$.

What choice of $c\_2$ would guarantee that $c\_2 g \log(c\_2 / c) + c\_2 g \log(g) \le c\_2 g \log(g)$?

I am looking for a formal argument.

# Answer
> 1 votes
An essential hint: "Assume that f and g are nondecreasing". That is essential. Without it the statement is false, for example $f (n) = 2$ and $g = 1 + 2^{-n}$, where log f (n) = 1 and log g (n) ≈ $2^{-n}$.

The problem here is showing that f (n) = O (g (n)) implies log f (n) = O (log (g (n)). So how does "g is non-decreasing" help? Well, if n ≥ N then 1 \< g (N) ≤ g (n) and 0 \< log g (N) ≤ log g (n).

f (n) = O (g (n)) means "there are $N, c \> 0$ so that we have $f (n) ≤ c·g (n)$ for $n ≥ N$". So there are $N, c \> 0$ so that $\log f (n) ≤ c + \log g (n)$ for $n ≥ N$. Now we need to somehow relate c and $\log g (n)$. We have $c = (c \div \log g (N)) · \log g (N) ≤ (c \div \log g (N)) · \log g (n)$, because $g (n)$ is not decreasing. Therefore $\log f (n) ≤ (c \div \log g (N) + 1) · \log g (n)$, so we found a constant c' = (c / log g (N) + 1) such that $\log f (n) ≤ c' · \log g (n)$ for n ≥ N and that means $\log f (n) = O (\log (g (n))$.

---
Tags: asymptotics
---


title: Estimation of average waiting time

text:
# Question
Title: Estimation of average waiting time
I'm simulating a procedure that assigns tasks to servers and want to estimate the average waiting time until a task is served (finds a free server). This procedure runs periodically, thus every task that is rejected in a run can try in the next runs until it finds a free server. The inter-arrival times of tasks follow an exponential distribution. Between runs, some tasks may finish.

Is there a way to estimate the average waiting time of tasks?

# Answer
If tasks arrive faster than they can be dealt with, average waiting time is unbounded.

You can probably adapt the Pollaczek–Khinchine formula to give an analytic answer to your question:

$$L = \rho + \frac{\rho^2 + \lambda^2 \operatorname{Var}(S)}{2(1-\rho)}$$

where

* $L$ is the mean queue length;
* $\lambda$ is the arrival rate of the Poisson process;
* $1/\mu$ is the mean of the service time distribution $S$;
* $\rho={\lambda \over \mu}$ is the utilization; and
* $Var(S)$ is the variance of the service time distribution $S$.
> 0 votes

---
Tags: algorithm-analysis
---


# Question
Title: Hashing methods for validating dowloaded files
The standard algorithm to generate hashes of files which are downloaded is MD5. For example, when ISO files of Linux distributions are offered most of the time they also give the MD5 sum so that you can check if an error happened while downloading the file.

I'm aware of the fact that MD5 should not be used for password hashing as it is fast to compute. However, in the case of downloaded files I think it is desirable if it is computed fast.

Hence my question: Which hashing algorithm is recommended? What are the relevant criteria? If it is easy to find collisions of a hashing algorithm, does that automatically imply that it should not be used in scenarios where one does not expect attacks, but only "random" errors?

# Answer
There are several reasons why one might want to add some extra material to validate a downloaded file. Different reasons require different kinds of extra material.

### Non-malicious corruption

A common type of corruption is that files get truncated. For this, the size is enough.

To detect accidental corruption of the downloaded file for hardware reasons (bits getting flipped, lost or reorderd in transit), any kind of checksum helps. It doesn't have to involve cryptography — for this purpose, MD5 is a little overkill, but suitable. Against accidental corruption, a well-designed checksum that can take $n$ different values has a probability of $1-\frac{1}{n}$ of detecting the corruption.

### Malicious corruption, single-file scenario

Malicious corruption is another matter. Against malicious corruption, you need two things:

1. **A known secure channel**. Without something to bootstrap security, the recipient has no way to know that what they're getting isn't wholly coming from an adversary.
2. A cryptographic tie between the secure channel and the download channel.

The reason to have two separate channels is, to put it succinctly, bandwidth. The goal is to insert the downloaded file into a chain of trust that starts from a computer and its operating system, and may rely on additional assumptions, e.g. trust in a particular website.

An example of a channel separation is when you trust some website (hopefully served over HTTPS, but you don't trust the channel through which the file is downloaded. In practice, these days, often the file would be distributed on the same website, and a separate verification doesn't provide any additional security. However separate verification can still be useful, for example if you've already downloaded the file in the past, but you aren't sure whether your local copy is pristine or whether it's the right version.

To establish a cryptographic tie, the basic method is to use a cryptographic hash function: calculate the hash of the large file distributed through the insecure channel, and distribute the hash through the secure channel. One of the properties of a cryptographic hash $H$ is that it's infeasible to find $x' \neq x$ such that $H(x') = H(x)$ (second preimage resistance); here this means that it's impossible to generate a fake file that has the genuine hash.

MD5 was designed to be a cryptographic hash function, but it is now known not to be one. Its second preimage resistance is not broken yet, but due to the weaknesses that have been found in MD5, the cryptography community no longer trusts it for anything. What has been broken for MD5 is its collision resistance, i.e. there are cheap ways of generating $x \ne x'$ such that $\mathrm{MD5}(x) = \mathrm{MD5}(x')$. (Note the difference with second preimage resistance: here the adversary does not get to choose the hash value.)

In addition to the risk that an attack would be found on second preimage resistance, there's a reason not to use MD5 to verify that something is genuine. Because collisions can be generated, it's possible to perform a bait-and-switch attack:

1. Generate a file with “good” contents (e.g. well-behaved software), and another file with “bad” contents (e.g. malware).
2. Have people review the good file and give it a good reputation.
3. Distribute the bad file.

This attack can be performed without the distributor being aware, if they're redistributing third-party content (e.g. a picture whose bad version triggers an exploit in an image viewer).

The state of the art of cryptographic hash functions is the SHA-2 family (generally SHA-256 or SHA-512). (There are a few alternatives but they don't get used much in the real world as of 2017.) Cryptographic hash functions are designed for speed, and there is no meaningful difference between MD5 and SHA-256 in practice in most scenarios — I/O is usually the limiting factor, not computation.

Password hashes are a different kind of function (closely related to key stretching) which are used in a specific case: when the data to be hashed has to be secret and cannot be encrypted (in the case of a password, the objective is to make the password hard to guess even if the adversary obtains all the information that the legitimate verifier has, including any encryption keys). Password hashes need to be slow to limit the impact of brute force guess attempts. Hashes used in other scenarios don't need this and are designed for speed.

A cryptographic hash function is a way to expand integrity. Assuming the integrity of the channel through which you obtain the hash, you get a guarantee of integrity of the hashed data.

A hash does not guarantee authenticity: it doesn't say who made this file. Anybody can calculate the hash of a file. To know that the file is authentic, you need to trust the authenticity of the channel through which you receive the hash.

### Malicious corruption: many-files scenario

There is another useful cryptographic primitive that is useful to distribute files: signatures. Where a hash propagates integrity, a signature propagates authenticity. Suppose you have a *public key* distributed through a secure channel (as in, a channel that guarantees the authenticity of the data, i.e. you know who the public key came from, and that it wasn't corrupted in transit). Then you can retrieve a signed file distributed through an insecure channel, and verify whether it has a correct signature. Whereas anybody can calculate the hash of a file, generating a valid signature requires the knowledge of the private key that is associated of a public key.

A signature allows distributing a single datum through the secure channel (the public key) and many large files through the insecure channel. In particular, if the distributor wants to distribute a new file, they can sign it and they don't have to update anything through the secure channel. So the secure channel can be offline, e.g. an operating system image.

The next level after signatures is signatures of signatures. For a file distribution mechanism, signatures introduce a bottleneck: the holder of the private key has to sign all the files. A mechanism where one entity signs other entities' public keys is called a public key infrastructure.

Note that signatures ensure that correctly-signed data is genuine, but they do not assure *freshness* — they do not protect against attacks such as replay attacks. The correctness of a signature is a mathematical property and does not decay in time. An attacker could, for example, hide a security update by continuing to distribute the old, vulnerable version of some software, even after a fix has been published. Protecting against such attacks requires verifying the freshness of a file via a secure channel (here, the security properties required from the channel are freshness and authenticity). This doesn't have to involve cryptography (beyond any cryptography that might be involved in the secure channel), it can be a simple check of a version number or publication date.
> 2 votes

# Answer
MD5 is still in use today mostly due to historic reasons, but there's no need to replace it just yet in domains where collisions aren't a big deal and/or are extremely unlikely. In security applications/protocols, SHA-2 is the go-to hash function family. The extra security comes at the cost of performance, which explains why MD5 is still widespread as it is much prefered to compute the checksum quickly for applications such as package corruption detection.

This thread is a pretty good resource.
> 1 votes

---
Tags: computer-networks, hash
---


# Question
Title: Consutrcting a transition diagram of a deterministic Turing machine
I'm having some issues constructing a transition diagram of a deterministic Turing machine for $L = \\{0^i1^j2^j3^k \ | \ i = j + k\\}$

The point where I get stuck is how I should make sure that $i = j + k$

**My thoughts:**

My thought was to initially do something similar to do something including an addition turing machine where I check that the final tape is of the structure generated by the language i.e we should have 2 $0$s, 1 $1$, 1 $2$ and 3 $1$s = 6 and if it is correct then we'd go through checking if $0$s come before $1$s, $2$s before $1$s and $3$s before $2$s.

I think this is a really complicated way to do it, and that's why I'm asking.

**Question:** Construct a transition diagram of a deterministic Turing machine for $L = \\{0^i1^j2^j3^k \ | \ i = j + k\\}$. What I'm asking is for some guidance.

Thanks in advance!

# Answer
This is meant to give you a hint, but if you are lost, you could think about doing it in three large steps:

1. Make a single pass through, making sure that you encounter $0$s followed by $1$s followed by $2$s followed by $3$s. You should think through the end conditions if this process goes smoothly, or what items you might encounter on the tape that could send you to a reject state.
2. Now check that there are the same number of $1$s and $2$s: go back and find the start of the $1$s. For every $1$, replace it with an $i$, run off to the right and find a corresponding $2$ (which you must also replace with some symbol, such as $T$). Again, think through the end conditions, and how you will know if something unexpected has happened.
3. Finally, check if $i=j+k$. Run to the beginning of the $0$s, and for every $0$ you replacing (with, say, $o$), run off and find the next $T$ or $3$ and replace that with some other symbol ($F$?). At the end, a pass left will be sufficient to tell you that there are no more $0$s, and a pass right will be sufficient to tell you that there are no remaining $T$s or $3$s.
> 1 votes

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


title: The meaning of symbols

text:
# Question
Title: The meaning of symbols
What does the following symbols or expression mean?

# Answer
$x$ and $y$ are elements of a set $S$. For example, if $S = \\{1, 2, 3\\}$, we can select $x = 1$ and $y = 2$.

EDIT: As pointed out by David below, $\*$ could be multiplication or convolution, it's hard to tell from the context.

$\in$ means 'in', that is, that $x$ and $y$ are in a set. We can write 'x and y are elements of the set $S$ ' in math as:

$x, y \in S$

Again, following my example, that would be $1$ and $2$ are in the set $\\{1, 2, 3\\}$.

$\forall$ is verbalized 'for all'. It means for every element in the set, something is either true or false. For example:

$\forall x \in S, x \< 5$ means that all of the elements in my set $S$ are less than 5.

$I$ is the identity function.

The entire phrase $I: \forall X. X \rightarrow X$

(EDIT: removed example, as it was misleading)

means the identity function preserves the value of the variable $X$. More concretely, $I$ is the function that maps $X$ to itself. For all values of X, the output of the function is X.

Hope that helps!
> 0 votes

---
Tags: discrete-mathematics
---


# Question
Title: Learning rule of multilayer neural networks
Suppose we have a 2-layer neural network completely connected with $d^{(0)}$ input units, $d^{(1)}$ hidden units and $d^{(2)}$ output units. We consider the error function given by $J(w) = \frac{1}{2}\sum\_{k=1}^{d^{(2)}}(t\_k-c\_k)^2$, where the vector $t = (t\_1,\dots,t\_{d^{(2)}})$ represents the labels and $z = (z\_1,\dots,z\_{d^{(2)}})$ represents the values obtained by the network. Suppose that the inputs to the second layer are calculated as $z\_k = \sum\_{j=0}^{d^{(2)}}y\_j w\_{kj}$, where $y$ represents the hidden layer output.

I want to know which are the learning rules between hidden and output layer, and between input and hidden layer, for a given activation function $\theta$.

Based on SGD, the learning rule consists in adding to the weights the gradient ot the error function.

For the first one I have tried this. I need to compute the gradient, so I derive $J(w)$ respect to the weight $w\_{kj}$ and apply the chain rule:

$$\frac{\partial}{\partial w\_{kj}}J(w) = \frac{\partial(\frac{1}{2}(t\_k-z\_k)^2)}{\partial w\_{kj}}=\frac{\partial(\frac{1}{2}(t\_k-z\_k)^2)}{\partial z\_k}\frac{\partial z\_k}{\partial w\_{kj}} = -(t\_k-z\_k) \frac{\partial (y\_jw\_{kj})}{\partial w\_{kj}} $$

But I'm not sure about how to continue. If $y\_j$ is not dependent of the weight $w\_{kj}$, then the derivative turns into $-(t\_k-z\_k)y\_j$, but is this right? Would this be the learning rule for the weights between hidden and output layer?

And for the learning rule between input and hidden layer I don't know how should I start. Any idea would be appreciated. Thanks.

# Answer
Have a look at backpropagation, which is essentially what you're trying to do here. Wikipedia has a good derivation that follows exactly your example. If you're more into blogs (and who isn't?) have a look at this one, which goes through the steps of backprop in detail.

Best of luck!
> 1 votes

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


# Question
Title: How to sort an array $A[1..i..n]$ where $A[i] \in \{1,2,..,n^5 \}$ in $\Theta (n)$ time?
> I need to write a sorting algorithm which will sort an array $A\[1..n\]$, $1 \le i \le n$ such that $A\[i\] \in \\{1,2,..,n^5 \\}$, all numbers are positive integers in $\Theta (n)$ time.

The solution **must** use some combination of radix/counting/bucket sort and possibly select algorithm, it can't use any advanced concepts or structures.

I thought of the following:

0) Convert the numbers into base $n$.

1) Count how many digits each number of the array $A$ contains. We know that the number with max amount of digits will be $n^5$. It'll have $\lfloor{\log\_b n^5} \rfloor +1= \lfloor 5\log\_b n \rfloor+1$ digits, where $b$ is the base.Because we changed the base to $n$, there will be $\lfloor 5\log\_n n \rfloor+1 =6$ unique digit lengths. Create an array `countArray` which will contain how many occurrences of tens, hundreds etc are.

2) Create `subArrays` which will contain numbers of the same amount of digits and run radix sort on each such subarray. Radix-Sort runs in $\Theta(d(n+b))$ in general and in our case it will become $\Theta(6(n+n)=\Theta(6n)=\Theta(n)$.

3) In the last step we copy the sorted subarrays into the output array.

Below is the pseudocode but I'm interested if my idea is correct and if the time complexity of my algorithm is $\Theta(n)$:

```
1 MySort(A, n)                    //A is the array, n is array length
2    uniqueDigitsNum <- 5log_n(n) + 1=6
3    init countArray             // the array of length uniqueDigitsNum
4    for i <- 0 to n             //O(n)
5        //B is a helper array which will store how many digits are in a given number
6        countDigits(A[i], B[i])
7        countArray[B[i]]++      //update the count of how many times we see x digits in CountArray
8    // init a 2d array which will contain uniqueDigitsNum subarrays
9    init subArrays of length uniqueDigitsNum
10    for k <- 0 to uniqueDigitsNum  //O(6)
11        init subArrays[k] of length countArray[k]
12    for k <- 0 to uniqueDigitsNum  //O(6n)
13        Radix-Sort(subArrays[k])   //O(countArray[k])
14    //we'll need 'j' to know at which index to start copying the next subarray in the big output array
15    j <- 0
16    for k <- 0 to uniqueDigitsNum  //O(n)
17        for j to countArray[j]     //O(countArray[j])
18            outputArray[j] <- subArrays[k][j]

```

# Answer
1. Radix sort for integers of arbitrary length has $\mathcal{O}(mn)$ time complexity, where m is the length of number.
2. Count digits takes $\mathcal{O}(\log(n))$ time, so, your cycle will take at least (in worst case though) $\mathcal{O}(n \log(n))$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, you need to find complexity of subcycle and multiply them.

Of course, there exists an algorithm that can sort any array of numbers in $\mathcal{O}(n \log(n))$ time and $O(\log(n))$ space.
> 1 votes

---
Tags: algorithms, sorting, radix-sort
---


title: Is vwwx regular language?

text:
# Question
Title: Is vwwx regular language?
I think I understand pumping lemma for regular and context free languages, but there is this one, which I have no idea if it is regular or context free or not context free.

$L = \\{vwwx : v,w,x \in \\{0,1\\}^\* \wedge w\neq \epsilon\\}$ - I think it may be regular, because I think that this is language, which accepts set of all words with $00,11,0101,1010$ substrings. I am sure that $\\{vww^Rx : v,ww,x \in \\{0,1\\}^\* \wedge w\neq \epsilon\\}$ is regular here is proof, because it is set of all strings, with $00$ or $11$ as substring, but without reversing $w$ I am not so sure. I do not understand if idea of "expanding" $v$ and $x$ in $vww^Rx$ as shown in proof (reducing language to language which accepts set of all string with $00$ or $11$ as substring) also applies to $vwwx$. What do you think ?

I would be glad if you could help me with this one.

# Answer
> 2 votes
Let's try to figure out which words are in $L$ and which aren't. If a word $w$ contains 00 or 11 then it is certainly in $L$. Otherwise, it alternates between zeroes and ones. If it contains 0101 or 1010 then it is in $L$. We are left with the words of length at most three, that is $\epsilon,1,0,10,01,101,010$. These are the only words *not* in $L$. Since $L$ is cofinite, it is regular.

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


title: Expected Behavior of FFT

text:
# Question
Title: Expected Behavior of FFT
I am debugging an FFT. My FFT uses complex numbers in polar form, $(r,\theta)$.

I am trying to establish that it works, with a unit test. My real values are all correct, after a polynomial multiplication...

However, I pad out my polynomials to a power of two with complex zeros, and when the multiplication is complete, I have random angle values in the polar form of the complex numbers.

For instance, I multiply the following polynomials, listed in standard form by their coefficients:

$$ A = \lbrace1,2,3\rbrace\\ B = \lbrace4,5,6\rbrace\\ $$

And I am expecting the answer to be: $$ C = \lbrace (4,0),(13,0),(28,0),(27,0),(18,0),(0,0),(0,0),(0,0)\rbrace $$

However, my FFT returns this exactly (ignoring floating point errors), except the last three terms are:

$$ C = \lbrace \ldots,(0,4.518),(0,0.4769),(0,2.2877)\rbrace $$

---

My question is whether these angle values in the extra terms are expected, or whether this is a sign of something going wrong in my FFT code?

(this is tricky for me, because it seems like everything is calculating correctly; and shouldn't it not work at all in a d&c if something is wrong?)

# Answer
Zero-padding is used to compute longer FFT, in your case the signal is padded to be power of 2. In fact, there is no need to do so, there are FFT available using different lengths (also prime ones).

The zero-padding does not introduce new data, does not change sampling frequency of the original signal, it just interpolates the values. In your example there are 5 points, padding them to 8 introduces additional result bins that are closer to each other - this makes particular frequency bin shift, which is stored in the phase component of the result.

So the most probably your FFT is fine, just the test changes the distance between frequency bins, but this step is not included in reading phase, so the test is faulty.
> 3 votes

# Answer
In polar coordinates, $(0,x) = (0,y)$ for any $x$ and $y$, so there's no issue. You've simply used a representation that has multiple representations of the complex number $0 + 0i$.

Going beyond your question a bit, I'd probably test (additionally) with randomized testing of properties of the Fourier transform such as linearity, Parseval's theorem, and the shift theorem. Technically, linearity, the shift theorem, and the impulse response would completely characterize the Fourier transform.
> 3 votes

---
Tags: fourier-transform
---


# Question
Title: Major Field Test Sample Questions (need further clarification)
I have several questions that do no make sense for me.

**First Question:** A stack can be implemented with an array A\[0..N-1\] and a variable pos. The push and pop operations are defined by the following code.

```
push (x)
  A[pos] <- x
  pos <- pos – 1
end push

pop ( )
  pos <- pos + 1
  return A[pos]
end pop

```

Which of the the following will initialize an empty stack with capacity N for this implementation?

a)pos \<- -1

b)pos \<- 0

c)pos \<- 1

d)pos \<- N - 1

e)pos \<- N

I have zero idea for this question and I dont understand what is being asked

**Second Question:** Consider the following recursive function

```
int Fun ( int n )
if ( n == 4 )
  return 2
 else
  return 2 * Fun ( n + 1 )
 end if
end Fun

```

What is the value returned by the function call Fun(2)?

a)2

b)4

c)8

d)16

e)24

The answer is **C** but I got 6 cox this is how I did it, because n is 2 and it not 4 so it return 2 * (2+1) which is equal to 6

**Third Question:** Following is a definition of a widget and a declaration of an array A that contains 10 widgets. The size of a byte, short, int, and long are 1,2,4 and 8 bytes, respectively. Alignment is restricted so that an n-byte field must be located at an address divisible by n. Th fields in a struct are not rearranged padding is used to ensure alignment. All widgets in A must have the same size

```
struct widget
  short s
  byte b
  long l
  int i
end widget

widget A[10]

```

Assuming that A is located at a memory address divisible by 8, what is the total size of A, in bytes?

a)150

b)160

c)200

d)240

e)320

The answer is **D** but I dont understand why is it D and not C.

# Answer
I will try my best to explain the **first** question.

They are basically asking what value **pos** need to be in order for the stack to be empty. Since we are using an **array** as a stack, we have a choice between **0** or **N-1**. Looking at the code, **Pop increment** **pos** and **push decrement pos**. We want to follow pop because it pops the first element and so on to the last element. If we pop all elements in the array it will equal N-1 values. The answer should be **D**.
> 2 votes

---
Tags: algorithms
---


# Question
Title: PSPACE-complete problems can't be in NL using the space hierarchy theorem?
I want to prove that no PSPACE-complete problem is in NL using the space hierarchy theorem. What I want to say is this : From the time hierarchy theorem I know that for every $t(n)$ there exists a language that is decidable in $O(t(n))$ space but not in $o(t(n))$ space. Then I want to assume that there exists $A \in PSPACE\text{-complete} \land A \in NL$ and take a language $L$ that is decidable in $O(n)$ time but not $o(n)$ time, reduce it to $A$, reduce it to $PATH$ and get that through that reduction $L$ is decidable in $\Theta (log(n)^2)$ time, a contradiction.

However my reasoning fails in that the reduction from $L$ to $A$ isn't necessarily a log-space reduction. What am I missing? How do I overcome this?

# Answer
> 2 votes
Use Savitch's theorem, which shows that PSPACE=NPSPACE, and the non-deterministic space hierarchy theorem.

Alternative (suggested by OP): use Savitch's theorem to show that $\mathsf{NL} \subseteq \mathsf{SPACE}(\log^2 n)$, and then the deterministic space hierarchy theorem.

# Answer
> 5 votes
This question is currently open, since a positive answer (i.e. no complete problems for PSPACE can lie in NL) would imply $\mathsf{P}\neq\mathsf{PSPACE}$. This statement is actually equivalent to $\mathsf{P}\neq\mathsf{PSPACE}$ (as a PSPACE complete problem in NL obviously implies P=PSPACE).

Examine the equivalent statement, that $\mathsf{P}=\mathsf{PSPACE}$ implies there exists a PSPACE complete problem in NL. To see why this holds, note that if $\mathsf{P}=\mathsf{PSPACE}$ then every non trivial language $L\in\mathsf{PSPACE}$ (i.e. $L\neq \emptyset,\Sigma^\*$) is complete for PSPACE. Now let $L$ be some non trivial language in NL (which is a subset of PSPACE), then $L$ is a PSPACE complete problem which lies in NL.

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


# Question
Title: Context free grammar for $bin(n)bin(n+1)^R$
It is pretty hard for me to understand, how binary representation of number may be context free. This language $L=\\{bin(n)bin(n+1)^R : n \geq 0\\}$ is context free.

Here, at 1.b, is a PDA which describes this language, so it is context free. I've tried to construct a context free grammar for this one, but I have no idea when to even start. How can I express a CFG binary representation of a number? I would be very glad for any suggestions.

# Answer
Here is one solution: $$ \begin{align\*} &S \to 01 \mid 1A1 \mid 1B1 \\ &A \to 1A0 \mid 0 \\ &B \to 1B1 \mid 0B0 \mid 0C1 \\ &C \to 1C0 \mid \epsilon \end{align\*} $$

Explanation:

* $A$ generates $1^n 0^{n+1}$, and so $1A1$ generates $1^{n+1} 0^{n+1}1$, which handles numbers whose binary expansion is $1^{n+1}$.
* $C$ generates $1^n 0^n$, and so $0C1$ generates $01^n 0^n1$.
* $B$ generates $w01^n0^n1w^R$, and so $1B1$ generates $1w01^n0^n1w^R1$, which handles numbers whose binary expansion is $1w01^n$.
* Finally, $01$ handles $0$.
> 2 votes

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


# Question
Title: Space-unconstructable function in the proof of Savitch's theorem
I'm learning about the Savitch's theorem, and while the construction proof is straightforward, I still don't understand one part about it.

The proof I'm talking about is the same as is currently on Wikipedia. It starts by describing a function - let's call it `CAN_YIELD(start, end, limit)` for now.

It is then said that the non-deterministic Turing Machine can be simulated by a deterministic Turing Machine by calling `CAN_YIELD(start_state, end_state, f(n))`.

The proof then continues by describing that the function takes `O(f(n))` space for one configuration and `O(f(n))` for the recursion of the function. This nicely results in `O(f(n)^2)` which is the result we want.

The issue is that if the `f(n)` is not space-constructible, we don't know what limit number we should input into the `CAN_YIELD` function. I've seen some proofs saying that we can add something like a 'size' parameter and check if it is large enough - but again, we don't know the actual `f(n)` value, so I don't understand how this works.

One example of such proof can be found here. Another instance is this answer that states that we can replace the space-constructability requirement of the function by using a fixed space bound, which we increase after every iteration. Same issue as before, I don't see how that might work without knowing when to stop.

I'd be happy for any insight into this issue, or any corrections made to my statements!

# Answer
> 1 votes
Starting Point:        For inputs x, if    \[there is no sequence of choices
which makes the non-deterministic machine accept x\]  and
\[for all positive integers S, there is a sequence of non-deterministic choices that,
when made for input x, will cause the non-deterministic machine to use more than S space\]
then on input x, the deterministic machine is allowed
to run forever with no bound on its space usage.

Otherwise, such simulation would suffice for solving the halting problem:
Run the simulator until it halts or loops, then output accordingly.
With that in mind, the simulation works as follows:

```
S = 1
while True:
    run CAN_YIELD with space-bound S
    if that accepts then accept
    increase S by 1
    for end_state in configurations_at_which_the_nondeterministic_machine_might_have_just_used_more_than_space_(S):
        run CAN_YIELD with space-bound S and end_state
        if that accepts then break out of the for loop
    if the for loop ended without a break then REJECT

```

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


title: How can memory size be 1M x 16?

text:
# Question
Title: How can memory size be 1M x 16?
1M = 2^20, while the max number of memory locations for 16 bits is 2^16. How could there be a memory size of 1M x 16? Or can there? Wondering about this for a question we were given..

# Answer
> 2 votes
It seems that a bunch of different things are being conflated here:

1. Bits in an addressable memory location - 16 in this example.
2. Addressable memory locations - 1M = 2^20 in this example.
3. CPU word size

These can all be the same, or they can be entirely different. I will try to explain the differences:

1 - Bits in an addressable word. This can be ANYTHING. Typically this will be the same as the CPU word size - e.g., 32-bits for a 32-bit processor. However, it can be larger (e.g., direct access to a "double word") or smaller (e.g., individual byte access for a CPU that has a 16-bit or larger word size). On some CPUs there will be different instructions that use different size operands and addressing schemes - e.g., floating point instructions might work only on 32-bit ("single word") or 64-bit ("double word") memory locations but other instructions might work with individual bytes. In some designs, every byte can be addressed and accessed directly but 16-bit words only on even addresses (or 32-bit only on addresses divisible by 4).

2 - Addressable memory locations. Historically this was often double the addressable memory location size. For example, a typical 8-bit CPU such as the Z80 or 6502 could directly address 64k = 2^16 memory locations. However, there are quite a few variations. One significant one is a segmented memory addressing scheme such as that used by the 8086 family. This is one method of expanding the *total* addressable memory while keeping the addresses directly used by most instructions to a smaller size (16-bit in the case of the 8086). While there is some logic to keeping the address size (=# of addressable memory locations) the same as the CPU word size, in many (most?) CPU architectures that was simply not practical in many cases until we arrived at the era of affordable 64-bit CPUs.

3 - CPU word size. The CPU word size normally refers to the standard chunks of memory operated on and produced as results by individual CPU instructions. Another way of looking at it is the register size. However, there have been exceptions here as well. For example, the 8-bit 8080 has 7 8-bit registers and 2 16-bit registers (SP and PC - both needed to be 16-bit to match the memory address size) and some of the 8-bit registers could be used in pairs for operations that really operated on 16 bit values. Similarly, many 16-bit CPUs have some instructions that operate on 32-bit quantities either for floating point arithmetic or again for memory addressing.

Now that I've rambled on a bit (pun intended), back to the original question: **1M = 2^20, while the max number of memory locations for 16 bits is 2^16. How could there be a memory size of 1M x 16?** A few possibilities come to mind:

1. 16-bit CPU with memory locations 16-bits wide and a 20-bit segmented architecture like the 8086. (But not actually the 8086 as the 8086 address space was 1M x 8)
2. 16-bit CPU with a 20-bit or larger (typically 31-bit or 32-bit) total word-addressable memory with the 1M being just a small portion of the potential addressable memory for that particular CPU.
3. 16-bit CPU with 21-bit or larger (typically 31-bit or 32-bit) total byte-addressable memory with the 1M just being a small portion of the potential addressable memory for that particular CPU.
4. 32-bit CPU with memory addressable in 16-bit words (i.e., 1/2 the native CPU word size) for better performance with instructions that don't need 32-bit words.

In case it isn't already clear, the CPU word size historically directly translated to the number of pins available for reading/writing memory. So an 8-bit CPU could interface with memory 8-bits at a time and a 16-bit CPU 16-bits at a time. That all changed famously with the 8088 which internally was a 16-bit CPU but externally only 8-bits. So while the 8086 could directly use 16-bit wide memory like the example 1M x 16, the 8088 could not. That difference gives the 8088 performance that is in some ways closer to an 8-bit CPU than a 16-bit CPU.

# Answer
> 0 votes
Well, just consider the common 4Gx8 memory size. That's 4 billion octets. How's that possible? Simple: a unique address takes 4 octets. Now you can figure out how many 16-bit words you need for an address in your system.

# Answer
> 0 votes
You are looking at a memory chip here. 1M x 16 has $2^{20}$ addressable units, and each unit is 16 bits in size. Computers often use more than one memory chip. You could buy four such chips and combine them to get something that works as if you had a 1M x 64 chip. Or a 2M x 32 chip. Or a 4M x 16 chip.

The number of bits that a single memory chip stores in one addressable unit is completely unrelated to what the processor does. And "word size" is quite unrelated to the design of the memory chips. A typical modern computer transfers data between memory and processor one cache line (512 bits) at a time, not one word at a time.

---
Tags: computer-architecture
---


# Question
Title: Nodes reached with exactly $k$ steps in an undirected graph?
Given an undirected graph $G$ of $N$ nodes and a starting node $s$, I want to build, with dynamic programming, a table whose $(k, n)$-th entry is $1$ if node $n$ is reachable with **exactly** $k$ steps from node $s$.

Specifically, for the first row of the table, I set $(1, n)$ to 1 if node $n$ is connected to node $s$. Then for the second row, I set $(2, n)$ to 1 if node $n$ is connected to any of the nodes who have value $1$ in the first row. I can stop the construction whenever I have a repeated row. In other words, I want to build the table to the point where more rows will be redundant, as there are already exact copies of them up in the table. So $k$ should be expressed in terms of $N$.

I want to check if this table construction can be done in polynomial time. I think it boils down to whether the number of rows is polynomially bounded. Is it so?

My intuition is yes, because in the worst case, where the $N$ nodes are serially connected one next to another, and starting node $s$ is at one end, I can still reach the other end with $N-1$ steps.

# Answer
> 2 votes
There is an easier way than dynamic programming. You can compute the adjacency matrix to the power of $k \in \mathbb{N}$. Let $m$ be your adjacency matrix. Then $m^k$ contains also paths of the length $k$. All other entries would be zero.

The runtime would be (because of only matrix multiplication): $\mathcal{O}(n^3)$

# Answer
> 0 votes
Yes, your algorithm will run in polynomial time.

I'll offer a sketch of a proof. Let's assume for simplicity that your graph is connected; otherwise just take the connected component of your graph that contains node s. Now, let d be the maximum distance between s and any other node of the graph. There are two cases to consider: if the graph is bipartite or not.

If the graph is bipartite, then reaching a node in exactly k steps is equivalent to the node having a minimum distance of any number less than or equal to k but with the same parity modulo 2. Thus rows d and d+2 are the same, so the number of rows is bounded by V+1.

If not bipartite, then there must be an odd cycle. Consider a rooted spanning tree T of the graph, and call a node's *depth* its distance to the root. An odd cycle implies that there must be an outside connection between nodes of depth that are either both odd or both even in the spanning tree.

From now on we'll work in the subgraph that consists of T and this outside connection. Starting from any node x, after 50V steps, it's possible to reach every node that has depth the same parity as x. Therefore after 50V+2 steps, you can take the outside connection as a kind of "bridge," meaning that at least one vertex of opposite parity can be reached. Add another 50V steps and the entire graph can be reached, so the 100V+2 and 100V+3 step must both be identical (all 1's in the matrix).

EDIT: Just to clarify, 50 was an arbitrary number here. 2V or even V-(V%2) would also have sufficed.

Note that if you just wanted to build a table such that (k, n)-th entry is true if the *minimum* number of steps to reach n is k, then the algorithm you are looking for is Breadth-First Search, which is an optimal O(E) time.

---
Tags: graphs
---


# Question
Title: How can I explain lossless compression to a misguided audio engineer?
I have recently been involved in a discussion with someone who doesn't accept that lossless compression is possible, even in principle. This person considers himself to be technically literate, and an expert in his field of audio engineering.

I and several others have patiently tried to explain how lossless compression is possible, using simple examples such as run-length encoding and delta encoding, but he refuses to believe that it's possible for a lossless audio codec such as FLAC, for example, to exactly reproduce the input bitstream from the raw PCM data.

His response is always along the lines of:

> it's getting smaller, so it must be losing data
>
> "lossless" is just a buzzword used by software companies to sell their software, it doesn't actually mean lossless

Are there any other examples I can use to demonstrate conclusively that lossless compression is actually possible?

# Answer
> 12 votes
Tell him to write out the integers between 1 and 100, inclusive. Ask him how it can be that your instruction was so much shorter than the list of numbers he wrote out. Did that brevity cause him to write out the wrong thing?

# Answer
> 2 votes
You're explaining the wrong way - explain the opposite way. Take the original data, and write each bit twice, i.e. 0101 --\> 00110011. Now the output is twice the size but still carries the exact same amount of information. Yes, n bits can represent 2^n unique values. But a specific value can be encoded in an infinite number of ways, some smaller than others. Maybe try referring him to capacity and to Kolmogorov complexity

# Answer
> 1 votes
Ask him to write a large matrix of floating point data into a text file with as many digits as there is precision. Then ask him to store the same data in a binary file format. Make note of the difference in file sizes.

Finally, ask him how it is possible to store the same matrix data in two files with drastically different storage footprints?

# Answer
> 1 votes
It's true that we're encoding a bit string $Y$ with some shorter bit string $X$, but we are not losing any information, because we're going to encode $X$ with some possibly *longer* bit string $Z$. On the average we won't gain anything, but our procedure works so that the bit strings that we *typically* see in practice get shorter during compression, and those that we do not see in practice get longer (but nobody cares about them).

# Answer
> 0 votes
A CD stores sounds as volume levels from -32768 to 32767. You need 16 bits for each volume level.

Instead of the volume level, store the difference from one sample to the next. Take a 440 Hz sound. The differences from one sample to the next are much smaller than the original levels and can be stored in less space.

---
Tags: data-compression, education
---


title: Distance-preserving permutations

text:
# Question
Title: Distance-preserving permutations
In the scope of my scheduling research, the question has been raised on whether distance-preserving permutations can be constructed easily.

Suppose that our domain is the set of natural numbers up until $n$, that is: $D=\\{1,2,...,n\\}$ where $n\geq 1$.

A permutation $\pi$ is a distance-preserving permutation in my context is one that has the following property: $|\pi(i) - \pi(j)| = |i-j|$.

For example, the most trivial distance-preserving permutation I have come up with is the following: $\pi(i) = n-i+1$, which is the permutation that maps $1$ to $n$, $2$ to $n-1$, etc. It can be easily shown that $|\pi(i) - \pi(j)| = |i-j|$.

My intuition says that there are no more distance-preserving permutations, since if we draw this as a graph where the $x$-axis is the numbers in $D$ and the $y$-axis is the values $\pi(i)$ then we will have a $90$-degree cornered triangle with the corner facing north-east, its' equal edges being the distances $|i-j|$ and $|\pi(i) - \pi(j)|$.

Are there distance-preserving permutations other than the above trivial one?

# Answer
The only permutations who satisfy this condition are the identity and its inverse (as string inverse), $\pi(i)=n-i+1$.

Note that $1$ has to be in one of the edges (if it has two neighbors, then at least one of them is bigger than $2$ and the condition is not satisfied). Placing $1$ in the left edge forces the entire permutation to be the identity, and placing $1$ in the right edge forces the permutation to be its inverse.
> 8 votes

---
Tags: permutations
---


title: Colored cliques complexity

text:
# Question
Title: Colored cliques complexity
Given:

1. graph with colored edges;
2. list of $\alpha$ colors;
3. list of $\epsilon$ colors;
4. clique size $k$.

Problem:

1. Do all edges colored in one of $\alpha$ colors are members of cliques with size $k$?
2. Isn't there an edge of some of $\epsilon$ color that is not contained in clique of size $k$?

**Example:**

Given some graph that has blue, red, green and magenta edges.

$\alpha$ colors: red, blue.

$\epsilon$ colors: green, magenta.

Answer is yes if both conditions are satisfied:

1. All red and blue edges are contained in cliques of size $k$ (or larger, of course).
2. There exists at least one green **and** at least one magenta edges that are contained in some cliques of size $k$.

Here are 2 special cases, for both $n = 10, k = 4, \alpha$: red and blue, $\epsilon$ - green and magenta. The only difference is color of edge BE.

1st graph satisfies the conditions: all red and blue edges are contained in 4-vertex cliques ABIH, FGIJ, CDEF as well as they contain at least one green and at least one magenta edge.

2nd graph doesn't satisfy the conditions because blue edge BE is not a member of 4-vertex clique.

I think this problem is PSPACE-complete but I'm not sure about reduction from TQBF to this. If such reduction is possible, it is not similar to known SAT to max-clique reduction.

# Answer
Your problem is in NP. (A certificate for a "yes" answer is to list one of the $k$-cliques that each edge is contained in.) Therefore, it's not likely to be PSPACE-complete: if it were PSPACE-complete, that would imply NP = PSPACE, which would be surprising.

Your problem is NP-complete. It is at least as hard as the $k$-clique problem. Suppose we have a graph and we want to know whether it contains a $k$-clique. Then we can color all edges green, let $\alpha$ be the empty list, and let $\epsilon$ be the list containing only the color green. Now the graph has a $k$-clique if and only if the answer to your problem is yes. But testing for a $k$-clique is NP-complete, so it follows that your problem is NP-complete too.
> 0 votes

---
Tags: complexity-theory, graphs, clique
---


title: Serial communication and parity bit

text:
# Question
Title: Serial communication and parity bit
I was revising Computer Science and I got these two doubts to which I've found contradictory answers on Google:

1. In a serial communication which bit is sent first?
2. When using a parity bit with ASCII is it set on the LSB or MSB?

Logically thinking I thought the answers should be 1- MSB first and 2 - set on LSB. Am I right?

Thanks in advance.

Gabriele

# Answer
> 3 votes
You may find contradictory answers because there are many kinds of serial communication protocols. Some are LSB first, some are MSB first.

For example, for the old RS232 standard and siblings, the LSB is transmitted first, and the parity may be transmitted after MSB. The MSB is usually the 7th bit or the 8th bit. The parity is not part of the source data and is not weighted, so this is not really a MSB.

Another serial protocol, CAN, used in many automotive or other embedded applications, uses MSB first.

Some have more complex interpretations, mixing LSB- and MSB- first for data and CRC, mixing the order of bytes and the transmission order of bits. Example : IP over Ethernet : Big endian data, LSB-first bits, reversed CRC.

---
Tags: communication-protocols
---


# Question
Title: Does this classify as Information retrieval?
I’m trying to figure out if what I’m doing would classify as Information Retrieval. According to this Thread:

> **Information retrieval** is **based on a query** \- you specify what information you need and it is returned in human understandable form.

I’ve a script that reads unstructured text (titles of books) and extracts names (which I gathered in a list beforehand) from the titles and outputs a CSV with all matched names. Would that be a simple use case of Information Retrieval or is this called „tagging“? If both not, what would one call this technique?

Thanks for your help!

# Answer
> 1 votes
You could consider that a form of information retrieval, if you want. It sounds like keyword matching, so not one of the more sophisticated forms of information retrieval, but sometimes the simplest solutions are the best.

I wouldn't worry too much about the name. There's no strict, hard-and-fast definition of exactly what counts and what doesn't. The term serves as an aid for communication, and to my way of thinking, it sounds fine to consider what you are doing as a form of information retrieval.

---
Tags: information-retrieval
---


# Question
Title: Contamination in Atomic Broadcast in crash stop failure model
I'm reading several papers about different broadcast algorithms. Most of them are designed for crash stop model but they also consider **contamination** scenarios.

> For example for a **Causal Atomic Broadcast** when a faulty process fails to delivers messages in order and then starts broadcasting other messages based on its inconsistent state which causes inconsistent state in other correct processes.

The above is just an example why a specific process could have such a weird behavior although our failure model is crash stop. Follwoing paper describes it more.

> A Modular Approach to Fault-tolerant Broadcasts and Related Problems. V. Hadzilacos and S. Toueg, Distributed Systems, 97-145, 1993.

See here section 3.11 (page 22) for more sophisticated example. This is really confusing to me. Why do we don't consider this type of failure as byzantine failures? In crash stop model a single failure should result in a crash. A faulty process can **NOT** continue to run without crashing. What am I missing?

# Answer
I think you are confusing the *failure model* with the *correctness goals* of a protocol.

* A *failure model* specifies what kinds of things can go wrong (i.e., what kinds of failures the protocol is designed to deal with and promises to be able to handle).
* A *correctness goal* describes what properties the protocol promises to provide (i.e., what properties it needs to achieve, to qualify as correct).

We then analyze whether a particular protocol meets a particular correctness goal in a particular failure model. For example, protocol might achieve the correctness goal in one failure model but not in another.

Example of failure models include crash-only; or Byzantine failures; or others. See Sections 2.3 and 2.6 for examples of kinds of failures. A failure model would specify which of those failures are in scope (and thus, implicitly, which are out of scope).

An example of a correctness goal is "Causal Broadcast" or "Atomic Broadcast" or "Causal Atomic Broadcast". For instance, the correctness goal that we call "Causal Broadcast" is that the protocol must ensure Causal Order for all delivered messages (see Section 3.3 of the paper you mention). There might be a protocol that achieves Causal Order in the presence of crashes but not in the presence of Byzantine failures.

With that understanding, Section 3.11 of your paper starts out with an example of a failure that can be problematic. That's a type of failure that isn't just a crash. Yes, it could be considered an instance of a Byzantine failure. However, it is also a more specific type of failure; one can articulate a more specific failure model that is more constrained than arbitrary Byzantine failures, but broader than just crashes, and which includes that failure as the sort of failure that can occur. It may be useful to think about what is achievable in that intermediate failure model. There are more failure models in the world than just "crash stop" and "Byzantine".
> 2 votes

---
Tags: distributed-systems
---


title: Approximation of a gaussian function

text:
# Question
Title: Approximation of a gaussian function
I want to approximate a Gaussian function as shown below $$ e^{\frac{-\\|x-c\\|^2}{2\sigma^2}} \approx \sum\_{i=1}^{N}\alpha(c,c\_i)e^{\frac{-\\|x-c\_i\\|^2}{2\sigma^2}} \forall x $$ Here c, $\sigma$ and $c\_i$ are known. Are there functions $\alpha(c,c\_i)$ which gives a good approximation? The limitation I am facing is that I can not optimize as I have to calculate the functions $\alpha$ for various c(around 1024\*1024) thus leading to too many optimizations. I used linear solver as this optimisation problem can be framed as $A\alpha=b$. Here $x$ in the above equation is sampled according to each $c$. Hence for every $c$, both $A$ and $b$ in $A\alpha = b$ changes.

I am also fine if functions in RHS are not Gaussians i.e existence of pair of $\alpha$ and $f\_\sigma$ such as

$$ e^{\frac{-\\|x-c\\|^2}{2\sigma^2}} \approx \sum\_{i=1}^{N}\alpha(c,c\_i) {f\_\sigma}(x,c\_i) \forall x $$

Can someone help me to point out how to go about it? Here N can be treated as a variable. So as N increases number of gaussians used to interpolate increases and hence get a better approximation.

Now to explain what I meant by a good approximation : The function in LHS is used as a filtering kernel to filter my data. Replacing it with RHS (one part of my algorithm) will help in speeding up my filtering algorithm by a huge margin. Now I check my performance by comparing actual filtering algorithm and this approximation by using parameters such as Mean Square Error.

# Answer
> 1 votes
One approach could be to use least-squares fitting.

Your problem is: given functions $f\_1,\dots,f\_N$ and $f$, we want to find constants $\alpha\_1,\dots,\alpha\_N$ such that

$$f(x) \approx \sum\_i \alpha\_i f\_i(x).$$

Here

$$f(x) = e^{\frac{-\\|x-c\\|^2}{2\sigma^2}}$$

and

$$f\_i(x) = e^{\frac{-\\|x-c\_i\\|^2}{2\sigma^2}}.$$

To make this problem well-defined, we need to make precise the notion of approximation. One plausible notion is the $L\_2$ error of the approximation, i.e., the error is

$$E = \int \big( f(x) - \sum\_i \alpha\_i f\_i(x) \big)^2 \\; dx.$$

This is tricky to compute, but we can approximate $E$ by picking values $x\_1,\dots,x\_m$ and then calculating

$$\hat{E} = \sum\_j \big( f(x\_j) - \sum\_i \alpha\_i f\_i(x\_j) \big)^2.$$

If the $x\_j$'s are chosen appropriately (e.g., evenly spaced over the range you care about; or randomly chosen according to the distribution of $x$-values you're likely to evaluate the approximation at), and if $m$ is large enough, then $\hat{E}$ should be a good approximation to $E$.

So, the problem becomes: given functions $f\_1,\dots,f\_N$ and $f$ and values $x\_1,\dots,x\_m$, we want to find constants $\alpha\_1,\dots,\alpha\_N$ that minimize the error $\hat{E}$.

This turns out to be exactly a multiple linear regression problem. We try to find a fit

$$z = \alpha\_1 y\_1 + \dots + \alpha\_N y\_N$$

where $y\_i = f\_i(x)$ and $z = f(x)$. We can evaluate the $f\_i$'s and $f$ at any input $x$ of our choice. When we evaluate at $x\_j$, we obtain a single input $(y\_1,\dots,y\_N)$ and a single output $z$; in this way, we obtain $m$ matching input-output pairs. You can now use a standard library to solve this multiple linear regression problem and find $\alpha\_1,\dots,\alpha\_N$.

All that remains is to choose $m$ and $x\_1,\dots,x\_m$. I would suggest that you try to figure out what values you'll evaluate the approximation on, and choose the $x\_j$'s randomly from the distribution (it might be a uniform distribution over some range, or something else), or choose the $x\_j$'s to be evenly spaced over some range. The larger $m$ is, the better the approximation will be, but the longer the algorithm will take, so experiment with some different values of $m$ and see what the tradeoff is. My guess is you'll want $m$ to be a small constant multiple of $N$ (say $m=2N$), but you can see what you get.

Since you said $N$ is small (8--16), this should be very fast.

An optimization: Since you're going to repeat this many times with the same values for $c\_1,\dots,c\_N$ (i.e., $f\_1,\dots,f\_N$) but a different value of $c$ each time, you can also speed things up. If the matrix is $X$ and the vector is $y$, the solution is $(X^\top X)^{-1} X^\top y$, where $X$ depends only on the $c\_i$'s but not on $c$. Thus, you can precompute the matrix $(X^\top X)^{-1} X^\top$ (once), then for each instance of the problem you want to solve, you just have to do a matrix multiplication -- no need to solve a new linear system.

Lastly, one optional refinement you could also try: use multiple linear regression to choose $\alpha\_i$'s, then follow that up with gradient descent to fine-tune the $\alpha\_i$'s and improve the quality of the approximation. Often if you choose a good starting point that is close to optimal, gradient descent will converge faster. Thus you can use the solution from multiple linear regression as the starting point for the gradient descent optimization routine.

---
Tags: complexity-theory, optimization, machine-learning, linear-algebra
---


# Question
Title: Pseudo code algorithm for beauty contestant question
Say beauty pageants are judged based on 3 criteria: 1) Appearance 2) Personality 3) Talent. A contestant $C$ will beat another contestant $C'$ if she gets higher scores in ALL THREE of the criteria.

There are $n$ girls competing. Contestant $C\_i$ is "Model Material" if $C\_i$ is not beat by any other contestant $C\_j$. Pretend you're the announcer and you have a collection of tuples: $(A\_i, P\_i, T\_i)$ for $i = 1, 2,...,n$

The $i$th tuple contains the appearance, personality, and talent rating for $C\_i$ (higher scores are better). Return a list of the "Model Material" contestants in in $O(n\log{n})$ time.

Given a data structure w/ a set $E$ of ints that, given an int $a$, --- (1) tells if a is in $E$ (2) finds smallest value \> $a$ or largest value \< $a$ in $E$ (3) inserts or removes a from $E$ in $O(\log{|E|})$ time.

I am trying to write pseudo-code for this algorithm but am lost trying to think of a correct algorithm that also runs in $O(n\log{n})$ time. I thought about starting initially with the $A\_1$, $P\_1$, and $T\_1$ values for the first contestant, and if another contestant has a higher score in each category, remove the current tuple and replace it with the higher tuple, then repeat this process starting with a different contestant each time, but that's obviously not $O(n\log{n})$, and probably doesn't even work.

(This question was from my algorithms professor, and I can't find it online or in our textbook)

# Answer
You are asking for the Pareto-optimal front in 3D space. This is a well-studied problem.

In 2D, there are $O(n \log n)$ time algorithms: see, e.g., What are some interesting applications of the skyline problem?, An online algorithm to find the Pareto frontier elements, minimum subset of dominating 2D points.

In 3D, life is more complicated, but apparently it is still possible to solve this in $O(n \log n)$ using fancy methods. See the following paper:

On Finding the Maxima of a Set of Vectors. H.T. Kung, F. Luccio, F.P.Preparata. Journal of the ACM, vol 22 no 4, Oct 1975, pp.469--476.
> 1 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis
---


# Question
Title: Approximate subset sum with two-dimensional vectors
Consider the following optimization problem:

> Given $n\leq 10^3$ vectors $v\_i\in\mathbb{R}^2$, all of which are small, i.e., $\\|v\_i\\| \leq 1$, find a subset $S$ of them that minimizes $ \\| w + \sum\_{i\in S} v\_i \\|^2$, where $w$ is a fixed known vector.

I know that this can be reduced to an unconstrained 0-1 quadratic program (with unknowns $x\_i\in\\{0,1\\}$, $x\_i=1$ whenever $i\in S$), but that is a hard problem in general.

However, since the constraints are so specific, is there a way to get a reasonably simple efficient approximation algorithm for it? One that doesn't involve integer programming? It's not even clear to me how to efficiently implement a greedy algorithm for it.

Are there special cases of this problem that are easier? For example, would it help if all the vectors were unit length, $\\|v\_i\\|=1$?

# Answer
> 2 votes
Let $\rm V$ be the $2 \times n$ matrix whose $i$-th column is vector $\rm v\_i$. We have the Boolean optimization problem in $\mathrm z \in \\{0,1\\}^n$

$$\min\_{\mathrm z \in \\{0,1\\}^n} \\| \mathrm V \mathrm z + \mathrm w \\|\_2^2$$

Let

$$\rm z = \frac 12 (x + 1\_n)$$

where $\mathrm x \in \\{\pm 1\\}^n$. Hence, we have an instance of the **Boolean least-squares** (BLS) problem

$$\min\_{\mathrm x \in \\{\pm 1\\}^n} \\| \mathrm A \mathrm x - \mathrm b \\|\_2^2$$

where

$$\rm A = \frac 12 V \qquad \qquad \qquad b = - \left( \frac 12 V 1\_n + w \right)$$

Since $\\{\pm 1\\}$ is the solution set of the quadratic equation $x\_i^2 = 1$, we have the following (non-convex) quadratically constrained quadratic program (QCQP) in $\mathrm x \in \mathbb R^n$

$$\begin{array}{ll} \text{minimize} & \\| \mathrm A \mathrm x - \mathrm b \\|\_2^2\\ \text{subject to} & x\_i^2 = 1 \quad \forall i \in \\{1,2,\dots,n\\}\end{array}$$

Exhaustive evaluation of the objective function at all $2^n$ points is only feasible for small $n$.

---

### SDP relaxation

Note that

$$\begin{array}{rl} \\| \mathrm A \mathrm x - \mathrm b \\|\_2^2 &= (\mathrm A \mathrm x - \mathrm b)^{\top} (\mathrm A \mathrm x - \mathrm b)\\ &= \mbox{tr} \left( (\mathrm A \mathrm x - \mathrm b) (\mathrm A \mathrm x - \mathrm b)^{\top} \right)\\ &= \mbox{tr} \left( \begin{bmatrix} \mathrm A & -\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix}^{\top} \begin{bmatrix} \mathrm A & -\mathrm b\end{bmatrix}^{\top} \right)\\ &= \mbox{tr} \left( \begin{bmatrix} \mathrm A^{\top}\\ -\mathrm b^{\top}\end{bmatrix} \begin{bmatrix} \mathrm A & -\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix} \begin{bmatrix} \mathrm x^{\top} & 1\end{bmatrix} \right)\\ &= \mbox{tr} \left( \begin{bmatrix} \\,\\,\\,\\, \mathrm A^{\top} \mathrm A & -\mathrm A^{\top}\mathrm b\\ -\mathrm b^{\top}\mathrm A & \\,\\,\\,\\, \mathrm b^{\top}\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x \mathrm x^{\top} & \mathrm x\\ \mathrm x^{\top} & 1\end{bmatrix} \right)\end{array}$$

Since $\mathrm x \in \\{\pm 1\\}^n$, all $n$ entries on the main diagonal of $\mathrm x \mathrm x^{\top}$ are equal to $1$. Thus,

$$\begin{bmatrix} \mathrm x \mathrm x^{\top} & \mathrm x\\ \mathrm x^{\top} & 1\end{bmatrix}$$

is symmetric, positive semidefinite and has only ones on its main diagonal, i.e., it is a *correlation* matrix. Its rank is $1$. Let

$$\mathrm C := \begin{bmatrix} \\,\\,\\,\\, \mathrm A^{\top} \mathrm A & -\mathrm A^{\top}\mathrm b\\ -\mathrm b^{\top}\mathrm A & \\,\\,\\,\\, \mathrm b^{\top}\mathrm b\end{bmatrix}$$

Hence, the BLS problem can be written as the following *rank-constrained* optimization problem in $(n+1) \times (n+1)$ symmetric matrix $\rm Y$

$$\begin{array}{ll} \text{minimize} & \langle \mathrm C , \mathrm Y \rangle\\ \text{subject to} & y\_{ii} = 1, \quad \forall i \in \\{1,2,\dots,n+1\\}\\ & \mathrm Y \succeq \mathrm O\_{n+1}\\ & \mbox{rank} (\mathrm Y) = 1\end{array}$$

which is a hard problem due to the rank constraint. *Relaxing* the optimization problem above by discarding the rank constraint, we then obtain the following **semidefinite program** (SDP) in $\rm Y$

$$\boxed{\begin{array}{ll} \text{minimize} & \langle \mathrm C , \mathrm Y \rangle\\ \text{subject to} & y\_{ii} = 1, \quad \forall i \in \\{1,2,\dots,n+1\\}\\ & \mathrm Y \succeq \mathrm O\_{n+1}\end{array}}$$

which is convex and computationally tractable. This SDP relaxation provides a **lower bound** on the minimum of the original BLS problem. In the very, very fortunate case where the optimal solution of the SDP happens to be rank-$1$, we have solved the BLS problem.

---

### References

# Answer
> 0 votes
Consider the following approach to approximate this problem.

First, construct an efficient data structure using your vectors that can perform Nearest Neighbor related searching, such as a KD Tree. Then, formulate your problem as an optimization that's a function of $N$, the number of nearest neighbors you will compute. To get there, we can do the following with the cost function:

\begin{align} J &= \left\lVert w + \sum\_{i \in S} v\_i\right\Vert^2 \\ &= \frac{N^2}{N^2}\left\lVert w + \sum\_{i \in S\_N} v\_i\right\Vert^2 \\ &= N^2\left\lVert \frac{w}{N} + \frac{1}{N}\sum\_{i \in S\_N} v\_i\right\Vert^2 \end{align}

Note that $S\_N$ is then an approximate solution for $S$. We can then approximate this problem by choosing $N$ such that we generate a set of vectors, which can be represented by the index set $S\_N$, that are the $N$ nearest neighbors to $\frac{-w}{N}$. The logic is that selecting $N$ nearest neighbors from $\lbrace v\_i \rbrace$ about $\frac{-w}{N}$ will produce a value for $\frac{1}{N}\sum\_{i \in S\_N} v\_i$ close to $\frac{-w}{N}$ and in turn help minimize the norm.

The resulting optimization then ends up being:

\begin{align} N^{\*} = \arg \min\_{N} N^2 \left\lVert \frac{w}{N} + \frac{1}{N}\sum\_{i \in S\_N} v\_i\right\Vert^2 \end{align}

How you go about tackling the above optimization is then up to you.

---
Tags: optimization, approximation, integer-programming, quadratic-programming
---


# Question
Title: Hoare logic - total correctness of loops
Consider a while loop of the form :

$\texttt{while (C) {S}}$

with $\texttt{C}$ the condition and $\texttt{S}$ the body of the loop.

Let $\texttt{I}$ and $\texttt{V}$ respectively be an invariant and a variant of this loop. The rule for total correctness of while loops is given in my textbook by:

> If $\texttt{I} \Rightarrow \texttt{V} \geq 0$
>
> And $\[\texttt{I} \land \texttt{C} \land \texttt{V} = v\_0\] \\,\texttt{S} \\, \[\texttt{I} \land \texttt{V} \< v\_0\]$
>
> Then $\[\texttt{I}\] \\, \texttt{while (C) {S}} \\, \[\texttt{I} \land \neg \texttt{C}\]$

From what I think I understand, in order for the loop to terminate, the variant $\texttt{V}$ must stricly decrease and that it must also be bounded by zero. However, when I translate that mathematically, I obtain a different proposition from that of my textbook :

$$\[\texttt{V} \geq 0 \land \texttt{V} = v\_0\] \\, \texttt{S} \\, \[\texttt{V} \geq 0 \land \texttt{V} \< v\_0\]$$

**My question** : Are this last proposition and my textbook's rule saying the same thing about what needs to be proven in order for the loop to terminate? In other words : is

$\[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v\_0\] \\, \texttt{S} \\, \[\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} \< v\_0\]$

the same as

$\texttt{I} \Rightarrow \texttt{V} \geq 0$ together with $\[\texttt{I} \land \texttt{C} \land \texttt{V} = v\_0\] \\,\texttt{S} \\, \[\texttt{I} \land \texttt{V} \< v\_0\]$

Why or why not?

# Answer
> 4 votes
They are equivalent, in the sense that every time you can apply the textbook rule you can also apply your own rule, and vice versa. The invariant for the two rules is similar, but not the same.

### Converting a textbook rule instance into an instance of your rule

Suppose we have an application or your textbook rule. I.e., we have found some $\texttt{I}$ for which:

$\texttt{I} \Rightarrow \texttt{V} \geq 0$ together with $\[\texttt{I} \land \texttt{C} \land \texttt{V} = v\_0\] \\,\texttt{S} \\, \[\texttt{I} \land \texttt{V} \< v\_0\]$

Then, thanks to the implication above, we also have $\texttt{I} \iff \texttt{I} \land \texttt{V} \geq 0$. Using rule PrePost, we can rewrite the invariant into its equivalent, and we get an application of your rule:

$\[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v\_0\] \\, \texttt{S} \\, \[\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} \< v\_0\]$

Here, we use the same invariant as in the textbook rule.

### Converting an instance of your rule into a textbook rule instance

Now, for the converse direction. Suppose we have found $\texttt{I}$ for your rule:

$\[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v\_0\] \\, \texttt{S} \\, \[\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} \< v\_0\]$

Now, we can't assume $\texttt{I} \Rightarrow \texttt{V} \geq 0$, so we can't use $\texttt{I}$ for the textbook rule. However, we can use as a new invariant $\texttt{I}' := \texttt{I} \land \texttt{V} \geq 0$. We trivially have $\texttt{I}' \Rightarrow \texttt{V} \geq 0$ by construction (\*). Further, from the hypothesis

$\[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v\_0\] \\, \texttt{S} \\, \[\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} \< v\_0\]$

we can obtain (by PrePost)

$\[\texttt{I}' \land \texttt{C} \land \texttt{V} = v\_0\] \\, \texttt{S} \\, \[\texttt{I}' \land \texttt{V} \< v\_0\]$ (\**)

Properties (\*) and (\**) are exactly what we need to apply the textbook rule.

---
Tags: hoare-logic
---


# Question
Title: How to find nearest number in a sequence that is strictly smaller than given number
Given a sequence of numbers $l\_1, \ldots, l\_k$, I want to find for each $i$ the nearest numbers to the left and right of $l\_i$ (if any) that are strictly smaller than $l\_i$. Is it possible to do this in linear time?

# Answer
Converting my comment into an answer.

Here is an algorithm for the interpretation that you are looking for $l\_j$ such that $l\_j \lt l\_i$ and $|i-j|$ is the smallest.

> Traverse left to right, push stuff on stack. If new element to be pushed \>= top element. If new element \< top element keep popping the stack till top \< new element. For the elements popped, the new element is the $l\_j$
> 1 votes

---
Tags: algorithms
---


# Question
Title: Is there a non-trivial type which is equal to its own derivative?
An article called The Derivative of a Regular Type is its Type of One-Hole Contexts shows that the "zipper" of a type—its one hole contexts—follow the differentiation rules in type algebra.

We have:

\begin{align} \partial\_x x &\mapsto 1 \\ \partial\_x 0 &\mapsto 0 \\ \partial\_x 1 &\mapsto 0 \\ \partial\_x (S + T) &\mapsto \partial\_x S + \partial\_x T \\ \partial\_x (S\times T) &\mapsto \partial\_xS \times T + S \times \partial\_x T \end{align}

We can use this model to derive that the derivative of unit is void, that the derivative of list is a product of two lists (prefix times suffix), and so on.

A natural question to ask is, "what type is its own derivative?" Of course we already have $\partial\_x 0 \mapsto 0$, which tells us that void (the uninhabited type) is its own derivative, but that is not very interesting. It is the analog of the fact that the derivative of zero is zero in the ordinary infinitesimal calculus.

Are there other solutions to the equation $\partial\_x T \mapsto T$? In particular, is there an analog of $\partial\_x e^x = e^x$ in type algebra? Why or why not?

# Answer
Consider the finite multisets $\mathbf{Bag}\\:X$. Its elements are given by $\\{x\_1,\ldots,x\_n\\}$ quotiented by permutations, so that $\\{x\_1,\ldots,x\_n\\}=\\{x\_{\pi 1},\ldots,x\_{\pi n}\\}$ for any $\pi\in\mathbf{S}\_n$. What is a one-hole context for an element in such a thing? Well, we must have had $n\>0$ to select a position for the hole, so we are left with the remaining $n-1$ elements, but we are none the wiser about which is where. (That's unlike lists, where choosing a position for the hole cuts one list into two sections, and the second derivative cuts selects one of those sections and cuts it further, like "point" and "mark" in an editor, but I digress.) A one-hole context in a $\mathbf{Bag}\\:X$ is thus a $\mathbf{Bag}\\:X$, and every $\mathbf{Bag}\\:X$ can arise as such. Thinking spatially, the derivative of $\mathbf{Bag}\\:X$ ought to be itself.

Now,

$$\mathbf{Bag}\\:X = \sum\limits\_{n\in\mathbb{N}}X^n/\mathbf{S}\_n$$

a choice of tuple size $n$, with a tuple of $n$ elements up to a permutation group of order $n!$, giving us exactly the power series expansion of $e^x$.

Naively, we can characterize container types by a set of shapes $S$ and a shape-dependent family of positions $P$: $$\sum\limits\_{s:S}X^{(P\\,s)}$$ so that a container is given by a choice of shape and a map from positions to elements. With bags and the like, there's an extra twist.

The "shape" of a bag is some $n\in\mathbb{N}$; the "positions" are $\\{1,\ldots,n\\}$, the finite set of size $n$, but the map from positions to elements must be invariant under permutations from $\mathbf{S}\_n$. There should be no way to access a bag that "detects" the arrangement of its elements.

The East Midlands Container Consortium wrote about such structures in Constructing Polymorphic Programs with Quotient Types, for Mathematics of Program Construction 2004. Quotient containers extend our usual analysis of structures by "shapes" and "positions" by allowing an automorphism group to act on the positions, allowing us to consider structures such as unordered pairs $X^2/2$, with derivative $X$. An unordered $n$-tuple is given by $X^n/n!$, and its derivative (when $n\>0$ is an unordered $n-1$ tuple). Bags take the sum of these. We can play similar games with *cyclic* $n$-tuples, $X^n/n$, where choosing a position for the hole nails the rotation to one spot, leaving $X^{n-1}$, a tuple one smaller with no permutation.

"Type division" is hard to make sense of in general, but quotienting by permutation groups (as in combinatorial species) does make sense, and is fun to play with. (Exercise: formulate a structural induction principle for unordered pairs of numbers, $\mathbb{N}^2/2$, and use it to implement addition and multiplication so that they're commutative by construction.)

The "shapes-and-positions" characterization of containers imposes finiteness on neither. Combinatorial species tend to organised by *size*, rather than shape, which amounts to collecting terms in and computing the coefficient for each exponent. Quotient-containers-with-finite-position-sets and combinatorial species are basically different spins on the same substance.
> 18 votes

# Answer
How about the infinite sum $$\sum\_{i, j \in \mathbb{N}} X^i ?$$ The derivative is $$\sum\_{i, j \in \mathbb{N}} \underbrace{X^i + \cdots + X^i}\_{i+1}$$ which is equal to the original by associativity and commutativity of sums.

Also, the infinite sum is equal to $\sum\_{j \in \mathbb{N}} \mathsf{List}(X)$), so we could try to calculate the derivative using lists.
> 3 votes

---
Tags: type-theory, algebra
---


# Question
Title: Does graph connectivity being NP-complete imply NL=P?
I asked this question on cstheory.se before, where someone pointed out that it is equivalent to asking whether P=NP implies NL=P (thus I edited the question accordingly).

However, my supervisor claims that actually, connectivity being NP-complete implies that NL=P=NP. I can't see why this would be the case; the only additional information we're assuming is that there is a polynomial-time reduction from any NP problem to an NL problem, which does not imply that there exists a corresponding log-space reduction. Wikipedia also mentions

> Whether under these types of reductions the definition of NP-complete changes is still an open problem. All currently known NP-complete problems are NP-complete under log space reductions.

... which seems to support my argument.

# Answer
If NP completeness of connectivity implies $\mathsf{NL}=\mathsf{P}=\mathsf{NP}$, then $\mathsf{P}\neq\mathsf{PSPACE}$. To see why, suppose $\mathsf{P}=\mathsf{PSPACE}$, then connectivity (and any other non trivial language in P) is NP complete, thus $\mathsf{NL}=\mathsf{P}=\mathsf{PSPACE}$ (by our original assumption), which contradicts the space hierarchy theorem.

This means such implication is not yet known. For completeness, I'll add that a negative answer would imply the existence of an NP complete problem which is not complete under logspace reductions (if all NP complete problems were also complete under logspace reductions, then NP completeness of connectivity implies $\mathsf{NL}=\mathsf{NP})$.
> 4 votes

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