title: Enhancing this turing machine's runtime

text:
# Question
Title: Enhancing this turing machine's runtime
As in, I have to design a determenistic (one-taped) turing machine that accepts that language (All strings made up of 0 and 1, where the j-th character from the end is a 0, and $j$ is a constant that we know what it is before running the machine) in less steps than the trivial steps.

In the trivial solution, I would first check if the starting point is a blank, if so the machine denies. If not, go to the last bit (first blank) then move $j$ steps to the left and check if it is $0$. All of that takes $1 + n + j$ steps, but my professor says there is a better runtime that I should come up with.

Any hints would help!

# Answer
There is a Turing machine operating in time $n + 1$ or so, but with lots of states. The machine simulates a DFA for your language. It has $O(2^k)$ states which "remember" the last $k$ characters.
> 3 votes

---
Tags: turing-machines
---


# Question
Title: Decidability. $\lbrace \langle D \rangle \mid \text{$D$ accepts $a^kb^k$ for some $k > 0$}\rbrace$
I'm trying to understand decidable languages. In particular, I would like to show that $$B = \lbrace \langle D \rangle \mid \exists k \geq 0 \\,.\\,\text{DFA $D$ accepts $a^k b^k$}\rangle.$$ I don't quite understand the process of proving these. I know that $a^kb^k$ is not regular, so then no DFA accepts it. I also know that $A\_{DFA}$ (acceptance DFA) is decidable, I also know several other decidable languages like $E\_{DFA}$ and $EQ\_{DFA}$. How can I use these to prove that $B$ is decidable?

If no DFA accepts $a^kb^k$, doesn't that mean that $A\_{DFA}$ will reject? So if $A\_{DFA}$ rejects then shouldn't the decider for $B$ accept?

# Answer
> -1 votes
Corollary 3.19 from *"An Introduction to the Theory of Computation":* "A language is decidable if and only if some nondeterministic Turing machine decides it."

You can construct a nondeterministic Turing machine, $TM\_A$, which is a decider for the language : $A\_DFA = \lbrace \langle B,w \rangle \mid \text{$B$ is a DFA accepting $w$}\rangle$.

$TM\_A$ works as follows on input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is a string:

1. Simulate $B$ on input $w$.
2. If the simulation ends in an accept state, accept. If it ends in an non-accepting state, reject.

Update: The string $a^kb^k$ is not regular and cannot be accepted by a DFA. A CFG for that string would be something like : $A \to aAb \mid \varepsilon$.

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


# Question
Title: Is it true that all languages which have polynomial circuits are in PSPACE?
I just read about polynomial-size circuit families and I have a question as the title. I know P/poly is defined as the class PSIZE of languages that have polynomial-size circuits. But what about other languages in other classes that have polynomial circuits?

# Answer
Some languages in P/poly are undecidable. For example, any language over the alphabet {a} is in P/poly because for any string length n, either an is in the language or it is not, so the advice string for length n can just be whether or not to accept the string. However, there are uncountably many languages over this alphabet and only countably many Turing machines, so infinitely many of these languages are undecidable.

Every language in PSPACE is, by definition, decidable. Therefore, PSPACE ≠ P/poly.

Hope this helps!
> 4 votes

---
Tags: np
---


# Question
Title: Find a binary matrix so that no vector from {-1,0,1}^n is in its kernel
Given integers $n,m$, I want to find a $m \times n$ binary matrix $X$ such that there does not exist any non-zero vector $y \in \\{-1,0,1\\}^n$ with $Xy=0$ (all operations performed over $\mathbb{Z}$). What algorithm could I use for this?

---

In more detail: We are given parameters $n$ and $m$. The problem is to determine if there exists $x$ such that $x\_{i,j} \in \\{0,1\\}$, and there does not exist $y\ne (0,0,\dots,0)$ where $y\_j \in \\{-1,0,1\\}$ for all $j$ and for all $1 \leq i \leq m$,

$$\sum\_{1 \leq j \leq n} x\_{i,j} y\_j = 0.$$

(Notice that we require that at least one of the $y\_j \ne 0$ to avoid the trivial solution.)

For example, consider $m=3,n=4$. Then, expressing $x\_{i,j}$ as a matrix $X$,

$$ X=\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ \end{pmatrix} $$

is a valid solution for $m=3$ and $n=4$.

What algorithm can I use to solve this problem? Can I formulate this as an integer linear programming problem or maybe as a constraint programming problem?

# Answer
> 4 votes
I have a method for you that will help you find valid solutions (matrices) for many possible values of $m,n$. However, it is not a complete answer to your question. It can try to find a matrix for a particular value of $m,n$, but it might fail, and if it fails, you've learned nothing; my method cannot prove that no such matrix exists.

The method is based upon the following observation:

**Theorem.** If we have a valid $m\_1\times n\_1$ matrix $X\_1$ that meets all your requirements (for parameters $m\_1,n\_1$) and a valid $m\_2\times n\_2$ matrix $X\_2$ that meets all your requirements (for parameters $m\_2,n\_2$), then we can find a valid $m\times n$ matrix that meets all your requirements (for parameters $m,n$), where $m=m\_1+m\_2$ and $n=n\_1+n\_2$.

*Proof.* Use the following matrix:

$$X = \begin{pmatrix} 0 &X\_1 \\ X\_2 &Z \end{pmatrix},$$

where $Z$ is arbitrary. Suppose $Xy=0$, where $y \in \\{-1,0,1\\}^n$. Then since the last $m\_1$ coefficients of $Xy$ are zero, and since $X\_1 y\_1 =0$ implies $y\_1=0$, it follows that the last $n\_1$ coefficients of $y$ are zero. Thus by letting $y\_2$ be the restriction of $y$ to its first $m\_2$ coefficients, we find that $X\_2 y\_2 = 0$. But this implies $y\_2 = 0$, i.e., $y=0$. In other words, if $Xy=0$, then $y=0$. This proves that $X$ is a valid matrix.

---

Now this lets us find many values of $m,n$ where it is possible to find a valid matrix $X$. In particular, seed things with some small matrices for various small values of $m,n$ (using any convenient method); then you can derive some larger values of $m,n$ that also have such a matrix.

Here are some observations that will help you identify seed values $m,n$ where such a matrix $X$ exists:

* First, a trivial observation: Obviously, if $n \le m$, it is easy to find a valid solution $x$: just use the identity matrix (if $n\<m$, fill in the extra rows arbitrarily). No need to use integer linear programming. So this problem is only interesting when $n\>m$.
* Second, if $n$ is small enough, you can express this as a SAT instance and apply an off-the-shelf SAT solver. The SAT instance will be of exponential size: it will have more than $3^n$ constraints, so this is only helpful for very small values of $n$, but it will still help you construct some values of $m,n$ where you can find a valid matrix $X$.
* Third, you can use bcorso's answer to handle all cases where $n=m+1$ (there is always a valid solution, for $m\ge 3$).

In particular, you can construct a SAT instance where the $x\_{i,j}$ are the variables. Now, for each possible non-zero vector $y \in \\{-1,0,1\\}^n$, you can add a complicated constraint enforcing the requirement that $Xy \ne 0$. (You'll need to have $m$ adders, each of which adds up to $n$ 0-or-1 values, and then a comparison to test whether the results of all of the $m$ adders are all zero or not.)

In this way, I would expect that, for each $n\le 8$ (or so), you can probably find the largest value of $m$ such that there exists a valid $m\times n$ matrix. Now once you have those seed values, you can use the Theorem above to help you find additional values of $m,n$ where such a matrix exists.

As I stated above, this is not a complete solution, but it might help you solve your problem at least some of the time.

---

For general $m,n$, I doubt that there's any straightforward formulation of this as a polynomial-size integer linear program (unless $\text{NP} = \text{NP}^\text{co-NP}$ or the polynomial hierarchy collapses or something like that, which is not expected to hold; or unless you use some special knowledge about the solution to this problem).

Just telling whether a candidate value of $x$ is indeed a valid solution to this problem is $\text{co-NP}$-complete. See https://cstheory.stackexchange.com/q/20277/5038. In other, recognizing a solution to this problem can't be done in polynomial time (as far as we know); just recognizing a valid solution is $\text{co-NP}$-complete. This means that the problem of finding a valid solution is in $\text{NP}^\text{co-NP}$. In contrast, integer linear programming is in $\text{NP}$. Therefore, without using some special knowledge about this problem, I don't think you can find a generic reduction from your problem to integer linear programming unless $\text{NP}^\text{co-NP} = \text{NP}$ (something that most complexity theorists believe is not likely to hold).

Don't take this too seriously. I'm not trying to prove a formal theorem or anything like that; I'm just trying to give some weak evidence why this problem does not look like it has a straightforward, generic formulation as an instance of integer linear programming.

Of course, you can probably get a formulation as an integer linear program with a number of constraints that is exponential (say, in $m$), similar to how we got a SAT instance. It'll be uglier, because expressing the constraint that some vector (namely, $Xy$) is not identically zero is ugly in ILP. But it's doable. See, e.g., Express boolean logic operations in zero-one integer linear programming (ILP). However, I'm not sure this will be any better than the SAT-based method. If I were implementing this, I would start by trying the SAT-based method, because (if you use a suitable front end, like STP) I think it will be easier to implement and might work just as well or better than an ILP-based formulation.

# Answer
> 2 votes
Below is an exact solutions for the case of $3 \leq n-1 \leq m$ . Thus, you would only need to manually check cases where $m \< n-1$, ($n\>3$).

$\mathbf{Theorem:}$ for $3 \leq n-1 \leq m$ there always exists a binary matrix $X$ such that no (non-trivial) solution exists to the equation $Xy=0$. Furthermore, $X$ has the form:

$$ X\_{(m\ \times\ n)}=\begin{pmatrix} M\_{(n-1\ \times\ n)} \\ 0\_{(m-n-1\ \times\ n)} \\ \end{pmatrix} $$

Where $0\_{(m-n-1\ \times\ n)}$ is a matrix of zeros and:

$$ M\_{(n-1 \ \times\ n)}=\begin{pmatrix} 1 & 1 & 0 & 0 & 0 & \cdots & 0 \\ 1 & 0 & 1 & 0 & 0 & \cdots & 0 \\ 1 & 0 & 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \cdots & \vdots \\ 1 & 0 & 0 & 0 & \cdots & 1 & 0 \\ 0 & 1 & 1 & 0 & \cdots & 0 & 1 \\ \end{pmatrix}, $$

$\mathbf{Proof:}$ Using the above definitions of $X$, $Xy=0$ reduces to $My=0$, which produces the following system of equation:

$$ \begin{pmatrix} y\_1 = t \\ y\_1 + y\_2 = 0 \\ y\_1 + y\_3 = 0 \\ y\_1 + y\_4 = 0 \\ \vdots \\ y\_1 + y\_{n-1} = 0 \\ y\_2 + y\_3 + y\_n = 0 \\ \end{pmatrix} \Rightarrow y=t\ \begin{pmatrix} 1 \\ -1 \\ -1 \\ -1 \\ \vdots \\ -1 \\ 2 \\ \end{pmatrix} $$ Which will never have a solution for all $y\_i \in \\{-1,0,1\\}$ for any choice of $t$ except the trivial solution $t=0$. $\Box$

---
Tags: complexity-theory, linear-programming, linear-algebra, constraint-programming, integer-programming
---


# Question
Title: Constructing inequivalent binary matrices
I am trying to construct all inequivalent $8\times 8$ matrices (or $n\times n$ if you wish) with elements 0 or 1. The operation that gives equivalent matrices is the simultaneous exchange of the i and j row AND the i and j column. eg. for $1\leftrightarrow2$ \begin{equation} \left( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{array} \right) \sim \left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right) \end{equation}

