# Question
Title: Proving that Turing Machine M runs in time $O(2^{dn})$
I'm trying to solve this question in order to review for my exam, and this one has got me a bit stumped. From the looks of it, it seems like a fairly straight-forward question, but I can't figure out what steps to begin with.

> Let $M$ be a linear-space Turing machine consisting of a single tape. We say $M$ is a linear-space Turing machine if M halts on every input, and if there are constants $c$ and $n\_{0}$ such that for all inputs $x\in \Sigma^{\ast}$ of length $n\geq n\_{0}$, $M$ running on $x$ visits at most $c\cdot n$ tape squares.
>
> Prove that for some constant $d$, $M$ runs in time $O(2^{dn})$.

I have a couple of ideas to begin with. First, my intuition tells me that I just have to build an algorithm that runs according to those rules and accepts/rejects in time $O(2^{dn})$. Secondly, theres a hint that tells me to "consider the number of configurations", however, I'm not sure on how to incorporate that.

Thank you in advance for any help.

# Answer
> 4 votes
Your intuition is problematic, for the following reason: you are given a specific machine $M$, not a language. Therefore, if you describe an algorithm that runs in $O(2^{dn})$ and decides the same language, you effectively prove that $L(M)$ is decidable in $O(2^{dn})$, but that does not imply that $M$ *itself* runs in that time frame.

As the hint suggests, consider the number of possible configurations of $M$: recall that a configuration of a TM consists of the contents of the tape, the position of the head, and the state. Given that the alphabet of the machine is fixed, and that the tape used in the run of $M$ on $x$ is of size $c\cdot |x|$, try to bound the number of possible configurations (expressed in the size of $M$ and $|x|$)

Now, recall that $M$ always halts. What does that mean about the sequence of configurations it goes through in its run on $x$?

Combining these two observations you will get the answer. Comment if you need more hints.

---
Tags: turing-machines, space-complexity
---


# Question
Title: Best problems that are prone to parallelization?
What are some problems that are prone to parallelization? When I think about this, the first thing that comes to my mind is matrix multiplication, which yields to faster calculations, meaning you can get speed ups easily. Any other examples like this?

# Answer
> 10 votes
Tasks that are easily parallelizable are sometimes called embarassingly parallel. Straightforward examples are computing fractals like Julia or Mandelbrot sets (since all points are independent of each other) or brute-force searches.

You can find many other examples on the wikipedia page.

# Answer
> 2 votes
this is actually a somewhat subtle/open question to prove that some particular problems are efficiently or not efficiently parallelizable. see also NC class. The class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. also NC$\stackrel{?}{=}$P is open. wikipedia states:

