# Question
Title: Confusion about $EXP \subseteq P^{EXPCOM}$ claim from Arora and Barak
In *Computational Complexity -- A Modern Approach*, by Arora and Barak, they have the following claim (Example 3.6).

> Let EXPCOM be the following language $$ \\{ \langle M, x, 1^n\rangle \mid M \text{ outputs 1 on $x$ within $2^n$ steps} \\} $$ Then $\mathbf{P}^{\mathrm{EXPCOM}} = \dots = \mathbf{EXP}$. \[...\]
>
> Clearly, an oracle to EXPCOM allows one to perform an exponential-time computation at the cost of one call, and so $\mathbf{EXP} \subseteq \mathbf{P}^{\mathrm{EXPCOM}}$. \[...\]

I believe their reasoning is as follows:

1. Suppose we have a language $L \in \mathbf{EXP}$.
2. Thus there is a TM $M$ that decides it in time $2^{n^c}$.
3. We want to create a poly-time oracle-TM $T^{\mathrm{EXPCOM}}$ that decides $L$.
4. $T$ works as follows on input a string $x \in \\{ 0, 1 \\}^{\*}$. It queries its EXPCOM oracle on input $\langle M, x, 1^{n^c} \rangle $, and outputs the same answer as the oracle.
5. Clearly $T$ runs in polynomial time, and it decides the same language as $M$. QED.

Here is my confusion. For $T$ to call its EXPCOM oracle, it needs to know *which* $M$ that decides $L$ (in exponential time). However, 2. only promises the *existence* of a machine $M$; it doesn't actually tell you how to find it! (this problem also applies to the running time $2^{n^c}$ of $M$).

So clearly I'm misunderstanding something, but what? Is it my understanding of the language EXPCOM? Is it my description of $T$? Or have I misunderstood oracle-TMs altogether? (Or maybe all three?)

# Answer
You are correct that $T$ needs to know which Turing machine accepts $L$. This Turing machine is $M$, and you can hardcode it into $T$. There is absolutely no problem with that.

Here is a similar example. Suppose that there is a proof that $P \neq NP$. Then there is a Turing machine that prints a proof of $P \neq NP$.

Proof: According to the assumption, there is a proof $\pi$ that $P \neq NP$. Construct a Turing machine $T$ that prints $\pi$. Then $T$ prints a proof of $P \neq NP$. $\quad\square$

What seems to worry you is that you think of $T$ as accepting $L$ *as an input*, from which it is supposed to come up with the Turing machine $T$. But this is not the case – all we have to do is to show that for each $L$ there exists an appropriate Turing machine $T$. Moreover, it is not clear how $T$ would accept $L$ as input – a language is, in general, an infinite object.

---

Sometimes we do need to be worried about the issue that you raised. Here is an example. Let $L\_1,L\_2,\dots$ be an infinite sequence of decidable languages. For each $L\_i$, there is a Turing machine $T\_i$ that decides $L\_i$. But is there a Turing machine $T$ that accepts an index $i$ and a word $w$ and returns whether $w \in L\_i$? Not necessarily (I'll let you come up with a counterexample). When such a machine $T$ does exist, we say that $L\_1,L\_2,\dots$ are *uniformly* decidable.

No such uniformity condition appears in your question. We could impose such a condition artificially by providing $L$ as an input via a Turing machine, not necessarily running in exponential time, that accepts $L$. In this case, your criticism would be valid – given a Turing machine that accepts a language in $\mathsf{EXP}$, it is not clear how to find a Turing machine accepting the same language and running in exponential time.
> 2 votes

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


# Question
Title: $\mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{P}/\mathrm{poly} \implies \mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{MA}$
Is anyone able to give a concise proof for the implication stated in the title? This is gonna be in stark contrast to this question.

---

For definition of $\mathrm{strict}$-$\mathrm{SUBEXP}$, see here.

# Answer
Yes, I can.

First of all, $\mathrm{poly}(\mathrm{subexp}) = \mathrm{subexp}$. So, we can simulate a *subexp* TM in *subexp* time. (This is in stark contrast to standard $\mathrm{SUBEXP}$ where we do not have any particular *subexp* machine)

Using this, we are able to put $\mathrm{strict}$-$\mathrm{SUBEXP}$ inside $\mathrm{PSPACE}$. The *poly space* TM would try every possible *poly-size circuit* and for each circuit make $2^n \times 2^n$ *local checking* of the tableaux using the current circuit. Note that the subexp TM never touches the $2^n$th cell and would cease to run long before $2^n$ time but that does not affect the poly space bound.

After putting $\mathrm{strict}$-$\mathrm{SUBEXP}$ inside $\mathrm{PSPACE}$, we use the result of interactive proving protocol with the power of the prover at most $\mathrm{P}^\mathrm{L}$ (where $\mathrm{L}$ is the language at hand) to push it down to $\mathrm{MA}$.
> 0 votes

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


title: Find 2 sets with an empty intersection

text:
# Question
Title: Find 2 sets with an empty intersection
I have the following problem. The problem can be formulated in three different ways

Given sets $B\_{-n},\ldots,B\_n \subset \\{1,\ldots,m\\}$.

Find $i,j \in \\{-n,\ldots,n\\}$ with $|i| \neq |j|$ and $i,j \neq 0$ that satisfy $B\_i \cap B\_j = \emptyset$

**"Invert" the sets $B\_i$**

Define $A\_k=\\{i: k\in B\_i \\}$. $A\_1, \ldots, A\_m \subset \\{-n,\ldots,n\\}$.

Find $i,j \in \\{-n,\ldots,n\\}$ with $|i| \neq |j|$ and $i,j \neq 0$ that satisfy the property $\\{i,j\\} \not\subset A\_k$ for all $k=1,\ldots,m$

**Relation instead of set of sets**

Define relation $R\subset\\{1,\ldots,m\\}\times\\{-n,\ldots,n\\}$ with $kRi \equiv k \in B\_i$.

Find $i,j \in \\{-n,\ldots,n\\}$ with $|i| \neq |j|$ and $i,j \neq 0$ that satisfy the property for no $k=1,\ldots,m: kRi \land kRj$

**Naive Algorithm**

As far as I can tell, the 3 problems are the same thing viewed from slightly different perspectives. One possible algorithm would be to iterate through all pairs $(i,j)$ and check if the condition is satisfied. This algorithm has runtime of $\mathcal{O}(n^2\cdot f(m,n))$ with the runtime $f$ of the check if the pair satisfies the property.

Specifically for the first case: Assuming the sets are implemented sorted lists the intersection can be checked to be empty in $\mathcal{O}(m)$ time via a simple mergesort-like scan.

**Question**

Is there an algorithm for this problem that solves it in $\mathcal{o}(n^2)$ time? (maybe with some tradeoff in the $m$ component)

# Answer
Here is one example for an algorithm, which can run at $O(4^m \cdot m+ n\cdot m)$ time, which is $o(n^2)$ if $m\ll c\log n$ for every $c\<0.5$.

We convert a subset $B\_i$ into an ordinal number $1\leq j\leq 2^m$, a number of $m$-bits, in $O(m)$ time, where the $k^{\text{th}}$ bit of $j$ euqals one iff $k\in B\_i$. Now, for every ordinal number $j$ we save a link list $L\_j$ which contains pointers to all subsets $B\_i$ that are associated with ordinal number $j$. This can be done in $O(n\cdot m)$ time.

Second, since all subsets with the same ordinal number are containing the same elements, using $O(m)$ time we can determine for every ordinal numbers $j\_1,j\_2$ if the corresponding subsets of $L\_{j\_1},L\_{j\_2}$ have a common element (i.e., there exists $1\leq k\leq m$ s.t., the $k^{\text{th}}$ bit of both $j\_1$ and $j\_2$ is one) or not. In case the corresponding subsets have empty intersection, and in case that $L\_{j\_1}$ and $L\_{j\_2}$ are non empty, and it is NOT the case where $L\_{j\_1},L\_{j\_2}$ containing a single subset, pointing respectively to to $B\_{n}$ and $B\_{-n}$, then we can find $B\_{i}$ and $B\_{j}$ satisfying the above condition in $O(1)$.

In the worst case, we run over all ordinal numbers $1\leq j\_1,j\_2\leq m$ in $O((2^m)^2)=O(4^m)$ time, and checking an empty intersection takes $O(m)$ time. Since the first step takes $O(n\cdot m)$ time, the complexity of the algorithm is $O(4^m \cdot m+ n\cdot m)$.
> 1 votes

---
Tags: algorithms, sets
---


# Question
Title: Is there a proof that shows why DFAs can't be used to show the concatenation of two regular languages?
Sipser goes on to show that regular languages are closed under concatenation using NFAs. His proofs typically use NFAs to prove closure under the operations.

Is there an alternative proof that goes on to show that regular languages are also closed under concatenation using DFAs?

# Answer
Using NFAs *does* prove the result for regular languages, since NFAs accept exactly the regular languages. In principle, one could give a proof using DFAs but it's likely to be very fiddly and probably not enlightening. It's much easier to give the proof using NFAs and separately show that anything accepted by an NFA is also accepted by a DFA.

Indeed, it's even easier to give the proof using regular expressions! This is part of the point behind giving the three equivalent characterizations of the regular languages: it means that, when you want to prove something about regular languages, you can use whatever system makes the proof easiest.
> 3 votes

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


title: Data structure with AVL and Hash table

text:
# Question
Title: Data structure with AVL and Hash table
Suggest a Data Structure for N elements that support on the following operations: Describe the Data Structure on a sketch and literally, describe how each method work.

\begin{array}{|c|c|c|c|} \hline Operation & Average Running Time & Deterministic Running Time \\ \hline Init(N)& &O(1)\\ \hline Insert(x)& O(log(n)) & O(log(n))\\ \hline Delete(x)& O(log(n))& O(log(n))\\ \hline getContinuous(KEY,k) & O(k) & O(max(k,log(n))\\ \hline \end{array}

---

getContinuous(KEY,k) - returns a list of the k successors to the element with key KEY

What I thought to do: Working with hash table that holds AVL trees instead of linked lists (this will ensue $O(logn)$ . I don't know though how to provide $getContinuous(KEY,k)$. Perhaps with another hash table? but how?

Thanks

# Answer
Use an AVL and a hash table implemented by link-list. All leaves in the AVL are connected via a doubly link-list, and every leaf will contain a pointer to the corresponding entry in the hash table.

The hash table will translate a key to a pointer. The pointer will point to the corresponding element in the AVL.

When inserting a element, we first enter it to the AVL, deriving the order of the key in the AVL, and connecting the element to its next and previous leaves. Then, we insert the a pointer to the corresponding leaf in the AVL to the hash table. This takes $O(1)$ in worst case, as the hash table is implemented by a link list. Finally, we connect the AVL leaf entry with the hash table entry. It takes $O(\log n)$ in worst case.

When deleting an element, we first find it in the AVL. Then, since the AVL points to the hash table, we can delete the corresponding entry in the hash in $O(1)$. Finally, we delete the element in the AVL, and "fix" the link-list of leaves. It takes $O(\log n)$ in worst case.

getContinuous(KEY,k) is implemented as follows: We search the key in the hash table for at most $\log n$ steps. If it found- then using the pointer to the AVL leaf, and using the link-list of the leaves we found the $k$ successors. If the key was not found within $\log n$ steps, then we search the AVL using the regular search procedure, find the corresponding key, and imply the $k$ successors.

Of course, getContinuous(KEY,k) takes $O(k+\log n)= O(max(k,\log n))$ time in the worst case. However, it takes in average $O(1)$ steps to find the key in the hash table, and thus getContinuous(KEY,k) takes $O(k)$ time in average.
> 2 votes

---
Tags: data-structures
---


# Question
Title: Prove that finding largest subset of undirected graph that is almost independent is NP-hard
> A subset $S$ of vertices in an undirected graph $G$ is called almost independent if at most 100 edges in $G$ have both endpoints in $S$. Prove that finding the size of the largest almost-independent set of vertices in a given undirected graph is NP-hard.

For these types of problems, I know that I should try to find a polynomial time reduction of an algorithm that is already known to be NP-hard. I tried my hand at trying to manipulate the k-coloring problem, but without any luck.

How would I go about proving this function is NP-hard?

# Answer
The proof is by reduction from independent set. Given an instance $(G,k)$ of independent set, construct a new instance $(G',1000k)$ in the following way: each vertex $x \in G$ is replaced by an independent set $I\_x$ of size 1000, and each edge $(x,y)$ is replaced by a complete bipartite graph $I\_x \times I\_y$.

If $G$ contains an independent set $S$ of size $k$, then $G'$ contains an independent set $\bigcup\_{x \in S} I\_x$ of size $1000k$. In the other direction, suppose that $G'$ contains an almost independent set $S$ of size $1000k$. Remove all vertices incident to any edges within $S$ to obtain an independent set $S' \subseteq S$ of size at least $1000k-200$. Let $T = \\{ x : I\_x \cap S' \neq \emptyset \\}$, and note that $T$ is an independent set of $G$. Finally, since $S'$ can contain at most 1000 vertices from each $I\_x$, we see that $|T| \geq \lceil |S'|/1000 \rceil = k$.
> 5 votes

# Answer
The following proof shows that the almost independent set problem is hard using a Cook reduction.

It is well-known that approximating the independent set problem is hard within every polynomial factor \[1\].

Suppose that if there is a polynomial algorithm for the almost independent set problem, then there is an $x-100$-approximation (i.e., the algorithm returns an independent set of size larger than or equal to $n\_{opt}-100$, where $n\_{opt}$ is the size of the optimal independent set) polynomial algorithm for the independent set problem. Thus, the problem is NP-hard.

The approximation algorithm for the independent set problem goes as follows:

1) Derive the largest almost independent set $S$.

2) Remove from $S$ all vertices that share the same edge. Denote the result by $S'$

3) Return $S'$.

