# Question
Title: Can Circuit Value Problem or HORN-SAT be reduced to PATH problem?
PATH = {(X,R,S,T) | exists an x in S that is admissible} Where R is a relation of X x X x X, S is a unary relation of X and T is a unary relation of X aswell. An x element of X is admissible if it is in T or if there is two elements y z both admissibles, where (x,y,z) is in R.

So, is there any logspace reduction from CVP or HORN-SAT to this problem, so I can prove that PATH is P-Complete?

# Answer
Hint: Reduce from the monotone circuit value problem. Let $X$ be the set of all inputs and internal gates in the circuit. Choose $T$ and $R$ so that an element is admissible if the corresponding input or gate is *true* (each AND gate will require one triple in $R$, each OR gate will require two). Choose $S$ to be the indicator of the output gate to complete the proof.
> 1 votes

---
Tags: complexity-theory, satisfiability
---


title: Maximum Flow with Binary Capacities

text:
# Question
Title: Maximum Flow with Binary Capacities
Consider the problem of finding a maximum flow from node $s$ to node $t$ in a directed graph where each link has capacity either $0$ or $1$. What is the state of the art regarding how fast this flow can be found?

It seems that the Dinic Algorithm will accomplish this $O \left( m n^{2/3} \right)$ where $n$ is the number of nodes and $m$ is the number of vertices. From table 1 in this paper, it seems reasonable to guess this was still the state of the art in 2001. Is this the best that is currently known?

# Answer
> 2 votes
According to Goldberg's post on the Fortnow–Gasarch blog from 2012, the best algorithm for unit capacity networks is the Karzaon/Dinic/Even–Tarjan algorithm, which runs in time $O(\min(n^{2/3},m^{1/2})m)$ time. The post came after Orlin's $O(nm)$ algorithm. Goldberg and Rao extended this result to any constant capacity (their running time is linear in the logarithm of the maximal capacity).

There is a more recent line of work which gives an approximation to the maximum flow in time $O(m^{1+o(1)})$, but this doesn't make use of any bound on the capacities.

---
Tags: algorithms, optimization, network-flow
---


# Question
Title: Placing a fixed number of points on a curve to make the finite second derivative constant
I am given a 1D curve $f(x)$ that starts at $a$ and ends at $b$. I have $n$ points I have to place on the curve, and I have to place two points at $a$ and $b$, respectively. Is there a way to place points $a=x\_1\<...\<x\_n=b$ along the line so that the finite second derivative (i.e., $f(x\_{i-1})-2f(x\_i)+f(x\_{i+1})$) is constant for all $i=2,...,n-1$? In my particular problem, $f(x)=-\log(x)$ on the interval $\[\frac{1}{t},1\]$. Maybe this additional structure makes the problem more tractable.

# Answer
> 1 votes
## In a nutshell

The problem can be solved algebraically by considering the equations as defining $y\_i=f(x\_i)$. This gives $n-1$ equations with $n$ unknowns ($y\_i$ for $i\in\[2,n-1\]$, and the values of $c$ and $u$ defined below), resulting in the abitrary choice of one value. The answers are given by the formula $$x\_i=f^{-1}(f(a)-(i-1)u+c\frac{(i-2)(i-1)}{2})$$

and the value of $u=f(a)-f(x\_2)$ is determined from that of the constant finite second derivative $c$, or the reverse, with the linear relation $$f(b)=f(a)-(n-1)u+c\frac{(n-2)(n-1)}{2}$$

However I wonder if the formula used is really that of a finite second derivative.

## Full proof

*With the formula used*, your question seems rather tractable, and solvable algebraically.

Like the previous answer, I note $c$ the value of the constant finite second derivative, as defined in the question (though this is further discussed below).

You should see it as a set of equations in $y$, with $y=f(x)$. If you note $y\_i=f(x\_i)$, you get a set of $n-2$ equations $$y\_{i-1}-2y\_{i}+y\_{i+1}=c\\;\\; \text{ for }i\in \[2,n-1\]$$ with $n-1$ unknown : $y\_{i} \text{ for }i\in \[2,n-1\]$ and $c$, given that you have $y\_1=f(a)$ and $y\_n=f(b)

This probably means an infinity of solutions, which may means that you can choose arbitrarily one of the values, for example that of $c$. I have not worked out the equations.

However, given the strictly monotonically decreasing function $f$ of your example, you have the additional constaints that: $$ \forall i\in\[2,n-1\], \\;\\;y\_i\in(f(a), f(b)) \\;\wedge\\; y\_i\>y\_{i+1} $$

One way to start resolving it is by defining $u\_i=y\_i-y\_{i+1}$ and $v\_i=y\_i-y\_{i+2}$ for $i\in \[1,n-2\]$. Then the equations become $y\_i-2(y\_i-u\_1)+(y\_i-v\_i)=c$ which simplifies into $2u\_i-v\_i=c$, from which we derive $v\_i-u\_i=u\_i-c$.

From the definition of $u\_i$, $u\_{i+1}$, and $v\_i$, we derive $u\_{i+1}=v\_i-u\_i$. Hence $u\_{i+1}=u\_i-c$. From this recurrence relation we get $u\_i=u-(i-1)c$, where $u$ is defined as $u=u\_1=y\_1-y\_2$.

So we now have the simpler recurrence relation: $y\_{i+1}=y\_i-u\_i=y\_i-(u-(i-1)c)$, i.e., $y\_{i+1}=y\_i-u+(i-1)c$, from which we get \begin{align} y\_i&=y\_1+\sum\_{k=1}^{i-1}{u\_k} \\ &=y\_1+\sum\_{k=1}^{i-1}{-u+(k-1)c} \\ &=y\_1-(i-1)u+c\sum\_{k=0}^{i-2}{k} \\ y\_i&=y\_1-(i-1)u+c\frac{(i-2)(i-1)}{2} \end{align} This last formula is valid for $i\in\[1,n-1\]$, since the recurrence formula is defined for $y\_{i+1}$ and the equations used were defined for all values of $i$ up to $n-2$.
We must now consider $y\_n$. Since $v\_{n-2}-u\_{n-2}=u\_{n-2}-c$, we get $y\_n=y\_{n-1}-(u\_{n-2}-c)$. Since $u\_{n-2}=u-(n-3)c$, we finally obtain $\begin{align} y\_n&=y\_1-(n-2)u+c\frac{(n-3)(n-2)}{2}-u+(n-3)c+c \\ &=y\_1-(n-1)u+c\frac{(n-2)(n-1)}{2} \end{align} $

Hence our formula for $y\_i$ is correct for all $i\in\[1,n\]$.

*Note: a much simpler technique for $y\_n$ would be to consider an extra point at $y\_{n+1}$ on the curve, so as to have more equations. But all this was already written when I thought of it.*

Considering that we have the last constraint $y\_n=f(b)$, we can use it with the equation for $y\_n$ to determine $u=y\_1-y\_2$ if we wish to choose $c$, or to determine $c$ if we rather choose $u$.

This is easily rephrased into the result given at the beginning of this answer. Then it should be easy to apply it to the example in the question. However, I do wonder whether all this is useful, because I am not sure this is the question you intended to ask.

The reason is that the formula given in the question is not the formula of the finite second derivative. The proper formula is something like: $$4\times\frac{f(x\_{i-1})-2f(x\_i)+f(x\_{i+1})}{(x\_{i+1}-x\_{i-1})^2}$$

See for example higher-order finite differences in wikipedia. Though I am not sure that even this corrected formula is meaningful as, the formula normally given assumes that $x\_i= (x\_{i-1}+x\_{i+1})/2$. But the expression you use is somewhere between the formulae for forward and backward finite differences, and should thus be usable with some meaning.

Thus, if I am correct, you should edit your question to make it consistent, either by removing the reference to the finite second derivative, or by using the proper formula for it.

# Answer
> 0 votes
Here is one approach. Set $x\_1=a$, $x\_2=a'$, choose a fixed value $c$ that you want the second derivative to have, and then define a sequence so that $f(x\_{i-1})-2f(x\_i)+f(x\_{i+1})=c$ for all $i$. In particular, this can be achieved by setting

$$x\_{i+1} = f^{-1}(c-f(x\_{i-1})+2f(x\_i)).$$

Iterate this until you get to $x\_n$. Now if you just choose $a',c$ haphazardly, then the final value $x\_n$ may be larger or smaller than $b$, so this doesn't immediately solve the problem.

