title: What is semantic closure?

text:
# Question
Title: What is semantic closure?
In the context of database theory, what does semantic closure mean (linguistically speaking, i.e. not the mathematical definition)

If **X** is the set of attributes of $F$, then the semantic closure $F^+$ of $F$ is defined as follows:
$F^+=\\{$ **Y** $\rightarrow$ **Z** $\ |\ $ **Y** $\cup$ **Z** $\subseteq$ **X** $\wedge\ F \models$ **Y** $\rightarrow$ **Z** $\\}$
$F \models $ **Y** $\rightarrow$ **Z** means that any database instance that satisfies every functional dependency of $F$ also satisfies **Y** $\rightarrow$ **Z**

# Answer
Generally speaking, the term *closure* is used when you have sets of items and some kind of operation that, given one or more items, can produce more such items. The closure of a set of items with respect to the operation is the set obtained by applying the operation on items in the set in whichever way possible, adding the resulting items to the set, and repeating this until no more items can be added (which may be infinitely often). The resulting set is the smallest set that includes the original set and is *closed* under the operation (in the sense that all possible applications of the operation on items in the set produce items that are also in the set).

Examples:

* the closure of {1} with respect to the operation *add 2* is the set of odd natural numbers
* the closure of {1,3,5} with respect to the operation *multiply* is $\\{3^n5^m \mid n, m \in I\\!\\!N\\}$
* the *transitive* closure of the relation {(1,2), (2,4), (4,5)} is {(1,2), (1,4), (1,5), (2,4), (2,5), (4,5)} (the smallest transitive set that includes the original set)
> 1 votes

# Answer
In this context, $F^+ = \\{ X \rightarrow Y \mid F \models X \rightarrow Y \\}$ is the set of all the dependencies that *semantically* (logically) follow from $F$ as you wrote. You also have a *syntactic* closure, defined as $F^\star = \\{ X \rightarrow Y \mid F \vdash X \rightarrow Y \\}$ where $F \vdash X \rightarrow Y$ means that $X \rightarrow Y$ can be deduced from $F$ according to an inference system, in this case, Armstrong's axioms.

Armstrong's system is both sound and complete so $F^+ = F^\star$, but the concepts are different. To illustrate the difference, let $\Sigma = \\{A \rightarrow B, BC \rightarrow D\\}$ and prove the following:

* $AC \rightarrow D \in \Sigma^+$ (semantic proof). Let $r$ an instance such that $r \models A \rightarrow B$ and $r \models BC \rightarrow D$. Assume $t\_1, t\_2 \in r$ with $t\_1\[AC\] = t\_2\[AC\]$ this implies $t\_1\[A\] = t\_2\[A\]$ which implies $t\_1\[B\] = t\_2\[B\]$ because $r \models A \rightarrow B$. Thus we have $t\_1\[BC\] = t\_2\[BC\]$ and we can conclude $t\_1\[D\] = t\_2\[D\]$ because $r \models BC \rightarrow D$. Thus $t\_1\[AC\] = t\_2\[AC\]$ implies $t\_1\[D\] = t\_2\[D\]$ for arbitrary tuples $t\_1$ and $t\_2$ so $r \models AC \rightarrow D$. We have shown an arbitrary instance model of $\Sigma$ is a model of $AC \rightarrow D$ too, so $\Sigma \models AC \rightarrow D$.
* $AC \rightarrow D \in \Sigma^\star$ (axiomatic proof). From $A \rightarrow B$ we obtain $AC \rightarrow BC$ by augmentation. Now using $BC \rightarrow D$ we obtain $AC \rightarrow D$ by transitivity.
> 2 votes

---
Tags: databases
---


# Question
Title: In a CSP, what is an extensional constraint?
When talking about Constraint Satisfaction Problems (CSP), what does the term `extensional constraint` mean?

# Answer
Let $X$ be a finite set of variables, where each variable $x \in X$ has a domain of values. Let $D(x)$ denote the domain of the variable $x$. Let $C$ be a finite set of constraints on the variables.

Each constraint $c \in C$ has a scope, which is a subset of the Cartesian product $D(x\_i) \times \cdots \times D(x\_j)$. In other words, the scope of the constraints gives the set of legal combinations of values.

An extensional constraint is the relational view of the constraint. It is an explicit listing of the subset of the Cartesian product. You could also have something called an intensional constraint, where the idea is that the values are instead computed by an algorithm.
> 5 votes

---
Tags: terminology, constraint-programming
---


# Question
Title: Tarjan's Strongly Connected Component algorithm
I am trying to understand Tarjan's strongly connected component algorithm and I have a few questions (the line numbers I am referring to are from Algoritmy.net):

1. On line 33 why is `node.lowlink = min(node.lowlink, n.index)` — shouldn't it be same as line 31: `node.lowlink = min(node.lowlink, **n.lowlink**)`?
2. Do we have to generate the components on line 40 in the while loop as we pop? Isn't it true that when the algorithm finishes, all the vertices grouped by `lowLink` should be the SCC?
3. Is it ever true that after we recurse in line 30, `n` may not be in stack? If not and (1) is true we can simplify line 29-33 as follows:

```
if n.index == -1
   tarjanAlgorithm(n, scc, s, index)
if stack.contains(n)
   node.lowlink = min(node.lowlink, n.lowlink)

```
4. I went ahead and implemented the algorithm in Scala. However, I dislike the code - it is very imperative/procedural with lots of mutating states and book-keeping indices. Is there a more "functional" version of the algorithm? I believe imperative versions of algorithms hide the core ideas behind the algorithm unlike the functional versions. I found someone else encountering the same problem with this particular algorithm but I have not been able to translate his Clojure code into idomatic Scala.

Note: If anyone wants to experiment, I have a good setup that generates random graphs and tests your SCC algorithm vs running Floyd-Warshall

Here is the full pseudocode (© Algoritmy.net, MIT licensed).

```
index = 0

/*
* Runs Tarjan's algorithm
* @param g graph, in which the SCC search will be performed
* @return list of components
*/
List executeTarjan(Graph g)
Stack s = {}
List scc = {} //list of strongly connected components
for Node node in g
if (v.index is undefined)
tarjanAlgorithm(node, scc, s)

return scc

/*
* Tarjan's algorithm
* @param node processed node
* @param SCC list of strongly connected components
* @param s stack
*/
procedure tarjanAlgorithm(Node node, List scc, Stack s)
v.index = index
v.lowlink = index
index++
s.push(node) //add to the stack
for each Node n in Adj(node) do //for all descendants
if n.index == -1 //if the node was not discovered yet                  // <--- line 29
tarjanAlgorithm(n, scc, s, index) //search
node.lowlink = min(node.lowlink, n.lowlink) //modify parent's lowlink  // <--- line 31
else if stack.contains(n) //if the component was not closed yet
node.lowlink = min(node.lowlink, n.index) //modify parents lowlink     // <--- line 33

if node.lowlink == node.index //if we are in the root of the component
Node n = null
List component //list of nodes contained in the component
do
n = stack.pop() //pop a node from the stack
component.add(n) //and add it to the component                         // <--- line 40
while(n != v) //while we are not in the root
scc.add(component) //add the compoennt to the SCC list

```

# Answer
> 3 votes
> 1... On line 33 why is node.lowlink = min(node.lowlink, n.index) — shouldn't it be same as line 31: node.lowlink = min(node.lowlink, **n.lowlink**)?

The code works either way. The two possibilities are:

I. `n.index == node.index`, which means the assignment will never change the value of `node.lowlink`, or

II. `n.index < node.index`, which means setting `node.lowlink` to either `n.index` or `n.lowlink` will cause `node.index` to be unequal to `node.lowlink`, guaranteeing that `node` will be part of the SCC containing everything on the stack back to the node with an index matching `n.lowlink`.

> 2... Do we have to generate the components on line 40 in the while loop as we pop? Isn't it true that when the algorithm finishes, all the vertices grouped by lowLink should be the SCC?

No, that's not true. The components of any particular SCC are **not** guaranteed to have the same `.lowlink` value, so you can't partition the vertices into SCCs that way. The `.lowlink` values are used to determine when to pop the stack; the stack determines what is in an SCC.

> 3... Is it ever true that after we recurse in line 30, n may not be in stack?

Yes, `n` may not be in the stack. `n` could be a vertex belonging to a previously identified SCC. There's a forward link to `n` obviously but there may be no back link from `n` or its SCC to the current SCC.

---
Tags: algorithms, graphs
---


# Question
Title: Deciding if a Turing machine has made a left move
In writing a decider for a machine to see if it has made a left move or not on an input of *w*, it is said that if we continue the computation for $|w|+N+1$ ($N$ : number of states) number of steps, we can make a decision for this decide.

I didn't get why $|w|+N+1$ number of steps. Could someone explain this in more detail?

# Answer
$|w|$ steps are needed to scan the input, if a left move is made during this scan accept.

Otherwise, at the end of the input, the head of the Turing machine is on the blank part of the tape (over the first blank symbol after the input). Suppose the state is $q\_{i\_1}$. If the Turing machine doesn't make a left step and stays on state $q\_{i\_1}$, then it will do it forever (it will continue moving right on the infinite blank tape on state $q\_{i\_1}$). But it can move right and switch to state $q\_{i\_2}, i\_1 \neq i\_2$.

If you continue with this reasoning you see that there are only two possibilities:

* it moves left or
* it enters a state $q\_{i\_{k+j}}$ for the second time and thus it will loop forever: $q\_{i\_k} \rightarrow q\_{i\_{k+1}}\rightarrow ...\rightarrow q\_{i\_{k+j}}=q\_{i\_k} \rightarrow q\_{i\_{k+1}}\rightarrow ...$

But there are only $N$ different states so at most $N+1$ more steps are needed to detect such loop.
> 9 votes

---
Tags: computability, turing-machines
---


# Question
Title: Circles covering a rectangular, how to verify it?
This may be basic to some of you, but excuse my inexperience with comp. geometry:

Given a set of $n$ circles with centers $(x\_i, y\_i)$ for $1 \leq i \leq n$ and each having radii $r$. Also given a rectangle. All objects are on a plane. How to verify that every point inside the rectangle (including its edges) is fully covered by the circles. That is, each point in the rectangle lay on at least one of the circles.

Anyone have hints ? I am currently trying with voronoi diagrams.

# Answer
> 10 votes
Create a Voronoi diagram on the $n$ disk centers in $O(n\log n)$ time. Intersect it with the rectangle in $O(n)$ time.

Now you have a set of convex shapes, thus the furthest point away from the center of the disk inside the cell is a vertex on the cell. Compute the furthest point for each cell can be done in $O(n)$ time. If for all of them, it is within $r$, then the set of disks covers the rectangle.

A $O(n \log n)$ algorithm.

---
Tags: algorithms, computational-geometry
---


title: Simple FSM question

text:
# Question
Title: Simple FSM question
Considering this FSM:

Can someone explain me why the grammar is not:

1. $S \rightarrow aA$
2. $A \rightarrow aA \mid bB \mid \varepsilon$
3. $B \rightarrow bB \mid \varepsilon$

Why does A not have a transition to $\varepsilon$?

# Answer
> 6 votes
Both grammars are wrong: The first does allow String $b$, which is not accepted by the NFA, the second does not allow $\epsilon$, which is accepted by the NFA.

Note that some definitions of regular grammars don't allow renaming of variables, which makes the first grammar irregular. In the same way $\varepsilon$-transitions don't extend the expressive power of NFAs, renaming variables does not extend the expressive power of regular grammars.