The algorithm runs in polynomial time.

Correctness: Let $S\_{opt}$ be the largest independent set. Then

$$|S'|\geq |S|-100\geq |S\_{opt}|-100.$$

The first inequity follows as remove up to 100 vertices. The second inequity follows as every independent set is also an almost independent set, and thus the size of the largest independent set is smaller than or equal to the size of the largest almost-independent set.

Thus, the algorithm is a $x-100$ approximation for the independent set problem, and unless P=NP, there is no polynomial algorithm for the almost independent set problem.

\[1\]-https://en.wikipedia.org/wiki/Independent\_set\_(graph\_theory)
> 1 votes

# Answer
## *My bounty is gonna be over in 7 days. Anyone with clever idea?*

## This answer is wrong. And I have no idea how to prove this to be complete for $NP$ in any sense.

## If only 1 edge is allowed in the *almost-IS*, then by complementing, this is Karp-complete as shown here.

## Even for 2 edges allowed, the hardness of this problem is very elusive.

## But if two missing edges are required to be incident to one vertex, then a gadget of one edge and one vertex being connected to all $V$ will show Karp-completeness.

> This is Turing complete for $NP$ by a Turing poly-time reduction trying to add each of the $O((n^2-|E|)^{100})$ possible $100$-subsets of $\bar E$ (the complement of $E$ in $G$) and query the **almost-clique oracle** whether the **denser** graph has a $k$-*almost clique*. Since, for each query we add only $100$ edges if one of the query return **YES**, return **YES**. Otherwise, return **NO**.
>
> For Karp completeness, I have not been able to devise any **NICE** *gadget*.
> 0 votes

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


# Question
Title: Is the language of Turing machines that calculate a given function $f$ in RE or coRE?
For a function $f$, consider the language $$L=\\{\langle M\rangle\mid M\text{ computes }f\\}\\,.$$

Where does the language above is and how do I prove it?
To me it seems that it's not in RE nor coRE but I struggle to prove so. what I have so far is reduction from HP to $L$ as follows:

$$R(\<M\>,w) = \<M'\>$$
$$ Define \ M': \\ M(w) \\ \qquad \qquad \qquad Write \ x \ on \ the \ tape$$

$$ 1. \ Run \ M \ on \ W \\ 2.\ write \ x \ on \ the \ tape $$

But I can't prove that this language is in RE.

So how do I proceed from here ?

# Answer
Below, we assume $f$ computable, otherwise $L$ is empty, so RE and coRE.

# For the "RE" part

This can be done with reductions, but the easy way is to exploit the Rice-Shapiro theorem.

Now, take a set of partial recursive functions $F$ ($F=\\{f\\}$, in your case), and define $L$ to be the set of TMs that implement some function in $F$. If $L$ happens to be in RE, then by Rice-Shapiro we must have

1. if $g\in F$ has infinite domain, some finite restriction of $g$ must belong to $F$ as well
2. if $g$ is non-total, every computable extension of $g$ must belong to $F$

Often, one of these cases is false, implying that $L$ was not RE (provided it has the form above).

In your case, $L$ can not be RE since $F$ only contains $f$: if $f$ has an infinite domain, 1) is violated, otherwise 2) is violated.

In both these cases, you can replace Rice-Shapiro by suitable reductions from the complement of the halting problem, but doing that you are essentially repeating the proof of Rice-Shapiro. It is still a nice exercise, though: one can define one reduction for each case.

Even more in general, $F$ can never be finite if $L$ is RE. But $F=\\{f\\}$ is finite.

# For the "coRE" part

If $f$ is the always-undefined function, $L$ is coRE. Indeed, for $M$ to implement a different function from $f$, it is enough that $M$ halts on some input, which is a RE problem.

If $f$'s domain is nonempty, say $f(x)=y$, $L$ is not coRE. To prove that, it suffices to reduce the halting problem to $L$. Given $M$, craft $M'$ which on input $w\neq x$ outputs $f(w)$. When $w=x$, instead, run $M$, and if that halts output $y$ (otherwise we diverge).
> 1 votes

---
Tags: computability
---


# Question
Title: Nine-input sorting network of optimal depth with minimum number of comparators
In the research on sorting networks, two parameters are typically of interest: The number of comparators required and the depth required. They have practical implications for throughput and latency. Results in latter category are usually easier to achieve than corresponding results in the former. Already in 1989, Parberry demonstrated that the optimal depth for nine-input and ten-input sorting networks is seven:

Ian Parberry. "A computer assisted optimal depth lower bound for sorting networks with nine inputs." In *Proceedings of the 1989 ACM/IEEE Conference on Supercomputing*, November 1989, pp.152-161

Not until 2014 was it shown by Codish et. al. that the optimal number of comparators for nine-input sorting networks is 25, while the optimal number of comparators for ten-input sorting networks is 29:

Michael Codish, Luís Cruz-Filipe, Michael Frank, and Peter Schneider-Kamp. "Twenty-five comparators is optimal when sorting nine inputs (and twenty-nine for ten)." In *Proceedings 26th IEEE International Conference on Tools with Artificial Intelligence*, November 2014, pp. 186-193

In general, sorting networks of optimal depth cannot necessarily be achieved by using the optimal number of comparators. Knuth (TAOCP, Vol. 3, 2nd ed.) states that often "one or two extra comparator modules" are required, and shows (Fig. 51) a ten-input sorting network of optimal depth seven that requires 31 comparators, that is, two more than optimal.

In a multi-hour search of the literature and the internet at large, I have been unable to find a worked-out example of a nine-input sorting network of depth seven, nor have I been able to find information on the minimum number of comparators needed to construct such network. I am currently unable to construct any nine-input sorting networks of optimal depth with my home-grown software.

What nine-input sorting networks of depth seven are known? Following Knuth, they should require no more than 26 or 27 comparators.

# Answer
> 4 votes
I found a 2002 Reference of the Best-Known Sorting Networks for up to 16 Inputs by Ron Zeno including a diagram of a 9-input network that seems to fit the bill.

His nine-input sorting network of depth seven uses the following arrangement of comparators

{0, 7}, {1, 6}, {2, 5}, {3, 4},
{0, 3}, {1, 2}, {4, 7}, {6, 8},
{0, 1}, {2, 6}, {3, 4}, {5, 8},
{1, 2}, {3, 5}, {4, 6}, {7, 8},
{1, 3}, {2, 4}, {5, 7},
{0, 1}, {2, 3}, {4, 5}, {6, 7},
{3, 4}, {5, 6}

---

Wolfram demonstrations includes a beta about Sorting Networks, which in due course contains an example of an optimal (module count) nine-input network:

> {{1, 2}, {4, 5}, {7, 8}},
> {{2, 3}, {5, 6}, {8, 9}},
> {{1, 2}, {4, 5}, {7, 8}, {3, 6}},
> {{1, 4}, {2, 5}, {6, 9}},
> {{4, 7}, {5, 8}, {3, 6}},
> {{1, 4}, {2, 5}, {6, 8}, {3, 7}},
> {{2, 4}, {5, 7}},
> {{3, 5}, {6, 7}},
> {{3, 4}}

(That's probably about as close as I will get to providing a visualisation:
*looks* trivial to plug "the Flensburg" or above 7-level configurations.)

# Answer
> 3 votes
In addition to the accepted answer, I found a second example of a nine-input sorting network of optimal depth seven wioth the optimal number of twenty-five comparators on this website. It appears to belong to a German research group and H. W. Lang is listed as the author of the referenced page, which dates to 2014. The arrangement of comparators used is as follows:

{0, 1}, {2, 3}, {4, 5}, {6, 7},
{0, 6}, {1, 7}, {2, 4}, {3, 8},
{0, 2}, {1, 6}, {3, 4}, {5, 8},
{1, 5}, {2, 3}, {4, 6}, {7, 8},
{1, 2}, {3, 4}, {5, 7},
{0, 1}, {2, 3}, {4, 5}, {6, 7},
{3, 4}, {5, 6}

---
Tags: algorithms, sorting
---


# Question
Title: How to convert a CFL to a deterministic PDA?
I am trying to complete this question. However, I am unsure of the steps necessary to complete the conversion from a CFL to a deterministic PDA.

I know that $ww' | w \in \left \\{ a,b \right \\}^{\*}, w' \in \left \\{ b,c \right \\}$ is a context free grammar.

I need to create a deterministic PDA diagram.

What steps do I need to complete in order to convert to a deterministic PDA?

# Answer
> 0 votes
The deterministic PDA has two states. In the initial state, whenever it reads $a$, it pushes $A$ into the stack, whenever it reads $b$, it does nothing, and whenever it reads $c$, it pops $A$ from the stack and moves to the second state. In the second state, if it reads $a$, it gets stuck, if it reads $b$, it does nothing, and whenever it reads $c$, it pops $A$ from the stack. The PDA accepts the word if it is in any state and the stack is empty.

(The exact definition depends on your PDA model. You need to take additional care to handle strings in $b^\*$.)

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


# Question
Title: Reducing lambda expression to normal form
Can someone explain the steps to reduce $$ (\lambda n. \lambda m. \lambda f. \lambda x.\ n\ (m\ f)\ x)\ (\lambda f. \lambda x.\ f\ (f\ x))\ (\lambda f. \lambda x.\ f\ x) $$ to $\lambda y. \lambda z.\ y\ (y\ z)$?