Eventually, I will also need to count how many equivalent matrices there are within each class but I think Polya's counting theorem can do that. For now I just need an algoritmic way of constructing one matrix in each inequivalence class. Any ideas?

# Answer
I have made some progress towards answering this question. I am posting here in case anyone else is interested and also because this construction might have some usefulness for (directed) graphs.

Count the number of 1s in each row. Let $a\_0$ be the number of rows with zero 1s, $a\_1$ the number of rows with one 1 and so on up to $a\_8$ which is the number of rows that have eight 1s. Obviously $\sum a\_i=8$. The proposed parametrization that I have come to after trial and error is: $$(a\_1,\cdots, a\_8; T, S)$$ where T is the trace of the matrix and S is $1$ if the matrix is symmetric and $0$ otherwise. T runs from $0$ to $\sum\_{i=1}^8 a\_i=8-a\_0$.

From my trials and errors it looks like that if two matrices are different in this parametrization then they belong to different equivalence classes, so to construct a representative in each class we just scan through the space of parameters as described above.

(Update) It turns out that this parametrization works fine for n=2 but not for n=3 as it can be seen by a brute force calculation. I still think it provides some insight on the structure of the answer and I invite people to try and modify/extend it to cover the most general case.
> 1 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: If a problem is PSPACE-complete what do we know about NL-completeness
I have a problem $A$ which was shown to be PSPACE-complete by reduction from planning. However, $A$ can also be transformed into reachability problem which is NL-complete.

I know that $NL=NSPACE(log \ n)$ and $PSPACE=NSPACE$.

Does this mean $A$ is also NL-complete? IF yes, does it make any difference in this context to say whether $A$ is PSPACE-complete or NL-complete ?

# Answer
> 3 votes
A PSPACE-complete problem cannot be in NL, and in particular cannot be NL-complete (this is a consequence of the space hierarchy theorem). However, it is NL-hard. If $A$ can be transformed into a reachability problem, then probably the transformation is not polynomial-time.

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


# Question
Title: How to express Rob Pike's classic Go Code presentation in Hoare's CSP Algebra?
At 15:30 in this talk (p13 of this presentation here) Rich Hickey mentions the formalisms available for reasoning about Communicating Sequential Processes. He then goes on to mention that these haven't yet been applied to Clojure's core.async.

The only reference I know of for CSP is Hoare's book. I can see some examples of formalisms to describe CSP here.

Suppose I wanted to do the most basic of CSP as per Rob Pike's presentation in Go (slide 43 of this).

```
var (
    Web = fakeSearch("web")
    Image = fakeSearch("image")
    Video = fakeSearch("video")
)

type Search func(query string) Result

func fakeSearch(kind string) Search {
        return func(query string) Result {
              //time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond)
              return Result(fmt.Sprintf("%s result for %q\n", kind, query))
        }
}

```

**How would I express this as an Algebraic statement? What benefit would it give me?**

Taking a stab at it - I get

`(Web → P) Π (Search → Q) Π (Video → R)`

Which tells me that the Search process can choose to interact with Web or Video depending on which environment the Search Process chooses to communicate with.

**Assumptions**

I'm told that you can't do this in pure CSP because of the timer. For an answer I'm happy to assume we'll ignore the timer part of this.

# Answer
As to the question what benefits it would give you, the answer is **simplicity**.

Modern programming languages are large beasts with complicated semantics, starting with syntax, and not ending with the rules for integer and floating point arithmetic (real languages, as you know, don't work with 'mathematical' integers and reals, but rather with finite approximations). A calculus boils programming languages down to some essentials of interest, in the case of CSP to agents that synchronise on names. This makes thinking about, and proving things to do with synchronisation much easier than doing so using a fully blown programming language. If you are not primarily interested in looking at computation from the point of view communication patterns engendered by synchronisation, then, maybe, CSP is not the right calculus for you.
> 4 votes

---
Tags: concurrency, process-algebras, threads
---


# Question
Title: Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?
Karp's 21 NP-complete problems show that 0-1 integer linear programming is NP-hard. That is, an integer linear program with binary variables.

If we set the $c^T$ vector of the objective $\text {maximize } c^Tx$ to all one (unweighted, i.e., $c^T=(1,1,\dots,1)$) is the problem still NP-hard?

# Answer
We can encode satisfiability of a SAT instance as the feasibility of a 0-1 integer linear program. For feasibility, the objective function doesn't matter, so you can impose whatever constraint you wish on it.

For an example of how to express boolean or, boolean and, and boolean negation in a 0-1 integer linear program, see Express boolean logic operations in zero-one integer linear programming (ILP). This is all that's needed to express a SAT instance as a 0-1 integer linear program.
> 5 votes

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


# Question
Title: A canonical representative, for this equivalence relation on matrices
This question is inspired by Constructing inequivalent binary matrices.

Define the equivalence relation $\sim$ as follows: If $M,N$ are two $8\times 8$ binary matrices (all elements are $0$ or $1$), say that $M \sim N$ if you can transform $M$ into $N$ by a sequence of moves, where each move picks some pair $(i,j)$ and swaps rows $i$ and $j$ and then swaps columns $i$ and $j$. For example, \begin{equation} \left( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{array} \right) \sim \left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right). \end{equation} This equivalence relation induces a set of equivalence classes.

Is there a way to define a canonical representative for each equivalence class, so that given any matrix $M$, we can efficiently compute the canonical representative $M^\*$ corresponding to the equivalence class containing $M$? I'm hoping for a simple and efficient algorithm to compute the canonical representative.

For instance, one way to define a canonical representative for matrix $M$ would be as follows: among all matrices $N$ that are equivalent to $M$, choose the one that is lexicographically first. However, I don't know of any fast way to compute the canonical representative corresponding to a given matrix $M$. (One could enumerate all matrices that are equivalent to $M$ by trying all $8!$ possible permutations, and then check which one is lexicographically first, but this is inefficient: it requires $8! \approx 2^{15.3}$ steps of computation, which is too much.) Is there a better approach?

Alternatively, is there a way to define a canonical representative for each equivalence class, so that we can quickly test any given matrix $M$ to determine whether it is in canonical form? (i.e., there is an efficient algorithm to check this)

A good answer to this question might help solve Constructing inequivalent binary matrices.

# Answer
Here are some ideas to get started. First, we can arrange that the diagonal is of the form $0 \cdots 0 1 \cdots 1$. This breaks the original problem into two new problems which are equivalent to each other. Let's concentrate on the part with zeroes on the diagonal. We can sort the rows according to Hamming weight, and can arrange the first row to be of the form $0\cdots 0 1\cdots 1$, say the one with minimal weight. If it is the only row having the same weight, then again we have broken the problem into two parts, and can continue recursively. If there are several rows with the same minimal weight, we can try tie-breaking using column weights, but this is not always enough. That's where this approach gets stuck, though perhaps one could be more creative and extract a normal form from these ideas.
> 1 votes

---
Tags: algorithms, matrices, permutations
---


# Question
Title: how to calculate Average-Case complexity time by using worst-case and best-case complexity time?
For example let's say that we know that the worst-case running time is o(n) and the best-case is o(1). how can i get the average-case running time using the given big Ohs?

# Answer
You can't. You don't have enough information. Consider the following program:

1. Let $n = |x|$.
2. If $x = 0^n$ then terminate.
3. If $x = 1^n$ then run a loop for $n$ steps.
4. Otherwise run a loop for $f(n)$ steps.

Here $f(n)$ is any function satisfying $f(n) = O(n)$. In an appropriate computation model, the best-case complexity is $O(1)$, the worst-case complexity is $O(n)$, and the average-case complexity is roughly $f(n)$.
> 3 votes

---
Tags: data-structures, asymptotics
---


title: Does NP=coNP imply P=NP?

text:
# Question
Title: Does NP=coNP imply P=NP?
We know that P=NP implies NP=coNP. Does the reverse implication hold? Does NP equal coNP imply that P equals NP? If not why not?

I googled but didn't find the answer.

# Answer
> 6 votes
The case that $P \subset NP = coNP$ is possible. The reason why $P = NP$ implies $NP = coNP$ is that $P$ is closed under complement, and so if $P = NP$, $NP$ must be closed under complement as well.

A class being closed under complement doesn't necessarily imply anything about its deterministic counterpart. For example, we know that $NL$ is closed under complement, but don't know whether $L = NL$.

---
Tags: complexity-theory
---


# Question
Title: Computation Tree Logic and its Temporal Opeators
I've got some questions about the temporal operators in computation tree logic:

1. Does the **F**`inally` path-specific quantifier `Fq` mean that `q` has to hold in a *subsequent* state or is it also fulfilled when `q` holds in the *current* state?
2. Please consider the following example:

What exactly is specified here? Does it mean: If `q AND r` holds on a path `P` in a graph `G` then `q` has to hold somewhere on the subsequent path of `P`. Or does it mean: ... `q` has to hold somewhere on the subsequent path of **every path of `G`**?

# Answer
> 3 votes
First, a small comment - the $F$ operator comes from the word "future", rather than "finally", although it is indeed very tempting to say "finally".

1. The semantics of $Fq$ with respect to a computation $\pi$ is: $$\pi\models Fq \iff \exists i\ge 0, \pi^i \models q$$ Thus, the 0th suffix is also considered, so if $q$ hold immediately, the formula is still satisfied. Observe that you can capture the notion of "strict future" with the formula $XFq$.
2. The formula states that along *every* path ($A$), *every state* $s$ satisfies ($G$) the following: if $q$ and $r$ are true in $s$, then in *every path* starting from $s$, $q$ eventually appears.

I think this is what you meant in your second option.

# Answer
> 1 votes
*For the first question:*
Yes. For a specific path, $Fq$ is evaluated to be true if and only if $q$ is satisfied eventually in the future. It includes the case in which $q$ is satisfied immediately in the first state (of the path).

