title: Is this a regular grammar?

text:
# Question
Title: Is this a regular grammar?
I went through a question asking me to categorize the following grammar.

$$S → AA, S → AB, A → a, A→BB, B → b, B → e$$

From the production rules, clearly it is Context-Free. But it accepts a finite set of strings. $\\{e, a, aa, ab, abb, ba, bba, b, bb, bbb, bbbb\\}$ which is regular language.

So, is the above grammar regular? Though it does not follow from the rules.

Basically my question is: **Is the grammar $\\{S → AA, A → a\\}$ regular?.**

# Answer
The answer is no. Whilst the **language** is finite and therefore regular the **grammar** itself is not regular. I think you already knew this as you said that this grammar's production rules are not of the form of a regular grammar.

The point here is that just because a grammar isn't regular doesn't mean the language it generates must not be regular.
> 4 votes

# Answer
This a type-2 grammar (CFG) not type-3 (regular garmmar), because it consists of both left hand derivation and right hand derivation. There are CFGs which generate regular languages. That's a property.
> 0 votes

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


# Question
Title: Is there an efficient method to store large DAGs?
I have a DAG representing strict partial order where each node is an assignment of variables $V$ to their values $v$. Each arc $(u,w)$ represents a change in one variable value such that $u\succ w$.

So if I have $n$ binary variables, I will end up with $2^n$ nodes which is exponential to the size of variables $n$. is there any method to store such DAG efficiently?

# Answer
Try constructing a reduced ordered binary decision diagram (ROBDD) as described here. The reducing algorithm removes redundant nodes, and reuses equal subtrees in the decision tree, such that every node is unique. The memory complexity of a ROBDD is $\mathcal O({2^n \over n})$ as proved here.
> 2 votes

---
Tags: algorithms, graphs, data-structures, partial-order
---


# Question
Title: Recursive function calculating number of ways to sum $a + 2 b + 3 c = x$
Using python need to code a recursive function with one input and no global integers that calculates the number of options to get $x$ using $a\*1+b\*2+c\*3$.

Say $x=3$, there are four options: $\lbrace (1,1,1),(1,2),(2,1),(3)\rbrace$.

# Answer
Recursion is a pretty bad choice here, but here is the recursion you could use: $$ f(n) = \begin{cases} 0, & n \< 0, \\ 1, & n = 0, \\ f(n-1) + f(n-2) + f(n-3), & n \> 0.\end{cases} $$ For example, $$ \begin{align\*} f(-2) &= 0, \\ f(-1) &= 0, \\ f(0) &= 1, \\ f(1) &= f(0) + f(-1) + f(-2) = 1, \\ f(2) &= f(1) + f(0) + f(-1) = 2, \\ f(3) &= f(2) + f(1) + f(0) = 4. \end{align\*} $$ The dynamic programming approach implied by this example is a much better idea; it can be implemented in constant space and linear time, whereas the recursion will take linear space and exponential time. You could also use matrix powering to compute $f$: $$ f(n) = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}^n \begin{bmatrix} 1 \\ 1 \\ 2 \end{bmatrix}. $$ The generating function is $$ \sum\_{n=0}^\infty f(n) x^n = \frac{1}{1-x-x^2-x^3}. $$ Finally, you can also find an explicit solution: $$ \begin{align\*} f(n) &= \mathrm{round}(Cx^n), \\ C &= \frac{1}{3} + \frac{\sqrt\[3\]{847+33\sqrt{33}}}{66} + \frac{4}{3\sqrt\[3\]{847+33\sqrt{33}}}, \\ x &= \frac{1 + \sqrt\[3\]{19-3\sqrt{33}} + \sqrt\[3\]{19+3\sqrt{33}}}{3}. \end{align\*} $$ This explicit solution isn't very helpful since you need a lot of precision, but it does give you the correct asymptotics; note $C \approx 0.6184199223$ and $x \approx 1.839286756$.
> 4 votes

# Answer
```
def f(n):
    """Compute the numbers of ways in which non-negative n can be expressed
    as a sum of 0s, 1s, and 2s."""
    (u, v, w) = (0, 0, 1)
    while n > 0:
        (u, v, w) = (v, w, u + v + w)
        n = n - 1
    return w

```
> 1 votes

# Answer
```
def f(n):
    if n < 0:
        return 0
    elif n == 0:
        return 1
    else:
        return f(n-1) + f(n-2) + f(n-3)

```
> 0 votes

---
Tags: combinatorics, recursion
---


# Question
Title: Is this data structure a hypertree or they are just isomorphic trees?
I have a data structure described as following:

```
- It's a collection of trees.
- Each tree has the same structure.
- Each tree has information of diferent nature.

```

A example of this data structure:

```
    4 - - - - - - - 'a' - - - - - - - 3.5
   / \              / \               / \
  3   1           'f' 'y'           1.0 3.1
     / \              / \               / \
    4   7           'e' 'f'           2.3 7.7

```

If you see, ignoring the contents of each tree, each of them is just the same tree (the same hierarchy, the same structure). The first contains natural numbers, the second one, characters, and the third one, floating numbers.

The idea of this data structure is that diferent classes (in a C++ program for example) explore diferent "layers" of this tree, in order to each class uses only the information this class needs, ignoring the remaining information. In other words, each class sees only one tree.

Does this data structure match with a hypertree or can it be reformulated/adapted to a hypertree? Or just they are isomorphic trees put together is a same data structure?

# Answer
You can describe what's going on here with the notion of a functor, extending things which you would do naturally with three different types (ints, chars, and floats) to trees over these types.

What you have is in effect only a single tree, *e.g.* $$ T = \left\\{\mspace{45mu}\begin{array}{c@{}c@{}c} & (4,a\mspace{-18mu}&,3.5) \\ &/&\backslash \\ &\mspace{-60mu}(3,f,1.0) & (1,y\mspace{-36mu}&,3.1) \\ & & /&\backslash \\ & &\mspace{-60mu}(4,e,2.3) & (7,f,7.7)\mspace{-60mu} \end{array}\mspace{50mu}\right\\} $$ and mappings from this tree over tuples, to the trees which are visible by the classes, $$ A = \left\\{\mspace{-10mu}\begin{array}{c} 4 \\ \\;/ \\;\\;\backslash & \\ \\;3 \quad 1 \\ \\;~ \quad\\; / \\;\\; \backslash \\ \\;~ \quad\\;4 \quad7 \end{array}\mspace{-10mu}\right\\}, \qquad B = \left\\{\mspace{-10mu}\begin{array}{c} a \\ \\;/ \\;\backslash & \\ \\,f \quad y \\ \\,~ \quad\\; / \\;\\; \backslash \\ \\,~ \quad\\;e \quad f \end{array}\mspace{-10mu}\right\\}, \qquad C = \left\\{\mspace{-20mu}\begin{array}{c} 3.5 \\ \\,/ \\;\\;\backslash & \\ \\;1.0 \quad 3.1 \\ \\;~ \quad\\;\\;\\;\\; / \\;\\; \backslash \\ \\;~ \quad\\;\\;\\;\\; 2.3 \quad 7.7 \end{array}\mspace{-10mu}\right\\}. $$ The mappings which carry $T \mapsto A$, $T \mapsto B$, and $T \mapsto C$ can be desribed in terms of the projectors $$\begin{align\*} \pi\_1 \\;\\;:\\;\\; \text{int} \times \text{char} \times \text{float} &\to\\;\\; \text{int} \\;, \\ \pi\_2 \\;\\;:\\;\\; \text{int} \times \text{char} \times \text{float} &\to\\;\\; \text{char} \\;, \\ \pi\_3 \\;\\;:\\;\\; \text{int} \times \text{char} \times \text{float} &\to\\;\\; \text{float} \\;. \end{align\*}$$ Each of these "projector" maps $\pi\_j$ can be extended to a mapping on trees, using the *tree functor* which carries all functions $f: A \to B$ to functions on trees, $\text{Tree}(f) : \text{Tree}(A) \to \text{Tree}(B)$ in the obvious way, preserving the tree structure for any given tree, and applying the function $f$ to each node in the tree. Thus $$\begin{align\*} A &= \Bigl\[\text{Tree}(\pi\_1)\Bigr\](T), \\ B &= \Bigl\[\text{Tree}(\pi\_2)\Bigr\](T), \\ C &= \Bigl\[\text{Tree}(\pi\_3)\Bigr\](T). \end{align\*}$$ So these trees are just the images of $T$ under projection maps in the natural way; they aren't meaningfully independent of one another, and what the classes do which can only access one of these trees is that they can only access information about $T$ through these projections.
> 6 votes

---
Tags: data-structures, trees
---


title: Summation of $O(n)$ from $1\le k\le n$

text:
# Question
Title: Summation of $O(n)$ from $1\le k\le n$
Summation of $O(n)$ from $1\le k\le n$.

I think it should be $O(n)$ only. Because we are addition $O(k)$ and maximum order will be $O(n)$. But answer is given as $O(n^2)$.

Correct me if I'm wrong.

# Answer
I think I understood you from your comments above. I think you have issues in the very basics of complexity analysis.

I think what you want to say is that you are summing the term $O(n)$, $O(k)$ times for $1 \leq k \leq n$ . right? In this case, the answer is $O(nk)$.

If $O(k) \in O(n)$ (for example $k = n/c$ for $c \in O(1)$) then, then the answer is $O(n^2)$. is that what you want ?

**Comment** I see from the comments $k = 3$. Therefore, I can understand $k$ is constant and $O(k) \in O(1)$. Therefore $O(kn) \in O(n)$. This is why you get $O(n)$, while you are confused with $O(n^2)$. But for instance, if k = n * (some weird constants) = 3, then badly your solution is $O(n^2)$.

**Example**: Assume that your program requires $k$ functions, each of with requires $O(1)$ (that is, no matter what size of input you got (i.e. $n$) it will always take $O(1)$ time units to run a function). In this case, your total is $O(k)$. The number of functions in your program also does not depend on the number of $n$. It is also constant (that is, $O(1)$). Therefore, the total running time of your program is $O(1)$ !

If the functions above required $O(n)$ execution time complexity, then similarly it is $O(n)$.. This is all because $k$ is constant. Even if $k = 10^6$ and your input was of size $n = 100$. The same bound remains. Why ? because one day, you will run an input of size $n = 10^{1000}$, but $k$ remains to be $10^6$.