# Answer
> 7 votes
$\lambda$-calculus is a rewriting system, but it's power to express all partial recursive functions makes it equivalent to Turing machines, in the sense that it is a universal model of computation. Means of computation in $\lambda$-calculus are conversions and reductions, of which the main ones are $\beta$-reduction and $\alpha$-conversion. You can learn a lot about $\lambda$-calculus on Wikipedia alone.

**$\alpha$-conversion**
Take for example $\lambda$-expressions $(\lambda x. x)$ and $(\lambda y. y)$. We say they are $\alpha$-equivalent because they clearly represent the same function. In short, we can rename variables (and sometimes have to).

**$\beta$-reduction**
This relation is the one that "gives life" to $\lambda$-expressions and reduces them to normal forms. We use $\beta$-reduction on terms of the form $(\lambda x. M)\ N$, i.e. when applying abstraction to some term $N$, and we call that construction a **redex**. What this expression becomes after $\beta$-reduction is written $M\[x:=N\]$ and it means that we replaced all free occurrences of $x$ in $M$ with $N$. For example: $$ (\lambda x. x\ x)\ N \rightarrow\_\beta N\ N$$

We will be reducing leftmost outermost redex in each step. This strategy garantees that we will get to normal form if it exists.

**Now let us dive into this...**
Let's find a leftmost outermost redex (underlined) in your expression: $$\underline{\Bigl(\lambda n.\lambda m.\lambda f.\lambda x. n\ (m\ f)\ x\Bigr)\ \Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)}\ (\lambda f. \lambda x. f\ x)$$

We have $\Bigl(\lambda n.\lambda m.\lambda f.\lambda x. n\ (m\ f)\ x\Bigr)$, which is an abstraction (it is of the form $\lambda n. M$), that is applied to $\Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)$, so ($\beta$-reduction) we have to replace all free occurences of $n$ in $M$ with $\Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)$. We get $\biggl(\lambda m.\lambda f.\lambda x. \Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)\ (m\ f)\ x\biggr)$, so entire expression is now (where I already underlined next outermost redex): $$\underline{\biggl(\lambda m.\lambda f.\lambda x. \Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)\ (m\ f)\ x\biggr)\ (\lambda f. \lambda x. f\ x)}$$ We now have to substitute $(\lambda f. \lambda x. f\ x)$ for $m$ in $\biggl(\lambda f.\lambda x. \Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)\ (m\ f)\ x\biggr)$ and get $$\lambda f.\lambda x. \underline{\Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)\ \Bigl((\lambda f. \lambda x. f\ x)\ f\Bigr)}\ x$$ Now just keep reducing $$\lambda f.\lambda x. \underline{\Bigl(\lambda x. ((\lambda f. \lambda x. f\ x)\ f)\ (((\lambda f. \lambda x. f\ x)\ f)\ x)\Bigr)\ x}$$ $$\lambda f.\lambda x. \Bigl(\underline{(\lambda f. \lambda x. f\ x)\ f}\Bigr)\ \biggl(\Bigl((\lambda f. \lambda x. f\ x)\ f\Bigr)\ x\biggr)$$ $$\lambda f.\lambda x. \underline{(\lambda x. f\ x)\ \biggl(\Bigl((\lambda f. \lambda x. f\ x)\ f\Bigr)\ x\biggr)}$$ $$\lambda f.\lambda x. f\ \biggl(\Bigl(\underline{(\lambda f. \lambda x. f\ x)\ f}\Bigr)\ x\biggr)$$ $$\lambda f.\lambda x. f\ \Bigr(\underline{(\lambda x. f\ x)\ x}\Bigr)$$ $$\lambda f.\lambda x. f\ (f\ x)$$ And now, if you are still alive, remember $\alpha$-equivalence. We can change the names of variables, say $f$ to $y$ and $x$ to $z$, and obtain your wanted solution.

**What have we computed?**
We computed that $2 \cdot 1 = 2$, in $\lambda$-calculus using Church numerals:

* $c\_0 = \lambda f. \lambda x. x$
* $c\_1 = \lambda f. \lambda x. f\ x$
* $c\_2 = \lambda f. \lambda x. f\ (f\ x)$
$\vdots$

Expression $\lambda n.\lambda m.\lambda f.\lambda x. n\ (m\ f)\ x$ is the multiplication operator, and other two expressions (on which this operator was applied) are Church numerals for $2$ and $1$.

---
Tags: lambda-calculus, functional-programming
---


title: What is a compact model?

text:
# Question
Title: What is a compact model?
I am a domain scientist and I study biophysical systems. When I asked a colleague in CS for suggestions about how to design a multi-scale simulator, he mentioned the term "compact model".

Now, I can't find a very good definition of this term. I can find the book "Compact Modeling" edited by Gildenblat but this is a collection of domain specific applications, similar to what I found on google scholar.

I haven't found a first-principles treatment of what a compact model is or the advantages of using one. It would be great to know where I could find this topic in a textbook or annual reviews type paper.

Q: What is a compact model, and when is it useful?

# Answer
> 4 votes
This paper uses the phrases "compact model" and "multiscale simulation". Perhaps it is relevant. Indeed, Googling "multiscale simulation compact model" yielded lots of results.

The back cover of the book you refer to states:

> Compact Models of circuit elements are models that are sufficiently simple to be incorporated in circuit simulators and are sufficiently accurate to make the outcome of the simulators useful to circuit designers. The conflicting objectives of model simplicity and accuracy make the compact modeling field an exciting and challenging research area for device physicists, modeling engineers and circuit designers.

My understanding is that a compact model is a parametric equation with certain parameters determined that models the phenomenon of interest to some degree of precision.