*For the second question:*
First, do you mean $AG(q \land r) \Rightarrow AF(q)$?

Whatever, $G$ here is not a graph. It is another temporal modality in Computation Logic Tree (CTL). $Gq$ is evaluated to be true if and only if $q$ holds from now on forever. $AG (q \land r)$ is pronounced "**invariantly** $q \land r$", meaning that along *all* paths that start in some specified state, $q \land r$ *always* holds. $AF (q)$ pronounced "$q$ is **inevitable**", meaning that along *all* paths that start in some specified state, $q$ *eventually* holds. Informally, "invariantly" implies "inevitable". Thus, we can conclude that $AG(q \land r) \Rightarrow AF(q)$ for some specified state.

---
Tags: logic, temporal-logic
---


title: TCP congestion problem

text:
# Question
Title: TCP congestion problem
Consider an instance of TCP’s Additive Increase Multiplicative Decrease(AIMD) algorithm where the window size at the start of the slow start phase is 2 MSS and the threshold at the start of the first transmission is 8 MSS. Assume that a time out occurs during the fifth transmission. Find the congestion window size at the end of the tenth transmission.

I am bit confuse in this concept.
What I know :

Slow start and congestion avoidance are different.
Slow start is used in conjunction with congestion avoidance.

Window size for 1st transmission = 2 MSS
Window size for 2nd transmission = 4 MSS
Window size for 3rd transmission = 8 MSS threshold reached, increase linearly (according to AIMD)
Window size for 4th transmission = ?? MSS Window size for 5th transmission = ?? MSS
time out occurs, resend 5th with window size reduced to half (according to AIMD)
Window size for 5th transmission = ??? MSS

What will be the Window size for 4th transmission ? 9 MSS or 10 MSS
It means i want to ask you after threshold window size should increase linearly means it should increase by 1 MSS or 2 MSS ( 2 MSS is given in example ) ?

What will be window size for 5th transmission ? Will it be 1 MSS or 2 MSS ?

Please clear my concept. I am so confused.

# Answer
This is a home work problem. By the way the problem is ambiguous. For concept see 3.6 pg259 of kurose 6th edition.

As for the solution normally what AIMD do is after the time out the it set window size to 1 in the next slow start phase In sort the window increase in this manner 2,4,8,9,10,1,2,4,5,6 So after 10th transmission window size will be 6 But in question says the slow start phase start with 2 MSS So to consider that the window will Grow this way 2,4,8(threshold reached additive increase),9,10(time out& set threshold to 5),2,4,5(threshold reached additive increase),6,7
> 1 votes

# Answer
Window size for 4th transmission is **9 MSS**
Window size for 5th transmision is **10 MSS**, here timeout happens
then we have to reduce the threshold to the half of the current window (i.e new threshold becomes 10/2 = 5 MSS) and window is re-set to **1 MSS** and slow start phase is started again. so, Window size for 5th transmission is **1 MSS**. In AIMD the window size is increased by **1 MSS** only.
> 0 votes

---
Tags: computer-networks
---


# Question
Title: Is there a specific problem that is in both NP and co-NP but not in P?
A problem is in NP if a correct answer to it can be verified to be so in polynomial time.

A problem is in co-NP if an incorrect answer to it can be verified to be so in polynomial time.

P is a subset of the intersection of the sets NP and co-NP.

My question is: what is a **specific** problem that is in the intersection of co-NP & NP, but is not in P?

# Answer
An answer to your question would be a problem $p$ which is in $\mathop{NP}\cap\mathop{coNP}$, and thus in $\mathop{NP}$, but not in $P$. Existence of such a problem would easily imply $P\neq\mathop{NP}$, which is a seriously open problem to this date. That is to say, no one can answer your question yet.
> 6 votes

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


# Question
Title: Proof of Correctness of Prim's algorithm
what is the reason for the correctness proof of Prim's Algorithm for the undirected case cannot carry over to the directed case?

Is it because of after any number of steps, $S$ might not be in a sub tree of an MST since it depends upon the direction of the edge of the directed graph, unlike the undirected one?

# Answer
> 2 votes
The key question is, what do you mean by "spanning subtree" for a directed graph?

If you just want a subgraph that is an oriented tree (i.e., a graph obtained from an undirected tree by choosing exactly one direction for each edge) then use Prim's algorithm and ignore the edge directions.

The normal concept for directed graphs, as @tbirdal points out, is the *arborescence*. An arborescence is what you might call a "consistently oriented" tree there's some vertex $v$ such that every edge is directed away from $v$. However, note that not every directed graph contains a spanning arborescence: for example, take the graph with vertices $\\{a, b, c, d\\}$ and directed edges $\\{(a,b), (c,b), (c,d)\\}$.

Prim's algorithm keeps going until it's added every vertex but we've seen that this can't work for directed graphs. Furthermore, even for directed graphs that do contain an arborescence, the greedy scheme of Prim's algorithm isn't guaranteed to find it. Essentially, this is because you might have to choose a sequence of high-cost edges to gain access to a sequence of low-cost edges. For example (source), in the graph with vertices $\\{a,b,c,d\\}$ and weights $w(a,b)=w(b,d)=3$, $w(a,c)=4$, $w(c,d)=1$, the minimum spanning arborescence is $\\{(a,b),(a,c),(c,d)\\}$ with weight $8$ but Prim's algorithm starting at $a$ produces the arborescence $\\{(a,b),(b,d),(a,c)\\}$ (adding the edges in that order), which has weight $10$.

A graph has a spanning arborescence if, and only if, there is at least one vertex (a root) that sends a directed path to every other vertex – this includes all strongly connected digraphs. In such a graph, Edmonds' algorithm finds a minimum-cost spanning arborescence from a given root in quadratic time.

# Answer
> 1 votes
Prim's algorithm starts with an arbitrary vertex. If you arbitrarily pick a vertex in a directed graph, you might end up with a vertex which is a pure sink, not a source (in other words no directed edge exists from that vertex to any other). In such a case you cannot find a minimum spanning tree including all the vertices.

You might still argue that this is an MST, because it is how they would be defined for directed graphs. However, this would be an Arborescence rather than an MST and other algorithms are there to give you a solution for that.

---
Tags: graphs, correctness-proof, greedy-algorithms, spanning-trees
---


# Question
Title: Does virtual address space resides in virtual memory?
I have several confusion like :

1. Does virtual address space resides in virtual memory ?
2. Does each process has its own virtual address space like each process has its own virtual memory and own page table ?
3. Mapping to physical address takes place from virtual memory or virtual address space if they are different thing ?

# Answer
> 2 votes
A virtual address space maps (addresses) in virtual memory. Typically one uses "virtual memory" when discussing the general concept and "virtual address space" for the concrete instance of a virtual memory.

(Virtual memory may be either relatively fast but expensive physical memory/primary storage \[with a simple translation of virtual address to physical address and typically byte-granularity of access\] or relatively slow but less expensive secondary storage \[which typically involves software "translation", I/O processing, and page-granular access\].)

In commonly used OSes, each process (but not necessarily each thread) is given a separate virtual address space, giving each process the illusion that it owns the entire machine's (virtual) memory capacity as if it was running on the computer by itself. Such OSes typically reserve a portion of the virtual address space (usually half) for OS use, in a sense providing the OS with its own address space. (Some earlier ISAs, e.g., Clipper and m88k, provided a separate address space for the OS.) This dedicated OS address range can typically share page tables across multiple processes (and TLB entries by using a global indicator bit). (For x86's hierarchical page tables, the top node cannot be shared since \[ordinarily\] half of its entries are process-specific. ARM uses separate global and per-process/ASID page table base pointers with indication of how much of the total address range is global.)

(One could consider Address Space IDentifiers as extensions of the virtual address. Segments in Power and Regions in Itanium provide address space extension *similar* to ASIDs, but apply separate extensions to large sections of the initial untranslated address \[e.g., Power uses 256 MiB segments and Itanium provides 8 regions within the 64-bit initial address\]. Power actually calls the address types *effective* \[the address computed by the memory access instruction\], *virtual* \[the address after the segment translation\], and *real* \[i.e., physical\].)

On the other hand, a Single Address Space OS shares the entire virtual address space among multiple processes (protection domains). This allows conceptually simple and potentially low overhead communication among processes very much like memory communication among threads within a single process in a more conventional OS. Obviously, in a SASOS a process is not free to use whatever memory address it wants for whatever purpose it wishes; the OS must prevent different processes from using the same address for different storage. This breaks the illusion that the process "owns" the entire machine.

Every virtual address with a valid page table entry maps to a physical address. If the page table entry is invalid, the address does not map directly to a physical address (it may be in secondary storage \[e.g., disk\] or may not yet be allocated by the process).

(Even the above has simplifications and missing concepts.)

---
Tags: operating-systems, memory-management, paging, virtual-memory
---


title: Non intersecting paths in a graph

text:
# Question
Title: Non intersecting paths in a graph
I'm trying to come up with a good algorithm for the following decision problem:

Let $G=(V,A)$ be a directed graph and let $s,t \in V$. Are there at-least 2 non-intersecting paths from $s$ to $t$?

By non-intersecting I mean that if $P\_1$ and $P\_2$ are non-intersecting paths from $s$ to $t$ then $\forall e\in P\_1\in A, e\notin P\_2$ (can share vertices but not edges).

I thought of the following algorithm:

1. Find the shortest path $P\in A$ in $G$ from $s$ to $t$. if no such path exist, return false;
2. Find the shortest path $P'\in A-P$ in $G$ from $s$ to $t$. if no such path exists, return false; else return true.

I didn't find a contradicting example but so far I was unable to prove its correctness.

Ideas about proof approaches for this algorithm or suggesting other algorithms is welcome.

# Answer
Nope, this algorithm doesn't work. It is possible to find an explicit counterexample. Since it sounds like this is an exercise you're doing to learn algorithms, I won't spoil the exercise for you, but I'll just give you some hints that may help you find a counter example.

* Start with a graph containing just a single path from $s$ to $t$, and nothing else. Make it a fairly short path, say, 5 edges long.
* Introduce a long path from $s$ to $t$ (say, 10 edges long or so) that coincides with the short path for a brief while then diverges.
* Now introduce a second long path from $s$ to $t$ with two properties: (a) it is edge-disjoint with the first long path, (b) it has at least one edge in common with the short path.

Finding a counterexample is a little tricky, but draw it out and try some ideas, and I bet you'll be able to figure out.

---

Your approach doesn't work, but there *are* other algorithms to solve this problem. However, they're fairly complicated: more complicated than your could reasonably be expected to discover on your own. Assuming this is a homework/exercise, I can't just can't believe your teacher would assign you an exercise that requires you to independently re-discover those algorithms -- so there must be some other trick or background information available to you. You might check in with your teacher.