So if the automaton is what you want (i.e. ensure that a word which contains a $b$, contains an $a$, too), just add $S \rightarrow \varepsilon$ to your second grammar. If the first grammar is what you want ($\\{a\\}^\*\\{b\\}^\*$) add $S{b \atop \rightarrow }B$ to your automaton and $S \rightarrow \varepsilon\mid bB$ to the second grammar.

---
Tags: formal-grammars, finite-automata
---


# Question
Title: Syntax of a Pushdown Automata transition function
I just learned PDAs in class today, but am having problems understanding the syntax of the transition function. Could someone please explain to me the meaning of this syntax:

$\delta(q, \lambda, S) = \\{(q, aaB), (q, bbA)\\}$

This is one of the rules for my language. I am unsure of what the meanings of this syntax exactly is.

# Answer
> 3 votes
The rule, in English, can be rendered roughly as follows:

> If the machine is in state $q$, and $S$ is the topmost stack symbol, the machine may do either of the following things without consuming any input: it may remain in state $q$ and replace $S$ with $aaB$; or it may remain in $q$ and replace $S$ with $bbA$.

A good way to think about PDAs and transitions is to reason about configurations. The configuration of a PDA consists of the following information: the state, the unread input, and the contents of the stack. Indeed, this makes the transition function (almost) a (partial) function from configurations to (sets of) configurations.

* $q$ is the state;
* $\lambda$ is used to indicate that the current symbol may be input symbol, and that the input should not be reduced as it normally would after a transition;
* $S$ gives the topmost stack symbol, which is the only part of the stack contents the PDA can see.

---
Tags: terminology, automata, pushdown-automata
---


# Question
Title: Initial temperature in simulated annealing algorithm
I've done some testing of different initial temperatures in my simulating annealing algorithm and noticed the starting temperature has an affect on the performance of the algorithm.

Is there any way of calculating a good initial temperature?

# Answer
> 10 votes
As noted by Thomas Klimpel in the comments, a certain acceptance probability is often used, which is equal to say $0.8$. The following is a simple iterative method to find a suitable initial temperature, proposed by Ben-Ameur in 2004 \[1\]. In the following, $t$ is a strictly positive transition, $\max\_t$ and $\min\_t$ are the states after and before the transition, $\delta\_t$ the cost difference $E\_{\max\_t} - E\_{\min\_t}$ and $\pi\_{\min\_t} \dfrac{1}{|N(\min\_t)|}$ the probability to generate a transition $t$ when the energy states are distributed in conformance with the stationary distribution

$$\pi\_i = \dfrac{|N(i)|\text{exp}(-E\_i/T)}{\sum\_j |N(j)| \exp(-E\_j/T)},$$

where $N(i)$ denotes the set of neighbors of $i$.

Finally, $\text{exp}(-\delta\_t/T)$ is the probability of accepting a positive transition $t$. Now, we can have an estimation $\hat{\chi}$ of the acceptance probability $\chi(T)$ based on a "random" set $S$ of positive transitions:

\begin{eqnarray} \hat{\chi}(T) &=& \dfrac{\sum\_{t \in S} \pi\_{\min\_t} \dfrac{\text{exp}(- \delta\_t / T)}{|N(\min\_t)|}}{\sum\_{t \in S} \pi\_{\min\_t}\dfrac{1}{|N(\min\_t)|}} \\ &=& \dfrac{ \sum\_{t \in S} \text{exp}(- E\_{\max\_t} / T) }{ \sum\_{t \in S} \text{exp}(- E\_{\min\_t} / T) }. \end{eqnarray}