# Answer
> 3 votes
Compact model refers to modeling of current-voltage behavior electron device (like MOS transistor) using a set of equations and parameters. It is used for circuit simulation of integrated circuit (IC). Since the fabrication cost and time of IC chip is large, IC designers need to simulate the circuit function before hand out the layout of IC to fabrication company. So it need to be accurate. And, since the IC scale is large (billions of transistor in Intel newest CPU), the model need to be sufficiently simple. It is also referred as SPICE model, since most of the circuit simulators are based on SPICE language (https://en.wikipedia.org/wiki/SPICE).

Another model used in semiconductor field is physical model, or TCAD model. It can simulate the physical properties inner the electron device, like charge densities, electronic potential distribution, and also the current-voltage output, based on the physical rules of electron transport. It's a powerful tool to analyze the performance of the device and the physics behind it. However it's very time consuming, even for a single device.

Compact model is like a black box of the electron device. It doesn't care what happen internal, and only gives the output behavior of the device (current and voltage responses on its terminals). I don't who invented the phrase "compact model" and why. I think this might be what the word "compact" refers to.

# Answer
> 3 votes
fwiw- when I think of compact models, I tend to think of combinatorial games. The idea is that simple rules and fully definable parameters can be used to produce complexity akin to nature (computational intractability), and that the compactness of the models makes them suitable for mathematical analysis.

a recent example of the utility of these models in computer science is AlphaGo. in the future, i suspect these types of models will be useful in gauging relative strength of problem solving algorithms.

# Answer
> 1 votes
This is strange, haven't heard of 'compact model' before, maybe this refers to compactness in model theory (http://en.wikipedia.org/wiki/Compactness\_theorem)? But it doesn't seem relevant to simulations.

# Answer
> 1 votes
A compact model is a circuit model that "can fit into SPICE", meaning that it is composed only of branches whose current-voltage characteristics are time-independent linear or nonlinear functions, or time-dependent relationships where voltage is the derivative of current with respect to time (L) or vice-versa (C).

# Answer
> 0 votes
Do not attach too much meaning to this terminology. So called simple analytical models of the complex system elements that are used in the CAD design of the whole complex systems. Gennady Zebrev

---
Tags: terminology
---


# Question
Title: Recursive DP vs Graph Traversal solutions to path-based problems
I am studying some algorithms interview questions and I am seeing many path-based questions like "if a robot is at the top left of a grid and can only move down or to the right, how many paths can take it to the bottom left of the grid". Or similarly sometimes they ask if the particular destination can be reached at all with some obstacles.

I've seen it solved with recursive DP solutions where you essentially start at the beginning state and recursively call the same function on all states reachable from the current state and the base case is when you reach the target state. Also sometimes memoization is used to optimize it.

However I think these types of problems can also be seen as graph traversal problems. The beginning state would be a node and each node has children which are the states that can be reached from the current node creating a directed graph. So finding a path to the target state can be done via a graph traversal algorithm.

So I guess my question is which is what are the tradeoffs for each approach? Or are they in some cases equivalent?

# Answer
Both approaches are valid. Assuming you're using memoization, they're largely equivalent; two different ways of thinking about the same thing.
> 1 votes

---
Tags: algorithms, dynamic-programming, shortest-path
---


# Question
Title: Finite state automaton for the reverse of the language, and multiple starting states
I am studying about Finite State Automaton, and I found that the when reversing a language (i.e., transforming $L$ to $L^R$), I have to add new start state. Why is that?

Also, can a Finite State Automaton have more than one starting state?

# Answer
> 2 votes
FSAs come in several varieties. The most common ones are deterministic (DFA), nondeterministic (NFA), and nondeterministic with $\epsilon$-moves (also called NFAs; sometimes $\epsilon$-NFAs).

The definitions of all three are not completely standard – there are several variants in the literature (for example, some allow the transition function of a DFA to be partial). However, in most standard definitions, all FSAs have a single initial state; though it is perfectly possible to define NFAs and $\epsilon$-NFAs having several initial states.

The reason you have to add a new initial state when reversing an NFA is exactly the requirement that there be a unique initial state. If we remove this requirement, then there is no need to add a new initial state.

---
Tags: automata, finite-automata, closure-properties
---


# Question
Title: Difference between concatenation of two languages and Intersection of two languages
Please also explain in terms of closure of these languages and plot a difference using specific example.

I am interpreted like this and now i am confused.

S1 and S2 are two languages.

"S --\> S1. S2 " ( S1 followed by S2 hence concatenation )

and

"S--\> S1.S2" ( S1 'and' S2 hence Intersection)

Correct me where I am going wrong.

P.S :

Also explain , In case of CFL's - Language is closed under Concatenation but not Intersection.

# Answer
> 2 votes
The concatenation of two languages $L\_1,L\_2$ is defined as follows: $$ L\_1L\_2 = \\{w\_1w\_2 : w\_1 \in L\_1, w\_2 \in L\_2\\}. $$ In words, we take all words in $L\_1$ and concatenate to them all words in $L\_2$.

The intersection of two languages $L\_1,L\_2$ is the set of words they have in common.

As an example, $$ \begin{align\*} &\\{a\\} \\{b\\} = \\{ab\\}, && \\{a\\} \cap \\{b\\} = \emptyset, \\ &\\{a\\} \\{a\\} = \\{aa\\}, && \\{a\\} \cap \\{a\\} = \\{a\\}, \\ &\\{a\\} \\{a,b\\} = \\{aa,ab\\}, && \\{a\\} \cap \\{a,b\\} = \\{a\\}. \end{align\*} $$

The concatenation and intersection of two regular languages is regular. In contrast, while the concatenation of two context-free languages is always context-free, their intersection is not always context-free. The standard example is $\\{a^nb^nc^m : n,m \geq 0\\} \cap \\{a^nb^mc^m : n,m \geq 0\\} = \\{a^nb^nc^n : n \geq 0\\}$. However, the intersection of a context-free language with a regular language is always context-free.

---
Tags: automata
---


# Question
Title: Minimum cost circulation problem with bounded number of edges
During an article I am writing, I encountered the following problem: Let $N=(G=(V,E),W,C)$ be a network with a graph $G$, a weight function $W:E\to R$ and an integer capacity function $C:E \to N$. Find a circulation $f$ with minimal cost $W(f)$ such that the number of edges used by the circulation (i.e., edges $e$ s.t. $f(e)\> 0$) is smaller than or equal to a parameter $r$.

Note that if $r=|E|$, the problem is simply the well-known circulation, which is solvable in polynomial time.

I tried to search "Google Scholar" and use variations of the cycle canceling (and other min cost flow) algorithms to solve the problem but with no successes.

# Answer
> 2 votes
After I posted the question in cstheory, I received an answer there.

> Your problem is NP-Hard and even hard to approximate via easy reductions from Steiner tree problem. Look at the following paper for more information. dl.acm.org/citation.cfm?doid=1077464.1077470.

# Answer
> 0 votes
I don't know of any existing algorithm, but perhaps you could think of some approach like:

1. Try some random triangles, pick a low flow cost circulation w
2. Remove all edges with weight \> w
3. If there is any node with degree just 2, remove the node and add the weights of the edges to create a new (longer) edge
4. Repeat steps 2 and 3, if possible
5. Start from the beginning with the new graph

You cannot get any closer to your final result when all the weights are pretty similar (differing about 3 times). So this seems like you should be able to get at least some O(1) approximation.

To get what the nodes were in the original graph, you have to remember which nodes were deleted from the middle of which edges and add them back afterwards.

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


title: Algorithm for wait-for graph

text:
# Question
Title: Algorithm for wait-for graph
During the process of deadlock detection, the wait-for graph can be obtained from the resource-allocation graph. To detect whether there is a deadlock using the wait-for graph, can topological sort be used?

By making a slight modification, i.e., instead of removing the source as done in usual topological sort, we can remove the node (here, node represents a process) which does not point to another node first and proceed in this manner. As soon as the algorithm detects that it cannot proceed further and there are still nodes existing in the wait-for graph, it can be concluded as deadlock.

Other tags are topological-sort and deadlock-detection.

# Answer
Hint: There is deadlock in the wait-for graph if the graph has directed cycles (why?). Perhaps topological sort is useful for detecting these.
> 0 votes

# Answer
IN single stance WFG the presence of cycle indicate that their is deadlock it is sufficient condition but in multi-instance WFG if the cycle is presence then we cant right away declare that their is deadlock it is just necessary condition not sufficient condition their might chance to presence. if the topological sorting is used then I think it always come up with the result that there is no deadlock just because topological order is acyclic graph and we know that deadlock to be present there should be presence of cycle .
> -1 votes

---
Tags: algorithms, operating-systems
---


# Question
Title: Differences between Church and Scott encoding
I'm kind of new to lambda calculus and I found this Wikipedia article https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott\_encoding

The section **Comparison to the Church encoding** presents a short comparison between Church and Scott encoding

**Church**

λx1...xAi.λc1...cN.ci (x1c1...cN)...(xAic1...cN)

**Scott**

λx1...xAi.λc1...cN.ci x1...xAi

Do you agree with the Church generic encoding description? The page specified that *citation is needed* for that description.

# Answer
It's correct *as long as* all the arguments $x\_1 ... x\_{A\_i}$ are recursive occurrences of the same structure. Otherwise there's no way to say what the Church encoding should be without more information.

That is the major difference between the Church and Scott encodings. If we think in terms of types, then for a fixed point type:

$T \cong F T$

the Church encoding of $T$ has a type like:

$(F r \to r) \to r$

while the Scott encoding has a type like:

$(F T \to r) \to r$

So, Scott encodings generally require some other source of recursion/iteration, both at the value level, because it only gives you access to one level of unfolding at a time, and at the type level (if you have one), because the fixed point type $T$ is still present in the type of the Scott encoding.

However, this means that Scott encodings are much better than Church encodings for some things. For instance, it's obvious how to write the (clamped) predecessor for Scott encoded naturals $\mathbb{N} = \forall r. r \to (\mathbb{N} \to r) \to r$:

```
pred n = n 0 (\pn -> pn)

```

However, for the Church encoded naturals:

$\mathbb{N} = \forall r. r \to (r \to r) \to r$

writing the predecessor function is a challenging exercise (and the resulting function is expensive).
> 3 votes

---
Tags: lambda-calculus
---


# Question
Title: What was Robert Floyd's algorithm for inserting brackets?
In page 71 of Mathematics for Computer Science (page 77 in the pdf) it says that "The Turing award (the “Nobel Prize” of computer science) was ultimately bestowed on Robert Floyd, for, among other things, being discoverer of a simple program that would insert the brackets properly \[into an arithmetic expression\]."

What was this algorithm?

Based on the page for Floyd's award, it looks like the algorithm can be found in this paper.

# Answer
> 12 votes
The seminal paper referred to is "Syntactic Analysis and Operator Precedence" (1963), which describes the operator precedence algorithm still used by many simple expression parsers today.

The basic approach described by Floyd was not exactly new. It was described by Edsger Dijkstra in 1961; Dijsktra's procedure was a pragmatic, special-purpose algorithm used to parse Algol-60, commonly referred to as the "Shunting Yard Algorithm". Floyd's contribution was to formalise and extend the idea, making it into a practical general-purpose parsing technique.

Floyd's approach to parsing was highly influential on another young parsing investigator of the time, Donald Knuth, whose 1965 paper "On the Translation of Languages from Left to Right" introduced the LR(k) parsing algorithm, capable of parsing a much larger set of languages than operator precedence parsing. However, it was not until 1969 when Frank deRemer invented the computationally manageable LALR(1) algorithm described in "Practical Translators for LR(k) languages" that Knuth's discovery moved out of the theoretical realm and into practical compiler construction.

Floyd's 1961 paper "An algorithm for coding efficient arithmetic operations", cited in the OP, was not about parsing ("inserting brackets properly") but rather about efficiently ordering the computation of the parsed expression so as to maximize the use of scarce CPU resources, based on the very limited CPU architectures common at the time. Modern CPU architectures demand different algorithms, but parts of Floyd's 1961 algorithm can be found in simple optimizations for minimising the stack size in stack-based virtual machines (or, equivalently, the number of temporaries required in three-address-code).

---

For reference, a quick summary of Floyd's operator precedence algorithm. The algorithm takes as input a *precedence grammar* $G$, which is a context-free grammar with the property that no right-hand side contains two consecutive non-terminals. (This definition allows unit productions and null productions; in practice, these would usually be removed before proceeding since they do not participate in the parsing algorithm.)

As usual, we will write $G = \langle N, T, P, S\rangle$, where $N$ is the set of *nonterminal symbols*, $T$ the set of *terminal symbols*, $P \subset N \times (N \cup T)^\*$ the set of *productions* and $S \in N$ the target (start) symbol. We will use uppercase letters to represent symbols in $N$, lowercase letters to represent symbols in $T$ and Greek letters to represent sentences which are elements of $(N\cup T)^\*$. We write $\alpha \Rightarrow \beta$ if $\alpha$ derives $\beta$ (that is, $\alpha = \alpha\_1 A \alpha\_3$ and $\beta = \alpha\_1\alpha\_2\alpha\_3$, where $A\rightarrow\alpha\_2 \in P$). Also, we write $\Rightarrow^+$ and $\Rightarrow^\*$ for the transitive closure and reflexive transitive closure of $\Rightarrow$.

Then we define three *precedence relations* over $T$: $\lessdot$, $\doteq$ and $\gtrdot$ , defined as follows:

$a \lessdot b \text{ if } A\rightarrow\alpha a B \beta \in P \text{ and either } B\Rightarrow^+b\gamma \text{ or } B\Rightarrow^+Cb\gamma$

$a \gtrdot b \text{ if } A\rightarrow\alpha B b \beta \in P \text{ and either } B\Rightarrow^+\gamma a \text{ or } B\Rightarrow^+\gamma aC$

$a \doteq b \text{ if either } A\rightarrow\alpha a b \beta \in P \text{ or } A\rightarrow\alpha a C b \beta \in P $

For an intuition about these symbols, think of a derivation being written with $\langle$ and $\rangle$ surrounding the strings replacing each nonterminal. Then $a\lessdot b$ holds if there is such a derivation where $b$ follows $a$ after a sequence of $\langle$s possibly followed by a single nonterminal. (Note that the *operator* property guarantees that there could not be two consecutive nonterminals.) In other words, ignoring nonterminals, $b$ is the first terminal in a reduction following $a$. $\gtrdot$ is analogous: $b$ is the first terminal following a reduction whose last terminal was $a$. (Again, the *operator* property guarantees that $b$ is not preceded by a nonterminal, since a nonterminal cannot follow a reduction.) $a\doteq b$ holds if $a$ and $b$ are consecutive terminals in a production, possibly separated by a (single) nonterminal.

Now, if the three precedence relations $\lessdot$, $\gtrdot$ and $\doteq$ are disjoint, we call $G$ an *operator precedence grammar*.

For simplicity, we will parse the augmented grammar

$$G' = \langle N\cup\\{S'\\}, T\cup\\{\\#\\},P\cup S'\rightarrow S\\#, S'\rangle$$

where $\\#$ is some symbol not in $T$. It's easy to verify that $a\lessdot \\#$ for every $a \in T$ and that there is no other precedence relation involving $\\#$. We also add a $\\#$ to the end of the input. Then we can parse the input as follows:

1. Create a parser stack $S$ consisting only of the symbol $\\#$.
2. For each input symbol $b$ in turn, from left to right:

1. While $TOP(S) \gtrdot b: \\;POP(S)$
    2. If $b = \\#$ and $top(S) = \\#$, $ACCEPT$ the input
    3. If $TOP(S) \lessdot b \text{ or } TOP(S) \doteq b: \\;PUSH(S, b)$. Otherwise, $REJECT$ the input.

In practice, we'll actually want to record the derivations discovered by this algorithm. If we $POP$ the stack in step 2.1, the popped symbols (both terminals and nonterminals) are accumulated into $X$, and just before we continue with step 2.2, we find the production in $P$ whose right-hand side is $X$, and output that production as a derivation step. If there is more than one such production, then we need some auxiliary algorithm to decide which one to use; usually, we sidestep the problem by requiring that the right-hand sides be unique. (This is also why it's common to eliminate unit and null productions, because the Floyd algorithm provides no clue whatsoever about when to insert their derivation steps.)

---

Like many others, I think Floyd's contribution to parsing theory was fundamental. But it is important not to be seduced by the beautiful simplicity of his algorithm. As Floyd himself noted, it suffers from two important issues:

1. It is not sufficient to parse many programming languages, whose grammars cannot conveniently be written as operator grammars with unique right-hand sides or do not yield disjoint precedence relations.
2. The fact that a string is accepted by the algorithm does not guarantee that the string is accepted by the grammar. Many syntactically invalid strings are accepted and must be filtered out using other algorithms.

Floyd's later work, including his investigation into bounded-context grammars, sought to overcome these shortcomings.

---
Tags: algorithms, reference-request, parsers, history
---


# Question
Title: Words generated by CFG whose parse tree contain even number of $X$
> Let $G$ be a context-free grammar with set of terminals $A$. Let $X$ be a non-terminal in $G$. Is the language of words over the alphabet $A$ with a syntax tree in which the non-terminal $X$ appears even number of times is context-free?

# Answer
> 1 votes
Add a new terminal $x$ to the alphabet, and replace $X$ with $xX$ in the right-hand side of all productions. Denote the corresponding context-free grammar by $G'$, and let $h\colon A \cup \\{x\\} \to A^\*$ be the homomorphism erasing $x$. Then your language is $$ h(L(G') \cap A^\*(xA^\*xA^\*)^\*). $$ Since the context-free languages are xlosed under homomorphism and intersection with a regular language, it follows that your language is context-free.

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