The other algorithms use the following idea: Look for a "funnel" edge $e$ such that all paths from $s$ to $t$ "funnel through" the edge $e$ (i.e., all paths from $s$ to $t$ must include the edge $e$). If you find such an edge, obviously there is no pair of edge-disjoint paths from $s$ to $t$. If you *don't* find such an edge, then it turns out that there's guaranteed to exist two edge-disjoint paths from $s$ to $t$. Proving this is tricky, though, as is devising an efficient algorithm to rapidly test for the existence of such an edge.

---

Since you asked for references, this problem is solved by the following characterization: there are two vertex-disjoint paths from $s$ and $t$ if and only if $s,t$ are part of the same biconnected component. There are fancy algorithms to decompose a graph into biconnected components in linear time. Similarly, there are two edge-disjoint paths from $s$ and $t$ if and only if $s,t$ are part of the same 2-edge-connected component. There are fancy algorithms to decompose a graph into 2-edge-connected components in linear time (or, you can reduce to the problem of computing biconnected components by computing a new graph that swaps vertices and edges).

So, an efficient answer to your question is: decompose the graph into 2-edge-connected components (using the algorithms mentioned in the previous paragraph), then test whether $s$ and $t$ are in the same component.

For more, see e.g., https://en.wikipedia.org/wiki/Biconnected\_component and https://en.wikipedia.org/wiki/Bridge\_%28graph\_theory%29 and https://en.wikipedia.org/wiki/K-edge-connected\_graph.
> 3 votes

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


# Question
Title: NP-complete decision problems - how close can we come to a solution?
After we prove that a certain **optimization** problem is NP-hard, the natural next step is to look for a polynomial algorithm that comes close to the optimal solution - preferrably with a constant approximation factor.

After we prove that a certain **decision** problem is NP-complete, what is the natural next step? Obviously we cannot "approximate" a boolean value...

My guess is that, the next step is to look for a randomized algorithm that returns the correct solution with a high probability. Is this correct?

If so, what probability of being correct can we expect to get from such a randomized algorithm?

As far as I understand from Wikipedia, PP contains NP. This means that, if the problem is in NP, it should be easy to write an algorithm that is correct more than $0.5$ of the times.

However, it is not known whether BPP contains NP. This means that, it may be difficult (if not impossible) to write an algorithm that is correct more than $0.5+\epsilon$ of the times, for every positive $\epsilon$ independent of the size of input.

Did I understand correctly?

# Answer
> 8 votes
You made a crucial change to the question. I've updated my answer to respond to the new question; I'll keep my original answer below for posterity as well.

---

To answer the latest iteration of the question: If the problem you really want to solve is a decision problem, and you've shown that it is NP-complete, then you might be in a tough spot. Here are some candidate next steps:

* Look for heuristics. This means algorithms that work on some problem instances, but not all. Basically, you're hoping that you only come across problem instances that are easy, not any of the worst-case problem instances.

SAT solvers are an example of this approach. They solve a NP-complete decision problem ("does SAT formula $\varphi$ have a satisfying assignment?") using heuristics that happen to work well on many of the formulas we run into in real life, but their worst-case running time remains exponential. Integer linear programming is another example of this.

One very powerful kind of heuristic is to formulate your problem as an instance of SAT, ILP, constraint satisfaction programming, or something like that; and then apply an off-the-shelf SAT/ILP/CSP solver to solve it.
* Look for a fixed-parameter tractable algorithm. Sometimes the complexity of a problem can be characterized by multiple parameters, and occasionally one can find an algorithm that is polynomial in one of the parameters, even if it is exponential in the length of the input (and thus is not a polynomial-time algorithm).

An example would be the knapsack problem, which takes as input an integer $W$ (the capacity of the knapsack) and some other inputs describing the items you can select from. The knapsack problem is NP-hard. However, there is a standard dynamic programming algorithm whose running time is $O(nW)$. This algorithm is exponential in the length of the input (because $W$ is specified in binary, so the value of $W$ is exponential in the length of the input), and thus this does not qualify as a polynomial-time algorithm. However, if $W$ is not too large -- as will often be the case in many practical settings -- this algorithm is efficient enough nonetheless.
* Start looking at algorithms whose running time is exponential, or at least super-polynomial. Sometimes the running time can be optimized so that the exponential running time is (just barely) tolerable.
* Change the problem. Start looking for way which you can "cheat", i.e., change the assumptions or the information given to you to make the computational problem easier.
* Give up. Accept that this is one problem you probably won't be able to solve.

These are standard strategies for coping with NP-completeness. Many textbooks mention these options.

No, randomization alone is not going to take a NP-complete problem and make it easy to solve in polynomial time. Everyone knows that proving $P\ne NP$ is a famous hard problem, and that most complexity theorists expect that $P \ne NP$ but just don't know how to prove it; similarly, most complexity theorists expect that $BPP \ne NP$, but they just don't know how to prove it. Proving that $BPP \ne NP$ looks *even harder* than proving that $P \ne NP$. That's why it is the $P \ne NP$ problem that is famous, not the $BPP \ne NP$ problem; if we can't prove that $P \ne NP$, we have no hope of proving that $BPP \ne NP$.

Incidentally, many complexity theorists expect that $P = BPP$, but proving that is way beyond our current knowledge. That said, for all practical engineering purposes, you can assume that $P = BPP$. (Complexity theorists, close your eyes here. I'm about to use some engineering reasoning that works well enough for all engineering purposes, but will drive theorists crazy.) If you have an efficient randomized algorithm that solves some natural real-world problem, I bet I can build a deterministic algorithm that will almost surely solve the problem, too; I won't be able to give you a proof of that fact, but I'll gladly take that bet even at \\$100 to \\$1 odds in your favor. How can I be so confident? Because if we take your randomized algorithm and, instead of feeding it truly random bits, feed it bits from the output of a cryptographic-strength pseudorandom generator, then there's no way your randomized algorithm is going to be able to tell the difference. After all, if it could, it would have found a way to break the crypto. If you find a way to break the crypto, there are people who will pay you a whole lot more than \\$100 for the secret. That's part of the reason why many people expect that $P = BPP$ (or some moral equivalent) is probably true.

---

Your original question said you wanted to find an approximate solution to a NP-complete problem, and asked what performance is possible. Here was my answer to that question:

It depends on the problem. Some NP-hard optimization problems have good approximation algorithms; others don't. There's lots written in textbooks (and in Wikipedia) on approximation algorithms for NP-hard problems; this is a standard topic in undergraduate algorithms. See, e.g., https://en.wikipedia.org/wiki/Approximation\_algorithm and https://en.wikipedia.org/wiki/Polynomial\_time\_approximation\_scheme, but make sure to read textbooks too.

BPP is not a relevant concept here. The question of whether $NP \subseteq BPP$ would be relevant if you were looking for a randomized algorithm that produces an exact solution to the NP-complete problem. But that's not what you're looking for. You're looking for a randomized algorithm that produces an *approximate* solution to the problem. Looking for an approximate solution is a different problem than looking for an exact solution. If there were a polytime randomized algorithm to find an approximate solution, that wouldn't imply that there's a polytime algorithm to find an exact solution, and it wouldn't imply that $NP \subseteq BPP$. Similarly, if there were a polytime deterministic algorithm to find an approximate solution, that wouldn't imply that there's a polytime algorithm to find an exact solution, and it wouldn't imply that $P=NP$.

Similarly, $PP$ is not very relevant here.

If you really want to relate this to complexity classes, the relevant complexity class is $APX$ (see, e.g., https://en.wikipedia.org/wiki/APX).

Incidentally, many approximation algorithms are deterministic algorithms. Randomization is occasionally helpful but often not needed.

---
Tags: np-complete, approximation, randomized-algorithms
---


# Question
Title: Is Knapsack Feasibility and Knapsack with Unit Values NP-Hard?
It is well known that the maximization problem of Knapsack if NP-hard. How about just finding a feasible solution i.e. objective is set to zero?

And also if we set the values to all one (not the weights) in the objective of the Knapsack problem is it still NP-hard i.e. $\max v^Tx$ where $v=(1,1,1..,1)$?

# Answer
Just finding a feasible solution is in $P$. The empty set is a feasible solution. It achieves an objective of zero. So, the answer to "does a feasible solution exist?" is always "yes!" (to the extent that the question is even well-defined). Similarly, the answer to "is any solution whose value is $\ge 0$?" is always "yes!". Thus, those problems are not NP-hard.

When all values are one, there is also a trivial polynomial-time algorithm to find the optimal solution. You should be able to find it yourself: just try a few examples, and you will quickly discover the trick.
> 3 votes

---
Tags: complexity-theory
---


title: Scheduling Algorithm with limitations

text:
# Question
Title: Scheduling Algorithm with limitations
I have a list of webpages and I must download them frequently, each webpage got a different download frequency. Based on this frequency we group the webpages in 5 groups:

```
Items in group 1 are downloaded once per 1 hour
items in group 2 once per 2 hours
items in group 3 once per 3 hours
items in group 4 once per 12 hours
items in group 5 once per 24 hours

```

This means, we must download all the group 1 webpages in 1 hour, all the group 2 in 2 hours etc.

I am trying to make an algorithm. As input, I have:

a) `DATA_ARR` = one array with 5 numbers. Each number represents the number of items in this group.

b) `TIME_ARR` = one array with 5 numbers (1, 2, 3, 12, 24) representing how often the items will be downloaded.

b) `X` = the total number of webpages to download per hour. This is calculated using items\_in\_group/download\_frequently and rounded upwards. `If we have 15 items in group 5, and 3 items in group 4, this will be 15/24 + 3/12 = 0.875 and rounded is 1.`

Every hour my program must download at max `X` sites. I expect the algorithm to output something like:

```
Hour 1: A1 B0 C4 D5
Hour 2: A2 B1 C2 D2
...

```

A1 = 2nd item of 1st group
C0 = 1st item of 3rd group

My algorithm must be as efficient as possible. This means that I should never download items more often than the update frequency of their group (unless I have absolutely no other choice)(see example)

---

**Example:**

```
group 1: 0 items | once per 1 hour
group 2: 3 items | once per 2 hours
group 3: 4 items | once per 3 hours
group 4: 0 items | once per 12 hours
group 5: 0 items | once per 24 hours

```

We calculate the number of items we can take per hour: `3/2+4/3 = 2.83. We round this upwards and it's 3.`

Using pencil and paper, we can found the following solution:

```
Hour 1: B0 C0 B1
Hour 2: C1 B2 C2
Hour 3: B0 C3 B1
Hour 4: C0 B2 C2
Hour 5: B0 C1 B1
Hour 6: C3 B2 C2
and repeat the above.

```