> Just as the class P can be thought of as the tractable problems (Cobham's thesis), so NC can be thought of as the problems that can be efficiently solved on a parallel computer.

---
Tags: parallel-computing
---


# Question
Title: How hard is it to solve for $P$ in $A = PBP^{-1}$?
From graph isomorphism, we know that two graphs A and B are isomorphic if there is a permutation matrix P such that $A = P \times B \times P^{-1}$

So, to solve the problem, if two graphs are isomorphic, we need to find such a permutation matrix P. The problem is believed to be NP (and NP complete for the case of subgraph isomorphism). However, I found an example to solve for P which seemed promising to me and can be found in http://en.wikipedia.org/wiki/Permutation\_matrix in section: solving for P.

The confusion I have now is, does that work for larger matrices? very large? am I right the above equation is hard to solve and can be candidate for a cryptographic system?

# Answer
Graph isomorphism has been well-studied. A short summary: the graph isomorphism problem is not known to be in P (there are no known polynomial-time algorithms), but it is not believed to be NP-complete. There are heuristic algorithms for graph isomorphism that work extremely well on most instances that arise in practice. Read the Wikipedia page on graph isomorphism for more.

As for your particular proposed approach: the Wikipedia page you linked to already explains why that method does not work in general. That method only works if there are no repeated eigenvalues in the matrix corresponding to the adjacency graph. Therefore, it will fail for graphs where there are repeated eigenvalues. Such graphs cannot be ignored. Consequently, that method may work for some graphs but it will fail (or work poorly) for other graphs, so it is not a general solution.

Graph isomorphism is not a good candidate for a basis for a cryptographic system, for two reasons. First, existing heuristic algorithms are very good at solving the problem in practice, and it's not clear how to generate hard instances of graph isomorphism. Second, and more seriously, to be useful for cryptography, we need to not only have a hard problem; we need to have a "hidden trapdoor" that the creator of the public key can embed, which makes the problem easy for the creator, but which is hard for anyone else to detect. No one knows how to embed such a "hidden trapdoor" into the graph isomorphism problem.
> 6 votes

# Answer
As D.W. rightly notes, graph isomorphism is not known to be in P, and believed not to be NP-hard. Moreover, many believe it to be in BQP, but this has not been proven. That puts it in the same category as other problems on which cryptosystems typically rely for their security, such as prime factoring and the discrete log problem, both of which are known to be in BQP. (I don't know where the elliptic curve inverse multiplication problem or whatever it's called sits with respect to BQP, but it wouldn't surprise me in the least if all of these cryptographically useful problems turned out to be equivalent in some sense.)

It's true that we don't know of graph isomorphism problems for which the solution is "hard". However, let's assume for a moment that we did. Then yes, you can use it for cryptography.

As an example, let's look at a zero-knowledge proof key system based on graph isomorphism.

Alice's private key is a labelled graph (the labels can just be integers) which has been constructed such that it is "hard" to check a graph isomorphism for, and it contains a Hamiltonian cycle that it is "hard" to find. Her public key is just the labelled graph, with no information about the Hamiltonian cycle. Note that deriving the private key from the public key requires solving the Hamiltonian cycle problem, which is NP-hard and, we assume, is hard for this graph in particular.

Alice wants to convince Bob that she knows a Hamiltonian cycle in the graph, without actually giving him the Hamiltonian cycle. Here's how she does it.

Alice sends Bob an unlabelled graph. She offers him a choice: Either she will reveal the labels, or she will reveal a Hamiltonian cycle in the graph. Bob flips a coin (or makes a decision by some other means) as to which one he wants, and Alice does whichever of the two that Bob asks.

If Bob asked for the labels to be revealed, he can easily verify (in linear time) that the resuling labelled graph is the same as Alice's public key, but can't find a Hamiltonian cycle because that would be NP-hard. If, on the other hand, Bob asked for the Hamiltonian cycle, he can easily verify (again, in linear time) that the resulting unlabelled graph does indeed contain a Hamiltonian cycle, but he can't verify that it's Alice's public key graph, because graph isomorphism is (presumably) hard.

From Bob's point of view, Alice could have tried to trick Bob by either giving a graph which does have a known Hamiltonian cycle but is not isomorphic to her public key, or by giving him her public key graph with the labels removed but not knowing the Hamiltonian cycle. She would be betting on Bob making the wrong choice. Assuming that Bob really did make his choice randomly, then this trick would have a 50% chance of success.

So the above exchange is repeated with a different unlabelled graph. After $n$ rounds of the protocol, the probability of Alice successfully tricking Bob on all rounds is $2^{-n}$, which converges very quickly to "as certain as you need to be".

This is, of course, nowhere near a practical system as it stands. Moreover, there are some obvious things you can do to make it more secure. For example, instead of Alice sending Bob an unlabelled graph, she could just send a hash of it. When Bob replies, she could then send the graph, and Bob can check that the graph matches.

Nonetheless, you could create a cryptosystem out of it in principle, even if it's not terribly useful.
> 1 votes

---
Tags: algorithms, graphs, cryptography, graph-isomorphism
---


# Question
Title: How to reduce INDEPENDENT SET to INDEPENDENT SET SIZE?
Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET:

INDEPENDENT SET VALUE

Input: An undirected graph G.

Output:The size of the largest independent set in G (but not the set itself).

Show how you can use this algorithm to solve the INDEPENDENT SET problem in polynomial time: given a graph G, return an independent set which is as large as possible.

Any help would be really appreciated. I am pretty lost in this question

# Answer
> 2 votes
There's a couple of issues to address, first is what definition of **INDEPENDENT SET** you are using, the "standard" definition is

> **INDEPENDENT SET** (Decision)
> *Input*: A graph $G$ and a number $k \in \mathbb{N}$.
> *Question*: Does $G$ have an independent set of size at least $k$?

This is the decision version of the problem, and it should be pretty obvious how to use **INDEPENDENT SET VALUE** to solve it.

If you however mean the *search* (or *optimization*) version of the problem:

> **INDEPENDENT SET** (Search / almost Optimization)
> *Input*: A graph $G$ and a number $k \in \mathbb{N}$.
> *Output*: An independent set $I\subseteq V$ where $|I| \geq k$.

If we're looking at the optimization version, then we have the optimization criterion "maximise $k$".

In these cases we can still use **INDEPENDENT SET VALUE** to solve the problem in polynomial time. What we want is an algorithm that makes a polynomial number of calls to our **INDEPENDENT SET VALUE** sub-routine, and at each step decides what to do with some element of the graph.

Further hints in spoilers (don't cheat! ;) ):

> Say you have a graph $G$ where the size of the largest independent set is $\alpha(G)$ Consider what happens if you delete a vertex from $G$ to get $G'$, then run the **INDEPENDENT SET VALUE** algorithm on $G'$ \- what possible values can you get for $\alpha(G')$, and what does that mean for the vertex you deleted?

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


# Question
Title: Determining if a TM decidable or not, with limited information
Were being asked to determine the whether this Turing Machine is decidable or not

"Given a two way, one-tape DTM $M$ whose tape set is $\Gamma=${$a,b,B$} and a string $x\in${$a,b$}\*, determine whether $M$ will ever overwrite a symbol $a$ by a symbol $b$ in its computation on *input* $x$"

I'm not looking for answers, just hints on how to even approach this problem. Like, would we declare a *language* which is a subset of that *language*, and then apply reducibility?

# Answer
> 4 votes
A TM cannot be "decidable". What you are asking is whether the *language* that you describe is decidable.

Hint: the language $A\_{TM}=\\{\<M,w\>: M \text{ accepts }w\\}$ is undecidable even if we restrict to TMs with a binary work alphabet. Try to reduce from this problem, by utilizing only the letters $\\{a,B\\}$ from $\Gamma$. Then, you can use $b$ only when you need it.

Please comment if you need further hints.

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


title: Data Structure for Set Intersection?

text:
# Question
Title: Data Structure for Set Intersection?
Is there any data structure that maintain a collection of set (of finite ground set) supporting the following operations? Any sublinear running time will be appreciated?

1. Init an empty set.
2. Add an element to a set.
3. Given two set, report whether they intersect.

# Answer
> 15 votes
If each set maintains a record of what other sets exist, and you have a total of $s \> 0$ sets, you can easily turn any data structure for a collection (*e.g.* binary search trees, *etc.*) into one where you can have retrieval of an element of the intersection of two sets in time $O(\log s)$.

* Each set should have a unique identifier from some totally ordered set. If you explicitly name your sets $S\_1, S\_2, \ldots$ then the identifier could just be the index.
* You should implement a "registry" of the sets; a data structure which maintains a collection of all of the sets which you have defined. The registry should be implemented as a search-tree data structure, to allow easy retrieval (*e.g.* if you wish to delete the set) and linear-time traversal of the sets.
* Each set $S\_j$ also maintains an "index" of each of the other sets — not a *copy* of them, but rather a data structure which is indexed by the labels of the other sets. This index will be used to maintain, for each set $S\_k$, a binary search tree of all of the elements of $S\_j \cap S\_k$. (The two sets $S\_j$ and $S\_k$ share one copy of that search tree.)

**Initialization**

Initialization of a set $T = \varnothing$ consists of $O(1)$ operations to initialize the tree of its elements, $O(s)$ operations as you initialize (copying from the registry) the index for the set $T$, and $O(s \log s)$ operations as you traverse the registry to add $T$ into the indices of each of the other sets $S\_j$. In the index of $T$, we create search trees representing $T \cap S\_j = \varnothing$ for the other sets $S\_j$; we copy the same pointer for the index of $S\_j$.

**Adding an element to a set $T$**

Adding some $x \in V$ to the set $T$ takes time $O(\log n\_T)$ as usual, where $n\_T = |T|$. We also test for membership of $x$ in each of the other sets $S\_1, S\_2, \ldots$, which takes time $$O(\log n\_{S\_1} + \log n\_{S\_2} + \cdots) \subseteq O(s \log n) ,$$ where $n = |V|$ is the size of the universe (or of the largest set $S\_j$) and $s$ is the number of sets in the registry. For each set $S\_j$ such that $x \in S\_j$, also insert $x$ into the index for the set $S\_j \cap T$. For each such set $S\_j$, this takes $O(\log s + \log n\_T)$ time, to look up $S\_j$ in the index of $T$ and to insert $x$ in $S\_j \cap T$; across all sets $S\_1, S\_2, \ldots$ this takes time $O(s \log s + s \log n\_T)$. If we suppose that the number of sets $S\_j$ is much less than the size of the universe $V$ (that is, if we suppose $s \ll n$), the total time for element insertion is then $O(s \log n)$.

If you do not allow duplicates in sets, we can save time in the case that $x \in S$ already by forgoing the membership test and insertions for the other sets $T$. "Insertion" in the case that $x$ is already present then takes time only $O(\log n\_T)$.

**Intersection testing**

The index of each set is maintained precisely in order to allow quick evaluation of whether or not two sets $S\_j$ and $S\_k$ intersect. For a set $S\_j$, simply by checking its index for the set $S\_k$, we can not only determine in time $O(\log s)$ whether or not $S\_j$ intersects $S\_k$, but we can also retrieve a binary tree containing the entire set $S\_j \cap S\_k$.

**Element Removal**

To delete an element $x$ from a set $T$, we remove it not only from the search tree for $T$ itself, but from each of the intersections $S\_j \cap T$ for the sets $S\_j$ in its index. This takes time $O(s \log n\_T)$, where $n\_T = |T|$.

**Set Deletion**

Because of the overhead of searching the registry, if you have many sets, it may be desirable to delete sets once they are no longer needed. By traversing the entire registry, we may delete $S$ from the index of all other sets $S\_j$ in time $O(sn\_T)$, dominated by the cost of deleting the search tree representing $S\_j \cap T$ for each of the other sets $S\_j$, where $n\_T = |T|$.

**Remarks**

If you expect only to implement a constant number of sets, then the above run-times reduce to:

* initialization: $O(1)$
* element insertion: $O(\log n)$
* intersection testing (and retrieval of the intersection): $O(1)$
* element removal: $O(\log n\_T)$
* set deletion: $O(n\_S)$

where $n$ is the size of the largest set in the registry, and $n\_T = |T|$ for the set $T$ which you are operating on.

If you expect to have $O(|V|)$ sets, where $V$ is your universe, you may need a different data structure if you want these operations to operate in sub-linear time. However, if you have pairs of sets whose intersection you know you will never test, you might be able to reduce the size of the index for the sets (by not including any sets whose intersection you will test) or use more than one registry (one for each collection of sets whose intersection you might test). In fact, a registry is only useful if you want centralized control of ensuring that each pair of sets has a record of each other in the index: it may be practical in some cases, at the initialization of a set $S$, simply to record *ad hoc* each new set into the indices of the other sets $T$ whose intersection with $S$ you are interested in.

# Answer
> 6 votes
There are data structures that allow you to do this in less than linear time, even for worst-case inputs. See https://www.microsoft.com/en-us/research/wp-content/uploads/2011/01/p255-DingKoenig.pdf (and the papers references in there).

If your two sets S and T have a large intersection and you have a dictionary for S, looking up elements of T in random order should quickly give you a common element. The most difficult case is when the intersection size is 0 or 1.

# Answer
> 3 votes
Usually your programming language of choice will support a data structure with unique elements. In general there are three popular approaches: Trees, Hashes and Bitmasks. Tree elements must be comparable, Hash elements must be hashable and Bitmask elements must have some way of conversion to integers.

A tree-set will support insertion in O(log n) and intersection testing in Worst Case O(n log n).

A hash-set will support insertion in Amortized O(1\*h) where 'h' is the running time of the hashing algorithm, and intersection test in Worst Case O(n).

Bitmask sets are not generally used like tree- and hash-sets.

# Answer
> 3 votes
If your case allows false positive answers, I'd use Bloom Filter with a single hash function.

You can implement it as follows :

**Init an empty set**

* $B$ = bit array of $n$ bits, all set to 0.($n$ should be chosen according to the number of possible elements)

**Add an element to a set.**

* $B\[hash(element)\]=1$

**Given two sets(B1,B2), report whether they intersect.**

* check if $B1$ $AND$ $B2$ $=$ $0$

**Complexity**

* If $n$ is not too big, all operations are $O(1)$.

---
Tags: data-structures, sets
---


# Question
Title: what is glushkov NFA. What is the difference between Glushkov NFA and Thompson NFA?
I saw this term "Glushkov NFA" at http://lambda-the-ultimate.org/node/2064 . Search engines are returning references to articles that use glushkov nfa, but nothing specific about the glushkov nfa itself.

What is Glushkov NFA? How different is it from the NFA created from Thompson Construction?

# Answer
The most significant difference is that Glushkov's NFA does not use $\epsilon$-transitions. Very roughly, the algorithm indexes the characters in the regular expression from left to right. Each state in the NFA is a subset of possible indices of the last character read from the input string.

Glushkov's construction \[3\] is described in detail in Aho, Sethi, and Ullman's classical compiler textbook, aka "The Dragon Book" \[1\]. The same construction was also described earlier by McNaughton and Yamada \[4\] and later by Berry and Sethi \[2\], so you may find it easier to search under those names.

1. A. V. Aho, R. Sethi, and J. D. Ullman. *Compilers: Principles, Techniques, and Tools*. Addison-Wesley, 1988.
2. G. Berry and R. Sethi. From regular expressions to deterministic automata. *Theoretical Computer Science* 48:117–126, 1986.
3. V. M. Glushov. The abstract theory of automata. *Russian Mathematical Surveys* 16:1–53, 1961.
4. R. McNaughton and H. Yamada. Regular expressions and state graphs for automata. *IEEE Trans. Electronic Computers* 9(1):39–47, 1960.
> 4 votes

---
Tags: nondeterminism
---


# Question
Title: Is there a name for complement of recursively enumerable set?
If there is a recursive function $$ f(x) = \begin{cases} 1 & \text{if $x \notin A$}\\ \text{undefined} & \text{if $x \in A$}\\ \end{cases} $$

Is there a special name for the class of sets like $A$?

# Answer
> 4 votes
The complement of a recursively enumerable (RE) language is called co-recursively enumerable (co-RE).

As RE and co-RE form the first level of the arithmetic hierarchy, they are also known by aliases $\Sigma\_1^0$ and $\Pi\_1^0$.

---
Tags: terminology, computability, undecidability
---


# Question
Title: How are two layer feed-forward neural networks universal?
Across my studies I have noticed the following statement in my Subject Guide; namely, that two-layer feed-forward neural networks using the sigmoidal activation function are universal. My question is how are the networks 'universal' and what does 'universal' actually mean in this instance?

Thanks in advance.

# Answer
I think they are talking about the universal approximation theorem which states that given a continuous function $f$ over an n-dimensional input vector $\vec{x}$, then a neural network with a single hidden layer can approximate $f(\vec{x})$ arbitrarily closely.
> 4 votes

---
Tags: neural-networks
---


title: Proving language in Space Complexity

text:
# Question
Title: Proving language in Space Complexity
I'd like to know if I have the right intuition and my answer is headed the correct way.

I am given a function $ f = \\{0, 1\\}^\* \rightarrow \\{0, 1\\}^\* $ that is computable in space $O(\log n)$ assume that for every $x \in \\{0, 1\\}^\*$, $f$ is length preserving, $|f(x)| = |x|$.

Define $$L = \left\\{ x\\#y \mid \ x, y \in \\{0, 1\\}^\*, |x| = |y|, \ \text{and} \ f(x) = f(y)\right\\}$$

I am suppose to prove that $ L \in {\sf DSPACE}(\log n) $.

Please correct me if my intuition is incorrect.

My solution would be to build a decider $M$ which is a Turing machine.

$M$ takes inputs $x$ and $y$, run the function $f$ on input $x$ and $y$ and if the lengths of the two strings are equal then accept, otherwise reject.

Now the Turing machine runs in $ O(\log n) $ because the function $f$ is computable in $ O(\log n) + O(\log n) = O(\log n) $ and comparing the length returned by the function is $ O(1) $ Thus the language is decidable by a Turing machine that is run in $ O(\log n) $ and only takes Space $ O(\log n) $.

# Answer
Here is a rough idea how to solve this. You compare $f(x)$ and $f(y)$ character by character. Your tape is devided into 4 pieces. The first one is for simulating $f(x)$ the second one for $f(y)$, then you have two parts, one that counts which character of $x$ you are currently computig, and another $O(\log n)$ area that helps you to navigate. Now the programm looks like this

1. Determine $|x|$ and $|y|$ (store it in binary!) and check if there are the same.
2. Compute the first character of $f(x)$ by simulating it on your machine. Store the output in a TM-state. Pause the Computation of $f(x)$.
3. Walk $|x|+1$ step to the right.
4. Simulate $f(y)$ until you get the first character, check if it coincides with the start of $f(x)$, if no reject, otherwise continue.
5. Walk $|x|$ steps left.
6. Repeat the steps 2.-5. until you check $f(x)=f(y)$ completely.
> 3 votes

# Answer
I'm afraid you've misread the question. It is the sizes of $x$ and $y$ that need to be equal, not that of $f(x)$ and $f(y)$. Of course, in this case, since $f$ is length preserving, $|x| = |y|$ is the same as $|f(x)| = |f(y)|$. But what then about the second part, $f(x) = f(y)$?

Another reason that your algorithm doesn't work is that it uses linear space. Computing the function $f$ takes logarithmic space, but the output takes linear space. So if you store $f(x)$ and $f(y)$ on the work tape, you are using space $\Theta(n)$ rather than $O(\log n)$.
> 2 votes

---
Tags: space-complexity
---


# Question
Title: Notions of information content and randomness of binary square matrix
We have well established theory for measuring the information content and randomness of binary strings. Notions such as Shanon entropy and Kolmogorov-complexity were developed for binary strings.

For a binary square matrix, it is not sufficient to just convert the matrix into binary string and measure its information content or its randomness since naive unraveling of the binary matrix into binary string would lose the adjacency information in each row and in each column.

My question: What are the analogous notions for measuring the information content and randomness of binary square matrix?

# Answer
You claim that unraveling the (square) matrix into a vector loses some information. However, the transformation is bijective - given the $n^2$ vector, you can easily reconstruct the $n\times n$ matrix. Information theory is oblivious to representation. If you have some random variable $X$ and some bijection defined on its domain $f$ then $H(X) = H(f(X))$. So classical information theory covers the case of matrices.
> 2 votes

---
Tags: information-theory, entropy
---


title: Extension of SQL capturing $\mathsf{P}$

text:
# Question
Title: Extension of SQL capturing $\mathsf{P}$
According to Immerman, the complexity class associated with SQL queries is exactly the class of *safe queries* in $\mathsf{Q(FO(COUNT))}$ (first-order queries plus counting operator): SQL captures safe queries. (In other words, all SQL queries have a complexity in $\mathsf{Q(FO(COUNT))}$, and all problems in $\mathsf{Q(FO(COUNT))}$ can be expressed as an SQL query.)

Based on this result, from theoretical point of view, there are many interesting problems that can be solved efficiently but are not expressible in SQL. Therefore an extension of SQL which is still efficient seems interesting. So here is my question:

> Is there an **extension of SQL** (implemented and **used in the industry**) which **captures $\mathsf{P}$** (i.e. can express all polynomial-time computable queries and no others)?

I want a database query language which stisfies all three conditions. It is easy to define an extension which would extend SQL and will capture $\mathsf{P}$. But my questions is if such a language makes sense from the practical perspective, so I want a language that is being used in practice. If this is not the case and there is no such language, then I would like to know if there is a reason that makes such a language uninteresting from the practical viewpoint? For example, are the queries that rise in practice usually simple enough that there is no need for such a language?

# Answer
As for your main question, I recommend this short survey by Martin Grohe.

---

> Are the queries that are needed in practice usually simple enough that there is no need for a stronger language?

I'd say this holds most of the time, given the fair amount of extensions added to common query languages (transitive closure, arithmetic operators, counting, etc.). This comes from the point of view of somebody who has done some work as a freelance developer of relatively simple web sites and other applications, so I'm not sure about the real uses of SQL in bigger industries/larger databases.

In the rare cases a more powerful language might be needed, my guess is that software developers deal with them by using the language in which they write the application, not the queries (like C++ or java).
> 5 votes

# Answer
First, the expressive power of SQL is less clear-cut than it seems. The aggregate, grouping, and arithmetic features of SQL turn out to have quite subtle effects. A priori, it seems feasible that by some encoding of algebraic operators using these features, one could actually express reachability in SQL. It turns out this isn't actually the case for SQL-92, which is "local".

This means that an extension is required for SQL-92 to capture PTIME, and one that allows the resulting language to be "non-local".

However, allowing *ordered* structures and with realistically limited arithmetic, proving that SQL-92 cannot express reachability would imply that uniform $\text{TC}^0 \subsetneq \text{NLOGSPACE}$ and is therefore likely to be quite difficult. (It could be argued that a natural linear ordering always exists on the data types in SQL-92, and that one could therefore assume that the underlying structures are ordered.)

Then the landscape changed again, since SQL:1999 (SQL3) included recursion. So SQL:1999 seems to be at least as expressive as fixed-point logic with counting (though I think the details might again be rather tricky, including the issue of order). Whether the new constructs made the logic more expressive than is required to capture PTIME, I don't know, and some study would be required to establish this. In the meantime, further revisions were made in 2003, 2006, 2008 and 2011 (being ISO documents, only drafts are freely available). These revisions added a whole slew of new features, including allowing XQuery as "part" of SQL queries. My guess is that "SQL" now is more expressive than is required to capture PTIME, but that the encoding required to do so might require large and rather un-natural queries that might not be supported in real systems.

So I think there is evidence that *there is no industrial extension of SQL that precisely captures PTIME*, answering your question in a fuzzy way. In short, the industrial extensions are rather powerful and may already have overshot PTIME. If it is true that SQL:1999 is already powerful enough to capture at least PTIME, then it is also not clear what "SQL" really means in your question, since one would have to define "SQL" to mean a version predating SQL:1999.

Finally, Grohe's survey on the search for logics capturing PTIME (also mentioned by Janoma) indicates not only that capturing PTIME is tricky unless we have a linear order as part of the language, but that a proof that there could be no such logic would also imply $\text{P} \ne \text{NP}$.
> 3 votes

# Answer
Your question is not clear enough if you want an extension that captures $P$ and only $P$ or if it captures $P$ and possibly things outside $P$. It looks like that you are interesting only in the exact $P$ class, since you want safe queries and if otherwise, any Turing-complete extension of SQL would do.

We don't know if $P = NP$. If $P = NP$, then a SQL extension capable of capturing $P$ and just $P$ should be capable to compute if a boolean formula is satisfiable in polynomial time or solve any other $NPC$ problem in polynomial time.

But, if $P \ne NP$, then your SQL-extended language will not be capable to compute if a given boolean formula is satisfiable.

So, we have a question: There exist and algorithm (or query, or whatever) written in such language that is capable to decide if a boolean formula is satisfiable? I can't answer this (and probably nobody here can, as answering this is answering if $P = NP$). This question makes me believe that it is very unlikely that this language exists for real purposes.

Althought it probably does not exists for real purposes, it surely exists and is constructible and implementable. You could define that language with something capable of simulating a Turing-machine up to a given unary number of steps. I.E, capable to solve a P-complete problem. However, if you construct such a thing, it is almost Turing-complete except for the "given a unary number of steps" restriction, which in an SQL-like language would be a very strange way to limit it to only safe queries. You could do this if the steps are records of some table, but this still does not looks anything valuable for practical purposes.
> -1 votes

---
Tags: database-theory, complexity-theory, finite-model-theory, descriptive-complexity
---


# Question
Title: Algorithm of Communication with Failures
I am interested in Distributed Algorithms especially in communication in network with failures.

I look for the proof of the following randomized algorithm of communication in network with failures. For me it seems like very general result in the communication, nevertheless I haven’t found the proof yet.

**Algorithm**: Initially only vertex $v\_0$ has the message, at the end of the algorithm every vertex of the network should have the message.

On every round every vertex that has the message choice the neighbour randomly and sends it the message.

**Assumptions**: only $f$ failures might happen on the edges between the vertices. $T = O(\log n)$ - time complexity and the entire network will know the message with high probability, when $f\<n/3$, where n - number of vertices.

I will appreciate for link or reference to the paper.

# Answer
> 5 votes
The problem you state is very close to the problem of Byzantine Agreement with faulty links. Yet, it is not clear to me what is the guarantees you seek out of your algorithm.

The algorithm you give does not solve the Byzantine-agreement problem. Specifically, if the party that holds the message is corrupt, and it begins by sending $v\_0$ to some player but also $v'$ to other player, then your algorithm will not converge (that is, maybe everyone will have $v\_0$, but they will also have $v'$ and will not know what is the message that was originally sent). If you don't care about the parties having $v'$ as well, then why not just sending the message to all the parties (then repeated by each node)?

Note that when links fail, there is a question of *connectivity*. For instance, if one of the nodes is not connected to any other nodes (all the edges between are faulty), then that node will never get the message. Of course, if the number of faulty edges $f$ is less than $n/3$, and assuming each two nodes are connected, there is no problem at all.

The following paper might be at your help: Vassos Hadzilacos, Connectivity requirements for Byzantine agreement under restricted types of failures, *Distributed Computing*, Volume 2, Issue 2, pp. 95-103, 1987. That paper deals with Byzantine agreement with $t$ faulty nodes and $k$ faulty links, and it holds for any architecture of the underlying graph (as long as some connectivity condition holds).

You might also want to take a look at the case where only nodes are faulty. See for instance, K. Perry, Randomized Byzantine Agreement, *IEEE Trans. on Software Engineering*, Vol SE-11, Issue 6, pp. 539-546, 1985.

# Answer
> 4 votes
First let's look at the failure-free case:

The algorithm that you're describing, namely forwarding the message to a uniformly at random chosen neighbor, is essentially a **gossiping algorithm**.

Clearly, the $O(\log n)$ bound does not apply for arbitrary networks, which might have a diameter of $\omega(\log n)$, so the algorithm will terminate with probability $0$ in $O(\log n)$ rounds.

The (failure-free) model was studied for example in \[1\], but there's much prior work (see references in \[1\]):

> In this model, nodes do not know the global topology of the network, and they may only initiate contact with a single neighbor in each round.

\[1\] show the general upper bound of $O(\phi^{-1}\log n)$ where $\phi$ is the conductance of the graph.

Regarding the case where $f$ links can fail: I'm assuming that you're talking about the failure model where messages can be lost over links and *not* corrupted, right?

Here the answer depends on what kind of adversary you're looking at. Does the adversary choose the $f$ failures in advance or can it observe the random choices of the algorithm? In the former case, we can simply discard those $f$ links from $G$ and get a new (sparser) network $G'$ with conductance $\psi$, which yields the upper bound $O(\psi^{-1}\log n)$, (for the smallest possible $\psi$).

\[1\] Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance. http://arxiv.org/abs/1104.2944 By Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov

---
Tags: algorithms, distributed-systems
---


# Question
Title: prove no DPDA accepts language of even-lengthed palindromes
How do you prove that the language of even-lengthed palindromes, i.e., $L=\left\\{ ww^R \mid w\in \left\lbrace 0,1 \right\\}^\* \right\\}$, can not be accepted by a determinsitc Push-Down-Automaton?

Is there any general way to prove that a context-free language can not be accepted by a deterministic PDA? I mean something like pumping lemma maybe?

# Answer
As Luke notes, there is a Pumping Lemma for deterministic CFL. If there are two strings $zz\_1$ and $zz\_2$ in the language with common prefix $z$, then for deterministic devices the computation in both substrings $z$ must be the same. The idea behind that Lemma is that now also the pumping must be the same for both strings. In context-free languages pumping is of the form $uvwxy$. The Lemma states that *either* $vx$ are inside $z$ for *both* $zz\_1$ and $zz\_2$ *or* $v$ is inside $z$ and there are $x\_1$ and $x\_2$ inside $z\_1$ and $z\_2$ so we can pump both words that way.

For full details check the Lemma.

Now consider $K = L \cap ( a^\*bba^\* \cup a^\*bba^\*bba^\* ) = \\{ a^nbba^n \mid n\ge 0 \\} \cup \\{ a^nbba^{2m}bba^n \mid m,n\ge 0 \\} $. If $L$ is DCFL then so is $K$. Can we pump $z\_1 = a^{2n}bba^{2n}$ and $z\_2 = a^{2n}bba^{2n}bba^{2n}$ in the same way? No. The $v,x$ parts are situated differently when we pump for $z\_1,z\_2$ which contradicts the DCFL Pumping.

Again, one has to be slightly more precise, and quote the proper parts of the Lemma.
> 5 votes

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


# Question
Title: Proving that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not context-free
How can I prove that $\\{0^n 1^{n^2} \mid n \in \mathbb{N}\\}$ is not a context free language?

I tried to prove it using the pumping lemma, but I don't know how to deal with the case when $vxy$ contains both $0$ and $1$.

# Answer
> 2 votes
If $v x y$ is just 0s or 1s, pumping does unbalance the 0s and 1s.

If $v$ is $0^a$ and $y = 1^b$, pumping once gives $0^{N + a} 1^{N^2 + b}$, now prove that that can't possibly work out as $a + b \le N$ (in particular, $N^2 + b$ can't be a perfect square).

---
Tags: context-free
---


title: concurrency and hardware

text:
# Question
Title: concurrency and hardware
I've a couple of questions that I need answers for. What I am looking for here is the outline of the answers. Not necessarily the exact complete answer. I can do that. The question is that common operating systems provide support for concurrency through processes and threads.

There are differences between processes and threads and that well documented and easily understood. The issue here is What support does the hardware need to provide for processes and threads? The initial guess that came to my mind was that it is related to process communication and synchronization. However, these concepts are parts from another question which gets me to think that they are not the right answer. I am aware of the hyper-threading which is a hardware approach for concurrency. Is it ?!

The other question is that Operating systems and programming languages offer various means for communication and synchronization between processes and threads. What are the most common ones? What support does the hardware need to provide and, in particular, what instructions does a processor need to offer for communication and synchronization?

I know it is a long question but again, I don't seem to figure out the outline for the specific hardware support for (concurrent process and threads, as well as communication and synchronization).

Your help is highly appropriated

# Answer
*Preemptive multithreading* is usually implemented by the operating system using timer interrupts. Everything else can be done in software. Even the timer interrupts aren't strictly necessary: in *cooperative multithreading* (what they had in Windows 3.1 and earlier and MacOS prior to MacOS X) the operating system would perform the thread switch whenever a thread did a system call (e.g. a file read or write.)

A *process* has an *address space* with one or more threads running in it. Address spaces typically require hardware support for *page tables*.

There is no hardware support required for synchronization or communication. Multiple threads in the same process communicate through the address space they share. Threads within the same process typically synchronize using *mutexes* and *condition variables*. Mutexes and condition variables can be implemented with load and store instructions. (For the most part. There are some processors that don't have sequentially consistent memory hardware, and for those the processor also needs to implement some kind of memory barrier instructions.) When a thread needs to wait for a long time it will put itself to sleep by calling into the operating system.

Threads in different processes typically communicate through one of the abstractions implemented by the operating system (pipes, files, sockets).
> 2 votes

---
Tags: operating-systems, concurrency
---


# Question
Title: Finding a tree that approximates the distances and total weights
Given an undirected graph $G=(V,E)$ could we build a tree $T$ that approximates the distances from given vertex $r$ and the total weight, i.e. $\forall x \in V, d\_G(r,x) \le d\_T(r,x) \le 3 \cdot d\_G(r,x)$ and $w(T) \le 3\cdot w(\text{MST}(G))$, where $\text{MST}$ is the minimum spanning tree and $w(\cdot)$ is the weight function i.e. $w:\Bbb E \to \Bbb R^+$. $d\_G(v,u)$ denotes the shortest path distance between $v$ and $u$ in $G$, and $d\_T(v,u)$ is the shortest path distance between $v$ and $u$ in $T$.

Could any one help me to understand how to build this tree and if there is any material that would help?

# Answer
Your problem is solved in the following paper by Khuller, Raghavachari, and Young. They show that you can construct a tree in which distances from the root are stretched by at most $\alpha$ and the total weight of the tree is at most $1 + 2/(\alpha - 1)$ times the weight of the MST. So, with $\alpha=3$, you can get $2$ times the weight of the MST. The algorithm does a depth-first traversal of the MST, and adds paths from the shortest path tree when necessary, roughly speaking maintaining a shortest path structure in the current graph, which consists of the MST edges and the edges added from the shortest path three. Check the paper for details.

As I mentioned in the comment, there are graphs in which the weight of the shortest path tree rooted at some vertex is greater than the MST weight by $\Omega(n)$. One example is a path of unit weight edges, and edges from the first vertex in the path to the $i$-th vertex of weight just slightly less than $i-1$.
> 3 votes

---
Tags: algorithms, approximation
---


# Question
Title: Is the language $a^{3}b^{+}$ the same as $\{a^{3}b^{n}, n \geq 1\}$ ? and what is the result of pumping this?
The regular expression $a^{3}b^{+}$ is indeed regular because we can define an automata $M$. But I see that $\mathcal{L} = \\{a^{3}b^{n}, n \geq 1\\}$ may generate the same strings, but using the pumping lemma with constant $N$ for a substring $\alpha\beta = a^{3}b^{t},|\alpha\beta| \leq N$, let $\alpha = a$ and $\beta = a^{2}b^{t}$, therefore $\gamma = b^{N-t}$, and when $k = 0$, $\sigma = \alpha \beta^{0} \gamma = \alpha \gamma = ab^{N-t}$, which doesn't belong to $\mathcal{L}$ and the language isn't regular.

So, is really the regex equal to $\mathcal{L}$? or am I pumping wrong?

# Answer
You are making a classical mistake in applying the pumping lemma. The pumping lemma states that each word $w$ of length at least $N$ in the language (where $N$ is the number of states in the minimal DFA for the language) can be decomposed as $w = xyz$, where $|xy| \leq N$, $|y| \geq 1$, and $xy^i z$ is in the language for all $i$. *You don't get to choose this partition!* The lemma just states that there is *some* partition. Taking as an example your word $a^3 b^t$, since $N = 6$ (indeed, the minimal DFA for the language has $6$ states), we can always choose $x = a^3$ and $y = b$, and then $xy^i z = a^3 b^{t+i-1}$ which is always in the language (since $t \geq 3$).

When you use the pumping lemma to prove that a language is not regular, you don't know $N$, and so you have to start by taking $N$ to be arbitrary, and run the proof from there. What you are in effect showing is that for each $N$, there is no DFA accepting the language with at most $N$ states.
> 3 votes

---
Tags: regular-languages, finite-automata, regular-expressions, pumping-lemma
---


# Question
Title: Can all permutations of a set or string be generated in O(n log n) time?
I was looking over this question requesting an algorithm to generate all permutations of a given string. A comment in the answer caught my eye:

*It might seem that it can take O(n) time per permutation, but if you think about it more carefully, you can prove that it takes only O(n log n) time for all permutations in total, so only O(1) -- constant time -- per permutation.*

This seemed strange to me because the best method I was aware of to generate all permutations of a string is in O(2^n) time. Looking through the other results, I came across a response to a similar question which states: *While it technically produces the desired output, you're solving something that could be O(n lg n) in O(n^n)*

I am aware of an algorithm to unrank permutations in O(n log n) time, but these responses seem to imply that all permutations in total can be generated in time O(n log n). Am I misunderstanding these responses?

# Answer
You have misinterpreted the SO question itself (or we have misinterpreted yours, which seems more likely). That SO quesiton is talking about generating a 'next' permutation from a previous given one, so that all permutations can be generated by calling 'next' multiple times.

The answer to that is talking about the (amortized) time complexity of the C++ implementation `std::next_permutation` which I believe uses Narayana Pandita's algorithm, and generates them in lexicographic order.

(Also, as an aside: permutations are different from combinations. There are $n!$ permutations, but $2^n$ combinations (subsets). You seem to be under the impression that permutation is same as a combination (based on your claim of $O(2^n)$)).

To get back to the original question, another way to look at the question: would using `next_permutation` to generate all the $n!$ permutations in lexicographic order be $\Theta(n!)$ or $\Theta(n\times n!)$?

While there are some wrong statements in the answer you linked, it does state the right answer: It is $\Theta(n!)$, i.e. the amortized time complexity of `next_permutation` is indeed $O(1)$.

This can be proven as follows:

If $T(n)$ is the time taken to generate all the $n!$ permutations using `next_permutation` then we have that

$$T(n) = n T(n-1) + O(n^2)$$

(You fix the first number $n$ times and generate the permutations for the rest, and pay $O(n)$ cost when the first number is switched.)

Let $G(n) = \dfrac{T(n)}{n!}$. Note that we are looking the the asymptotics of $G(n)$. We get

$$G(n) \le G(n-1) + \frac{cn^2}{n!}$$

This is a simple telescoping sum, and since $\sum\_{n=1}^{\infty} \frac{n^2}{n!}$ is convergent, we get that

$$G(n) = O(1)$$

Note that you could have changed the recursion to

$$T(n) = nT(n-1) + O(n^k)$$

and still have gotten $O(1)$ amortized per permutation.
> 5 votes

# Answer
No, it is impossible. There are $n!$ permutations of a string of $n$ characters, which is vastly more than $O(n\log n)$.
> 2 votes

# Answer
generating permutations has complexity $O(N!)$ it means that we do $O(1)$ per permutation
I dont know why you think that to generate is less than accessing but in this problem we have a mathematical proof why you need at least $N!$
> 2 votes

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


# Question
Title: What does the posterior probability of a variable mean in the Bayes' rule?
I have been studying Artificial Intelligence and I have noticed that the Bayes' rule allows us to infer the posterior probability if a variable. But, my question is, what does the word, or phrase, 'posterior' mean in this context with regard to the Bayes' rule?

# Answer
> 4 votes
The word *posterior* stems from the latin word *posterior* (base form posterus), which means *later*, *after*, *behind*.

In the context of probability and Bayes' theorem it denotes a probability, often written as a symbol $P(A|B)$, where $A$ and $B$ are random variables. This symbol $P(A|B)$ means the probability of $A$ after you have observed $B$. Hence the naming *posterior probability*, or short *posterior*.

In this context the probability of observing a certain value of the random variable $B$ is denoted by $P(B)$ and is called *prior probability*, or just *prior* for short sometimes. The word prior also stems from a Latin word, *pri*, which means *before*. The name hints that you will gather observations of $B$ before you calculate $P(A|B)$.

In this way you use prior information to improve your model of $A$, expressed by the posterior probability $P(A|B)$. By this your probability of $A$ is based on the observed outcome of $B$. Like it has been said by John Maynard Keynes "When the facts change, I change my mind. What do you do, sir?".

---
Tags: artificial-intelligence, probability-theory
---


# Question
Title: Particularly Tricky Recurrence Relation (Master's Theorem)
Master's theorem is shown below,

The recursive function to be solved is shown below,

I understand that `a` refers to the number of recursive calls in this function (**3** in this case). `b` refers to what the input size is being divided by in each recursive call. Which I believe should be **4**. `d` refers to the overhead of each recursive call, which should be 1.

So we have:

```
a = 3
b = 4...?
d = 1

```

The problem is, b apparently doesn't equal 4.

Now the actual answer shows that the answer is:

Which seems incorrect, since given the Master's Theorem, I don't see how `n` is being subtracted by a constant.

Thank you for your help.

# Answer
> 2 votes
Since n refers to "the length in bits of x", you should translate n with the binary log of x, and (n-2) with the binary log of x/4.

Hope it helps.

---
Tags: recursion
---


title: Pebbling Problem

text:
# Question
Title: Pebbling Problem
> Pebbling is a solitaire game played on an undirected graph $G$ , where each vertex has zero or more pebbles. A single pebbling move consists of removing two pebbles from a vertex $v$ and adding one pebble to an arbitrary neighbor of $v$ . (Obviously, the vertex v must have at least two pebbles before the move.) The PebbleDestruction problem asks, given a graph $G = ( V; E )$ and a pebble count $p ( v )$ for each vertex $v$ , whether there is a sequence of pebbling moves that removes all but one pebble. Prove that PebbleDestruction is NP-complete.

First, I show that it is in NP since I can verify the solution in polynomial time, tracing back the pebble count from just one pebble.

Next, what are some ideas on which problems to use as the basis for a polynomial-time reduction?

Would something like vertex cover work? Or a vertex cover of different sizes?

If so, how can it handle the varying number of pebbles on each move?

Thank You.

From: http://courses.engr.illinois.edu/cs473/sp2011/hw/disc/disc\_14.pdf

# Answer
> 8 votes
Suppose in a graph $G$ there is one pebble on each vertex except one vertex $v$ with $p(v) = 2$, then above pebbling problem has solution on $G \space iff \space G$ has a Hamiltonian circuit. It's easy to check if there is a Hamiltonian circuit, then there is a solution for pebbling on $G$. On the other hand, in any solution to the pebbling, we should start from vertex $v$. Suppose that we visit some vertex $u$ twice such that this $u$ is the first vertex which visited twice in $G$ by pebbling algorithm, then we have a loop which starts from $u$ and ends in $u$ and finally because $u$ is the first for making loop then we have $p(u) = 1$ so we cannot continue pebbling algorithm. Indeed if the algorithm has a solution then we have $u=v$ which means we found a Hamiltonian circuit which starts in $v$.

---
Tags: algorithms, graphs, np-complete
---


# Question
Title: If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$
If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$.

Can anyone clarify what does this mean?

# Answer
> 6 votes
This is just a set-theoretical equality. Two sets are equal precisely when they are included in one another: $A = B$ iff $A\subseteq B$ and $B\subseteq A$. The notation is applied in the context of languages of automata. In order to show an automaton $M$ defines language $L$, you have to show it accepts all strings from $L$, and no more than those strings.

Basic, when doing automata and language theory, I am afraid.

---
Tags: terminology, sets
---


# Question
Title: Show that TQBF $\notin$ SPACE$((\log{n})^4)$?
How do I show that TQBF $\notin$ SPACE$((\log{n})^4)$? I know that TQBF is PSPACE complete, but is this the right approach?

# Answer
Hint: TQBF is PSPACE-complete, so it "requires" polynomial space. If there were an algorithm to solve TQBF using space $O(\log^4 n)$, you could use it to solve *all* problems in PSPACE using surprisingly small space. So surprising, in fact, that the space hierarchy theorem says it can't be.
> 5 votes

# Answer
Another hint: As $TQBF$ is PSPACE-complete, for every problem $L$ in PSPACE, there exists a reduction $f$ such that for every instance $x$ of $L$ we can construct an instance $f(x)$ of $TQBF$ in time $O(n^{d})$ for some $d\in\mathbb{N}$ (note that $d$ depends on $f$, so it's unbounded, it can be different for every $f$).

Then there's two questions:

1. If $|x| = n$, what can $|f(x)|$ be at most?
2. Then how much space could you solve $x$ in if you could solve $f(x)$ with at most $O(\log^{4}n)$?
> 2 votes

---
Tags: complexity-theory
---


title: performance between the data structures

text:
# Question
Title: performance between the data structures
I have developed two existing data structures and I want to see their performances over a certain algorithm. In this case I use Dijkstra's algorithm with binary and Fibonacci heaps. Just to ask, if I have 100 to 1000 number of vertices in the tested sparse digraphs, how many times should I execute my program for a single n vertices? How do I know that the empirical differences in performance that I've obtained between data structures are not due to chance?

# Answer
> 1 votes
You can use the program ministat to get statistical information about runtime differences. This blog post gives an example for the usage.

But in general, comparing runtimes is difficult and very machine dependent. Ideally you would find another performance measure that doesn't change so much between processors.

You should also take care that your input instances are well chosen. Random instances might behave very differently from real-world cases, but the latter are typically hard to come by. You should try modelling "interesting" properties of real-world instances and generating instances that also have those properties. You can also try to look very hard at the data structures and try to generate instances that trigger worst-case behaviour, but that is typically also very hard.

---
Tags: data-structures, priority-queues, performance, empirical-research
---


title: Resolving this recurrence equation

text:
# Question
Title: Resolving this recurrence equation
I have this recurrence equation:

$T(n) = T(n/4) + T(3n/4) + \mathcal{O}(n)$

$T(1) = 1$

I know that the result is $\mathcal{O}(n \log n)$ but i don't know how to proceed.

# Answer
Construct a recursion tree. The sum of the costs per level is less then $c\cdot n$, for $c$ being the constant in the $O(n)$. The tree has roughly $n\log\_4 n$ full levels, and the deepest level is $n \log\_{4/3} n$. So, summing up over all levels gives $T(n)=O(n\log n)$.
> 1 votes

---
Tags: asymptotics, runtime-analysis, recurrence-relation, recursion
---


# Question
Title: How to represent OOP concepts in algorithms in a standard way?
I have usually been using the Cormen algorithm format to teach some introductory courses in Programming. I mean something like this:

```
TreeSearch(k,n)
1. if x==NIL or k==x.key
2.     return x
3. if k<x.key
4.     return TreeSearch(k.left,n)
5. else return TreeSearch(k.right,n)

```

Actually I have not agree with a couple of lecturers in my institution that they insist to put the type of the variable that they are using in the algorithm. I mean, to do that, will it not be to make a bias toward the programming language and not to focus on the algorithm? For example what would happen if the student grab other programming language, like R or Python, that really do not care about the type of variable.

The other issue that I have is how to represent OOP algorithms in a nice algorithmic way. For example when I make a constructor should I put something like:

```
Class: car
Attributes: wheels
Constructor car()

```

or something like

```
Class: car
Function car()

```

also when I come to the part of inheritance, one of my colleages put the word super() to define inheritance in an algorithmic way, but again I think that is too Java-way to do this part. Usually they teach in that way because the practical part is made in Java, but again I think that the algorithm should be more freely, directly towards the logic, and not to an specific programming language.

Does anybody knows some standard to represent algorithms for OOP?

# Answer
> 1 votes
Generally there is no unified to present algorithms. Each researcher should use/introduce notation with which he is most comfortable with.

If you look at some algorithmic books writers have different approach to this manner.

For instance:

* CLRS book gives no types for functions arguments
* Tel's "Introduction to distributed algorithms" gives types
* Sedgewick's "Algorithms" gives code in Java (which is not very good solution IMO)

On the other hand any object can be represented as tuple of base data types, eg binary tree can be presented as:

```
(5,(3,(1,NIL,NIL),(4,NIL,NIL)),(6, NIL, NIL))

```

Which might corresponds to

```
5
|\
3 6
|\
1 4

```

But the first notation is not very readable, so its easier to relate so such tuple as Node.

Additionally algorithms representation depends on field on which they are presented. If you assume that algorithm should be more or less translatable from pseudo code to actual code then you should introduce hints and notation to your algorithm presentation which allow this. But if that is not the case and you want to focus mainly on algorithm idea, or some other complexity value then, time then mathematical notation might become handy. In the end as previously stated it depends on needs.

If you look closely on various papers and books you can see that types of arguments are either obvious from context, or explained in algorithm description.

I suggest you to get familiar with $\LaTeX$ Algorithms module.

---
Tags: algorithms, terminology, education, object-oriented, didactics
---


# Question
Title: How come the Bernstein operator creates a polynomial of the same degree as its input function?
I read that the Bernstein operator

$$ \mathfrak{B}\_f(t) = \sum\_{i=0}^n f\left(\frac{i}{n}\right) \\; B^n\_i(t) $$

applied to a polynomial $f(x)$ of degree $m \leq n$ with the Bernstein polynomial

$$ B^n\_i(t) = \binom{n}{i} \\; t^i \\; (1-t)^{n-i} $$

returns a new polynomial also of degree $m$. In other words, the Bernstein operator does not increase its degree when applied to $f$.

How is this possible? Since we're only sampling $f$ at a certain interval, wouldn't the original degree of $f$ become irrelevant? How can the degree of the result be smaller than $n$, since we will have at least one $t^n$ in the expression resulting from one of the Bernstein polynomials?

# Answer
The coefficients of $t^k$ for $k \gt m$ can cancel out.

For instance, let $f(x) = x^m$ and consider the coefficient of $t^n$ for $n \gt m$.

The coefficient we get is

$$n^{-m}\sum\_{i=0}^{n} \binom{n}{i} i^m (-1)^{n-i}$$

which can be shown to be zero by starting with

$$\sum\_{i=0}^{n} \binom{n}{i} x^{i} (-1)^{n-i} = (x-1)^{n}$$

And differentiating and multiplying by $x$, $m$ times, and then setting $x=1$.

For $m \lt n$, this indeed comes out to be zero.
> 1 votes

---
Tags: computational-geometry
---


title: Cost at Each Level of a Recursion Tree

text:
# Question
Title: Cost at Each Level of a Recursion Tree
Given a recursive function $T(n)=T(a\_1\cdot n)+\dots +T(a\_k\cdot n)+\Theta(n)$ such that $\forall a\_i: 0\<a\_i\<1$, what is the most general thing I can say about the sum of the cost of the nodes at each level of the recursion tree? I've looked at a few, and for the ones I've looked at it's always come out to $(a\_1+\dots +a\_k)^i$ where $i$ is the level in the tree.

Could anyone explain this? If it matters it's in the context of trying to prove that $T(n)=\Theta(n) \Leftrightarrow a\_1+\dots +a\_k \< 1$

# Answer
> 1 votes
You are right!

The work $W$ at each node (of level $i$), splits into $Wa\_1, Wa\_2, \dots, Wa\_k$ at level $i+1$.

If you add them up, you get that the total work at level $i+1$ is $a\_1 + a\_2 + \dots + a\_k$ times the total work at level $i$.

Of course, this assumes that your $\Theta(n)$ is some exact $cn$, but this argument is good enough to prove that $T(n) = O(n)$. Proving $T(n) = \Omega(n)$ is trivial.

btw, I recommend you look at Akra-Bazzi as a useful tool, if you are interested in such questions.

---
Tags: recurrence-relation
---


# Question
Title: Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular
Prove that $L\_1$ is regular if $L\_2$, $L\_1L\_2$, $L\_2L\_1$ are regular.

These are the things that I would use to start.

* As $L\_1L\_2$ is regular, then the homomorphism $h(L\_1L\_2)$ is regular.
* Let $h(L\_1) = L\_2$ and $h(L\_2) = L\_1$, then $h(L\_1L\_2) = L\_2L\_1$ is regular (we already know that) or $h(L\_2) = \epsilon$ and we get $L\_1$
* By reflexing, $L\_1L\_2 = (L\_2L\_1)^{R}$, same result.

But i don't know how to, for example, intersect something that gives me $L\_1$ in order to preserve closure and finally $L\_1$ be regular.

Any help?

# Answer
Here is a counterexample. Let $L\_1$ be any language over some alphabet $\Sigma$ containing the empty string, and let $L\_2 = \Sigma^\*$. Then $L\_2 = L\_1L\_2 = L\_2L\_1 = \Sigma^\*$ are all regular, but $L\_1$ need not be, in fact it could even be uncomputable!
> 7 votes

# Answer
Another counterexample (special case of the first answer) is find just one non regular language in specific and another regular language where $L\_1 \subseteq L\_2$.

Let $L\_1 = \\{a^{n^2}, n \geq 0\\}$ (it includes $\epsilon$) and $L\_2 = \\{a^n, n \geq 0\\}$. It's concatenation $L\_1L\_2 = L\_2L\_1 = L\_2$ since the subset property established at the beggining. Then $L\_1$ is not necessarily regular.
> 2 votes

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


# Question
Title: Formalisms in concurrent and/or distributed programming?
My background came from imperative languages, primarily C, C++, and Python. I picked up Scala, Erlang, and a bit of Haskell a few years later and have since become very interested in functional programming and the formalisms behind it.

I am also interested in concurrent and distributed programming and have been looking into formalisms behind that, especially those that have seen at least a tiny bit of the "light of day" (e.g. real world use, or at least an implementation somewhere). So far I know of Communicating Sequential Processes, the Actor model, Algebra of Communicating Processes, and the Calculus of Communicating Systems. Among these I know the Actor model has realized itself in languages like Erlang, Scala, and Haskell.

I am wondering if there are foundations I should learn and practice before tackling these fields, if there is a "classic" one that I should study first, and if there are any other popular ones that I may have missed?

# Answer
> 5 votes
The most widely used formalism is the $\pi$-calculus by Milner, Parrow and Walker. It is an extension of CCS, and comes in many variants, some of which (the asynchronous $\pi$-calculus) attempt to be a formalisation of the actor model. There are now many typing disciplines for $\pi$-calculi, the simplest of which are probably Honda's session types. Such types are slowly diffusing from research papers to research implementations.

---
Tags: distributed-systems, concurrency
---


# Question
Title: How do we determine how much time a multi-tape DTM saves over a one-tape DTM?
Note: This is a part of a homework question

Were asked to construct a multi-tape Turing Machine for language {$a^n b^n c^n \mid n \geq 0$}

Then it says "Discuss how much time your machines saves over a one-tape DTM using the same algorithm" Any hint?

Here's my algorithm:

(1) Cut-and-paste c's to tape 3

(2) Cut-and-paste b's to tape 2

(3) Cross out each triplets, accept if last round cuts all three, reject if there's leftover

Which seems like it has a time complexity of $O(n+n+3n)=O(5n)$ Then how do we determine the time complexity for the one-tape version?

# Answer
Figured it out. Turns out a theorem states that

> For any multi-tape DTM $M$, there exists a two-way, one-tape DTM $M\_1$ computing the same function s.t. for all inputs $x$, $Time\_{M\_1}(x) \leq c \centerdot (Time\_M(x))^2$

Reference: Du, Dingzhu, and Ker Ko. Problem solving in automata, languages, and complexity. New York: Wiley, 2001. Print.
> 0 votes

# Answer
As this is homework, I'll go for the gentle hint approach. Firstly, it's a bit odd to talk about a TM using an algorithm - a TM *is* an algorithm, so my interpretation of the question is:

Given a multitape TM, you want to produce a single tape TM that does the same job (i.e. has the same language), and you want to know how much slower the single tape version is (in the worst case).

To put it another, hint laden way, how much slower is it to *simulate* a multitape machine with a single tape machine?

There's a rather important result regarding this (i.e. there's a way to do it that guarantees an upper bound on the slowdown factor), a little searching should get you that at least.
> 1 votes

---
Tags: time-complexity, turing-machines, efficiency
---


title: Dynamic loading vs. dynamic linking?

text:
# Question
Title: Dynamic loading vs. dynamic linking?
What is the difference between dynamic loading and dynamic linking?

Both systems seem to allow shared libraries, but I am struggling to differentiate between them.

# Answer
Dynamic linking is performed at the time of program loading only and uses compile-time established names. Dynamic loading can be done at any point in program execution.

From wikipedia:

> Unlike static linking and loadtime linking, this mechanism allows a computer program to startup in the absence of these libraries, to discover available libraries, and to potentially gain additional functionality.
> 3 votes

---
Tags: memory-allocation, memory-access
---


title: How to take complement of a language?

text:
# Question
Title: How to take complement of a language?
I'm stuck on this question about context-free languages and was hoping for some clarification.

> $\qquad L = \\{a^i b^j c^k \mid i=j, i=k\\}$
>
> is *not* context-free. Show that its complement *is* context-free.

I understand that the complement basically means everything not in $L$, that is $A^\* \setminus L$. However, I have no idea how to actually take a complement for a language like this.

# Answer
You are right. The complement consists of all strings *not* in the language. So basically if the language says "all strings such that X holds" the complement is "all strings such that not X holds", the logical negation of X.

In this case the logical negation of "$i=j$ and $i=k$" equals "not ($i=j$ and $i=k$)" or using the Morgan's rule, "$i\neq j$ or $i\neq k$".

But there is a slight catch. Actually the strings in $L$ have an additional explicit condition, they are of the form $a^i b^j c^k$ for some $i,j,k$. That means the actual complement is the union of (1) all strings *not* of the form $a^i b^j c^k$ (thus, not in $a^\* b^\* c^\* $) and (2) all strings of the form $a^i b^j c^k$ such that "$i\neq j$ or $i\neq k$".

The strings in (1) form the regular language $\\{a,b,c\\}^\* - a^\* b^\* c^\* $ and should not bother you too much. The strings in (2) are treated elsewhere in this forum.
> 4 votes

# Answer
In order for a string not to be in language $L$, either $i \neq j$ or $i \neq k$

Anytime we take the complement of a language which depends on variables equality, we make any (either or both) pair originally equal to unequal each other

so if $L =$ { $a^xb^y \mid x = y$} then $ L'=$ {$a^xb^y \mid x \neq y$}
> 1 votes

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


# Question
Title: Upper bound on register machine contents
I am doing some work on register machine theory which revolves around a 2-register register machine and attempting to show that it is not possible to compute an upper-bound on the final contents of its two registers on the basis of its program code and initial input, in halting configurations only. I believe this can be related in some way to the *busy beaver* problem, but I cannot quite see how, and the stipulations that it is for halting configurations only has confused me somewhat.

What do I know so far?

* Clearly a register machine configuration specified by the 3-tuple *(instruction label, register 0, register 1)* has an infinite number of possible states, owing to the abstract nature of the machines, as no practical limit is imposed on the size of the natural numbers which can be stored in each register.
* I considered whether I could simply define a partial function $f : \mathbb{N}^3 \to \mathbb{N}$ where the arguments are the program encoded as a natural number and the initial contents of the two registers, but I do not think this gets me anywhere. I defined the function to be undefined when the partial function computed by the register machine specification is undefined on the given input, as the problem specifies computing the upper bound for halting configurations only.
Therefore, I cannot use a diagonal argument to suggest it would imply the halting problem, because being undefined for a non-halting configuration suggests it would not.
* Secondly, I tried to come up with a proof on the basis that there is an infinite number of possible configurations which a 2-register machine can be in. In particular, there is an infinite number of possible programs $e \in \mathbb{N}$ which could be executed, and each of those programs can be executed on an infinite number of initial register configurations $\mathbb{N}^2$.
By construction, if there is a machine which can decide this partial function for any given combination, then I thought it may be the case that it required an infinite number of states in which to do so - which is of course not possible, as a register machine must be specified by a finite number of instructions.

I am not confident that either approach is correct or not, and wonder whether either of the above is a correct tact or if a formal proof exists for this?

# Answer
> 1 votes
Hint: Your computation model is Turing-complete. If you could compute an upper bound, that would enable you to solve the halting problem.

---
Tags: computability, turing-machines, church-turing-thesis
---


title: Is linear-time reduction symmetric?

text:
# Question
Title: Is linear-time reduction symmetric?
By reduction I mean the following:

> Problem X linear reduces to problem Y if X can be solved with:
> a) Linear number of standard computational steps.
> b) Constant calls to subroutine for Y.

If a problem X reduces to a problem Y, is the opposite reduction also possible? Say

X = Given an array tell if all elements are distinct
Y = Sort an array using comparison sort

Now, X reduces to Y in linear time i.e. if I can solve Y, I can solve X in linear time. Is the reverse always true? Can I solve Y, given I can solve X? If so, how?

# Answer
> 6 votes
No, it is not symmetric.

Here's my counter-example: Consider the language $L\_1 = \\{A:A'| A'$ is $A$ sorted$\\}$ and $L\_2 = \\{A:a| a$ is the largest element in $A\\}$.

We can solve the max-element problem with a constant number of calls to a machine solving sorting. Just sort $A$ then take the first element. But we can't solve sorting with a constant number of calls to a machine solving max-element (otherwise, we could sort in $O(n)$, which is known to be impossible).

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


title: proving $P \subseteq PCP(0,O(log(n))$

text:
# Question
Title: proving $P \subseteq PCP(0,O(log(n))$
I was working on proving this one and I've solve one direction as follows :
to prove that $P \subseteq PCP(0,logn)$ I said :
let $M$ be deterministic polynomial TM that accepts $L \in P$ ,we want to show that we can there exists a proof system which consists of prover and deterministic polynomial verifier that have access to an oracle and make at most $O(log(n))$ queries and $\forall x \in L$ $\exists \pi \_x $suchthat the verifier always(i.e. probability =1) accepts and $\forall x \notin L$ always reject what ever the proof was.
the prover and the verifier will be the machine $M$ (since no randomness required) and $\pi \_x$ will be: run M and obtain solution denoted by : $ANS$ send it to the verifier then the verifier checks if $ANS$ is the same and rejects or accepts accordingly ... this proves that: $P \subseteq PCP(0,O(1)) \subseteq PCP(0,O(log(n)) $

# Answer
> 5 votes
As Kaveh points out, any problem in $P$ by definition can be solved in polynomial time by a Turing Machine, so it in effect produces its own proof and checks it, hence $P = PCP\[0,0\]$ and the inclusion you want to show is trivial.

What's more interesting is to show that $PCP\[0,O(\log n)\] \subseteq P$ (and hence equal).

Hint:

> Try and think of why a proof that's only logarithmic in the size of the input isn't giving more information than you could work out. The sub question here, is why can we consider the proof to only be logarithmically sized?

# Answer
> 4 votes
The verifier is a polynomial-time machine, it can solve a problem in $\mathsf{P}$ by itself (without needing to check the certificate/proof sent by prover at all). Also no need for any randomness.

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


# Question
Title: Finding Hamiltonian cycles in polynomial space
Question: If $H = \\{(G,m)$ $|$ $G$ is a graph with $m$ distinct Hamiltonian cycles $\\}$ ($m$ is in binary), prove that $H \in$ polynomial space.

My thoughts: I thought that I could show that $H \in NP$, by which it would automatically follow that $H \in$ polynomial space. By the witness theorem, the $m$ distinct Hamiltonian cycles (call them the set $C$) would serve as a witness. However, what is not apparent is if $|C| \leq |G|^k$. In fact, that is the entire problem, isn't it? What am I thinking about wrong over here?

# Answer
Observe that a naive witness for $m$ cycles is a list of the cycles, which may be exponential (in case the value of $m$ is exponential in the size of $G$).

So perhaps you should work directly with PSPACE.

A possible approach is to order the vertices of $G$, and then try all sequences of $n$ (the number of vertices) vertices, in lexicographical order (one at a time, erasing the last one every time you proceed to the next, so as not to waste space), and for each sequence check whether it is a Hamiltonian cycle, and increment a counter if it is. If the counter passes $m$ then you have $m$ distinct cycles.

If by "distinct cycles" you mean that you do not count cyclic permutations, then after you complete the entire count, simply divide the number of cycles you found by $n$, giving you the number of cycles without cyclic permutations, and compare this number to $m$.
> 3 votes

---
Tags: graphs, np
---


# Question
Title: Find all increasing/decreasing sub array
I have a question that I still struggle with. It would be really appreciated if you guys could give me some hints.

Here is the problem : Assume that $a\[1\dots n\]$ is an array of $n$ positive real numbers. Let $\alpha \>0$ and $\beta \>0$

* a subarray $a\_1$ with $m$ elements of $a\[1 \dots n\]$ is called increasing if $\frac{a\_1\[i\]}{a\_1\[j\]}\geq \alpha$, for all $i\>j$ and $1 \leq i, j \leq m$.
* a subarray $a\_2$ with $k$ elements of $a\[1 \dots n\]$ is called decreasing if $\frac{a\_2\[i\]}{a\_2\[j\]}\leq \beta$, for all $i\>j$ and $1 \leq i, j \leq k$.

Question : write a program to find all increasing/decreasing subarrays of $a\[1 \dots n\]$ ? thanks so much for your help.

# Answer
> 1 votes
The question is not clear, you say sub-array, but in the comments you say sub-sequence, and also the comment "the array is discrete" (not sure what that means...).

It is also not clear whether you want a sub-sequence that is both increasing *and* decreasing. I will presume they are disjoint problems.

So, on the assumption that you want to find all increasing sub-sequences of the array: $a\[i\_1\], a\[i\_2\], \dots, a\[i\_m\]$ with $i\_1 \lt i\_2 \lt \dots \lt i\_m$ here is an algorithm.

Given the array $a\[1, \dots n\]$, you construct a directed acyclic graph of $n$ vertices: $v\_i = (a\[i\], i)$ with a directed edge from $v\_i$ to $v\_j$ iff $a\[j\] \ge \alpha a\[i\]$ and $j \gt i$.

Now you enumerate all the paths in this directed graph. This is $O(n^2 + f(P))$ where $P$ is the number of paths in the graph, and $f$ is the complexity of the algorithm you pick to do the enumeration.

If you just wanted a *count* of paths rather than the actual paths themselves (which is what I suspect was your original problem, based on asking for a "hint"), then a dynamic programming algorithm which finds the number of sequences ending at a given $a\[i\]$ could be made to work in $O(n \log n)$ time.

# Answer
> 0 votes
Note: This answer was given before the OP substantially changed the question by requiring that the inequality holds for any pair of elements in the sub-array.

This is a basic brute force solution. Keep two nested for loops. In the outer loop, iterate the loop variable $i$ from $1$ to $n$. In the inner loop, iterate the loop variable $j$ from $i$ to $n$. Inside the inner loop, check for the ratio of $\frac{a\[j\]}{a\[i\]}$ and declare the sequence of $a\[i \dots j\]$ to be increasing or decreasing depending on the ratio in comparison with $\alpha$ or $\beta$.

---
Tags: algorithms, substrings
---


title: Big O notation of max?

text:
# Question
Title: Big O notation of max?
I'm coding a few set comparisons and noting their big O's using different algorithms and set implementations. I got to one particular function and I decided that it is $O(max(n,m))$ runtime. Is that the proper way to express this?

# Answer
> 9 votes
The expression $O(\max(n,m))$ is meaningful, and we even have $O(n) + O(m) = O(n+m) = O(\max(n,m))$.

---
Tags: asymptotics
---


# Question
Title: Is the problem of evaluating a boolean formula on a given assignment P-complete?
I know that the CIRCUIT VALUE problem is P-complete. In the CIRCUIT VALUE problem the input is a Boolean circuit together with an input to this circuit, and the answer is the evaluation of the given circuit on the given input.

I wish to know if the problem of evaluating a Boolean formula on a given assignment is also P-complete. From one hand, it seems that a Boolean circuit and a Boolean formula are very similar objects. Also, the proof of that CIRCUIT VALUE is P-complete results from the Cook-Levin problem, the same theorem that actually shows that SAT is NP-Complete, so I don't see a reason why this problem won't be P-Complete. From the other hand, it seems pretty easy to evaluate a Boolean formula in logarithmic space, so if this problem is indeed P-complete I think it would imply L = P which is unknown.

So I think I'm missing something.. any ideas people?

# Answer
this is apparently the same as the "boolean formula value problem" similar to the "boolean sentence value problem" (BSVP) proven to be in ALOGTIME by Buss-Cook-Gupta-Ramachandran. an improved algorithm and refs are given in Algorithms for Boolean Formula Evaluation and for Tree Contraction by Buss.
> 4 votes

# Answer
In his 1987 paper "The Boolean formula value problem is in ALOGTIME", Buss showed that Boolean formula evaluation is in ALOGTIME (alternating logarithmic time), which is a uniform version of NC1 and so probably smaller than P. It is also ALOGTIME-complete under AC0 reductions.
> 8 votes

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


# Question
Title: Show that this language is in NP $\cap$ coNP
Say $\ell: \\{0,1\\}^\ast \to \\{0,1\\}^\ast$ is a one-to-one polynomial-time computable function that preserves length. Consider the language $$L = \Bigl\\{v \\;\Big|\\; \exists u: \bigl(u\_1 = 1 ~~\text{and}~~ \ell(u) = v\bigr) \Bigr\\}.$$ How do I prove that $L$ is in $\mathsf{NP} \cap \mathsf{coNP}$? Basically, what would appropriate witnesses for $L$ in $\mathsf{NP}$ and $\mathsf{coNP}$ be?

# Answer
> 4 votes
Hint: Use the fact that $\ell$ is one-to-one, and so to every $v$ there corresponds a unique $u$ such that $\ell(u) = v$.

---
Tags: np-hard, np
---


# Question
Title: What type of formal notation is being used here to represent functional algorithms?
Interested in learning more about algorithm design in functional programming, I picked up Andrew Bird's Pearls of Functional Algorithm Design. I have experience with a number of programming languages, but my only experience with functional programming is in Scala. I understood that I would have to pick-up Standard ML and Haskell from the description of the book, but when I started reading the first section, I wasn't familiar with some of the operators being used.

Here are some examples of function definitions from the first chapter of the book (free to preview on Amazon):

---

I have seen "^" and "v" used to represent "and" and "or," but some of the other syntax (like `False (0,n)`) still throws me off.

In this one, I'm not sure what the `accumArray(+)...` is referring to. I'm thinking it's like a fold method using addition, but I don't understand the rest of the line.

Here, the author has done a good job of describing that \\ is set difference and the two vertical lines crossed with a horizontal one is union. However, I've never seen anything like that union symbol before.

---

I don't want to know what each of these examples means as much as I want to know **what library of formal representation is Bird using to represent these algorithms**, and also, if a specific programming language (Haskell/SML?) syntax is being used as well in conjunction with these special symbols.

# Answer
> 5 votes
The language is pretty-printed Haskell.

In regular source code, it would look like this:

```
checklist :: [Int] -> Array Int Bool
checklist xs = accumArray (||) False (0, n)
               (zip (filter (<= n) xs) (repeat True))
               where n = length xs

countlist :: [Int] -> Array Int Int
countlist xs = accumArray (+) 0 (0, n) (zip xs (repeat 1))

(as ++ bs) \\ cs = (as \\ cs) ++ (bs \\ cs) -- Not actual code
as \\ (bs ++ cs) = (as \\ bs) \\ cs
(as \\ bs) \\ cs = (as \\ cs) \\ bs

```

# Answer
> 3 votes
I haven't read the book but the snapshot is definitely Haskell. Most texts that contain Haskell code use some kind of pretty printer, most likely lhs2TeX. It assigns more type-setting-friendly symbols to many standard Haskell infix operations such as `++` or `<=`.

I suggest you to use browse Haskell's Prelude module, which contains functions available to all Haskell programs by default. Or you can search for a particular function using Hoogle.

---
Tags: algorithms, formal-languages, functional-programming, notation
---


# Question
Title: clarification about Algorithm of page replacement LRU with reference bits
Studying LRU approximation Algorithms I think to have not understand how it works, for example:

```
consider a process with 3 logical pages and 2 frames allocated , an approximation of the
Algorithm Last Recently Used based of reference bits where every four references there is
a shift and where are considered just the first 2 bits, and the follow reference string:

```

> 1 2 1 1 1 1 0 1 0 0

I'd solve it in this way:

> 1 2 1 1 **(*m1)*** 1 1 **(*m2)*** 0 1 0 0

**(*m1)***

4 references so I'd pass from

```
 frame                     frame
 -----+---+---     to       -----+---+---
    1 | 1 | 0                  1 | 0 | 1
    2 | 1 | 0                  2 | 0 | 1

```

**(*m2)***

page fault so I'd pass from

```
 frame                     frame
 -----+---+---     to       -----+---+---
    1 | 1 | 1                  1 | 0 | 0
    2 | 0 | 1                  0 | 0 | 0

```

So the questions are:

* Is my doing correct?
* At **m2** there is a page fault, is there a "reset" and all bits puts at 0?
* the shift frequency (4 in the example) restart counting every page fault?

# Answer
> 2 votes
> Is my doing correct?

If I don't misunderstand your notation, when you manipulate the frame for first time (filling it with page 1, then page 2) and then page 1 is called again, you shouldn't send to disk page 2, there is no need because page 1 it is already in frame.

---
Tags: operating-systems, paging, virtual-memory
---


# Question
Title: Simulation BPP by Pseudorandom Generator
I use the following scribe to study Pseudorandom Generators.

The most intriguing question for me is how exactly PRG can be used in order to simulate BPP.

Let $A(x,r) \in BPP$, where $x$ is primary input and $r$ - randomness provided by BPP. Instead of $r$ we can provide $A$ with pseudorandom input $G(U\_{d(n^c)})$ and according to the **Claim 7.6** from the scribe. $A$ with pseudorandom input differs from $A$ with random $r$ in less than half of running cases. The proof of Lemma shows that if it's so, that there is a distinguisher that distinguishes $U\_{d(n^c)}$ from $U\_{n^c}$ with advantage at least $\frac{1}{2} - \frac{1}{3} \> \frac{1}{8}$ which is contradicts to the definition of PRG.

Q: Where this advantage comes from? I simply don't understand what these numbers mean.

Q: Construction question. Why do need to run over all seeds of length $d(n^c)$ there are $2^{(d(n^c))}$ such string. For me it sounds like a strengthening of randomness because after that we use the majority as a result. But actually why do need that, why we cannot use single seed of length $d(n^c)$.

Q:Philosophical question. Why do we need PRG to be non-uniformly strong? Why we cannot use uniformly indistinguishable PRG? I saw the idea that the primary input $x$ to the $A$ can be used as advice, but I still don't understand why do we need it.

# Answer
The idea of a PRNG is coming up with a "deterministic" sequence that "looks like" random, in the sense that programs getting access to it act (roughly) as if they had access to a completely random string. The PRNG takes a seed or a key, and outputs a larger pseudorandom sequence. When simulating some probabilistic algorithm, instead of choosing a completely random string, it is enough to choose a random seed and use a PRNG.

How would you use a PRNG to simulate (say) a BPP algorithm? Suppose we had a PRNG that takes a seed of length $L = O(\log n)$, and $\epsilon$-fools every BPP algorithm. (Pseudorandom sequences don't look completely random, but in this case, using them instead of a random sequence changes the probability of any event by at most $\epsilon$.) That means that if we pick the seed at random, then the BPP algorithm returns the correct answer with probability at least $2/3-\epsilon$ (supposing that the original success probability was $2/3$ - that depends on your definition of BPP). If $\epsilon \< 1/3$, then we have the following property:

* If we run the algorithm on a YES instance and a random seed, then it returns YES with probability larger than $1/2$.
* If we run the algorithm on a NO instance and a random seed, then it returns YES with probability less than $1/2$.

This property assumes we choose a random seed, but we wanted a deterministic algorithm. To that end, we go over *all possible seeds*, and calculate the probability that the algorithm returns YES. This is just the number of times that the algorithm returns YES divided by $2^L$. If the probability is larger than $1/2$ then it's a YES instance, otherwise its a NO instance. If indeed $L = O(\log n)$, then $2^L$ is polynomial, and we obtain a deterministic polynomial time algorithm.

Now regarding your questions:

1. I haven't looked at the scribal notes, but the advantage might come from the BPP algorithm.
2. Looking at a fixed seed is the same as looking at a fixed "random" sequence - you don't need a PRNG for that. All you know is that on average, the performance of the algorithm on a pseudorandom sequence correlates with whether the input is a YES or a NO instance. That doesn't say *anything* about a single seed.
3. As to uniformity, the program that your PRNG should fool is $A(x)$ for an arbitrary input $x$. While $A$ is a uniform circuit, $A(x)$ isn't, since $x$ could be arbitrary. Your PRNG should fool at one and the same time $A(x)$ for *all* possible inputs $x$.
> 5 votes

---
Tags: complexity-theory
---


# Question
Title: Generating 3SAT circuit for Integer factorization example
I read somewhere that 3SAT can be used to solve Integer Factorization.

If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given the number 6, then the factors are 2 and 3.

# Answer
First we reduce the task of factorization to finding any factor of $n$ (or showing that it's prime). Once we know how to do this, we divide $n$ by such an factor and repeat the process until all factors are broken down to primes, and this takes $O(\log n)$ steps.

Let $k=\lceil\log\_2 n\rceil$ the number of bits in $n$.

Next, we design a binary multiplication circuit that accepts two $k$-bit numbers and produces $2k$-bit results. The size of the circuit is obviously polynomial in $k$.

To the output of the circuit we add a $2k$-bit comparator that returns *true* if the result is equal to $n$ and *false* otherwise. We also add comparators to the inputs that check that the inputs are $\>1$. So the combined circuit takes two $k$-bit numbers and returns *true* if they're both $\>1$ and their product is equal to $n$.

Such a circuit can be described by a propositional formula, so this way we convert it to SAT.

Finally, we convert it from SAT to 3-SAT by a standard procedure. The result will be a 3-SAT formula with $2k$ propositional variables. If it is satisfiable, the propositional variables will just encode two factors of $n$. If it's unsatisfiable it means that $n$ is prime.
> 11 votes

---
Tags: np-hard, factoring, 3-sat
---


title: Determining grammar decidability

text:
# Question
Title: Determining grammar decidability
Got a final coming up, so I gotta get this concept down.

Given $A= \\{(G\_1,G\_2 \mid G\_1$ and $G\_2$ are two CFG's and $L(G\_1)=L(G\_2) \\}$. Is $A$ decidable?

Would it be sufficient to take an undecidable language such as $B= \\{x \mid L(M\_x)$ is a CFG $ \\}$. Then reduce it to A with function $f(x) = G'\_{M\_x}$?

# Answer
I don't really understand your reduction, but there is a very easy reduction from $ALL\_{CFG}=\\{G| G \text{ is a CFG and } L(G)=\Sigma^\*\\}$. Given $G$, Simply output $(G,G\_{\Sigma^\*})$, where $G\_{\Sigma^\*}$ is a (concrete) grammar that generates every word.

And the problem $ALL\_{CFG}$ can be shown to be undecidable with a very nice (but elaborate) reduction from the word problem for TMs.
> 2 votes

---
Tags: undecidability
---


title: Sorting Problem

text:
# Question
Title: Sorting Problem
I have come across the following problem.

You have $N$ registers, numbered $1,2,\dots, N$, each of which can hold an integer value. You are given the initial values of the registers, which have the property that every number from $1, \dots, N$ occurs exactly once among the $N$ registers.

Each register has a "**reset button**": pressing the reset button on register $i$ changes its value to $i$.

In one move you can pick any subset of the registers (say, registers $3, 5, 9$) and simultaneously press all their reset buttons.

**However you must ensure that every number from $1,2,\dots, N$ continues to occur exactly once amongst the $N$ registers**.

The cost of a move that resets $m$ registers simultaneously is $m^2$.

You can perform a sequence of such moves one after the other, and the total cost is the sum of the costs of the individual moves.

Register $i$ is said to be stable if it contains the value $i$. Given a target $K$, where $K \le N$, the goal is to perform a sequence of moves at the end of which at least $K$ registers are stable.

**Find the minimum possible cost for achieving this.**

My attempt on problem:

Let $A\[1, \dots, n\]$ be given registers with initial values.

```
1. Divide $A$ into Disjoint Sets
2. For each disjoint set maintain the number of elements in it.
3. Find the minimum operations from these subsets(explained below with example)

```

Example:

```
Register:      1  2  3  4  5  6  7  8  9  10  11

Initial Value: 11 3  6  9  8  4  1  5  10  2  7

```

and $K=7$

Since Every number should be in the register we need to `reset` set of registers as shown below.

We can Reset $1,11,7$ in a single `RESET` operation.

Similarly we can reset $2,3,6,4,9,10$ and $5,8$ in a single `RESET` operation.

So we now have $3$ disjoint subsets of $A$

Let

$S\_1=\\{1,11,7\\}$, note that $|S1|=3$

$S\_2=\\{2,3,6,4,9,10\\}$, $|S2|=6$

$S\_3=\\{5,8\\}$ and $|S3|=2$

So Minimum number of operations for $K=7$ is $(6^2+2^2)=40$.

Now we need to find minimum number of oprations form these three subset.

more formally Given $S=\\{S\_1, S\_2, \dots, S\_n\\}$ we need to find Subset $\\{S\_{i\_1},S{i\_2}, \dots, S\_{i\_p}\\}$ such that

$\sum\_{j=1}^{p} S\_{i\_j} \ge K $ and $\sum\_{j=1}^{p} S\_{i\_j}^2$ is as minimum as possible.

How to efficiently find the minimum number of operations from these subsets?

Any Alternative solution(s)?

# Answer
You have it right so far.

btw, the disjoint sets you are talking about are called cycles of the permutation.

An $O(n^2)$ time dynamic programming algorithm (for the problem you state at the end) works as follows:

We compute the arrays $M\_j\[1 \dots n\]$ such that $M\_j\[L\]$ contains the minimum cost of using $S\_1, S\_2, \dots, S\_j$ (your notation) to reset exactly $L$ registers in total. Note: exactly $L$, and if some exact $L$ is not possible to achieve, you set it to $\infty$.

$M\_{j+1}$ can be computed, given $M\_{j}$ and $S\_{j+1}$, in $O(n)$ time using:

$$M\_{j+1}\[L\] = \min\\; \\{M\_j\[L\]\\;,\\; M\_j\[L-S\_{j+1}\] + S\_{j+1}^2\\}$$

In the end, given your target of at least $K$, you find the minimum among $$M\_{n}\[K\], M\_{n}\[K+1\], \dots, M\_{n}\[n\]$$

By reusing the array, the space usage can be made $O(n)$.
> 2 votes

---
Tags: dynamic-programming, sorting, permutations
---