# Question
Title: Is every regular/context free langauge decidable in LogSpace?
I know all the regular languages are decidable but not sure whether it can be done in LogSpace.

# Answer
> 3 votes
For regular languages, we have $$ \text{REG = DSPACE}(O(1)) = \text{NSPACE}(O(1))$$ where REG is the class of regular languages. This can be easily seen from the equivalent formalisms of regular languages. A language is a regular language iff it is the language accepted by a deterministic finite automaton. A language is a regular language iff it is the language accepted by a nondeterministic finite automaton.

In fact, $\text{REG = DSPACE}(o(\log \log n))$. That is, $Ω(\log\log n)$ space is required to recognize any non-regular language \[1\].

For context-free languages, please see the answer by Yuval Filmus.

# Answer
> 3 votes
It is unknown whether context-free languages can be decided in logarithmic space. The best known result shows that they can be decided in nondeterministic space $O(\log^2 n)$. It is also known that if all context-free languages can be decided in deterministic logarithmic space then $\mathsf{L} = \mathsf{NL}$, which is considered unlikely.

For references, see this question and this question on cstheory.

---
Tags: regular-languages, terminology, decision-problem, space-complexity
---


# Question
Title: Efficient algorithm to find the nth number in a base-k numeral system with only different digits
I am looking for an efficient algorithm for the following problem.

There is a base-k numeral system, and we want to have some k-length numbers, but all of the digits must be different ones.

It would be useful, if all of the possible feasible numbers would be unequivocal sortable (so the given nth number is always the same one).

**An example to be clear:**

k=5

possible digits: 0 ... (k-1) -\> 0, 1, 2, 3, 4

we have a base-5 numeral system

we need numbers with length 5

possible feasible numbers:

01234

10234

02134

...

43210

**The goal is**, to find a way, that if I say, I need the 8th number, it will give me for example 34210 (and it will give me always this number, if I ask for the 8th one).

It is also important, that this algorithm should be efficient, if it is possible in O(1), or in P.

It would be also great, if the algorithm would not generate and store all of the possible feasible solutions, but somehow it could generate only that one appropriate number, which is the answer for the input.

I guess, there is no known P solution for this.

The brute-force and probably not the most efficient way would be, to generate and store all of the possible feasible solutions in a given order, and then we could answer any input, and the same input would generate always the same output. This solution satisfies all of the above criteria, but maybe there is a much more efficient algorithm to do this.

# Answer
> 1 votes
Your problem is known as *unranking permutations in lexicographic order*. Bonet, Efficient Algorithms to Rank and Unrank Permutations in Lexicographic Order describes efficient algorithms, and contains some pointers to the literature.

As described in the paper, more efficient algorithms are possible if you don't insist on lexicographic order.

---
Tags: permutations
---


# Question
Title: Is the language $K=\{u \in\{0,1\}^n\mid n \geq 0, \forall_{v \in\{0,1\}^n} (u+v) \in L \}$ regular?
> For two words $w,v \in\\{0,1\\}^\*$ of equal length, let $w+v \in\\{0,1,2\\}^\*$ denote the word in which the $i$-th word is the sum of $i$-th position of $w$ and $v$, as follows: if $w=a\_1 \ldots a\_n$ and $v=b\_1 \ldots b\_n$, then $w+v=c\_1 \ldots c\_n$, where $c\_i=a\_i+b\_i$ for each $i\in \\{1, \ldots, n\\}$.
>
> Assume $L \subseteq \\{0,1,2\\}^\*$ is a regular language. Decide whether the language $$K=\\{u \in\\{0,1\\}^n\mid n \geq 0, \forall\_{v \in\\{0,1\\}^n} (u+v) \in L \\}$$ is regular.

I would appreciate any hint as I don't know how to start. I know that the every word u+v can be easily converted to be over the alphabet $\\{0,1\\}^\*$ such that $h(a\_i) = 0$ if $a\_i=0$ and $h(a\_i) = 1$ if $a\_i=1$ and if $a\_i = 2$, then $h(a\_{i+1})=a\_{i+1}+1$. Then $u+v$ is just binary addition.

# Answer
> 1 votes
It might be easier to consider the complement of your language: $$ \overline{K} = \\{ u \in \\{0,1\\}^\* : \exists v \in \\{0,1\\}^{|u|} \text{ s.t. } u+v \in \overline{L} \\}. $$

You can now easily convert an NFA for $\overline{L}$ to one for $\overline{K}$ by replacing all edges labelled $1$ with edges labelled $0,1$ and all edges labelled $2$ with edges labelled $1$.

I'll let you figure out why this works.

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


# Question
Title: Algorithm to solve constraint satisfaction problems
I have group of people. Each person can be described by few characteristics:

```
age, occupation, city, favorite_color

```

I would like to generate 60 random people and combine them into pairs. With a constrain that no person in a pair can share any characteristic, for example I can't have two people in a pair whose **favorite\_color** is green.

I was thinking about using Backtracking algorithm to solve it.

What other algorithms I could use to solve this particular problem? I would like to research and implement some.

# Answer
Use an algorithm to find a perfect matching in a graph. Build a graph where each vertex represents a person, and draw an edge between each two people who don't share any characteristic, then look for a perfect matching. If none exists, you can throw away that data and generate a new random sample, and repeat until you find a valid solution.
> 1 votes

---
Tags: constraint-satisfaction, constraint-programming
---


# Question
Title: what are the conditions for two NFAs to be equivalent?
It's a pretty basic question, but I couldn't find an explicit answer in the book which I'm using, also when searching for it - I didn't find a reliable reference.

Correct me if I'm wrong but for two DFA's, $A , A'$ -given that $L(A) = L(A')$ doesn't mean that the DFA's are equivalent, so what are the (sufficient and necessary) conditions under which $A$ and $A'$ are equivalent? The closest I found was a claim states that in case $\bigcup\_{q\in Q} L(q) \neq \bigcup\_{q'\in Q'}L(q')$ (when $L(q) = \\{w\in\Sigma^\* : \hat{\delta}(q\_0,w) =q \\})$ then $A, A'$ are not equivalent.

# Answer
> 3 votes
As commented, they are equal when they accept the same language.

In practice:

Every NFA has one (1) minimized DFA, which is unique. If two minimized DFA are equal, the corresponding NFA's must also be equal.

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


# Question
Title: Efficient way to compute mod(w +1) or mod(w - 1) where w= 2^p
Knuth in his book provides a method of how to efficiently calculate mod(w +1) or mod(w-1) where w is a power of 2. I am not sure I could understand his assembly language completely.

Could you explain how to efficiently calculate those mod operations through mod(2^w) and can we extend it to a more common case of mod(w +/- c)?

Another question if we mod by a constant primary number in many places they mention different tricks compilers can do to avoid expensive division operation. Any ideas about those tricks?

# Answer
Mod(2^N-1) algo:

Split number into N-bit parts (i.e. extract digits in 2^N-ary system). Sum up these parts. If result is higher than 2^N-1 - reiterate. Because

```
256 mod 255 = 1
2*256 mod 255 = 2
256*256 mod 255 = 256 mod 255 = 1
...
A*2^N mod (2^N-1) = A
A*2^N*2^N mod (2^N-1) = A*2^N mod (2^N-1) = A
...

```

Mod(2^N+1) algo:

Split number into N-bit parts. Sum up these parts with changing signs. If result is higher than 2^N+1 - reiterate. Because

```
256 mod 257 = -1 mod 257
2*256 mod 257 = -2 mod 257
256*256 mod 257 = -1*256 mod 257 = 1
...
A*2^N = -A (modulo 2^N+1)
A*2^N*2^N = -A*2^N = A (both equations are modulo 2^N+1)
...

```

Mod(2^N-K) - multiply by K each next digit

Mod(2^N+K) - multiply by -K each next digit
> 1 votes

---
Tags: discrete-mathematics, arithmetic, hash, modular-arithmetic
---


# Question
Title: $\mathrm{BPEXP} = \mathrm{BPP} \iff \mathrm{BPEE} = \mathrm{BPE}$
Concerning about a wide variety of complexity classes, I have come up with the above conjecture.

Please, establish the claim in the title formally.

# Answer
This is true because both sides of the $\iff$ are false.

$\mathrm{BPEXP}\neq \mathrm{BPP}$ because if not, then $\mathrm{BPP} = \mathrm{EXP}$ and by padding, we have $\mathrm{BPEXP} = \mathrm{EEXP} \neq \mathrm{EXP} = \mathrm{BPP}$

$\mathrm{BPEE}\neq \mathrm{BPE}$ because if not, then by padding, we have $\mathrm{BPEEXP} = \mathrm{BPEXP}$, this implies that $\mathrm{BPEXP} = \mathrm{EEXP}$, and by padding again, we have $\mathrm{BPEEXP} = \mathrm{EEEXP} \neq \mathrm{EEXP} = \mathrm{BPEXP}$
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: $\mathrm{ZPEXP} = \mathrm{BPP} \iff \mathrm{ZPEE} = \mathrm{BPE}$
Please, establish the above claim formally. It seems that the structure of complexity classes has so much bizarre features everywhere.

For the $\Longrightarrow$ direction, a padding technique will work out. For the other direction, the time bounds are pushed down, so hardly any current technique would succeed.

# Answer
\[IKW02, Theorem 38\] relativizes, due to the relativization of \[IW98, Theorem 5\]. The original theorem states that $\mathrm{EXP} = \mathrm{BPP} \iff \mathrm{EE} = \mathrm{BPE}$.

We have that $\mathrm{EXP}^\mathrm{ZPP} = \mathrm{BPP}^\mathrm{ZPP}\iff \mathrm{EE}^\mathrm{ZPP} = \mathrm{BPE}^\mathrm{ZPP}$.

Now by padding upward from $\mathrm{P}^\mathrm{ZPP} = \mathrm{ZPP}$, $\mathrm{BPP}^\mathrm{ZPP} = \mathrm{BPP}$, we conclude that $\mathrm{ZPEXP} = \mathrm{BPP} \iff \mathrm{ZPEE} = \mathrm{BPE}$

\[**IKW02**\] R. Impagliazzo, V. Kabanets, and A. Wigderson. **In search of an easy witness: exponential time vs. probabilistic polynomial time**, http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IKW02/IKW02.pdf

\[**IW98**\] R. Impagliazzo and A. Wigderson. **Randomness vs. time: De-randomization under a uniform assumption**, http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW98/proc.pdf
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Divide-and-conquer: Determining the top two candidates and whether these two candidates received more than n/2 votes
*Suppose that each person in a group of n people votes for exactly two people from a set of candidates to fill two positions on a committee. The top two finishers both win positions as long as each receives more than n/2 votes.*

*Describe a divide-and-conquer algorithm that determines the top two candidates and whether these two candidates received more than n/2 votes.*

I have the answer (below), but there's one part I don't understand:

Our algorithm will take a sequence of 2n names (two different names provided by each of n voters) and determine whether the two top vote-getters occur on our list more than n/2 times, and if so, who they are. Actually for technical reasons we will need the top 3 vote-getters.\** The votes of each voter are adjacent. Note that we can have at most 3 people (but not 4) with more than half of the votes. Divide the list into two parts, the first half and the second half. (No one could have gotten more than n/2 votes on this list without having more than half votes in one half or the other, since if a candidate got less than or equal to half the votes in each half, then he got less than or equal to half the votes in all.) **Thus apply the algorithm recursively to each half to come up with at most six names (three from each half)**. Then run through the entire list to count the number of occurrences of each of these names to decide which, if any, are the winners. **This requires at most 12n additional comparisons for a list of length 2n**.