Instead, our goal will be to find $a',c$ that makes this work. Define $g(a',c)$ to be the value of $x\_n$ you get when you use the values $a',c$ above. For your class of functions, $g(a',c)$ should be a monotonically increasing function of $a'$ and of $c$, so you can now try to find $a',c$ such that $g(a',c)=b$ by using any standard method for such a problem -- e.g., binary search, Newton's method, etc.

---
Tags: algorithms
---


# Question
Title: What is required for universal analogue computation?
What operations need to be performed in order to do any arbitrary analogue computation? Would addition, subtraction, multiplication and division be sufficient?

Also, does anyone know exactly what problems are tractable using analogue computation, but not with digital?

# Answer
Unfortunately, there is no "universal" concept of universality in analogue computing. However, this paper by Delvenne proposes a unifying formalism for universality in discrete (e.g. Turing Machines) and continuous (e.g. differential equations) dynamical systems and reviews some universal systems studied in the literature. Here is an excerpt from the paper which informally describes the procedure for proving universality of a dynamical system:

> But most dynamical systems studied in mathematics and physics have an un-countable state space, e.g., cellular automata, differential equations, piecewise linear maps, etc. Examples of those systems have been proved universal. Their halting problem is imitated from the Turing machine in the following way. We choose a particular countable family of initial states, and countable family of final states, or final sets of states. Then the halting problem is given an initial state and a final state/set of states, whether the trajectory starting from the initial state will reach the final state/set of states. More specific examples are given in Section 7.

Jean-Charles Delvenne, What is a universal computing machine?, Applied Mathematics and Computation, Volume 215, Issue 4, 15 October 2009, Pages 1368-1374
> 8 votes

# Answer
I don't think the question can be answered unless we have a definition of what kind of computations we are talking about.

Universality of a machine model w.r.t. a class of computationw means that any computation in that class can be computed by a machine. Unless you define the class of "arbitrary analogue computations", we cannot answer what is universality w.r.t. to them.

Now, the functions you have listed will only give you polynomials and their quotient which is a rather small class of real functions, you cannot even compute simple functions like $2^x$, $\lfloor x \rfloor$, $\sqrt x$, ... using them.

---

If your question is if there are physical systems that starting from an initial state will reach another state in some time and if that is always computable, then the answer depends on what kind of physics we are talking about, and what it means to set up an initial configuration and observing the result, etc.

If we are just talking mathematically about classical physics (we can set any initial configuration to infinite precision and without any considerations about things like energy needed to set up the configuration and observing the result is similarly from mathematical point of view) then it has been know for long time that there are differential equations about computable functions s.t. their solution is not computable, see Marian B. Pour-El, and J. Ian Richards, "Computability in Analysis and Physics", 1989.

An interesting case is if the n-body problem is computable (and if I remember correctly the answer is no, at least for $n\>4$).

Generally, if we can just check equality of two real numbers that gives a function which is not continuous w.r.t. typical typologies of information about real numbers and therefore cannot be computed by a Turing machine since any function (including higher type functions) that a Turing machine can compute is continuous (w.r.t. the topology of information).
> 11 votes

# Answer
**TL;DR:** *If by “analogue computers”, you mean differential analysers, the answer is adders, constant units and integrator. Bournez, Campagnolo, Graça and Hainry have shown in 2006 (paywalled / free reprint) that an idealized model of it allows to compute all the computable functions in the framework of computable analysis, and this model only needs these 3 kind of units.*

## Transcendental functions

The set of operation you propose (addition, multiplication, subtraction, and division), even completed by root equation is by definition not sufficient to compute any transcendental function. Transcendental functions includes very common functions, like $\sin$, $\exp$, $\log$. However, as discussed below, some analogue computer model allow to compute transcendental functions and, basically all real functions computable by a Turing machine.

## Analogue computing models

As stressed by others, the concept of “universal computation” is less clear for analogue computers than for standard computer, where different natural notion of computability in different computing models where found equivalent in the 1930’s (see Wikipedia page on Church Turing Thesis for details).

In order to define such a universality, one should first define a good model for analogue computation, and it is a difficult task, since the model should be idealized and and natural enough to be useful, but its idealization should not give unrealistic power to the model. An example of such a good idealization is the infinite tape of Turing machines. The problem with analogue computers comes with real numbers which could allow to build unreasonable stuff like the Zeno machine. However, several such models have been proposed and used in the literature (The GPAC is the main subject of this answer, but I try to be complete in the list below, without any hypercomputer):

## Power of the GPAC model

In his 1941 paper, Shanon introduced the GPAC to model differential analysers.This model only needs 3 kinds of interconnected units (constant units, adders and integrators. Multipliers can be built from integrators and adders.) He showed that the set of functions which it generates is the set of algebraic differential functions, but excludes the hypertranscendental functions. It means that the $\Gamma$ and $\zeta$, which are Turing-computable cannot be generated. In other words, no differential analyser will ever have an output $y(t)=\Gamma(t)$, ant it seemed for a long time that such an analogue computer is not “universal”, since it cannot generate some reasonable computable functions, used by mathematicians.

However, in 2004, Daniel Silva Graça showed that the previous model, based on instantaneous computation is too restrictive. If one define the computability of a function $f$ differently, allowing $y(t)$ to converge towards $f(x)$, for an input $x$, then the $\gamma$ and $\zeta$ functions are computable by a GPAC. Bournez, Campagnolo, Graça and Hainry then showed in 2006 (paywalled / free reprint) that an idealized model of it allows to compute all the computable functions in the framework of computable analysis.

Bournez, Graça and Pouly then showed in 2013 that these analogue computers can efficiently simulate a Turing machine (p.181 of a big pdf) and, in 2014, that the P and NP complexity classes are equivalent in this model.
> 5 votes

# Answer
Would it be useful to propose that a universal analog system could be modelled by an infinite neural net i.e. Any other analog system input/output values can be replicated matched neural network for a given operation, and operations can be chained as required?

While I did formulate this thought on my own, a subsequent search has shown a similar proposal:

> What emerges is a Church-Turing-like thesis, applied to the field of analog computation, which features the neural network model in place of the digital Turing machine (see here).

Arguably then all you would need is the primitive operations to move value from one node to another. Off the cuff that could be plus, minus and divide to get ratio between connections.

Now as to the intractable problems, do look at where neural networks have been successfully applied, or are under performing due to being implemented on a a discrete computer.

(and apologies if my nearly lay person view on this topic is glaringly obvious)
> 3 votes

---
Tags: computability, computation-models, turing-completeness
---


# Question
Title: Red-black tree. Adding a red child to a red node with a black sibling
According to my lecture notes, adding a red child to a red node with a black sibling in a red-black tree, is equivalent to changing a 3-node into a 4-node in a 2-3-4 tree. I've built several red-black trees with different values to try to get to this situation, but I never seem to get to the situation where I have a red node with a black sibling, and where the value to be inserted will be inserted below the red node. I'm starting to ask myself if this situation could ever happen in a red-black tree?

# Answer
> 4 votes
Assume we have a black node $N$ with black child $L$ and red child $R$. Thus we have a red and black sibling. Recall that in a red-black tree all paths from root to leaf must have the same number of black nodes. The path $N-L$ contains two black nodes, the path $N-R$ just one. That means that both children of $R$ must be present, and must be black. So indeed, we can not add a new red child to $R$ because it already has black children. However, what can happen is that one of these black children turns red as consequence of a flag-flip. We then are in the situation you describe.

---
Tags: data-structures
---


# Question
Title: How does augmenting linear bounded automata tape alphabets increase memory?
A linear bounded automaton is a Turing machine that is restricted by memory.
How would augmenting the tape alphabet of a linear bounded automaton increase its memory? While the memory that the automata can use is as size of the input?

# Answer
If you consider an input, hence a tape, of size $n$ and a tape alphabet of $b$ symbols, you get $b^n$ configurations possible on your tape. If you measure memory in bits, the memory size is the base 2 logarithm of the number of configurations, very simply because that is the number of bits required to have the same number of configurations (rounding up to the next integer, because half-bits have not been invented yet).

So the tape memory of your linear bounded automaton (LBA) is $\log\_2 b^n$, which is equal to $n\log\_2 b$.

Augmenting your tape alphabet does not increase your memory very fast. Doubling the size of the alphabet is equivalent to a single extra bit per cell, i.e. adding $n$ bits total. The positive side of it is that it does not take many bits per cell of the tape to have a huge alphabet.
> 5 votes

---
Tags: turing-machines, linear-bounded-automata
---


# Question
Title: Is the language given by this CFG regular?
```
 S → AB | C
 A → aAb | ab
 B → cBd | cd
 C → aCd | aDd
 D → bDc | bc

```

How can I prove that this language is regular or not? I need your help. It also has two leftmost derivations. Does this help me to prove it?

# Answer
The language denoted by your grammar is:

$L=\\{a^nb^nc^md^m | n\geq 1,m \geq 1\\}\cup \\{a^nb^mc^md^n | n\geq 1,m \geq 1\\}$

Hint: You can prove that this language is not regular using the pumping lemma.

Spoiler alert:

> Use the word $\sigma= a^Nb^Mc^Md^N$ with $N\neq M$ and $K=N+M$ your pumping lemma constant.
> 0 votes

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


title: Hamming Distance, Bit message

text:
# Question
Title: Hamming Distance, Bit message
My professor told us to try and remember the equation used for an upcoming exam, however I'm struggling to fit the equation into the question:

https://i.stack.imgur.com/RoPYG.png (need a high reputation to post image)

From the above information can anyone tell me how I'm supposed to slot in values in order to work out the following practise question:

Sixteen-bit messages are transmitted using a Hamming code. How many check bits are needed to ensure that receiver can detect and correct single-bit errors?

Answer given to us is "5 check bits for a total of 21 bits".

Can anyone help me out with this please, as I expect it will come up on the exam, bu with another bit message size.

# Answer
> 1 votes
The professor is asking you to find the lowest r such that the equation is true. At $r=1$, $2^1\<17+1$,
$r=2$, $2^2=4\<17+2=19$...
$r=4$, $2^4=16\<17+4=21$
and finally $r=5$, $2^5=32\geq17+5=22$.

---
Tags: discrete-mathematics, computer-networks
---


# Question
Title: Intuition for PH notation in Arora-Barak's Computational Complexity
For the definition of polynomial hierarchy:

$x \in L \Leftrightarrow \exists u\_1 \in \\{0, 1\\}^{q(|x|)}\forall u\_2 \in \\{0, 1\\}^{q(|x|)} \cdots Q\_i u\_i \in \\{0, 1\\}^{q(|x|)} M(x, u\_1, \ldots, u\_i) = 1$

What does the notation of $M(x, u\_1, \ldots, u\_i)$ mean? The definition used for $\mathcal{NP}$ is $M(x, \alpha)$ where $\alpha$ is the certificate. What is the intuition for what the $u\_i$ signify in terms of the TM $M$?

# Answer
The notation $M(x,u\_1,\ldots,u\_i)$ stands for a polytime Turing machine with $i+1$ inputs, applied to the inputs $x,u\_1,\ldots,u\_i$. There are many ways of implementing Turing machines with several different inputs, and from this perspective they are all equivalent, so pick one. (Some examples: several input tapes, inputs separated by special separator symbol, oracle mechanism for obtaining $j$th input.)

Your definition is for languages in $\Sigma\_i^P$. When $i = 1$, you get $\mathsf{NP}$. A language $L$ is in $\mathsf{NP}$ is we can verify that $x \in L$ using a polytime Turing machine given a polysize hint $\alpha$. If the verifier is $M$, then this means that $$ x \in L \Leftrightarrow \exists \alpha \in \\{0,1\\}^{q(|x|)} M(x,\alpha) = 1, $$ where $q$ is a polynomial bounding the size of the witness.

For $i \> 1$ there are more quantifier alternations, and you can think of it as a game between two players: the *existential* player is trying to prove that $x \in L$, while the *universal* player is trying to prove that $x \notin L$. The game proceeds in $i$ rounds, in which the players alternate giving polysize "witnesses" $u\_1,\ldots,u\_i$. After $i$ rounds, a judge $M$ is shown the transcript, and makes a verdict; $M(x,u\_1,\ldots,u\_i)=1$ means that the judge thinks that $x \in L$. A *winning strategy* for either player is a strategy that guarantees that the verdict will be favorable to them. A language is in $\Sigma\_i^P$ if there exists such a polytime judge $M$ such that if $x \in L$ then the existential player has a winning strategy, while if $x \notin L$ then the universal player has a winning strategy.

Here are two examples:

1. $SAT \in \Sigma\_1^P$. In this case the judge $M$ takes as input a formula $x$ and a witness $w$, and checks that $w$ is a satisfying assignment for $x$. If $x \in SAT$ then there is a satisfying assignment, and so the existential player can guarantee that the judge declares $x \in SAT$. If there is no satisfying assignment then the universal player (who is silent) can guarantee that the judge declares $x \notin SAT$.
2. Circuit minimization $CMIN \in \Sigma\_2^P$: a pair $(A,k)$ is in $CMIN$ if $A$ is a circuit encoding a function $f$ which can be computed by a circuit of size at most $k$. The judge $M$ takes as input the pair $(A,k)$, a witness $B$ from the existential player, and a witness $x$ from the universal player, and accepts if $B$ is a circuit of size at most $k$ that agrees with $A$ on the input $x$. If $(A,k) \in CMIN$ then the winning strategy of the existential player is to produce a circuit $B$ of size at most $k$. If $(A,k) \notin CMIN$ then the winning strategy of the universal player is, for each circuit $B$ of size at most $k$, to find an input $x$ on which $A$ and $B$ disagree.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: Efficiently enumerating all paths from i to j of given length in a graph
I've been trying to efficiently solve this problem : given a integer p \> 0 and a directed graph whose nodes are 0, ..., N-1, enumerate (not simply count) all the paths (not necessarily elementary) from a node i to a node j of length p. For instance, i-\>j is of length 2 if the edge i-\>j exists, i-\>k-\>j is of length 3, etc...). The graph is either given as an adjacency matrix or adjacency lists. In my very special case, I'm searching for cycles 0-\>...-\>0 of given length, but I'm pretty sure I'm gonna need the more general case i-\>...-\>j.

Right now, I'm dynamically storing paths from k to j of length q in a matrix Z\[k\]\[q\], and since I need Z\[i\]\[p\], I first compute all the Z\[j\]\[p-1\] for i-\>j, then append i to them.

The problem is that this approach uses an awful lot of memory and doesn't scale very nicely for large graphs. Any advice on this ?

# Answer
It's not possible to solve this problem "efficiently". There can be exponentially many paths of a given length, so enumerating all of them is not feasible in large graphs.

Your dynamic programming approach is a pretty good one, though you might be able to improve it by not storing the paths explicitly but instead storing the paths as linked lists or using pointers, so that you only use $O(1)$ storage per path, letting paths share their common suffixes (if you do not do this already).
> 3 votes

---
Tags: algorithms, graphs, enumeration
---


title: Is $BQP$ in $P^{NP}$?

text:
# Question
Title: Is $BQP$ in $P^{NP}$?
I read in the introduction of this paper

http://www.scottaaronson.com/papers/uncompute.pdf

that there is a problem $B$ such that $BQP^B \not\subset P^{NP^B}$, and that $B$ is in $BPP$. But, using the fact that $BPP$ is in $BQP$ and that $BQP$ is low for itself (i.e. $BQP^{BQP}=BQP$), as proved in

http://arxiv.org/pdf/quant-ph/9701001v1.pdf

can we state that $BQP^B \subseteq BQP^{BPP} \subseteq BQP^{BQP} = BQP$ and thus $BQP \not\subset P^{NP^B}$ and finally $BQP \not\subset P^{NP}$?

# Answer
I think your logic is valid, but not sound.

The problem is that the oracle $B$ is not what's in $BPP$. The question being asked about $B$ is what's in $BPP$.

When Scott Aaronson's paper "Quantum Lower Bound for Recursive Fourier Sampling" says

> Green and Pruim \[10\] gave an oracle B for which $BQP \not\subset P^{NP}$. \[...\] while Green and Pruim’s problem is in BPP

the noun phrase "Green and Pruim’s problem" is not refering to $B$.

# The Problem

The referenced paper "Relativized Separation of EQP from $P^{NP}$" defines a problem $L$.

The input to $L$ is a predicate $B$ and a range parameter $n$. The predicate $B$ accepts natural numbers between $2^n$ and $2^{n+1}$, and returns either true or false for each. It is promised that $B$ will return true for either exactly $\frac{1}{4} 2^n$ of the allowed inputs, or else for exactly $\frac{3}{4} 2^n$ of them.

The output $L(B, n)$ is the classification of the relevant range of $B$ into the promised quarter-true or quarter-false categories.

# The Separation

A $P^{NP}$ machine can't compute $L$ because $B$ has too many inputs to check. There's exponentially many spots to check (w.r.t. $n$), so eventually any accepting path must be leaving a huge proportion unchecked. An adversary can start with some arbitrary accepting input, simulate the proposed $P^{NP}$ machine to find out which inputs the machine checks on one path that accepts that input, then toggle inputs that that particular path didn't check to create a should-be-non-accepting input that fools the machine into accepting.

(Note: I implicitly assumed that $B$ could be inspected *only* by querying it. This fails e.g. if $B$ is provided as a circuit diagram. That's why $B$ will end up being our oracle.)

A $BPP$ machine can compute $L$ easily: just sample $B(x)$ at a random allowed $x$ and return that. The odds of getting it wrong are $\frac{1}{4}$, which is less than the typical-but-arbitrarily allowed $\frac{1}{3}$. You can sample more to make it more reliable.

A $BQP$ machine can also compute $L$, with the $BPP$ strategy.

An $EQP$ machine can use Grover's algorithm to solve $L$ with certainty. (Also works for BQP, but overkill.)

# The Oracle

So we have a decision problem $L(B, n)$ that separates $P^{NP}$ and $BQP$, but relying crucially on the assumption that the machine is limited to querying $B$. Furthermore, we don't have enough input space to specify all of $B$'s outputs, and we can't use a compact representation like a program or circuit because that violates the only-querying-allowed assumption. Thus we're forced to cheat and give $B$ to the machine as an oracle.

This raises the issue of how to pick $B$. What if we picked a weak $B$, such as one where $L(B, n)$ is always $0$? Something that a $P^{NP}$ machine could be hardcoded into defeating? Fortunately we can get around that by choosing $B$ with diagonalization: iterate all $P^{NP}$ machines and use the $2^i$ to $2^{i+1}$ range of $B$ to defeat the $i$'th machine by the adversarial method I explained earlier.

Thus $B$ is an oracle that tells you something about how $P^{NP}$ machines try to query predicates, *not* an oracle about solving some problem in $BPP$. So it is not necessarily the case that $B \subset BPP$. It's probably *not* the case, actually, since computing a bounded version of $B$ involves simulating exponentially many $P^{NP}$ machines.
> 3 votes

---
Tags: quantum-computing, oracle-machines, relativization
---


title: The meaning of relativization

text:
# Question
Title: The meaning of relativization
I don't understand the notion of relativization. I expose with an example. Consider a class $A$ that contains $P$, e.g. $NP$. Why $P^A$ is not necessarily equal to $A$? I can naively think that if one can decide any problem in $A$, one can also decide any problem that uses polynomially many steps in a Turing machine plus calls to $A$. One can have at most polynomially many calls to $A$, thus $P^A$ seems there is only a polynomial overhead compare to $A$. If $A$ is $NP$, I could give a certification for all the (polinomially many) oracle calls, and also easily give a certification of the polynomial rest of the computation. I understand that if it is true, then $NP$ is the same as $coNP$, both being contained in $P^{NP}$ from the polynomial hierarchy. So, where is the error in my naive argument?

# Answer
Take $A=NP$, as you requested. $P^{NP}$ is not necessarily equal to $NP$.

Let me give an example why not. Consider TAUTOLOGY (given a boolean formula $\varphi$, is it true for all possible assignments to the variables?). TAUTOLOGY is known to be co-NP-complete. Therefore, TAUTOLOGY most likely is not in NP, since if TAUTOLOGY were in NP, it would follow that NP = co-NP, which is widely suspected not to be the case.

However, TAUTOLOGY is certainly in $P^{NP}$. Here's why. Given an oracle for SAT, we can solve TAUTOLOGY as follows: Given $\varphi$, query whether $\neg\varphi$ is in SAT; then flip the answer (if $\neg\varphi$ is in SAT, answer "no, $\varphi$ is not in TAUTOLOGY"; if $\neg\varphi$ is not in SAT, answer "yes, $\varphi$ is in TAUTOLOGY"). This shows how to solve TAUTOLOGY in polynomial time given an oracle for SAT, and SAT is in NP, so this shows that TAUTOLOGY is in $P^{NP}$.

So TAUTOLOGY is an example of a problem that is in $P^{NP}$, but probably isn't in NP (unless NP = co-NP). Hopefully this helps illustrate why NP is not the same as $P^{NP}$.

If not, here's a little more intuition. NP is a particular class. $P^{NP}$ is the class of problems that can be solved by querying an oracle for NP, possibly many times. The "many times" part is the key difference between NP and $P^{NP}$. A (many-one) reduction between two NP problems can only query a NP-oracle once, while $P^{NP}$ allows you to query the oracle as many times as you like. That seems to be a lot more powerful, and it's the reason why $P^{NP}$ seems to be a bigger class than NP.
> 5 votes

# Answer
Why might $P^A$ not equal to $A$?

**$A$ might be weaker than $P$**

$P^A$ can't be weaker than $P$, but $A$ might be. For example, if $A$ is the complexity class of linear-time problems $O(n)$ then $P^A = P^{O(n)}=P$.

**$A$ might have different strengths than $P$**

For example, consider $B=O(1)^{3SAT}$ and $A=3Coloring$. The *only* problem $A$ can solve is 3-coloring. It can't solve 3-Sat. $B$ can solve 3-sat, and various constant time problems, but it can't solve 3-coloring because it doesn't have enough time to do so directly or to translate the problem into 3-sat.

On the other hand, $B^A = {O(1)^{3SAT}}^{3Coloring}$ can solve *both* 3-sat and 3-coloring, so it's stronger than either $A$ or $B$ individually.

In the case of $P$, a class with different strengths could be the class of problems that takes $O(n)$ space. Some problems in $P$ require more-than-linear space, and some problems that require $O(n)$ space use exponential time. So $P^{O(n) space}$ gains both the powers of $P$ and $O(n) space$, making it larger than either of them individually.

**$A$ and $P$ might synergize into something better**

For example, $P^{NP}$ can trivially solve $coNP$ problems, but it's suspected that $P \subset coNP$ and $NP \neq coNP$ and $(P \cup coNP) \not \subset coNP$.

This is even more striking if you think of it as $NP^{NP}$. Complexity classes don't have to be low for themselves.
> 2 votes

---
Tags: complexity-theory, oracle-machines, relativization
---


# Question
Title: How to properly solve this Hidden Markov Model problem?
I got a an exercise problem which should be seen as a HMM scenario and argument some statements. However I'm quite confused about how to properly solve and argument my solutions.

Problem tells:

*Imagine you want to determine the annual temperature centuries of years ago, when of course there wasn't any thermometer or records. So, nature as an evidence is a worth to try resource, we may achieve it by watching at tree's inside rings. There's reliable evidence suggesting that there's a relation among the rings inside trees and temperature. There will be 2 different temperature states, WARM (W) and COLD (C) and three discretized tree rings sizes: SMALL (S), MEDIUM (M) and LARGE (L). Some researchers have provided two matrixes:*

$\begin{bmatrix}.7 & .3\\\.4 & .6\end{bmatrix}$

*As transition matrix, so the probability of remaining in COLD state if COLD is present is $.6$ and the probability of passing from COLD to WARM is $.7$.*

*Also, a second matrix with the relation among the ring's size and the temperature over the year:*

$\begin{bmatrix}.1 & .4 & .5\\\.7 & .2 & .1\end{bmatrix}$

So, problem asks what I should do to calculate the chance of a sequence (for example):

> **SSSMMLLL**

To happen. I considered multiplying the 4 distinct cases and so generate a Markov matrix with transitions among trees ring sizes. However I never got a matrix whose rows sum 1 as it should.

How could I solve this?

# Answer
> 3 votes
The Viterbi algorithm solves the problem. It calculates the most probable state sequence for an HMM given an observation sequence. In your example, ring sizes are observations and temperatures are hidden states. I suggest to refer to the Wikipedia article about the Viterbi algorithm (http://en.wikipedia.org/wiki/Viterbi\_algorithm). It contains an example of an HMM with 2 hidden states and observations with 3 discrete probabilities.

# Answer
> 1 votes
I think since likelihood of observation sequence was asked in the question you should use the *Forward Backward probabilities*. This uses a technique of dynamic programming.

Reference to wiki page

---
Tags: artificial-intelligence, hidden-markov-models
---


title: Algorithm to find all paths of length k

text:
# Question
Title: Algorithm to find all paths of length k
Consider the following definition of 3-friends:

person 1 is 3-friends with person 2 if they are direct friends or person 1 is friends with a friend of person 2 or person 1 is friends with a friend of a friend of person 2.

In graph-theoretical terms, person 1 is a 3-friend with another person 2 if there is a path of length 1, 2 or 3 from vertex 1 to vertex 2.

Is there an efficient algorithm to find all the paths between say person 1 and all its 3-friends? (I.e. all the paths of length 3, all the paths of length 2, all the paths of length 1).

Or the only option is an exhaustive search?

# Answer
You are asking for *all* paths of length 3 emanating from a given vertex. There are $O(n^3)$ of these, the worst case being a clique. If you want to actually output all of them, then *exhaustive search* (on the adjacency matrix) is the perfect algorithm, and it is efficient, since there are only $O(n^3)$ paths (or less).
> 5 votes

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


title: Ordered knapsack problem?

text:
# Question
Title: Ordered knapsack problem?
I'm trying to find the name of this problem, and with it a reasonable algorithmic solution.

Setup: There are $n$ items with weights $w\_1,\dots,w\_n$, and $m\<n$ buckets with target weights $a\_1,\dots,a\_m$, satisfying $\sum\_iw\_i=\sum\_ja\_j=1$. The goal is to find an assignment $f:\\{1,\dots,n\\}\to\\{1,\dots,m\\}$ of the weights to the buckets such that $f$ is nondecreasing (the weights have to be in the same order as the buckets) and the sum of the weights in each bucket is "close" to the target for that bucket.

The sense of "closeness" is up to the implementation (whatever is easiest to model), but for concreteness let's suppose this is least-squares error; then we can define the error of a given assignment as $\varepsilon(f)=\sum\_{i=1}^m(\sum\_{j:f(j)=i}w\_j-a\_i)^2$, and the goal is to find the $f$ that minimizes $\varepsilon(f)$.

This problem seems similar to the knapsack problem, but there are some differences in the constraints and I don't know if this is also NP-complete. Does this problem have a name or reduce to a named problem?

# Answer
> 2 votes
The fact that $f$ is non-decreasing makes the problem much easier, solvable in polynomial time.

You have to find a way to split the weights so that weights $1,\ldots,x$ go to bucket $1$, weights $x+1,\ldots,y$ go to bucket $2$, weights $y+1\ldots,z$ go to bucket $3$, and so on.

If you define $D(i,j)$ to be the best way to assign weights $j,\ldots,m$ to buckets $i,\ldots,n$ you can apply dynamic programming.

---
Tags: complexity-theory, terminology, reference-request, optimization, knapsack-problems
---


# Question
Title: Checking a property of all of the cycles in a graph
Suppose $G= (V,E)$ is a directed graph with weights on the edges. I would like to check if $G$ has the following property: if $C \subset E$ is the set of edges in a cycle of length at least $3$, then the weight of at least one of the edges in $C$ is zero. Can this be done in polynomial time?

# Answer
> 1 votes
Remove all edges with weight 0 and check that you then have only cycles of length 2 at most that are left.

---
Tags: algorithms, graphs, weighted-graphs
---


# Question
Title: What are GEN and KILL statements in dataflow analysis?
In data flow analysis, is GEN statement where a variable is used and KILL statement is where variable is redefined?

# Answer
> 11 votes
Dataflow analysis works on sets of *facts*. GEN points are points in the graph where one of the facts you care about becomes true, and KILL points are points in the graph where one of the facts you care about becomes false.

The GEN and KILL points thus depend on the facts you care about.

For example: if you were doing a constant propagation analysis you might care about the fact that variable `x` has the constant value `3`. Any point in the graph where `x` is assigned the value `3` is a GEN point. Any point in the graph where `x` is assigned a constant value other than `3` is a KILL point.

If you were doing *reaching definitions*, and `x` is defined in two different places then the facts you are interested in are (1) "`x` from the first definition may be available here" and (2) "`x` from the second definition may be available here." In this case the point where `x` is first defined is a GEN point for fact (1) and a KILL point for fact (2). The point where `x` is second defined is a GEN point for fact (2) and a KILL point for fact (1).

As a third example, suppose you were doing a *liveness* analysis. This is a backwards analysis. In this case the places where `x` is used are GEN points, because `x` is live at the statement where it is used, and at some of the statements above the statement where it is used. The definitions of `x` are KILL points, because the previous definitions of `x` are no longer needed after this node (as well as at along all the nodes along the reverse path until you reach a GEN statement higher in the graph.)

---
Tags: compilers, formal-methods, software-verification, data-flow-analysis
---


title: Is this problem NP-hard?

text:
# Question
Title: Is this problem NP-hard?
Good day. Subset sum selection problem is NP-hard.

I trying to solve following problem: Input: a grid NxN and subset size K and radius R. Every entry in grid contains a value. Solution: subset of size K, so that sum of all selected items and items within radius(when selected items is in center) is maximal.

Here example(with radius 1 and K=2):

On this picture 2 orange items selected. all blue and green items are added to sum also, but green item, added only once( in other words any item on grid can be taken once in final sum).

So sum of selected subse: 2xOrange(selected)+9xBlue(adjacent)+1xGreen(taken only once into account).

When radius is 0 the problem is trivial: Just choose K best items, But when radius 1 or more is following problem NP-hard?

If yes, what is the best way to prove it ?

If no, is there an algorithm that return optimal solution?

Many thanks for help!

# Answer
> 2 votes
It seems very likely that it is $NP$-complete.

A good "trick" to tackle a problem like this would be to create an instance where there are $X$ very big numbers in the grid and you're allowed to choose $X$ items. Choose the goal amount so that you need all of these big numbers, and this constrains you to "use" all of the $X$ items to cover the $X$ big numbers. The only freedom is in where exactly you pick the position of the rectangles relative to the big numbers.

A good candidate for a reduction would be Vertex Cover, which is $NP$-complete even for planar, 3-regular graphs. You could fix some embedding of the graph in the plane, and then place large numbers on the edges, so that you need to collect these numbers to win. You'd make $K$ so large that you can cover almost all of the big numbers in each edge, but not quite. Placing a rectangle at the position of a vertex would cover numbers in all of the incident edges.

I'll leave it to you to figure out the details (since you only asked for a "way" to prove it) but I'm pretty sure this is a feasible approach.

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


title: Lamarckian and Genetic algorithm

text:
# Question
Title: Lamarckian and Genetic algorithm
Yesterday I've done some research how to optimize genetic algorithm and I've encountered a very interesting theory that we can use Lamarckian theory (adaptive theory) to optimize the neural network. But I still didn't understand how can it be done? What I've read from some source to optimize the genetic algorithm we must do some adaptation to the parents before we do the mating (crossover & mutation) but how is exactly the adaptation done? For example, if I have a genetic algorithm population to train a neural network, how can I alter the chromosome of the population to be adapted to the environment? Is it based on the error of the output or how?

# Answer
> 2 votes
In fact, you're talking about Memetic Algorithms. In the case of a neural network, supposing you have training samples, the individual learning may be done through an iteration of backpropagation. If you don't have training examples, you may apply some noise to the weights and keep the modification only if it performs better (hill climbing). Actually, any local search algorithm could be used. Regarding the frequency of individual adaptation, this is currently a research topic, but you can find works that suggest applying the adaptation to all individuals at every generation as well as other works suggesting to increase this frequency gradually, since the last generations are the ones which need more fine tuning. Genetic algorithms are very good to find some good global solution, while local search is very good to find the optimal local solution. So the trick is to find the optimal solution **region** with GA and fine tune with local search.

---
Tags: algorithms, artificial-intelligence, genetic-algorithms
---


# Question
Title: What does "context" in "context-free grammar" refer to?
There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble:

What *context* is it free of?

To investigate, I Googled "context sensitive grammar" but I still failed to find what the "context" was all about.

Can someone please explain what the `context` term refers to in these names?

# Answer
> 44 votes
You are right, there always is a context in some sense. I don't think you can understand what "context" means in "context-free" without understanding a production.

A production is a substitution rule. It says that, to generate strings within the language, you can substitute what is on the left for what is on the right:

```
A -> xy

```

This means that the abstract sequence A can be replaced by the character "x" followed by the character "y". You can also have more complex productions:

```
zA -> xy

```

This means that the character "z" followed by the abstract sequence A can be replaced by the characters "x" and "y".

A context-free production simply means that there is only one thing on the left hand side. The first example is context-free, because A can be replaced by "x" and "y" no matter what comes before or after it. However, in the second example, the character "z" has to appear before the A, and then the combination can be replaced by "x" and "y", so there is some context involved.

A context-free grammar is then just a grammar with only context-free productions.

The second example is actually an example of an unrestricted production. There is another category that is between context-free and unrestricted called "context-sensitive". An example of a context-sensitive production is:

```
zA -> zxy

```

The difference being that what comes before A (and after) on the left hand side has to be preserved on the right. This effectively means that only A is substituted, but can only be substituted in the proper context.

# Answer
> 11 votes
Consider the rule $$ A \rightarrow \beta $$ and lets say you have a sentential form $$ αAδ $$ then A reducing to β does not depend on what α and δ are. So that way it is context free as it does not depend on surrounding context.

---
Tags: terminology, context-free, formal-grammars
---


# Question
Title: Minimise simultaneous equation remainder
I'm not sure if this is the right place to ask, or what the right terminology to use is. The problem I have is this: I have a vector for example: v = \[1,4,5,6,3,1,4,5,6,7,...7\]

and I have a set of other vectors for example: a1 = \[0,0,0,0,0,1,2,3,0,0,...0\] a2 = \[0,0,0,0,1,2,5,0,0,0,...0\] a3 = \[0,0,0,2,2,3,0,0,0,0,...0\] a4 = \[0,0,1,1,1,0,0,0,0,0,...0\] ... an = \[0,0,1,1,1,0,0,0,0,0,...0\]

I want to find out what linear combination of the vectors is closest to v. I define the distance of two vectors to be the sum of the absolute differences of each of its elements. For example the distance between \[1,2,3\] and \[2,2,2\] is abs(1-2) + abs(2-2) + abs(3-2) = 2.

Does such an algorithm exist? If it doesn't exist, are there any algorithms that could get me close to a solution?

Ideally I would like an integer multiple of each vector, does such a solution exist with integer multiples?

# Answer
This problem is an instance of linear programming.

If you allow fractional multiples then it can be solved in polynomial time using standard techniques for linear programming.

If you require integer multiples the problem is (strongly) $NP$-complete. There is a very easy reduction from **1-in-3-SAT**. Let the dimension of the vectors be equal to the number of clauses, let the target vector be $(1,\ldots,1)$ and for every variabele create a vector $a\_i$ that for each clause it appears in has a $1$ in that position (and a $0$ otherwise). You can achieve distance $0$ if and only if the formula is satisfiable.
> 2 votes

---
Tags: algorithms, linear-algebra
---


# Question
Title: Example of worst case input for Build-Max-Heap
What would be an example of a worst-case input for Build-Max-Heap? What would the "shape" of it "look like"? I'm having trouble getting a feeling for it.

# Answer
> 1 votes
Think of a heap as a tree, not its array implementation.

Building a heap work bottom-up. Working from the lowest levels up to the root we add the keys one by one. Worst case is when each key moves as much as possible, so all the way to the level of leaves.

This should start getting the picture.

# Answer
> 1 votes
## Binary Heaps

There are many different ways of implementing a Max Heap, but the simplest (and the one I'm guessing you're interested in) is a **binary heap**.

A binary heap is just a binary tree, in which the nodes contain the keys of the heap, and we maintain an invariant that *the key of a parent node is no smaller than the keys of its children.*

## Insertion

We can choose to implement insertion in a number of different ways, but again there is a simple choice which I've seen referred to as the "swim" method. Begin by inserting a node at the bottom of the tree. If it's key is larger than its parent's, "swim" it up (exchange it with the parent); otherwise, leave it where it is.

What is the worst case series of inputs for this implementation? The most work we can do per insertion is to move the inserted node all the way up the tree, which translates to $1 + log\_2(n)$ compares, where $n$ is the number of nodes already in the tree. Therefore, the worst case sequence of inputs is one sorted in increasing order.

## Removing the maximum

A good exercise to test your understanding of these binary heaps might be to answer a similar question to the one you asked. Max Heaps are generally used to implement Max Priority Queues, so in addition to *insert* we have a method for *remove the maximum.* A common implementation of *remove the maximum* involves swapping the max element (the root) with a leaf node, and then "sinking" this leaf down the heap (exchanging it with a child if its key is smaller than that child).

**What's the worst case selection of leaves to exchange with the root?** Hint: think about the most work we can do in a single *remove the maximum* operation.

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


title: A particular complexity

text:
# Question
Title: A particular complexity
Whats is the name for a complexity like $n^{\log \log n}$ ? Is this exactly subexponential, or less than that ?

# Answer
It is quasi-polynomial time. See it under examples http://en.wikipedia.org/wiki/Time\_complexity
> 7 votes

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


# Question
Title: Converting a digraph to an undirected graph in a reversible way
I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I understand that this will come in expense of the undirected graph having more vertices but I do not mind.

Does one know how to do this or can suggest any references? Thanks in advance.

---

Update: Regarding the answer of AdrianN below. It might be a good starting point but I don't think it works in its current form. Here is an image of why I think it doesn't:

---

Update after D.W.'s comment: I consider the vertices of the graphs to be unlabeled. If a solution involves labeling the vertices (like AdrianN's does), then it should give the same (isomorphic) undirected graph no matter how the labeling is done. My definition of "isomorphic" for graphs with labeled vertices is that there is a permutation of the labeling that relates the two graphs, but I am not sure of the exact definition for unlabeled graphs...

# Answer
> 7 votes
For each directed edge $e=(x,y)$, add new vertices $v^e\_1, \dots, v^e\_5$ and replace $e$ with the edges $xv^e\_1$, $v^e\_1v^e\_2$, $v^e\_1v^e\_3$, $v^e\_3v^e\_4$, $v^e\_4v^e\_5$, $v^e\_3y$.

To decode, every leaf (degree-1 vertex) whose neighbour has degree 2 must be $v^e\_5$ for some edge $e=(x,y)$; its neighbour is $v^e\_4$ and the other neighbour of $v^e\_4$ is $v^e\_3$. $v^e\_3$ has a unique neighbour that has both degree 3 and is adjacent to a leaf: the neighbour is $v^e\_1$ and its leaf is $v^e\_2$ (if $v^e\_1$ has two leaf neighbours, pick one arbitrarily to be $v^e\_2$). The other neighbour of $v^e\_1$ is $x$ and the other neighbour of $v^e\_3$ is $y$. Restore the directed edge $(x,y)$ and delete the vertices $v^e\_1, \dots, v^e\_5$.

# Answer
> 10 votes
David Richerby's answer (which was accepted) is good.

I followed his instructions on a simple example digraph, and hope it helps someone.

(I would have posted this as a comment on David's answer, but I do not have the reputation points required.)

# Answer
> 2 votes
To convert a directed graph $D$ to an undirected graph $G$ one do the following:

1. Number the nodes of $D$
2. Create two undirected graphs $G'$, $G''$ on the same vertex set as $D$
3. For every edge $u$,$v$ in $D$ add the edge to $G'$ if $u\<v$, else add the edge to $G''$
4. G is the disjoint union of $G'$ and $G''$

When doing the disjoint union one must take care to make it reversible.

# Answer
> -1 votes
What about the identity function ? I.e. every digraph can be seen as a undirected, bipartite graph with equal sized partitions and vice versa.

# Answer
> -1 votes
Here's a stab at this:

Replace the direction information with additional vertices in the undirected graph. In other words, use the additional vertices in the undirected graph to "encode" the direction information. For example, for each directed vertex with at least one edge, add a number of undirected vertices equal to 1 + the number of "incoming" edges. Vertices with zero edges remain unchanged.

To perform the reverse direction, create a directed vertex for each vertex that has 0 or more than 1 edge. (Vertices with exactly one edge are the "direction encoding" vertices). Each edge that connects another multi-edged vertex is a connection in the directed graph. Now is the tricky part that I can't explain an algorithm for (but I think one exists): You must deduce the direction of the arrows given only the number of incoming arrows for each vertex.

I think the tricky part is sort of like playing minesweeper :-) Figure out where the bombs (incoming edges) are given the number of adjacent bombs for each square (vertex).

---
Tags: algorithms, graphs
---


# Question
Title: Why doesn't my object code/machine code contain 1's and 0's
I know when I compile my C program to machine code it gets compiled into something that specific computer can understand

But I thought computers can only understand 1's and 0's (high/low) so why doesn't my program look like a bunch of strange symbols and not 1's and 0's?

ie: "UHâÂHÉÏHç=7∞Ë1…âE¸â»HÉƒ\]√êˇ%¶LçïASˇ%ÖêhÈÊ"

There must be one last piece I'm missing where these symbols get converted to 1's and 0's somehow

# Answer
> 3 votes
This is a result of the program that opened the file.

All files on the system are in binary. What matters is how you interpret it.

The editor you used has displayed the digits in their common form:

"UH...." is the equivalent hexadecimal "5548...." which is binary "101010101001000...."

Thus you need a Hex or Binary editing program to 'view' the '1's and '0's.

# Answer
> 0 votes
Machine/object code is specific to the interpreter/parser. What you mean to say by "1's and 0's" is binary code, which is what is presented to the machine when the interpreter/parser receives the machine/object code as input.

---
Tags: compilers
---


# Question
Title: Tips for creating “Context Free Grammar”
I am new to CFG's, Can someone give me tips in creating CFG that generates some language

For example

$L =\\{ w v w^R \mid v,w\in \\{a,b\\}^\*\wedge|v| \text{ is even } \\}$, where $w^R$ is the reverse of string $w$.

I'm having trouble understanding the language .. I want to build DFA to convert it

# Answer
Mmmm.

Let me note that in fact $L =\\{ w v w^R \mid v,w\in \\{a,b\\}^\*\wedge|v| \text{ is even } \\}$ equals $\\{ v \mid v \in \\{a,b\\}^\*\wedge|v| \text{ is even } \\}$.

Al strings in $L$ are of even length, and conversely all strings of even length can be otained by taking $w=\varepsilon$.

That should help.
> 3 votes

# Answer
Hints:

1. Construct a non-terminal $V$ and appropriate productions so that $V$ generates all strings of even length.
2. Create productions so that your starting symbol $S$ generates $wVw^R$ for all $w$. To accomplish that, modify a grammar for $ww^R$.
> 2 votes

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


# Question
Title: Why is binary search called binary search?
I heard several possible explanations, so I would like some trustable reference.

Update 05.19: I'm interested in the question because one of mine students wrote in his thesis that the name comes from the below explanation (1). Until now I thought/heard that it comes from explanation (2). I would feel bad both for letting the wrong thing in his thesis, as well as telling him to remove it if it might be right.

(1) Consider the search for an integer in the interval $\[0,2^{n-1}\]$. We can find it using $n$ questions by asking in step $i$ the $i^{th}$ *binary* digit of the number.

(2) If we have a search space with $2^n$ elements, we can find an unknown element by questions that repeatedly split the remaining part of the space in *two*.

And yes, I know that (2) can give the same algorithm as (1) but that's not the point here. (2) can be also applied for more general problems.

# Answer
I tried to look up the Mauchly reference cited by Knuth but my library seems to have misplaced their copy.

In the meantime, consider the following early-ish citations for "binary search":

* Halpern, Mark. "Variable-width tables with binary-search facility." Communications of the ACM 1.2 (1958): 1-4.

> The family of subroutines described in this report was designed to create, search and maintain tables which are to contain entries of different lengths, and yet be amenable to search by partition, or “binary” search.
* Nagler, H. "An estimation of the relative efficiency of two internal sorting methods." Communications of the ACM 3.11 (1960): 618-620.

> This report concerns the IBM 705, models I and II. It is a study of the machine time required by two internal sorting methods, the conventional two-way merge, and a form of the binary search, which is due to D. Mordy, of the IBM Corporation.
* Petersen, T. L. RE-ENTRY VEHICLE SYNTHESIS PROGRAM. No. STL/TR-60-0000-09103 (pdf link). TRW SPACE TECHNOLOGY LABS LOS ANGELES CA, 1960.

> The value of ${V\_0}^\*$ for which $g({V\_0}^\*) = 0$ must now be found. It is easily seen that $g(0) = K\_3 - 1$ and $g(K\_1) = -1$, so that the required value of ${V\_0}^\*$ lies between 0 and $K\_1$ if $K\_3\>1$. A binary search is conducted for the root of $g({V\_0}^\*)$; the ${V\_0}^\*$ selected is that for which the absolute value of the difference between consecutive values of ${V\_0}^\*$ is less than $0.01$.

I'll note how the first 1958 citation uses quotation marks around "binary" but by the third citation in 1960, a binary search is mentioned without any further description or explanation. The allusion to "search by partition" would tend to suggest that explanation 2) is closer, but further verification is required.
> 2 votes

# Answer
Explanation (2) is a good explanation.

(2) is the better explanation of the two, because it applies generally to all uses of binary search, not just one specific instance. (1) is not an unreasonable way to think about it -- it's just not as general or complete as (2).

I don't think you need to feel obliged to require the student to correct this statement. It would not be embarrassing if a student gave explanation (1) in their thesis, so you don't need to feel bad. But if you want to teach them something, you can tell them about explanation (2) and about how binary search is more general and why the name "binary search" is reasonable for the general algorithm as well. But it's a minor point and not something that I would view as problematic or embarrassing if they left things as is.
> 1 votes

# Answer
According to Wikipedia, binary search concerns the search in an array of sorted values.

The more general concept of divide and conquer search by repeatedly spliting the search space is called dichotomic search (literally: "that cuts in two"). The use of dichotomy may be considered in other contexts, as sonn as you have something to split. It is actually the first expression I learned (in high school, I think, and that was long ago), including in cases where you might want to call it binary.

Afaik, "dichotomic" does not imply that the two parts are (nearly) equal.

I do not know that binary is reserved to search in a space of size $2^n$.

Dichotomic is clearly the more general term, but it may sound pedantic to some who might instead improperly use binary.

Your example (1) is strangely stated, as one does not consciously ask for binary digits, but rather for comparison with the median of an interval. But it could qualify as binary.

Youe example (2) is unclear. Just splitting in two should be called dichotomic. Now, as you seem to hypothesize (strangely) a way of making 2 equal parts, I am not sure.

But a guessing game, where people ask questions that are answered by yes or no is clearly dichotomic.

My own guess, no reference given:

The original expression was probably "dichotomic", but with the popularity of binary systems, binary computer, etc., the term "binary" became more popular.

One other factor that may have played an important role is that binary search (as well as dichotomic) is based on binary choices. Now the expression "dichotomous choice" does exists, but is much less used than "binary choice", which appear about 6 times more often on the web.

So this may have influenced that. We should remember that though we are largely immersed in binary number (I mean we, computer scientist), most people are not and are nor concerned with binary numbers, but will easily talk of a binary choice. It is true that binary search is a topic for computer scientist, but short of a reliable reference to the contrary I will not believe it comes from binary numbers in any direct way.
> 1 votes

# Answer
Knuth (V.3 Pg. 82) gives Mauchly as the source for binary search; it is used to find the insertion point during a sort which then shuffles elements forward to make a vacancy, in a process called binary insertion.

So (2) would be valid, but I can't see the original paper; it's obscured here: https://books.google.com/books?id=A6EEAQAAIAAJ&focus=searchwithinvolume&q=sorting+and+collating
> 1 votes

---
Tags: terminology, reference-request, history
---


# Question
Title: Soon to be computer science major with some questions
I'm going to apologize in advance for this wall of text, and if you're looking for me to ask technical questions about the field, that isn't what this post is going to be. So this Fall I'm going to be starting my degree for computer science. To be honest I'm not sure what to expect. I've done research and some people say that the degree will be far more math heavy than it needs to be for a lot of fields, while others disagree. The problem, besides there not being a very helpful answer, is that none of these people seem to even be in the field. What will I be learning besides programming? My goal is to actually be a video game programmer, but I'm getting this degree because I know that could change, and I also like the idea of a degree that isn't quite that niche. So is that a wise choice? I began teaching myself to program some with online resources and such, and have focused mainly on Python as a starting point. However, when I see some of the things people on this site and other places, I have no clue what's going on half the time. Is this a bad sign, or should I just quit stressing? Any advice is greatly appreciated.

# Answer
Firstly, is CS going to be Math heavy? It's not a very easy question to answer as it depends on quite a few factors. How good are you in Mathematics and how strong are you with the basic concepts? If you were comfortable with the Math you have done so far, then you won't have any problem. If not, then there is nothing that some hard work cannot solve. Plus CS is definitely not he most heavy of all the majors in engineering or sciences. I believe Mechanical, Aeronautical, etc to involve a lot more advanced Math in them.

Secondly, what will you be learning?

You will be learning Algorithms, various programming languages and there pros and cons, maybe artificial intelligence, operating systems, networking, database theory, some electronics I believe, and maybe sensor networks,etc.

Thirdly, should you quit stressing?

Definitely Yes. If you have decided to become a Computer Science major then I am guessing that you have interest in the field. If that is true you should be able to grasp the concepts just fine.

My Advice, pick an area like Artificial Intelligence or Networking or Operating System etc, which ever field you like best, early, and try and master that field. That will help you tons in the future.

I have a PhD in CS and seen quite a few young guys go through the same phase as you. It's very natural to feel nervous about the unknown, specially when it's about your career and the rest of your life. Just try and make smart decisions whenever you have to. Plus, there will be lots of people around to help you when you are unsure.

So, Good Luck and have Fun.
> 1 votes

---
Tags: programming-languages
---


# Question
Title: A Query regarding Quadratic Residuocity Problem
In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: $$ x^2\equiv q \pmod{n}. $$Otherwise, q is called a quadratic nonresidue modulo n.

Problem Definition: Given a constant c, is there a positive integer x \< c such that $$ x^2\equiv q \pmod{n}. $$

If n is composite, the problem is NP-Complete, even if given the prime factorization of n. But, if n is a prime the problem is solvable in polynomial time.

Query: In case n is composite, and given that it has lets say exactly 3 distinct prime factors, does the problem still remain NP-Complete? Any link to the references?

# Answer
> 5 votes
It can be solved in randomized polynomial time, so it's not NP-complete (unless RP=NP, which is considered unlikely).

If $n=p\_1p\_2p\_3$ is composite, where $p\_1,p\_2,p\_3$ are three distinct prime factors, and $p\_1,p\_2,p\_3$ are given, then the problem can be solved in polynomial time. In particular, in this case, there are only 8 square roots of $q$ (modulo $n$), and you can enumerate them all and check whether any of them are in the range $\[0,c)$.

Details and justification: you can use the Chinese remainder theorem. Let $x\_1$ be one of the two square roots of $q$ modulo $p\_1$, i.e., it satisfies $x\_1^2 \equiv q \pmod{p\_1}$. (Then the other square root is $-x\_1$.) Similarly, let $x\_2$ be a square root modulo $p\_2$ and $x\_3$ a square root modulo $p\_3$. Then you can find a square root modulo $n$ by using the Chinese remainder theorem to find the unique solution to $x \equiv x\_1 \pmod{p\_1}$, $x \equiv x\_2 \pmod{p\_2}$, $x \equiv x\_3 \pmod{p\_3}$. In general, you can look for $x$ to be $x\_1$ or $-x\_1$ mod $p\_1$, and $x\_2$ or $-x\_2$ mod $p\_2$, and $x\_3$ or $-x\_3$ mod $p\_3$; each of those $2 \times 2 \times 2 = 8$ combinations gives a different square root of $q$ modulo $n$. You can find $x\_1,x\_2,x\_3$ in randomized polynomial time, and the CRT computation can be done in polynomial time, so you can enumerate all square roots modulo $n$ in polynomial time.

This same argument generalizes to any case where the number of prime factors of $n$ is constant, and where those prime factors are given in advance. However, when the number of prime factors is unlimited, this line of argument doesn't work, so this won't work for general $n$.

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


# Question
Title: Creating a 2D map of objects given a sparse matrix of pairwise distances
I have a set of points on the two-dimensional plane, but their locations are not given to me. I am given the distance between some pairs of the points. However, I only know these differences for some pairs: I don't have every pairwise distance between the objects. I would like an algorithm to output the locations of the points.

The complication is that there could be some errors in the distances provided to me, so I want the algorithm to output a location for each point such that the pairwise distances between those locations match the provided distances as closely as possible.

Could anyone point me towards a method of computing a placement in 2-dimensional Euclidean space that would best solve this problem?

It would be nice to be able to provide hard constraints as well. For instance, I might be given that $C$ is exactly at the point $(1,2)$, or that all of the objects must fit in a $10 \times 10$ square. However, this is not strictly necessary: an algorithm that does not support hard constraints would still be interesting.

# Answer
This is known as "graph layout" or "graph drawing" (practical methods) or "graph embedding" (theoretical interest). The relevant techniques are more closely associated with computational geometry and mathematical optimization, not machine learning. See this Wikipedia article and Recovering a point embedding from a graph with edges weighted by point distance and Efficient algorithm to fulfil a set of coordinate constraints for an overview of some standard techniques. Pairwise comparisons with confidence might also have some helpful techniques (it is focused on the 1D case, not the 2D case, but it might be possible to generalize Yuval's answer to the 2D case as well).
> 1 votes

---
Tags: computational-geometry, planar-graphs
---


# Question
Title: Is the closure of P under e-free homomorphisms equal to NP?
The context free languages can be obtained as the closure of the Dyck language under the cone operations. The Dyck language $D\_2$ is a deterministic context free language, and the cone operations correspond to the operations that can be implemented by nondeterministic finite state transducers. This result becomes less surprising, if we consider that nondeterministic finite state transducers can provide certificates (or verifiers, or witness strings, I wrongly called this oracle strings initially) of length $O(n)$, where $n$ is the length of the input string.

The definition of the class $\mathsf{NP}$ allows for certificates of length $O(n^c)$, but many $\mathsf{NP}$-complete problems are perfectly happy with certificates of length $O(n)$. The transducer should not change the length of the input uncontrollably, so we need faithful cone operations. For $\mathsf P$, this should be equivalent to closure under e-free homomorphisms. (Intuitively, the homomorphism removes the certificate). Hence my question:

> Is the closure of $\mathsf P$ under e-free homomorphisms equal to $\mathsf{NP}$?

As stated above, this question should be equivalent to the question whether certificates of length $O(n)$ (instead of $O(n^c)$) are enough for $\mathsf{NP}$.

# Answer
As Ryan Williams explains on CSTheory.SE, the answer is probably no: certificates of linear size are probably not enough for NP; some NP problems seems to require certificates of super-linear size.

You can also find some examples of NP-problems that appear to require super-linear certificates over on CSTheory: see Natural NP-complete problems with “large” witnesses and Is the Witness Size of Membership for Every NP Language Already Known?. Also Problem unsolvable in 2o(n) on inputs with n bits, assuming ETH? might be relevant as well.
> 2 votes

---
Tags: complexity-theory, formal-languages, closure-properties, np
---


title: Homomorphism erasing information

text:
# Question
Title: Homomorphism erasing information
I would be grateful if anyone could help me with the tricky exerciese \*7.52 from Sipser's Introduction to the Theory of Computation 3rd ed.

I got stuck in proving that, if P is closed under nonerasing homomorphism (replacing all characters with nonempty string), then P = NP. With nonerasing homomorphism I cannot delete the characters, but I can get rid off the information by overwriting it e.g. with 0s.

I'm trying to complete the following idea:

1. Checking whether a given assignment to propositional formula makes it true is in P class.

Let s be the 0-1 string encoding both the formula and particular assignement.
2. I'm trying to find such nonerasing homomorphism H over 0-1 alphabet that H applied to string s will erease (overwrite with something that will destroy information) the particular variables assignment but I must be able to read off the formula.

Have anyone the idea how such a homomorphism could look like? (only 2 letter alphabet is allowed).

# Answer
> 2 votes
Denote the closure of a class **C** of languages under log-space many-one reductions by **Closure( under log-space many-one reduction of, C)**, and the closure of a class **C** of languages under e-free homomorphisms by **Closure( under e-free homomorphisms of, C)**. So for example

* **NP**=**Closure( under log-space many-one reduction of, NP)**
* **NP**=**Closure( under e-free homomorphisms of, NP)**

We want to show:

> If **P**=**Closure( under e-free homomorphisms of, P)** then **P=NP**.

For this, it is sufficient to show

1. **P**=**Closure( under log-space many-one reduction of, P)**
2. **NP**=**Closure( under log-space many-one reduction of,
Closure( under e-free homomorphisms of, P))**

because if **P**=**Closure( under e-free homomorphisms of, P)** then
**NP**=**Closure( under log-space many-one reduction of,
Closure( under e-free homomorphisms of, P))
=Closure( under log-space many-one reduction of, P)=P**

It is well known how to show (1). For showing (2), it is sufficient to show

3. **NP**=**Closure( under log-space many-one reduction of, {SAT})**
4. **SAT $\in$ Closure( under e-free homomorphisms of, P)**

because if **X$\subset$Y** then **Closure( under ... of, X)$\subset$Closure( under ... of, Y)**.

It is well known how to show (3), which says that **SAT** is **NP**-complete under log-space many-one reductions. For showing (4), note that certificates of length O(n) are sufficient for **SAT**, where n is the length of the input. So we need to show that e-free homomorphisms can erase a certificate of length O(n) from the input, if the certificate is encoded suitably. This is straightforward in a certain sense, but we have to change the alphabet. The letters of the larger alphabet contain both an original input letter, and an additional certificate letter. To "erase the certificate", the homomorphism replaces this pair of "(original letter, certificate letter)" by the "original letter".

---

If you want to stay with the 0-1 alphabet, then homomorphisms from the free monoid over 0-1 can't erase information selectively enough, because such a homomorphism is already uniquely determined by the image of 0 and 1. But if you look instead at the submonoid of words whose length is a multiple of some number k, then you can easily find suitable homomorphisms.

---
Tags: complexity-theory, np, p-vs-np
---


title: Time quantum assignment to processes

text:
# Question
Title: Time quantum assignment to processes
In a book I am reading it is stated that an input/output intensive process should receive a higher time quantum whereas a computing intensive process on the other hand should receive a lower one. Here however, it is stated that:

> A short quantum is good because it allows many processes to circulate through the processor quickly, each getting a brief chance to run. This way, highly interactive jobs that usually do not use up their quantum will not have to wait as long before they get the CPU again, hence improving interactive performance.

That's basically the exact opposite to what's stated in the book. So my question is should the quanta for input/output intensive processes and computing intensive processes be high or low and why?

# Answer
It depends on what you are trying to achieve, but generally i/o intensive jobs should receive a higher *priority*, and a small time quantum.

I assume you are asking about some variety of *multilevel feedback queuing*. The idea behind multilevel feedback queue-based schedulers is to try to approximate *shortest remaining time first* scheduling, where you are trying to minimize the average time each process spends waiting while it is ready-to-run.

We assume each process goes through the following cycle:

1. ready-to-run: waiting for all higher-priority processes to finish using cpu.
2. running: for some amount of cpu time then perform a blocking i/o request.
3. sleeping: after making a blocking i/o request, the process sleeps, waiting for the response from the i/o system.

When the response comes back from the i/o system the process wakes up and is ready-to-run again. We call the set of processes that are ready to run (the processes *not* blocked waiting for a response from the i/o system), the *run queue*.

If we were able to predict exactly how long each process needed the cpu before its next i/o request, then we wouldn't need to have quanta at all. Every time a process made an i/o request (moving it from state running to state sleeping) or got a response from i/o (moving it from sleeping to ready-to-run) we would just find the process with the shortest remaining time to its next i/o request, and run it.

But we don't know exactly how long each process will use the cpu before its next i/o request. So we have to guess (e.g., by keeping track of how long it took the last few times, and using the average of those as the guess), but we might be way off. So we also start a timer with a length somewhat larger than our guess for the expected cpu usage. If our guesses are very good, then the timer will never fire. Instead, each process will either make an i/o request, causing itself to block and allowing some other process to run, or a response to an i/o request will return, preempting the currently running job and allowing us to perform a new scheduling decision.

Multilevel feedback queues approximate shortest remaining time first by having a few priority levels and moving jobs to lower priority when they use more than their allotted quantum. The idea is over 50 years old:

Corbató, FJ; Daggett, MM; Daley, RC: An Experimental Time-Sharing System, *AFIPS Conference Proceedings*, Vol. 21, pp. 335-344, 1962.
> 2 votes

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


# Question
Title: Path optimization in a DAG: maximizing number of least cost arcs
I've got the following problem.

I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$.

The optimal path has to maximize the number of least cost arcs. In the example:

R-\>B-\>S is the least cost path but it's not the optimal. R-\>-A-\>D-\>S costs less than R-\>A-\>C-\>E-\>S , but the latter is the optimum as it goes through more, least cost arcs.

My current problem, which constitute the object this question, is to find a way of defining formally how to compare two paths according to my intuitive understanding, as comparing them comes before choosing the optimal one.

Of two paths, the better one is the one that traverses the highest number of least cost arcs.

I have been considering three ways, some that seem not fully adequate for my purpose, but would welcome other suggestions.

My three ideas are the following:

1. Minimizing the average of the cost of arcs on the path.

Minimizing the average is not fully ok: imagine to have a path with cost \[3,12\], and a path with cost \[3,10,10\]. The average of the first path is less than the average of the second, but the second is the optimal as it traverses more paths.
2. Comparing individually the arcs of the paths

Given two paths $A$ and $B$:

Let $A$ = \[$a\_1,\ldots,a\_n$\] and $B$ = \[$b\_1,\ldots,b\_m$\] where $a\_i$ and $b\_i$ are the arc costs of $A$ and $B$ respectively.

Then $A$ is better than $B$ if $\sum\_{i=0}^n card(B \< a\_i)$ \< $\sum\_{i=0}^m card(A \< b\_i)$ where $card$ represents the cardinality of the set, and $B \< a\_i$ is defined as $\\{b\_j \in B \mid b\_j \< a\_i\\}$, the comparison being on the weight of the concerned arcs.

However, with this second approach I get many ties between different paths, increasing the risk of getting a suboptimal path.
3. Comparing the min-max of the arcs weights for each path.

Another possibility is to compute the min-max of the arcs of each path, and choose the smaller one. It is intrinsically different from the other approaches.

But it is not fully what I seek to achieve. For example, min-max over \[1,1,1,3\] and \[2,2,2,2\] chooses the latter one, while the best one is the first.

To motivation behind my intuition is the following: each node is a "checkpoint" that the solution may traverse on its way from the node $R$ to node $S$. The goal is to output a sequence $Q$ with an associated "precision"

if the chosen path is R-\>A-\>D-\>S, then $\\;Q\\;$ is $\\;\\;$A $\pm$ 10, D $\pm$ 5, S $\pm$ 7

Clearly, the optimal solution has to be as precise as possible, so the optimal path has to emit the maximum number of least cost arcs.

Once the comparison of paths has been formalized precisely, my problem will be to compute the optimal path on a given graph. But right now the question is only to find a proper way of comparing paths. The role of the graph structure is only, possibly, to help convey the intuition of my problem.

# Answer
> 1 votes
I've not thought completely through it, but some thoughts on 1) which might be useful:

If you add a constant value k to each edge traversed, you could take into account the number of nodes traversed. In your case, this constant value k should be negative (e.g. the negative value of the maximum edge weight, in your example 11).

Then you might be able to state the following:

The path maximizes the number of least links if $\sum\_{i=0}^n (a\_i + k)$ \< $\sum\_{i=0}^m (b\_i + k)$.

For your example: (let $P\_i$ denote the $i$-th path and $C\_i$ denote the costs of path $P\_i$)

$P\_A=\[R, B, S\], C\_A = -2$

$P\_B=\[R, A, D, S\], C\_B = -11$

$P\_C=\[R, A, C, E, S\], C\_C = -20$

So $C\_C \< C\_B \< C\_A$ and hence $P\_C$ is your optimal path.

As mentioned, I've not spent too much time to look if there is an example where this approach does not work, but maybe it's a good point to start with.

Of course you get some ties with this approach as well but I think all of these ties are equivalent in the sense that the least cost arcs are traversed and the number of traversed vertices are equivalent. Correct me, if I'm wrong.

# Answer
> 0 votes
The question is proposing 3 definitions for comparing paths. The first and third are apparently not satisfactory for the author of the question. We show that the second definition is not usable either.

The second formalization seems more sophisticated, and is precisely given. It is not a metric but the definition of a "*better*" relation between paths, that is noted here "$\prec$".

$$A\prec B\\;\\;\\;\mbox{ iff }\\;\\;\\;\sum\_{i=0}^n |B \< w(a\_i)|$ \< $\sum\_{i=0}^m |A \< w(b\_i)|$$ where $w(a)$ is the weight of an arc $a$,
and $B \< w(a\_i)$ is defined as $\\{b\_j \in B \mid w(b\_j) \< w(a\_i0\\}$

Actually, this can be redefined, I think more intuitively, as it helped me find the example below, as:

$\begin{align} A\prec B\\;\\;\text{ iff }\\;\\;|\\{(a\_i,b\_j)\mid a\_i\in A, b\_j\in& B, w(b\_j)\<w(a\_i)\\}|\\;\<\\; \\ &|\\{(a\_i,b\_j)\mid a\_i\in A, b\_j\in B, w(b\_j)\>w(a\_i)\\}| \end{align}$

However, the problen is that this relation is not an order on paths, not even a preorder, since it is not transitive:

A counter example is given by the following three paths, here just given as sets of weights:

$$A=\\{9,5,4\\},\\;\\;\\; B= \\{6\\},\\;\\;\\; C= \\{8,7,3\\}$$

It is easily verified that

$$A\prec B,\\;\\;\\; B\prec C,\\;\\;\\; C\prec A$$

Thus, despite the notation chosen here, the relation $\prec$ cannot be used to order solutions. Hence this relation cannot be used to define the choice of an optmal path, independently of how paths are defined or the graph explored.

None of the three modes of comparison seems to meet the need of the author of the question. The motivation given by the author for his intuition is too vague to help. A full example of the real problem he is adressing should be given to have a chance for further progress.

---
Tags: algorithms, graph-traversal, weighted-graphs, partial-order, order-theory
---


# Question
Title: Time complexity of $\sim c \cdot n^3$ with a computer which is 10 times faster
I am trying to solve the following question

> There's an algorithm with time complexity $\sim c \cdot n^3$. Suppose there's another computer which is 10 times faster. How much bigger can our $n$ be to be solved in the same time?

My answer so far is $\sqrt\[3\]{10}$.

$n^3$ can be 10 times bigger, so I have to multiply N with $\sqrt\[3\]{10}$. Is my conclusion correct or is there a fault in my reasoning?

# Answer
> 1 votes
You've correctly reasoned that the additional speed doesn't change the $n^3$ part of the tilde expression. The only component left for it to effect then is $c$.

Let $c\_1$ be the constant of the first computer and $c\_2$ the constant of the second. If the second computer is 10x faster, then $c\_2 = c\_1/10.$ Now, all you need to do is solve the following equation:

$$c\_1 \cdot n^3 = \frac{c\_1 \cdot n'^3}{10},$$

which gives the same answer you came up with!

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


# Question
Title: Conflict Driven Clause Learning backtracking clarification
On the wikipedia page here it describes pretty well the CDCL algorithm (and it seems the pictures were taken from slides created by Sharad Malik at Princeton). However when describing how to backtrack all it says is "to the appropriate point". MiniSAT also uses a variant of the CDCL algorithm so I read this paper. What they seem to say is that you should backtrack until the learned clause is a unit clause. That is certainly clarification but it doesn't make sense to me. The last assignment is definitely going to be part of the learned conflict clause as far as I can tell (perhaps I am wrong here?) so when you backtrack one step you will immediately make the learned clause unit, the last assigned value will flip, and the algorithm will proceed exactly as DPLL without ever backtracking sufficiently far. Additionally the wikipedia page doesn't follow this rule, it backtracks much further as seems desirable.

How far is one supposed to backtrack?

# Answer
> 7 votes
Here's the relevant paragraph from the MiniSAT paper:

> The decision phase will continue until either all variables have been assigned, in which case we have a model, or a conflict has occurred. On conflicts, the learning procedure will be invoked and a conflict clause producted. The trail will be used to undo decision, one level at a time, until precisely one of the literals of the learnt clause becomes unbound (they are all $False$ at the point of conflict). By construction, the conflict clause cannot go directly from conflict to a clause with two or more unbound literals. If the clause remains unit for several decision levels, it is advantageous to chose \[sic\] the lowest level (referred to as *backjumping* or *non-chronological backtracking*).

A point you seem to have missed is that once the learned clause becomes unit due to undone assignments (backtracking), the solver doesn't stop there. There could be other assignments before this one that have no bearing on the current conflict and experimentally it has been shown that it is better to undo these unrelated assignments also. So the solver continues to undo assignments until the next undo would make the learned clause non-unit, i.e. it would contain more than one unassigned variable. The solver stops here, runs unit propagation to satisfy the unit clause and then resumes the search, assigning variables normally.

Note also that the current decision variable may not be present in the learned clause. A common strategy for a CDCL solver is to find the *first unique implication point* and use that variable in the learned clause. In some cases the first UIP is the decision variable, but often it is not.

---
Tags: machine-learning, satisfiability, sat-solvers, backtracking
---


# Question
Title: Probabilistic Analysis in real time network : Error in data and feedback channel. Two users communication
I'm studying probabilistic analysis in real time network. We have learned how many attempts in average are required to transmit a packet when there is no error on the feedback channel.

## With no error in the feedback

$p$ Probability packet not send

$1-p$ Probability packet send

$i$ transmission attempts

$Pr(n=i) = p^{i-1} (1-p)$

$E\[n\] = \sum\_{i=1}^{\infty}i p^{i-1} (1-p)$

With some rules of derivation and geometric series :

$E\[n\] = \frac{1}{1-p}$

---

## I need to extend the analysis for the case of errors in the feedback channel.

How to find how many attempts in average are required to transmit a packet when there is error in the data channel and the feedback channel?

I have tried something :

$p$ Probability packet not send

$1-p$ Probability packet send

$i$ transmission attempts

$q$ Probability ACK not send

$1-q$ Probability ACK send

$Pr(n=1) = (1-p)(1-q)$

$Pr(n=2) = p(1-p)(1-q) + q(1-p)^2(1-q)$

$Pr(n=2) = (1-p)(1-q) (p+ q(1-p))^{2-1}$

$Pr(n=i) = (1-p)(1-q)(p+q(1-p))^{i-1}$

I'm a little confused. The number of possibilities increase very fast. For 2 attempts : The data fails one time and succeeds the second time with no error in the feedback or the data succeeds in both case but the feedback fails the first time.

But when I arrive at 20 attempts the number of possibility reach $2^{i-1} = 2^{19}$. Which looks too big for me.

How can I check if I'm on the right track?

# Answer
Your analysis so far is correct. Let's consider the probability that it will take $k$ attempts to transmit a package. This means that there must be $k-1$ failures followed by a final success. There are two ways a transmission can fail:

1. Transmit succeeds, ACK fails. Call this a type-1 failure. Its probability will be $(1-p)q$.
2. Transmission fails (so ACK is not sent). Call this a type-2 failure; its probability will be $p$.

For there to be $k-1$ failures, we must have a sequence of events $E\_1, E\_2, \dotsc, E\_{k-1}$, each of which is a failure of type 1 or type 2. The probability, then, of each $E\_i$ must be the sum of the probabilities of both types of failure, namely $p + q(1-p)$. Since the events are independent, the probability of the entire sequence will be the product $(p+q(1-p))^{k-1}$. The sequence must be followed by a successful transmission and a successful ACK, so $$ Pr(n=k) = (1-p)(1-q)(p+q(1-p))^{k-1} $$ The expected number of attempts to reach a successful transmission will be $$\begin{align} E\[n\] &= 1\cdot(1-p)(1-q)+2\cdot(1-p)(1-q)(p+q(1-p))+\dotsm\\ &= (1-p)(1-q)\[1+2(p+q(1-p))+3(p+q(1-p))^2+\dotsm\]\\ &= (1-p)(1-q)\sum\_{k=1}^\infty k(p+q(1-p))^{k-1} \end{align}$$ It's a more or less well-known result that $$ \sum\_{k=1}^\infty kx^{k-1}=\frac{1}{(1-x)^2} $$ and so we have $$ E\[n\]=(1-p)(1-q)\frac{1}{(1-(p+q(1-p)))^2} = \frac{1}{(1-p)(1-q)} $$ which, as they say, is just too pretty not to be correct, not to mention that it's what we should expect, given the symmetry of the problem.
> 2 votes

---
Tags: probability-theory, computer-networks, real-time, network-analysis
---


# Question
Title: Software or program, what is the difference?
I am a CS student. When I first came to school, I thought that programming was to make a software. Now I found I was wrong. Now I want to know what the difference is, and what is the difference between a programmer and a software engineer. I hope people can give me some advice. (forgive my broken English)

# Answer
1) A "program" is a kind of "software". "Software" is a somewhat broader concept than just "a program".

2) Here's a good definition of software:

http://www.openprojects.org/software-definition.htm

3) You can find other definitions, and they may or may not agree precisely with this one.

But I like this part of the definition:

Software is created with programming languages and related utilities

This implies that, depending on how broadly you define "software" and how specifically you define "programming languages", you should be able to "create software" without necessarily knowing a programming language or using a compiler.
> 3 votes

# Answer
Expanding Pradhyuman's answer. From Wikipedia:

Software Engineering can be divided into ten subdisciplines that correspond to distinct phases of the software development process. They are:

1. Software requirements: The elicitation, analysis, specification, and validation of requirements for software.
2. Software design: The process of defining the architecture, components, interfaces, and other characteristics of a system or component. It is also defined as the result of that process.
3. Software construction: The detailed creation of working, meaningful software through a combination of coding, verification, unit testing, integration testing, and debugging.
4. Software testing: The dynamic verification of the behavior of a program on a finite set of test cases, suitably selected from the usually infinite executions domain, against the expected behavior.
5. Software maintenance: The totality of activities required to provide cost-effective support to software.
6. Software configuration management: The identification of the configuration of a system at distinct points in time for the purpose of systematically controlling changes to the configuration, and maintaining the integrity and traceability of the configuration throughout the system life cycle.
7. Software engineering management: The application of management activities—planning, coordinating, measuring, monitoring, controlling, and reporting—to ensure that the development and maintenance of software is systematic, disciplined, and quantified.
8. Software engineering process: The definition, implementation, assessment, measurement, management, change, and improvement of the software life cycle process itself.
9. Software engineering tools and methods: The computer-based tools that are intended to assist the software life cycle processes, see Computer Aided Software Engineering, and the methods which impose structure on the software engineering activity with the goal of making the activity systematic and ultimately more likely to be successful.
10. Software quality: The degree to which a set of inherent characteristics fulfills requirements.

...

As you can see, programmers are mainly required for software construction and maintenance.

A software engineer should have strong knowledges of all the software development phases and should be a good programmer, too (actually most programmers employed in big companies are engineers :-).

Obviously for small software projects some phases may overlap (or may be ignored) and programmers may be involved directly in many of them. For large software projects (like an operating system) there can be hundreds (thousands) of software engineers and programmers involved.
> 3 votes

# Answer
This is purely an accidental property of the English lexicon.

In French and other languages, *software* is apparently a countable noun. In English, it is not: you cannot not say *a software* any more than you can say *a hardware* or *a garbage*. You say *a program* or *an application* instead.

This is due to the origins of the word *software*: it was formed from the word *ware*, a mass noun meaning *goods*, used to form nouns indicating what sort of goods are involved: *silverware*, *earthenware*, *hardware* (hard goods), and, to express the opposition with hardware, *software*.

*Ware* has been a mass noun for a long time, considering that the same word in Dutch is used as a mass noun as well: *waar*, *koopwaar* (merchandise, literally *buyware*), although the plural form *waren* is more common.

French lacks *ware*, and borrowed *software* as a whole; apparently, without adopting its property of being a mass noun.
> 2 votes

# Answer
For the difference between programmer and s/w engineer check out this history. It says, "many practitioners called themselves software engineers to escape the stigma attached to the word programmer".

As for the question in the title, there is no difference. Both mean a set of instructions to a computer/computer's processor. You can find this too on Wikipedia.
> 0 votes

---
Tags: terminology, software-engineering
---