# Question
Title: Boruvka MST algorithm using doubly linked lists
I'm reading Sedgewick & Wayne's Algorithms book, and one of the questions in one of the chapters is the following:

> Develop an implementation of Boruvka's algorithm that uses doubly-linked circular lists to represent MST subtrees so that subtrees can be merged and renamed in time bounded by E during each stage (and the union-find data type is therefore not needed).

I'm aware of the standard version of Boruvka's algorithm that uses a union-find data structure to do the merges and check subtree identifiers (there is also an implementation on the book's official website )

But I'm not being able to figure out how to improve the performance of the algorithm by replacing the union-find data structure for subtrees represented by doubly-linked circular lists.

Any ideas?

# Answer
> 1 votes
I came across your question in pursuit of the same answer. Anyway this comment gives a hint, I would say, why a detailed algorithm is not there or easily searchable:

> It is possible to remove the lg\*E factor to lower the theoretical bound on the running time of Boruvka’s algorithm to be proportional to E lg V, by representing MST subtrees with doubly-linked lists instead of using the union and find operations. However, this improvement is sufficiently more complicated to implement and the potential performance improvement sufficiently marginal that it is not likely to be worth considering for use in practice (see Exercises 20.66 and 20.67)."

from *Algorithms in C, Third Edition, Part 5: Graph Algorithms* by Robert Sedgewick, 2001.

---
Tags: algorithms, graphs, algorithm-analysis, minimum-spanning-tree, linked-lists
---


# Question
Title: The difference between absurd reasoning and contraposal reasoning
What is the difference between absurd reasoning and contraposal reasoning? To show that a language is not regular

# Answer
I've never heard those terms in the context of computer science. When you mention "contraposal reasoning", I've never heard that term before, but I suspect that might be a reference to proving the contrapositive. When you mention "absurd reasoning", I've never heard anyone use that specific phrase, but I suspect you might be referring to proof by contradiction, also known as reductio ab absurdum, which is Latin for reduction to absurdity.

These are general proof techniques. They're not specific to showing that a language is not regular.

---

General advice: I recommend that you try to avoid proof by contradiction. It's a valid proof technique, but my experience is that it often leads beginners awry and causes them to make mistakes in the proof. I recommend instead proving the contrapositive; it leads to more straightforward proofs where it is easier to avoid errors, and spot where you went wrong if you do make an error.
> 1 votes

---
Tags: formal-languages, automata
---


# Question
Title: Omission of smaller variables in Big-O Complexity
I have an algorithm that:

**1.** takes in a book's text as a string.

**2.** splits that string into words and stores it in a list.

**3.** creates a hash table from this list by iterating over the elements of the list

**4.** It then iterates over a separate list of words to see if each of these words (in this separate list) is contained in the hashmap.

Three linear traversals occur here. One to split the input string into a word list, one linear traversal of the word list to create the hash table and one final traversal over the separate list to check each word is in the newly created hash table.

Time complexity is O(n + k + m), where n is the number of characters in the input string, k is the number of words and m is the number of words in the other list.

My question is, since k is derived from n and we can guarantee that k will always \<= n can we omit n and write the complexity as O(n+m)?

# Answer
> 1 votes
Yes, you can. Since $k \le n$, you have $n+k+m \le 2n+m = O(n+m)$.

---
Tags: time-complexity, asymptotics
---


# Question
Title: How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?
Admittedly, homework.

For the purpose of this question: $\phi$ is a DNF formula similar to this one: $(x\_1 \wedge \neg x\_3 \wedge x\_4) \vee (\neg x\_1 \wedge x\_2)$ Also $C\_i$ is a clause in this formula, for example $C\_1=x\_1\wedge \neg x\_3\wedge x\_4$

The tasks is to do this in a little bit more sophisticated way than to choose a random assignment, see if it satisfies the formula, repeat N times. More specifically the tasks tells us to:

* Uniformly at random choose a clause $C\_i$ in $\phi$.
* Set the values of the variables in $C\_i$ so that $C\_i$ is satisfied.
* Set the values of the remaining variables randomly.
* In this way sample only satisfying assignments and sample all of them.

I fail to understand: ALL OF THEM? If I want to sample ALL satisfying assignments then I'm not sampling, but rather I'm counting?

Further the task asks:

* For a given assignment $p\_i$ what is the probability of sampling $p\_i$? That's an easy question: $\frac1{2^{n-m}}$ where $n$ is the number or distinct variables in $\phi$ and $m$ is the number of variables in $C\_i$. Or am I wrong?
* How you can use the result of the previous question (the previous question was to sample trivially as I described above) to construct an estimate for the number of satisfying assignments? I don't know.

Well, I can check if this random assignment satisfies any other clauses than $C\_i$. But how can I use the result?

My Googling yielded this page: http://theoryapp.com/dnf-counting-and-the-monte-carlo-method/ But this is even more confusing for me. Instead of choosing the clause $C\_i$ uniformly, the site tells us to "pick up a clause $C\_i$ with probability $P\_i=\frac{\left|S\_i\right|}{\sum\_{j=1}{l}\left|S\_j\right|}$, where $S\_i$ is the collection of assignments satisfying $C\_i$ and $l$ is the amount of clauses in $\phi$ and then pick up an assignment from $S\_i$." But then we are told to "Check whether this assignment satisfies $\phi$. Finally, count the number of satisfying samples; denote the count by $M$". This is nonsense, each assignment that satisfies clause $C\_i$ for any $i$ must necessary satisfy the whole formula?

Admittedly, this basic course on probability and statistics is the first course where I feel like a total idiot.

Any tips? I'm loosing hopes to be able to figure this out on my own.

Finally, I'm not sure, is this question more appropriate on scicomp.stackexchange.com?

# Answer
Let $\alpha$ be a satisfying assignment. Suppose that it satisfies the terms $\\{C\_j : j \in J\\}$. If you choose $C\_i$ in the first step, then the probability that you choose $\alpha$ in the third step is 0 if $i \notin J$ and $2^{-(n-|C\_j|)}$ if $i \in J$. Hence the probability of sampling $\alpha$, assuming there are $m$ terms, is $$ p(\alpha) = \frac{2^{-n}}{m} \sum\_{j\colon \alpha \text{ satisfies } C\_j} 2^{|C\_j|}. $$ Let $A$ be a random satisfying assignment chosen according to the algorithm, and let $X = 1/p(A)$. Then $$ E\[X\] = \sum\_{\alpha \text{ satisfying}} \frac{\Pr\[A=\alpha\]}{p(\alpha)} = \sum\_{\alpha \text{ satisfying}} = \text{# satisfying assignments}. $$
> 2 votes

---
Tags: algorithms, np-hard, probability-theory, propositional-logic, monte-carlo
---


# Question
Title: Given matrix $A$, find vector $x$ such that every entry of $Ax$ is nonzero
> Given a matrix $A \in \mathbb{R}^{n \times n}$ with no zero rows, what is the complexity of deterministically finding a vector $x \in \mathbb{R}^n$ such that every entry of $Ax$ is nonzero?

It is easy to see that a vector whose entries are realizations of Gaussian random variables works. Indeed, in this case every entry of $Ax$ is a realization of a continuous Gaussian random variable and, hence, is nonzero with probability $1$. Thus, the probability that all entries of $Ax$ are nonzero is $1$. Thus if "generate a Gaussian" (or any other continuous random variable) is an allowed operation, then this takes $O(n)$ operations.

In the deterministic case, you probably need at least $O(n^2)$ operations since every entry of the matrix $A$ probably needs to be read. I'm wondering if you could do it in $O(n^2)$ or, if not, what the best time that you can do this in is.

**Edit:** I don't seem to have enough reputation to post comments on my own question. In any case, let us suppose that the entries of $A$ are all rational, and we are looking for a vector $x$ with rational entries.

# Answer
Define $$ M = 1 + \frac{\max\_{ij} |A\_{ij}|}{\min'\_{ij} |A\_{ij}|}, $$ where the minimum is taken over all non-zero entries. Then the vector $x$ given by $x\_j = M^{j-1}$ satisfies your condition.

Indeed, consider some row $A\_{i\cdot}$, and suppose that $A\_{ik} \neq 0$ but $A\_{i\ell} = 0$ for all $\ell \> k$. Suppose, without loss of generality, that $A\_{ik} \> 0$ and that $\min'\_{ij} |A\_{ij}| = 1$. Then $$ (Ax)\_i = \sum\_{j=1}^k A\_{ij} M^{j-1} \geq M^{k-1} - (M-1) \sum\_{j=1}^{k-1} M^{j-1} = 1. $$

Whether the encoding of $x$ is small enough depends on your exact computation model.
> 3 votes

# Answer
Given $\mathrm A \in \mathbb{R}^{n \times n}$ with no zero rows, we would like to find $\mathrm x \in \mathbb{R}^n$ such that every entry of $\rm Ax$ is nonzero. Let $\mathrm b \in \mathbb{R}^n$ be a vector of nonzero parameters. Solving the linear system

$$\rm A x = b$$

we find at least one solution $\rm x\_{b}$ for every choice of $\rm b$ that has no zero entries and is in the column space of $\rm A$ (so that the linear system is feasible).

If matrix $\rm A$ happens to have **full rank**, then the unique solution is $\rm x\_b = A^{-1} b$, i.e., a linear combination of the $n$ columns of $\rm A^{-1}$ in which all $n$ coefficients are *nonzero*.
> 0 votes

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


# Question
Title: Recursive definition of a language $ L $ over $ \{a,b\} $
How would I start the recursive definition of the following language:

> L over {a, b} such that L consists of strings in which each occurrence of b is immediately preceded and followed by an a

The 'and' part is causing me problems with this problem and I don't see a clean way to gurantee the occurence being preceeded and followed recursively.

The recursive definition structure is as follows:

Basis: The base we have to start with for the recursion Recursive step: How we generat ethe language from the basis Closure: Trivial to state

My thought process on this:

We can have lambda, because no b's or no a's doesn't apply to the condition.

My attempt so far:

> Basis: $ \lambda \in L $
>
> Recursive Step: If $ w\in L $ then $ aw, wa, babw, waba \in L $.

What i don't see is how th break the recursive step to account for being able to place b's anywhere in $ w\in L$ such that the condition is satisfied.

# Answer
> 1 votes
There is no problem to obtain $b$'s anywhere in the string: basically you can just "read" the string from left to right, and add the $aba$ to the end. That leaves one with only two recursive steps: if $w\in L$, then $wa\in L$ and $waba\in L$.

A bigger problem is that you now do not generate strings like $ababababa$!

This can be handled by having rules like: if the string ends with a $a$ we can add $ba$ to the end.

# Answer
> 0 votes
It can be:

> Basis: $ \lambda \in L $
>
> Recursive Step: If $ w\in L $ then $ aw, wa, abaw, waba \in L $.

You can generate with the above rules all strings in the language.

---
Tags: complexity-theory, formal-languages, regular-languages, recursion
---


# Question
Title: Can there exist more than one optimal solution in a dynamic programming problem?
In any dynamic programming problem can there exist more than one optimal state ?

If so how would I enumerate all of them ?

For example: in the subset sum problem for the given set $\\{-3, -2, 7, 5\\}$ and target sum $0$.

There exists two ways of reaching $0$. ie. $\\{\\}$ = empty set as a sum of zero, or $\\{-3, -2, 5\\}$ = also which has a sum of $0$.

In dynamic programming how would you distinguish between these two ?

# Answer
> 4 votes
Yes, but it's implicit in the dynamic programming table.

The dynamic programming table starts by filling out objective values for trivial sub-solutions, then combining them to obtain the optimum objective value by the time the final entry is reached. The central part to emphasise here is that the dynamic programming table has objective values as its entries, rather than the sub-solutions themselves (although you may hang on to all sorts of information to help the computation of course). So the way you obtain the actual solution from a dynamic programming table is to trace back from the final entry reconstructing the steps taken to get there.

Then if there's multiple ways to get there, in the tracing you just run into situations where you can go more than one way. If you were only interested in obtaining some solution, you just pick a route. If you want all of them, you exhaustively explored all routes back through the table.

---
Tags: dynamic-programming
---


# Question
Title: Proving or disproving a set of total functions is countable
> Let S be the set of total functions from $N \rightarrow M$, such that for each $f \in S$, there is $i \> 1$ such that for all $j \< i$, $f(i)$ and $f(j)$ are not equivalent Turing machines. Prove or disprove that S is countable

I don't think this is actually countable, but I'm having a hard tie proving this using diagonilzation. Can anyone give me pointers / hint? Preferably explained at a lower level.

# Answer
> 3 votes
Hint: Let $M\_1,M\_2$ be an arbitrary pair of inequivalent Turing machines. Your set $S$ contains all functions satisfying $f(1) = M\_1$ and $f(2) = M\_2$.

---
Tags: complexity-theory, computability, proof-techniques, counting
---


# Question
Title: Use the pumping lemma to show the language is not regular
I can use the pumping lemma to prove simpler examples, but i'm finding this problem rather complex partly due to the notation.

Can anyone explain how I would do this problem:

> For any string $s$ in $\\{a, b\\}^\*$, let $n\_a(s)$ be the number of a’s in s, and let $n\_b(s)$ be the number of b’s in s. Let L over {a, b} be given by $L = \\{x \in \\{a, b\\}^\* | n\_b(x) = n\_a(x)^2 \space \text{and} \space x \notin ((a^∗b^∗) ∪ (b^∗a^∗))\\} $. Prove, using the pumping lemma for regular languages, that the language L is not a regular language

I know we suppose that it is regular then by the pumping lemma it has to satisfy the properties of the pumping lemma for regular languages.

Hence, we need to find a decomposition and break it by pumping this decomposition which is no longer in the language forming a contradiction by hypothesis. However, I fail to see the decomposition or what to pump....

# Answer
> 2 votes
Assume $L$ is regular, and let $p$ be as in the pumping lemma.

Note that $s = a^pb^{(2p)^2}a^p\in L$. Now, by the pumping lemma, we have a decomposition of $s = xyz$. As $|xy|\leq p$, we must have that $y\subseteq a^p$, Say that $y = a^k$ for some $k\leq p$ (and by the property that $|y|\>0$, we have that $k\geq 1$).

Then, we have that: $$s = \underbrace{a^{p-k}}\_x\underbrace{a^k}\_y\underbrace{b^{4p^2}a^p}\_z$$ Again, by the pumping lemma, we have that $L\ni xz = a^{p-k}b^{4p^2}a^p$. But, we have that $n\_a(xz) = 2p-k$, and $n\_b(xz) = 4p^2$, but $n\_a(xz)^2 = 4p^2-4pk+k^2\neq 4p^2 = n\_b(xz)$, where the lack of equality holds because $1\leq k\leq p$, as stated before.

So, we have a contradiction to the pumping lemma, so $L$ isn't regular.

This all is entirely standard, and the only "trick" is picking the right string $s$. A few tips for this:

1. $s$ will generally need to depend on $p$ in some way so it's "long enough to be pumped"
2. You'll want to carefully choose the first $p$ characters of $s$. If it can all be one character repeated (like in this case we had $a^p$), it makes determining what $y$ is *much* easier, and you can do the proof with a single case.
3. Besides that, you want to choose the rest of the string so $s\in L$, and some "pumped version" of $s$ isn't in $L$. This is clearly the hardest part, and the part I don't have a great procedure for. Generally trying a few things ends up with something working eventually. For "counting" based ones like the one you posted (some number of one symbol is equal to some number of some other symbol), usually having the part you pump be of the form $a^k$ is enough to mess with the counting.

# Answer
> 1 votes
An alternative proof uses Parikh's theorem. If $L$ were regular, then by Parikh's theorem the set $S := \\{(n,n^2) : n \geq 2\\}$ would be semilinear. In particular, there is an infinite linear subset, and so there must exist $a\_0,b\_0,a\_1,b\_1$ (with $(a\_1,b\_1) \neq (0,0)$) such that $(a\_0,b\_0) + \mathbb{N}(a\_1,b\_1) \subseteq S$, and in particular it must be the case that $b\_0 + nb\_1 = (a\_0 + na\_1)^2$ for all $n \geq 0$. However, this is impossible: it implies that $a\_0 + na\_1 = o(b\_0 + nb\_1)$, which is only possible when $a\_1 = 0$, a case that is easy to rule out directly (since $b\_1 \neq 0$ necessarily holds in that case).

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Deterministic Nonfinite Automaton - Longest Block of Ones
How to Think About Algorithms - Jeff Edmonds

Exercise 2.2.2

The problem asks to find $\sum$, Q, δ, s, and F of this program if we see it as an automaton. Edmonds characterized this as deterministic non-finite automaton since 'n' is not bounded.

$\sum$ is {0,1} but I'm not sure how to model Q and the transition functions.

One guess is just simply Q = { q\[p\_max, q\_max, length\_max, p\_current, length\_current\] }, with each of the 5 variables taking a value in the set of size around n ( { 1, 2, 3, ... , n} ), which will have O(n^5) states

but even if I use this brute force approach I can't easily define transition functions that determine the next state based on current state and the input read each iteration (0 or 1).

The biggest difficulty is modeling conditionals. When you are at a state q\_1, the next state seems to be defined not just by 0 or 1 input but also by the length variables.

He didn't provide any solutions and I did a lot of research but still lost.

Any suggestions?

# Answer
> 1 votes
Your guess is definitely on the right track, though you may need one more piece of information. As you have infinite states (of which each input will use some number of them according to a function of the length of the input), you can use (as you observe) the states to encode information that deals with the length of the input.

There are a number of ways to do this (you can use the same variables as the code essentially), but I think it's clearer to be more explicit. Each state can keep track of the following six things:

1. The starting position of the best run so far.
2. The ending position of the best run so far.
3. The length of the best run so far.
4. The starting position of the current run being counted.
5. The ending position of the current run being counted.
6. The length of the current run being counted.

So each state could be labeled something like:

$$q\_{maxstart,maxend,maxlength,currentstart,currentend,currentlength}$$

This then solves the transition problem:

* A zero in the input ends the current run, and resets to start counting again, but doesn't affect the best run so far
* A one in the input increases the end point of the current run (and sets the starting point if the current run length is zero) **AND** if you happen to be in a state where the current run length is the same as the best run length, it also alters the best run length subscripts (that is, the transition takes you to a state where those change suitably).

There's no branching in either of those, so the process is completely deterministic.

A couple of examples to illustrate:

* The start state is easy, it's just $q\_{0,0,0,0,0,0}$ with the transitions $\delta(q\_{0,0,0,0,0,0},0) = q\_{0,0,0,1,1,0}$ and $\delta(q\_{0,0,0,0,0,0},1) = q\_{0,1,1,0,1,1}$. This uses the case where the current run length is the same as the best, and we see a one, so we update the best start and end to be the same as the current start and end etc.
* Now let's try a state where the current run changes, but isn't better than the best. Imagine we're in state $q\_{a,b,50,x,y,3}$, then the two transitions will be $\delta(q\_{a,b,50,x,y,3},0) = q\_{a,b,50,y+1,y+1,0}$ and $\delta(q\_{a,b,50,x,y,3},1) = q\_{a,b,50,x,y+1,4}$.

This actually pretty much covers all the cases (as there's really not much going on except the abuse of subscripts to count for us).

To boil that down to some rules for putting in the transitions:

1. $\delta(q\_{a,b,n,x,y,m},0) = q\_{a,b,n,y+1,y+1,0}$
2. If $m \< n$, $\delta(q\_{a,b,n,x,y,m},1) = q\_{a,b,n,x,y+1,m+1}$
3. If $m = n$, $\delta(q\_{a,b,n,x,y,n},1) = q\_{x,y+1,n+1,x,y+1,n+1}$

You don't need any states where $m \> n$, so you don't have to worry about that case (though you can include them and give them a rule like #3 if you want a complete infinite enumeration of all the subscripts.

# Answer
> 1 votes
Based on Luke Mathieson's amazing answer,

and using the concept of an "**empty**"\** block from the book

i.e. A\[i..j\] is empty is i \> J;

The transition functions can be modeled as follows (difference being how we update starting position of the current run using the empty block):

δ( Q\[p, q, leng\_max, p\_c, i, leng\_curr\] , 0 ) = Q\[p, q, leng\_max, i+2, i+1, 0\]

the other two transition functions are excellently described in Luke's answer

---
Tags: automata, finite-automata, loop-invariants
---


title: Why not a $coNP$ hierarchy?

text:
# Question
Title: Why not a $coNP$ hierarchy?
In the polynomial hierarchy we have $\Sigma\_2=NP^{NP}$ and $\Pi\_2=co\Sigma\_2$.

So we have $\Pi\_2=co(NP^{NP})$.

Is it same as $(coNP)^{NP}$?

I just wonder why not a hierarchy with $coNP$.

# Answer
> 1 votes
By definition, for any oracle for a language $A$, $(coNP)^{A}=\\{L \mid \overline{L} \in NP^{A}\\}$. Using this definition and definition of co-class we have

$$L \in co(NP^{NP})\iff \overline{L}\in NP^{NP} \iff L \in (coNP)^{NP}$$

You can also use $coNP$ instead of $NP$ as oracle (as Yuval commented), since if we can decide $x \in L$ using an oracle for a language $A$ we can decide $x \in L$ using another oracle for $\overline{A}$ as well, because $x \in A \iff x \notin \overline{A}$.

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


title: Limited oracle TM

text:
# Question
Title: Limited oracle TM
Let $M$ be a Turing machine with oracle to $B$ that can decide $B$ in polynomial time. In the general case it means nothing, since we can just pass the input as a query to the oracle of $B$ and accept/reject according to its answer.

Now, we add the next limitation: given an input of length $n$, the queries' length can be at most $n-1$. Now, how does the fact that this TM with oracle to $B$ can decide $B$ in polynomial time imply that $B$ is in PSPACE?

# Answer
> 1 votes
From the definition we can check whether $0$ and 1 (or the empty word if you want)are in $B$ without any oracle access. So we do so and now construct a new Turing machine to decide $B$. We simulate the special machine for $B$ on our input. When it makes an oracle access to $B$ we intercept it (it is of size smaller then our input’s size) and now run another copy of the special Turing machine on this oracle. Finally we work with at most $n$ queries at each time for each size from $n$ to $1$. It can be observed that when we get to a query of size $1$ we can answer immediately and return to the left of the tape. As we won’t work with two oracle queries of the same size simultaneously it is actually a $\mathbf{PSPACE}$ machine. Moreover, we do not save any oracle answer we compute it each time it is asked - on the fly.

---
Tags: complexity-theory, turing-machines, reductions, space-complexity, oracle-machines
---


# Question
Title: Minimal set of rows and columns covering all non-zero entries in matrix
> Given a matrix $A \in \\{0,1\\}^{n \times n}$, use network flows to describe an algorithm that finds the minimal set $I$ of rows and columns such that any non-zero entry is in one of the rows or columns in $I$.

### What I have tried

1. Create an intermediate column (between $s$ and $t$) for every column and row.
2. For every column, draw an edge from that column to $t$ with a capacity equal to the number of $1$s it has in it.
3. For every row, draw an edge from that row to $t$ with a capacity equal to the number of $1$s it has in it.
4. Take the cut between this intermediate column and $t$, calculate the entry with the most capacity, add that to set $I$.
5. For the selected row or column, remove all $1$s from that column and recalculate the network flow.
6. Continue to do this until the flow is $0$, i.e., all $1$s have been accounted for.

### Examples

```
1 1 0
1 0 0
1 0 0

```

We would take column 1, and row 1 here.

```
1 1 1
0 0 0
0 0 0

```

We would take row 1 here.

Is there a better approach?

# Answer
> 2 votes
Your problem can be phrased as minimum vertex cover in a bipartite graph: there is a vertex for each row and column, and each non-zero entry contributes an edge. You can find a minimum vertex cover by finding a maximum matching; see Kőnig's theorem.

---
Tags: algorithms, network-flow, matrices
---


# Question
Title: Does closure under union and concatenation imply closure under Kleene star?
For decidable languages (or a particular subset of decidable languages, e.g., regular, context free) does closure under Kleene star follow from the proof of closure under union and concatenation? The only thing that the latter seems not able to produce is an empty string.

# Answer
You haven't stated whether you're interested in finite or infinite union, though as you mention, it doesn't really matter due to problem with the empty string. However, instead of giving the answer, let me explain how to answer such questions.

**Showing that a language class is closed under operation $O$ given that it is closed under operations $O\_1,\ldots,O\_m$.** You show how to simulate $O$ using $O\_1,\ldots,O\_m$. For example, suppose that a language class is closed under union and complement. Then it is also closed under intersection, since $A \cap B = \overline{\overline{A} \cup \overline{B}}$.

**Showing that if a language class is closed under $O\_1,\ldots,O\_m$ then it is not necessarily closed under $O$.** You given a language class which is closed under $O\_1,\ldots,O\_m$ but not under $O$. For example, let us show that a language class which is closed under finite union isn't necessarily closed under infinite union. Consider the language class consisting of all finite languages. This class is closed under finite union but not under infinite union.

Given this information, you should be able to answer your question on your own.
> 3 votes

# Answer
No, it doesn't.

As an example subset of decidable languages which is closed under both union and concatenation, but not under Kleene star, consider: $\\{ \emptyset \\}$

$\emptyset \cup \emptyset = \emptyset$
$\emptyset\emptyset = \emptyset$
but
$\emptyset^\* = \\{ \epsilon \\}$, which doesn't belong to our subset.
> 3 votes

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


title: Help understand the notation

text:
# Question
Title: Help understand the notation
I'm reading a computer science paper, this one: https://arxiv.org/abs/1608.03960. It uses certain notation in one of the illustrations (Figure 9, page 8 in the PDF version) that I don't understand how to interpret. Attaching here as well for better visibility:

$$ \text{EXEC} ~ \frac{\text{cmd}\_1 : \text{CMD} \quad A\_p, \text{cmd}\_1 \implies A^\prime\_p}{A\_p, \langle \text{cmd}\_1 ~ ; ~ \text{cmd}\_2 ~ ; \ldots \rangle \implies A^\prime\_p, \langle \text{cmd}\_2 ~ ; \ldots \rangle} $$

I've tried to search for this online, but haven't come up with anything. I'd appreciate if someone explain it to me, particularly these questions:

1. Does this notation has an official or widely recognized name?
2. What's the relationships between expression above and below the horizontal line?
3. What's the meaning of $\Rightarrow$, long arrow?
4. What's the meaning of two expressions being separated by a comma, as in $A\_p, cmd\_1$? How is it different from two expressions separated by a blank space, as in $$\mathrm{cmd}\_1, \mathrm{CMD}\ \ \ \ \ \ \ \ A\_p, \mathrm{cmd}\_1\\,?$$

Here's another example from the paper:

$$ \text{VAR} ~\frac{x \in \text{dom}(A\_p)}{A\_p, x \implies A\_p(x)}$$

5. What's the meaning of $dom(A\_p)$ here?

# Answer
> 6 votes
Answering your questions one by one:

1. The rules are part of an operational semantics, which defines how to evaluate expressions.
2. The notation with the horizontal line is an inference rule: if all the logical statements above the line are true, then you can conclude that the statement below the line is also true.
3. The arrow is a predicate that indicates that the left hand side can be *evaluated* (or *reduced*) to the right hand side.
4. The expressions separated by a comma form a tuple; for example, $A\_p, cmd\_1$ is a pair consisting of $A\_p$ and $cmd\_1$.
5. $\mathrm{dom}(f)$ returns the domain of the function $f$, that is, the set of values $x$ for which $f(x)$ is defined.

In these rules, $A\_p$ is a *state* object: a function that maps variable names to values. (Think of it a bit like the heap on which you can allocate objects, and where the variable names are pointers.) The VAR rule performs variable lookup in that state:

* *If* the statement above the line is true: $x \in \mathrm{dom}(A\_p)$, that is, the function $A\_p$ is defined for the argument $A\_p(x)$,
* *Then* the statement below the line is true: $A\_p, x \Longrightarrow A\_p(x)$, that is, the expression $x$ in the state $A\_p$ can be evaluated to $A\_p(x)$, which is just the value of the function $A\_p$ when you pass in the variable name $x$ as argument.

Hope that helps. For more details, lecture notes on operational semantics (e.g. these from Cambridge) will further explain the notation.

# Answer
> 4 votes
The expressions are in the general form of sequents, which are a way of writing down proofs. A rule of the form

$$\frac{\ X\ }{Y}$$

means that, if you can prove that $X$ is true, then you've proven that $Y$ is true. A word written to the left or right of the rule is just that rule's name. As such, proofs are read from the bottom. It's also possible to have multiple statements on the top line, as in $$\frac{\ X\_1\quad X\_2\ }{Y}\\,.$$ This means that proving both $X\_1$ and $X\_2$ proves $Y$. The meaning is the same as $$\frac{\ X\_1\land X\_2\ }{Y}$$ but the point is that, in a full proof, you'll need to supply separate proofs of $X\_1$ and $X\_2$: $$\frac{\ \frac{\ \vdots\ }{X\_1}\quad \frac{\ \vdots\ }{X\_2}\ }{Y}\\,.$$ Written out in a little more detail, you might have $$\frac{\ \frac{\ \vdots\ }{X\_1}\quad \frac{\ \vdots\ }{X\_2}\ }{\frac{\ X\_1\land X\_2\ }{Y}}\\,,$$ which means the following. I have some proof of $X\_1$ (which is just written as dots) and some proof of $X\_2$ (ditto). This allows me to conclude that $X\_1\land X\_2$ is true and, from that, I can conclude $Y$. I think that covers your questions 1, 2 and half of 4. Your remaining questions are about the specific logic used in the paper, and I'll leave that to somebody with domain expertise.

# Answer
> 1 votes
Sorry for my inability to recall a better resource, plus I did not want to write out a textbook.

Here is a book which I learned the concept from using a hard copy of: Introduction to Bisimulation and Coinduction by Davide Sangiorgi

Luckily, I found a lecture slide which is based on that book. Take a look starting from page 56 titled "Mathematical induction".

---
Tags: notation
---


title: How do you get a regex from this DFA?

text:
# Question
Title: How do you get a regex from this DFA?
I've been trying for hours. I'm teaching myself automata theory right now and I have this DFA:

And I'm trying to create a regex from it by removing q1 first and then q2. I already managed to remove q1 by doing it like this:

But now I'm not sure how to continue. The next step I'm trying to do is remove q2 and then read the regex from it. Even after trying to wrap my head around it for a long time I didn't really get it. Hopefully someone here can help me :)

# Answer
By reading a 0, your DFA switches its state from right to left, By reading a 1, it switches state from up to down. So to reach your final state $q\_3$ your DFA has to read an odd number of 1's and an even number of 0's. Therefore your language is $L=\\{w \in \\{0,1\\}^\*| |w|\_1 mod 2 = 1, |w|\_0 mod 2 = 0 \\}$
> 0 votes

---
Tags: formal-languages, automata, finite-automata, regular-expressions
---


title: Typing by value

text:
# Question
Title: Typing by value
I wondered if there was a generalized name for typing a variable by assigning a specific value to it. For instance

```
  a = 4

```

This would make the variable `a` an integer, since 4 is an integer. Likewise

```
  b = 0.8

```

is `b` a float in this instance.

Technically this is not dynamic typing (since there is only one defined type, it is just written as the value), but then how is this form called?

# Answer
> 4 votes
Determining the type of a variable from the type of the value that is assigned to it is a form of **type inference**.

In dynamically typed languages, variables usually don't have types, only values have types. In statically typed languages, variables do have types. Most modern statically typed general purpose languages have a form of type inference that can at least infer the type of a variable from the type of what is assigned to it.

Type inference can infer types in other circumstances. The power of type inference depends on the language: full type inference limits the expressive power of the language, as there are many useful typed languages where full type inference is undecidable, but type verification is easy. Different languages make different compromises on automatic inference vs expressiveness.

---
Tags: programming-languages, typing, type-inference
---


# Question
Title: DPDA - a language that contains the same number of A and B
I need help with creating Deterministic pushdown automaton for language: L = {v1w | v, w ∈ {a, b, c}\*, #a(v) = #c(w)} where the number "a" in the string v is the same as "c" in the w string.

In the first state, I try to load the first string v. But I do not know how to control the same number of "a" and "c" characters.

Thanks for help

# Answer
Your language:

```
L = {v1w | v, w in {a, b, c}* and #a(v) = #c(w)}

```

The first thing to notice is that `b`s and `c`s in the first part of the string can be ignored, whereas `a`s and `b`s in the second part of the string can be ignored. In the first part of the string, push onto the stack; and in the second part of the string, pop off. You know you've moved from the first part of the string to the second when you read a `1`. Reject if you (a) run out of stack before you're done seeing `c`s in the second part of the string or (b) if you still have stuff on the stack when you're done reading the second part of the string. If you run out of input with an empty stack, accept. Something like this:

```
Q    s    S    |    Q'    S'
---------------+---------------
// first part of the string
---------------+---------------
q0   a    Z/a  |    q0    aZ/aa
q0   b    Z/a  |    q0    Z/a
q0   c    Z/a  |    q0    Z/a
---------------+---------------
// transition to 2nd part
---------------+---------------
q0   1    Z/a  |    q1    Z/a
---------------+---------------
// second part of the string
---------------+---------------
q1   a    Z/a  |    q1    Z/a
q1   b    Z/a  |    q1    Z/a
q1   c    a    |    q1    -

```

We can define acceptance to be by empty stack in state `q1`. If you want a separate accepting state you can add a new one and an empty transition for that purpose, although that results in a non-deterministic PDA. We can get a DPDA with a separate accepting state if we really want to as follows:

1. read `b`s and `c`s in a loop on the initial state (accepting).
2. if you read an `a`, go to state `A`. In state `A`, read `b`s and `c`s in a loop, and if you read `a`s, push `a`s onto the stack.
3. from the initial, upon seeing `1`, go to state `E`, which is accepting, and loop on `b`s and `c`s. Crash on an `a`, or transition to a dead state.
4. from `A`, upon seeing `1`, go to state `C` read `a`s and `b`s in a loop, and if you read `c` with an `a` on the stack, pop the `a`. If you read a `c` with `Z` on top of the stack, transition to `B`.
5. state `B` loops to itself on `a` and `b` and crashes, or transitions to a dead state, on `c`.
> 3 votes

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


# Question
Title: Why Can't Reverse Hashing Prove $P \neq NP$?
Lets assume a hashing algorithm that runs in polynomial time and produces a hash that is mathematically impossible to reverse. As far as I know, the $P=NP$ problem states that if they are indeed equal, then if an algorithm exists to verify a solution in polynomial time, then an algorithm exists to find a solution in polynomial time. In this case, we can verify a solution by just running it through the hashing algorithm and comparing the final results. However, there cannot exist an algorithm to find a solution, since the hash is impossible to reverse.

# Answer
> Give a polynomial time hash function that takes exponential time to compute the inverse of.

That’s an open problem. It can’t currently be used to resolve $P$ vs $NP$ because no one knows if there is an example of such a function. In CS, we often assume that $P\neq NP$ and that there are cryptographically secure hashes, but that’s an (experienced based) assumption, not a probable fact.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Solving recurrence relation having square root
T(n) = 2T(√n) + n.

---

I tried putting n=2^m

T(2^m) = 2T(2^(m/2)) + 2^m.

If I subsitute T(2^m) = S(m) then,

S(m) = 2S(m/2) + 2^m.

This is same as (1\*2^m) + (2\*2^(m/2)) + (4\*2^(m/4)) + ...

Now I am stuck in this summation as it's not a GP.

Can someone please help?

# Answer
The solution is $T(n) = \Theta(n)$. It is easy to see that $T(n) = \Omega(n)$ (indeed, $T(n) \geq n$), and you can prove $T(n) = O(n)$ by induction: choose some constant $C\>0$. Suppose that you have shown that all small enough $n$ satisfy $T(n) \leq Cn$. Then for larger $n$, $$ T(n) \leq 2T(\sqrt{n}) + n \leq 2C\sqrt{n} + n = \left(\frac{2C}{\sqrt{n}} + 1\right)n. $$ This is at most $Cn$ if $2C/\sqrt{n}+1 \leq C$, and in particular if $n \geq 16$ and $C \geq 1$. Therefore if we define $C = \max(1,T(1)/1,\ldots,T(15)/15)$ then the argument above shows that $T(n) \leq Cn$.
> 2 votes

---
Tags: recurrence-relation
---


# Question
Title: Why do we use RSA if it is not secure against chosen ciphertext attack?
I am reading RSA cryptosystem from Farouzan book on network security. The author has mentioned that RSA encryption is prone to chosen ciphertext attack. Then why is this algorithm still so popular?

# Answer
The exact quote from the book is

> The basic RSA algorithm is vulnerable to a Chosen Ciphertext Attack (CCA)

So the answer to your question is that we don't use the "basic RSA algorithm" in practice. The basic RSA algorithm is also sometimes referred to as textbook RSA. Textbook RSA is malleable, which is why it is vulnerable to a chosen ciphertext attack. The attack works like this.

Eve has a ciphertext $c$ that she wants to learn the corresponding plaintext $m$ for. She has access to a decryption oracle that will decrypt any $c'\neq c$. So, she chooses a random value $r\<n$ and computes $c'=c\cdot r^e\bmod{n}$. Note that since $c=m^e\bmod{n}$, we have $c'=(mr)^e\bmod{n}$ and $c'\neq c$.

Eve submits $c'$ to the decryption oracle, which returns $mr$. Eve now divides this by $r$ to recover $m$.

In practice, no one should use textbook RSA. To thwart this particular attack, we use padding. This removes the malleable property of RSA.
> 4 votes

---
Tags: encryption
---


title: Common parse tree for several formulas

text:
# Question
Title: Common parse tree for several formulas
I have a large (~1k) number of boolean formulas like:

```
f1(x) = p1 AND p2
f2(x) = (p1 AND p2) OR p3
f3(x) = p4 OR !p5

```

The argument x is a set, and the predicates (the p's) assert that a certain condition is met on the set (typically, that x contains a certain value).

For every input, I have to evaluate all the formulas.

As an example, given a chair, f1 would say: the chair is red and the chair has a head rest, f2 would say f1 OR the chair was built before 1980 and so forth.

Some predicates invalidate the formulas statistically sooner than others in my data set; one of them would be, for example, the chair was built before 1900 (not many very old chairs are found).

If I scan all the formulas, find the pieces of them that are equal, like in this example, the first part of f1 and f2, is there a way to build a common parse tree that lets me use this information to make evaluating all the formulas faster?

# Answer
> 1 votes
This is the circuit minimization / logic optimization problem. You have a circuit with some number of inputs (one per predicate `p1`, .., `pn`; or based on the representation of `x`) and ~ 1k outputs (one per formula `f1`, .., `fm`). Now the goal is to construct another equivalent circuit that computes the same output, as efficiently as possible. That's a circuit minimization problem. The problem is hard in general, but there are some heuristics and tools that may be effective in many situations (e.g., Espresso, Quine-McClusky, BDDs, and more). I suggest reading about that subject and trying out one of those tools or techniques.

---
Tags: trees, boolean-algebra
---


title: Digital Image Processing

text:
# Question
Title: Digital Image Processing
I'm a Computer Science Graduate but I didn't study digital image processing during my college years. Now I'm thinking of learning it, but I'm little bit confused about where to start.

Is there any short series of undergrad-level lectures that I can follow, combined with any hands-on mini project (like processing and identifying nudity in an image), so that I can apply my learning?

# Answer
I found these lectures from Tufts University. I read some of the slides where the basics are explained and how to use MatLab to apply them. I think they are easy to follow.

Even if you don't have MatLab, you can learn pretty much from them and use other tools to do your projects.

Here are some of the topics you can find on the slides:

* Images representation
* Image file formats
* Basics of MatLab (focused on images)
* Image enhancement
* Region processing and convolution
* Edge filtering
* Image segmentation
* Geometric transformations

The link: EN 74-ECE: Processing and Analysis of Multidimensional Signals Fall 2007
> 1 votes

# Answer
Check this course from Northwestern University :

Fundamentals of Digital Image and Video Processing.

The link to view the contents: https://www.coursera.org/learn/digital
> 0 votes

---
Tags: education, image-processing
---


# Question
Title: Mathematical proofs implemented purely by Lambda Calculus
I've seen often stated that Lambda Calculus can be used for mathematical proofing but I haven't yet seen any example how it is actually used for the task.

Is there a simple example, lambda abstraction or application that can be shown to be a valid mathematical proof? For example what does it take to make a Church numeral successor function regarded as a mathematical proof?

# Answer
> 6 votes
So, the trick is that the untyped lambda calculus is not very useful as a mathematical proof, since it has non-halting terms.

Lambda Calculus as a proof system is most useful with types, particularly in terms of the Curry-Howard Isomorphism. Phillip Wadler has a great article outlining this.

The basic idea is that lambda abstraction corresponds to the way that you prove an implication. To write a function of type $A \to B$, you assume you have a value of type $A$, and use it to construct a return value of type $B$. This is exactly how you prove $A \implies B$: assume that $A$ holds, then use this to prove $B$.

Not every lambda term corresponds to a mathematical proof in the sense we're used to, although each term can be regarded as a proof that its type is inhabited. In particular, to prove anything really useful, you need dependent types, where types are allowed to be indexed by values.

For Church-Numerals, their typed version if $\forall a \ldotp a \to (a \to a) \to a$, which, when interpreted as a proposition, is really boring. It's saying that if something holds, and it implies itself, then that something still holds.

For more information on the various type systems for Lambda Calculi, I'd start with the Lambda Cube.

---
Tags: proof-techniques, lambda-calculus, mathematical-foundations
---


# Question
Title: Is there an algorithim to construct a graph with an even number of vertices, and each vertex has k edges?
Ideally, such an algorithm would not be a brute force one. Is there a clever way to do this?

# Answer
> 2 votes
The complete bipartite graph $K\_{k,k}$ has $2k$ vertices, each of which has degree $k$.

# Answer
> 1 votes
If $k$ is odd, take the complete graph on $k+1$ vertices. If $k$ is even, take the complete graph on $k+2$ vertices numbered $1,\ldots,k+2$, and disconnect the $k/2+1$ edges $(1,2),(3,4),\ldots,(k+1,k+2)$.

It is not hard to check that these graphs have the minimal number of vertices, and are moreover unique (up to isomorphism) for this property.

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


# Question
Title: Understanding Wirth's symbol table entry
N.Wirth's book on compiler introduces the concept of symbol table and states that every declaration statement results in a new entry in symbol table.

Then after showing how an entry in symbol table looks like he talks about types which can be specified anonymously like the following :

$\ VAR a: ARRAY 10 OF INTEGER $

Then it is written that named types are represented in the symbol table entry by an entry of type object -----(1)

which in turn refers to an object of type "Type" and provides the following snippet :

$\ Type = POINTER TO TypDesc; TypDesc = RECORD form, len: INTEGER; fields: Object; base: Type END $

The book is written in pascal or oberon and I don't understand its syntax but I want to know how to interpret this type desc .

Does whatever follows typedesc , describes the fields of the record ? Form ,length,fields and base being the columns of the record ?

Wirth ,for the following declaration :

TYPE R = RECORD f, g: INTEGER END ; VAR x: INTEGER; a: ARRAY 10 O OF INTEGER; r, s: R;

shows the following symbol table entry :

The picture , I am getting from this is every object will point to its "type" ,.

In case of records , the type will point to the first field . I guess each field is being implemented something like a C structure ,having the pointer to the next field and pointer to its base type as its member . And here in the diagram ,the attribute "next" is pointing to "g" and its attribute "type" is pointing to "integer" .

The above was just an attempt to interpret what the author exactly means by it . Is my understanding correct ?

# Answer
> 1 votes
Pretty much, yes. The list of variable names form a linked list, and the fields within a record are basically a nested symbol table.

---
Tags: compilers
---


# Question
Title: Is it possible to implement dependent types by any object oriented language supporting inheritance and classes?
When I was reading Agda tutorial, I noticed resemblance between dependent type declarations and class definitions which I've been primarily used to work with. I'm not totally sure how much sense this questions makes, but what is the real practical difference between types and classes? Could we very well use object oriented approach to define types, and thus construct proofing system similar to Agda by any language supporting class and object construction?

# Answer
So, things like this are possible, but the usefulness varies depending on your system.

First, you can absolutely model object oriented programming in a functional, formal setting. System F-sub is the classic example of this, but Scala Dependent Object Types are another model.

Secondly, let's talk about the difference between types and classes, without dependent types. A class is essentially just a type, combined with a bunch of methods that operate on that type. Classes can be modeled with recursive record types in some languages. The algebraic data types you see in languages like Haskell and Agda are kind of like regrouped classes. An interface groups functions together, and the type specific implementation of those functions for specific classes are spread out. Conversely, algebraic data types group all the variants of a type together, but the different functions are spread out, with each function specifying how it is implemented for each type.

Finally, how do dependent types play into all this? Well, Agda and other Dependent Type languages have a particular feature, namely that types can be indexed by values, and that types are themselves values. Computation can happen not just in expressions, but in types.

Java, Haskell, and every other mainstream language are weaker than this, since their types can't be indexed by arbitrary values. This is what the dependent in dependent types means, and it's what makes them useful for proving things.

To have dependent object oriented types, you need to overcome a few hurdles. One is, do you have mutation, and how does it affect dependent types? Can types refer to mutable variables, or alter state? How is that possible, when type computation happens at compile time, not runtime?

And then you need to decide whether you want to prove actual theorems in your language. Most OO languages are Turing Complete, meaning that the would be inconsistent if interpreted as a logic. This doesn't mean that Dependent types are useless, you can still enforce sophisticated program invariants using them. But Agda and the others feature termination checkers that make them Turing Incomplete.
> 4 votes

---
Tags: dependent-types, object-oriented, proof-assistants
---


# Question
Title: Array with queries to decrement or find sum of range
I have been given an array of integers of ***size n*** and ***q queries*** which can be of 2 types:
1.Decrement all elements in the given range by some value
2.Find sum of all elements in the given range
***1\<=n,q\<=10^5***
I have tried brute force but it gives TLE
Same goes for prefix sum and even segment trees which improve sum query but slow down updation
I cannot figure out how to update in O(log n)
Would lazy propagation help ?
If not , how else can i proceed with this?
P.S. First timer here . Apologies if i missed out on something

# Answer
Suppose that your array is $a\_1,\ldots,a\_n$, but instead of storing it this way, you store the differences $\delta\_i = a\_i - a\_{i-1}$ (where $a\_0 = 0$). Decrementing $a\_i,\ldots,a\_j$ by $x$ is then the same as decrementing $\delta\_i$ by $x$ and incrementing $\delta\_{j+1}$ by $x$. Querying the prefix sum $a\_1 + \cdots + a\_j$ (using which you can query the sum of any range) amounts to calculating $$ \sum\_{t=1}^j \sum\_{k=1}^t \delta\_k = \sum\_{k=1}^j \sum\_{t=k}^j \delta\_k = \sum\_{k=1}^j (j-k+1)\delta\_k = (j+1)\sum\_{k=1}^j \delta\_k - \sum\_{k=1}^j k\delta\_k. $$ The idea now is to use a Fenwick tree, which is an array data structure which can perform both element updates and prefix sums in $O(\log n)$. We use two Fenwick trees, one storing $\delta\_1,\ldots,\delta\_n$ and the other storing $\delta\_1,2\delta\_2,\ldots,n\delta\_n$ (we can in fact merge them into a single Fenwick tree which stores information for both values at every node). Above we have outlined how to perform each of your two queries in $O(\log n)$.
> 2 votes

---
Tags: algorithms, complexity-theory, time-complexity, arrays
---


# Question
Title: Recognizability of machines which halt in $n$ steps on some input
We define the following language:

$$L = \\{M \mid \text{$M$ is a TM and there exists an input $x$ on which $M$ halts in at most $|x|$ steps}\\}.$$

Following this question I understand that $L$ is not decidable, but I know that it is recognizable, and therefore I'm looking for a reduction from the HALTING problem to $L$.

I thought of the following reduction:

On input $M$ for $L$, create a Turing machine $M'$ that for input $y$ for the HALTING problem runs $M$.

If $M$ halts, then $M'$ halts too, but I'm having problems proving the reduction.

Another way of proving this problem in my opinion is by building an $M'$ that recognizes the language by running $M$ all inputs for their length.

If $M'$ halts on some input it accepts, otherwise it keeps going.

Does this solution work?

# Answer
> 0 votes
This could be proven without reduction. The proof is straightforward: given $M$ run through all strings, say over $0$ and $1$, in canonical order and for each string $x$ simulate $M(x)$ for $|x|$ steps and check if it halts. If there is such $x$, then you will eventually find this $x$ and so accept $x$.

---
Tags: undecidability
---


# Question
Title: Relation between $\sqrt{x^2+y^2}$ and $|x|+|y|$
I have a problem in which I was given $n$ points and an integer $k$, and I need to find the $k$ points that are the closest to origin. My approach is to find the distances from origin of all points and sort them. Instead of using distances $\sqrt{x^2+y^2}$, can I use $|x|+|y|$ as my key? Also, I would like to find out the complexity for both approaches.

# Answer
The two notions of distance are not equivalent. That is, you can find a pair of points $p,q$ such that $p$ is closer to the origin with respect to the distance $\sqrt{x^2+y^2}$ (known as $L\_2$), and $q$ with respect to the distance $|x|+|y|$ (known as $L\_1$). An example is $p=(2,2)$ and $q=(3,0)$. However, you can simplify your task by considering $x^2+y^2$ instead of $\sqrt{x^2+y^2}$.

There is no need to sort the distances. Instead, you can use a comparison-based linear time selection algorithm.
> 3 votes

---
Tags: time-complexity, discrete-mathematics
---


# Question
Title: Computational Complexity and P vs. NP, A New Insight
There is a preprint on arXiv that states (in my own words).

If there are three numbers (digits) and task is to add all three numbers. First we well take two number to add, set aside third number. Then we will add third number in previous sum of two numbers. So, addition of three number requires two steps, **because we cannot interact and manipulate more than two numbers in single instant**. Our limitation to interact with only two number in single step has played very important role. This is one of reasons why Math axioms involve only two number e.g a.0=0, b.1=b etc…Similarly we cannot sort more than two numbers in single step. If there is a system that can sort three objects in single step it will be 200% more time efficient. The kind of sorting that involves three numbers in single step is not possible by humans or man-made machines (not even Turing machines ). But one such system is explained in the paper along with consequences.

The paper concludes

**“It can be stated explicitly that computational complexity appears because of Mathematical Axioms that are constrained by and based on human cognitive limits as human cannot interact with more than two numbers at an instant”**

Is above statement right?

Preprint Link https://arxiv.org/abs/1711.10874

# Answer
> 3 votes
Who says we cannot add three numbers in a single step? We can, and if we use the fastest known methods to add integers, adding three numbers only takes a little bit longer than adding two numbers, not twice as long.

Most modern processors have instructions adding three numbers, for example the LEA (Load Effective Address) instruction on processors based on the Intel architectures.

# Answer
> 5 votes
No. The paper appears to be total baloney. I noticed multiple unjustified statements in my first 60 seconds reading the paper. Don't waste your time with it.

arxiv is not peer-reviewed. Some papers on arxiv are great; some papers are arxiv are terrible and a waste of time. Its presence on arxiv says very little about its quality. It's like finding a paper on someone's personal website.

---
Tags: complexity-theory, turing-machines, np-complete, proof-techniques, p-vs-np
---


# Question
Title: What does it mean to be "closed" under beta reduction?
I am reading the paper *Compiling with Continuations, Continued*, and in section 2.4, *Comparison with ANF*, the author draws attention to the fact that ANF is not closed under beta reduction. The snippet of text in question follows:

> As Flanagan et al. (1993) suggest, the “back end of an A-normal form compiler can employ the same code generation techniques that a CPS compiler uses”. However, as we mentioned in the Introduction, it is not so apparent whether ANF is ideally suited to optimization. After all, it is not even closed under the usual rule for β reduction (λx.A) v → A\[v/x\].

What does the author mean by this last sentence? (My guess is that he means ANF beta reduction can introduce new, unbound variables into the reduced term. If that is the case, I am having a hard time visualizing when this would occur and would appreciate outside confirmation that my interpretation is correct.)

# Answer
> 6 votes
The claim is that after applying β-reduction to an expression in A-normal form you can be left with an expression no longer in A-normal form.

The only explicit definition I can find of A-normal form is not consistent with the definition Kennedy seems to be (implicitly) using in this paper. Wikipedia defines *A-normal form* as the subset of lambda calculus expressions where only constants, $\lambda$-terms, and variables can be arguments of function applications, and then (vaguely) says that results of non-trivial expressions must be captured by let-bound variables.

That is: `f(g(x))` is *not* in A-normal form because the argument to the application of `f` is another application (`g(x)`) rather than a constant, $\lambda$-term, or variable. This expression in A-normal form would be something like `let y=g(x) in f(y)`.

Kennedy uses the vague "definition"

> a let construct assigns names to every intermediate computation. (Section 1.1.ANF).

But then in Section 1.2 he gives an example of an A-normal form not being preserved under β-reduction

> Consider the ANF term `let x = (λy.let z = a b in c) d in e`. Now naïve β-reduction produces `let x = (let z = a b in c) in e` which is not in normal form. The ‘fix’ is to define a more complex notion of β-reduction that re-normalizes let constructs (Sabry and Wadler 1997), in this case producing the normal form `let z = a b in (let x = c in e)`.

So apparently Kennedy's variant of A-normal form places some kind of restriction on what can be in the assignment part of a `let` clause, but I can't figure out what (or why) that restriction is. In addition to Kennedy's paper you linked, I looked in several of his references:

> Amr Sabry; Philip Wadler: A reflection on call-by-value. *ACM T. Prog. Lang. and Sys. (TOPLAS)*, 19(6):916-941, 1997.
>
> Amr Sabry; Matthias Felleisen: Reasoning about Programs in Continuation-Passing Style. *Lisp and Symbolic Computation* 6(3-4):289-360, 1993.
>
> Flanagan, Cormac; Sabry, Amr; Duba, Bruce F.; Felleisen, Matthias: The Essence of Compiling with Continuations. *Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation*, (PLDI):237-247, 1993.

# Answer
> 1 votes
A set $S$ is closed under an operation $f$ if, whenever $x\in S$, $f(x)\in S$ also.

# Answer
> 0 votes
An example:

```
(let (x (f v))
   (g x))

```

is in ANF. But beta reduction of the x would yield

```
(g (f v))

```

which is not.

---
Tags: compilers, lambda-calculus, continuations
---


title: Query regarding Integer factorization

text:
# Question
Title: Query regarding Integer factorization
Let us consider a product $P$ (whose factors we do not know). Given a base $b$, such that all the Modulus Residues are calculated using powers of $b$ w.r.t. $P$.

For some (unknown) power $x$ we know the corresponding residue ($R\_x$), i.e.:

$b^x\bmod P = R\_x$.

Query 1: Without knowing (or calculating) the factorization of $P$ and value $x$, for a given $k$, (using $R\_x$) is it possible to calculate $b^{(x-k)}\bmod P = R\_{(x-k)}$ efficiently?

Query 2: Can the above procedure (if known/exists) help in factorization of $P$?

I am uncertain about how to achieve 1 and its relation to factorization if any.

# Answer
You can calculate $b^k \bmod P$ efficiently for $k \geq 0$ using repeated squaring. There is no need to know the factorization of $P$. Furthermore, you can calculate $b^{-1} \bmod P$ (if it exists) efficiently using the Euclidean algorithm. This also doesn't require the factorization of $P$.
> 1 votes

# Answer
Yes, given $b^k$ you can compute $b^{x-k}$ by $b^x = b^x \times b^{-k}$. Yuval Filmus explains how to compute $b^{-k}$.

No, this doesn't appear to lead to a better algorithm for factoring $P$.
> 1 votes

---
Tags: algorithms, factoring
---


# Question
Title: Filling a 3x3 board with connected tiles
long story short: I want to list all possible combinations of n tiles on a 3x3 board with the restriction that at least 6 tiles are part of a connected chain. Tiles are connected if the pattern continues from one to the other and a tile can be repeated any number of times (see image below for clarification, I would like to increase the number of available tiles at one point).

You can see some of my thoughts below, I would like to know if there's a more elegant solution to this problem or (if I'm on the right track) some ideas on optimizations and data structures that I would need to actually implement this.

It seems to me there are three separate problems:

1. I need to map out all connected graphs with 6 vertices
2. Try all the combinations of tiles that fit on those vertices
3. List item

Since I actually need to print all the solutions I was thinking that there's no way of avoiding backtracking, so all my ideas so far are basically optimizations of the process. The biggest time save so far is the fact that once you have a valid configuration you can also print out its rotations (see picture below), thus cutting the search time to a quarter, but the catch is i don't know how to deal with duplicate solutions :/

There's also the observation that since I need to have a minimum of six connected tiles, one of them will surely be in a corner (upper left corners seems like the logical place to start) so all the connected graphs would have to start out in that corner.

That's about everything I have right now, thank you for reading and any help is highly appreciated.

# Answer
> 1 votes
There are only $9^9$ possible ways to fill each cell with one of the 9 tiles. That's a bit under 400 million possibilities. So, I suggest a simple approach: enumerate all of them, and for each, check whether or not it meets your conditions. That should run pretty fast: you should be able to very quickly test a candidate configuration to see if it satisfies your requirements, and then a computer should be able to do that 400 million times pretty rapidly. Repeatedly doing some tedious task is what computers are really good at.

You could also use backtracking or other more sophisticated methods to reduce the number of configurations you need to examine, but it might not be worthwhile to implement. You might spend 10 hours programming to save 1 hour of CPU time -- might not be worth it. I suggest you try the simple, dumb, brute-force search first, before thinking too hard about more sophisticated algorithms.

---
Tags: graphs, optimization, backtracking, tiling
---


# Question
Title: rebalance red-black tree with many violations
Every red-black tree implementation I've come across use a strategy that considers re-balancing the tree after each mutation (e.g. insert, delete, ...).

I have a situation where I graft several sub-trees from one red-black tree onto another. After these grafts I would like to consider re-balancing the resulting tree.

Are there any approaches to doing this, either applying existing techniques in a brute force manner, or strategies that would make it efficient. It isn't entirely clear that existing algorithms can be naively applied.

# Answer
In general, I would say that the algorithm you want is a tree *union* (also called a *merge*), which takes two trees and combines them so that the new tree contains the union of the keys of both inputs. You can read a brief description on Wikipedia, or a more in-depth description (which generalizes to other balancing schemes such as AVL, BB\[α\], Treap) in a recent paper.

**However**, it seems that your use-case is slightly more specific than a tree union. In particular, I'm guessing that the subtrees you are grafting onto the existing tree don't violate the ordering property of the BST. In this case the algorithm you want is even simpler than a tree union, and is much closer to a simple insertion:

```
// graft B onto T
function graft(T, B):
  let (L, R) = split T at B.root.key
  return join(L, join(B, R))

```

This algorithm is inspired by the union algorithm but does not need to recurse, because of the nice properties of the input. It uses two functions which I've summarized below; you can find them described in more detail in the links I provided above.

1. `split` cuts a tree at a specific key k, producing two trees L and R where all keys in L are less than k, and all keys in R are greater than k.
2. `join` takes two trees (L, R) where all keys in L are smaller than all keys in R and combines them into a single tree.

Both `split` and `join` have logarithmic time complexity. **Because of this, `graft` only takes logarithmic time**. If you have a small number of branches to graft, then simply iteratively applying `graft` should be fastest. However if you have a large number of branches to graft, it may be faster to first combine them into a single tree and then merge this tree with the original.
> 2 votes

---
Tags: binary-trees, balanced-search-trees
---


# Question
Title: In describing the tokens of a programming language using RE, it is not necessary to have the $\epsilon$ or t. Why is this?
In describing the tokens of a programming language using regular expressions, it is not necessary to have the $\epsilon$, (for the empty set) or t (for the empty string). Why is this?

Please tell me why is it not necessary thanks

# Answer
> 3 votes
The empty set is only needed in order to describe the empty regular language. The set of tokens of a certain type is never empty, so the empty set isn't needed.

Similarly, the empty string is only needed to describe regular languages which include the empty string. The empty string isn't a token of any type, so the empty string isn't needed.

---

Here are some proofs. I will use the convention in which $\emptyset$ is the emptyset and $\epsilon$ is the empty string. I will use the following inductive definition of regular expressions over an alphabet $\Sigma$:

* $\emptyset$ is a regular expression.
* $\epsilon$ is a regular expression.
* For any $\sigma \in \Sigma$, $\sigma$ is a regular expression.
* If $r$ is a regular expression then $r^\*$ is a regular expression.
* If $r\_1,r\_2$ are regular expressions then $r\_1+r\_2$ is a regular expression.
* If $r\_1,r\_2$ are regular expressions then $r\_1r\_2$ is a regular expression.

Two regular expressions are *equivalent* if they generate the same language. We denote this by $\approx$. The language generated by $r$ is denoted $L\[r\]$.

**Lemma 1.** Every regular expression is either equivalent to $\emptyset$ or to a regular expression without $\emptyset$.

**Corollary 1.** If a regular expression doesn't generate the empty language, then it is equivalent to a regular expression without $\emptyset$.

Note that every regular expression not involving $\emptyset$ doesn't generate the empty language.

**Proof.** The proof is by structural induction. The base cases $\emptyset,\epsilon,\sigma$ are obvious. Consider now a regular expression $r$ constructed inductively from one or two regular expressions $r\_1,r\_2$, which we can assume satisfy the dichotomy in the lemma. If $r\_1,r\_2 \neq \emptyset$ then there is nothing to prove, so assume that at least one of them is $\emptyset$.

* $r = r\_1^\*$: in that case $r = \emptyset^\* \approx \epsilon$.
* $r = r\_1 + r\_2$: if $r\_1=r\_2=\emptyset$ then $r \approx \emptyset$. If $r\_1 \neq \emptyset$ and $r\_2 = \emptyset$ then $r \approx r\_1$.
* $r = r\_1r\_2$: in that case $r \approx \emptyset$. $\qquad\square$

**Lemma 2.** Every $\emptyset$-free regular expression can be written in one of the forms $\epsilon,s,s+\epsilon$, where $s$ is $\emptyset,\epsilon$-free and $\epsilon \notin L\[s\]$.

**Corollary 2.** If $\epsilon \notin L\[r\]$ and $L\[r\] \neq \emptyset$ then $r$ is equivalent to a regular expression not involving $\emptyset,\epsilon$.

**Proof.** Again the proof is by structural induction. The base cases $\epsilon,\sigma$ are obvious. Let us now consider a regular expression $r$ constructed inductively from $r\_1,r\_2$ which are of one of the forms $s\_i,s\_i+\epsilon,\epsilon$, where the $s\_i$ satisfy the conditions stated in the lemma.

* $r = r\_1^\*$: If $r\_1 = \epsilon$ then $r \approx \epsilon$. If $r\_1 = s\_1 + \epsilon$ or $r\_1 = s\_1$ then $r \approx s\_1s\_1^\* + \epsilon$.
* $r = r\_1 + r\_2$: If $r\_1=r\_2=\epsilon$ then $r \approx \epsilon$. If $r\_1=s\_1$ and $r\_2 = s\_2$ then $r$ is already of the required form. Otherwise $r \approx (s\_1+s\_2) + \epsilon$.
* $r = r\_1r\_2$: If $r\_1=r\_2=\epsilon$ then $r \approx \epsilon$. If $r\_1=s\_1$, $r\_2=s\_2$ then $r$ is already of the required form. If $r\_1=s\_1$ and $r\_2=s\_2+\epsilon$ then $r \approx s\_1s\_2 + s\_1$. Similarly, if $r\_1=s\_1+\epsilon$ and $r\_2=s\_2$ then $r \approx s\_1s\_2 + s\_2$. Finally, if $r\_1=s\_1+\epsilon$ and $r\_2=s\_2+\epsilon$ then $r \approx (s\_1s\_2 + s\_1 + s\_2) + \epsilon$. $\qquad\square$

---
Tags: compilers
---


# Question
Title: DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?
https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php

The second question in the above link requires us to fill an 2xN grid with tiles of dimension 2x1 and an L shaped tile.

**Question 1)** In the recursive formula for `g(n)`:

`g(n) = f(n-1) + h(n-1)`

Why didn't we include the case that we can also put a 2x1 tile horizontally on the top row. Something like -

`g(n) = f(n-1) + h(n-1) + x(n-3)`

where `f(n) = f(n-1) + f(n-2) + g(n-2) + h(n-2)` still holds.

Basically, are we not looking into the cases how we can start tiling from the state `g(n)` ? ither we add an L-shaped tile, and look at `f(n-1)`, or we add a 2x1 tile in the bottom layer and look at `h(n-1)`, or add a 2x1 tile in the top layer and look at `x(n-3)` ?

**Question 2)** It seems like while writing the recursion, we should only deal with cases that we have already named, i.e. only moving from state g(n) to h(n-1) or moving from state g(n) to f(n-1) ? Is it true, that when once we have decided which states to deal with, we only consider those states?

# Answer
Q1. Of course you can consider a third variable in the recursion, but that would not simplify the analysis. In fact from the case where you put the single horizontal domino, the next step would automatically put the second horizontal one below it. So the given recursion takes a little shortcut.

Q2. That is precisely the point. We have to make sure the analysis steps from existing state to existing state, in a kind of unique way. If we overlook a state we miss possibilities. But here we easily see how the states are related, and how we step from one to another.
> 1 votes

---
Tags: algorithms, algorithm-analysis, dynamic-programming, recursion, tiling
---


# Question
Title: What is the difference between a 'page' of memory and a 'frame' of memory?
WP has an adequate discussion of *paging*, which I think I understand.. However I am confused by the articles repeated use of the term *Page Frame*.

I thought frames and pages were different things. Could someone please clarify the difference.

# Answer
Short version: "page" means "virtual page" (i.e. a chunk of virtual address space) and "page frame" means "physical page" (i.e. a chunk of physical memory).

That's it, pretty much. It's important to keep the two concepts distinct because at any given time, a page may not be backed by a page frame (it could be a zero-fill page which hasn't been accessed, or paged out to secondary memory), and a page frame may back multiple pages (sometimes in different address spaces, e.g. shared memory or memory-mapped files).
> 47 votes

# Answer
Physical memory is organized into frames and virtual memory into pages. The "page frame" term is a bit confusing and in my opinion wikipedia shouldn't use it. What they really mean by "page frame" is a block/group/segment of physical memory, which is equivalent to a frame. So they should instead use the term "frame", not "page frame".

In short remember:

* page = block of consecutive virtual memory
* frame = block of consecutive physical memory

That is how i use it.
> 6 votes

# Answer
A *page frame* is a storage unit within the main memory, while a *page* is the contents in the frame.
> -2 votes

---
Tags: memory-management
---


# Question
Title: #3-Coloring Problem for Tree with Some Pre-Colored Nodes
I have a undirected tree and three colors to choose from. Some nodes are already colored; these nodes and their colors are given. What is an efficient algorithm to find the number of ways to color the rest of the nodes such that no two adjacent nodes are the same color?

# Answer
> 1 votes
Many problems on trees can be solved using dynamic programming. Let me explain how to solve a similar problem, *independent set with fixed vertices*. In this problem, you are given a tree $T$ and an independent subset $I$ of its nodes, and your task is to count all independent sets which contain $I$.

Arbitrarily root $T$ at some vertex $r \in T$. For every vertex $v \in T$, let $T\_v$ be the subtree of $T$ rooted at $v$. For every $v \in T$, we will calculate two quantities:

* $\alpha\_v$ is the number of independent sets in $T\_v$ containing $T\_v \cap I$ and $v$.
* $\beta\_v$ is the number of independent sets in $T\_v$ containing $T\_v \cap I$ but not containing $v$.

We calculate these quantities recursively, as explained below, and output $\alpha\_r + \beta\_r$, which is the total number of independent sets in $T$ containing $I$.

The base case is when $v$ is a leaf. If $v \in I$ then $\alpha\_v = 1$ and $\beta\_v = 0$, and otherwise $\alpha\_v = \beta\_v = 1$.

Now suppose that $v$ is an internal node, say with children $v\_1,\ldots,v\_m$. If $v \in I$ then $\beta\_v = 0$ and $\alpha\_v = \prod\_{i=1}^m \beta\_{v\_i}$, since an independent set containing $v$ cannot contain any of its children. If $v \notin I$ then it is still the case that $\alpha\_v = \prod\_{i=1}^m \beta\_{v\_i}$, and additionally $\beta\_v = \prod\_{i=1}^m (\alpha\_{v\_i} + \beta\_{v\_i})$, since we don't have any constraints on the $v\_i$.

Now that the algorithm is laid out, you can check that it runs in linear time. Your problem can be solved in a similar fashion, also in linear time.

---
Tags: algorithms, trees, colorings
---


# Question
Title: Towers of Hanoi Algorithm "Using Auxiliary" Peg
I'm trying to fully understand how the recursive Towers of Hanoi Algorithm works and to implement it in code.

Something that keeps throwing me of is the use of phrases like "move n-1 discs from A to B using C."

I understand that the peg which is referred to is as being "used" is the auxiliary or spare peg, but the language seems misleading because if n-1 has a value of more than 1, then more than one peg is used to perform the move. So the phrase "using C" or "using B" or "using A" doesn't seem accurate and is hindering me from thinking clearly about the problem.

Am I missing something, or can I substitute the phrase "with C as the spare/auxiliary peg" for "using C" without loss of meaning?

I've seen one video where for the n=2 problem, the first move is described as "move a disc from A to B using C" - in this case C isn't involved at all!

I wonder if anyone who has managed to fully grasp the algorithm can advise if it would be helpful to adopt the "using A/B/C" language or if there is another alternative that you have found more helpful, such as my suggestion above - "with C as the spare/auxiliary peg"?

# Answer
> 1 votes
In mathematics, the literal meaning of a phrase is of little importance. What is important is that both author and reader know what a phrase means, and this can come about in two ways. Either the phrase is well-known, or the phrase is defined in the article. In your case, the phrase "move $n$ pegs from $A$ to $B$ using $C$" means "call the function Hanoi with parameters $n,A,B,C$" - no more, no less. The author could have chosen a completely different phrase, for example "jump from $A$ to $B$ doing $n$ flips above the midpoint $C$", as long as they make it clear that it means "call the function Hanoi with parameters $n,A,B,C$".

Another point that you raise is that when $n=1$, you can move the disc directly from $A$ to $B$, without involving $C$ at all, which you feel contradicts the phrase "using $C$", since $C$ isn't actually used. However, in mathematics such phrases are usually inclusive rather than exclusive — it is not obligatory to actually use $C$. This highlights the fact that mathematical terms often differ in meaning from their common use. For example, when mathematicians say "$p$ or $q$", they are also allowing the possibility "both $p$ and $q$", although common knowledge precludes it.

---
Tags: recursion
---


# Question
Title: References for the computational complexity of training neural networks
I'm looking for a good review paper or book chapter that offers an accessible introduction to the computational complexity of training neural networks for classification problems.

In particular, I'm trying to study questions like:

1. How is training complexity related to network topology ?
2. How is training complexity related to the complexity of the decision boundary?

# Answer
At present the theory of computational complexity has little useful to say. This is largely an empirical science: to find out how many epochs of training are needed or is optimal, the only way to know for sure is to try it and see. While there is some limited amount of theory, the theory isn't very useful in practice. Ultimately, we don't really understand why deep learning works or how well it works or exactly what conditions are needed for it to work.

Training usually involves a series of epochs. The time for each epoch is proportional to the time to evaluate the network on each of the training set instances, once. There's no theory about the number of epochs needed. However, in many situations the number of epochs is a relatively small number, say, 20-100 -- not always, but fairly often. So, that gives you some idea.

Ultimately, topology doesn't seem to affect training time much except insofar as it affects the time to evaluate the classifier on an instance. It could influence the number of epochs too, but on many networks seen in practice, it doesn't seem to have a large influence for many of the architectures we use in practice. However, this could be a consequence of the fact that we typically select architectures that do perform well with a reasonable amount of training (i.e., the architecture is often selected so a huge number of epochs isn't needed). In any case, this isn't a hard-and-fast rule.

Bottom line: ultimately, we understand very little about the complexity of neural networks, the complexity of training, or rigorous/well-founded/provable answers to your questions.
> 1 votes

---
Tags: complexity-theory, reference-request, neural-networks
---


# Question
Title: Reduction — Do they work for unrelated problems?
I think I understand that a P class problem is reducible to an NP class problem (P≤NP).

I´d like to understand if I need to figure out a potential algorithm which could solve the NP class problem to know if it can be used as a subroutine for a P class problem.

So for example, if I ask you if the problem from class P —sum of integers— is reducible to a problem of class NP —Clique graph problem—, how would you reply to it?

Is this a valid reduction as the more complicated Clique problem is NP and the easier problem sum of integers is a P problem even though they deal with different math branches (one being algebra and the other one being graph theory)?

# Answer
If you have a problem $X$ that is in P, then you can construct a polynomial time reduction to *any* problem $Y$ in NP (or in 'any' other class of problems\*). This is possible, as our 'reduction' is allowed to spend polynomial time on the input of $X$, so it can simply determine whether a given input $I$ for $X$ is a 'yes'-input in polynomial time and map to a trivial input for $Y$ with the same truth-value.

---

\*: To be precise, any decision problem such that we can find at least one 'yes'-instance and one 'no'-instance, which holds for pretty much any interesting decision problem.
> 3 votes

---
Tags: complexity-theory, reductions
---


title: Containment of ACC$^0$ in TC$^0$

text:
# Question
Title: Containment of ACC$^0$ in TC$^0$
The Complexity Zoo states that ACC$^0$ is contained in TC$^0$ and links to the paper On ACC and Threshold Circuits. However, what the linked paper proves is that depth-3 threshold circuits of quasipolynomial size can simulate ACC$^0$ circuits.

Wouldn't it be necessary to prove that constant depth threshold circuits of polynomial size simulate them rather than quasipolynomial? Is it obvious how to do the simulation with just a polynomial number of gates?

# Answer
> 1 votes
You can show directly how to simulate a polynomial fan-in modular gate using polynomially many threshold gates. The idea is that given inputs $x\_1,\ldots,x\_m$, you can use two threshold gates and an AND gate to determine whether $x\_1 + \cdots + x\_m = w$ for any $w$. Taking at most $m+1$ copies of this gadget and ORing them, we can simulate a single modular gate.

---
Tags: complexity-theory, circuits
---


# Question
Title: Pumping-Lemma regular languages: Consider multiple cases?
The language $ L = \\{ a^nb^mc^m : n,m \in \mathbb{N} \\} $ is non regular. Suppose this needs to be proven using the pumping lemma for regular languages:
Be $ z = ab^nc^n $ such that $ z=uvw, |v| \geq 1, |uv| \leq n $.
Obviously $uv^2w \notin L $ with $ v=b^{k}$ and $ 1 \leq k \leq n-1$.
Is this proof finished now? Or do I need to consider $ v=ab^{n-1} $ as well?
More general: Using the pumping lemma for regular languages, do i need to consider all possible combinations for $uv$?

# Answer
> 2 votes
Of course, you have to consider all possible cases. Otherwise you do not prove that "there exists a factorization" is false. So you actually have to consider all $ab^k$ with $k \< n$. Here you get some prefix $ab\cdots bab\cdots b$ and therefore the words are outside tha language. Or you chose a different word $z$ if $n=0$ is allowed, which depends on your definition of the natural numbers - then you only have one case.

For the case you treat, probably stating that $uv^2w = ab^{n+k}c^n$ would be more complete than saying "obviously."

---
Tags: regular-languages, pumping-lemma
---


title: Is the set of real numbers a language?

text:
# Question
Title: Is the set of real numbers a language?
Is the set of real numbers a language?

My idea is that the set of real numbers can't be a language because it is uncountable. Every language must be countable.

Is there any other way to solve this problem?

# Answer
The definition of a language, from *Hopcroft-Ullman Introduction to Automata and Language Theory*, is :

> A set of strings all of which are chosen from some $\Sigma^\*$, where $\Sigma$ is a particular alphabet, is called a *language*.

And from the same book, the definition of a string is :

> A string (or sometimes *word*) is a finite sequence of symbols chosen from some alphabet.

So strings must be finite. If we represent real numbers by sequences of digits, those sequences would be infinite in length, so that representation won't give us the language of real numbers.

But can we use another representation ? For example, even though we have rationnal numbers with an infinite sequence of digits, we can consider them as a language thanks to fractional representation.

Suppose that the set of real numbers were a language. Let's call that language $L$, and $\Sigma$ its alphabet. $L$ is a subset of $\Sigma^\*$, thus $L$ is countable because $\Sigma^\*$ is countable. We conclude that the set of real numbers can't be a language because it's an uncountable set.

*NOTE :* We can explicitly define an injection from $\Sigma^\*$ to natural numbers. First, associate for every letter of $\Sigma$ a unique integer, call it $int(a)$. Let $\sigma$ be that bijection, here is its definition :

$$\left \\{ \begin{array}{r c l} \sigma(\epsilon) &=& 0 \\ \sigma(\omega) &=& \prod\_{i=1}^{|\omega|} \pi(i)^{int(\omega\_i)} &;& \omega \neq \epsilon \end{array} \right .$$

Where $\pi(i)$ is the $i^{th}$ prime number and $\omega\_i$ the $i^{th}$ letter of $\omega$.
> 3 votes

---
Tags: formal-languages
---


# Question
Title: Finding a subset of objects with max value with constraints
There are m people and n kinds of objects. Each person has exactly one instance of each kind of objects, but these objects have different values associated. Now I want to find a subset of objects from all those m\*n objects satisfying the condition: it should have p objects of each kind (p \< m), and a person cannot contribute more than p objects. I want to maximize the total value of the objects picked. I have tried several obvious greedy algorithms, but none of them has found the optimal solution. Is there an algorithm that is not NP hard?

# Answer
Yes sure. You can solve this problem using Minimum Cost Maximum Flow technique. With this algorithm you can find the maximum flow in a network with weighted edges that have minimum total weight (weights can be negative). So let's build the model that fits our problem best.

Build the following graph

* There are $n$ nodes in the set $A$ that represent each person.
* There are $m$ nodes in the set $B$ that represent each type of object.

The set $A$ and $B$ are full connected the edge $e\_{i,j}$ that connects node $A\_i$ and $B\_j$ has:

* capacity: 1 (It can be taken at most once)
* cost: $-w\_{i,j}$ (We are looking maximum which is the same as minimize the negation of each value)

Source node $S$ is connected with an edge to each node in the set $A$.

* capacity: $p$ (each person can carry at most $p$ objects)
* cost: 0

Nodes on set $B$ are connected to target node $T$.

* capacity: $p$ (each object can be carried by at most $p$ persons)
* cost: 0

Maximum flow in this graph is $m * p$ since there is an answer where each object is taken exactly $p$ times. Minimum cost is the negation of the answer you are looking for.

This problem is in P.
> 1 votes

---
Tags: algorithms
---


title: Colouring the graph

text:
# Question
Title: Colouring the graph
We have a directed simple graph $G$. Out-degree of any vertex is at most $k$ in $G$. We need to show that $G$ is $2k+1$-partite.

# Answer
> 1 votes
Attempt it by induction. Assume the property is true for every graph with less than $n$ vertices. Now let $G$ be a graph with $n$ vertices. Take the vertex $v$, with the smallest in-degree.

How big can the in-degree of this smallest $v$ be? And you know the outdegree of $v$ is at most $k$. So how many vertices is it adjacenct to? Now $G$ minus $v$ is a graph of $n-1$ vertices and so it is coloured with your $2k+1$ colours. Now adding that $v$ back.... (you can finish from here)

---
Tags: graphs, colorings
---


# Question
Title: Must algorithm for comparing numbers investigate all bits?
Suppose algorithm $A$ on a digital computer takes as input integers $x$ and $y$ in binary. The algorithm outputs one if $x=y$, and zero if $x \neq y$. Is there a proof that for any input $x$ and $y$ in which $x=y$, there exists a one-to-one function $f: \mathbb Z \rightarrow \mathbb Z$ such that $A$ compares all of the bits of $f(x)$ to all of the bits of $f(y)$?

# Answer
There is a problem with your question because it is ill-posed.

First, in your question you talk about a function $f$ as if a Turing machine somehow operates with functions and can "use" such an $f$ during its execution. This is not the case. A Turing machine operates with tapes and heads, and it has states, and a transition function. So you need to carefully explain what it means for the machine to "compare bits of $f(x)$ and $f(y)$". Do you claim that the machine will write down $f(x)$ and $f(y)$ onto a tape at some point? What if it encodes the least significant bit of $f(x)$ and $f(y)$ in its state, and it writes down the rest onto a tape?

Second, there is no instruction corresponding to "compare bits". Even if we add one to the Turing machine, the machine can avoid using it and still effectively compare bits. It is also possible to compare bits in ways that are not easily recognizable as such. So the whole notion of "compare bits" is ill-formed, at least for the traditional notion of Turing machine.

It is possible to make your question precise in several ways. For example, we could devise a "comparison network" that consisted of wires and equality tests, much like the sorting networks use comparisons. Then we could ask about the structure of a comparison network that correectly compares numbers.

Another way to make your question precise is to avoid talking about "comparison of bits", and instead ask whether the machine *reads* bits. This is not a problematic concept because we know what it means: the machine reads a bit if at any point in the execution of the algorithm the head scans the cell that contains the bit.

Now, to answer your question, let us make the conditions of the problem precise. Let us say that the two numbers in question $x$ and $y$ are written on two read-only tapes $t\_x$ and $t\_y$. Suppose we have a Turing machine $T$ which writes $0$ on the output tape if $x \neq y$ and it writes $1$ if $x = y$.

> **Theorem:** If $T$ outputs $1$ then during its execution it scans every bit on $t\_x$ and every bit on $t\_y$.

*Proof.* We prove the statement by contradiction. Suppose there were a bit of $t\_x$ which was not scanned (the argument is symmetric if there is an unscanned bit of $t\_y$). Then the machine would operate in exactly the same way if we flipped that bit. Because we assumed that the machine works correctly, this would imply that the machine outputs $1$ on input $x$, $y$, and also on input $x'$, $y$ where $x'$ is $x$ with one bit flipped. It would follow that $x = y = x'$, a contradiction. QED.
> 4 votes

---
Tags: logic, proof-techniques
---


# Question
Title: Highly colored vertices in greedy coloring imply existence of subtrees
I have a graph $G$ on which I try greedy coloring; i.e. I order the vertices and then start coloring them according to their order and I assign each vertex the smallest possible color available to it. (It is easy to see that this might not be the optimal coloring possible)

So after the coloring, we see that a vertex has color $k$ which is the highest assigned color in the graph (other vertices might have color $k$ but no vertex has color more than $k$). I would like to say that given any tree on $k$ vertices I can find that tree as a sub-graph of $G$.

My ideas : I observed that the $k$ vertex tree can be found in the graph with one vertex being the one colored $k$ (as one might expect). Moreover I think that if someone mentions any $k$ vertex tree and any node, $v$, in that tree we can find the tree in $G$ with the vertex colored $k$ acting as the node $v$. This is what I tried to induct on but couldn't succeed.

# Answer
Let us prove the following claim by induction.

> Let $T$ be a colored rooted tree in which each color appears at most once, and the colors of the children of a node are smaller than the color of the node.
>
> Let $G$ be a greedily colored graph, and let $v$ be a vertex whose color is the same as the color of the root of $T$. Then we can embed $T$ into $G$ in such a way that the root gets mapped to $v$ and the colors of all nodes match.

If $T$ consists of a single node, this is clear. Otherwise, let $T\_1,\ldots,T\_m$ be the subtrees rooted at the children of the root of $T$. Since the colors of the roots of $T\_1,\ldots,T\_m$ are distinct and smaller than the color of the root of $T$, the node $v$ must have distinct neighbors $v\_1,\ldots,v\_m$ whose colors match the colors of the roots of $T\_1,\ldots,T\_m$. Inductively, we can embed $T\_1,\ldots,T\_m$ into $G$. Since all colors in $T$ are distinct, the embeddings are disjoint, and so can be put together to construct the desired embedding of $T$.

To derive your claim from this one, you need to show that every tree of size $k$ can be colored according to the prescriptions of this claim. You can use BFS to accomplish that.
> 1 votes

---
Tags: graphs, trees, colorings
---


# Question
Title: Hueristic Algorithm to find the maximum clique
Let the algorithm be defined as follows:

Consider the following heuristic algorithm for finding the maximum size clique in a graph. (1). Delete from the graph a vertex that is not connected to every other vertex. (2). Repeat (1) until the remaining graph is a clique.

Now, how do I show that this algorithm does not give a solution which is within constant times of the optimal solution? I was reading about heuristic algorithms when I came across this problem. Any sort of input is appreciated.

# Answer
Consider a graph which is the disjoint union of $K\_i$ and $K\_1$, the isolated vertex.

Let the order of selection of vertices be such that the isolated vertex is last.

Then your heuristic outputs solution 1 for any $i \in \mathbb{N}$.
> 2 votes

---
Tags: algorithms, graphs, search-algorithms, heuristics, clique
---


# Question
Title: Solving recurrence relation with square n
I have the following recursive function:

$$ T(n) = \begin{cases} \theta (1) & \text{if $n$ = 1;}\\ T(\sqrt{n}) + \theta (log(n)) & \text{if n $\geq$ 2}\\ \end{cases} $$

I tried:

\begin{eqnarray\*} T(n)&=&T(\sqrt{n}) + log(n)\\ &=&T(\sqrt\[4\]{n}) + 2 log(n)\\ &=&T(\sqrt\[8\]{n}) + 3 log(n)\\ \end{eqnarray\*}

I can't find a way to solve it without master theorem. Is it possible to solve this with the recursive three method? I don't know when should i stop the recursion.

I've already seen other questions about this topic, but they didn't solve my problem.

Thanks

# Answer
The thing to point out is that the $\sqrt{n}$ in the recurrence relation should be interpreted correctly - either you view $T$ as a function defined on $\mathbb{R}\_{\geq 1}$, which is bounded near $1$, or you actually understand the $\sqrt{n}$ as the integral part, i.e. $\[\sqrt{n}\]$.

In the first case, you fix a small neighborhood of $1$ on which the function $T$ is bounded by a fixed constant, and the recurrence stops when $n$ falls into this neighborhood; in the second case, the recurrence simply stops at $n = 1$.

---

Here I give a solution using the first understanding:

Put $m = \log(n)$ and rewrite the relation as:

$$ S(m)=\begin{cases}\theta(1) & m = 0 \text{ (or better: $m \rightarrow 0$)};\\ S(m/2) + \theta(m) & m \> 0, \end{cases} $$ where $S(m)$ is the function defined by $S(\log(n))=T(n)$.

This translates to the following: we have constants $r$, $c$, $d$, such that:

* $S(m) \leq c$ for all $0 \leq m \< r$;
* $S(m) \leq S(m/2) + d \cdot m$ for all $m \geq r$.

It is then easily proved using induction that we actually have $$ S(m) \leq \max(2c/r, 2d) \cdot m $$ for all $m \geq r/2$. (First note that it is true for $m$ in the interval $\[r/2, r)$, and then show that if it is true on the interval $\[x/2, x)$, then it is also true on the interval $\[x, 2x)$.)

So finally we get $T(n) = \theta(\log(n))$.
> 1 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Converting between (standard) primal to dual forms (LP)
I'm working on a HW assignment as follows:

Given the primal canonical problem: $$min \langle c,x \rangle \text{ s.t. } Ax \geq b, x \geq 0$$ and the canonical dual problem: $$ max \langle b,y \rangle \text{ s.t. } A^Ty \leq c, y \geq 0$$

Show that converting PC (primal canonical) to DC (dual canonical) is similar when done directly or when done via canonical to standard conversion (i.e. primal canonical -\> dual canonical == primal canonical -\> primal standard -\> dual standard -\> dual canonical).

---

I converted the CP to SP (standard primal) by adding slack variables $s\_1,\ldots,s\_n\geq 0$ and adding them to each inequality.

My problem is showing the similarity between the SP and SD (standard dual).

What I've done so far is this: SD (standard dual) wants to maximize $b^Ty$ so:

1. $b = Ax$
2. $b^ty = (Ax)^Ty = (x^TA^T)y = x^T(A^Ty) \leq x^Tc$

Now, I don't know how to proceed. How can I show that minimizing $c^Tx$ is maximizing $b^Ty$? Am I on the correct path?

*PS: I am pretty sure dual and primal problems can be shown where the primal is max and the dual is min, but I think it doesn't matter at all, right?*

# Answer
> 2 votes
In class you have been shown several algorithms:

* Algorithm A: Convert a primal canonical to a dual canonical.
* Algorithm B: Convert a primal canonical to a primal standard.
* Algorithm C: Convert a primal standard to a dual standard.
* Algorithm D: Convert a dual standard to a dual canonical.

Notice that if you run Algorithms B,C,D in sequence, then you get another algorithm for converting a primal canonical to a dual canonical. The question is to compare the dual canonical program constructed this way to the one constructed by applying Algorithm A.

---
Tags: linear-programming
---