---

I don't understand why we are coming up with at most six names. I also don't get where the 12n comes from. To be more clear, I sort of understand why the 12n is a thing *given* the 6 names, but I don't understand *why* it's 6, and if it means 6 names for each step of recursion, or 6 names after all of the recursion (and if the latter, what happens during each step of recursion?).

# Answer
## The original problem is not quoted/rephrased correctly

Here is one correct version as it appears as exercise 18 in section 8.3 of the book *Discrete Mathematics and Its Applications*, 7th Edition by Kenneth H. Rosen, with slight modification.

> Suppose that each person in a group of $n$ people votes for exactly two people from a set of candidates to fill two positions on a committee. The top two finishers both win positions as long as each receives more than $n/2$ votes.
> Devise a divide-and-conquer algorithm that determines whether the two candidates who received the most votes each received more than $n/2$ votes. **If so**, determine who these two candidates are.

What is difference? As I have emphasized, only when it has been determined that each of the two candidates who received the most votes (the top two candidates) has received more than $n/2$ votes, the desired algorithm is required to determine these two candidates . In other word, if it has been determined that at least one of the top two candidates received at most $n/2$ votes, the algorithm is not required to determine these candidates.

The catch here is that **it is possible to determine whether the top candidate received more than $n/2$ vote without identifying who is the top candidate**. It is also possible to determine whether the second top candidate received more than $n/2$ vote without identifying who is the second candidate. For example, if we are able to ascertain the most votes received by any single candidate is at most $n/2$, which can happen when we have checked enough but not all of the votes (so we might not be able to identify who are the top candidates), then we are sure that none of the top two candidates received more than $n/2$ votes.

On the other hand, by its very nature, **any (usual) divide-and-conquer algorithm cannot find the top (two) candidates unconditionally**. The idea is that it can happen that the top candidates overall is not among the top candidates in either half of the list. In fact, it can happen that the top candidate overall is the bottom candidate in each half of the list. For example, 10 people can vote in the following way, $(A,B), (A,B), (A,B), (C,D), C,D), (E,F), (E,F), (E,F), (C,D), (C,D)$. While $C$ and $D$ are the top candidates overall, they are the bottom candidates voted by the first 5 people and they are the bottom candidates voted by the other 5 people.

---

The "answer" given by the OP, the fourth paragraph in the question, which starts with "our algorithm" and ends before the separator line, is in fact a part of an answer key. For brevity, I will refer to it as "the answer key".

## How to understand the answer key

You can check the other cool answer written by D.W., which includes a very detailed analysis of the answer key.

D.W.'s answer describes in great detail, according to the answer key, an algorithm that returns a list of three candidates which contains all the candidates who got more than $n/2$ votes and possibly other candidates. More specifically, if a candidate got more than $n/2$ votes, then he/she must be in the returned list. However, the list may contain people who did not get more than $n/2$ votes. It can also happen that none of the people in the returned list is the top candidate, or the second top candidate, or the third top candidate.

D.W.'s answer also explains clearly "why we are coming up with at most six names" as well as "where the $12n$ comes from".

I have confirmed that D.W.'s algorithm is correct (since he, in his modest way, claim he does not "know whether this algorithm is actually correct") in that it conforms to the answer key and it is a full answer to the original problem except it omits the easy steps such as "if so, determines who these two candidates are".

## A better written problem

It turns out, as you must have noticed by now, somewhat subtle to understand exactly what is the requirement of the original problem. Here is my version of the problem that should be much clearer, at least for me.

> Suppose that each person in a group of $n$ people votes for exactly two people from a set of candidates. Devise a divide-and-conquer algorithm that determines all candidates who received more than $n/2$ votes.

If you are careful, you may point out the my version missed "... to fill two positions on a committee. The top two finishers both win positions as long as each receives more than n/2 votes". Well, although it is interesting to know that election goal and election rule, it has nothing to do with the specification of the desired algorithm. You may also point out that my version does not require "if so, determine who these two candidates are". Well, if we have determined all candidates who received more than n/2 votes, the number of whom is at most 3, then by just counting the number of votes received by each of those candidates, we can, easily, "if so, determine who these two candidates are".

## An interesting algorithm as an exercise

There is **an algorithm using linear time and constant space** that determines all candidates who received more than $n/2$ votes. The construction of such an algorithm is left as an intriguing and challenging exercise for the readers who has read thus far.

Thanks to Tom van der Zanden, who pointed out a typo in my previous formulation of the exercise.
> 2 votes

# Answer
I can understand why you are finding this unclear. The sketch of a solution that you quote is pretty sparse, and it leaves it to you to fill in details. Here is how I interpret the proposed algorithm:

Algorithm $F\[1..n\]\[1..2\]$):
1. If $n=1$, return $\\{A\[1\]\[1\], A\[1\]\[2\]\\}$. Otherwise:
2. Set $S\_L := F(A\[1..n/2\]\[1..2\])$ and $S\_R := F(A\[n/2+1..n\]\[1..2\])$ and $S := S\_L \cup S\_R$.
3. For each $x \in S$, count the number of times that $x$ appears in $A\[1..n\]\[1..2\]$ and sort the $x$'s by that count.
4. Return the three values that occur the most often in $S$ (breaking ties arbitrarily).

where $A\[i\]\[1\]$ denotes the first vote from the $i$th voter and $A\[i\]\[2\]$ the second vote from the $i$th voter. At the end, after running $F(A\[1..n\]\[1..2\])$, we take the three values returned by this algorithm and check which (if any of them) have received at least $n/2$ votes.

The running time of this algorithm satisfies the recurrence relation

$$T(n) = 2 T(n/2) + O(n).$$

(Why? It's easy to see that $F$ returns at most 3 elements, so $|S| \le 6$. Each iteration of step 3 can be done in $O(n)$ time, and we do only $6=O(1)$ iterations of the loop, so the total running time for steps 3 and 4 is $O(n)$.) This recurrence solves to $T(n) = O(n \log n)$.

So, this gives an $O(n \log n)$ time algorithm for the problem.

I don't know whether this algorithm is actually correct. I'm just trying to explain what algorithm I believe they are proposing, and to explain their running time analysis. I haven't tried to prove the algorithm correct. The solution you listed appears to sketch the key ideas behind such a proof (or, at least that's the claim). I haven't tried to fill in the details and verify carefully that the proof works out, so you should do that if you care, but it looks plausible to me -- all the ideas make sense to me.

Now, to answer your questions: The reason we come up with only 6 names is that each recursive call returns at most 3 names, and we perform two recursive calls, so we end up with at most $3+3=6$ different names in $S$. Why $12n$? Because each iteration of the loop in step 3 takes $2n$ comparisons (you compare $x$ to each element of $A\[1..n\]\[1..2\]$, and there are $2n$ such elements), and you do at most 6 iterations of the loop, so the total number of comparisons in step is at most $6 \times 2n = 12n$.

I hope this answers your questions and makes the proposed solution clearer.
> 1 votes

---
Tags: algorithm-analysis, divide-and-conquer
---


title: Examples of non-sparse languages

text:
# Question
Title: Examples of non-sparse languages
All I could find is an example of sparse language.

I understand that I need to design a language whose all strings generation should not be bounded by a polynomial function, but I feel all the languages string generation is bound to at least one polynomial, so I am unable to design a language L whose strings are not bounded to a polynomial function.

# Answer
> 1 votes
For a language $L$, let's write $\\|L\\|\_n$ for the number of length-$n$ strings it contains. So $L$ is sparse if there is a polynomial $p$ such that $\\|L\\|\_n\leq p(n)$ for all $n$. The key point is that, for a language to be sparse, we must be able to pick just one polynomial that works for all $n$: you're not allowed to use a different polynomial for each $n$.

For example, suppose that you wanted to prove that the language of strings over $\\{0,1\\}$ with at most two $1$s is sparse. You can't say "Well, for $n=3$, there are seven valid strings, and $7 \< n+5$ for $n=3$. And for $n=4$, there are eleven valid strings, and $11 \< n^2-4$ for $n=4$, and..." You have to pick just one polynomial that works for all values of $n$: in this case, $n^2$ works, so the language is sparse.

So, for a non-sparse language, $\\|L\\|\_n$, when considered as a function of $n$, must grow faster than any possible polynomial. The simplest examples of functions that grow faster than polynomials are exponentials. Conveniently, $\\{0,1\\}^\*$ has $\\|\\{0,1\\}^\*\\|\_n=2^n$ for all $n$. So, whatever polynomial $p$ you pick, $\\|\\{0,1\\}^\*\\|\_n\>p(n)$ for all large enough $n$. Therefore, $\\{0,1\\}^\*$ is not sparse.

Another example of a non-sparse language is the complement of a sparse language. If $\\|L\\|\_n\leq p(n)$ for all $n$, then $\\|\overline{L}\\|\_n\geq 2^n-p(n)$ and this grows faster than any polynomial if $p$ is a polynomial.

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


# Question
Title: A data structure to do a specific lookup fast
I have 30,000 items; each item has 30 parameters that take values from 0 to 5. These parameters are named $p\_0$ to $p\_{29}$ and their value is an integer between 0 and 5. I want to store these items in a data structure where I can do this lookup quickly: find the parameter with a given value for $(p\_0, \ldots, p\_{29})$.

All items that have $p\_i$ less than or equal $x\_i$.

So having 50 values $x\_0$ to $x\_{29}$ I run the above lookup and it returns all items that satisfy it. I used PostgreSQL and created indices for each of these parameters. Querying in PostgreSQL happens in ~20ms. I stored them in a Python list and did a simple `[i for i in items if all(i['p' + str(j)] < n[j] for j in range(30))]` and it takes ~250ms. By using 30 dicts each containing 6 sets for different values of each parameter and doing the lookup in dicts and intersecting sets I was able to each ~10ms (a bit memory consuming but not that much). Does anyone know about a better data structure to do this query faster? Memory is not an issue as long as it's below 2GB.

In formal language I'd describe it this way: I have 30,000 records; each record contains 30 values, each in range 0..5:

```
type Record: array[1..30] of 0..5
var Store: array[1..30000] of Record

```

I need to find all records in the store, where each element is smaller than in the target one:

```
procedure Find(target: Record):
  for item in Store:
    if item[0]<=target[0] and item[1]<=target[1] and ... and item[30]<=target[30]:
      print item

```

I need to perform Find quick, and can preprocess the Store to make the lookups faster. What data structure and algorithm can I use?

# Answer
> 2 votes
Using SSE2 operations, you can save the entire dataset in 512 KB and search through it, with 4-core CPU, is less than 10 microseconds.

PCMPB+PMOVMSKB instructions will give you 16-bit mask made from 16 byte-wide comparisons. You need to combine two such masks as a\<\<16+b and make sure that result is all 0s.

---

Even faster approach is to make bitmap for each `p[i]<k` condition, overall you need 30\*6=180 bitmaps. Each bitmap takes 30K/8=3.75 KB, overall 675 KB.

You need to AND-combine 30 maps corresponding to chosen x\[i\], i.e. AND-process 675/6=112.5 KB of data. With 128-bit SSE operations, this requires 7K operations, and on the same 4-core CPU, it's less than microsecond long.

# Answer
> 1 votes
This is how I optimized it so far: created python dictionary that contains 30 keys for 30 parameters, each value is another dict that contains keys from 0 to 5 (including) for different values each parameter can take. then the values of this final dicts are sets that include indices of the items in original list of items. To look up the query, I simply intersect the relevant sets finding them with fast dict lookups. To optimize it further I sort sets that I want to intersect by their size before intersecting them so that intersections happen with smaller sets.