We take `C0`, `C1` and `C3` once every 3 hours. We also take `B0`, `B1` and `B2` once every 2 hours.

We take `C2` once every 2 hours. This is more often than needed, wasting bandwidth, but if there is no other way around (like here), we will take it every 2 hours. My question on SO here and Math Overflow here made me understand that sometimes you are forced to download items more often than the absolutely minimum.

---

**Question: Please, explain to me, how to design an algorithm able to download the items, while using the absolute minimum number of downloads?** Brute force is **NOT** a solution and the algorithm must be efficient CPU wise because the number of elements can be huge.

# Answer
> 2 votes
Here is a very simple algorithm that will probably suffice in practice.

For each site, keep track of when you last visited, and how long you're supposed to go between downloads. This lets you tell how "overdue" each site is (the difference between those two numbers).

Now at any point in time, you are permitted to download $X$ sites. So, I suggest that you download the $X$ sites that are most overdue.

(Note that if $X$ is large enough, this rule may tell you to download some sites before they are due to be downloaded again. You can either download them now earlier than necessary, or decide to skip downloading them at all at this point and wait for later, depending upon what your goal is.)

---

If for some reason you absolutely need the optimal solution (not one that is good enough), then you could formulate this as an integer linear program and try solving it using an off-the-shelf ILP solver. I am very skeptical of the request for an absolutely optimal solution; I think that is poorly motivated and I doubt it will be necessary in most practical solutions. In practice, the loss from other factors not considered in this simplified model will almost certainly dominate any slight loss of optimality from the simple algorithm above.

But if you insist you absolutely must have the optimal, periodic solution and you're certain you know what you need, then you can formulate this as an ILP problem. Suppose the period is $p$ hours. Introduce integer variables $x\_{t,i}$, with the intended meaning that $x\_{t,i}=1$ means that the $i$th website is downloaded at time $t$, and $x\_{t,i}=0$ means that it isn't. (Here $t$ ranges over $1,2,\dots,p$ and $i$ ranges over the number of websites you have.) Introduce the constraints $0 \le x\_{t,i} \le 1$, to force each $x\_{t,i}$ to be $0$ or $1$. Since you're only allowed to download at most $X$ websites per hour, introduce the constraint

$$\sum\_{i} x\_{t,i} \le X \text{ for } t=1,2,\dots,p.$$

If you want to ensure that item $i$ is downloaded at least $n\_i$ times every $p$ hours, then introduce the constraint

$$\sum\_{t} x\_{t,i} \ge n\_i \text{ for all } i.$$

(You can derive the desired value of $n\_i$ from the required frequency for downloading item $i$; e.g., if the desired frequency is $f\_i$, you can set $n\_i=\lceil f\_i p \rceil$. If you prefer to set a smaller window, say length $\ell$, and require that every window of length $\ell$ download site $i$ at least $n\_i= \lceil f\_i \ell \rceil$ times, you can do that instead; that will give you a more stringent requirement -- just remember to treat time as periodic, when you construct your windows.) Now check whether this ILP has a feasible solution. If it does, you've found a periodic solution of period $p$. Repeat this for each value of $p$ from one to, say, a thousand or so (solving one ILP per possible value of $p$), and keep the best solution you've found. It's unlikely this will yield much improvement over the simple algorithm, but hey, there you go.

---
Tags: algorithms
---


# Question
Title: Largest set of vertices that is larger than its set of neighbors
I am reading a unpublished paper describing an algorithm. In one step of the algorithm, there is a bipartite graph $G(X,Y,E)$, where $X=\\{1,...,n\\}$.

For every subset $X' \subseteq X$, they define

$$f(X')=\bigcup\_{i \in X'} \\{j \in Y| (i,j)\in E\\}.$$