**One example commonly found**. Assume we have a graph $G = (V, E)$ constructed in a way such that each vertex $v$ is connected to $d$ other vertices. In this case $0 \leq d \leq n - 1$. Therefore, the number of edges of the graph $|E| = (\sum \_{v \in V} d) / 2 = nd /2$. If $d$ is fixed (let's say to exactly 4), then $|E| \in O(n)$.

However, assume that $d$ is a function of $n$. For instance, a vertex $v$ select $1/2$ of the other vertices as neighbors. Therefore, $d = \frac{1}{2}(n-1)$. In this case $|E| = nd/2 = n (\frac{1}{2}(n-1)) \in O(n^2)$.

In the first case (i.e. $|E| \in O(n)$), the graph is *sparse*. In the other case, the graph is *dense*.
> 3 votes

# Answer
Suppose $T\_n = O(n)$. That means that for some constant $C$, $T\_n \leq Cn$. Therefore $$ \sum\_{m=1}^n T\_m \leq C \sum\_{m=1}^n m = \frac{C}{2} m(m+1) = O(m^2). $$ If also $T\_n = \Omega(n)$ then you can show in exactly the same way that the sum is $\Omega(n^2)$, so that no better bound is possible (for concreteness, you can take $T\_n = n$).
> 3 votes

# Answer
There's no correct answer unless you specify what the $n$ functions are.

For example, consider, for each $k$, the function $f\_k(n) = kn$. For any fixed $k$, $f\_k(n) \in O(n)$.

Yet $\sum\_{k=1}^{n} f\_k(n) = \sum\_{k=1}^n kn = n\frac{n(n+1)}{2} \in O(n^3)$. A different choice of sequence $f\_k$ could yield just about any function in $\Omega(n)$.

So we can take a sequence of $k$ functions, each of which is $O(n)$, and sum them to get a function that's $O(n^3)$ (for instance).

If you have a single fixed function $f(n) \in O(n)$, then of course $\sum\_{k=1}^n f(n) = nf(n) \in O(n^2)$.
> 2 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Proving regularity via equivalence classes
Given two regular languages $L\_1$ and $L\_2$, we define a new language

$$L=\\{w\_1w\_2\mid \text{ there exist two words } x,y \text{ such that } xw\_1\in L\_1, w\_2y\in L2\\}$$

How do I show that $L$ is regular with equivalence classes?

My assignment allows the use of closure properties that all regular languages hold, but I cannot use $\text{rank} (L)$, as in show a limit to the number of equivalence class.

Can someone lead me in the right direction?

# Answer
If you are allowed to use closure properties (as the formulation in the question suggests) then $xw\_1\in L\_1$ so $w\_1$ is a suffix of $L\_1$, similarly $w\_2$ is a prefix of $L\_2$. Taking suffixes and prefixes is a closure property of regular languages, and so is concatenation. That solves the regularity.

At what level do you want/need equivalence classes for your answer?

(**added**) For language $K$ its set of prefixes is defined as $$\mbox{pref}(K) = \\{ w \mid \mbox{there exists string $y$ such that } wy\in K \\}$$ precisely as used for $L\_2$ in the operation in the question.

Given a finite state automaton for $K$ we get a FSA for $\mbox{pref}(K)$ by making all states final that have a path leading to a final state.

Also $\mbox{suff}(K) = \\{ w \mid \mbox{there exists string $x$ such that } xw\in K \\}$. Similarly one proves closure under suffix by making all states initial. As that is not commonly allowed for FSA that is solved by adding $\varepsilon$-transitions to all other states.

Your language $L$ based on $L\_1,L\_2$ equals $\mbox{suff}(L\_1)\mbox{pref}(L\_2)$, the concatenation of a suffix and a prefix language.

I could not find a reference to a question in this forum that dealt with the prefix/suffix operations, perhaps someone can help. Closure under prefix is a special case of closure under quotient.
> 4 votes

# Answer
L = {w1w2| there are two words, x,y such that : xw1 is in L1, w2y is in L2} is regular if L1 and L2 are regular languages.

> Lsuff = { w1 | xw1 ∈ L1 }
> Lpref = { w2 | w2y ∈ L2 }

**And,**

> L = LsuffLpref

We can easily proof by construction Finite Automata for `L`.

Suppose Finite Automata(FA) for L1 is M1 and FA for L2 is M2.

**\[SOLUTION\]**
Non-Deterministic Finite Automata(NFA) for L can be drawn by introducing NULL-transition (^-edge) form every state in M1 to every state in M2. then NFA can be converted into DFA.

e.g.
L1 = {ab ,ac} and L2 = {12, 13}

> L = {ab, ac, 12, 13, a12, a2, ab12, ab2, a13, a3, ab13, ab3, ............}
> **Note:** w1 and w2 can be NULL

M1 =is consist of Q = {q0,q1,qf} with edges:

q0 ---a-----\>q1,
q1 ---b/c---\>qf

Similarly :

M2 =is consist of Q = {p0,p1,pf} with edges:

p0 ---1-----\>p1,
p1 ---2/3---\>pf

Now, NFA for L called M will be consist of Q = {q0,q1,qf, p0,p1,pf} Where Final state of M is pf and edges are:

q0 ---a-----\>q1,
q1 ---b/c---\>qf,
p0 ---1-----\>p1,
p1 ---2/3---\>pf,

q0 ----^----\> p0,
q1 ----^----\> p0,
qf ----^----\> p0,

q0 ----^----\> p1,
q1 ----^----\> p1,
qf ----^----\> p1,

q0 ----^----\> pf,
q1 ----^----\> pf,
qf ----^----\> pf

^ means NULL-Transition.

Now, A NFA can easily convert into DFA.(I leave it for you)

**\[ANSWER\]**
DFA for L is possible hence L is Regular Language.

---

I will highly encourage you to draw DFA/NFA figures, then concept will be clear.
> 2 votes

---
Tags: automata, regular-languages, finite-automata, proof-techniques
---


# Question
Title: Intuitive meaning of modal $\mu$-calculus formula
I am solving one of the past exams and I am not certain with my solution to one of the exercises. The exercise is asking to give intuitive meaning to modal $\mu$-calculus formula:

$$ \phi = \mu Z. \langle - \rangle tt \wedge \[-a\]Z $$

According to an article *Modal logics and mu-calculi: an introduction* by Bradfield and Stirling\[1\] the intuition behind $\mu$ operator is "*finite looping*". So my reasoning is following: on every path through states in $Z$ there must be only a finite number of transitions with labels different from $a$ and then we must reach a state which is both non-terminal (from the first condition) and all transitions from it are labelled $a$ (from finiteness).

Hence on every path through states in $Z$ there must eventually be a transition labelled $a$. (similar to CTL formula $\forall F(a)$).

Is my reasoning correct? I am unable to find any formal reason for my solution to be right, can you give me a little hint?

\[1\] http://homepages.inf.ed.ac.uk/jcb/Research/bradfield-stirling-HPA-mu-intro.ps.gz

# Answer
> 4 votes
Let's break it down.

First, let's look at $\[-a\]\phi$. This means every non-$a$ transition leads to a state where $\phi$ holds. It follows then that $\[-a\]\mathrm{ff}$ holds for states that have no non-$a$ transitions, which we will use when looking at the least fixed point semantics.

$\langle-\rangle\mathrm{tt}$ is pretty simple. It holds in any state that has any transition, i.e. is not deadlocked.

So together $\langle-\rangle\mathrm{tt} \land \[-a\]\phi$ means the state can take a transition and $\phi$ holds after every non-$a$ transition.

One way to view the meaning of $\mu Z.\phi(Z)$ is by the approximants referenced in your linked tutorial. If the formula is satisfied in state $s$ then there is some $\beta$ such that $\bigvee\_{\alpha\<\beta} \phi^{(\alpha)}(\mathrm{ff})$ is satisfied in $s$. The notation $\phi^{(n)}(x)$ means $\phi$ iterated on $x$, $n$ times, i.e. $\underbrace{\phi(\phi(\dots\phi(x)))}\_{\text{$n$ times}}$. Let's look at some of these.

\begin{align} \phi^{(0)}(\mathrm{ff}) &= \mathrm{ff} \\ \phi^{(1)}(\mathrm{ff}) &= \langle-\rangle\mathrm{tt} \land \[-a\]\phi^{(0)}(\mathrm{ff}) \\ &= \langle-\rangle\mathrm{tt} \land \[-a\]\mathrm{ff} \\ \phi^{(2)}(\mathrm{ff}) &= \langle-\rangle\mathrm{tt} \land \[-a\]\phi^{(1)}(\mathrm{ff}) \\ &= \langle-\rangle\mathrm{tt} \land \[-a\](\langle-\rangle\mathrm{tt} \land \[-a\]\mathrm{ff}) \\ \phi^{(3)}(\mathrm{ff}) &= \langle-\rangle\mathrm{tt} \land \[-a\]\phi^{(2)}(\mathrm{ff}) \\ &= \langle-\rangle\mathrm{tt} \land \[-a\](\langle-\rangle\mathrm{tt} \land \[-a\](\langle-\rangle\mathrm{tt} \land \[-a\]\mathrm{ff})) \end{align}

Hopefully it is clear that these have the meanings

1. $\phi^{(1)}(\mathrm{ff})$: States that can take only $a$ transitions
2. $\phi^{(2)}(\mathrm{ff})$: Live states that
    1. have only $a$ transitions; or
    2. all length 1 non-$a$ paths lead to a live state with only $a$ transitions
3. $\phi^{(3)}(\mathrm{ff})$: Live states that
    1. have only $a$ transitions; or
    2. all length 1 non-$a$ paths lead to a live state with only $a$ transitions; or
    3. all length 2 non-$a$ paths lead to a live state with only $a$ transitions

If that is unclear, remember that $\[-a\]\phi$ is trivially satisfied for states with no non-$a$ transitions.

Now you should see that $\phi^{(n)}(\mathrm{ff})$ is true if and only if the state can take at most $n-1$ non-$a$ transitions before reaching a live state with only $a$ transitions. It turns out that $\phi^{(n)}(\mathrm{ff}) \implies \phi^{(n+1)}(\mathrm{ff})$ so we don't need to take the disjunction with lesser approximants and can simply say $\mu Z. \langle-\rangle\mathrm{tt} \land \[-a\]Z \iff \exists \beta \in \mathbb{N}. \phi^{(\beta)}(\mathrm{ff})$, or in english, after a finite number of non-$a$ transitions we reach a live state with only $a$ transitions.

---
Tags: modal-logic, mu-calculus
---


# Question
Title: How to recognize a STRIPS planning problem has no solution?
> Strips –Stands for STanford Research Institute Problem Solver (1971).

**STRIPS Pseudo code -**

```
STRIPS(stateListstart, stateListgoals)
1.Set state = start
2.Set plan = []
3.Set stack = goals
4.while stack is not empty do
     1.STRIPS-Step()
5.Return plan

STRIPS-Step()
switch top of stack t:
1.case this a goal that matches state:
    1.pop stack
2.case this an unsatisfied conjunctive-goal:
    1.select an ordering for the sub-goals
    2.push the sub-goals into stack
3.case this a simple unsatisfied goal
    1.choose an operator op whose add-list matches t
    2.replace the twith op
    3.push preconditions of op to stack
4.case this an operator
    1.pop stack
    2.state = state + t.add-list -t.delete-list
    3.plan = [plan | t]

```

Some explanations -

`state` \- is a list of predicates.

`stack` \- is a stack which includes both predicates or operations.

`[plan | t]` \- add the opreration `t` to list `plan`.

If the `stack` gets empty, it means that `plan` holds the solution plan.

Since the algorithm is running `while stack is not empty do`, how can I recognize that there is no solution (i.e `plan`) which led to the *goal state* ?

Those who are not familiar with this algorithm, you can see its running example here. Brief introduction: imagine a crane which picks boxes and put them each other , so `operation` can be `put box A on box B` and `state` can be `box A is on box B` .

# Answer
> 5 votes
Realize that STRIPS solves *linear* planning problems. By this I mean those planning tasks where the order in which the goals are satisfied is not relevant and these are, in practice, easier to solve than the *non-linear* planning problems ---be aware, however, that STRIPS is PSPACE-complete anyway and it is necessary to restrict it quite a lot to prove it to be NP-complete (though whether both classes are equal is still unknown but, ... may I say unlikely?)

*Non-linearity* is quite intriguing. It does not only mean that a particular planning task with, say, 3 goals $G=\\{g\_1, g\_2, g\_3\\}$ can only be satisified in a particular ordering (such as: first $g\_2$, then $g\_1$ and finally $g\_3$). It might also imply that while some goals are achieved simultaneously, others have to be satisified in a particular order. A good discussion on the subject can be found in *Korf, Richard E. Planning as Search: A Quantitative Approach. Artificial Intelligence 33, pp. 65--88. 1987*

From your pseudocode, realize that STRIPS commits to a particular order in line 2.1 of STRIPS-step and it never tries any other one. In fact, the ordering selected for the goals is strict after step 2.2. Thus, STRIPS explores the whole state space engendered by the definition of the planning task **for a particular ordering of the subgoals** If this ordering has not been properly chosen, then the problem is unsolvable for STRIPS.

In the end, all that STRIPS can say is that a problem is unsolvable for a particular ordering but not whether the planning task is solvable or not. Although it is not shown in your pseudocode, recall that STRIPS can discard a particular operator if its preconditions introduce goals that were considered before ---i.e., it avoids circular reasonings. And, in the end, it will have no available operator if the problem is unsolvable for the selected ordering.

PRODIGY was an attempt to solve this problem by explicitly enumerating all the different orderings of the subgoals which, however, might become very easily an unmanageable number. FF, *Hoffmann, Joerg, Nebel, Bernhard. The FF Planning System: Fast Plan Generation Through Heuristic Search. Journal of Artificial Intelligence Research 14, pp. 253--302. 2001*, however, can detect that some planning tasks are unsolvable even if they are *non-linear* planning tasks just by verifying that the relaxed graphplan cannot achieve them. Nevertheless, this procedure is sound but incomplete ---i.e., some unsolvable planning tasks can seem solvable fooling FF.

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


# Question
Title: What is the purpose of Mark field in Fibonacci Heaps?
In Fibonacci heaps, we keep a mark field for every node in the heap. Initially all the nodes are unmarked. Once a node is deleted, its parent is marked. If a node is deleted and its parent is already marked, the parent will be cut and inserted into the root list. I just wonder what the purpose of marking is? What happens if we cut the parent just the first time without marking it? Does it change the time complexity of the operations? How?

# Answer
> 12 votes
It does change the complexity of the operations. Simply speaking, the root list $W$ gets too large.

We have two *expensive* operations, which are **ExtractMin** and **DecreaseKey**. Remember that the amortized analysis uses the potential function $$ \Phi(F)=|W| +2\cdot \text{# marks}. $$ If we call **ExtractMin** this might cost $O(\left|W\right|)$, however after the operation, the root list has only size $O(\log n)$, and we have charged most of the costs to the potential. The question now is how to charge-up the potential. Here come the **DecreaseKey** operations into play. They are responsible for a large root list $W$. Say, we add $k$ trees to the root list $W$ during the **DecreaseKey** operation. This means that we remove $k-1$ marks, and we pay with the marks the costs of **DecreaseKey** and the change of the potential function (that is why we have a factor 2 for the marks in $\Phi$).

So what happens if we immediately put a vertex into the root list when decreasing the key. Then of course the root list might get large. But this is not the problem. The problem is, that you cannot show that after the repair-part of **ExtractMin** $W$ has at most $O(\log n)$ elements. If I am not mistaken the size of $W$ can then contain up to $\Omega(\sqrt{n})$ elements. That means that if we delete directly the **DecreaseKey** operations are in $O(1)$ and their worst-case running time is even better than for Fibonacci heaps, but the **ExtractMin** is $O(\sqrt{n})$.

Another softer perspective is the following: The marks guarantee that you only delete one child for every node. Without deletion every tree in a Fibonacci heap is a binomial tree. The marks ensure that we do not diverse from the binomial tree structure too much.

---
Tags: data-structures, heaps, amortized-analysis
---


title: Power of Double - Logarithmic Space

text:
# Question
Title: Power of Double - Logarithmic Space
I try to solve exercise "on the power of double - logarithmic space" from the great textbook Computational Complexity by Oded Goldreich. The goal is to show that the given set $S=\left \\{ w\_k \mid k \in \mathbb{N} \right \\}$, where $w\_k$ - concatenation of all $k$-bit long strings separated by \*'s is not regular and yet it is decidable in double-logarithmic space. The exercise contains guidelines, and I would like to shed the light on few sentences from guidelines in order to solve the exercise.

In the guidelines it's mentioned that

> we can take advantage of of the \*'s (in $w\_i$) , the $i$th iteration can be implemented in space $O(\log i)$

The $i$th iteration is verifying whether $x = w\_i$, which is really can be decided in $O(\log i)$ space, where $\log i$ can be used to note the position in $i$ long string, but the position in $x$ can be included in $O(\log i)$ or not?

> Furthermore, on input $x \notin S$, we halt and reject after at most $\log |x|$ iterations.

It means only $\log |x|$ $w$'s from the set S will be compared to $x$. Why it is actually so?

> Actually, it is slightly simpler to handle the related set $\left \\{w\_1\**w\_2\**..\**w\_k \right \\}$

Why it is actually so, and I would call it set, it is rather concatenated string.

# Answer
Well, the set $\left \\{w\_1\**w\_2\**..\**w\_k \right \\}$ contains only one single element, but is nevertheless a set. And TM can accept only languages, which are sets of words.

Why is it slightly easier? Hmm, I would say, it is easier since you can simplify the algorithm **slightly**. You have one counter for $k$, and then you check, whether in the string $\cdots \*x\*y\*\cdots$, you have $\text{bin}(y)=\text{bin}(x)+1$ on every position. You do not have to care about detecting the right $k$. Other than this, the suoer-string is longer, which gives you more space. But this effect vanishes in the big-O.
> 2 votes

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


# Question
Title: Looking for some more details on "Turing" devices
I've been reading a lot of computer science literature in the recent past but haven't ran across an explanation of Turing machines, the different types, and why they seem to come up so often (I understand they are a sort of a basis for CS topics).

I've also seen comments by some members mentioning turing-completeness (Particularly when dealing with programming languages) and was just looking for some clarification.

I did search around before posting this and haven't been able to find a similar post or a website that describes this in terms that I have been able to understand or decipher. Thanks.

# Answer
> 1 votes
A Turing machine is named after British mathematician Alan Turing; he first described them in his paper "On computable numbers, with an application to the Entscheidungsproblem". It serves as the mathematical basis of computation and allowed various notions of computability to be mathematically proven even before physical computers existed.

Using Turing machines we can reason about what algorithms are fundamentally unsolvable, which ones are solvable in a reasonable amount of time, and which ones are solvable but take an unreasonable amount of time. Here, "reasonable" means the algorithm goes through a number of steps which is polynomial in the length of the input. For example, being able to prove mathematically that it is very hard to calculate the two prime factors of a large composite number is the underpinning of the security of the internet, the RSA algorithm.

The basic Turing machine consists of a 'tape' divided into 'cells', where each cell contains either a symbol or a blank; and a read/write head which can read symbols from the tape, write symbols onto the tape and move left or right along the tape. The action of the head is given by a transition function, which basically has a bunch of rules like "if you are in state q1 and you read an X, replace the X with a Y, move the head one cell right, and change to state q2".

The Church-Turing thesis is what makes Turing machines useful: simply put, states that a function is algorithmically computable if and only if there is a Turing machine which can compute it.

A language is Turing complete if and only if it can be used to simulate any single-taped Turing machine. Due to the Church-Turing thesis, this means it can be used to compute any algorithmically-solvable function.

As an interesting aside, a machine with only the instruction "subtract and branch if less than or equal" (see one instruction set computer) is actually Turing complete: it has conditional branching and the ability to change arbitrary memory locations, which is all that is required.

I recommend Sipser's "Introduction to the Theory of Computation" for a grounding in this stuff.

# Answer
> 3 votes
A Turing machine is a simple theoretical/conceptual computational device based on state. Computation is done through state transitions based on the machines current state. It is popular in Computer Science theory due to how models and proofs can be built off of it. Wikipedia has a far more detailed write up on Turing machines than is practical to put here and a general discussion of Turing machines is probably off topic for IT Security. Computer Science is probably a good place to ask more about Turing machines in general, since they are a fundamental conceptual device for Computer Science theory.

In case you are a visual-learner, interestingly enough, there exist physical incarnations of the abstract device.

# Answer
> 0 votes
> The "Turing" machine was described in 1936 by Alan Turing\[1\] who called it an "a-machine" (automatic machine). The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation. from Wikipedia.

This was hard for me to understand as well, since that is something as they described `hypothetical device` just to let computer scientists understand how the CUP process the instructions.

I think this is a very nice article to read : http://en.wikipedia.org/wiki/Turing\_machine

---
Tags: terminology, turing-machines, computation-models, turing-completeness
---


# Question
Title: Single machine job scheduling to minimize weighted sum of completion time
Given $n$ jobs, schedule them such that the weighted sum is minimum.

weighted minimum sum S for the schedule $\sigma = \\{ J\_1, J\_2, ... J\_n \\}$ is given by :

$S = \sum\_{1\leqq i \leqq n} w\_i C\_i$ where $C\_i\ = \sum\_{1\leqq j \leqq i} t\_j$ and $w\_i$ is the weight of job $J\_i$, $t\_i$ is the time $J\_i$ takes to complete.

I think the solution is to schedule the jobs in shortest weighted processing time i.e. to arrange them in the increasing order of $ t\_i/w\_i $.

But how to prove this.

# Answer
> 4 votes
Hint: Let $\sigma$ be the optimal schedule. Suppose that jobs $k$ and $k+1$ are switched. How is the cost affected? What does the optimality of $\sigma$ tell us about $w\_k,w\_{k+1},t\_k,t\_{k+1}$?

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


# Question
Title: Data structures for general (non-tetrahedral) cell complexes
For 2D polygonal meshes, the QuadEdge and HalfEdge data structure representations are sufficient to store and enable efficient query of all topological and incidence information. Are there compact and efficient data structures for 3D polyhedral meshes? I know there has been some recent work on compact representations for tetrahedral meshes, like, for example SOT. I don't know enough about these to know if they generalize to unstructured non-tetrahedral meshes.

I can imagine that half-edges might generalize to half-faces with associated half-edges, but it seems like that is a lot of data to store, and there might be more compact representations. I should add that I really only care about retrieving facet information (like which facets are on the boundary, which facets belong to a certain cell); the edge incidence information is not as useful.

# Answer
> 8 votes
There is an extension of half-edge in any dimension, called *darts* in combinatorial maps. There are two packages in CGAL allowing to use these combinatorial maps in any dimension (see here for combinatorialMaps and here for LinearCellComplex).

You can use this data structure to represent any *Quasi manifold* orientable subdivided 3D object. Quoting from CGAL webpage(section 2.4 Combinatorial Map Properties):

A quasi-manifold object is defined as:

> A dD quasi-manifold is an object obtained by taking some isolated d-cells, and allowing to glue d-cells along (d-1)-cells.

and orientable as:

> It is orientable if it is possible to embed it in the Euclidean space and to define a global "left" and "right" direction in each point of the embedded object.

---
Tags: data-structures, computational-geometry
---


title: Number of digits in a binary product

text:
# Question
Title: Number of digits in a binary product
Assume i have 2 numbers in binary form (or, more precisely, assume to know the number of their digits, DF1, DF2):

101010101001010101010101010111111111111111111111010101 10101111111111111111010101

Is there a formula for the exact number of binary digits (DP) of the product?

```
  DP = F (DF1, DF2)

```

\[I need this, in a practical case, to size a target array\]

# Answer
> 5 votes
I assume you want to know the *maximum* possible bits that a product of two numbers might have. Under that assumption, let the first number $a$ have $m$ bits, and the second number $b$ have $n$ bits.

Then, $$a \leq 2^{m} - 1 $$ Similarly, $$b \leq 2^{n} - 1$$

Then, the product is: $$a \cdot b \leq 2^{m+n} - 2^m - 2^n + 1$$ Now, both $2^m$ and $2^n$ are greater than $1$ (since $n, m \> 0$). So, $$a \cdot b \< 2^{m+n} - 1$$

Therefore, **at most** $m+n$ bits are sufficient for the product of the two numbers. Of course, lesser bits might suffice. Also, the sign bit is not included in the computation, and each of $a$, $b$, and $a \cdot b$ might have a separate sign bit.

If you really need to optimize on space, you can check $a$ and $b$ for special cases. Some cases could be:

* $a$ or $b$ is $0$: You need 1 bit
* $a$ or $b$ is $1$: You need as many bits as the other number
* One of the numbers is a power of $2$: It will contain exactly one $1$, say at position $i$ (LSB is position 0). Then, the multiplication is equivalent to left shifting the other number by $i$ bits.

You might think up other special cases if you *really* need to.

**Edit:** As pointed out by Sam in the comments, if you impose the restriction that the most significant bit has to be 1 (unless the number itself is 0), you can get a lower bound too. Since the MSB is 1, we have: $$a \geq 2^{m-1}$$ and $$b \geq 2^{n-1}$$. Thus, $$a \cdot b \geq 2^{m + n - 2} = 2^{(m+n-1) - 1}$$

To represent $2^{(m+n-1)-1}$, you require $m+n-1$ bits, and so to represent $a \cdot b$, you need **at least** $m+n-1$ bits. This leaves the special case when either of the numbers is $0$, and assumes there are no leading 0's in any of the numbers.

As a conclusion, if you know the number of binary digits/bits of your number (as you mention in your question), you are most likely implying that there are no leading $0$'s and the left-most bit is $1$ (exception being when the number itself is 0, where you can simply assign 1 bit for the resulting product). In such a scenario, the product will have either $m+n$ bits or $m+n-1$ bits.

# Answer
> 1 votes
Let $a.b = c$

$\log a + \log b = \log c$

Length of a number $n$ in base $b$ is $\lceil \log\_b (n + 1)\rceil$.

So $\lceil\log\_2 (a + 1) + \log\_2 (b + 1)\rceil$ bits should be enough.

---
Tags: factoring
---


# Question
Title: Is the intersection of two regular languages regular?
Trivially decidable problem is one in which the problem is a known property of the language/grammar. So **intersection of two regular languages is regular should be trivially decidable**? But it is given as not trivially decidable.

# Answer
> 5 votes
Summarizing the discussion, the intersection of two regular languages is always regular, and so "trivially decidable".

---
Tags: regular-languages, undecidability, decision-problem
---


# Question
Title: Why does the experience propagation rule for checkers work in Tom Mitchell's book?
In Tom Mitchell's book "Machine Learning", Chap.1, a checkers game is used to illustrate how machine learning can be applied solve problems.

An experience propagation rule is described for iterative learning of a hypothesis. Suppose a game has been played and watched by the program, the state of the endgame is labeled 100 for winning and -100 for losing. For each of the states on the path toward the endgame, we label it as $\hat{V}(Successor)$, where $\hat{V}(state)$ is the current model output on some state. Then the model is trained by adding the new label, and iteratively, the model converges to a good checkers program.

Why does this experience propagation rule work? It is mentioned in the book that it works quite well for most chess games.

# Answer
> 5 votes
Sutton's book on reinforcement learning explains it but probably in more detail than what you're looking for, so I'll try to explain it more briefly and clearly.

Start by thinking about the last position before the end of the game. The winning player can win in one move from that position, so that position is almost certainly good for that player and bad for the other player. Now Think about the second to last position: that's only one move away from the last position which we've just established is probably a good position for the player that won in the end. The same logic applies to the third-last, fourth-last, etc.

See also: Wikipedia's page on mathematical induction, which works in a similar way.

---
Tags: machine-learning
---


title: Characteristic path length

text:
# Question
Title: Characteristic path length
I am unable to understand that what the characteristic path length (CPL) of a graph is.

In one of its definitions, it is written that

> it is defined as the median of the means of the shortest path lengths connecting each vertex to all other vertices.

This is what I understand. Is it right?

Suppose we have 3 nodes A, B and C. A can reach to B and C through different paths. We consider just the two paths, AB and AC. These two are the shortest path lengths from which A can reach to B and C respectively. We will then take the mean of AB and AC. Similarly, we will calculate two more means for B and C like I calculated it for A. In the end, we will take the median of the 3 means.

Am I right?

# Answer
> 7 votes
To get the CPL by this definition you first take the average distance from a certain vertex to any other vertex: $$d\_v = {{\sum\_{v \ne w} d(v,w)} \over {|V(G)| - 1}}$$ After doing so for every vertex $v \in V(G)$, calculate the median of all previously calculated $d\_v$.

# Answer
> 3 votes
Let $d\_G(x,y)$ be the distance between the vertices $x,y \in V(G)$ for a connected graph $G.$ The characteristic path length is then defined as $$\frac{\sum\_{x,y \in V(G)} d\_G(x,y)}{n(n-1)} = \frac{\sum\_{v \in V(G)} \sum\_{u \in V(G) \setminus \\{v\\}} d\_G(x,y)} { {n \choose 2}}$$ where $n$ is the number of vertices in $G$ and the sum ranges among all pairs of vertices of $G.$

In more graph theoretical terms the characteristic path length is the Wiener index of $G$ dividied by $n(n-1).$

---
Tags: graphs
---


# Question
Title: How to show that given language is unambiguous
Given following grammar:

$$ \begin{align} S \rightarrow &A1B \\ A \rightarrow & 0A \mid \varepsilon \\ B \rightarrow & 0B \mid 1B \mid \varepsilon \\ \end{align} $$

How can I show that this grammar is unambiguous? I need to find a grammar for the same language that is ambiguous, and demonstrate it.

I know if I was asked to prove that the language is ambigious then I should find two different parse trees for same string, but I don't know what to do.

# Answer
> 4 votes
To show a grammar is unambiguous you have to argue that for each string in the language there is only one derivation tree.

In this particular case you can observe that $A$ only generates $0$'s, so the $1$ generated by the start symbol $S$ must be the first $1$ in the string.

Any grammar can be made ambiguous by adding chain productions like $S\to S$.

# Answer
> 1 votes
This grammar is equivalent with $$ \begin{align} S \rightarrow &0A1B\mid 1B \\ A \rightarrow & 0A \mid \varepsilon \\ B \rightarrow & 0B \mid 1B \mid \varepsilon \\ \end{align} $$ and so *like* a simple grammar we can show that this grammar is not ambiguous. Of course this grammar is not simple.

---
Tags: formal-languages, formal-grammars, context-free, proof-techniques, ambiguity
---


# Question
Title: Definitions of an algorithm running in polynomial time and in strongly polynomial time
Wikipedia defines it to be

> An algorithm is said to be of **polynomial time** if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., $T(n) = O(n^k)$ for some constant k.
>
> The algorithm runs in **strongly polynomial time** if \[8\]
>
> * the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
> * the space used by the algorithm is bounded by a polynomial in the size of the input.

In Bernhard Korte, Jens Vygen, Combinatorial Optimization:

> Definition 1.4.
>
> An algorithm with rational input is said to run in **polynomial time** if
>
> * there is an integer k such that it runs in $O(n^k)$ time, where n is the input size, and
> * all numbers in intermediate computations can be stored with $O(n^k)$ bits.
>
> An algorithm with arbitrary input is said to run in **strongly polynomial time** if
>
> * there is an integer k such that it runs in $O(n^k)$ time for any input consisting of n numbers and
> * it runs in polynomial time for rational input.

Please correct me if I am wrong. Following are the literal differences I noticed:

* For polynomial time algorithms, Korte and Vygen's definition is "the Wikipedia's definition + polynomial storage space".
* For strongly polynomial time algorithms, Korte and Vygen's definition and Wikipedia's definition both require polynomial time in the input storage size. But K and V's additionally requires polynomial time in the number of numbers in any input, while Wikipedia's additionally requires polynomial storage space in the input size.

So are K and V's and Wikipedia's definitions for these two concepts equivalent, respectively? What other differences and relations are between them?

Thanks and regards!

# Answer
Before formal definitions, consider what the "strongly/weakly" classification aims to distinguish.

First, consider running either one on a Turing Machine. Both will run in a number of steps polynomial in the length of binary-encoded input. Consequently, the number of arithmetic operations performed by both would have to be polynomial *in the length of binary-encoded input*. Hence, for both Turing Machine running time would grow polynomially as the number of input values or their magnitudes grows. To emphasize the latter, note that even the strong one will take more TM steps on larger magnitudes (it needs to at least read the extra bits). Under no circumstance does one become exponential (as is the case with the unrelated pseudo-polynomial time). With a Turing machine alone, a fundamental difference doesn't seem detectable.

Now consider running each on an arithmetic machine where any operation is an arithmetic operation on whole numbers and arithmetic operations are $O(1)$. As you increase the magnitudes of the input numbers, the length of the binary-encoded input grows, and the running time of the weak algorithm would grow, however the running time of the strong algorithm would not change, because can be bound by the number of input numbers, which you are not changing (e.g. matrix multiplication vs. Euclid's GCD).

The set of algorithms that run in number of arithmetic operations polynomial in the number of input numbers is well-defined, but overlaps with the class of algorithms that take number of TM steps exponential in the length of binary-encoded input (see examples). Hence, for this set, the properties in the second paragraph would not hold. To exclude the unwanted intersection, we add a condition for a polynomial TM space \[\*\].

In \[1\] this is stated in two ways:

* The algorithm runs in strongly polynomial time if the algorithm is a polynmomial space algorithm and performs a number of elementary arithmetic operations which is bounded by a polynomial in the number of input numbers.
* A polynomial algorithm is a polynomial space algorithm (in our standard Turing machine model) and polynomial time algorithm in the arithmetic model (see this question for a clarification).

This sub-classification of what are already "efficient" algorithms might be be useful since physical computers resemble arithmetic machines more than Turing machines, so the sub-class *might* identify the algorithm that would run faster on a physical machine if their polynomial bounds in length of binary-encoded input are otherwise comparable (which is not the case in e.g. strong $O(n^3)$ vs. weak $O(n^2)$)

\[\*\] The second condition is stated everywhere as polynomial space, whereas requiring polynomial time makes more sense to me. The former is more inclusive, but strange. Are there strongly-polynomial algorithms that take more than polynomial time? Note that repeated-squaring example takes neither polynomial time nor polynomial space.

\[1\] Grötschel, Martin; László Lovász, Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.
> 8 votes

---
Tags: complexity-theory
---


# Question
Title: Are there strongly-polynomial algorithms that take more than polynomial time?
In \[1\] *strongly-polynomial* is defined as either:

* The algorithm runs in strongly polynomial time if the algorithm is a polynmomial space algorithm and performs a number of elementary arithmetic operations which is bounded by a polynomial in the number of input numbers.
* A polynomial algorithm is a polynomial space algorithm (in our standard Turing machine model) and polynomial time algorithm in the arithmetic model (see this question for a clarification).

Why do they restrict to polynomial TM space as opposed to polynomial TM time? (this came up here)

It seems strange for an algorithm that takes a number of TM steps unboundable by a polynomial to still be considered strongly-polynomial (provided it takes polynomial space and a number of arithmetic operations polynomial in the number of numbers in the input). Can it be shown that such an algorithm does not exist? Perhaps based on this argument: the number of arithmetic operations would not be polynomial, since under the arithmetic model every operation is an arithmetic operation (?).

\[1\] Grötschel, Martin; László Lovász, Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.

# Answer
> 14 votes
No, any strongly-polynomial time algorithm can be converted into a polynomial time algorithm on a TM by replacing the arithmetic operations with equivalent algorithms in the TM model. That is the whole point of strongly-polynomial vs weakly-polynomial.

When you've analysed algorithms in the past, you've probably assumed that your arithmetic operations (addition, multiplication, etc.) take unit time. This is the arithmetic model of computation, where a step is defined as one arithmetic operation and input size is the number of integers. In the TM model, this isn't true, as a step is defined as moving the head and input size is defined as the number of bits used to represent the input. Thus arithmetic operations take time proportional to the number of bits used to represent them.

The definition restricts to TM space because that's the only condition you need to convert a polynomial time algorithm in the arithmetic model to a polynomial time algorithm in the TM model. The algorithm is already polynomial time in the arithmetic model, so as long as it's space is bounded in the TM model then the rest of the algorithm is still polynomial time in the TM model. Think of it like this, when converting from the arithmetic model to the TM model, the only thing that can go wrong is the space. The numbers you produce need to be representable in a number of bits that is polynomial in the number of bits in the input. So long as that holds, the rest of the algorithm is still polynomial time in the TM model.

In the case where you can't bound the space of your algorithm, you can't guarantee anything about the time when converting between the two models. There exist algorithms that take polynomial time in the arithmetic model but not in the TM model, and vice versa. Drawing examples from wikipedia let's elaborate on this.

**An algorithm that is polynomial in the arithmetic model but not the TM model** Suppose given the integer $2^n$ we wish to compute $2^{2^n}$ by repeated squaring. The integer $2^n$ takes space proportional to $n$ (i.e. the bits used to represent it). However $2^{2^n}$ takes space proportional to $2^n$, which is exponential in the size of the input. In the arithmetic model this algorithm is clearly polynomial since we perform $O(n)$ multiplications assuming each takes unit time which is polynomial in the input size. However the resulting value is exponential in the size of the input, so in the TM model this would take exponential time simply to write the bits necessary to store the result. Note that if we could bound the space of the algorithm, then we can guarantee that it is polynomial in the TM model as well.

**An algorithm that is polynomial in the TM model but not the arithmetic model** The standard GCD algorithm is one such example. Given two integers $a,b$ computing $gcd(a,b)$ takes $O((\log(a)+\log(b))^2)$ steps which is polynomial in the size of the input $\log(a)+\log(b)$. However in the arithmetic model the size of the input is just two integers and we can't bound the number of steps of the algorithm since it depends on the magnitude of $a$ and $b$.

Notice that the last example does not contradict the definition of strongly-polynomial. Strongly-polynomial doesn't say anything about algorithms that are polynomial in the TM model, it's only defined in the arithmetic model. If an algorithm is polynomial time in the arithmetic model and also happens to use space bounded in the size of input in the TM model, then it is strongly-polynomial.

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


# Question
Title: The stable marriage algorithm with asymmetric arrays
I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices.

For example if we have 10 students that should be assigned to 10 dorms, then I can build the preference and ranking matrix of this data. The question that I have is what to do in the case that I have, for example, only 5 students to assign and for example 10 dorms. Can I still apply the stable marriage algorithm?

Maybe this question is a little bit foolish, but as I said I only saw this algorithm applied to quadratic arrays.

# Answer
You can add $5$ dummy students, and put them low in the dorms' preference order. The resulting perfect matching $\pi$ will have the following two properties:

1. There is no student $s$ and dorm $d$ which are *not* matched such that $s$ prefers $d$ to $\pi(s)$ and $d$ prefers $s$ to $\pi(d)$.
2. There is no student $s$ and empty dorm $d$ such that $s$ prefers $d$ to $\pi(s)$.
> 7 votes

# Answer
Yes, the stable marriage problem still makes sense with unequal arrays. Permit me to use men and women as opposed to students and dorms. There are different stable matchings that you can ask for resulting in different cases.

* A specific stable matching is desired, either male optimal or female optimal solution
* Any valid stable matching is desired
* All the stable matchings are required

Let's consider the first case where we want a specific stable matching. Suppose there are $m$ men and $w$ women. Depending on which set is larger we modify the termination condition of the standard algorithm accordingly. Suppose without loss of generality we want the male optimal solution. If $m \< w$ we continue until $m$ women have been proposed to. If $m \> w$ then we continue until each man is either on the string of some women or has been rejected by all the women.

It's easy to see how the above algorithm can be applied to the second case where any such stable matching is required. Just have the smaller set be the one that proposes.

The third case depends on a theorem that states that if a person is unmarried in one stable matching then they are unmarried in every stable matching. The case then becomes identical to the case with equal sized sets.

More detail on all three cases as well as pseudo-code for each algorithm can be found in McVitie and Wilson's paper titled "Stable marriage assignment for unequal sets".
> 9 votes

---
Tags: algorithms, optimization, bipartite-matching, matching
---


# Question
Title: Find $\epsilon'$ s.t $L_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon<\epsilon'$
Let $L\_\epsilon$ be the language of all $2$-CNF formulas $\varphi$, such that at least $(\frac{1}{2}+\epsilon)$ of $\varphi$'s clauses can be satisfied.

I need to prove that there exists $\epsilon'$ s.t $L\_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon\<\epsilon'$.

We know that $\text{Max}2\text{Sat}$ can be approximate to $\frac{55}{56}$ precent of the clauses from a $\text{Max}3\text{Sat}$ reduction. How should I solve this one?

# Answer
> 8 votes
In his famous paper, Håstad shows that it is NP-hard to approximate MAX2SAT better than $21/22$. This likely means that is is NP-hard to distinguish instances which are $\leq \alpha$ satisfiable and instances which are $\geq (22/21) \alpha$ satisfiable, for some $\alpha \geq 1/2$. Now imagine padding an instance so that it becomes a $p$-fraction of a new instance, the rest of which is exactly $1/2$-satisfiable (say it consists of groups of clauses of the form $a \land \lnot a$). The numbers now become $1/2 + p (\alpha - 1/2)$ and $1/2 + p((22/21)\alpha - 1/2)$. The latter number can be made as close to $1/2$ as we want.

# Answer
> 5 votes
If you know that *ε* is a rational number, then you do not need inapproximability for Max-2-SAT to prove your statement. A typical proof of the NP-hardness of Max-2-SAT (e.g., the one in the textbook *Computational Complexity* by Papadimitriou) actually proves the NP-completeness of *L*1/5. To prove the NP-hardness of *L**ε* for positive rational numbers *ε*\<1/5, we can reduce *L*1/5 to *L**ε* as follows: given a 2CNF formula *φ* (an instance for *L*1/5), let *m* be the number of clauses in it. Let *r* and *s* be positive integers such that (1/5−*ε*)*mr* = 2*ε**s* holds. Then construct a 2CNF formula (an instance for *L**ε*) by repeating *φ* for *r* times and adding *s* pairs of contradicting clauses. A simple calculation shows that this is indeed a reduction from *L*1/5 to *L**ε*.

This reduction clearly works only if *ε* is rational, because otherwise *r* and *s* cannot be taken as integers. The general case where *ε* is not necessarily rational seems to require inapproximability, as Yuval Filmus wrote in his answer.

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


# Question
Title: Lower bound on size of proof that a list of integers is sorted
Suppose we have a list of unbounded integers, written in binary, and we want to write a (formal) proof that the list is sorted in ascending order.

Such a proof might look (informally) like: "2 \< 3, and 3 \< 5, and ... and 71 \< 79, so the list is sorted."

It would seem such a proof must have length $\Omega(n)$ where $n$ is the length of the list of integers, as you could use the same kind of argument that is used to show that comparison sorting is $\Omega(n \log n)$; roughly, if the proof was any shorter than $n$, it would have missed one of the integers on the list.

Is this the case, or have I missed something? Is there a clever way to construct an asymptotically shorter proof?

**Edit**: As Gilles and Yuval Filmas point out below, a specific answer can only be given if we have some constraints on the language in which the formal proof is written. For the purposes of this question, suppose that no matter what particular proof language is used, *the proof must be written such that it can be verified in time at most polynomial in the length of the proof*. This excludes proofs of the form "for all elements of the list, ..." (I realize this constraint may make the question more difficult than if a particular proof language was chosen, but it really is closest to what I was thinking when I asked the question.)

# Answer
When talking about proofs, you need to explain three things: (1) formal proof system, (2) what you want to prove, (3) what you want to prove it from.

You seem to imply that item 3 should be $n$ different axioms, listing the contents of the array. In that case, you're right that you will need to invoke all axioms to prove that the list is sorted, in any consistent formal system.

Another reason why the proof will need to be of linear length is that item 2, what you want to prove, might be stated as $A\[1\] \leq A\[2\] \land A\[2\] \leq A\[3\] \land \cdots \land A\[n-1\] \leq A\[n\]$.

However, perhaps it is the case that item 3 is a description of the algorithm, and item 2 is something similar to Gilles's formulation, $\forall i \in \[n-1\], A\[i\] \leq A\[i+1\]$. In that case, if the proof system is strong enough (say ZFC), then you should be able to prove item 2 in $O(\log n)$ by starting with a general correctness proof for your algorithm, and then invoking it for your particular $n$. If your proof system is too weak to prove something like that, you might still be able to prove that the array is sorted in $O(\log^{O(1)})$; the relevant subject is known as *bounded arithmetic*.
> 4 votes

# Answer
An alternative way to look at the problem is to ask what is the complexity of checking if a given list of numbers is sorted. Then by an adversary argument it can be shown that you have to access all of the numbers and therefore the time complexity (also query complexity) of the algorithm needs to be $\Omega(n)$.

This is related to Yuval's answer. You can consider an algorithm as a proof system for the problem: a proof will be an execution of the algorithm on the input resulting in the desired output.
> 0 votes

---
Tags: proof-techniques, lower-bounds, descriptive-complexity
---


# Question
Title: Are any problems in P known to have logarithmic-time-verifiable certificates?
Problems in NP have certificates which can be verified in polynomial time.

It seems conceivable that there could be problems in P which have certificates which can be verified in logarithmic time. (Such certificates would also have to be logarithmic in size, naturally.)

However, it is also conceivable that there are no such problems. I've tried to come up with examples, but none of them have worked out so far.

Have problems like this been studied and shown to exist (or not exist)?

I can't seem to find a complexity class that would describe them in the Complexity Zoo, although it's certainly possible that there's one there and I'm just having a hard time identifying it. (L and LOG usually refer to space, and neither LH nor NLOG looks like it necessarily captures the idea.)

# Answer
> 5 votes
The question here is that in the certificate definition of $\mathsf{NP}$, what is more important is the size of the certificate (in the size of the input), the complexity class that the certificate verifier belongs too is less important. In fact you can take the verifier to be in $\mathsf{AC^0}$ as long as the size of the certificates are polynomial in the size of the input and you will still get the whole problems in $\mathsf{NP}$. $\mathsf{AC^0}$ is a very small complexity class that is included in almost every complexity class you have heard of.

To obtain smaller classes you also need to restrict the way the certificate verifier accesses the certificate. One kind of restriction that is considered is restricting the number of times the verifier can read the input using a log-space verifier. Something similar may work to capture $\mathsf{P}$, but just capturing it in this way is not interesting. The certificate definition should be nice and interesting so that it would give us some insight about $\mathsf{P}$. The certificate definition of $\mathsf{NP}$ is interesting because it is an exceptionally nice, it is even more intuitive than the original definition using non-intuitive non-deterministic machines. It allows us to cast the question regarding $\mathsf{P}$ vs. $\mathsf{NP}$ as "efficient solving vs. efficient verifying". Just having a certificate definition by itself is not very interesting.

---
Tags: complexity-theory, nondeterminism
---


title: Reducing a problem to Halt

text:
# Question
Title: Reducing a problem to Halt
I'm reviewing for a computability test, and my professor has not provided solutions to his practice questions. I came up with a "solution" to this problem, but it really seems like my answer is wrong (since I call upon $\mathsf{Halt}$ twice)...

We are given this initial language for some machine $M$:

$\mathsf{2Strings} = \left\\{ \left\<M\right\>\ |\ L(M)\text{ contains at least 2 distinct strings }\land M\text{ is a }TM \right\\}$

And we are told to "*\[s\]how that \[the language\] is recursive-enumerable.*" The problem title is **Reduction**, so I assume we are supposed to use that.

My solution is as follows:

1. Pass $\left\<M\right\>$ to the following reduction:
2. Create $w\_1 \in L(M), w\_2 \in L(M)$, so that $w\_1 \not= w\_2$, and let $M' = M$.
3. Pass $\left\<M', w\_1\right\>$ to $\mathsf{Halt}$. If the answer is **Yes**, proceed to step 4. Otherwise, return **No**.
4. Pass $\left\<M', w\_2\right\>$ to $\mathsf{Halt}$. If the answer is **Yes**, return **Yes**. Otherwise, return **No**.

Basically, this is my logic: We pass each of two distinct strings from $L(M)$ to $\mathsf{Halt}$ separately; if either one says **No**, our answer is **No**. If both say **Yes**, the answer is **Yes**.

Is my answer valid? More importantly, is it correct? If not, what should I do to fix it?

# Answer
> 5 votes
First of all I find it rather artificial to argue with reductions, since a more direct argument is applicable here. However, you can of course do it.

I think your approach follows basically the right direction. But it is not a *clean* reduction. Here is how I would phrase it.

We want to show that ${\sf 2Strings}$ is recognizable by showing ${\sf 2Strings}\le\_m {\sf Halt}$. The reduction goes as follows: Assume we have a TM $M$ and based om $M$ we define a different TM $M'$. Let us first define a NTM $N$:

```
 0. Delete the input
 1. Guess two words u and w
 2. If u=w cycle
 3. Simulate u on M
 4. Simulate w on M
 5. Accept if both simulation accepted, otherwise cycle

```

Now let $M'$ be the deterministic version of $N$. The reduction maps $\langle M \rangle $ to $\langle M',\varepsilon \rangle$. By construction, $$ \begin{align} \langle M \rangle \in {\sf 2String} & \iff N \text{ accepts every input}\\ & \iff M' \text{stops on every input}\\ & \iff M' \text{stops on }\varepsilon \\ & \iff \langle M',\varepsilon\rangle \in {\sf Halt} \\ \end{align} $$

# Answer
> 0 votes
You don't need to give a reduction to show that the language is r.e., you can simply give an algorithm that will recognize the language.

Given $\langle M \rangle$:
0. Check if $M$ is a TM, if it is not reject,
1. Run $M$ in parallel on all strings using dove-tailing,
2. As soon as two branches halt and accept, halt and accept.

or

Given $\langle M \rangle$:
1. Check if $M$ is a TM, if it is not reject,
2. Guess two strings $u\neq v$,
3. Run $M$ on $u$ and $v$,
4. If both halt and accept, halt and accept.

A reduction to $Halt$ proves more than the language being r.e., it proves that the complement of the language is not r.e., if the question was asking for that then you would need to give a reduction.

---
Tags: computability, reductions
---


# Question
Title: Generalizing the Comparison Sorting Lower Bound Proof
Let's start with the comparison sorting lower bound proof, which I'll summarize as follows:

1. For $n$ distinct numbers, there are $n!$ possible orderings.
2. There is only one correct sorted sequence of the $n$ numbers.
3. We are given that comparison ($\<$) is the only operation we have that can narrow down the $n!$ possible orderings, and each comparison has only two possible outcomes.
4. So $\log\_2(n!)$ comparisons are required.

Now consider the following generalization of the argument above:

1. Define a space of possibilities and its size (in the case of sorting, $n!$ orderings)
2. Define the goal state and its size (in this case, only one correctly sorted answer)
3. Define the amount of information that is gained at each step of the computation (in this case, one bit since there are only two possible outcomes per comparison)
4. Calculate the information difference between the space of possibilities (step 1) and the goal space (step 2) and divide by the information gain per step (step 3) to yield the lower bound on the number of steps (in this case, $(\log\_2(n!)$ - $\log\_2(1))$ / 1 = $\log\_2(n!)$).

Please answer all the following questions. I'm less concerned with the correctness of the particulars of step 4 than I am with the correctness of steps 1 - 3.

1. Are there any problems with the generalized argument?
2. If the problems can be fixed, what are the fixes?
3. If the problems can't be fixed, please point out the fatal ones and provide directions to sources which describe these lower-bounds proofs and their pitfalls.

# Answer
> 4 votes
The decision tree method for proving lower-bounds (like the $\Omega(n \lg n)$ lower-bound for comparison based sorting you mentioned) are often called information theory methods.

Here is a short video by Faith Ellen about this method:

The first part is here:

---
Tags: proof-techniques, sorting, information-theory, check-my-proof, lower-bounds
---


# Question
Title: Question related to Hilbert's 10th problem
Given $n \in \mathbb{N}$ and $p,q \in \mathbb{N}\[x\_1,\ldots,x\_n\]$ one can define the following formula in the language of formal arithmetics

$$\varphi(n,p,q) = \forall x\_1 \cdots \forall x\_n : \neg (p(x\_1,\ldots,x\_n) = q(x\_1,\ldots,x\_n))$$

I would like to show that there are infinitely many triples $(n,p,q)$ such that neither $\varphi(n,p,q)$ nor $\neg \varphi(n,p,q)$ is a theorem of formal arithmetic.

In showing this I can use the fact that the problem of deciding if a polynomial $r \in \mathbb{Z}\[x\_1,\ldots,x\_n\]$ has a natural zero is undecidable.

Knowing the above fact we know that there is a polynomial $r \in \mathbb{Z}\[x\_1,\ldots,x\_n\]$ such that neither $$\varphi' = \forall x\_1 \cdots \forall x\_n : \neg (r(x) = 0)$$ nor $\neg \varphi'$ is a theorem. (Here the quantifiers are over the naturals which I am not sure if I can use deliberately?)

Once we have such $r$ we can write it as $$r(x\_1,\ldots,x\_n) = p(x\_1,\ldots,x\_r) - q(x\_1,\ldots,x\_n)$$ for $p,q \in \mathbb{N}\[x\_1,\ldots,x\_n\]$ and hence $\varphi(n,p,q)$ and $\neg \varphi(n,p,q)$ are also not theorems since $\varphi$ is logically equivalent to $\varphi'$ and we have shown that this is not a theorem.

Once we have one such triple $(n,p,q)$ we have infinitely many of them since we can just take $(n,p+k,q+k)$ for $k \in \mathbb{N}.$

Since I never did such things before I am wondering if the above reasoning is correct?

# Answer
> 4 votes
As pointed by Yuval and cody there are easy solutions to get infinitely many Diophantine equations that are not provable nor refutable (let's say in PA).

However these syntactic solution result in provably equivalent sets, i.e. sets that the theory can prove they are equivalent. You can consider these as padding arguments. Another way is adding a variable which is not used at all.

You can also play with adding or removing some strings explicitly (finite variations of the set).

If you want to get Diophantine equations that are "essentially" different (e.g. the sets are not Turing equivalent) then that is more challenging and I think knowing that there is an independent Diophantine equation is not enough, you will need the fact that every r.e. set can be encoded as a Diophantine equation (or something similar).

ps: since you only care independence it is more natural to represent these formulas as Diophantine equations not their negations.

---
Tags: computability, logic, undecidability
---


# Question
Title: Simulate the concatenation of two log-space programs in log-space
I've got two log-space programs $F$ and $G$.

* Program $F$ will get input in array $A\[1..n\]$ and will create the output array $B\[1..n\]$.
* Program $G$ will get as input $B$ as created by $F$ and create from it the output array $C\[1..n\]$.

I have to write a proof that there exist a log-space program $H$, which will get input Array $A$ and create from it corresponding array $C$. But I can't find the correct way to write it. How is this done?

---

A log-space program is a program which uses $O(\log n)$ bits of memory. Here are some conditions you have to keep:

1. You have to use only variables which have simple integer type (for example `int` in C++, `longint` in Pascal).
2. Allowed range of integer is defined: if $n$ is the size of the input we can save into variables only values which are polymonial sized based on $n$.

For example: we can have variables which can takes on values in $\[-n...n\]$, $\[-3n^5...3n^5\]$ or also values $\[-4...7\]$, but we can't have variables which will take on values in $\[ 0...2^n\]$. No other types of variables are allowed, neither are arrays and iterators.
3. Exceptions from the rules about are input and output. Input will be available in special variables (mostly arrays) which your program can only read from, and the output can only be written to other special variables. So you can't read from output, and you can't increase values of input variables etc.
4. Your programs can't use recursion.

Example of log-space program written in Pascal (so everyone can understand it) which will find the largest number in the array of integer

```
    var n: integer;  //input variable the number of elements in A
    A: array [1..n] of integer; //input variable - the array of integers
    m: integer;      // output variable, the position of maximum
    i, j: integer;   //working variables
    begin
      j := 1;
      for i := 2 to n do
        if A[i] > A[j] then j := i;
      m := j;
    end;

```

The only two variables here are `j` and `i` and they evidently take values in $\[1...n\]$. Therefore all conditions are fulfilled and it really is a log-space program.

# Answer
The idea here is that we can't compute the output of the first algorithm completely because it can take more than logarithmic space (it can be polynomially large). But we don't need to if we are intelligent. What we can do is simulate the second algorithm and produce the bits it needs from the output of the first algorithm on-line. In other words, we will simulate the second machine, when it wants to read bit $i$ from its input, i.e. the bit $i$ from the output of the first machine, we stop the simulation of the second machine, simulate the first and count (but not store) the bits it outputs until it outputs the $i$th bit at which time we can stop the simulation of the first machine and continue with the simulation of the second machine as we now have the value of what it wanted to read.
> 3 votes

---
Tags: algorithms, complexity-theory, simulation, space-complexity
---


# Question
Title: How can I prove that the language of a read-only Turing machines is regular?
I find this, but I can't complete it, is there any other solution for it?

# Answer
> 4 votes
According to wikipedia, a read-only Turing (rTM) machine is a two-way finite automaton (2FSA). Two-way finite automata accept regular languages, and we are done.

Unfortunately, it is not *that* simple.

A Turing machine is allowed to wander into the area of the tape that consists of blank cells. This a 2FSA cannot do, usually it has end-of-tape markers. (Turing machines in general do not have these markers, otherwise they would be equivalent to linear-bounded automata.) Now a simulation of a rTM machine by a 2FSA is straightforward for the written part of the tape. For the blank parts we need transitions to code that the machine leaves to the right in state $q$, making a computation on blanks, returning in the rightmost cell in state $q'$. These are fixed by the machine, and do not depend on the actual input. Similarly for the left part (is the tape is two-sided infinite). Then there are accepting transitions that recognize that the rTM walks off the tape, does not return, but halts (and accepts). Non-halting non-returning excursions in the blank part can be ignored, they do not add to the accepted language.

# Answer
> 0 votes
Just hearing the question makes me think of two aspects:

* **Why class of automata from Regular Language(RL) is called finite automata.**

The class of automata for Regular Language(RL) is Finite Automata(FA). The automata is called finite because of finite memory available in term of states. So can construct Finite Automata for a language for which to process any string in language it requires to stored finite(Bounded) information only at any instance.
**e.g** Fan-Switch example with ON-OFF state we can say which state is in FAN(running or off). But we can't tell how many time switch has been ON-OFF.

Because there is only Finite state in any automata, memory in-term of states can be finite. We can only read input string `w` and switch state to memorized what type has been come like even or odd, or dived by two, But can not count information as required in anbn for n \>0.

* **How to enhance capability of Finite automata?**

The next is, if we can have only finite memory in form of states, how can we improve automata, and build a new class of automata that is more capable then Finite Automata. `Obvious answer is add external memory`.

In PDA memory is attached in restricted from called stack (where push and pop operation are allowed). We can store information in stack while processing input string `w`. that can be read later as required.

**\[ANSWER\]**

In Turing Machine memory is much flexible than PDA, like a Random Access Memory. We can read-write any memory location at any instance while processing a language input string `w`. Hence Turing Machine is much capable then FA because we can store information and read from any where in memory.
But think if we don't store information in memory then how can we keep track of unbounded information in form of state. This become again incapable to processes languages that required to stored unbounded information while processing strings in language.
In this way A READ ONLY only TURING MACHINE that doesn't write(store) information in memory is just a kind of Finite Automata. (external memory not used).

---
Tags: regular-languages, turing-machines
---


# Question
Title: Greedy Optimum Dominating Set For A Tree
I am trying to figure out a greedy algorithm that finds the optimum (minimum) dominating set for any tree in linear time.

So a greedy algorithm to find a dominating set for a general graph is not optimum. It's an approximation of the optimum dominating set. But since this is a tree I am assuming that a greedy algorithm can give the optimum.

What i have so far is:

Select a vertex with the maximum number of adjacent vertices that are not dominated (that is, it's neighbors are either not dominated by one it its neighbors or they are not a dominated vertex themselves). We add this vertex to the dominated set.

We repeat this proceudue until all vertices are either in the dominated set or are neighbors of one of the dominated vertices.

But I am not sure this will give an optimum solution.

# Answer
There is a simple dynamic programming algorithm. Root the tree at some arbitrary vertex. For each subtree, compute the optimal dominating set (a) with the root, (b) without the root.
> 5 votes

# Answer
Choose the root so that it is a balanced tree. Put the parents of the leaves into the dominating set, do the same for the nodes of every other level.
> 0 votes

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


# Question
Title: Formalization of the shortest path algorithm to a linear program
I'm trying to understand a formalization of the shortest path algorithm to a linear programming problem:

For a graph $G=(E,V)$, we defined $F(v)=\\{e \in E \mid t(e)=v \\}$ and $B(v)=\\{ e \in E \mid h(e)=v\\}$ where $t(e)$ is a tail of a node, and $h(e)$ is a head of a node.

Also the solutions for the conditions for the linear problem was defined as $b\_v=1$ for every node $v$ except of the root $r$ which from it we find all the shortest paths in the graph where $b\_r=-(n-1)$. It is written here "We associate a flow (primal variable) $x\_e$ with each arc $e \in E$.

The main linear program is to minimize $\sum\limits\_{e\in E }c\_ex\_e$, subject to $\sum\limits\_{e\in B(v)}x\_e-\sum\limits\_{e\in F(v)}x\_e=b\_v$ for all $v \in V$ and $x\_e \geq 0$ for all $e \in E$, where $c\_e$ is the length of arc $e$.

I'd really love your help with understanding what does $x\_e$ represent. Is it the number of times I use $e$ in order to find all the shortest paths in the graph?

I don't understand why does the above condition for this linear program is as at it, why does $\sum\limits\_{e\in B(v)}x\_e-\sum\limits\_{e\in F(v)}x\_e=b\_v$ for all $v \in V$ should be $1$ for every node and $-(n-1)$ for the all the root? If I think of a $3$ nodes tree for a graph,for the middle node we get that the condition equals to $1$, which makes me think that I might be misunderstood what $x\_e$ stands for.

# Answer
> 3 votes
This formalization takes Dijkstra's algorithm and formalizes it as a network flow problem.

In the network flow problem, $b\_i$ represents the amount of flow that enters or leaves a network at vertex $i\in V$. If $b\_i \> 0$ we say that $i$ is a source supplying $b\_i$ units of flow. If $b\_i \< 0$ we say that $i$ is a sink with a demand of $|b\_i|$ units of flow. Here $B(v)$ are $v$'s outgoing edges and $F(v)$ are $v$'s incoming edges. So the condition $\sum\_{e\in B(v)} x\_e - \sum\_{e \in F(v)}x\_e = b\_v = 1$ means that I'm allowed to supply $1$ more unit of flow coming out of $v$ than going into $v$.

Now in the network flow algorithm I'm pushing flow into the sink node, in this case the root $r$. Since each node can supply only $1$ unit of flow, the amount of flow going into $b\_r$ is $n-1$. So these equations are satisfied when each node pushes it's one unit of flow down to the sink node, enforcing that we find the shortest path from every node to $r$. Now you can see that $b\_r=-(n-1)$ means that it expects the $1$ unit of flow from every node.

From this it should be easy to see that $x\_e$ represents the number of times you've travelled along the edge $e$ in every shortest path. The minimum cost flow problem asks for flows $x\_e \in \mathbb{R}^{n\times n}$ that conserve the flow at each vertex and minimize your objective function $\sum\_{e\in E} c\_e x\_e$. So if $x\_e$ is the number of times you've used the edge $e$ in all the shortest paths and $c\_e$ is the cost of pushing $1$ unit of flow across $e$ (i.e. the length of $e$), then $\sum\_{e\in E} c\_e x\_e$ is summing the cost of every edge used across all the shortest paths.

Let's take an example with three nodes and a graph that looks like 0--1--2.

Assume that 2 is the root and each edge is unit length. So the shortest path for vertex 0 is 0--1--2 and the shortest path for vertex 1 is 1--2. So I used 0--1 once and 1--2 twice. This satisfies the equations that the units of flow going into a vertex must be one less than those going out. Additionally we have $-2$ units of flow going into vertex $2$, so that equation is satisfied as well. The objective function then sums to $3$ which is our minimum flow cost.

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


title: About complexity of a language

text:
# Question
Title: About complexity of a language
I have a language which is made out of and has a grammar only operating on well parenthesized words or words of one symbol. I want to know if the problem of belonging to this language is decidable.

**Example.** Consider the following grammar: $$a \to a(aa) \\ a \to b \\a (a(a(ab))) \to b$$ I'll denote by $L(x)$ the language generated by the above grammar and rule $S \to x$.

Trivially, $b \in L(a)$, using rule 2.
Also $b \in L(a(aa))$ by the sequence of productions $a(aa) \to a(a(a(aa))) \to a(a(a(ab))) \to b$.
However $b \notin L(aa)$ because after applying rule 1 any number of times and then rule 2, symbol $a$ will be repeated $2n + 1$ times and rule 3 can only remove $4m$ of them.

Note, the grammar is actually dealing with trees. Parentheses denote a subtree and symbols denote leaves. Hopefully the notation is clear enough. The language seems much weaker than RE but stronger than context free.

# Answer
(I completely removed the previous answer, which was applicable only to this particular example).

Your grammars seem to be known as *ground term rewriting systems* nowadays.

They are rather old. They might be introduced by W.S. Brainard: Tree generating regular systems. Inform. and Control 14 (1969) 217-231.

Concerning your question. I googled a paper of a good old collegue. Joost Engelfriet: Derivation trees of ground term rewriting systems. If my hunch, that this is the correct model, is correct, I like to cite Theorem 4 of that paper:

> For every extended ground tree grammar $G$ a regular tree grammar $G'$ with $L(G') = L(G)$ can effectively be constructed.

It is in the section called "New proofs for old results", so that must be a known result.
> 1 votes

---
Tags: formal-languages, computability
---


# Question
Title: Bipartite Problem is Log-Space Reducible To $s$-$t$ Undirected Connectivity
Prove that the problem of determining if graph is bipartite is computationally equivalent under log-space reductions to $s$-$t$ undirected connectivity.

Problem of $s$-$t$ undirected connectivity is the following given an undirected graph $G = (V, E)$ and two designated vertices, $s$ and $t$, determine whether there is a path from $s$ to $t$ in $G$.

I assume the idea is to consider mapping from graph $G$ to bipartite graph $G'$, there should be a correspondence between edges of $G$ and edges of bipartite graph $G'$, and between edges of $G$ and the edges that violates the bipartite property of graph $G'$. The problem is I cannot come up with such correspondence.

I would appreciate any idea.

# Answer
Here are some ideas on how to reduce checking bipartiteness to undirected *non*-connectivity:

1. A graph is bipartite iff it has no odd cycles.
2. Suppose we guess that vertex $v$ participates in a cycle of length $2k+1$. Using a layered graph, we can check whether it is the case using undirected connectivity.
3. We can also implement a disjunction ("or") using undirected connectivity.

Here are some ideas for the other direction:

1. Every graph can be made bipartite by splitting every edge into a path of length $2$.
2. What happens when we join $s$ and $t$, after splitting the edges?
> 4 votes

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


# Question
Title: Prove given equality check function works for all subset of integers
I wrote a function to check equality between integers `a` and `b` using bitwise shift operators. Return value of `1` means both are Equal and `0` means unequal inputs.

```
int foo(int a, int b)
{
        return ((a>>= b<<= a) ? 1 : 0);
}

```

How can I prove theoretically that function `foo()` works for all values in subset of integer range including negative values. If it fails for certain values, can I theoretically find out for what set of values will foo() works correctly.

# Answer
I don't think this is the right place for such questions, and maybe Stackoverflow or programming puzzles and code golf may be better suited. However, I'll try to answer the question nevertheless.

I do not think your code has anything to do with equality of two numbers.

Your code can be separated into three lines as:

`b = b << a;`

`a = a >> b;`

`return a != 0 ? 1 : 0`

Well, first of all, if the right side of such a shift operator is negative, the behavior is undefined in C99 and C11. So for negative values, you can't be sure what will happen. The behavior is also undefined if the right operand is greater than or equal to the width of the promoted left operand. See quote below from C11 standard, section 6.5.7:

> If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

And, the behavior will indeed be undefined for most values, either for the first part, or for the second. For the very few cases where both are defined, you are essentially calculating:

$$\frac{a}{2^{b \cdot 2^a}}$$

and I have no idea how that would help in checking for equality. Basically, even if $a$ equals $b$, the above under integer division would be 0, and will give the wrong output.

In short, the behavior is undefined, and to get theoretical answers, you need to at least define the behavior theoretically and completely.
> 3 votes

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


title: Multisets of a given set

text:
# Question
Title: Multisets of a given set
A multiset is an unordered collection of elements where elements may repeat any number of times. The size of a multiset is the number of elements in it counting repetitions.

(a) What is the number of multisets of size $4$ that can be constructed from $n$ distinct elements so that at least one element occurs exactly twice?

(b) How many multisets can be constructed from $n$ distinct elements?

For part b, infinite is correct.

For part a, taking $n=3$ and elements $\\{1,2,3\\}$ we have multisets as: $\\{1,1,2,2\\}, \\{1,1,3,3\\}, \\{1,1,2,3\\}, \\{2,2,3,3\\}, \\{2,2,1,3\\}, \\{3,3,1,2\\}$, for a total of $6$.

Similarly for $n=4$ and using elements $\\{1,2,3,4\\}$, we have $18$ multisets. There must be some formula, or we have to develop one!

I am in particular looking for a formula when there is a restriction on the number occurrences in the multiset.

# Answer
Here is one way to go about your part (a):

There are four places to be filled in the multiset using the $n$ distinct elements. Atleast one element has to occur exactly twice. That would leave 2 more places in the multiset. This means, *atmost* two elements can occur exactly twice. We can thus divide this into 2 mutually exclusive cases as follows:

1. Exactly one element occurs exactly twice: Select this element in ${n\choose{1}} = n$ ways. Fill up the remaining two spots using 2 distinct elements from the remaining $n-1$ elements in ${{n-1}\choose{2}}$ ways. Overall: $n \cdot {{n-1}\choose{2}} = \frac{n(n-1)(n-2)}{2}$ ways.
2. Exactly two elements that occur twice each: These two will fill up the multiset, so you only have to select two elements out of $n$ in ${n\choose 2} = \frac{n(n-1)}{2}$ ways.

Since these are mutually exclusive, the total number of ways to form the multiset is: $$\frac{n(n-1)(n-2)}{2} + \frac{n(n-1)}{2}$$$$ = \frac{n(n-1)^2}{2}$$

Note, that $n \ge 2$ otherwise no element can be present twice. This is also obvious from the formula (when $n = 0, 1$).

You can check that the formula tallies with your counts.
> 7 votes

---
Tags: combinatorics, sets
---


# Question
Title: Can abstract syntax trees be unparsed in subexponential time?
### Abstract problem description

The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST, i.e. `parse(unparse(AST)) = AST` should hold.

This is the equal to finding a valid parse tree which would produce the same AST.

The language is described by a context free S-attributed grammar using a eBNF variant.

So the unparser has to find a valid 'path' through the traversed nodes in which all grammar constraints hold. This bascially means to find a valid allocation of AST nodes to grammar production rules. This is a constraint satisfaction problem (CSP) in general and could be solved, like parsing, by backtracking in $O(e^n)$.

Fortunately for parsing, this can be done in $O(n^3)$ using GLR (or better restricting the grammar). Because the AST structure is so close to the grammar production rule structure, I was really surprised seeing an implementation where the runtime is worse than parsing: XText uses ANTLR for parsing and backtracking for unparsing.

### Questions

1. Is a context free S-attribute grammar everything a parser and unparser need to share or are there further constraints, e.g. on the parsing technique / parser implementation?
2. I've got the feeling this problem isn't $O(e^n)$ in general -- could some genius help me with this?

I didn't receive an answer for this question on StackOverflow. It was suggested to ask here, but I hate redundancy, so I hope you forgive me for asking you to answer here.

# Answer
> 3 votes
There is a version of your question for which unparsing is easy and can be done in linear time. However, I'm not entirely sure if your question pertains to this specific version of unparsing, so I'll look at that first.

You say in your question over at StackOverflow that your AST looks like "AnyObject -\> AnyObject -\> Vehicle \[name="Car"\]". Your question would be a lot easier if your AST looks like "Area -\> Highway -\> Car", that is, that we know which productions were taken when your AST was constructed/parsed. In ordinary context-free parsers, you (almost) always get this information: you might decide to throw it away, but (nearly) all parsing algorithms can also give you this information.

If you don't have this information, I'm pretty sure exponential time is the best you can do, unless you know something about your S-expressions. The problem then is simply recovering the "Area -\> Highway -\> Car" AST, the unparsing after that is the easy part.

If you do have this information, then we can just look at context-free grammars and try to unparse them. Consider this grammar:

> 1: $S \to a$
> 2: $S \to a S a$

An AST for this grammar may look like $S \to a (S \to a) a$, on input "aaa". Unparsing this AST is easy: perform a postorder walk of the tree and output all terminals found in this walk. The result is "aaa" again.

Things become a bit more complicated when you look at ambiguous context-free grammars. On one hand, things are still easy: you just pick any parse tree of your input and do the above: you can reconstruct all other parse trees from the result.

However, in the presence of disambiguation rules, you have to do something clever. In particular, the input "(1+2)\*3" may be unparsed as "1+2\*3", which is different from the original. It is possible to do this in linear time on $LR(1)$ grammars (where precedence and associativity are enforced like in Yacc) by doing a reverse $LR$ parse at unparse time. I'll skip the details, as this was not part of your question, but it can be done.

---
Tags: algorithms, compilers, parsers, attribute-grammars
---


# Question
Title: What is the advantage of Randomized Quicksort?
In their book *Randomized Algorithms*, Motwani and Raghavan open the introduction with a description of their RandQS function -- Randomized quicksort -- where the pivot, used for partitioning the set into two parts, is chosen at random.

I have been racking my (admittedly somewhat underpowered) brains over this for some time, but I haven't been able to see what advantage this algorithm has over simply picking, say, the middle element (in index, not size) each time.

I suppose what I can't see is this: if the initial set is in a random order, what is the difference between picking an element at a random location in the set and picking an element at a fixed position?

Can someone enlighten me, in fairly simple terms?

# Answer
If the input array is distributed uniformly at random then (as you noted) there is no difference between always picking an element at a fixed position (for example the middle one as you suggest) or picking an element chosen at random.

If however your input array is not really in random order (which happens to be the case in almost all practical scenarios) then one needs to either "preshufle" the array in order for the elements in it to be placed in random order, or (equivalently) always take a random element as a pivot. This ensures the partitioning phase of quicksort partitions the arrays into sub-arrays of almost equal size and hence that the expected running time remains $O(n\log n)$

So your confusion appears to come from the fact that somehow you assume a sorting algorithm can (in practice) expect the input array to always be randomly distributed.
> 19 votes

# Answer
As noted by Jernej, the assumption that the all permutations of the input are equally likely does not always hold in reality. The first idea might be to permute the input array. This would work, but is easier to analyze the situation where a pivot is chosen at random. This is also known as *random sampling*.
> 4 votes

---
Tags: algorithm-analysis, sorting, randomized-algorithms
---