Suppose that all items are stored in list `L`:

```
L = [
    {"entry":"e1","p0":0,"p1":2,"p2":3,"p4":0,...}.
    {"entry":"e2","p0":5,"p1":1,"p2":0,"p4":4,...},
...
]

```

I build the above mentioned dict like this:

```
index = {p + str(i): {
            j: {k for k in range(len(words))
                if words[k]['p' + str(i)] <= j} for j in range(5)
        } for i in range(30)}

```

It just runs once and takes few seconds. Then to lookup I run:

```
[L[i]['entry'] for i in sorted(functools.reduce(
            operator.and_,
            sorted(
                [index[p + str(i)][x[i]]
                    for i in range(30)],
                key=lambda set: len(set),
            ),
        ))]

```

It runs in ~5ms and is 4 times better than Postgresql results (as expected because it runs in memory with no disc usage.) But I think it's not smart enough, I'm consuming lots of memory, it's alright for 30,000 items and only 5 values which is the requirements of my real world problem, but I'm still curious to know if this problem has a better solution with less memory usage or even faster?

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


# Question
Title: Merging $k$ sorted lists in $O(n\log k)$ time
This question is based on a solution of Laura Toma to a question from CLRS (#6 on the sheet).

**Question:** Give an $O(n\lg k)$-time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: use a min-heap for $k$-way merging.)

**Solution:** The straightforward solution is to pick the smallest of the top elements in each list, repeatedly. This takes $k − 1$ comparisons per element, in total $O(k · n)$. As the hint suggests, the idea for the “improved” solution is to keep the smallest element from each list in a heap; each element is augmented with the index of the lists where it comes from. We can perform a DeleteMin on the heap to find and delete the smallest element and insert the next element from the corresponding list. Analysis: It takes $O(k)$ to build the heap; for every element, it takes $O(\lg k)$ to DeleteMin and $O(\lg k)$ to insert the next one from the same list. In total it takes $O(k + n \lg k) = O(n \lg k)$.

---

So I understand everything that's going on here. I just have one little question about this part:

$$O(k+n\lg k)=O(n\lg k)$$

The solution states:

> It takes $O(k)$ to build the heap; for every element, it takes $O(\lg k)$ to DeleteMin and $O(\lg k)$ to insert the next one from the same list. In total it takes $O(k + n \lg k) = O(n \lg k)$.

So in my head I want to do something like this:

$$O(k+n(2\lg k))=O(k+n\lg k)=O(n\lg k)$$

Is this also correct since there are two instances of $O(n\lg k)$? Is the solution just skipping over that one part assuming it's trivial?

# Answer
Yes, you are right.

$O(c \cdot f(n)) = O(f(n))$ for any constant $c$.

It may also be written (maybe even more clear) in the form $$O(k) + O(n \lg k) + O(n \lg k) = O(n \lg k)$$
> 1 votes

---
Tags: algorithm-analysis, mergesort
---


# Question
Title: Performance - Computer Organization and design
A popular app takes 10 seconds to execute on a 11 watt smartphone A, and it takes 8 seconds to execute on a 13 watt smartphone B. The app is a bigger drain on the battery on which smartphone?

# Answer
> 1 votes
According to Wikipedia, 1 Watt equals 1 joule per second; here joule is a unit of energy. Using this, you can come up with a formula that relates the power of a machine, the number of seconds that the machine works, and the amount of energy expended. Using this formula, you can calculate the amount of energy spent in your two scenarios, and deduce the answer to your question.

---
Tags: performance
---


title: On the exponential hierarchy?

text:
# Question
Title: On the exponential hierarchy?
We know $P\subseteq PH\subseteq PSPACE\subseteq EXP\subseteq NEXP$.

1. Is it known or believed that $\Delta\_2^{exp}=EXP^{NP}\subseteq NEXP=\Sigma\_1^{exp}$ and/or $EXP^{PH}\subseteq NEXP$?
2. Does $NP=coNP\iff NEXP=coNEXP$ hold?

Note $NEXP=coNEXP\implies \Delta\_2^{exp}=\Sigma\_1^{exp}$?

# Answer
1) Both two unbelieved scenarios that $\mathrm{NP}=\mathrm{P}$ and $\mathrm{NP}=\mathrm{EXP}$ implies that $\mathrm{EXP}^\mathrm{NP} = \mathrm{NEXP}$ and $\mathrm{EXP}^\mathrm{PH}=\mathrm{NEXP}$. So we cannot refute these two claims at present.

On the other hand,

* assuming $\mathrm{EXP}^\mathrm{PH}=\mathrm{NEXP}$ would imply $\mathrm{BPP}\neq\mathrm{NEXP}$, since $\mathrm{BPP}\subseteq\Sigma\_2^{p}$ and $\Sigma\_2^p\subsetneq\mathrm{\Sigma\_2^{exp}\subseteq\mathrm{EXP}^\mathrm{PH}}$
* assuming $\mathrm{EXP}^\mathrm{NP}=\mathrm{NEXP}$ would imply $\mathrm{P}^\mathrm{NP}\neq\mathrm{NEXP}\cap\mathrm{co}-\mathrm{NEXP}$

2) First of all, your implication that $\mathrm{NEXP}=\mathrm{co}-\mathrm{NEXP}\implies\Delta\_2^{exp}=\Sigma\_1^{exp}$ is not known since exponential-time hierarchy does not possess the upward collapsing property like polynomial-time hierarchy (some inner collapse at some level does not necessarily imply the collapsion of all the exponential-time hierarchy to that level).

Beside from that, $\mathrm{NP}=\mathrm{co}-\mathrm{NP}\implies\mathrm{NEXP}=\mathrm{co}-\mathrm{NEXP}$ is true by standard translation technique, but the opposite implication is not known due to the difficulty in achieving the **downward closure** theorems for non-determinism and co-non-determinism. It has been done for probabilistic classes (zero-sided, one-sided, bounded-error all done, but general probabilistic $\mathrm{PrTime}$ still open). For more details on downward closure theorems, see the reference in this answer.
> 2 votes

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


# Question
Title: IS $LOGSPACE\subsetneq QMA$ an open problem?
Having read some chapters of *Computational Complexity: A Modern Approach*, I see no time or space hierarchy theorem which applies to this case. As far as I can see, we know the following inclusions:

$L \subseteq NL \subseteq P \subseteq BPP \subseteq BQP \subseteq QMA$

but no inclusion is known to be strict, and it is not known whether at least one of these inclusions is strict. The statements $L=P, P=BQP, BQP=QMA$ are all unsolved, so I am free to conjecture that they are all true, or all false. I know that it is absolutely obvious that $L\subsetneq QMA$, because to go from one to the other one must (1) remove the logarithmic space bound, (2) introduce randomness to the algorithm, (3) add quantum and (4) add nondeterminism. This question is interesting because each of these augmentations is believed but not proved to add computational power (with the possible exception of (2)), they correspond to their respective flagship inclusions above, and this question captures all of them simultaneously, showcasing an enormously long distance unsolved relationship. It is also interesting because to my knowledge it is the longest-distance unresolved inclusion between two natural complexity classes (classes that arise naturally in studying theory and which capture fundamental notions of resource-bounded computation, but this point is subjective).

The only strict inclusions I can find are $L\subsetneq Space(n) \not= NP$ and $L \subsetneq PSPACE \supseteq P$. The first is not satisfying because $Space(n) \subsetneq NP$ is open.

This also begs the question, alright if these augmentations individually are hard to reason about, but surely you cannot add them all at once without changing your complexity class? And is it easier to prove such weaker strict inclusions?

(and, tongue in cheek, if the answer to my question is *yes*, what have complexity theorists been up to the past few decades?)

# Answer
Widely open, I can tell. $\mathrm{QMA}\subseteq\mathrm{PP}$ is known. But, $\mathrm{PP}$ has been only separated from $\mathrm{uniform}$-$\mathrm{TC}^0$ up to now. So, even the stronger claim $\mathrm{L}=\mathrm{PP}$ is still unrefutable.

From the Wikipedia article https://en.wikipedia.org/wiki/PP\_(complexity)#PP\_compared\_to\_other\_complexity\_classes, $\mathrm{PP}$ strictly contains $\mathrm{TC}^0$, the class of constant-depth, unbounded-fan-in uniform boolean circuits with majority gates. (Allender 1996, as cited in Burtschick 1999)

Allender, E. (1996). "**A note on uniform circuit lower bounds for the counting hierarchy**". Proceedings 2nd International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science. 1090. Springer-Verlag. pp. 127–135

Burtschick, Hans-Jörg; Vollmer, Heribert (1999). "**Lindström Quantifiers and Leaf Language Definability**". ECCC TR96-005
> 2 votes

---
Tags: complexity-classes, quantum-computing
---


# Question
Title: Request for examples to show various types of subproblems in dynamic programming
Chapter 6 of "Algorithms" by Dasgupta, Papadimitriou, and Vazirani summarizes four types of subproblems that are quite common in dynamic programming. They are

1. prefix/postfix of a string/sequence/array
2. both prefixes/postfixes of a pair of strings/sequences/arrays
3. an interval of a string/sequence/array
4. a rooted subtree

What are the other types of subproblems (and examples/references) for dynamic programming?

---

***Added:*** In a comment on this post, JeffE mentioned:

> Tables are sometimes used. Dynamic programming over trees (for example: maximum independent set) doesn't normally use a table \[=array\] to memoize the recurrence; it uses a tree, or in some cases a tree of arrays, or an array of trees, or in some cases a Cartesian product of trees. Similarly for dynamic programming over dags or dynamic programming over tree decompositions for graphs of bounded treewidth.

I would like to know dynamic programming examples over, e.g., a tree of arrays, an array of trees, a Cartesian product of trees, tree decompositions, or more general graphs.

# Answer
Everything you need could be found on Topcoder.com (TCC for short).

Start with Dumitru's tutorial. Done that, you should be able to integrate the DP technique on various structures, like *2D grids*, *narrow ribbons*, *convex polygons*, etc. to name just a few.

An archive of DP problem on TCC: https://www.topcoder.com/tc?module=ProblemArchive&sc=2&sd=desc&cat=Dynamic+Programming

And the **match editorial** is the best collection: https://community.topcoder.com/tc?module=Static&d1=match\_editorials&d2=archive

I have learnt so much from these. Unfortunately, this editorial series stopped since 2008. From that time on, the SRMs are only discussed in the forum like these more recent SRMs: https://www.topcoder.com/blog/single-round-match-735-editorials/

A tagged search produces this: https://www.topcoder.com/blog/tag/srm-editorials/ So you may easily access all the recent SRMs.

**SRM**: *Single Round Match* (TCC is the arena of *online competitive programming*)

---

Please note that TCC has been gone through various reconstruction (since the integration with Data Science market). As a (unwanted) consequence, many links are broken but can be fixed by modifying some middle parts (as often the cases for decades-old websites)
> 1 votes

---
Tags: algorithms, reference-request, dynamic-programming
---


# Question
Title: Push down automata for $\{a^n b^n c^n | n \ge 0\}$
I am learning about context free languages.

I understand how $\\{a^n b^n c^n | n \ge 0\\}$ can be shown to be not context free using the pumping lemma for CFL's.

Intuitively however it seems that a pushdown automata to recognize $\\{a^n b^n c^n | n \ge 0\\}$ can be constructed. This PDA would initially push two $a$'s into its stack whenever it sees an $a$ in the input. It would change state when it first encounters a $b$ and pop a single $a$. It would continue to pop $a$'s for every b in the input until it encounters a $c$. It would again change state and pop single $a$'s for every c encountered. If the stack is empty at the end of the input the language is recognized as $\\{a^n b^n c^n | n \ge 0\\}$.