We want to find a temperature $T\_0$ such that $\chi(T\_0) = \chi\_0$, where $\chi\_0\in\]0,1\[$ is the acceptance probability we desire.

$T\_0$ is computed by an iterative method. Some states and a neighbor for each state is generated. This gives us a set of transitions $S$. The energies $E\_{\max\_t}$ and $E\_{\min\_t}$ corresponding with the states of the subset $S$ are stored. Then a value for $T\_1$ is chosen, which can be any positive value. $T\_0$ is then found with the recursive formula

$$T\_{n+1} = T\_n \left(\dfrac{\ln(\hat{\chi}(T\_n))}{\ln(\chi\_0)}\right)^{1/p},$$

where $p$ is a real number $\geq 1$.

When $\hat{\chi}(T\_n)$ gets close to $\chi\_0$ we can stop. $T\_n$ is now a good approximation of the wanted initial temperature $T\_0$. For more explanation, proofs and discussion, please see the first section of the original paper \[1\].

---

\[1\] Ben-Ameur, Walid. "Computing the initial temperature of simulated annealing." Computational Optimization and Applications 29, no. 3 (2004): 369-385.

# Answer
> 3 votes
this is a very advanced topic related to getting very tight optimums. my understanding, the initial temperature is generally considered part of a "temperature schedule" strategy for which there is some deep research. in other words both the initial temperature condition and the temperature decay algorithm (which you dont mention) affect the overall optimization results. simple strategies or heuristics for both often yield good or "good enough" results.

there is however at least one paper that studies the initial temperature alone.\[1\] the bottom line is that unless you are doing very advanced work, treating the initial temperature as a parameter of the problem and iterating over different initial temperatures as part of the overall optimization \[after finding that it does indeed affect results\] is a very reasonable and a probably widespread practice.

or, even just choosing an initial temperature that gives good results is also common (it would seem to be somewhat surprising & not be often that problem instance optimization results vary substantially from a "better" initial temperature parameter found by trial-and-error). as dhj pointed out some problems will be more sensitive than others to initial temperature.

\[1\] Computing the Initial Temperature of Simulated Annealing Ben-Ameur 2004

\[2\] An Efficient Simulated Annealing Schedule: Derivation Lam & Delosme

\[3\] Temperature control for simulated annealing Munakata & Nakamura

---
Tags: optimization, artificial-intelligence, heuristics
---


title: Can an FSA count?

text:
# Question
Title: Can an FSA count?
This may be a silly question. It seem clear that an FSA, since it is finite, can only count the number of symbols in its input string up to a number bounded by the number of its states. But now suppose we equip the FSA with output (e.g. printing) capabilities. It would then be *very* easy to construct a machine capable of printing one symbol for each symbol that it reads. Would that count as counting? If not, why not?

To put it in terms of FSTs instead: I take it that it is not possible to construct an FST capable of mapping a string of an arbitrary length to a binary representation (i.e. a number in the base-2 numeral system) of its length. But it IS of course trivial to construct an FST capable of mapping a string of arbitrary length to a string of says zeroes (or ones) of the same length. But that could count as counting, could it not, beacuse what the FST is doing is building a representation of the length of its input. A somewhat odd representation, but still a representation, is it not?

# Answer
> 9 votes
This question is a bit vague, so here is a vague answer: Translating unary to unary is not exactly counting, since the machine doesn't actually "know" what the size of the input was "in the end".

You realize this, of course, which is why you question the fact that it is indeed counting.

Translating from unary to binary, however, seems like a way-more advanced operation, because it does not only involve counting, it also involves arithmetic.

So perhaps the more precise notion to look at, instead of counting, is *comparing*. That is, given two numbers (in unary) $1^n$ and $1^m$, determine if $n=m$.

The ability to do this comparison is what gives rise to the famous non-regular language $\\{a^nb^n: n\ge 0\\}$. And the inability of an NFA to count is what makes this language non-regular.

Interestingly, this language is a CFL. And indeed, the corresponding automata model - PDAs, do have the ability to do a limited comparison.

When you talk about comparing, transducers no longer give you any additional power, so the question is resolved in that sense.

An additional note: completely informally, the ability to compare two numbers can often be used to simulate a 2-counter machine Minsky Machine, which are equivalent to TMs.

# Answer
> 4 votes
**No.** Finite state automata do not count. They may do things that look like it, but they cannot count. They can even do a little (hard-wired) computations (like determining whether a binary number is divisible by three) but that is not counting.

A little story. You are on a big rectangular square in a famous city. The locals tell you the square is actually square. If you can count you check whether the horizontal and vertical numbers of tiles match by counting tiles along the sides of the square. If you cannot count you can still verify the claim: start at a corner and walk diagonally. If you exactly reach the opposite corner you have a square.

In your example the fsa tests whether a string has an equal number of $a$'s and $b$'s by tallying these numbers to two different output tapes. Another device has to be doing the final comparison, unless you have a trick to handle the letters $a$ and $b$ in pairs and cros off one against the other. Like in the square.

Now a more formal model to compare with. According to the Chomsky–Schützenberger Theorem every context-free language $L$ is an inverse of a finite state transduction $T$ of the Dyck language $D\_2$ on two pairs of brackets $L = T^{-1}(D\_2)$ (it is not stated like that on wikipedia, but you have to believe me). Now the finite state transducer $T$ can "accept" its context-free language $L$ as follows (for each language its own transducer). On input $T$ transforms the string into the (guessed) series of pops and pushes of the pda for $L$, then test whether the result is pushdown behaviour, i.e., the result is a string in $D\_2$. (Technical details omitted, but this is as claimed by the Ch-Sch Theorem: one has $w\in T^{-1}(D\_2)$ iff $T(w) \in D\_2$)

My point here is that some "computation" is done by the transducer but much power is hidden in the test with $D\_2$. Likewise your example, where two letters are sorted on two tapes.

# Answer
> 1 votes
@Shaull: Thanks for your answer! I'm new to StackExchange and don't know how to comment on an answer, so I choose to write an answer instead, in the hope that I may be forgiven.

Hmm, it seems to me that a shepard counting his sheep by writing a mark on a slip of paper for each sheep that he sees, or a prisoner counting the days he's been in jail by writing marks on the wall, are counting. Why wouldn't n marks on a slip of paper or on a wall count as a representation of the number n? Isn't that what is called a tally representation? AFAICS it is in no obvious way inferior to (say) a binary representation, except that it uses more space.

I suppose that for you then, "know" means that it has an internal representation of the count in the end. Then, of course, it is obvious that an FSA of FST cannot compute the length of an arbitrary string. But if we don't require knowledge in that sense, but demand only that the FSA or FST should be able to tell the result to an external observer, then it seems to me that presenting the count in a tally format should be ok.

Furthermore, if an FSA is equipped with both incremental input and output, then it should in principle be able to use its external environment as a read/write memory, and thus be as powerful as a Turing machine. Right?

Thanks for bringing up the case of comparing. Now, it appears to be the case that if we lift the requirement of an internal representation, and we only require that the machine is able to present the result to en external observer, then we could easily build an FSM that could produce a kind of graphical presentation of the outcome. Suppose the FSM, upon readins "aaaaaabbbbbb" wrote

000000
000000

then, since the bars are of the same length, the FSM has accepted the string "aaaaaabbbbbb". Two bars of the same length means "yes", different lengths means "no".

I guess I'm bending the rules, but that's what I want since I'm interested in the more or less implicit assumptions that are being made in the field of mathematical linguistics.

# Answer
> 1 votes
FSMs can "count" within a finite range/number of steps signified by state transitions. however, they cannot count past a finite number of steps.

there is a sense in which an FSA-like machine can count. a closely related machine is called a Finite State Transducer. the transducer can indeed count in the sense of "piped" input and output. a single transducer can take an input sequence (say in binary) and "transduce" it to an output sequence that is incremented. then one "chains" the (identical) count-by-1 transducers, each one incrementing its input by 1 and outputting it. its also like a rudimentary "streaming algorithm".

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


# Question
Title: Why is the following language not context-free?
$L = \\{a^n b^m | m \not= n^2 \\}$ I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck.

Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ and $b$ symbols in them. Otherwise pumping would generate strings not of the form $a^i b^j$.

Hence both $v$ and $y$ must consist only of one kind of symbol each. Beyond this I wonder what string in $L$ has to be chosen in order to pump and obtain something of the form $a^n b^{n^2}$.

***Alternative idea :*** Assuming that $L$ is context-free, then I must have a PDA accepting it by final state. Can I say that this PDA can be adjusted\* to accept $L'$ i.e., all $a^n b^{n^2}$ ? However I know that $L'$ is not a CFL. Hence, contradiction ?

\*Adjusted = Make the non-final state on reading $a^n b^{n^2}$ as final and the rest as all non-final.

# Answer
Your first approach is not very clear. What are $n$ and $m$? You have to *fix* a word in order to use the Pumping lemma; please see our reference question for how it's done.

Your second approach is fundamentally flawed as CFL is *not* closed against complement, i.e. your PDA construction does not work. Also, note that $L^c$ does not only contain words of the form $a^nb^{n^2}$, but also all that do not match $a^\*b^\*$.

Towards showing that $L$ is not context-free, note that $\mathrm{CFL} \cap \mathcal{L}(a^\* b^\*)$ is closed against complement (see here). Therefore, if $L$ was context-free so would be

$\qquad L' = \\{a^n b^m \mid m = n^2\\}$.

It is easy to show that $L'$ is not context-free by using the Pumping lemma.
> 2 votes

# Answer
Examining this answer mentioned by Raphael,

I don't believe the pumping lemma could help you with this language. It seems you can always choose the part to pump so that you will "miss" the condition that $m=n^2$.

I also believe the same difficulty will be there if you try to use Ogden's Lemma, which generalize the pumping lemma to deal with such problematic questions, (marking $N$ places will reduce to pumping the marked substring.)

However, the method using Parikh's Theorem, should work and is not very difficult for this case, since $\Psi(L) = \\{ (n,m) \mid m\ne n^2\\}$. You are left to show that it is not a finite union of "linear" sets. Not too easy, but should be doable.
> 2 votes

---
Tags: formal-languages, context-free, automata, finite-automata, pumping-lemma
---


# Question
Title: Average length of s-t (simple) paths in a directed graph
Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating them? What if paths are allowed to revisit vertices?

Relevant results on special graphs could also be helpful.

# Answer
> 3 votes
calculating/estimating/approximating the average path length has been studied for some random graph models including the Erdos-Renyi model and the Barabasi-Albert scale free networks, and also the Strogatz small world graphs which may be suitable as approximations for your graphs. \[it would be better if you could narrow down/detail some nature/characteristics of the graphs you're studying.\]

---
Tags: algorithms, complexity-theory, graphs, approximation, enumeration
---


title: Convert CFG to PDA

text:
# Question
Title: Convert CFG to PDA
Is there any set of rules or methods to convert any context free grammar to a push down automata?

I already found some slides online but I wasn't able to understand them.

In slide 10 he speaks about some rules could anyone explain that?

# Answer
> 1 votes
The actual rules for this construction of a PDA from a given CFGare given on slide 7 in this presentation. Wikipedia calls these rules "match" and "expand". The context-free rules are simulated on the stack (leftmost variable rewritten) and whenever a terminal is generated it is compared with the next symbol on the input. The PDA needs only a single state $1$.

> intitial stack symbol $S$ (the axiom of the grammar)
>
> $(1,\varepsilon ,A,1,\alpha )$ for each rule $A\to \alpha$ (*expand*)
>
> $(1,a,a,1,\varepsilon )$ for each terminal symbol $a$ (*match*)

Note however that this PDA will accept "by empty stack", i.e., whenever the stack is empty after the input has been read. Common PDA models accept "by final state", i.e., whenever an accepting state is reached after the input has been read. For this we need another state $2$ for accepting and a new bottom of stack symbol $Z$ to recognize the empty stack and move to the accepting state. We have to start with $SZ$ on the stack now, and since classical models start with a single stacksymbol here we start with $Z\_0$ and rewrite in the first step.

> $(1,\varepsilon ,Z\_0,1,SZ )$ (initialize)
>
> *expand* and *match* as before
>
> $(1,\varepsilon ,Z,2,Z )$ (move to accepting state)

The slides you use are from a course by Jeff Ullman it seems. (One of the authors of a famous book on formal languages and automata). He also has prepared an online course on the topic, where I guess he will explain the details himself.

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


# Question
Title: Difference between Dominant strategy and Winning Strategy
I am a little bit confused by the definition of dominant strategy and winning strategy, what's the difference between them.

Following are the definitions taken from wikipedia, below every definition I added some thoughts. If you fell that my thoughts are not correct or ambigues please let me know.

> **Dominant strategy**.In game theory, dominant strategy (commonly called simply dominance) occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play. Many simple games can be solved using dominance.

The first interesting note is that the term **dominant strategy** is applied only to two different strategies, and more precisely it's should be defined as "A is dominant strategy over B", actually the notion "dominant strategy" might be relevant to the game itself in this case the dominant strategy A dominates over all other strategies of the player.

> **Winning strategy**.A strategy is winning if the player following it must necessarily win, no matter what his opponent plays.

This notion sounds like stronger notion than dominant strategy, because having winning strategy its guaranteed that the player wins if he follows the strategy no matter what the opponent does, on the other hand dominant strategy does not guaranteed the win, it only says that dominant strategy guarantees the best possible outcome for the player over all possible player's strategies and **no matter what the opponent does.**

I would to emphasize one common property for the dominant strategy and the winning strategy they both determined by the outcome of the game and **don't depend on the strategy of the opponent.**

In my opinion, winning strategy is always a dominant strategy, but vice verse is not always true.

Do you agree with the intuitive understand and thought?

# Answer
> 2 votes
Your intuition seems mostly correct. However don't forget that not all games are winner vs. loser, see e.g. Coordination games. The meaning of a winning strategy is somewhat meaningless there, unless you define the winner to be the one with the greater outcome (or allow multiple winners which gain more than a certain threshold). Dominance is still an important tool for those strategies.

There is another problem, because your definition of domination includes "better" in any case. This is a **strict dominance**. A **weak dominance** means "at least as good as" in all cases and "better" in at least one case, where case means an opponents strategy (or a set of strategies for multiple opponents).

1. Possible outcomes are only $\\{\text{win},\text{lose}\\}$: A winning strategy for you results in $\text{win}$ for any strategy of the opponent and is thus weakly dominant compared to any non-winning strategy, if there is one. But in many games an opponent can play so badly, that some non-winning strategies lead to a win nevertheless and so they are not strictly dominated by a winning strategy. But more important than the dominance of winning strategies is the dominance between non-winning strategies of your opponent. If s/he has a weakly dominant strategy relative to all other strategies and you can win against this single strategy, you have a winning strategy.
2. Possible outcomes are some set linear ordered set $A$ and you win, if your profit is greater than that of the opponent (this is **not** a usual definition, one would use other tools like equilibria in this case). For example in the following table each player has two strategies and yours correspond to the rows (each cell is: your outcome, others outcome): $$\matrix{10,12&\mid &10,12\\\hline\\7,4 &\mid&7,4}$$ If you choose the second strategy you'll always win and if you choose the first one, you'll lose, but your outcome is higher, so choosing row $1$ dominates a winning strategy.

Resumé: Dominance is a much broader concept and for many but not all games winning strategies are weakly dominant to at least one other strategy.

---
Tags: terminology, game-theory
---


# Question
Title: Why we need EEPROM in this micro-controller
PIC16F887 Block Diagram

According to the block diagram above, since we already have Program Memory, which may be used to store our program, why should we still need EEPROM? What is it for?

# Answer
> 5 votes
See EEPROM#Related\_types on Wikipedia. Your Program Memory is likely flash memory, which you'll flash (i.e. completely erase and rewrite) with your program every time you like to change it. 8KB is smaller than the usual size of blocks for flash memory, so its unlikely that you can erase only a half or a quarter of your Program Memory.

The program itself may store small quantities of information (a few bytes for important data) without erasing itself by using the EEPROM, which can be written to bytewise (or wordwise).

So the EEPROM is like a tiny hard disk and the Program Memory is more like a tiny rewritable CD.

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: Does Turing Machine divergence depend on the input?
If there is a Turing Machine $M\_e$ (computing some partially computable function $f$), is there an algorithm to decide if $f$ diverges for all possible inputs?

# Answer
> 3 votes
No. It is very easy to reduce $A\_{TM}=\\{(M,w): M$ accepts $w\\}$ to the complement of the problem you describe: given input $(M,w)$, output a machine $M'$ that simulates $M(w)$. If $M$ accepts $w$ then $M'$ halts and accepts. Otherwise, $M'$ goes into an infinite loop (either if $M$ loops on $w$, or manually if $M$ rejects $w$).

Now, if $M$ accepts $w$, then $M'$ does not diverge on every input, and otherwise it does.

---
Tags: computability, turing-machines, undecidability, halting-problem
---


# Question
Title: Why the name Recursively Enumerable and Recursive?
Why did the sets of languages accepted/decided by a TM get the name Recursively Enumerable and Recursive, respectively?

# Answer
> 4 votes
A recursive set is synonymous with computable set. In the beginning of computer science, the notion of computer had not been completely fleshed out, and there were various ideas on the matter. These ran from Turing's machines, Church's Lambda calculus, and Kleene-Gödels recursive function theory. The idea is a set is computable if its elements can be decided by a (terminating) algorithm.

Recursively enumerable sets are more general. It turns out that not every subset of the natural numbers is decidable by an algorithm. However, for some sets, we can give a procedure (possibly non-terminating) that will enumerate the elements of the set (enumerate is used because each number appears exactly once thus a bijection from the natural numbers to the set in question is defined). This is equivalent to saying that the set is semi-decidable in more modern terms.

---
Tags: terminology, computability, turing-machines, history
---


# Question
Title: What determines valid and invalid turing machines?
According to my understanding, a Turing machine that's valid *has* to have finite steps to finish a certain step. If this is right, what else determines the validity of a turing machine?

# Answer
If you are referring to what I think you are referring to then your understanding seems correct.

A Turing machine has a precise definition: It is a tuple ... see for example http://en.wikipedia.org/wiki/Turing\_machine#Formal\_definition

Any system with the same components and conditions as described by the definition is indeed a Turing machine. Anything else (which may at first glance appear to be a Turing machine) is not a Turing machine.

This distinction is to weed out some wrong intuitions.
Here is an example adopted from: https://stackoverflow.com/questions/2435607/why-is-this-an-invalid-turing-machine

For example (given a polynomial P as input):

Start counter at 0 Start Zero at False while(not Zero) { eval P(counter) if ^^ is 0 set Zero to True } Return True

Can be computed by a Turing machine (i.e. describes a valid Turing machine) while

Start list at \[\] Start counter at 0 while(true){ add eval P(counter) to list } if any element of list is 0 return true else return false

Describes an invalid Turing machine, i.e. the code does not correspond to a Turing mahcine.

Well ^^ is all I can come up with. Maybe it will help.
> 1 votes

---
Tags: terminology, turing-machines
---


title: Cartesian construction of PDA and DFA

text:
# Question
Title: Cartesian construction of PDA and DFA
How would I go about using Cartesian construction to find the intersection between a PDA and a DFA?

Is there another term for Cartesian construction? Would it be similar to the procedure for finding the intersection/union of 2 DFAs?

# Answer
The more common term is the "product construction".

The product of a PDA and a DFA is a PDA whose state space is the Cartesian product of the states of the two automata (just like in two DFAs), the transition function is similar to the product construction in DFAs, only the PDA component can act on the stack.
> 6 votes

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


# Question
Title: Fair cake-cutting when players join late
The usual statement of the fair cake-cutting problem assumes that all $n$ players get their share at the same time. However, in many cases the players arrive incrementally. For example, we may divide a cake over $n$ players, but then a new player arrives and wants a share.

Usually, fair cake division requires a lot of effort (for example, requires the players to answer many queries), especially when the number of players is large.

Is it possible to use the existing division of the cake over $n$ players, in order to create a new division of the cake to $n+1$ players, with minimal additional effort (i.e. substantially less effort than re-distributing the cake from scratch)?

# Answer
I will say up front that I can't provide a good answer to your question (I think you could maybe get a research paper out of it if you could), but I think I can help by defining the problem formally and stating where some of the difficulties lie.

**Background**. Let me clearly state the model for cake-cutting. We wish to divide the interval $\[0,1\]$ between $n$ players. Each player $i$ has a valuation function $v\_i(S)$ over subsets $S$ of the cake. We will assume that this function is a probability measure; it is nonnegative and additive (for disjoint $A,B \subseteq \[0,1\]$, $v\_i(A \cup B) = v\_i(A) + v\_i(B)$) and $v\_i(\[0,1\]) = 1$. A solution to this problem is a *protocol* or algorithm that queries the players and assigns portions of the interval. Note that players may misreport/lie in answering queries.

Some papers will have more specific restrictions; *e.g.*, valuation functions are continuous, or piecewise-linear, or piecewise-constant.

Let the pieces assigned to the players be $\\{S\_1,\dots,S\_n\\}$. We often want the following properties of a protocol:

* **proportionality**: Every player $i$ has a strategy that guarantees s/he receives a value of at least $(1/n)v\_i(\[0,1\])$. (From $i$'s perspective, s/he gets $1/n$ of the total value of the cake.)
* **envy-freeness**: Every player has a strategy that guarantees that $v\_i(S\_i) \geq v\_i(S\_j)$ for every other player $j$. (Every player prefers his/her own piece to any other player's piece.)

Note that envy-freeness implies proportionality.

There are also "operational" properties we might want, such as cutting into few pieces, polynomial running time (or indeed computability/constructability at all -- we don't want to use the Axiom of Choice to select a subset of the cake!), and so on.

---

**Specific questions to ask**. Two notes. First, any answer to your question will solve the general problem: Start by giving the whole cake to player $1$, then let the other players arrive online and iteratively apply this protocol. So we should expect this problem to be harder than the standard cake-cutting setting that we apply it to.

Second, we can always solve your problem by taking the entire cake back from everyone and using a known algorithm to redistribute it from scratch. So the question is just if there's a somewhat more elegant way to do this. I think a good way to quantify this is "when does the redistribution require less time or fewer cuts than starting from scratch; and/or when do players get to keep a significant portion of their current slice?"

1. *Suppose we have a envy-free allocation for $n$ players. How do we redistribute to produce an envy-free allocation among the $n+1$ players?*

I suspect this is very difficult. The reason is that finding an envy-free, efficient allocation is already a difficult problem. As far as I know, known protocols could require an unbounded number of cuts to the cake and are very complex. (See Brams and Taylor, *An Envy-Free Cake Division Protocol*, 1995.) So there may be nothing better than to take the entire cake back from everyone and redistribute it to the $n+1$ agents using Brams-Taylor.

1. *Suppose we have a proportional allocation for $n$; how do we redistribute to get a proportional allocation for $n+1$?*

I think this is still difficult (although more doable). Consider the case where every player values the cake uniformly and every player has a $1/n$-sized slice. Then whatever the new player does will require reshuffling among everyone. Here's another bad case: Suppose player $1$ has a valuation of exactly $1/n$ for her slice, but values player $2$'s slice at $(n-1)/n$. Suppose player $2$ values her own slice at exactly $1/n$, but values player $3$'s slice at $(n-1)/n$, and so on, with player $n$ valuing her own slice at $1/n$ and player $1$'s slice at $(n-1)/n$. Now the new player arrives. No matter what the new player wants, your protocol will end up having to reshuffle something from player $2$ to player $1$, from player $3$ to player $2$, etc.

---

One reference might be Walsh, *Online Cake Cutting*, in Algorithmic Decision Theory 2011 (pdf link). But I think that paper assumes we know in advance the number of agents arriving, and assumes players must be allocated a piece precisely when they leave (which is before the end of protocol), so it is really not that applicable to your problem.

---

One way to redistribute a proportional allocation that maintains proportionality is as follows. Let each of the present $n$ players cut his allocated piece of cake into $n+1$ pieces that he himself equally values. Player $n+1$ will now choose the best piece, according to him, from each of the $n$ player's cuts. It is easy to show that the resulting allocation is also proportional.
> 6 votes

# Answer
Assume the cake/area is a circle $C$ with radius $r$. Then, we can create $n$ fair pieces by the canonical cake cutting and thus assign each player an area of $\frac{\pi r^2}{n}$. We can then assign the $(n+1)$th a small circle around the center, and subsequent new players rings around that one (swallowing part of the inner circle), and so on. In this way, every player gets one contiguous piece/plot which shrinks in a monotone way for the first $n+1$ players, and moves towards the center for those joining later.

Working out the numbers is simple; for the first new player, simply solve

$\qquad \pi r\_1^2 = \frac{\pi r^2}{n+1}$

to get the radius for his plot. For the second, solve

$\qquad\begin{align} \pi r\_1^2 &= \frac{\pi r^2}{n+2} \\ \pi r\_2^2 - \pi r\_1^2 &= \frac{\pi r^2}{n+2} \end{align}$

to get (outer) radii for both new players, and so on. It seems that player $n + i$ gets outer radius $r\_i = \frac{r\sqrt{i}}{\sqrt{n+k}}$ after $k$ additional players have joined, but I did not prove this.

This is what you get for $n=6$ and $k=0,1,2,3$:

<sup>\[source\]</sup>

The same idea works for regular polygons with $n$ sides. If you assume a rectangle as basic form, you can do a similar thing by assigning the first $n$ equally sized columns and the following players rows (starting at one side).
> 6 votes

---
Tags: algorithms, game-theory, online-algorithms
---


# Question
Title: Parallel merge sort using hypercube connection template
I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in *Designing and Building Parallel Programs* by Ian Foster and it's pretty clear.

What I don't understand is how it's applied on the merge sort in §11.4 The point I'm most interested is the `parallel_merge` function in the pseudocode, i.e. parallel merge algorithm.

The point I'm most interested is the `parallel_merge` function in the pseudocode, i.e. parallel merge algorithm.

```
procedure parallel_mergesort(myid, d, data, newdata)
begin
  data = sequential_mergesort(data)
  for dim = 1 to d
    data = parallel_merge(myid, dim, data)
  endfor
  newdata = data
end

```

Please, explain to me step by step, assuming we have an array of twelve elements $(3,1,5,7,4,2,8,9,4,2,7,5)$ and we've broken this data to four processors like this:

$\qquad ((3,1,5),(7,4,2),(8,9,4),(2,7,5))$.

What data will have each process after each iteration? I understand why we use the hybercube template in this algorithm, but why do we have exactly $i$ compare-exchanges at the $i$-th level? I mean, when $i=1$, we compare-exchange data from processes $1-2, 3-4, .. P-1, P$. That's not $1$, that's $P/2$? Do I misunderstand something?

# Answer
> 1 votes
They write

> The $i$-th parallel merge takes two sequences, each distributed over $2^{i-1}$ tasks, and generates a sorted sequence distributed over $2^i$ tasks.

For $i=1$, that reads

> The first parallel merge takes two sequences, each stored locally on one task, and generates a sorted sequence distributed over two tasks.

That is, *every node* performs *one* compare-merge. Similarly, for higher $i$, *each node* performs $i$ such operations.

They use it to derive "per-processor communication cost" $T\_{comm}$ which clarifies that they do indeed count processor-wise in the prequel. That makes sense, too: communication happens in parallel, so in order to derive bounds on overall runtime you can bound every (abstract) step from above with the longest processing time found among all processors in that step.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, parallel-computing, machine-models
---


# Question
Title: Given a tree, find a vertex which maximizes the minimum distance to any leaf
If I am given a graph which forms a tree, I am interested in finding a vertex which maximizes the minimum distance to any leaf.

I am sure this problem has been studied before. Does anybody know the name of this problem or an algorithm for solving it?

# Answer
> 5 votes
To find a vertex of maximum distance from any leaf, you can perform a breadth-first search starting from many starting points, i.e. the leaves. Because a BFS visits each node by the shortest possible path from the source(s) of the search, we can easily attribute to each node the distance to the nearest leaf.

* Insert into a queue a collection of pairs $(\ell,0)$ for $\ell$ ranging over all leaves, and record $\textrm{max} = 0$.
* Repeat the following until the queue is empty:

1. Pop a pair $(v,d)$ off the queue. If $d = \textrm{max}$, insert $v$ in a collection of maximum-distance elements.
    2. If there are nodes adjacent to $v$ which haven't been visited, push a pair $(w,d+1)$ into the queue for each such neighbour $w$, marking them as having been visited. If there are any such $w$ at all, empty the collection of maximum-distance elements (if it is non-empty), and set $\textrm{max} = d+1$.

The result is a collection of nodes which are all at distance at least $\textrm{max}$ from any leaf.

Let $n = |V|$ (note that $m = |E| = n-1$). Assuming that we can populate the queue with the leaves of the tree in time $O(n)$ by examining all nodes of the graph, and that the vertices have adjacency lists of their neighbours, we "traverse" each edge twice to consider the neighbours of each vertex; then this algorithm takes $O(n+m) = O(n)$ time. It also works for non-trees, taking again $O(n+m)$ time.

# Answer
> 4 votes
Perform breadth-first seach from all leaves in parallel, i.e. visit all neigbours of all leaves, then their respective neighbours, and so on. The node visited last is your winner.

If you let all searches share the `visited` flag, no vertex is visited twice. Since we have a tree, also every edge is visited only once. In total, we get linear runtime (in the number of nodes).

---
Tags: algorithms, graphs, reference-request, trees
---


# Question
Title: Why is one often requiring space constructibility in Savitch's theorem?
When Savitch's famous theorem is stated, one often sees the requirement that $S(n)$ be space constructible (interestingly, it is omitted in Wikipedia). My simple question is: Why do we need this? I understand the requirement for $S(n)$ being in $\Omega(\log n)$, which is clear from the proof. But no proof I have seen so far explicitly uses that $S(n)$ is space constructable.

My explanation: in order to call the procedure REACH (or PATH or whatever you like to call it), the last parameter needs to be "spelled out", and in order not to leave our space bounds of S(n) for one call, we must not need more than $S(n)$ space to write it down.

# Answer
I believe your explanation is correct. The st-REACH subroutine gets $(s,t,\ell)$ as an input, and finds whether or not $t$ is reachable from $s$ by $\ell$ steps. $s$ and $t$ will be the initial and final configurations, and $\ell=2^{O(s(n))}$, the upper bound on the number of different configurations.

In order to set $\ell$ one needs to be able to compute $s(n)$ (or rather, $2^{O(s(n))}$). If this process takes more than $O(s^2(n))$ space, then the entire machine will have space more than the allowed. It is possible that even $O(s^2(n))$ is too much because of the recursive call to st-REACH (is there any other possible reason?), but I didn't check that.
> 2 votes

# Answer
This is elaborated nicely in Dexter Kozen's Theory of Computation textbook, in chapter 2.

Savitch's Theorem (Theorem 1 in his paper) says: if $S(n) \ge \log n$, then $\text{NSPACE}(S(n)) \subseteq \text{DSPACE}(S(n)^2)$. Space-constructibility often seems to be assumed in a proof, but this requirement can be removed by restarting the search with a fixed space bound that is allowed to increase with each attempt.

The confusion perhaps arises because the original Savitch paper is largely about investigating whether $\text{NSPACE}(S(n)) \not\subseteq \text{DSPACE}(S(n))$. It therefore spends a lot of effort on space-constructible functions, due to the following observation from the paper:

> It is natural to ask if there is any storage function whose deterministic and nondeterministic complexity classes are equal. The answer was given by Manuel Blum and is "yes". Blum showed that there are arbitrarily large storage functions L(n) such that a set is accepted within deterministic storage L(n) if, and only if, it is accepted within nondeterministic storage L(n). These functions L(n) are not, however, "well-behaved" and Theorem 3 does not apply to them.

(Here "well-behaved" refers to the space-constructible functions, called *measurable* by Savitch.)
> 8 votes

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


title: What is a computer year?

text:
# Question
Title: What is a computer year?
In one of the text book its mentioned that 'running time of this algorithm is 200 computer years'. Can somebody please explain what is the meaning of a computer year?

# Answer
Computer years, like man hours, are a measure of work. A computer year is the work one computer (of some agreed-upon speed...) performs in a year. 365 computers working in parallel for a day also perform one computer year of work.
> 10 votes

---
Tags: algorithms, terminology, runtime-analysis
---


title: TQBF as interactive game

text:
# Question
Title: TQBF as interactive game
My teacher describes true quantified boolean formula (TQBF) as an interactive game between two players $\exists$ and $\forall$, and asks us to show a winning strategy for the existential player $\exists$. Can someone describe what this game is? I feel like this is background knowledge I am missing.

# Answer
> 4 votes
Hint: Imagine the formula in some (prenex) normal form and consider the order of quantifiers: $\exists x\_1 \forall x\_2 \exists x\_3 \exists x\_4 \dots Q x\_t \phi(\overline{x})$. Let the player corresponding to the first quantifier choose its valuation (true or false) and then continue the game with that variable $x \mapsto v$ where $v$ is the value chosen for $x$, and with the first quantifier removed from the formula, i.e., in the example, if $\exists$ chooses true, let $x\_1 \mapsto \mathtt{true}$ and continue the game on $\forall x\_2 \exists x\_3 \exists x\_4 \dots Q x\_t \phi(\overline{x'})$.

Let $\exists$ be the winner (as usual) if and only if the end result is a quantifier-free true formula.

# Answer
> 3 votes
TQB formulae are in prenex normal form, so all quantifiers are at the beginning of the formula. Try and read such a formula from left to right:

$\qquad \forall w. \exists x. \forall y. \exists z. P(w,x,y,z)$

translates to

> for every $w$ there is an $x$ so that for every $y$ there is a $z$, so that $P$ is fulfilled.

Reading like it like a game goes like this:

* $\forall$ chooses arbitrary $w$.
* $\exists$ has to come up with a fitting $y$.
* Out of all values still remaining, $\forall$ chooses arbitrary $y$.
* Finally, $\exists$ has to come up with $z$ so that the predicate is fulfilled.

In general form that does not make too much sense; have a look at the Pumping lemma as a concrete example, which is often taught like a game. Another similar type of game is the Ehrenfeucht–Fraïssé game.

---
Tags: terminology, logic
---


# Question
Title: Is the 0-1 Knapsack problem where value equals weight NP-complete?
I have a problem which I suspect is NP-complete. It is easy to prove that it is NP. My current train of thought revolves around using a reduction from knapsack but it would result in instances of 0-1-Knapsack with the value of every item being equal to its weight.

Is this still NP-complete? Or am I missing something?

# Answer
Yes, this is called the subset-sum problem and is NP-Hard.
> 11 votes

---
Tags: complexity-theory, np-complete, decision-problem, packing
---


# Question
Title: Minimizing a multivariate polynomial over the hyper-cube is NP-Hard
In an exercise I have to show that minimizing a multivariate polynomial with $n$ variables over the hyper-cube $H = \\{ (x\_1, \ldots, x\_n) : 0 \leq x\_i \leq 1 \\}$ is NP-Hard. Formally, given $p(x\_1, \ldots, x\_n)$ and $\alpha$, does $\min\_{0 \leq x\_i \leq 1} p(x\_1, \ldots, x\_n) \leq \alpha$?

My idea is to reduce it to MAX-SAT as follows. Suppose I am given the formula:

$(x\_1 \vee \overline{x\_2} \vee x\_3) \wedge (\overline{x\_1} \vee \overline{x\_3}) \wedge (\overline{x\_1} \vee x\_2 \vee \overline{x\_3})$

Then I consider:

$p(y\_1, y\_2, y\_3) = y\_1 (1 - y\_2) y\_3 + (1 - y\_1) (1 - y\_3) + (1 - y\_1) y\_2 (1 - y\_3)$

If $p$ reaches a minimum at a corner of $H$ then the assignment: $$x\_i = \textit{true} \ \text{if} \ y\_i = 0 \ \text{and} \ x\_i = \textit{false} \ \text{if} \ y\_i = 1$$ is a solution for MAX-SAT value for the corresponding formula and since MAX-SAT is NP-Hard we are done. However, how do I proceed if $p$ reaches its minimum at an interior point? Or is it the case that it will always be a corner?

# Answer
Hint: Modify your polynomial slightly so that (a) it is always negative, (b) its only zeroes are solutions to SAT.
> 1 votes

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


# Question
Title: $\{xx^r\mid x\in L_1, x^r\in L_2\}$ is context-free if $L_1$ and $L_2$ are regular languages
I have this problem:

> Let $L\_1$ and $L\_2$ be two regular languages. Show that $L\_3 = \\{xx^r : x \in L\_1, x^r \in L\_2 \\}$ is a context-free language.

I am unsure how to prove that some language is context-free. Could someone please provide the steps?

# Answer
> 1 votes
One way to prove that a language is context-free is to find a context-free grammar that recognizes it. Just go through the definition (on Wikipedia for example) and try to find a context-free grammar for $L\_3$ (it's easy). Good luck!

# Answer
> 0 votes
Hint: you don't need to construct any generator, closure properties are sufficient here.

> Details follow later.

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


# Question
Title: How is a witness found in a proof of $\mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$?
I'm having a hard time understanding the actual proof of this proposition:

$\qquad \mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$

The sketch of the proof is on slides 6-8 of this PDF.

So I let $L \in \mathsf{NP}$. That means that there's a deterministic polynomial-time TM $M^1\_L$ s.t. $x \in L \iff \exists w. M^1\_L(x,w) = 1$. I now need to construct a deterministic poly-time TM $M^2\_L$ s.t. $x \in L \iff M^2\_L(x) = 1$.

Looking at the proof in the slides above, I realize that given $x\in\\{0,1\\}^n$, $M^2\_L$ needs to somehow find a witness $w$ for $x$ and then simply return whatever $M^1\_L(x,w)$ does. But how do I find that witness?

# Answer
Let's consider an $\mathsf{NP}$-complete like $SAT$: given a formula $\varphi$, is there a turht assignment $\tau$ such that $\tau \vDash \varphi$?

By assumption $\mathsf{NP} \subseteq \mathsf{P/\log}$ we know that $SAT \in \mathsf{P/\log}$. We will show that $SAT \in \mathsf{P}$ which will imply $\mathsf{NP} \subseteq \mathsf{P}$.

---

### Notations

Let us denote a partial truth assignment as a function from the set of variables to $\mathbb{B}\_\bot = \\{1,0,\bot\\}$ where $\bot$ means the corresponding variable is not determined. We will denote the empty assignment where all variables are left undetermined as $\[\]$ and the assignment that sets only the value of the variable $x$ to $b$ as $\[x\mapsto b\]$. Let $FV(\varphi)$ denote the set of free variables in $\varphi$. Let us also denote the formula resulting from pluging in the values from a partial truth assignment $\sigma$ into a formula $\varphi$ as $\varphi\sigma$.

---

### Witness Search Problem: $SATSearch$

Consider the witness search problem $SATSearch$: given a formula $\varphi$, find a truth assignment $\tau$ s.t. $\tau \vDash \varphi$ if there is one, otherwise return $None$.

It is easy to see that if the witness search problem can be solved in deterministic polynomial-time then $SAT$ is in $\mathsf{P}$: we just run $SATSearch$ on $\varphi$ and $\sigma = \emptyset$ and we accept iff the answer is not $None$.

Also note that if $SAT \in \mathsf{P/\log}$, then so is $SATSearch$: consider the following polynomial time algorithm for $SATSearch$ that uses $SAT$ as a black box:

$\tau = \[\]$
if not $SAT(\varphi\tau)$ return $None$
for $x \in FV(\varphi)$

* if $SAT(\varphi(\tau \cup \[x \mapsto 0\]))$ then $\tau = \tau \cup \[x \mapsto 0\]$
* else $\tau = \tau \cup \[x \mapsto 1\]$

return $\tau$

More generally the claim holds for any class which is closed under Cook reductions.

---

By our assumption $SATSearch\in \mathsf{P/\log}$. Let $M$ be an TM with polynomial running time and advice of length $l(n)=O(\log n)$ where $n$ is the size of the input formula $\varphi$. We show that $SATSearch$ can be solved in deterministic polynomial time.

for all c of length $l(|\varphi|)$

* $\tau = M(\varphi,c)$
* if $\tau \vDash \varphi$ then return $\tau$

return $None$

If $\varphi$ is satisfiable, then at least for the right advice $M$ will return a witness and we can verify it. If the formula is not satisfiable, no $\tau$ can satisfy $\varphi$ so we will return $None$.

The running-time of the algorithm is polynomial and it uses no advice. So $SATSearch$ can be solved in deterministic polynomial time with no advice.

Therefore we can conclude that $\mathsf{NP}=\mathsf{P}$ if $\mathsf{NP}\subseteq \mathsf{P/\log}$.
> 1 votes

# Answer
Here's a sketch of my proof:

It is enough to show that $\mathsf{SAT}\in \mathsf{P}$. Since $\mathsf{SAT}\in \mathsf{NP}$, by our assumption, $\mathsf{SAT}\in\mathsf{P}/\log$.

This means that there exists a sequence of advices $\\{a\_n\\}\_{n\in\mathbb{N}}$ such that $|a\_n|\le \log(n)$, and a polynomial-time DTM $M$ such that for all $x\in\\{0,1\\}^n$, $M(x,a\_n) = 1 \iff x \in \mathsf{SAT}$.

We can use this DTM to construct another polynomial-time DTM $M\_1$ that takes as input $x\in\\{0,1\\}^n$ (an encoding of some CNF formula $\varphi(x\_1,\ldots,x\_m)$) and an advice string $|a|\le \log(n)$ and generates a *candidate* for a witness for $x$ the following way:

1. Verify that $\varphi$ is satisfiable by checking that $M(x,a)=1$, reject otherwise.
2. For $i = 1$ to $m$ do

Run $M(\varphi(\ldots,x\_i=0,\ldots),a)$ and $M(\varphi(\ldots,x\_i=1,\ldots),a)$, Whichever returns 1 is a correct assignment, so output the corresponding value of $x\_i$, and modify the formula $\varphi$ with that assignment for the next iteration...

It's easy to see that $M\_1$ runs in polynomial-time and does indeed produce a correct witness if it exists, and if the advice given was the correct one.

Now, the last step of the proof is to *use* a deterministic poly-time verifier $M\_V$ for $\mathsf{SAT}$ (one exists because it's in $\mathsf{NP}$) and *create* a deterministic poly-time decider for it. We can do this easily, because since the length of the advice is $\log(n)$, there can be at most $2^{\log(n)}=n$ advices, meaning that we can simply create a loop from $i = 0$ to $n-1$ and in every iteration generate a witness $w = M\_1(x,i)$ and then test it with our verifier: $M\_V(x,w)$.

We accept only if one of the witnesses match, and reject if none do.
> 0 votes

---
Tags: complexity-classes, time-complexity
---


# Question
Title: Finding no. of leaf nodes for each node in a BST
A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is

$\qquad \min(\\#\text{leaves in } L(x), \\#\text{leaves in } R(x))$

for $L(x), R(x)$ the left resp. right subtree of $x$, then the worst-case time complexity of the program is

1. $\Theta(n)$
2. $\Theta(n \log n)$
3. $\Theta(n^2)$
4. $\Theta(n^2 \log n)$

I am actually looking for a subtle hint.

# Answer
> 2 votes
Traverse your graph in post order, create two auxiliary functions, $Cost$ and $Total$, first one demonstrates cost of your $g(x)$ at each vertex, second one calculates total number of leafs. set the cost function to zero: $Cost(leaf)=0$ for leaf, and $Total(leaf) = 1$ for leaf, then for parent node set this two functions as:

> $$Cost(v) = min\\{Total(child\_l),Total(child\_r)\\}$$$$Total(v) = Total(child\_l) + Total(child\_r)$$

Because is post order, will be filled correctly and is $O(n)$ algorithm.

But actually worst case complexity in different algorithm may be differ, you can show that you cannot do this better than $\Omega(n)$, and above algorithm is $\Theta(n)$, which gives a tight bound, but, may be someone implement it in a bad way that causes to the $\Omega(n^9)$, or may be someone else provide an algorithm of $\Theta(n^3)$, At all, I mean your current question is not well defined, and if it was for real exam, it was wrong, and any answer which satisfies $\Omega(n)$ barrier, is correct.

# Answer
> 2 votes
Three questions that can lead you towards an answer:

* In a binary search tree with $n$ nodes, how many leaves are there?
* How often is each leaf "counted" by $g$?
* How many predecessors does each leaf have?

---
Tags: algorithms, algorithm-analysis, runtime-analysis, binary-trees, search-trees
---


# Question
Title: How to find the pumping length of a context-free language?
Please help me understand, and if possible, tips, to determine a pumping length $p$.

Suppose I have the example :

Let $G$ be a Context-Free-Grammar with a set of variables $\\{S,A,B,C\\}$, set of terminals $\\{0,1\\}$, start variable $S$, and rules

$S \to ABA \mid SS$
$A \to S0 \mid 1C1$
$B \to S1 \mid 0$
$C \to 0$

Now given the above, how do I find the pumping length $p$?
Please explain how you actually got it from the grammar.

# Answer
As Raphael says in the comments, any sufficiently large number is suitable as a pumping length, however (also as he points out), the proof of the pumping lemma gives an upper bound for the minimum pumping length.

Similar to the pumping lemma for regular languages, we want to take a length that is sufficiently large that we can guarantee that we have used the same production at least twice. For regular languages this often easy to think of as the number states in a minimal DFA for that language.

For context free languages expressed with a grammar, we can take a similar approach and ask "how many symbols can be in the string before I know that I must have used some production twice?". To figure this out you may want to consider how many symbols any production could insert into the string, and what the parse tree for a sufficiently long string may look like (you can consider each level of the tree to be one production). If you do this correctly you can get a minimal pumping length for that grammar (not exactly a precise concept), then taking the minimum of these minimal lengths over all grammars for the language will give you the minimum for the language.

Further hint:

> If there's a rule with $m$ symbols on the right hand side, and the parse tree is $d$ levels deep, what's the maximum number of symbols in the string?
> 3 votes

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


# Question
Title: Is the language $\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free?
Is the language $ L = \\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\\}$ context-free ?

I guess that it's not context free because it seems too complicated for a PDA to decided whether 2 numbers are co-prime or not.

I tried using the pumping lemma to no avail.

Any help would be gladly appreciated.

Edit:

Here is one of my failed attempts with the pumping lemma:

Let $N$ be a constant. Take a prime $p$ such that $p \> N!$ and then take the word $z = 0^p 1^{p+N!} \in L$. Let $ z = uvwxy $ be a decomposition of $z$ satisfying the conditions in the pumping lemma.

If $ vx $ contains only zeros then $ |vx| = k $ is an integer between $1$ and $N$. Define $m$ as $m = N!/k$. For $i = m+1$ the word $ uv^iwx^iy = 0^{p+N!}1^{p+N!} \not\in L $

However, I've failed to find such an integer $i$ for the other decomposition cases.

# Answer
> 4 votes
Ridiculous that I didn't see this earlier...

The proof that the language (call it $\mathcal{L}$) isn't context free is by contradiction. Assume $\mathcal{L}$ is context free, by the pumping lemma for CFGs there is a constant $N$ such that each string $\sigma \in \mathcal{L}$ such that $\lvert \sigma \rvert \ge N$ it can be written $\sigma = u v x y z$ with $v y \ne \epsilon$ such that for all $k \ge 0$ the string $u v^k x y^k z \in \mathcal{L}$. Take $m, n$ different primes (such that $\gcd(m, n) = 1$) and $m, n \> 2N$, and take $\sigma = 0^m 1^n$. The pumped string will be $0^{m + k a} 1^{n + k b}$ for some constants $a$, $b$, not both zero, and such that $a \< m$ and $b \< n$ (we have $a, b \le N \< m / 2, n / 2$ by the way $m$, $n$ were selected). The case of one of them zero was covered by OP, so consider $a, b \ne 0$. Now:

$$ \begin{align\*} m + k a &\equiv 0 \pmod{n} \\ n + k b &\equiv 0 \pmod{m} \end{align\*} $$

This has a unique solution $k^\*$ modulo $m n$ by the chinese remainder theorem (we have $a \< n$, and as $n$ is prime, $\gcd(a, n) = 1$; similarly $b$ and $m$), and thus we can write: $$ \begin{align\*} m + k^\* a &\equiv 0 \pmod{mn} \\ n + k^\* b &\equiv 0 \pmod{mn} \end{align\*} $$ i.e., $m n \mid \gcd(m + k^\* a, n + k^\* b)$. Contradiction.

---
Tags: formal-languages, context-free, pumping-lemma, pushdown-automata
---


# Question
Title: Finding the element that occurs more often than the other
I want an algorithm that calculates which element, among two, appears more often than the other in a sorted array. The array will have only two types of elements.

Example : $aaaaaabbb$

Here $a\>b$.

I have to find an constant time algorithm. Is it possible? The only thing I could come up with was using stack. Push all $a$'s and pop them with $b$. But it takes $O(n)$ operations. Any better approaches? Need a hint (no solution).

# Answer
I am guessing that the solution you are meant to give is to check the middle entry in the array. Below is a spoiler as to why this works. Hover with mouse to see, but I suggest you try to figure it out alone first.

> If the middle number is $a$, then since the array is sorted, $a$ appears more than $b$, and otherwise $b$ does.

However, it is not really true that this is a constant time algorithm, as it assumes you can compute the length of the array in constant time.

This is impossible in a standard TM, and even in a RAM model. It requires at least $O(\log n)$ operations in the latter, where $n$ is the length of the array.
> 3 votes

---
Tags: algorithms, data-structures, search-algorithms, arrays
---


# Question
Title: Does this loop invariant guarantee that the variable never changes?
Suppose you have some loop and and integer k:

```
int k = 5;
for (int i = 0 ; i < N; i++)
{
  //(*)
  //do something
}

```

The loop invariant at (\*) is: $\\{ K=k\\}$

Does that guarantee that $k$ doesn't change in between iterations? if not, is there any otherway to guarantee that?

# Answer
> 3 votes
The loop invariant doesn't "guarantee" anything. It is a summary of relevant information you know about the state of the program when it reaches that point. If your loop is e.g.:

```
k = 5;
...
for(int i = 0; i < N; i++) {
   /* Invariant: k = 5 */
   ...
   k = 207;
   ...
   frob_very_hard(&k);
   ...
   k *= 3;
   ...
   k = 5;
}

```

at the marked point k == 5, but not all over the program.

---
Tags: loop-invariants, program-correctness, hoare-logic
---


# Question
Title: Proof that regular languages are closed against taking the even-length subset
This question is on the GRE Computer Science test booklet (not homework). I tried applying closure properties of regular languages but no success.

Suppose $L$ is a regular language over $\Sigma = \\{0, 1\\}$. Show that the language

$\qquad L' = \\{w \in L \mid |w| \in 2\mathbb{N}\\}$

is also regular.

What I find surprising is that the booklet mentions that the language $\\{w \in L \mid |w| = 2^k, k \in \mathbb{N}\\}$ is not necessarily a regular language.

# Answer
> 5 votes
The language $Even = \\{w\in\Sigma^{\ast}\mid \text{length of }w\text{ is even}\\}$ *is* regular. user5507's answer demonstrates this with an NFA, and it's a basic exercise in most texts.

Then given that $L$ is regular, if we know that regular languages are closed under intersection for the purposes of the question, then the language $L'=L\cap Even$ is also regular.

If we're not allowed to use these closure properties, we can recapitulate the construction that gives the closure property (I'll just sketch it). Given a DFA $M\_{L}$ for $L$ and a DFA $M\_{Even}$ for $Even$, we can construct a DFA for $L' = L\cap Even$ that has a state space that is the product of the state spaces of $M\_{L}$ and $M\_{Even}$, with the follow transition rule: if $\delta\_{L}(\sigma, q\_{i}) = q\_{j}$ and $\delta\_{Even}(\sigma, p\_{m})=p\_{n}$ where $\sigma \in \Sigma$ and the $p$s and $q$s are states of the appropriate machines, then the product machine has a transition $\delta\_{prod}(\sigma,(q\_{i}, p\_{m})) = (q\_{j}, p\_{n})$. Our accepting states are those states $(q\_{i},p\_{j})$ where $q\_{i}$ and $p\_{j}$ are accepting states in their respective machines.

That's the long an fiddly way around.

The second question depends on $L$, that is, if $L$ is not regular, then the intersection of $L$ and $Even$ may is not necessarily regular - the $w\in L$ in the definition is key.

**EDIT:** actually, reading vonbrand's answer, I misunderstood the second part. He is quite correct - the second language is the intersection of $L$ and $X=\\{w\in\Sigma^{\ast}\mid \exists i \in \mathbb{N} \text{ such that } |w| = 2^{i}\\}$ - not $Even$. So while what I said about $L \cap Even$ with $L$ not regular holds, $X$ isn't regular to begin with, so we get the same situation, but $L$ is regular and $X$ isn't.

# Answer
> 3 votes
For the language with lengths an integer power of two, they can be regular only if they are finite. It is easy to prove by the pumping lemma that an infinite language of such kind can't be regular (just look at the lengths of the strings).

# Answer
> 0 votes
If the number of even-length strings in $L$ is finite (say $w\_i,i \in \\{1,\dots,n\\}$, then $L^\prime$ is regular and the regex $(w\_1\mid \dots \mid w\_n)$ accepts it. If it's infinite, then by the pumping lemma we know that for strings $w \in L$, there are strings $x,y,z$ such that $w=xy^iz\in L$ for $i=0,1,2,\dots$. A case-analysis is required:

1. $x,y,z$ are odd-length, $i$ is even: the regex $x(yy)^\*z$ accepts case-1 even-length strings.

---

You should be able to fill in the missing cases. Now a regex accepting strings in $L^\prime$ can be formed by taking the union of the regex's of each case. The resulting regex accepts even-length strings in $L$.

# Answer
> -2 votes
We need to show that

$\\{w ∈ L |$ length of w is even$\\}$ is regular.

In order to show that, it is enough to construct an NFA/DFA for that. You can construct an NFA for this like

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: A pumping lemma for deterministic context-free languages?
The pumping lemma for regular languages can be used to prove that certain languages are not regular, and the pumping lemma for context-free languages (along with Ogden's lemma) can be used to prove that certain languages are not context-free.

Is there a pumping lemma for *deterministic* context-free languages? That is, is there a lemma akin to the pumping lemma that can be used to show that a language is not a DCFL? I'm curious because almost all of the proof techniques I know to show that a language is not a DCFL are really complicated, and I was hoping that there was an easier technique.

# Answer
There *is* a Pumping Lemma specifically for DCFL, under the title "A Pumping Lemma for Deterministic Context-Free Languages", by Sheng Yu; Information Processing Letters 31 (1989) 47-51, doi 10.1016/0020-0190(89)90108-7. With this explicit title I must apologize that I missed it!

The online copy unfortunately has a blank spot in one of the formula, so I hope I reconstructed the result properly. Below ${}^{(1)}y$ is the first symbol of $y$ (when it exists) or $\varepsilon$ (if $y=\varepsilon$).

**Lemma 1** (Pumping Lemma). Let $L$ be a DCFL. Then there exists a constant $C$ for $L$ such that for any pair of words $w,w'\in $ if

(1) $w=xy$ \[?\] and $w'=xz$, $|x|\>C$ and

(2) ${}^{(1)}y = {}^{(1)}z $, \[?\]

then either (3) or (4) is true:

(3) there is a factorization $x=x\_1x\_2x\_3x\_4x\_5$, $|x\_2x\_4|\ge 1$ and $|x\_2x\_3x\_4|\le C$, such that for all $i\ge 0$ $x\_1x^i\_2x\_3x^i\_4x\_5y$ and $x\_1x^i\_2x\_3x^i\_4x\_5z$ are in $L$;

(4) there exist factorizations $x=x\_1x\_2x\_3$, $y=y\_1y\_2y\_3$ and $z=z\_1z\_2z\_3$, $|x\_2|\ge 1$ and $|x\_2x\_3|\le C$, such that for all $i\ge 0$ $x\_1x^i\_2x\_3y\_1y^i\_2y\_3$ and $x\_1x^i\_2x\_3z\_1z^i\_2z\_3$ are in $L$.

Two applications of the Lemma are given: $\\{ a^ib^i \mid i\ge 0 \\} \cup \\{ a^ib^{2i} \mid i\ge 0 \\}$ as well as $\\{ w\in\\{a,b\\}^\* \mid w=uv, |u|=|v|, \mbox{ and } v \mbox{ contains an } a \\}$ are not DCFL. The proof uses the fact that each DCFL has an LR(1) grammar in Greibach normal form.
> 10 votes

---
Tags: context-free, proof-techniques, pumping-lemma
---


title: Proving calculating Minhash

text:
# Question
Title: Proving calculating Minhash
I'm reading about MinHash technique to estimate the similarity between 2 sets: Given set A and B, h is the hash function and $h\_\min(S)$ is the minimum hash of set S, i.e. $h\_\min(S) = \min(h(s))$ for s in S. We have the equation: $$ p(h\_\min(A) = h\_\min(B)) = \frac{|A \cap B|}{|A \cup B|} $$ Which means the probability that minimum hash of A equals to minimum hash of B is the Jaccard similarity of $A$ and $B$.

I am trying to prove above equation and come up with a proof, which is: for $a \in A$ and $b \in B$ such that $h(a) = h\_\min(A)$ and $h(b) = h\_\min(B)$. So, if $h\_\min(A) = h\_\min(B)$ then $h(a) = h(b)$. Assume that hash function h can hash keys to distinct hash value, so $h(a) = h(b)$ if and only if $a = b$, which means the probability is $\frac{|A \cap B|}{|A \cup B|}$. However, my proof is not complete since hash function can return the same value for different keys. So, I'm asking for your help to find a proof which can be applied regardless the hash function.

# Answer
> 3 votes
Min-hash are not just (standard) hash functions, but a **family** of functions $\cal H$, such that if you randomly pick one function $h\leftarrow \mathcal{H}$ out of the family, it will satisfy the requirement you have in your question.

Check "Min-wise independent permutations" by Broder, Charikar, Frieze and Mitzenmacher, 2000. They define this notion and analyze it in a very simple way to follow.

From a practical point of view, you usually have a bound on the size of the sets you use (say $2^{256}$, probably more than the number of atoms in the universe). Then, a 256bits output is enough to have hash-functions that are permutations (and clearly, the set of all the permutations is a good family of min-hash functions..) So the problem is not the output length, but how many functions are there in the min-hash family, so that if you pick one at random, you get the probability that any element is the minimum exactly $1/2^{256}$.

To overcome the huge set of hash-functions (there are $256! \gg 2^{256}$ permutations of 256 bits..), they relax the requirements on the probability of the min-hash and get an approximated notion of $\epsilon$-min-hash, which guarantees that $$\Pr\_{h\leftarrow {\cal H}}\[h(A)=h(B)\] = \frac{|A\cap B|}{|A\cup B|}\pm \epsilon$$ which is more useful from efficiency perspective (the set $\mathcal{H}$ is smaller and easier to get).

---
Tags: hash
---


# Question
Title: Extracting the set of chains from a partial order
Given a partial ordered set (poset) $S$, is there a known procedure or algorithm to find the set of chains (i.e. subsets of $S$ where every two elements are comparable)?

Note: I am asking here instead of math.SE because i'm looking for *an algorithm* for the problem.

# Answer
Yes there is, have a look at :

Chen, Yangjun, and Yibin Chen. "On the Decomposition of Posets." Computer Science & Service System (CSSS), 2012 International Conference on. IEEE, 2012.

and also this:

Daskalakis, C., Karp, R. M., Mossel, E., Riesenfeld, S. J., & Verbin, E. (2011). Sorting and selection in posets. SIAM Journal on Computing, 40(3), 597-622.
> 5 votes

---
Tags: algorithms, partial-order
---


# Question
Title: How to find the minimum number of vertices whose removal make the graph disjoint
Given a graph $G = (V,E)$.

Is there any algorithm which finds the minimum number of vertices to be removed from $G$ so that every vertex in the graph becomes disjoint, *i.e.*, every vertex is disconnected from every other vertex?

# Answer
> 10 votes
This problem is known as *vertex cover*. The minimum vertex cover of a graph is the smallest number of vertices adjacent to every edge. The complement of a vertex cover is an *independent set*.

Given a graph $G = (V,E)$ and $k \in \mathbb{N}$, the problem of finding whether $G$ has a vertex cover of size at most $k$ is NP-complete. However, it admits a polynomial kernel and is thus *fixed-parameter tractable*. It also admits a quite easy and nice $2^k n^{O(1)}$ branching algorithm:

Pick any edge $e = vu$: Either $v$ goes to the vertex cover, or $u$ goes to the vertex cover. Make a recursive algorithm which picks $e$, removes $v$ from the graph and calls itself recursively with $k-1$ as parameter. If that fails, proceed by removing $u$. If that fails as well, can conclude that there is no such vertex cover.

There are also nice 2-approximation algorithms for this problem.

Ps. this is maybe one of the "easier" NP-hard problems. So if you want to implement it, you're in good luck despite the hardness.

Pps. if you want to find an independent set (also known as *stable set*) of size at least $k$, you are *out of luck*, as that problem is $W\[1\]$-complete, see the W-hierarchy. However, there is an $O(2^{0.288n})$ exact algorithm solving independent set using Measure and Conquer by Fomin et al. (SODA 2006) (doi=10.1.1.79.831). A quick caveat here: Many are confused upon first reading why a trivial reduction does not show that independent set is in FPT as well. The answer here lies in the fact that a reduction will set the new parameter $k' = O(n-k)$, i.e., the new parameter will depend on $n$ as well.

---
Tags: algorithms, graphs
---


# Question
Title: Time Complexity of Universal Turing Machine Simulations and the Time Hierarchy Theorem
I have a little problem to understand the proof of the Time Hierarchy Theorem (Hennie and Stearns, 1966) that ensures the existence of a language acceptable in $U(n)$ but not acceptable in $T(n)$ for any functions $T(n),U(n)$, such that $U(n)$ is time-constructible and

$$n \leq T(n) = o\left(\frac{U(n)}{\log T(n)}\right).$$

This proof is based on the existence of the Universal Turing machine simulating any Turing machine with time complexity $T(n)$ in time $T(n) \log T(n)$.

I understand (and believe) the proof that every $k$-tape Turing machine can be simulated by a two-tape Turing machine with a logarithmic overhead. However, I understand this construction only if the simulated Turing machine is fixed, not in the case of the Universal TM simulation.

I see one "problem" in the reasoning given in the cited paper (and also in several standard books on computational complexity) related to the construction of the Universal machine. This "problem" is that in the Universal machine simulation, one computational step of a simulated machine is supposed to be executed in constant time by the Universal machine. In other words, the length of the description of the simulated machine is supposed to be constant.

But is this OK? Since in the proof of the Time Hierarchy Theorem, the input given to the simulated Turing machine is exactly this description, and thus, the description is somehow dependent of $n$. I am aware of that the description can be lengthened by a sequence of leading bits, but this does not seem to solve this problem.

That is, I cannot figure out why the computation step of a simulated machine can be supposed to be executed in a constant time by the Universal machine. The paper of Hennie and Stearns does not pay much attention to this, it merely states that this time is something that is implicitly assumed to be a constant. Similarly in the textbooks I have read on the topic.

I simply cannot figure out why the time complexity of the simulation is $T(n)\log T(n)$, and not $n T(n) \log T(n)$.

I am almost sure that I am missing something. However, I am trying to understand this for a relatively long time and somehow I cannot figure this out.

# Answer
> 9 votes
I'm referring here to the proof of the hierarchy theorem as I am familiar with it, in which I don't see the problem you mention.

We define the language $L=\\{(M,w): M $ does not accept $(M,w)$ within $\le \frac{t(n)}{|M|^3+|M|\log t(n)}, n=|(M,w)|\\}$ (where $t$ is the time function we are working on).

We show that $L$ is decidable in $O(t(n))$ using the universal machine, and in the universal machine each step is indeed dependent on the size of the machine, which is why we have $|M|^3$ in the denominator (the 3 is just some upper bound on the computations needed to simulate a step).

For completeness of the answer: when we try to reach a contradiction, then we assume that there exists a machine $T$ that decides $L$. After this assumption, the encoding of $T$ is fixed, and then a simulation of a single step really does take constant time, and we can reach a contradiction by taking a long enough $w$ to increase the length of the input without changing $T$.

---
Tags: complexity-theory, turing-machines, simulation
---


# Question
Title: What complexity class decision problems can be solved by only addition, multiplication, division and subtraction?
So in what complexity class would all decision problems in that class can be transformed into a problem (by many-one reduction) that its solution only involves basic arithmetic operation of multiplication, division, addition and subtraction?

So, like this: for every problem, there is input and output (we consider only those that halt) and my question is that is there any complexity class that all problems in the class can be transformed into a problem that involves only elementary arithmetic of the form of arithmetic function involving only arithmetic like $2^x+x^5/4-4x+2$ where $x$ is input coded as natural number.

# Answer
The question isn't exactly well-defined, but seems like a good/interesting question to me. I believe the answer you might be looking for is the class of Elementary Recursive functions. This class consists of almost exactly what you described: Problems solvable by functions that can be written with only addition, subtraction, and multiplication of integers. (Except, we also require a zero function and a "projection" function that outputs one of the inputs.)

You can get more functions (the Primitive Recursive functions) by additionally allowing functions that call themselves (but are guaranteed to terminate). Finally, you can get the class of all Turing-computable functions by introducing a minimization operator: find the minimum $x$ such that $f(x) = 0$.

Anyway, it turns out that $\mathsf{EXPTIME} \subsetneq \mathsf{ELEMENTARY}$, so it includes many (most?) problems that we'd usually consider interesting.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: If A is poly-time reducible to B, is B poly-time reducible to A?
Basically, is the following statement true?

> $A \leq\_p B$ $\rightarrow$ $B \leq\_p A$

# Answer
> 7 votes
Short answer: No.

For one example, take $A$ to be the language $A = \\{0, 1\\}^\*$, i.e. the language that contains *every* possible string. It is polytime reducible to pretty much anything, for example 3-SAT (the reduction outputs the formula $x\wedge y \wedge z$ on every input). But 3-SAT is definitely not reducible to $A$: there is nothing to map unsatisfiable instances to.

Maybe a bit less silly. Take $A$ to be any problem in P. Take $B$ to be a problem complete for exponential time (for example the problem of deciding, given a Turing machine $M$, an input $x$, and a number $k$ written in binary, whether $M$ halts on $x$ within $k$ time steps). Because $B$ is complete for exponential time, $A$ is reducible to $B$. Because a polytime reduction from $B$ to $A$ would imply a polytime algorithm for $B$ and therefore for any exponential time problem, contradicting the time hierarchy theorem, such a polytime reduction does not exist.

# Answer
> 1 votes
If $A,B$ are NP-complete, then every problem in $NP$ is polytime reducible to $A$ and polytime reducible to $B$. In particular $A$ is polytime reducible to $B$ and vice-versa. So this answers the question for NP-complete problems.

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


title: Temporal logic for interface invariants

text:
# Question
Title: Temporal logic for interface invariants
I am looking for some sort of temporal logic for expressing invariants in interfaces. Since interfaces do not specify data representation, the invariants must rely solely on the publicly available functions of the interface.

For example, suppose we have a simple interface (Java style) Sum:

```
interface Sum {
    public void add (int a);
    public int getSum();
}

```

I want to express in an invariant that `getSum` returns the summation of `a` in all calls to `add(a)`, without using any data representation of this sum.

The only way I can think of doing this is by using some form of temporal logic. Is there any literature on this subject available I can read? Any pointers would be much appreciated.

# Answer
A standard method is to use so-called *ghost variables*. A ghost variable is just like an ordinary variable, except it appears only in the specification (it isn't part of the program that actually executes). In other words, the ghost variable is not present in the original program; it is added by the spec. The preconditions, postconditions, and invariants are allowed to refer to the ghost variable.

Intuitively, a ghost variable allows you to maintain state about what methods have been invoked in the past; the specifications for those methods can update the ghost variable, thus remembering this information.

We can solve your specific challenge problem by adding a ghost variable `totalSoFar`. Then, we add an appropriate specification for each method, like this:

```
interface Sum {
    ghost int totalSoFar = 0;

    /* postcondition: totalSoFar = old(totalSoFar) + a */
    public void add (int a);

    /* postcondition: returnvalue = totalSoFar */
    public int getSum();
}

```

Notice how the postcondition for `add()` updates the ghost variable, based upon the parameter passed to `add()`. Similarly, the postcondition for `getSum()` describes its return value in terms of the ghost variable.

This is the standard pattern: you use ghost variables to keep track of whatever state you need; for methods that modify this state, you write postconditions to update the state in the ghost variables; and for getters, you express their result in terms of the state of the ghost variables.
> 2 votes

# Answer
Whatever you do, your specification will turn out to have internal state reflecting the accumulator inside your object. For a class this simple, the specification won't be any simpler than the implementation. The point is that for much more complex cases the specification is simpler. Consider a dictionary, where you add data under a key and must be able to retrieve it later. Your specification can very well be the equivalent of a linear array of key/value pairs, and the search a simple linear search. Your implementation would perhaps be a scheme based on hashing or balanced binary trees. The *specification* is easy to reason with, you prove your *implementation* behaves the same as the specification, and you are set. Tomorrow you rip out the implementation, and replace it by some fancier structure, prove again that it complies with the specification. No changes elsewhere.

Specifications are essentially writing the same program again in another (hopefully easier to handle) programming language, probably foregoing any performance considerations, and reasoning that both programs do the same. The specification languages up to date have turned out *much* harder to use than the regular programming languages (and specifications can have bugs too...), and the proof that they behave the same isn't for the faint of heart. And if I come up with an idea of how my program should behave, and program that, it stands to reason that the specification and the final program will share the same misconceptions and missed corner cases. There have been spectacular failures of the "program verification" movement. Look at Berry's "Academic Legitimacy of the Software Engineering Discipline" (CMU/SEI-92-TR-34) for an example of a program of a couple dozen lines, written and "proved correct", then fixed and again verified *for publication in academic journals* by some of the maximal experts in the area several times, and which was wrong each round.
> 2 votes

---
Tags: logic, object-oriented, linear-temporal-logic, software-verification
---


# Question
Title: Finding shortest and longest paths between two vertices in a DAG
Given an unweighted DAG (directed acyclic graph) $D = (V,A)$ and two vertices $s$ and $t$, is it possible to find the shortest and longest path from $s$ to $t$ in polynomial time? Path lengths are measured by the number of edges.

I am interested in finding the range of possible path lengths in polynomial time.

Ps., this question is a duplicate of the StackOverflow question Longest path in a DAG.

# Answer
> 12 votes
For the shortest path problem, if we do not care about weights, then breadth first search is a surefire way. Otherwise Dijkstra's algorithm works as long as there are no negative edges.

For longest path, you could always do Bellman-Ford on the graph with all edge weights negated. Recall that Bellman-Ford works as long as there are no negative weight cycles, and therefore works with any weights on a DAG.

# Answer
> 8 votes
Let $n = |V(G)|$ and $m = |E(G)|$. Let $w(a \to b)$ denote the weight of the edge $(a \to b)$. Suppose that you want to find the minimum and maximum path cost from $s$ to $t$.

Starting from $b := t$, perform the following:

1. If $b$ has already been visited, return the already computed $\min(b)$ and $\max(b)$. Otherwise mark $b$ as visited.
2. Determine and record $\min(b)$ and $\max(b)$ as follows.

* If $b = s$, store $\min(s) := \max(s) := 0$.
    * Else set $$\begin{align\*}\min(b) &:= \min\_{a \to b} \Bigl\[ w(a \to b) + \min(a) \Bigr\] \\ \max(b) &:= \max\_{a \to b} \Bigl\[ w(a \to b) + \max(a) \Bigr\]\end{align\*}$$ ignoring vertices for which $\min(a) = \max(a) = \mathrm{inaccessible}$. When computing minimum and maximum over an empty set of edges (no inbound edges to $b$ at all, or all ignored), set $\min(b) := \max(b) := \mathrm{inaccessible}$.

You should be able to prove that this algorithm runs in time $O(m)$, neglecting the time required to initialise all of the vertex variables.

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


title: Hardware interrupts from keystrokes

text:
# Question
Title: Hardware interrupts from keystrokes
If there is an interrupt from every keypress (or one for keydown, one for keyup, one for keypress?) how does the OS handle so many interrupts at the same time. A person typing at 120WPM would be sending more than 500 interrupts per minute. How does a process ever finish if there is a context switch for the CPU to handle the interrupt 500 times per minute.

I must be missing something here?

# Answer
A modern computer is designed to handle many more interrupts than you could possibly generate with your keyboard.

> You should expect interrupts to range upward from 1,000 per second for computers running Windows 2000 Server

See this link.
> 2 votes

---
Tags: operating-systems
---


# Question
Title: What does it mean to say that there doesn't exist an algorithm from a TM point of view?
> A TM for a recursive language corresponds to our informal notion of an algorithm.

as per Automata Theory, Languages and Computation by Ullman et al. Then there are languages called RE and $L\_d$, where there exist TM that halts for accepting strings in the case of RE languages.

This means that we cannot construct a algorithm for RE languages that are not recursive? Then what is the significance of these RE languages from an algorithm point of view.

What confuses me is that for RE language you can construct a TM. So you can construct an algorithm?

# Answer
> 5 votes
First, note that it is easy to write algorithms that not always halt:

```
algo(n) {
  while ( n % 2 != 0 ) {
    n += 2
  }
  return n
}

```

It seems that you are asking for a semi-decidable problem of practical relevance. Consider verification of hard- and software. Many interesting properties require logics of higher order for their formulation, and usually satisfiability and/or validity of such formulae is undecidable.

But these logics have proof system, sets of axioms and rules that make up every proof for valid formulae¹. Along these systems, all proofs can be (recursively) enumerated: thus, we can semi-decide many important properties. Using clever heuristics, lots of computational power and human intervention, e.g. by providing key lemmata, many problems can be solved in practice (i.e. for some useful instances) that are theoretically undecidable.

---

1. Beware incomplete proof systems.

# Answer
> 3 votes
Yes. RE is the set of languages which you can construct an accepting TM for. Recursive languages are those where you can construct a TM that always halts. There are some functions which we can build TMs to accept, but those machines always have infinite time complexity. Also note, that the diagonal language Ld is Not in RE. It is a problem outside RE.

# Answer
> 0 votes
the word "algorithm" is very old, about a *millenium* old, dating to the beginning of the 2nd millenium ie the year ~1000s & also has a similar etymology to the word "algebra". it was originally based on algebra techniques or problems of integer arithmetic such as multiplication or division.

TMs were invented in 1936 by Turing. the best way to understand it is that computer science has formally defined "algorithm" to refer to recursive languages that always halt on all inputs. RE languages can be modelled by TMs which dont halt on some inputs but are not technically "algorithms" for this reason. so yes if you have an idea that TMs in general somehow model "algorithms", that will be confusing and basically incorrect.

---
Tags: computability, turing-machines, undecidability
---