In other words, $f(X')$ is the set of neighbors of vertices in $X'$.

Then they define:

$$ X^+ = \arg \max\_{X' \subseteq \\{2,3,...,n\\}\ s.t.\ |X'|\geq|f(X')|}\\{|X'|\\}$$

i.e., $X^+$ is a largest subset of $\\{2,3,...,n\\}$ such that $X^+$ is at least as large as the set of its neighbors in $Y$ (i.e., the largest subset such that $|X^+| \ge |f(X^+)|$).

And then they do some stuff with this $X^+$.

MY QUESTION IS: Can this $X^+$ be found in polynomial time?

The authors do not prove that it can, but this is implied by the paper (otherwise the algorithm itself cannot be polynomial). Maybe it is so obvious that only I haven't seen this?

EDIT: The following similar problem can be solved easily:

```
Find the largest set of vertices in X with less than |Y| neighbours.

```

Solution: find a $y \in Y$ with a minimal number of neighbours in $X$. Return the set that includes all vertices in $X$ except $y$'s neighbours.

What about the following similar problem?

```
Find the largest set of vertices in X with less than |Y|/2 neighbours.

```

# Answer
> 1 votes
Consider the following problem.

> Find $X''$ such that $|X''| = k$ and $|f(X'')| = m$

If it was **P** then so would set cover: fix $m = |Y|$ and iterate over all $k \in \\{1, \dots, |X|\\}$ to find a minimum.

---

Let's call this problem $\text{exact}(G, k, m)$ and let's call your problem $\text{largest}(G)$.

Let $G(X, Y, E)$ be any bipartite graph. Let $G^1$ be a graph with one additional vertex in $X$, not connected to anything. Let ${\_1}G$ be a graph where for every vertex of $X$, a new vertex is added to $Y$ and the two are connected. Let ${^1}G$ be a graph where for every vertex of $Y$, a new vertex is added to $X$ and the two are connected. Let ${\_k^l}G^i = ({\_k}({^l}G))^i$ be these transformations applied repeatedly. Note the order.

$G^i$ will be used to artificially raise $|X^+|$ and therefore $|f(X^+)|$. ${\_k}G$ will be used to weight down vertices $v$, so we can control whether $v \in X^+$ even if $f(v) \subset f(X^+)$ in $G$. ${^l}G$ will be used to prioritize larger $|f(X^+)|$.

Say $X^+ = \text{largest}(G^i)$. This implies that $\text{exact}(G, |X^+|-i, |f(X^+)|)$, because you know that the $i$ new vertices in $X$ will be used and thus $|X^+|$ old vertices have a neighborhood of $|f(X^+)|$ old vertices. Similarly $X^+ = \text{largest}({\_k}G)$ implies $\text{exact}(G, |X^+|, |f(X^+)|-k|X^+|)$.

---

To find $\text{exact}(G, k, m)$, let $X^+\_i = \text{largest}({\_M^i}G^{(mi+k)M+(m-k)})$ for sufficiently large $M$ (say, $M = |X|+|Y|$).

* If $|X^+\_0| \< kM + (m-k) + k$ then $\text{exact}(G, k, m)$ is false.
* If $|f(X^+\_i)| = (mi+k)M+m$ then $\text{exact}(G, k, m)$ is true. Note that if $\text{exact}(G, k+ix, m-x)$, then $|f(X^+\_i)|$ could also have the value $(mi+k)M+m-x$.
* Raise $i$ until $\forall x\>0, \neg \text{exact}(G, k+ix, m-x)$ (you can jump directly to $i=|X|$). Then $|f(X^+\_i)| = (mi+k)M+m$ if and only if $\text{exact}(G, k, m)$.

---
Tags: algorithms, graphs, time-complexity, runtime-analysis
---


# Question
Title: Does two languages being in P imply reduction to each other?
Given two languages $L\_1$ and $L\_2$ that are in $\mathsf{P}$, can it be proven that there is a polynomial time reduction from $L\_1$ to $L\_2$ and vice versa? If so, how?

I noticed that if $L\_1$ is the empty language, and $L\_2$ is the "full language" $\\{ 0,1 \\}^\*$, there does not seem to be a reduction from $L\_2$ to $L\_1$, but this is not clear to me. I know how a reduction works, so that is not a problem for me.

# Answer
> 11 votes
# No, in general

As you've already noticed, if $L\_2$ is either the full language or the empty language, there can be no reduction from $L\_1$ to $L\_2$ \- the argument is simple enough.

Recall the definition. $L\_1$ reduces to $L\_2$ iff there exists a function $f: \Sigma^\* \rightarrow \Sigma^\*$ such that $\forall w \in L\_1, f(w) \in L\_2$, and $\forall w \notin L\_1, f(w) \notin L\_2$, and $f$ is computable in polynomial time.

Suppose $L\_1 \neq \emptyset$ and $L\_2 = \emptyset$. Suppose also that some function $f$ exists such that $w \in L\_1 \implies f(w) \in L\_2$. This argument immediately gives us a contradiction. We know that $w \in L\_1$ can be true, but $f(w) \in \emptyset$ can never be true, so there cannot be such an $f$, poly-time or not.

The argument for $L\_1\neq\Sigma^{\*}$ and $L\_2 = \Sigma^{\*}$ is similar. For any function $f: \Sigma^\* \rightarrow \Sigma^\*$, $w \in L\_1$ can be false, but $f(w) \in \Sigma^{\*}$ is always true.

There are some other subtleties floating around this question, and it's a worthwhile exercise to think of all the possible combinations you could get from assigning $L\_1$ and $L\_2$ to $\emptyset$, $\Sigma^{\*}$ and some non-empty non-"full" language.

This said, with a further assumption, there's a small trick we can apply to make this argument hold:

# Yes, if we have that neither $L\_1$ nor $L\_2$ are empty or "full"

Both $L\_1$ and $L\_2$ are in $P$, so we can decide them in polynomial time.

Let $w\_\top \in L\_2$ and $w\_\bot \notin L\_2$. These words are constant, so are of constant length.

We will define $f$ as follows. If $w \in L\_1$, then $f(w)=w\_\top$. If $w \notin L\_1$, then $f(w)=w\_\bot$. Clearly, $f$ represents a reduction from $L\_1$ to $L\_2$ according to the above definition. Since $L\_1$ can be decided in polynomial time, we can compute $f$ in polynomial time.

So $f$ is a poly-time reduction from $L\_1$ to $L\_2$. This argument can work the other way to provide a reduction from $L\_2$ to $L\_1$, so the languages reduce to each other.

If exactly one of $L\_1$ or $L\_2$ is empty or "full", we can reduce from one to the other. Which way? Why?

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


# Question
Title: Why will the Hindley-Milner algorithm never yield a type like t1 -> t2?
I'm reading about the Hindley-Milner typing algorithm while writing an implementation, and see that, as long as every variable is bound, you'll always get either atomic types or types where the arguments will determine the final type, such as `t1 -> t1` or `(t1 -> t2) -> (t1 -> t2)` where `t1` and `t2` are type variables.

I cannot think of a way you'd get something like `t1 -> t2` or simply `t1`, which I understand would mean the algorithm is broken since there would be no way to determine the actual type of the expression. How do you know you'll never get a type such as these "broken" ones as long as every variable is bound?

I know the algorithm yields types with variables, but these are always resolved once you pass the arguments to the function, which wouldn't be the case in a function with type `t1 -> t2`. This is why I want to know how we know for sure the algorithm will never yield such types.

(It seems that you can get these "broken" types in ML, but I'm asking about lambda calculus.)

# Answer
> 16 votes
In the lambda calculus with no constants with the Hindley-Milner type system, you cannot get any such types where the result of a function is an unresolved type variable. All type variables have to have an “origin” somewhere. For example, the there is no term of type $\forall \alpha,\beta.\\; \alpha\mathbin\rightarrow\beta$, but there is a term of type $\forall \alpha.\\; \alpha\mathbin\rightarrow\alpha$ (the identity function $\lambda x.x$).

Intuitively, a term of type $\forall \alpha,\beta.\\; \alpha\mathbin\rightarrow\beta$ requires being able to build an expression of type $\beta$ from thin air. It is easy to see that there is no **value** which has such a type. More precisely, if the type variable $\beta$ does not appear in the type of any term variable in the environment, then there is no term of type $\beta$ which is in head normal form. You can prove this by structural induction on the term: either the variable at the head would have to have the type $\beta$, or one of the arguments would have to have a principal type involving $\beta$, i.e. there would be a smaller suitable term.

Just because there is no value of a certain type doesn't mean that there is no term of that type: there could be a term with no value, i.e. a non-terminating term (precisely speaking, a term with no normal form). The reason why there is no lambda term with such types is that all well-typed HM terms are strongly normalizing. This is a generalization of the result that states that simply typed lambda calculus is strongly normalizing. It is a consequence of the fact that System F is strongly normalizing: System F is like HM, but allows type quantifiers everywhere in types, not just at the toplevel. For example, in System F, $\Delta = \lambda x. x \\, x$ has the type $(\forall \alpha. \alpha) \rightarrow (\forall \alpha. \alpha)$ — but $\Delta\\,\Delta$ is not well-typed.

HM and System F are examples of type systems that have a Curry-Howard correspondence: well-typed terms correspond to proofs in a certain logic, and types correspond to formula. If a type system corresponds to a consistent theory, then that theory does not allow proving theorems such as $\forall A, \forall B, A \Rightarrow B$; therefore there is no term of the corresponding type $\forall \alpha,\beta.\\; \alpha\mathbin\rightarrow\beta$. The type system allows one to deduce “theorems for free” about functions over data structures.

This result breaks down as soon as you add certain constants to the calculus. For example, if you allow a general fixpoint combinator such as $Y$, it is possible to build terms of arbitrary type: $Y (\lambda x.x)$ has the type $\forall \alpha. \alpha$. The equivalent of a general fixpoint combinator in the Curry-Howard correspondence is an axiom that states $\forall A, \forall B, A \Rightarrow B$, which makes the logic obviously unsound.

Finding the fine line between type systems that ensure strong normalization and type systems that don't is a difficult and interesting problem. It is an important problem because it determines which logics are sound, in other words which programs embody proofs of theorems. You can go a lot further than System F, but the rules become more complex. For example, the calculus of inductive constructions which is the basis of the Coq proof assistant, is strongly normalizing yet is capable of describing common inductive data structures and algorithms over them, and more.

As soon as you get to real programming languages, the correspondence breaks down. Real programming languages have features such as general recursive functions (which may not terminate), exceptions (an expression that always raises an exception never returns a value and hence can have any type in most type systems), recursive types (which allow non-termination to sneak in), etc.

---
Tags: lambda-calculus, type-theory, typing, type-inference
---


# Question
Title: Using approximations to optimization problems for threshold problems
Many problems in computer science come in two flavors:

* Optimization problem: "Find an object with the largest size".
* Decision problem: "Given $n$, find an object with a size of at least $n$, or reply that such an object does not exist".

Given a solver for the optimization problem, the decision problem can be solved simply by checking if the optimal solution has a size of at least $n$. But this doesn't help if the optimization problem is NP-hard.

MY QUESTION IS: If we have a constant-factor approximation algorithm for the optimization problem, how can we use it for the threshold problem?

A possible way is: if the approximate solution has a size of at least $n$, return it; if it has a size of less than $n/c$ (where c is the approximation constant), return that an object of size $n$ does not exist; otherwise, return "I don't know". This may return a correct answer in many cases, but not in all cases.

Is there a better way?

# Answer
> 4 votes
First off, a technicality: optimization problems aren't NP-complete; only decision problems can be NP-complete (or in NP). Thus, it's only the decision problem (what you call the "threshold problem") that is in NP, or NP-complete.

On to the substance of your question. The answer is: You can't. In general, the approximation algorithm typically doesn't let you solve the decision problem. Think about it. We have many problems for where the decision problem is NP-complete, but where we have a polytime approximation algorithm. If the approximation algorithm let us quickly solve the decision problem (or the corresponding optimization problem), then we'd immediately have a polytime solution to a NP-complete (or NP-hard) problem, and thus a proof that P=NP. When you start with some assumption and it leads to a conclusion that is too good to be true, that's a sign that the assumption probably wasn't valid.

No, your "obvious answer" doesn't work. Decision problems aren't allowed to return "I don't know". No, there isn't a better way (assuming the problem is NP-hard, and assuming $P\ne NP$).

---
Tags: np-complete, reductions, optimization, approximation
---


# Question
Title: Prove that every maximal flow yields the same minimal cut
Hi I'm trying to prove the following proposition:

---

Given a network $G,s,t,\omega$ where $\omega$ is the capacity, create a minimal cut cut ${S=\left\\{ (s,v)\in E\_{G\_{r\\\_max}}\right\\} }$ where $G\_{r\\\_max}$ is graph representing the the residual network(meaning we take the group of all vertices that are reachable from s in $G\_{r\\\_max}$). So that the cut is $\left(S,V\backslash S\right)$.

Given two maximal flows $f\_1\neq f\_2$ prove that $\left(S\_1,V\backslash S\_1\right)=\left(S\_2,V\backslash S\_2\right)$ (which are defined in the above mentioned form for each maximal flow).

---

I've tried proving by assuming the contrary and saying that $S\_1 $ is not subset of $S\_2$. Tried to say that this leads to $\exists \ v\in S\_1 \ \ \mbox{s.t} \ \ v\notin S\_2$. Tried looking at the intersection and union of these groups but to no avail.

I'd appreciate some guidance\explanation as to how best prove this claim.

# Answer
> 1 votes
Here are some hints. Instead of trying to prove the contrapositive, try proving the statement directly. If $f\_1 \ne f\_2$, then that means that there is some edge $e$ where $f\_1$ sends a different amount of flow down than $f\_2$ does. What does that imply about the residual graph for $f\_1$, vs the residual graph for $f\_2$? Those two residual graphs must differ in some specific way: how? What does that difference imply for $S\_1$ vs $S\_2$? Try writing out some small examples, with small graphs, where you draw the flows, residual graphs, and cuts explicitly. What do you find?

I suggest you spend a bit more quality time on your own, trying a bit harder to solve it yourself. This is your exercise; you need to solve it yourself. And you need to put in a bit more effort to explore this problem. Don't give up easily -- you can do it!

---
Tags: graphs, network-flow
---


# Question
Title: Digraph problem relating in- and out-degrees
Given a digraph $D = (V, A)$ and $m \in \mathbb{N}$, the question is is there a subset $A' \subseteq A$, such that $\lvert A' \rvert \geq m$ and $d\_{D'}^+(u) \leq d\_{D'}^-(v)$ holds for every arc $(u, v) \in A'$ in the subgraph $D' = (V, A')$, i.e. the out-degree of $u$ is not larger than the in-degree of $v$? Note that the degree constraints should hold in the subgraph $D'$.

This seems like a straight-forward problem, alas I am unable to connect it to some more familiar graph problem. I am mostly interested in its complexity.

# Answer
> 1 votes
There is a formulation of this as integer linear programming (ILP). There is no theoretical guarantee that the resulting ILP will be solvable in polytime, but off-the-shelf ILP solvers are pretty good, and I wouldn't be surprised if in practice an ILP solver is often effective at solving this problem.

In particular, for each edge introduce a variable $x\_e$, with the intention that $x\_e=1$ means that $e \in A'$ and $x\_e=0$ means that $e \notin A'$. Then we get the obvious constraints $0 \le x\_e \le 1$ and $\sum\_e x\_e \ge m$. Also introduce a variable $y\_e$ for each edge $e \in A$, defined as

$$y\_{(u,v)} = \sum\_t x\_{(t,v)} - \sum\_w x\_{(u,w)}.$$

Notice that $y\_{(u,v)} = d^-\_{D'}(v) - d^+\_{D'}(u)$.

Now we want to express the requirement that if $x\_e=1$ then we must have $y\_e\ge 0$. One way to do this is to introduce the variables $y^+\_e, y^-\_e$ and add the linear inequalities $y\_e = y^+\_e-y^-\_e$, $y^+\_e \ge 0$, $y^-\_e \ge 0$, $y^-\_e \le c \cdot (1-x\_e)$, where here $c$ is a large constant (setting $c=|V|$ is large enough). Notice that if $x\_e=1$, then these constraints imply $0 \le y^-\_e \le c \cdot 0 = 0$, i.e., $y^-\_e=0$, which implies that $y\_e \ge 0$. In contrast, if $x\_e=0$, then these constraints imply $0 \le y^-\_e \le c$, which will always be satisfied (the difference of two degrees cannot be more than $|V|$, for trivial reasons), so if $x\_e=0$, there are effectively no restrictions on the allowable values of $y\_e$, just as we wanted.

There will be a feasible solution to this ILP if and only if there is a subset $A'$ satisfying the desired properties.

My thanks to @user12537, who pointed out that my original answer was flawed. This revision attempts to address those problems.

---
Tags: graphs, time-complexity, decision-problem
---


# Question
Title: Chinese Postman Problem: finding best connections between odd-degree nodes
I am writing a Program, solving the Chinese Postman Problem (also known as route inspection problem) in an undirected draph and currently facing the problem to find the best additional edges to connect the nodes with odd degree, so I can compute an Eulerian circuit.

There might be (considering the size of the graph that wants to be solved) an enormous combination of edges which need to be computed and evaluated.

As an example there are the odd-degree nodes $A, B, C, D, E, F, G, H$. The best combinations could be:

1. $AB$, $CD$, $EF$, $GH$
2. $AC$, $BD$, $EH$, $FG$
3. $AD$, $BC$, $EG$, $FH$
4. $AE$ ....

where $AB$ means "edge between node $A$ and node $B$".

Therefore my question is: is there a known algorithm to solve that problem in a complexity better than pure brute force (computing and evaluating them all)?

€:After some research effort I found this article, speaking about the "Edmonds' minimum-length matching algorithm" but I cannot find any pseudo-code or learners-descriptions of this algorithm (or at least I do not recognize them, as Google offers a lot of hits an matching algorithms by J. Edmonds)

# Answer
> 1 votes
As remarked in the comments, Wikipedia gives a reduction from route inspection to minimum-weight matchings. Vladimir Kolmogorov has published a fast implementation of the weighted version of Edmonds' blossom algorithm, in C++ \[1\].

\[1\] V. Kolmogorov, Blossom V: A new implementation of a minimum cost perfect matching algorithm. *Mathematical Programming Computation*, 1(1):43–67, 2009.

---
Tags: algorithms, graphs
---


title: Decrypting transposition ciphers

text:
# Question
Title: Decrypting transposition ciphers
How do I see if the following ciphertext `eaeairtntrnaeemtve` is a transposition cipher, using letter frequency?

This article suggest how to detect by using letter frequency detection and cryptanalysis but I am unsure of how to do this. Any suggestions?

# Answer
It might be problematic to use letter frequency when you have short ciphertext.

Anyway, this is transposition cipher! so your plaintext is probably some permutation of the ciphertext.

You have $18 = 3 \cdot 6$ chars. Try to write them as a rectangle of $3 \times 6$ or $6 \times 3$ and read it in different ways (spiral, zigzag, etc.).
> 2 votes

# Answer
It is impossible to do cryptanalysis on such a short message. It could be anything, encrypted with anything. Even if you somehow knew that it's a substitution cypher, it could be any 18-character message where the right characters match (there must be seven different letters; characters 1, 3, 13, 14 and 18 have to be the same; characters 1 and 2 must be different, etc.).

If you had a longer cyphertext (say a few hundred characters), you'd just compute the frequency of the characters appearing in the cyphertext and compare that to the frequency of the letters in the language you think the message was written in. The frequencies in English are: e 12.7%, t 9.1%, a 8.2%, o 7.5%, i 7.0%, n 6.9%, etc. If a decently long cyphertext comes decently close to that distribution, you'd expect a transposition cypher. If you only have that the most common characters occur about 13%, 9%, 8%, 8%, 7%, 7%... of the time, you'd suspect a substitution cypher and you'd start guessing the letters based on their frequency. Note that the process is not automatic and you need to be flexible: for example, if the message is about the Zulus playing zithers in zoos in Zanzibar, the letter frequencies may be skewed quite some distance from the average over all English text.
> 3 votes

---
Tags: cryptography
---


# Question
Title: Queue, moving the element at the tail to the head
Suppose I have a queue where I pull from left and push to the right, and suppose I have the contents in the queue as $a b c @ d e$ (from left to right, left is head, right is tail).

Is there a simple algorithm that doesn't require extra structures that makes $e$ at the head? meaning to get us to the queue $eabc@d$?

P.S.: I need an algorithm like that for the purpose of a queue automaton.

# Answer
> 4 votes
If you can only push (enqueue) or pull (dequeue) from the queue, then your only option is to pull all the elements and re-enter them.

If you need such an operation, you can use deque (double-ended queue). See: http://en.wikipedia.org/wiki/Double-ended\_queue .

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


title: Regular language using pumping lemma

text:
# Question
Title: Regular language using pumping lemma
a^2n b^(2n+1) is a regular language. I am not able to decompose it in xyz so that I can pump any power of y as per pumping lemma. Please help me out.

# Answer
> 2 votes
You probably misunderstood the question. For starters, the pumping lemma can't be used to prove that a language is regular, it can only be used to prove that a language *isn't* regular. The Wikipedia page for the pumping lemma gives a counterexample.

Secondly, as already pointed out by @DavidRicherby, this particular language is *not* regular, and as it turns out, you *can* use the Pumping Lemma to prove *this* statement.

Roughly speaking, the proof goes as follows:

Assume for the sake of contradiction that the language is regular, and thus, the Pumping Lemma holds. The "y" can take one of three forms:

1. y contains all "a"s
2. y contains all "b"s
3. y is of the form $a^ib^j$ for some $i,j \> 0$.

Now, can you see how to derive the contradiction?

---
Tags: regular-languages
---


title: What is combinatorial explosion?

text:
# Question
Title: What is combinatorial explosion?
In the theory of NP-completeness, researchers refer to the concept of combinatorial explosion. Some researchers use it as justification for intractability or NP-completeness. Others use it to refer to the exponential growth of possible solutions of an intractable problem while others use to refer to the apparent exponential time required to solve NP-complete problems. I am interested in formal connection to combinatorics.

> Is there combinatorial basis that captures and explains the phenomena of combinatorial explosion?

# Answer
> 8 votes
There is no formal connection to anything because "combinatorial explosion" is an informal term. It refers to rapid growth of a function caused by the combinatorics of the situation.

# Answer
> 3 votes
Assume your algorithm has a complexity of $\Theta(n!)$. For small $n$ your problem can be easily solved in any machine, however when $n$ grows large enough even the fastest computers cannot figure out the solution. As the options and cases to observe increase, your complexity increases so rapidly that even for some reasonable $n$, it becomes impossible to run the algorithm with current resources. This is combinatorial explosion.

It is however, as mentioned, an informal term.

---
Tags: complexity-theory, terminology, combinatorics
---


# Question
Title: Having trouble proving a language is NP-complete
I'm asked to prove that, if P=NP, that 0\*1\* is NP-complete, but I'm having trouble going about doing it. I know it's fairly easy to prove it's NP by creating a TM to verify an input (which can be done in O(n) time, and that's polynomial).

But then I now have to reduce an NP-complete problem to 0\*1\* in order to prove that 0\*1\* is NP-complete. I'm thinking reducing SAT to it, but I have no idea how to do that, since in SAT all you can use is and, or, and negate, and there's no way to tell if a 1 came before a 0 in an input by doing that (at least, as far as I can tell).

Thanks

# Answer
I might be taking this question too lightly, but if you are given that P = NP then showing that 0\*1\* is in P should satisfy the definition of NP-Complete... i.e if a language L is in P we now know its also in NP (because P=NP is given) and every language in NP is clearly polynomial time reducible to L! Think about it, if A is polynomial time reducible to L and we know L is in P (you'd have to prove this part), then A is also in P...and since P=NP...we know all languages in NP will be polynomial time reducible to L. This satisfies the two conditions of NP-completeness: 1. L is in NP and 2. All A in NP is polynomial time reducible to L
> 3 votes

# Answer
Here is a more technical answer. The "trick" is to put all the work in the reduction function.

Assume $NP = P$, $L \in P$ and let $x\_0, x\_1$ be two instances, such that $x\_1 \in L$ and $x\_0 \not\in L$. We have to show that some $NP$-complete problem $Q$ is poly-time reducible to $L$. By assumption, there is an algorithm $M$ deciding $Q$ in polynomial time.

Define a function $$ f(x) = \begin{cases} x\_1 & \mbox{if $M(x) = 1$} \\ x\_0 & \mbox{else} \end{cases}\mbox{ ,} $$ for all instances $x$ of $Q$. Then clearly $f \in FP$ and $x \in Q \Leftrightarrow f(x) \in L$.
> 4 votes

# Answer
So let $L=\\{0^n1^m | n,m \in {\mathbb N} \\}$.

As you note, that $L \in P$ is straightforward --- simply make a Turing machine that checks the membership in $L$ in poly time, and this is proven. Since $P \subseteq NP$, this also shows membership in $NP$.

Now you must show hardness. If $P=NP$, then all $P$-hard problems are also $NP$-hard by definition. Thus, to show hardness we need only show that deciding $L$ is $P$-hard. So we reduce a $P$-hard problem to $L$. This is where you run into trouble, because the way you have defined it, $L$ is regular, and therefore requires only log space. I think it may be impossible to prove hardness even with the rather strong assumption that $P=NP$.
> 0 votes

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


# Question
Title: How to optimize Dijkstra's algorithm for a grid graph?
I'm trying to apply Dijkstra's algorithm to the Problem 83 on projecteuler.net. The problem reads:

> In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.
>
> ```
> 131   673   234   103    18
> 201    96   342   965   150
> 630   803   746   422   111
> 537   699   497   121   956
> 805   732   524    37   331
>
> ```
>
> Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.

I wonder if the original algorithm can be simplified due to the fact that the graph is represented as a matrix?

In particular, I've noticed that every edge in the graph is only relaxed once (i.e. the node's distance is changed only once from infinity to some value). Can I rely on this fact in my code?

# Answer
> 3 votes
I am in love with Project Euler so that I am glad to see questions regarding it here. Be aware, however, that getting hints is somehow *forbidden* (note the italics :) ). The following is taken from the About page once you login:

**I learned so much solving problem XXX so is it okay to publish my solution elsewhere?**

*It appears that you have answered your own question. There is nothing quite like that "Aha!" moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, however, that will not be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.*

So I hope to provide a useful answer to your question while I honor the statement above ...

Regarding your first question the answer is No. There is nothing particularly interesting from the fact that you have a matrix. I see this more a matter of convenience for posting the problem than for finding the solution. I think I am not uncovering any interesting observation here since the same technique for solving this problem can be applied to arbitrary graphs.

Regarding your second question, you are right if you apply Dijkstra directly in a forward manner (ie., from the top left corner to the bottom right corner) but you have then a problem, and this is that the number of paths grows exponentially. Be sure that this problem can be solved in less than a second, ... So you should try something slightly different. Do not give up, I can see you are on the right path, so keep up pushing ...

And that's all I should say to respect the pleasure you'll get when solving this problem. Your "Aha!" moment :)

Hope this helps,

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


# Question
Title: Minimum number of people required to invite everyone to a reunion
I'm trying to organise a large reunion though facebook. Over the years we've all drifted apart, and so there isn't anyone who is still facebook friends with everyone.

You need to be facebook friends to invite someone to the facebook event and I have invited all the people that I can. I also know that each of the uninvited people has at least one friend amongst the invited people, and by checking for 'mutual friends' I can know who they are.

In order to get everyone invited to the reunion I'm going to ask some of the invited people to invite the uninvited people.

My question is, does anyone happen to know an algorithm to find the minimum number of invited people that are required to message all of the uninvited people? I don't need anything super detailed, just something to point me in the right direction.

# Answer
> 1 votes
One way to think about it is to make an undirected graph, and have every person be a vertex. There is an edge between two people if they are Facebook friends.

Now, assuming that you're asking people to invite their friends, and have those people invite *their* friends, and so on, then your problem basically boils down to finding the *connected components* of the graph you just made. (Two vertices are in the same connected component iff there exists a path between them)

Actually finding them isn't that bad; it's basically a slightly modified DFS.

---
Tags: algorithms
---


# Question
Title: How can it be detected that a number generator is not really random?
I heard that random number generation in computers isn't really random, but there is no efficient algorithm to detect it. How can it be detected at all ?

# Answer
**Computers Being Really Random:**

True randomness is impossible for Turing Machines in a theoretical sense, and most computers can't generate truly random output. Therefore, some modern computers include hardware that allows the computer to access an outside source which will hopefully include some randomness. One example of how this can be accomplished is to track small fluctuations in temperature inside the computer. Randomness can be obtained from an outside source as well. But from the tone of your post I don't think that outside sources of randomness are what you're interested in.

**Seeds:**

Without an outside addition, everything a computer does is deterministic. This leads to a big issue: if you call a random number generation program, it will give you the same result every time if you give it the same input. Clearly, we need a program that outputs a random number to change its behavior each time it's run (otherwise we'll keep getting the same "random" number, which is not particularly helpful). One idea is to give the program some input, which changes each time the program is run, so that a different number will be output. We call this input a "seed." The random number generator needs to take in a seed, perform some operations, and give us a random number.

The current system time is a classic example of a seed. This gives a long string with high entropy, and if the time is kept track of in a sufficiently granular fashion (i.e. if your system clock uses hours then "time" is a pretty poor seed), you're unlikely to feed the pseudorandom number generator the same number twice.

**Algorithms that are Random Enough:**

Now we have an algorithm that at least has some way to be different each time it's run. We give it a seed, and while the algorithm gives the same number when prompted with the same seed, we want the numbers it generates to be random otherwise. This acts like the above--you take in some input, and it produces some (hopefully different enough from the input to be "random") output.

Now let's say you came up with your own algorithm to do this, and you claim that the numbers you come up with are pretty close to random when you gave it a bunch of different seeds. How would we test how good it is?

Now we want some algorithm that will take in a seed, do some operations, and produce a random number. At the simplest, the algorithm could just output the seed--it's not giving us the same number each time, and random seeds give us random outputs. But clearly that's not what we want. On the other hand, an algorithm can be fairly complicated, like many actual pseudorandom generators. How can we tell which algorithms give us "random" numbers from our not-necessarily-random seeds? If we can't get it exactly, how can we tell which are best?

It's hard to tell which of those tests are ideal, but it's easy to come up with some minimum requirements these algorithms should meet before we say they give us "random" numbers. Maybe we want to make sure that your algorithm gives even numbers half the time. Maybe we want to make sure that if I ask for a random number between $1$ and $n$, all numbers in that range will be output for some input to your function. Clearly there are a lot of tests we can run; if your algorithm passes some suite of tests it's a pseudorandom generator. Which tests to use is a very interesting and well used/studied area of computer science.

**Random Enough to Fool an Attacker:**

Now what you MAY be referring to is Cryptographially Secure Pseudorandom Generators. I think the best way to explain this is in the context of the above--here, we're using our randomness for cryptography, so when we're designing tests what we really care about is that someone won't be able to break our security by predicting what random number we picked. I don't know your level of familiarity with cryptography, but imagine we're doing a simple replacement cypher---each letter is replaced with some other letter. We want to pick these replacements randomly, so they're hard for an attacker to guess. But if he can figure out how my random number generator works, he'll be able to solve the whole cipher! Therefore, cryptographic algorithms require random number generators that are specifically hard to guess. Specific cryptographic algorithms may require additional tests (like for some sort of nice-enough distribution as mentioned above).

For this reason, CSPRGs are defined in terms of how well other algorithms solve them (which is where we finally come to your question). Specifically, let's say I have a CSPRG which I'll call R. R is a CSPRG if and only if there is NO feasible algorithm that can guess which bit it will output next. This is true even if you know all the previous bits it output!

So let's say that the first five bits my CSPRG has output are 10100. You don't know the input I used to the program, but you have access to the code I used to write my CSPRG. Then the claim is that it's impossible for you to write a program to decide if the next bit output will be 101000 or 101001.

So for reasons of cryptography, sometimes how well a pseudorandom number generator does is defined in terms of how predictable it is to other programs. Note that this still gives much of the intuition of "randomness," as (say) if you know all of the random outputs will be odd it is neither cryptographically secure nor does it pass a common-sense randomness test.
> 14 votes

# Answer
Recently I found a nice post about randomness in computation on the MIT CSAIL Theory of Computation Group blog: Can you tell if a bit is random?

The post starts with some ideas extracted from a Avi Wigderson's wonderful talk *about the power and limitations of randomness in computation, surveying the beautiful area of randomized algorithms, and the surprising connection between pseudorandomness and computational intractability*.

Then it summarizes some recent results on quantum cryptography; in particular the way to efficiently test if the output of a certain kind of device is truly random (randomness expansion protocols).

For example see the recent work by Umesh Vazirani, Thomas Vidick, Certifiable Quantum Dice (Or, testable exponential randomness expansion)

**Abstract:** *We introduce a protocol through which a pair of quantum mechanical devices may be used to generate n bits of true randomness from a seed of O(log n) uniform bits. The bits generated are certifiably random based only on a simple statistical test that can be performed by the user, and on the assumption that the devices obey the no-signaling principle. No other assumptions are placed on the devices' inner workings....*
> 4 votes

# Answer
Assuming you are talking about statistical randomness -- cryptography has other needs! -- there is a whole slew of goodness-of-fit tests that can detect whether a sequence of numbers fits a given distribution. You can use these to test whether a (pseudo) random number generator is sound (up to the quality of your test and the chosen significance).

Diehard test suites combine different methods.
> 4 votes

# Answer
This is a broad/complex topic in computer science which the other answer by SamM addresses some. Your *specific* question seems to be about if computers have what are called PRNGs, ie pseudo random number generators, how can one detect that?

The short answer is that nontrivial PRNGs are built so that their algorithms cannot be detected (derived). In general, if the PRNG is what is called "secure", even if an attacker knows the algorithm used to generate the pseudorandom sequence, they cannot guess the particular parameters used to generate the sequence. In this way pseudorandomness has many deep ties to cryptography, and one can talk about "breaking" a PRNG in much the same way that a cryptographic algorithm can be "broken". There are many research papers in this area, its an active area at the forefront of cryptography.

For "trivial" PRNGs, eg say a linear congruential generator, if the attacker knows the algorithm used to generate it and it is not generated with "bignums", the search space is "relatively small" and the attacker could theoretically also find the parameters used by the particular PRNG basically by brute force and trying all combinations.

PRNGs can be broken in practice (again depending on their "security") in some cases by running a large suite of statistical randomness tests against them. eg this is the rationale of the program "Dieharder" (by Brown). There is also an NIST suite.

The intrinsic difficulty/hardness of breaking PRNGs is not yet strictly theoretically proven but is basically associated with what are called "trapdoor" or "one-way functions" which can be computed efficiently in one direction but are "hard" to invert (reverse). There are some open problems in cryptography about randomness hardness. These questions relate closely to complexity class separations eg the famous P=?NP question.

Questions about breaking PRNGs also relate to Kolmogorov complexity, a field which studies the smallest Turing Machines that can generate sequences. breaking the PRNG also closely relates finding the "shortest" program to compute a pseudorandom sequence. And Kolmogorov complexity is undecidable to compute in general.

As Gilles points out in a comment there do exist hardware-based RNGs built out of physical electronic processes such as related to quantum noise. these if engineered correctly are unbreakable.
> 0 votes

# Answer
In fact everything a classical computer do is deterministic, in the sense that when you give them some tasks it follows them in a deterministic way. Therefore if you want to have **one** random number you can compute it accordingly to the time (based on the user's input time), but if you want to have **a set** of random numbers you can not use the time for the next numbers, because the numbers would no more be independent.

What people do is to use pseudo-random generators which have a seed, i.e. a number that is used to compute all the numbers of the pseudo-random number generator (in some more sophisticated cases of simulation or other tasks, more seeds may be needed, if more than one set of independently random numbers is needed). The seed is usually 0 or a specific number if you want reproducible results, or the time if you and different unreproducible results.

The fact that the pseudo-random number generators are good enough, lies in the fact that they follow "the basic characteristics of a pseudo-random numbers generation", in order to be computeded efficiently and behave like real random numbers:

* the produced numbers must follow an uniform distribution (from this distribution you can achieve any other distribution);
* the produced numbers must be statiscally independent;
* the sequence is reproductible (this point is imposed because of that property of the hardware of a classical computer, and it's why they are called "pseudo-random numbers");
* the period of the sequence must be large enough;
* the numbers generation must be fast.

From each number of the sequence of pseudo-random numbers a new number is computed (usually we work with integers). However there is a period, n, in a sequence of pseudo-random number generators prepared to work in a specific base with finite number of available bits to express the numbers (eg. binary). If this n wouldn't be big enough there would be serious problems, but don't worry, the computer scientists choose the seeds and other parameters of the pseudo-random generators well, in order to have a good n.

For instance, a possible pseudo-random number generator, with the linear congruential method, which is one of the oldest and best-know pseudo-random number generators algorithmns can be defined accordingly to:

it has four values:
\- x\_0 ≥ 0
\- a ≥ 0
\- c ≥ 0
\- m \> x\_0, where:

x0 is the initial value, a, c, and m are constants where: m \> a, m \> c, and it produces the sequence with the fornula:

x\_{i+1} = (a\*x\_i+c) MOD m

The values for these constants must be carefully chosen. One possibility is:

x\_{i+1} = (1664525\*x\_i + 1013904223) MOD 2^32, refs.\[1-2\]

There are other algorithms more sophisticated to generate random numbers, which avoid some of the problems of previous algorithms, that included: \[3\]

> * shorter than expected periods for some seed states (such seed states may be called 'weak' in this context);
> * lack of uniformity of distribution for large amounts of generated numbers;
> * correlation of successive values;
> * poor dimensional distribution of the output sequence;
> * the distances between where certain values occur are distributed differently from those in a random sequence distribution.

In the future, the classical computers may be united to quantum systems which can provide really random numbers, and deliver them. \[4\]

references:
\[1\] http://en.wikipedia.org/wiki/linear\_congruential\_generator
\[2\] William H., et al. (1992). "Numerical recipes in fortran 77: The art of scientific computing" (2nd ed.). ISBN 0-521-43064-X.
\[3\] http://en.wikipedia.org/wiki/pseudorandom\_number\_generator
\[4\] http://www.technologyreview.com/view/418445/first-evidence-that-quantum-processes-generate-truly-random-numbers/
> -1 votes

---
Tags: randomness, random-number-generator
---