There must be something I am overlooking whilst constructing the PDA as a language is context free if its has a PDA recognizing it. Please point out my mistake.

# Answer
> 14 votes
Your PDA would also accept strings of the form $a^nb^ic^j$ where $i+j=2n$ and $i,j\>0$. For example the string "aaabbbbbc" is accepted. There is no way to tell that there are exactly $n$ $a$'s still remaining on the stack once you've finished reading the $b$'s.

# Answer
> 0 votes
The PDA would accept the strings which are not present in the languages . For example a string 'aabccc' can also be accepted by the PDA by popping out each a when it encounter b by changing the state anf when it encounters 'c' it will again pop out 'a' . Therefore PDA for a^nb^nc^n is not possible .

# Answer
> -1 votes
You are trying to say that for every a read from the tape you will push two a's on the stack then string aabccc will also be accepted by this PDA which is not part of given language

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


# Question
Title: Complexity classes that are low for equivalent definitions of $\mathrm{PP}$
**What is the biggest complexity class that is low for each other equivalent definition of $\mathrm{PP}$?**

I already know that $\mathrm{PP}^\mathrm{BQP}=\mathrm{PP}$. This is a lowness result using standard definition of $\mathrm{PP}$.

Since, it is known that $\mathrm{PP} = \mathrm{PostBQP} = \mathrm{PQP}$.

1. If we use $\mathrm{PostBQP}$, then what is the biggest complexity class that is low for this equivalent definition.
2. Similarly, if we use $\mathrm{PQP}$, then what is the biggest complexity class that is low for this equivalent definition.

For known results: https://en.wikipedia.org/wiki/PP\_(complexity)

# Answer
> 0 votes
$\mathrm{BQP}$ is semmingly the largest class that is low for $\mathrm{PP}$.

Using the definition of $\mathrm{PostBQP}$ (a $\mathrm{BQP}$ circuit with postselection) and $\mathrm{BQP}^\mathrm{BQP}=\mathrm{BQP}$ we can also derive that $\mathrm{PostBQP}^\mathrm{BQP}=\mathrm{PostBQP}$

In comparison to $\mathrm{MidBitP}$ (denote $\mathrm{MP}$) for short, all these classes are low for $\mathrm{MP}$: $\mathrm{ModPH}$, $\mathrm{BPP}^{\oplus \mathrm{P}}$. The last one ($\mathrm{BPP}^{\oplus \mathrm{P}}$) already contains $\mathrm{PH}$. That is the power of the middle bit. More on middle bit, see here.

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


# Question
Title: Any evidence that one way functions exist?
There is no known proof that one way functions exist. But what is the heuristic evidence that they exist?

I sometimes read that the existence of cryptography is heuristic evidence that they exist. E.g. the ciphertext from a block cipher like AES is easily computable if you know the plaintext and key, but the key is not easily computable if you know the plaintext and ciphertext.

This is seen as evidence that AES might be a one way function, but to me it simply suggests that we don't know how to invert AES. In other words, it seems like this is an algorithm-search problem that is very hard (finding the key inversion algorithm), not that that algorithm doesn't exist.

**Is my reasoning correct? Whether it is or not, what is the heuristic evidence that one way functions exist?**

# Answer
> 3 votes
AES is widely believed to be secure: many smart people have tried to break it and haven't been able. This is not a proof, and it is arguable exactly *how* strong this evidence is, but it does count as heuristic evidence of some sort. The fact that we haven't been able to find an algorithm to break AES does seem to count as some sort of heuristic evidence that no such algorithm exists -- again, not ironclad, not a proof, arguable how strong the evidence is, some might even call it weak evidence, but still evidence of some sort.

Moreover, it is easy to prove that if AES is secure, then the function $F$ defined by

$$F(k) = \text{AES}\_K(0)$$

is one-way, where $0$ represents the block of 128 zero bits. To be precise, if AES is a secure PRP, then $F$ is a secure one-way function -- this latter statement can be mathematically proven in a 100% rigorous way. Here by "security" I refer to concrete security rather than asymptotic security. If you're interested in asymptotic security, you'll need something more.

Thus, this is heuristic evidence that one-way functions exist: in particular, we have heuristic evidence that the $F$ defined above is one-way. You can form your own judgement about how persuasive or how strong this evidence is; that probably comes down to a personal judgement.

---
Tags: cryptography, one-way-functions
---


title: DFS on reversed graph

text:
# Question
Title: DFS on reversed graph
I was watching a lecture on determining the strongly connected components of a graph using Kosaraju's algorithm and the lecturer claimed one can *easily* walk the edges in reverse fashion.

While I see this happening with an adjacency matrix representation(the reverse is the matrix transpose, and you can determine its elements on demand), I'm having a hard time coming up with a solution in the case of the adjacency list representation.

Any hints?

# Answer
> 1 votes
You can iterate over all of the edges in $O(|E|)$ time. So, construct a copy of the graph with reversed edges as follows: iterate over all the edges, and as you examine each edge, add the reversed edge to the copy. That takes $O(|E|)$ time in total, and you only need to do it once, as a pre-processing step. Now, during Kosaraju's algorithm, if you ever need to walk edges in a reversed fashion, you can just refer to the reversed graph you created earlier.

---
Tags: graphs, graph-traversal
---


title: Merge sort mxn matrix

text:
# Question
Title: Merge sort mxn matrix
The question is as follows:

I am new to this, and I do not understand how to apply divide and conquer to a matrix, the algorithm that I have come up with is as follows (I am not sure if I am correct)

I thought I can divide the matrix into a matrices of 3 x 3 and 2 x 3 first. Then I will apply sorting of rows over column individually on both the matrices. Finally I will copy the second matrix sorting result over to the first sorted matrix. However, my problem is how do I sort the matrix first in to some order so that my division will yield a correct partition else what happens is, post copy I have to again sort (Which I thought is probably wrong)

# Answer
As far as I can see, "sort the rows of the matrix, with respect to their columns" means that you're supposed to sort the rows lexicographically. That is, the row $$a\_1\ a\_2\ \ldots\ a\_n$$ comes before $$b\_1\ b\_2\ \ldots\ b\_n$$ if and only if there's some $i$ such that $a\_j=b\_j$ for $j\<i$ and $a\_i\<b\_i$.

As far as the divide and conquer goes, it doesn't matter that it's a two-dimensional matrix. You're trying to sort a collection of "things" according to some ordering on "things". These "things" happen to be the rows of some array but that doesn't make any difference to the algorithm.
> 1 votes

---
Tags: matrices, mergesort
---


# Question
Title: Does the set $\{10^n \mid n\geq1\}^*$ include $10100$?
Consider the following set constructed with a regular Kleene-star operation: $$ \\{10^n \mid n\geq1\\}^\* $$

Would something like $10100$ be in this set? I know $1010,100100100,1000,$ etc would be, but I'm not sure if you can change $n$ per repetition and have it be something like $10100, 101001010010$, etc.

# Answer
**Short answer:** Yes. $10100$ is included.

**Long answer:**

Let's go through how this particular set is constructed. First, the expression $$ 10^n $$ (in this context) denotes a single string consisting of a $1$ followed by $n$ $0$s (so the string depends on one variable $n$). Then, the set $$ \\{10^n \mid n \ge 1\\} $$ denotes the set of strings $\\{10, 100, 1000, 10000, \ldots\\}$. This set can also be denoted using the Kleene-star operation as $100^\*$ or $10^+$. Note that this set does not depend on $n$ -- rather, $n$ is just a dummy variable used to describe the elements of the set.

Finally, the set $$ \\{10^n \mid n \ge 1\\}^\* $$ then denotes a concatenated sequence of elements of the original set, like $10100$, $1000$, $1010000010$, etc. When you use the $\*$ operation, the string used each time does not have to be the same (that is, you can change $n$ for each repetition). So you can do $10$ first, then $100$, then $10$ again, etc.
> 8 votes

---
Tags: regular-expressions, kleene-star
---


# Question
Title: Maximizing quantities/length in buckets to match each other
I have a use case, real one, and I'm trying to come up with an efficient maximization algorithm to solve it.

I'll try to simplify, with a simple analogue, and after will explain the real world use case:

### Analogue:

Imagine you have 2 buckets of springs. Each spring has 2 properties: resting length, and maximum stretching length. Some springs are basically just rods, and resting length = maximum stretch length.

Your job is to maximize **length** of joined springs (& rods) in each bucket, such that the length of the 2 joined springs in the 2 buckets match exactly.

### Example:

A bucket of springs $S\_k$ is a non-empty multiset of intervals $\[i,j\]$, where $i$ denotes the "resting length", and $j$ denotes the "maximal stretch length". For example, if the two buckets are

$$\begin{align\*} S\_1&=\\{\[2,4\],\[2,4\],\[4,4\]\\} \\ S\_2&=\\{\[1,1\],\[2,4\],\[13,15\]\\} \end{align\*}$$ then the maximum achievable length is 5, since $2 + 3 = 1 + 4$ and $2 \in \[2,4\]$ and $3 \in \[2,4\]$ and $1 \in \[1,1\]$ and $4 \in \[2,4\]$.

Note that if the last spring in $S\_2$ would have been $\[12,15\]$ instead of $\[13,15\]$, the maximum length would have been $12$ (by the choice $4+4+4=12$). But since lengths in each bucket must match exactly, we end up with only $5$.

### Real (boring) problem:

My use case is from the finance world. I'm trying to match buy orders & sell orders for different amounts. Some of the orders can be partially accepted, whilst other must be strictly accepted or rejected. The orders I can partially accept, also specify the minimum amount it must be accepted with.
Each order is a "spring" in the analogy, where "resting length" is minimum accepting amount, and "maximum stretching length" is the full amount. The 2 buckets are the buy orders & sell orders.
Also, note that for now I've been asked to maximize **amounts**, but a further complication of the algorithm would be to maximize both amount & price. Either by preferring amount over price, and when there's a choice, to prefer the better price (lower for buy, higher for sell), or by maximizing total revenue (sell price * amount - buy price * amount).

### Just for fun

Try to generalize to any number of $n\>1$ buckets. In a valid solution, all buckets must end up with the same total length.

P.S. To be clear, I haven't solved it efficiently myself. And I am still looking for an efficient way to do the matching. I'm interested in the subset of orders, and not just the maximal amount that can be matched. Also, this kind of reminds me of bean packing problem (NP complete), because of the strict orders (rods), but not quite. Even if it is NP complete, I'm still gonna implement it (inefficiently), since mostly it'll work on a small number of orders (pretty sure it's gonna be OK). But I have a hunch there's a dynamic algorithm somewhere that can be more efficient.

# Answer
I would solve this problem with an SMT solver like z3. Example in Python:

```
import z3

buckets = [
    [(2, 4), (2, 4), (4, 4)],
    [(1, 1), (2, 4), (13, 15)],
]

solver = z3.Optimize()

m = z3.Int("m")

for bnr, bucket in enumerate(buckets):
    springs = []
    for b, (lo, hi) in enumerate(bucket):
        include_spring = z3.Bool(f"is{bnr},{b}")
        spring = z3.Real(f"s{bnr},{b}")
        solver.add(lo <= spring)
        solver.add(spring <= hi)
        springs.append(include_spring * spring)

    solver.add(z3.Sum(springs) == m)

solver.maximize(m)
solver.check()

model = solver.model()
print(solver.model())

```

The constraints are easy to express and SMT solvers are really quite powerful nowadays.
> 2 votes

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