# Question
Title: Big O and program calls with varied input sizes
Suppose I have a program p that has time complexity $O(n)$ and a second program q that calls program p $m$ times. If we know the input size of p will be the same every one of those times (n), we can say that the complexity of q is $O(m \times n)$. This case sounds pretty simple to me.

However, suppose the input size of p varies over these $m$ times, from $0$ to $m-1$.

If we knew that p ran precisely $f(n) = a \times n$ instructions for an input of size $n$, it would be simple: q would run $a \times 0 + a \times 1 + \ldots + a \times (m-1) = am(m-1)/2$ instructions exactly, which is $O(m^2)$.

However, in this case, all we know is that $f(n)$ is below $a \times n$ for all $n$ greater than some $n\_0$, by the definition of big-O. We can't say for sure that $f(0) + f(1) + ... + f(m-1)$ is below $a \times 0 + a \times 1 + \ldots + a \times (m-1)$, because we don't know that $0, 1, \ldots, m-1$ are greater than this $n\_0$. For this reason, I don't think we can say that q runs in $O(m^2)$.

Is there a way, in this case, when all we know is the big-O behaviour of p, to analyze q?

What if we replace all the big-O's with big-Theta's?

# Answer
> 1 votes
Actually, since you did not specify what q does beyond calling p, there is too little information to know anything about the time complexity of q, except that it is $\Omega(m)$ since it must execute at least $m$ calls to p, whatever else it does.

Let's look at a special case which is probably what you were thinking of. Suppose that q looks like this:

```
data := preprocess(input);
for i = 0 to m -1 do
    data := p(data);
end

```

That is, p potentially has access to all the internal data of q. This is the most general case. Where this program is not general is that **in the loop, it does nothing but call p**.

The running time of this program is $Q = A + \left( \sum\_{i=0}^{m-1} P(S\_i) \right) + O(m)$ where

* $A$ is the time taken to run the preprocessing step;
* $P(s)$ is the maximum time taken by p to process data of size $s$;
* $S\_i$ is the size of `data` when the $i$th step starts.

The assumption on the running time of p is that $P(s) = O(s)$. That is, there exists $n\_0$ and $a$ such that if $s \ge n\_0$ then $P(s) \le a \\, s$. This gives us a bound for the running time when $s$ is large. When $s$ is small, we can simply use the maximum running time of p for small sizes: there are only a finite number of sizes that are smaller than $n\_0$. Let $\hat P = \max\\{P(0), P(1), \ldots, P(n\_0-1)\\}$.

Then, expanding the definition of $O(m)$ in the equation for $Q$ above, we get that there exist $m\_0$ and $b$ such that for $m \ge m\_0$, $$ \begin{align} Q &\le A + \left( \sum\_{i=0}^{m-1} P(S\_i) \right) + b m \le A + \left( \sum\_{i=0}^{m-1} \max \\{\hat P, a\\, S\_i\\} \right) + b m \\ &\le A + \left( \sum\_{i=0}^{m-1} (\hat P + a\\, S\_i) \right) + b m \le A + a \left( \sum\_{i=0}^{m-1} S\_i \right) + (b + \hat P) m \\ &\le A + a \left( \max\nolimits\_{i=0}^{m-1} S\_i \right) m + (b + \hat P) m \end{align} $$

Notice how the constant $\hat P$ resulting from the small cases of running the subprogram has been absorbed into the multiplicative constant for the calling program. This is a general phenomenon: when studying the complexity of algorithms, the performance of subtasks on small inputs is irrelevant for obtaining a first bound on the complexity of the whole task. It can be relevant to prove better bounds (sometimes, the inequalities above are too crude).

We aren't quite there yet: the component $\max\nolimits\_{i=0}^{m-1} S\_i$ remains unevaluated. The behavior of this component depends on what p does. For example, if p is a program that duplicates its input, say

```
return arg ++ arg

```

where `++` is the string concatenation operator and string concatenation takes $\Theta(n)$ where $n$ is the length of the string, then $S\_i = S\_0 2^i$ and all the analysis above tells us is that $Q$ grows exponentially with $m$ — which is the case.

If we additionally assume that **p does not change the size of the data** and that **the preprocessing step is linear in the size of the input**, then $S\_i$ does not depend on $i$ and is $O(n)$ (i.e. $S\_i \le S n$ for large enough $n$), and we have (for sufficiently large $n$ and $m$): $$ Q \le a' n + S n m + (b + \hat P) m $$ For sufficiently large $n$ and $m$, the dominant term is $S n m$: the time complexity of Q is $O(m n)$.

Note again that the reason why it took a lot of additional assumptions to prove that Q runs in $O(m n)$ is not the running time of p on smaller inputs, it's because for all we knew p could receive some very large inputs.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis
---


title: Prove that $|P(X)| = 2^{|X|}$

text:
# Question
Title: Prove that $|P(X)| = 2^{|X|}$
Prove that for any finite set $X$, $|P(X)| = 2^{|X|}$. The solution should use induction.

# Answer
Basis $$ |X| = 0 $$ $$|P(X)| = 2^{|X|} = 2^0 = 1$$ True. Any set with zero elements takes the form $\\{\\}$, and thus its power set will be $\\{\\{\\}\\}$. One element.

Inductive Step

We must show: $$|P(X+1)| = 2^{|X+1|}$$ Thus: $$|P(X+1)| = 2^{|X+1|} = 2\*2^{|X|} = 2\*|P(X)|$$ This is true because, if $X$ as a set grows by one, the power set, for every member in its set now has a new binary choice: include the new element or not. Thus the power set doubles.
> 1 votes

---
Tags: sets
---


# Question
Title: If $M$ recognizes an infinite language, then $M$ has a cycle
An NFA $M$ contains a cycle if there is a state $q$ and a string $x$ such that if $M$ is in state $q$ and reads string $x$, $M$ can return to state $q$. Prove:

If $M$ recognizes an infinite language, then $M$ has a cycle.

# Answer
> 1 votes
Whithout a cycle, each string can only traverse a state once. If it is at a state $q$, there exists no string $x$ that can return the machine to state $q$. So if a string can only traverse each state once, then we can bound the lenght of the string to k, the number of states. Thus you can only represent a finite number of strings if they are bounded in length ($\sum\_{n=0}^{k-1} |\Sigma|^n$). Thus to recognize an infinite language, there must be a cycle.

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


# Question
Title: Why the height of the weight balanced tree is logarithmic
Could somebody explain to me why the height of a weight balanced binary tree in $O(\log n)$ in the worst case?

# Answer
What have you tried? Where did you get stuck?

In particular, you're going to want to look at a proof by induction. Does a tree with 1 node have logarithmic height? Then look at a tree with $n$ nodes. When you add another node to a balanced binary tree, which you know to have logarithmic height, what is the worst thing that can happen to the height?
> 1 votes

# Answer
Think of a Weight Balanced Tree (wbt) as a certain instance of a quick sort run. The invariant of the wbt indicates that the 2 halves of the sub-arrays to be sorted recursively are Theta of each other. This means that each tree of execution in quick sort will never be deeper than Theta(log n).
> 1 votes

---
Tags: binary-trees, trees
---


# Question
Title: How to solve for recurrence with substitution or other methods?
Forgive me if I am new, I am trying to learn how to solve recurrences.

I have the following recurrence:

$$T(n) = 2 T(\lfloor\frac{n}{3}\rfloor) + \frac{1}{2} T(\lfloor\frac{2n}{3}\rfloor) + n^2 \text{ if } n\>0$$

Now from my understanding is that I am not able to use the following methods.

1. Master Thereom (because it's not in the form $aT(\frac{n}{b}) + f(n)$)
2. Tree Method (because of the $\frac{1}{2} T$, you cannot have a node of $\frac{1}{2}$), please correct me if I am wrong.

So which leaves me with the following method:

Only the substitution method, but what I don't understand that is the fact that for the substitution method, you have to guess for the $f(n)$ to substitute into the recurrence.

So my question is, how does one select the correct $f(n)$ to substitute?

# Answer
Use the Akra-Bazzi theorem. Let $p$ be the solution to $2\cdot(1/3)^p + (1/2)\cdot(2/3)^p= 1$, namely $p = 1$. Compute $$ S(n) = \int\_1^n \frac{x^2}{x^{p+1}} \\, dx = n-1= \Theta(n). $$ Then $T(n) = \Theta(x^p S(n)) = \Theta(n^2)$.
> 0 votes

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


# Question
Title: Characterising $(aa)^*$ in first order logic
In my descriptive complexity class, we've been asked to find a formula that characterises the language $(aa)^\*$ (over the alphabet $\\{a\\}$) with a first order formula over the language $\\{\<, P\_a\\}$.

This was the first class, so I will recall what we've learned to be sure that I understood. To a $L$-formula $\phi$ we associate a language $\mathcal L(\phi)$ which is the class of all $L$-structures in which $\phi$ is valid.

In my case, we then are looking for a $\\{\<, P\_a\\}$-formula for which words of even length are models. I guess I have to say in $\phi$ that $\<$ is a total order, so that I can interpret the models as words, and that $\forall x, P\_a(x)$ to say that all points are labelled as 'a'. But how to say that there has to be an even number of points in the model? The definition of having an even number of points seems recursive, so I get the impression that a formula for $(aa)^\*$ should be of infinite length in first-order logic..

# Answer
**Short answer**. There is no such first-order formula, you need a monadic second order formula.

**Details**. This can be proved directly using an Ehrenfeucht-FraÏssé games argument if you want to stay inside logic, but the real answer to your question is the conjunction of three results.

\[1\] Büchi (1960): A language is monadic second order expressible iff it is regular.
\[2\] McNaughton-Pappert (1971): A language is first-order expressible iff it is star-free.
Counter-free Automata. Research Monograph 65. With an appendix by William Henneman. MIT Press. p. 48. ISBN 0-262-13076-9.
\[3\] Schützenberger (1965): A regular language is star-free if and only if its syntactic monoid is aperiodic. On finite monoids having only trivial subgroups

\[3\] gives an algorithm to decide whether a given regular language is star-free (and hence, first-order expressible, by \[2\]). Now, the syntactic monoid of $(aa)^\*$ is the cyclic group of order $2$, which is not aperiodic. To get a monadic second order formula, you need first to have first order "macros" to express $\min$, $\max$ and $+1$ and then the following second order formula will do the job $$ \exists X\ \forall x\ (\min \in X \wedge \max \notin X) \wedge (x \in X \leftrightarrow x+1 \notin X) $$
> 7 votes

---
Tags: formal-languages, regular-languages, logic, first-order-logic
---


# Question
Title: Can a loop be expressed by only the sequence of statements and the choice of statements?
The theorem of structured programming says that any algorithm can be expressed by those three control structures:

1. Sequence
2. Selection
3. Iteration

Isn't it possible to rewrite any loop using a finite sequence of statements and choice between statements? Isn't this what compilers do? Can't we thus omit the third structure and stay equally expressive?

# Answer
I convinced myself that this is not possible, I was indeed mixing up the *selection* structure with *conditional jumps*; but they're not equally expressive.

The *conditional jump* is as powerful as both *selection* and *iteration* together; this is what compilers use to rewrite both *choice* statements and *loop* statements.

As a counterexample for rewriting any loop using only the first two control structures, think of an infinite loop. This can not be rewritten using only *sequence* and *selection* while it can be rewritten using *sequence* and *conditional jumps*. So, we would lose expressiveness if we went without *iterations*.

---

Addendum to clear up the terminology:

1. *Sequence*
2. *Selection* (synonymous to *choice*), for example IF or SWITCH
3. *Iteration* (synonymous to *loop*), for example WHILE or FOR
> 4 votes

---
Tags: programming-languages, computation-models, programming-paradigms
---


title: Are turing machine really countable?

text:
# Question
Title: Are turing machine really countable?
I feel the notion "there are countably many Turing machines" is wrong. Suppose there is a Turing machine whose input alphabet is {0}. If we replace the input alphabet {0} with {a} and replace every occurrence of "0" with "a" in the transition table, then we get another Turing machine. Obviously, these two machines are different beacause they recognize different languages, but using any one reasonable encoding sheme, they could be encoded into the same string. So claiming Turing machines are countable only by enumerating their encodings is wrong, because actually there isn't a bijection between Turing machines and their encodings. Is my opinion right?

# Answer
> 13 votes
You are technically right. The correct phrasing should be that there are countably many TMs up to isomorphism of the tape alphabet and the state-space.

Indeed, if you say that a TM with states $\\{q,r\\}$ is different than the same TM with states named $\\{1,2\\}$, then not only are TMs not a countable collection, they are not even a *set* in the ZFC axiom system. This follows from the fact that the collection of all sets is not a set itself.

# Answer
> 2 votes
Maybe a more straightforward illustration of the "up to isomorphism" thing: take a TM with 1 state and no transitions, then you can generate uncountably many TMs by assigning the state some subset of $\mathbb{N}$ as its label. Since you get uncountably many labels this way, you have uncountably many, obviously isomorphic TMs.

# Answer
> -3 votes
I believe neither of the other two answers are correct, they are falling prey to the same logical mistake : that there are

> "uncountably many labels this way"

in the collection of subsets of $\mathbb{N}$.

However, only finite subsets should count. If the subset/language is finite, (or even finitely describable,) there are only countably many of them. See Wikipedia in particular: this sentence.

> **Theorem: The set of all finite subsets of the natural numbers is countable.**

So

> Indeed, if you say that a TM with states {q,r} is different than the same TM with states named {1,2}, then not only are TMs not a countable collection, they are not even a set in the ZFC axiom system.

is wrong.

The way I like to think of countable is

> If every element of the set can be theoretically written down **unambiguously** in a large enough finite book, then the set is countable. This should be self evident:)

**Examples:**

> The set of rationals. Every rational can be written down finitely.
>
> The set of algebraic numbers. Every algebraic number can be described by writing out the equation along with a number and an ordering scheme to define which value is meant.(I.e $x^2=0$ has both $x=\sqrt{2}$ and $x=-\sqrt{2}$.)

So unless you are using languages that cannot be defined finitely and therefore shouldn't count, your set of Turing machines is still countable.

If anyone can think of a reason why a machine that fails this test of "finitely describable" should count in a set of Turing machines when it can't be built and run, I'd be happy to hear about it.

---
Tags: turing-machines
---


# Question
Title: Which classifier is more accurate for a SVM classification?
I am learning the SVM classification and encounter a problem. I am not sure if this dilemma has a terminology for it.

Assume we would like to classify patient by SVM given the samples of healthy people ( of both gender) and people with liver cancer ( of both gender). If we label healthy people sample as class 1 and the people with cancer as class 2, we can train a binary SVM and obtain a classifier 1 to predict any new patient. Now, image another scenario. Assume that we first divide all samples by gender before SVM classification. For each gender, we still label healthy patients vs cancerous patients into 2 classes and train a binary SVM to obtain classifier 2 and classifier 3 for female and male samples respectively. The question is if there is a new female patient, which classifier, 1 or 2, should be used to obtain more accurate prediction ? Here is the dilemma for the arguments I have

(1) When the number of samples is large, the prediction should be more accurate. Based on this argument, the classifier 1 seems a good choice.

(2) However, if we divide samples into female and male groups first, the classifier 2 seems a better choice since the new patient (unknown test sample) is female.

Does this kind of dilemma have a terminology or does anyone know any further information or how to solve problem like this ? I am not even sure if this is a legit question and sorry for the naive question in advance. Thanks

# Answer
You should take a look at Feature selection and algorithms that automate this process. It's okay if you are new to ML and don't understand the entire feature selection process, just get the proper intuition and then you can use a library to automate the process.

The key idea of having a Learning algorithm is so that *it* can find the patterns ... the most you can do, is help *him* out by providing lots of (non-redundant) data and having a good preprocessing step, that usually involves stuff like feature selection, and normalization.

On a friendly note, when implementing learning algorithms, you *should not* try to modify your dataset just by 'looking' at it, unless you have concrete metrics that testifies it needs modifications, many a times, it has been the case, that the learning algorithm put high bias towards features that did not appear to be even remotely 'related' to the classification process. Always try to do a feature selection step before trying any modifications on your data.
> 3 votes

# Answer
one general heading for this type of step of the machine learning process is data preprocessing which wikipedia says includes "cleaning, normalization, transformation, feature extraction and selection, etc".

another aspect of machine learning is "creating the model". this involves decisions eg about how many classes will detected, what the "size" or "dimensions" of the ML structure will be (eg "how many Kernels will the SVM include" etc, roughly analogous to choice of number of neurons in a NN model). unfortunately some refs tend to skip or "gloss over" this step. but note its common with statistics and some statistics books will have a good description.

in ML type approaches it is conventional that there is a strong iterative/feedback/evolutionary process to determine both effective preprocessing and modelling. the experimenter tries various preprocessing and modelling ideas and moves in the direction of the more successful ones. the general rule of thumb is "the better the predictions, the more one is correctly \[and presumably also *realistically*\] preprocessing and modelling", but also given that overfitting is carefully ruled out.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: What kind of reductions are usually used in order to prove PP-completeness?
I've read that MAJSAT is PP-complete. Under what type of reduction is this true? What kind of reductions are usually used in order to prove PP-completeness?

# Answer
> 2 votes
Here "PP-complete" means "complete for PP". The definition of PP defines the complexity class PP; it does not define the type of reduction you can use, as that is an orthogonal concern. So, "complete for PP" actually means "complete with respect to a particular class of reductions", and the meaning of that is implicitly parametrized by a class of reductions (usually the reader assumes you will be able to infer the class, from context). For each class of reductions, you potentially get a different notion of completeness.

In this case, we're talking about polynomial-time many-one reductions, also known as Karp reductions -- the same class of reductions as is commonly used in the definition of NP-completeness. This becomes immediately clear if you read the proof of completeness of MAJSAT (it's immediate to see that this is the type of reduction that gets constructed, in that proof).

In the future, please make sure to do research through standard sources before asking here, and to use some effort to formulate your question clearly and precisely -- that will increase the chances that you get a useful answer.

---
Tags: complexity-theory
---


# Question
Title: Constructing regular expressions with given substring requirments
I'm having trouble with this question about regular expressions:

> Let $L\_1$ be the language of passwords containing at least one lowercase letter, at least one uppercase letter, and at least one number. Write down a regular expression that describes $L\_1$.

This is my answer, but I'm not too sure about it. I let $\mathcal{A}$ be the alphabet, and attempted to cover all permutations. I think my answer is correct, but is there a simpler way to go about it? \begin{equation\*} (\mathcal{A}^\*\mathcal{A}\_{LC}\mathcal{A}^\*\mathcal{A}\_{UC}\mathcal{A}^\*\mathcal{A}\_{No}\mathcal{A}^\*) \cup (\mathcal{A}^\*\mathcal{A}\_{LC}\mathcal{A}^\*\mathcal{A}\_{No}\mathcal{A}^\*\mathcal{A}\_{UC}\mathcal{A}^\*) \cup (\mathcal{A}^\*\mathcal{A}\_{No}\mathcal{A}^\*\mathcal{A}\_{LC}\mathcal{A}^\*\mathcal{A}\_{UC}\mathcal{A}^\*) \cup (\mathcal{A}^\*\mathcal{A}\_{No}\mathcal{A}^\*\mathcal{A}\_{UC}\mathcal{A}^\*\mathcal{A}\_{LC}\mathcal{A}^\*) \cup (\mathcal{A}^\*\mathcal{A}\_{UC}\mathcal{A}^\*\mathcal{A}\_{LC}\mathcal{A}^\*\mathcal{A}\_{No}\mathcal{A}^\*)\cup (\mathcal{A}^\*\mathcal{A}\_{UC}\mathcal{A}^\*\mathcal{A}\_{No}\mathcal{A}^\*\mathcal{A}\_{LC}\mathcal{A}^\*) \end{equation\*}

I'm really stuck on this second part:

> Let $L\_2$ be the language of "good" password. It is related to L1 by: \begin{equation\*} L\_2=\\{w\in L\_1 : w \text{ has length } \geq 8\\} \end{equation\*} Specify a regular expression that describes $L\_2$, without writing it down in full. What is the length of this regex?

I'm not sure about how to construct a regular expression using my answer for $L\_1$. I thought it might be similar to the first part, where I could specify all the permutations.

# Answer
Hint: Replace each sub-expression of the form $\Sigma^\* A \Sigma^\* B \Sigma^\* C \Sigma^\*$ with a union of expressions of the form $\Sigma^\alpha \Sigma^\* A \Sigma^\beta \Sigma^\* B \Sigma^\gamma \Sigma^\* C \Sigma^d \Sigma^\*$ for appropriate $\alpha,\beta,\gamma,\delta$.

Notice also the point of the exercise, namely that (plain) regular expressions aren't a good fit for describing passwords. We would really appreciate being able to *intersect* regular expressions (do you see how that helps?).
> 1 votes

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


# Question
Title: Is there a binary tree structure with fast access to recently accessed elements and worst $O \left( \log n \right )$ complexity?
The idea of splay trees is very nice as they move frequently accessed elements to the top, which can gain a considerable speed up in many applications. The drawback is that in the worst case an operation can have $O(n)$ complexity. (Although amortized bounds are $O(n\log n)$ if we perform at least $n$ operations.)

Is there a self-adjusting search tree structure that has both? Favoring recently accessed elements and with worst $O(\log n)$ complexity for a single operation?

# Answer
> 2 votes
It sounds like you're looking for a binary search tree with the **working-set property**; this is a good bit weaker than **dynamic optimality**. In fact, there are no known binary search trees with dynamic optimality, according to Iacono's "In pursuit of the dynamic optimality conjecture" from June 2013.

But, if you're looking for the simpler working-set property, you're in luck! The working-set property is that the time to access an item $x$ is proportional to the log of the number of items accessed since $x$ was last accessed.

There are a variety of structures with the working-set property. There is even one that is a binary tree, meets both the logarithmic worst-case bound and the working-set property in the worst-case, not just the amortized case: Bose et al's "Layered Working-Set Trees".

# Answer
> 5 votes
The amortized cost of entering an element to splay tree is $O(\log n)$ so in the worst case $n$ operations would do $O(n\log n)$ steps. There is a conjecture about splay tree that says that it is as optimal as a binary search tree up to constant factor called *Dynamic optimality conjecture*.

Tango trees are online, self adjacent trees that achive $O(\log \log n)$ competitive ratio compared to offline optimal binary search tree which is the best known.

# Answer
> 3 votes
I am not quite sure what you want to achieve with your data structure. Indeed, Splay-trees are a cool data structure. They are known to have the **static optimality** property. This means if you know the distribution of you search queries in advance and you built the optimal binary search tree for this distribution, then a splay-tree (without knowing the distribution) will perform asymptotically as good as the binary search tree. Of course, you may say this is cheating since the binary search tree cannot readjust, but it is still a very impressive property. People also expect, that splay trees are as good as any self-adjusting data-structure (known as **dynamic optimally conjecture**) - but this is one of the most prominent open question in the area of data structures.

Back to your question, since splay-trees are statically optimal, you have to sacrifice something. This means that if you access an element with low probability you might have to perform a more expansive operation. However, this is justified since the element is only rarely requested - and every statical optimal data structure will show this behavior. Of course you can always us a balanced binary search tree, but then you lose static optimality.

# Answer
> 0 votes
How about this procedure (works only for static BSTs).

With every node, you maintain a pointer to another node, which exists in the sub-tree rooted at that node. Along with the pointer, you also maintain the level number of the node being pointed to (along with your level number). The root is at level 0, and levels increase as you go down the tree. Initially, the pointer at a node points back to the node itself. The invariant is that you will only ever point to a node at a lower or equal level than the level number of the node.

When you search for an element in the tree, it will either:

```
1. Be found at its location in the BST, or
2. Be found along a path to its location because some node along the node to root path has a pointer to this node, or
3. Not be found at all.

```

In either case, we first make a forward pass to find the node, and if it is found, we bubble down the pointed nodes along the root to node path for the found node. If the node was found as a result of case-2, we only bubble down till the node that was pointing to the target node (this allows us to be quick for recently accessed nodes).

If a node is going to be bubbled down to a level greater than the node itself, we delete the node from the mapping set.

If a node that has no mapping is accessed, we create a new mapping for that node, and set it to replace whatever mapping existed at the node, and bubble it up progressively.

When a node is accessed, it is bubbled up all the way to the top.

---
Tags: data-structures, binary-trees, search-trees, splay-trees
---


# Question
Title: Constrainted Optimization Problem in Matrix Entropy
I have a constrainted optimization problem in the (Shannon) matrix entropy $\mathtt{(sum(entr(eig(A))))}$. The matrix $A$ can be written as the sum of rank 1 matrices of the form $\[v\_i\\,v\_i^T\]$ where $v\_i$ is a given normalized vector. The coefficients of the rank one matrices are the unknowns in which we optimize and they have to be larger than zero and sum up to 1.

In a CVX-like syntax the problem goes as follows: given variable $\mathtt{c(n)}$

$$\text{minimize} \qquad \mathtt{sum(entr(eig(A)))}$$

$$\begin{align} \text{subject to} \qquad A &= \sum c\_i v\_i v\_i^T\\ \sum c\_i &= 1\\ c\_i &\ge 0\end{align}$$.

Does any have an idea how to solve this efficiently? I already know it probably can't be cast as a semi-definite programming (SDP) problem.

# Answer
> 8 votes
**Edit:** A colleague informed me that my method below is an instance of the general method in the following paper, when specialized to the entropy function,

> Overton, Michael L., and Robert S. Womersley. "Second derivatives for optimizing eigenvalues of symmetric matrices." SIAM Journal on Matrix Analysis and Applications 16.3 (1995): 697-718. http://ftp.cs.nyu.edu/cs/faculty/overton/papers/pdffiles/eighess.pdf

**Overview**

In this post I show that the optimization problem is well posed and that the inequality constraints are inactive at the solution, then compute first and second Frechet derivatives of the entropy function, then propose Newton's method on the problem with the equality constraint eliminated. Finally, Matlab code and numerical results are presented.

**Well posedness of the optimization problem**

First, the sum of positive definite matrices is positive definite, so for $c\_i \> 0$, the sum of rank-1 matrices $$A(c):=\sum\_{i=1}^N c\_i v\_i v\_i^T$$ is positive definite. If the set of $v\_i$ is full rank, then eigenvalues of $A$ are positive, so the logarithms of the eigenvalues can be taken. Thus the objective function is well-defined on the interior of the feasible set.

Second, as any $c\_i \rightarrow 0$, $A$ loses rank so smallest eigenvalue of $A$ goes to zero. Ie, $\sigma\_{min}(A(c)) \rightarrow 0$ as $c\_i \rightarrow 0$. Since the derivative of $-\sigma \log(\sigma)$ blows up as $\sigma \rightarrow 0$, one cannot have a sequence of successively better and better points approaching the boundary of the feasible set. Thus the problem is well-defined and furthermore the inequality constraints $c\_i \ge 0$ are inactive.

**Frechet derivatives of the entropy function**

In the interior of the feasible region the entropy function is Frechet differentiable everywhere, and twice Frechet differentiable wherever the eigenvalues are not repeated. To do Newton's method, we need to compute derivatives of the matrix entropy, which depends on the matrix's eigenvalues. This requires computing sensitivities of the eigenvalue decomposition of a matrix with respect to changes in the matrix.

Recall that for a matrix $A$ with eigenvalue decomposition $A = U \Lambda U^T$, the derivative of the eigenvalue matrix with respect to changes in the original matrix is, $$d\Lambda = I \circ (U^T dA U),$$ and the derivative of the eigenvector matrix is, $$dU = UC(dA),$$ where $\circ$ is the Hadamard product, with the coefficient matrix $$C = \begin{cases} \frac{u\_i^T dA u\_j}{\lambda\_j - \lambda\_i}, & i=j \\ 0, &i=j \end{cases}$$

Such formulas are derived by differentiating the eigenvalue equation $AU=\Lambda U$, and the formulas hold whenever the eigenvalues are distinct. When the there are repeated eigenvalues, the formula for $d\Lambda$ has a removable discontinuity that can be extended so long as the nonunique eigenvectors are chosen carefully. For details about this, see the following presentation and paper.

The second derivative is then found by differentiating again, \begin{align} d^2 \Lambda &= d(I \circ (U^T dA\_1U)) \\ &= I \circ (dU\_2^T dA\_1 U + U^T dA\_1 dU\_2) \\ &= 2 I \circ (dU\_2^T dA\_1 U). \end{align}

While the first derivative of the eigenvalue matrix could be made continuous at repeated eigenvalues, the second derivative cannot since $d^2 \Lambda$ depends on $dU\_2$, which depends on $C$, which blows up as the eigenvalues degenerate towards one another. However, so long as the true solution does not have repeated eigenvalues, then it is OK. Numerical experiments suggest this is the case for generic $v\_i$, though I don't have a proof at this point. This is really important to understand, as maximizing entropy generally would try to make eigenvalues closer together if possible.

**Eliminating the equality constraint**

We can eliminate the constraint $\sum\_{i=1}^N c\_i = 1$ by working on only the first $N-1$ coefficients and setting the last one to $$c\_N = 1-\sum\_{i=1}^{N-1} c\_i.$$

Overall, after about 4 pages of matrix calculations, the reduced first and second derivatives of the objective function with respect to changes in the first $N-1$ coefficients are given by, $$df = dC\_1^T M^T \[I \circ (V^T U B U^T V)\]$$ $$ddf = dC\_1^T M^T \[I \circ (V^T\[2dU\_2 B\_a U^T + U B\_b U^T\]V)\],$$ where $$M = \begin{bmatrix} 1 & \\ & 1 & \\ &&\ddots& \\ &&&1\\ -1 & -1 & \dots & -1 \end{bmatrix},$$

$$B\_a = \mathrm{diag}(1+\log \lambda\_1, 1 + \log \lambda\_2, \ldots, 1 + \log \lambda\_N),$$

$$B\_b = \mathrm{diag}(\frac{d\_2\lambda\_1}{\lambda\_1},\ldots,\frac{d\_2\lambda\_N}{\lambda\_N}).$$

**Newton's method after eliminating the constraint**

Since the inequality constraints are inactive, we simply start in the feasible set and run trust-region or line-search inexact newton-CG for quadratic convergence to the interior maxima.

The method is as follows, (not including trust-region/line search details)

1. Start at $\tilde{c} = \[1/N,1/N,\ldots,1/N\]$.
2. Construct the last coefficient, $c = \[\tilde{c},1 - \sum\_{i=1}^{N-1} c\_i\]$.
3. Construct $A = \sum\_i c\_i v\_i v\_i^T$.
4. Find the eigenvectors $U$ and eigenvalues $\Lambda$ of $A$.
5. Construct gradient $G = M^T \[I \circ (V^T U B U^T V)\]$.
6. Solve $H G = p$ for $p$ via conjugate gradient (only the ability to apply $H$ is needed, not the actual entries). $H$ is applied to vector $\delta \tilde{c}$ by finding $dU\_2$, $B\_a$, and $B\_b$ and then plugging into the formula, $$M^T \[I \circ (V^T\[2dU\_2 B\_a U^T + U B\_b U^T\]V)\]$$
7. Set $\tilde{c} \leftarrow \tilde{c} - p$.
8. Goto 2.

**Results**

For random $v\_i$, with linesearch for steplength the method converges very quickly. For example, the following results with $N=100$ (100 $v\_i$) are typical - the method converges quadratically.

```
>> N = 100;
>> V = randn(N,N);
>> for k=1:N V(:,k)=V(:,k)/norm(V(:,k)); end
>> maxEntropyMatrix(V);
Newton iteration= 1, norm(grad f)= 0.67748
Newton iteration= 2, norm(grad f)= 0.03644
Newton iteration= 3, norm(grad f)= 0.0012167
Newton iteration= 4, norm(grad f)= 1.3239e-06
Newton iteration= 5, norm(grad f)= 7.7114e-13

```

To see that the computed optimal point is in fact the maximum, here is a graph of how the entropy changes when the optimal point is perturbed randomly. All perturbations make the entropy decrease.

**Matlab code**

All in 1 function to minimize the entropy (newly added to this post): https://github.com/NickAlger/nalger\_helper\_functions/blob/master/nalger\_helper\_functions/maxEntropyMatrix.m

---
Tags: optimization, entropy
---


# Question
Title: Isn't std::bernoulli_distribution inefficient? Designing a bit-parallel Bernoulli generator
C++11 has a convenient Bernoulli RNG, illustrated at http://en.cppreference.com/w/cpp/numeric/random/bernoulli\_distribution . However, distilling an entire random integer into a single random bit seems inefficient when the expectation parameter $p$ is rational with a small or power-of-two denominator. Is there a reasonably fast way to generate 32 random Bernoulli bits at once in such cases? My application uses long streams of bits, so I can keep track of statistics if needed (but this would consume runtime).

# Answer
> 2 votes
Actually, generating a pseudorandom integer is very fast, so the simple approach will likely be quite efficient. As always, beware premature optimization. Benchmark it first before assuming it'll be too slow.

If you have a power-of-two denominator, it's easy to come up with a procedure that doesn't require as many random bits -- but in practice this doesn't matter, because with most PRNGs, it's just as fast to generate an entire word as to generate a few pseudorandom bits.

# Answer
> 1 votes
If the denominator is a small power of two, say $p = A/2^B$, then you can divide the 64-bit integer into parts of length $B$, and compare each one to $A$. A similar idea works for $p = A/B$, only this time you think of your integer as being written in base $B$, and you have to worry about "extra digits": if $2^{64} = c\_kB^k + c\_{k-1} B^{k-1} + \cdots + c\_0$, you should reject if the input is at least $c\_kB^k$, since otherwise the lower-order digits wouldn't be uniform. These methods are not optimal, but might be faster than more randomness-efficient methods.

If you are generating a lot of random bits, each one should cost you about $h(p) = -p\log\_2 p -(1-p)\log\_2 (1-p)$ bits (less bits the more biased your bits are!). One method to achieve this is "arithmetic decoding" - you think of your random stream as infinite, and encoding a number $x \in \[0,1\]$. If $x \< p$ then the first output bit is $1$, and you continue with $x/p$. If $x \geq p$ then the first output bit is $0$, and you continue with $(x-p)/(1-p)$. Of course, you don't need all the random stream to decide which of these options is true. Just write $p$ in binary and compare it to successive bits of $x$. (The subsequent bits are more difficult this way.)

---
Tags: randomized-algorithms, integers, randomness, binary-arithmetic
---


# Question
Title: Prove L to not context free using pumping lemma on language L
$L = \\{0^i1^j0^i1^j|i,j \geq 0\\}$

I've tried letting $s = 0^p1^p0^p1^p$. But not sure where to go from here. Help would be appreciated.

# Answer
Take a look at the following proof; if this is "nasty", you might just be too picky. :)

Consider the string $0^p1^p0^p1^p \in L$. The string consists of four distinct parts with three boundaries separating the parts: $0^p1^p0^p1^p = (0^p)(1^p)(0^p)(1^p)$. By the pumping lemma for context-free languages, this string can be written as $uvxyz$ such that $vxy \leq p$ and $uv^kxy^kz \in L$. We must now determine what values the substring $vxy$ may assume. There are seven interesting cases:

* The substring $vxy$ consists entirely of one of the four parts of the string (four cases); or
* The substring $vxy$ consists of symbols from two adjacent parts and encompasses exactly one of the three boundaries (three cases).

Consider a representative of the first set of four cases; e.g., assume $vxy$ consists entirely of $0$s from the first part of the string. Pumping $vxy$ will change the number of $0$s in the first part of the string without affecting the number of $0$s in the third part, so we will not get a string in $L$. Similar reasoning applies to the other three cases.

Consider a representative of the second set of three cases; e.g., assume $vxy$ consists entirely of $0$s and $1$s from the first and second parts of the string. Pumping $vxy$ will change the number of $0$s from the first part of the string, and the number of $1$s from the second part, without affecting the number of symbols in the third and fourth parts of the string. Therefore, any pumped string cannot possibly be in $L$. Similarly reasoning applies to the other two cases.

Since, in each of the seven cases, pumping the substring fails to produce a string in $L$, we have a contradiction, namely, we assumed that the language is context free, but have found that the pumping lemma for context-free languages does not hold. We conclude that our assumption was incorrect, i.e., that $L$ must not be context-free.
> 1 votes

# Answer
**Hints**

1. What is the language $K = L \cap 0^\*10^\*1$ ?
2. Apply the pumping lemma to $K$ (or to $L$ directly).
> 1 votes

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


# Question
Title: Are the following loops $O(n^2)$ complexity
I'm presented with two snippets of code, and I need to determine their time complexity. I'm pretty convinced that both of these are $O(n^2)$, but I'm not 100% sure

1.)

2.)

# Answer
It's quite easy, you just have to write down the first terms :

1.) The print instruction will be called $n$ times, then $n/2$ times, then $n/4$ times, etc... Finally, the number of calls to print is $\Sigma\_{i=0}^{\log n} \frac{n}{2^i} = n \Sigma\_{i=0}^{\log n} \frac{1}{2^i} = n \frac{1-1/2^{\log n}}{1-1/2}=\mathcal{O}(n)$.

2.) The print instruction will be called $n$ times, then $n/2$ times, then $n/3$ times, etc... Finally, the number of calls is $\Sigma\_{i=1}^{n} \frac{n}{i} = n \Sigma\_{i=0}^n \frac{1}{i} = \mathcal{O}(n \log n)$.
> 5 votes

# Answer
Yes, they're both $O(n^2)$: in both cases, the outer ($i$) and inner ($j$) loops can be executed at most $n$ times each. Timot gives better bounds in his answer but remember that $O(-)$ is just an upper bound.
> 0 votes

---
Tags: algorithm-analysis
---


title: Immediate positions algorithm?

text:
# Question
Title: Immediate positions algorithm?
Im studying for the computer science subject GRE test, as an exercise i need to implement the followin algorithm in java, any idea on how to aproach it?.

Given a set $X$ and $z$ not in $X$, indicate between which would be the immediate positions $z$ in $X$

# Answer
> 1 votes
It depends on how $X$ is given. If $X$ is given unsorted, find the minimum element larger than $z$, and the maximum element smaller than $z$. If $X$ is given sorted, use binary search.

---
Tags: algorithms, algorithm-analysis, search-algorithms
---


# Question
Title: Are there algorithms to exactly minimize NFAs which are sometimes efficient?
I'm doing some research with NFAs, and I'm wondering there are algorithms which quasi-efficiently minimize them. I realize that this problem is $PSPACE$ hard, so I'm not looking for a polynomial time algorithm.

What I mean by this is an algorithm which may run in exponential time in the worst cases, but which uses some sort of heuristic to speed up the process, albiet not enough to make it exponential.

I'm only using this to try to get a better idea of what the minimal NFAs of certain languages look like. I'm not using it in any production code, so it doesn't need to be blazingly fast.

For example, the Antichains algorithm for NFAs does equivalence testing which is usually fast but sometimes has exponential explosion. I'm looking for something similar, but for minimization.

Note that I'm NOT looking for things like equivalences, etc. which run efficiently but don't produce a minimal NFA.

Bonus points to anyone who find one with an implementation, and quadruple bonus points if it's in Prolog or Python. If the tool I'm looking for doesn't exist, I'd be happy if anyone gave any old implementation of NFA minimization.

# Answer
> 3 votes
SAT solvers have been pretty good at this. See \[1\] for more; the method produces a minimal automaton in almost all cases. Following some references, Tsyganov \[2\] combined the Kameda-Weiner with local search methods.

I don't know if there are readily available implementations out there, but at least \[1\] describes the reduction to SAT. One can then use any available SAT solver.

---

\[1\] Geldenhuys, Jaco, Brink Van Der Merwe, and Lynette Van Zijl. "Reducing nondeterministic finite automata with SAT solvers." Finite-State Methods and Natural Language Processing. Springer Berlin Heidelberg, 2010. 81-92.

\[2\] Tsyganov, Andrey V. "Local Search Heuristics for NFA State Minimization Problem." International Journal of Communications, Network and System Sciences 5 (2012).

# Answer
> 2 votes
I've implemented the Kameda-Weiner algorithm; see the source on Github. Note, however, that a minimal NFA is not generally unique (there may be multiple solutions), so I don't know if I'd say it's "exact" as in your question.

# Answer
> 1 votes
The title of the question insists on an exact algorithm, but then you say it would "use some sort of heuristic to speed up the process". Generally, heuristics are associated with inexact solutions. This following paper is more focused on an inexact solution i.e. heuristics, but has some discussion and further references on the general minimization problem.

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


title: SAT not reducible to 2SAT

text:
# Question
Title: SAT not reducible to 2SAT
Why is the reduction $\textbf{SAT} \leq\_P \textbf{3SAT}$ possible, but $\textbf{SAT} \leq\_P \textbf{2SAT}$ not possible, given, that $\textbf{SAT}$ is $\textbf{NP}$-complete, $\textbf{2SAT} \in \textbf{NP}$ and $\textbf{3SAT} \in \textbf{NP}$?

# Answer
> 13 votes
I believe the asker is wanting to know specifically why the standard approach to reducing $\text{SAT}$ to $\text{3SAT}$ does not continue to extend to the $\text{2SAT}$ case. Here is a walkthrough as to why.

**Conversion of a SAT Instance to a 3-SAT Instance:**

For convenience, let us assume everything is in $\text{CNF}$, or conjunctive normal form. The $\text{SAT} \le\_p \text{3SAT}$ proof works by introducing dummy variables to spread the actual variables over multiple clauses.

**Illustration:** Consider a single clause in boolean formula $(x\_1 \lor x\_2 \lor x\_3 \lor x\_4)$. The $\text{3SAT}$ reduction works by introducing a dummy variable to represent a disjunction of two literals in hopes that it reduces the clause's length by one. For example, $y = x\_3\lor x\_4$. The clause can be rewritten as:

$(x\_1 \lor x\_2 \lor y) \land (\bar y \lor x\_3 \lor x\_4)$

Notice that these clauses are now in a $\text{CNF}$ for $\text{3SAT}$. If this is repeated multiple times for each clause, the final $\text{CNF}$ formula will be at most polynomial in length of the original. This is why a polynomial time reduction would suffice.

**Attempting to Apply the Method to Convert to 2-SAT:**

If we tried to use the trick above with a clause of length 3, $(a\lor b\lor c)$, then we would not get the desired improvement. Let our dummy variable here be $y=b \lor c$.

The result: $(a \lor y) \land (\bar y \lor b \lor c)$

As you can see, it still has a clause of size 3. If we used the method again on the second clause, we would end up with the same problem while also adding an additional clause of length 2.

It could be said that the simplest reason for this is because $\land$ and $\lor$ are binary operators. You still need to apply these operators on pairs of variables, then include an additional dummy variable (resulting in a clause of length 3).

There have been attempts at getting around this that are successful, but the resulting sequence of clauses become exponential in length. Handling such a formula is outside the scope of $\text{P}$, which is why such a reduction would not be a polynomial time reduction.

# Answer
> 3 votes
First of all, "not possible" is only under the assumption that $P\neq NP$.

While it is true that $2SAT\in NP$, we also know that $2SAT\in P$. Thus, if indeed $SAT\leq\_p 2SAT$, then $P=NP$.

The reduction $SAT\le\_p 3SAT$ is possible since we know that $3SAT$ is $NP$-complete, and therefore there is a reduction from every problem in $NP$ to $3SAT$.

# Answer
> 1 votes
one way to conceptualize this: this can be seen as a case of a more general phenomenon where various problems are "simpler" for "small" fixed parameters of the problem. this happens with many NP complete problems but also outside of NP (eg with undecidable problems becoming decidable for small fixed parameters). see also 2SAT, wikipedia for the proof that 2SAT is in P.

another way/angle to understand this phenomenon is that the Tseitin transformation allows conversion of arbitrary circuits (including SAT itself) to 3SAT but some of the conversions require 3 variables (but none require more than 3).

yet another way to visualize this concept is with the SAT transition point where it is (theoretically/empirically) found that formulas of particular structure move from "hard-easy-hard" based on alteration of basic form, in particular (with SAT) the clause/variable ratio, but the transition point phenomenon is known to apply to all NP complete problems.\[1\] in this case the (average) number of variables in clauses is also a source of a transition point from hard to easy.

\[1\] Phase transition behavior Toby Walsh

---
Tags: reductions
---


# Question
Title: why not just use a random number generator as a hash function?
I guess at the heart of this is that I don't really understand hash functions.

One article says any function mapping objects to an object of fixed size:

> A hash function usually means a function that compresses, meaning the output is shorter than the input. Often, such a function takes an input of arbitrary or almost arbitrary length to one whose length is a ﬁxed number, like 160 bits.

Why not just use a random number generator to generate the hash keys? Wikipedia suggests SHA1 which maps to $2^{160}\approx 10^{48}$ possible outputs has never experienced a "collision".

I was trying to understand why the hash is necessary in a probabilistic counting algorithm:

```
class LinearCounter():
    def __init__(self, m, h):
        self.array =  [False for x in range(m)]
        self.hash = h

    def add(value):
        self.array(self.hash[ value ]) = True

```

Is the hash necessary? Why can't we use a random number generator right away?

```
def add(value):
    self.array(int(m*random.random()))

```

# Answer
If I understand the question correctly, the answer is simple: if `Hash(object)` returns `27` when you call it this afternoon, we want `Hash(object)` to return 27 if we call it next week, on a different computer. If you use a random number generator in such a way that this is guaranteed, then go for it. Consider that a key use case for hash functions is implementing hash tables, and we want to be able to access what we put into a hash table tomorrow with the key we used today.

In your example, you might want to add a contains(value) method; using the hash, this would be as easy as checking self.hash\[value\] =? value. Otherwise, you'd need to iterate through the entire array to see if some position contains value.
> 11 votes

# Answer
To expand Patrick87's comment and help you better understand the probabilistic counting algorithm : Linear Counting is used to get an approximate value of the number of *distinct elements* in a big set $S$ *using a small amount of space*.

Suppose that you have a set of 1000 of names and you want to know how many *distinct* names are present in it. In the worst case (all names are distinct) you should use an array of 1000 names. But if you only want an approximation, then you can use a hash function to map the names to a much shorter bitmask of $m$ bits.

Suppose that $d$ is the number of distinct names. $L = d/m$ is the *load factor*.

* If $L$ is low ($L \< 1$) then few distinct names will be mapped (by the hash function) to the same bit, and the number of $1s$ in the final bitmask will be a good approximation of the "density" of distinct names in $S$;
* If $L$ is greater than 1 ($L \> 1$), then certainly (pigeonhole principle) some distinct names will be mapped to the same bit; but nevertheless the number of $1s$ in the final bitmask can still be used to approximate the number of distinct elements in $S$;
* If $L$ is high ($L \gg 1$) then many distinct names will be mapped (by the hash function) to the same bit, and probably all bits of the mask will be set to 1; in this case you cannot recover the number of distinct items in $S$ from the bitmask (and you should increase $m$).

If you use a random function instead of the hash function, you'll always end with all bits set to 1 (like in the case $L \gg 1$), and you cannot use it to approximate the number of distinct elements.

Returning to our example, suppose that there are only 2 distinct names, and $m$ = 10.

Using a hash function, the 1000 names will set 2 bits in the mask (or less probably 1 bit if they collide) and the approximate number of distinct names is $-10 \ln (8 /10) = 2.23$

Using a random function, the 1000 names will set all 10 bits in the mask, and the formula cannot be even applied.
> 6 votes

---
Tags: hash, probabilistic-algorithms
---


# Question
Title: Clarification sought for definition of a cut that respects a set A of edges in Graph Theory
From CLRS (3rd edition), I came have this question on page 626:

Given these definitions from the text,

DEFINITIONS: Given an undirected graph G = (V,E),

1. A CUT (S ,V-S) of G is a partition of V,

2. A LIGHT EDGE over a cut is any edge crossing the cut with a weight smaller than or equal to any other edge crossing that cut,

3. A cut RESPECTS a set A of edges if no edge in A crosses the cut.

In every example in the text, the set A is coincident with one of the partitions of the cut but I cannot see why this must be. Given an arbitrary new vertex v', it could be added to the partition that contains A and no edge from v' to A would cross the cut. The definition of respects says that a cut cannot divide A, not that A must define the partition.

There is clearly something here I missed since that does not seem consistent with the theorems. Can anyone point out my error?

+++++++++++++++

Amendment. Thanks for the help. I also now realize that Theorem 23.1 only says that a light-edge is a safe edge but not that such a cut is guaranteed to find every safe edge since some edges may have both vertices in the same partition as A. I see in GENERIC-MST(G) that line 3 only says to find an edge. It is not until Kruskal or Prim algorithms that the method by which we find this edge is explained and neither depend upon the partition being coincident with the set of vertices defined by the set of edges A.

I find it interesting that in Kleinberg Tardos that they take a different approach and define a cut property (4.17, pg 145) that avoids this (what I find awkward) development of the ideas.

# Answer
> 1 votes
One mistake you're making with the statement:

> In every example in the text, the set A is coincident with one of the partitions of the cut but I cannot see why this must be.

$A$ is a set of *edges*, while a cut is a partition of *vertices*: $(S, V - S)$.

Suppose, as you say, that $A$ is a subset of the set $\\{(u,v): u,v \in S\\}$, then $A$ respects the cut $(S,V-S)$ because none of the edges with both ends in $S$ will cross the cut.

If you add a new vertex $v'$ into $S$, and some other edges from $v'$ to other vertices $x$ in $S$, then $A$ can include ALL of these edges and still respect the cut $(S,V-S)$ because both $v'$ and the other edges from $v'$ are in $S$.

---
Tags: graphs, terminology
---


# Question
Title: Class of the language of Turing machines that loop on at least one input
$L = \\{ \langle M \rangle \mid \text{there is at least one input string on which the \\(M\\) does not halt} \\}$

Here, for a Turing machine $M$, the notation $\langle M \rangle$ denotes an encoding, over some alphabet, of the code of the Turing machine. To which of the following language classes does $L$ belong?

1. Regular.
2. Context-free but not Regular.
3. Recursive but not Context-free.
4. Recursively enumerable but not recursive.
5. Not recursively enumerable.

# Answer
> 1 votes
The language $L$ consists of (descriptions of) Turing machines $M$ such that $M$ does *not* halt on all inputs. In other words, $\langle M \rangle \notin L$ if $M$ halts on all inputs. Can you think of any connection to the halting problem?

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


title: What is "polynomial delay?"

text:
# Question
Title: What is "polynomial delay?"
I am reading a paper and it uses the expression "polynomial delay" which I don't understand. It is used in conjonction with the big O notation, which I'm familiar with.

Here is a example sentence showing how it is used:

> The loop is executed in time $O(n^2(e+n))$, which makes a polynomial delay for the output of the data.

I've tried searching a bit but I can only seem to find other papers and no definition.

# Answer
The term "polynomial delay", in this case, appears to refer to the time complexity of generating (or enumerating) subsequent solutions. This is a bit different than our standard notion of runtime, since we usually only consider single executions of a machine or algorithm on an input. The *delay complexity measure* deals with time spent between enumerations through a set (e.g. a set of solutions).

Suppose you are working with a large dataset or database. You might want to step through or enumerate solutions to some problem using that data as an input. There are at least two steps involved here:

1. Initialization (perhaps generating your first solution)
2. Computing the next solution for the purpose of enumeration.

For example, you might use a polynomial space or exponential time algorithm to initialize and preprocess your data. To find or generate multiple solutions to a problem, you may only need to do a little bit of extra work. The time complexity with generating that next solution is the time delay complexity measure that you encountered in that paper. In particular, the time delay between enumerations is polynomial in respect to the input.

Jan Ramon mentions this and other time complexity measures in his talk on "General Graph Refinement with Polynomial Delay": http://videolectures.net/mlg07\_ramon\_ggr/
> 9 votes

---
Tags: algorithm-analysis, terminology, landau-notation
---


# Question
Title: How to map the tapes of a "k-tape" Turing Machine into the single tape of a "1-tape" Turing Machine
I'm reading Sipser and I'm finding it hard to understand what the process is such that if you give me k Turing machines with k tapes, I can spit out an equivalent Turing machine with only one tape. An example would be nice. Actually, a worked out example that shows how to go from TM that has $k$ tapes to one that has 1 tape is what I'm really looking for. I have been unable to find one so far. I'm also not looking for any proofs.

# Answer
> 27 votes
An answer shamelessly copied from myself:

A multi-tape Turing Machine is mostly the same as a single-tape machine, except we have an extended transition function $Q\times\Gamma^{k}\rightarrow Q\times\Gamma^{k}\times\\{L,R\\}^{k}$ where $k$ is the number of tapes. So in each state, the transition function reads the contents of each tape, moves to a new state, (maybe) writes something on each tape and moves each head - just as a regular TM, except now we have more things to read, write and move.

As your question suggests, such a machine can be simulated by a *single-tape* TM. Even better, it can be done with only quadratic slowdown (so for polynomially closed classes, it's sufficient to talk about single-tape machines).

The proof for this is somewhat involved, and easily available with a simple web search, so I'll just sketch the key mapping of the $k$ tapes to a single tape.

The basic idea is pretty straightforward; we simply add a few new symbols and keep track of each tape and head one after the other. At each step in the computation we can only have visited a finite amount of any of the tapes, so we need only to store this much information about each tape. Thus for each $\gamma \in \Gamma$ we add a new symbol $\underline{\gamma}$ to $\Gamma$ which will indicate where the head (for each tape) is at any point in the computation. We also introduce a separator character $\\#$ to $\Gamma$ which will indicate the start and end of the "virtual" tapes. Given input $\omega = \omega\_{1}\ldots\omega\_{n}$ (we can assume that even on the multi-tape machine all of the input is on the first tape - proving why is a good exercise) on the multi-tape machine, our single-tape machine will have input $$ \underbrace{\\#\underline{\omega\_{1}}\ldots\omega\_{n}\\#\underline{\sqcup}\\#\underline{\sqcup}\\#\ldots\\#\underline{\sqcup}\\#}\_{k \text{ sections, one per tape}}\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup\ldots $$

We then use the state of the single-tape machine to encode what state the multi-tape machine is in and what the heads are looking at. The transition function of the single-tape machine is a multistage simulation of the multi-tape transition function, where we perform the $k$ different tape actions appropriately, moving up the single tape to each section in turn. The only wrinkles left are shifting everything along when we run out of space in a section (but such a sub-machine is a simple exercise) - we never reduce the size of each section.

**A (hopefully) simple example:**

Say we have a 3-tape TM, where the input alphabet is just $\Sigma=\\{0,1\\}$, the tape alphabet is $\Gamma=\\{0,1,\sqcup\\}$ and the input is $\omega=10101$. The initial tape state of the machine looks like: $$ \begin{array}{lc} \text{Tape 1:} & \underset{\wedge}{1}0101\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array} $$ The "$\wedge$" is to denote where the read/write head is on each tape.

To construct the combined single-tape machine, we need to add new symbols to the tape alphabet:

1. We need a symbol that will denote the start and end of the simulated tapes
2. For each symbol in $\Gamma$ we also need a version that indicates that the simulated tape head is at that character on the simulated tape.

So for the single-tape machine, our new tape alphabet is $\Gamma' =\\{0,1,\sqcup,\underline{0},\underline{1},\underline{\sqcup},\\#\\}$. The initial state of the tape is: $$ \\#\underset{\wedge}{\underline{1}}0101\\#\underline{\sqcup}\\#\underline{\sqcup}\\#\sqcup\sqcup\sqcup\ldots $$ Note the difference between the head of the machine (the $\wedge$) and the simulated heads of the 3 simulated tapes (the underlined characters). Of course the tape extends infinitely to the right as usual. I have also cheated mildly by moving the tape head to the first character on the first string; strictly it should start out on the leftmost cell, but this is a trivial technicality.

So we have three marked out sections (between the $\\#$ marks), which will correspond to the 3 tapes of the original machine.

Now let's make up an action for the machine. Let's say that the original machine reads from the first tape, if it sees a $1$, it writes a $1$ on the second tape, if it sees a $0$ it writes a $1$ on the third tape. At each read or write, the head moves to the right.

So after the first "step" (perhaps requiring several states and transitions in the actual machine), the tapes should have a $1$ on the second tape, and the first and second heads will have moved right one step:

$$ \begin{array}{lc} \text{Tape 1:} & 1\underset{\wedge}{0}101\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array} $$

On the second go around, the first tape reads a $0$, so we write to the third tape instead:

$$ \begin{array}{lc} \text{Tape 1:} & 10\underset{\wedge}{1}01\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array} $$

The single-tape machine simulates this by moving the underline (by using the alternate version of the characters in $\Gamma'$, and writing to the appropriate simulated tape. So after the first step, the combined tape looks like:

$$ \\#1\underset{\wedge}{\underline{0}}101\\#1\underline{\sqcup}\\#\underline{\sqcup}\\#\sqcup\sqcup\sqcup\ldots $$

After the second step:

$$ \\#10\underset{\wedge}{\underline{1}}01\\#1\underline{\sqcup}\\#1\underline{\sqcup}\\#\sqcup\sqcup\sqcup\ldots $$

Of course this is a high level view of the process - I haven't attempted to explain how to construct the states, or how each simulated tape gets longer (for this, you need a little routine that checks if you've run into the end of the simulated tape, then moves everything to the right one step along and squeezes in a new blank - i.e. it only adds simulated tape cells when they're needed).

---
Tags: turing-machines, simulation
---


# Question
Title: Math term for Associative arrays/Maps/Dictionaries
What would be the equivalent math concept for associative arrays/maps/dictionaries?

EDIT: Disregard mutability. FYI,off topic, the reason why I ask this question, is that I want to calculate the distance(or similarity) between two maps given that I have a distance function for each entity(or key) in the map.

# Answer
Function ($A \to B$). If that doesn't work for you, try a set of pairs (subset of $A \times B$).

Note that something like mutable state is not common in maths, outside of computer science.
> 3 votes

---
Tags: discrete-mathematics
---


title: Two Dimensional Tape of Turing Machine

text:
# Question
Title: Two Dimensional Tape of Turing Machine
I was looking at this: http://www.cs.odu.edu/~toida/nerzic/390teched/tm/othertms.html

At the very beginning, they show a 2d tape and (I assume) it's 1d equivalent. However, I cannot figure out they got from the 2d case to the 1d case. I was hoping someone could elaborate.

# Answer
> 2 votes
The idea is very similar to the way we show that the rational numbers are countable. Essentially, what you need to do is to find a (bijective) mapping of the 2D tape onto the 1D tape. Of course, you want this mapping to be computable, and it would be helpful if it is computable efficiently.

The illustrative way to think about this is in diagonals: the cell $(1,1)$ is mapped to cell $1$ in the 1D tape. Then the second diagonal, namely cells $(1,2)$ and $(2,1)$ are mapped to cells $2,3$ respectively. Continuing in the same manner, you can map the entire 2D tape to the 1D tape. Of course, any movement of the head needs to be translated to the correct position in the 1D tape, so a single movement in the 2D tape may actually take several operations to simulate in the 1D tape.

There are many explicit functions that compute such a mapping. See for example the Cantor pairing function.

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


# Question
Title: NP-COMPLETE:Why say "reduction algorithm computes reduction function"?
In Chap 34.3 *NP-completeness and reducibility* of the book, *Introduction to Algorithm(3rd Edition)*, the author states(the original text):

We call the function *f* the ***reduction function***, and a polynomial-time algorithm *F* that computes *f* is a ***reduction algorithm***.

In my mind, function should be a machine dependent implementation(a set of instructions) of the algorithm. Why does he say *algorithm* computes *function*?

# Answer
> 5 votes
A *function* is a mapping from elements in the domain to elements in the range. Here is an example of a function: $f(n) = n!$. If you want a machine to compute $f(n)$ given $n$, you need an algorithm, for example: given $n$, multiply together all the numbers from $1$ to $n$. There can be other algorithms for computing $f$. The function exists without reference to a machine. In fact, some functions (such as the halting function) cannot be computed by any algorithm.

You might be confusing the mathematical meaning of the term *function* with its meaning in programming languages, which is what you describe.

---
Tags: np-complete, complexity-classes
---


# Question
Title: least significant bit,and most significant bit
if a,b are both binary bit. a=0, and b=0, what is least significant bit,and most significant bit of a+b, which means 0+0? if c is the carry bit, and c=1, what is the least significant bit,and most significant bit of a+b when a=0,b=1

My thought is 0+0=0, thus least significant bit,and most significant bit are same, which is 0. and if C is carry bit, than a+b=1, then add carry bit, which is 10, so the the least significant bit is 0, and msb is 1..am I right? someone help

# Answer
> 2 votes
"Most significant bit" is a concept that depends on the size of the machine word. If $a + b + c = 10$ and the machine word has size $64$, then the MSB is $0$. It is $1$ only if the machine word has size $2$. (Under your definition, the MSB is always $1$, unless the number is $0$, in which case it is undefined.)

---
Tags: computer-architecture
---


title: Banker's Algorithm and deadlocks

text:
# Question
Title: Banker's Algorithm and deadlocks
So we have the following table of processes , where A, B and $\Gamma$ are the resources.

Here is a pic that i drew with the processes and the resources.

So the exact question is this: Using banker's algorithm, calculate the minimum values of $x$ and $y$ in order the system is Deadlock free.

I have done pretty much *huge* paper work and found that $x,y$ should be the numbers 2 and 3. But in order to find this I run the algorithm on paper several times ; for $\[x,y\] = \[0,0\],\[0,1\],\[1,0\],\[1,1\],\[1,2\]$ etc. until I found that for pair $\[x=2, y=3\]$ the system is deadlock free!

So, I think that I am missing the point. All this took me like 1 hour or so. Is there a simple method with less paperwork?

Thanks a lot in advance!

# Answer
A "shortcut" to the solution; first calculate the `NEEDED = MAX - ALLOCATED`resources:

```
    ALLOCATED MAX      NEEDED
    A B C     A B C    A B C
P1  0 1 0     7 5 3    7 4 3
P2  2 0 0     3 2 2    1 2 2
P3  3 0 2     9 0 2    6 0 0
P4  2 1 1     2 2 2    0 1 1
P5  0 0 2     4 3 3    4 3 1

AVAILABLE: x y 2

```

In order to complete P1 we need 4 Bs. But if you observe the column B of ALLOCATED, we see that we can only gain a single B if P4 is executed before P1. So whatever the execution order is, we need more than 3 new Bs (y \>= 3).

Furthermore in order to complete P3 we need 6 As, but if you look at column A of ALLOCATED, we see that we can only gain 4 Bs if P2 and P4 are executed before P3. So whatever the execution order is, we need more than 2 new As (x \>= 2).

So we have:

```
AVAILABLE: 2+x' 3+y' 2

```

and we can start completing processes that need less than `(2 3 2)` (P4 and P2)

```
P4: (2 3 2) - (0 1 1) + (2 2 2) = (4 4 3)
P2: (4 4 3) - (1 2 2) + (3 2 2) = (6 4 3)
now also P3 can be completed:
P3: (6 4 3) - (6 0 0) + (9 0 2) = (9 4 5) which are enough resources for
both P1 and P5

```

So the state is safe even with x'=0 and y'=0 and the solution is x=2, y=3
> 1 votes

# Answer
For $\[x,y\] = \[2,2\]$, we get the result. Therefore the minimum is $\[x,y\] = \[2,2\]$. We get the correct sequence as $P\_3 P\_4 P\_1 P\_2 P\_0$ is the safe sequence with $\[x,y\] = \[2,2\]$.
> -1 votes

---
Tags: algorithms, reference-request, concurrency
---


# Question
Title: Undecidable among these for turing machine
Below are two questions I found in Theory of Computation book but couldn't find its correct answers, can anyone please give correct answers with explanation?

1. It is undecidable, whether
    1. an arbitrary Turing machine(TM) has 15 states
    2. an arbitrary TM halts after 10 steps
    3. an arbitrary TM ever prints a specific letter
    4. an arbitrary TM accepts a string w in 5 steps
2. Which one of the following is not decidable?
    1. given a TM M, a string s and an integer k, M accepts s with k steps
    2. equivalence of two given TMs
    3. language accepted by a given DFSA(Deterministic finite state automata) is nonempty
    4. language accepted by a CFG(Context free grammar) is nonempty

Update: In first question I think 1.2 is right because halting is undecidable for Turing machine but not sure whether remaining options are decidable or not.
In second question I think 2 is right, but not sure about the decidability of non emptiness of CFG and DFSA.

# Answer
> 17 votes
> (1.1) Is it undecidable whether an arbitrary Turing machine(TM) has 15 states?

No, this is a decidable problem. Given a TM in a suitable encoding, it is fairly straightforward to determine how many states the TM has. Consider any common encoding, or define a reasonable one yourself, and then describe an algorithm that answers the question using the encoding. *Hint: you can make your algorithm really simple if you define the encoding such that the first part of the encoding is an encoded list of states that are part of the TM.*

> (1.2) Is it undecidable whether an arbitrary TM halts after 10 steps?

I assume what you mean by this is the following: is it undecidable whether an arbitrary TM halts after exactly 10 steps for some input? The answer is that, no, this is also decidable. Consider all $\Sigma^{10}$ configurations of the first $10$ cells of the tape. For each of these, configurations, execute 10 steps according to the TM's transition table (for nondeterministic TMs, this includes all possible paths of length 10). If one of the paths halts after exactly 10 steps, output yes; otherwise, output no.

> (1.3) Is it undecidable whether an arbitrary TM ever prints a specific letter?

This one is actually undecidable. Suppose it weren't undecidable. Take an arbitrary TM. Construct a new TM with a new alphabet symbol not in the alphabet of the original TM. Replace all transitions in the original TM which cause the machine to halt with transitions which cause the machine to halt and which write this new symbol to the tape. By the assumption, the problem of whether the new TM prints this specific symbol is decidable; however, solving this problem would give us a way to solve the halting problem for the original TM (since the new one printing the symbol would only occur if the original one halted). Since the halting problem is undecidable, we have a contradiction, hence, this problem is undecidable.

> (1.4) Is it undecidable whether an arbitrary TM accepts a string w in 5 steps?

This is clearly decidable. Given a TM and a string, write the string on the tape and execute five steps of the TM according to its transition table.

> Which one of the following is not decidable?
>
> 1. given a TM M, a string s and an integer k, M accepts s with k steps
> 2. equivalence of two given TMs
> 3. language accepted by a given DFSA(Deterministic finite state automata) is nonempty
> 4. language accepted by a CFG(Context free grammar) is nonempty

* (2.1.) is definitely decidable as per the argument in (1.4).
* (2.2.) is ambiguous; if we mean syntactically equivalent, then this should be decidable given a suitable encoding. If it means semantically equivalent, i.e., they decide/accept the same language, then this is definitely undecidable.
* (2.3.) is definitely decidable, since you can always minimize the DFA and see whether it's a single state with no accepting states.
* (2.4.) is definitely decidable. Begin marking symbols (terminal/nonterminal) if they lead to a string of only terminal symbols. First, mark all terminal symbols. Next, mark nonterminals which lead to a string of only nonterminals. Iteratively, mark unmarked nonterminals which lead to strings of terminals or already-marked nonterminals. Continue until you complete an iteration without marking any new nonterminals. If the start symbol is marked, then it leads to a string of terminals, which is a string generated by the grammar, so its language is non-empty. Otherwise, the start symbol doesn't lead to a string of all terminals, so its language is empty.

By process of elimination, the answer to question (2) must be (2.2) and the interpretation given to "equivalent" must be "decides/accepts the same language."

---
Tags: formal-languages, turing-machines, undecidability
---


title: Automaton equivalent of the π calculus?

text:
# Question
Title: Automaton equivalent of the π calculus?
If Turing Machines are the automata equivalent of the $\lambda$ calculus, what is the automaton equivalent of the $\pi$ calculus? I suppose it would be some class of automata that resembled a Turing Machine, but with support for communication channels or signals of some type, but I'm not sure, and would appreciate some direction.

# Answer
The question doesnt make too much sense because the $\pi$-calculus was proven Turing complete, or in other words equivalent to a Turing machine ever since its inception by Milner in 1992. There is a reference on Wikipedia.
> -1 votes

# Answer
Turing Machines are to the λ-calculus as Chemical Abstract Machines are to the π-calculus.

Basically, a Chemical Abstract Machine is modeled as a set of molecules that, on each process step, some subset of the molecules react, are consumed by the reaction, and produce new molecules.
> -1 votes

---
Tags: automata, concurrency, machine-models, pi-calculus
---


# Question
Title: For what kinds of languages is min |NFA| = Ω(min |DFA|)?
Consider a regular language $L$. Let $D(L)$ be a minimal DFA for $L$ and $N(L)$ be a minimal NFA for $L$ (minimal in the sense of the smallest possible number of states for an automaton that recognizes the given language). Write $|A|$ for the size (number of states) of the automaton $A$. In general, $|N(L)|$ can be a lot smaller than $|D(L)|$ (down to $\lg |D(L)|$, since determinization is exponential in the worst case).

I am interested in languages for which the minimal NFA is guaranteed to be at least a fraction of the size of the DFA: $|N(L)| \ge k |D(L)|$. What families of regular languages have this property? In other words, for what family of languages $(L\_n)$ such that $|D(L\_n)| = n$ is $|N(L\_n)| = \Omega(n)$?

# Answer
Perhaps this is too trivial to bear mentioning, but I'll mention it anyway: one class of languages comes to mind (although there may be much more interesting classes of languages than this which satisfy the property).

Consider a family of languages $\\{\\{\epsilon\\}, \\{w\\}, \\{ww\\}, ..., \\{w^n\\}, ...\\}$ where $w \in \Sigma^\*$. A minimal NFA for the $n$th language will have $n|w|+1$ states (assuming no dead state), whereas a minimal DFA will have $n|w|+2$ states (assuming a single dead state). We have that $n|w|+1 = \Omega(n|w|+2)$.

We get another family by allowing each language to accept up to $n|w|$; this is the family $\\{\\{\epsilon, w, ww, ..., w^n\\} \mid n \geq 0\\}$. The automata for these languages are practically identical to the corresponding automata from the other family, except these have more accepting states.

These happen to be families of finite languages. We could, of course, get a family of infinite languages as follows: $\\{\\{w^nw^\*\\} \mid n \geq 0\\}$.

Consider any family of languages which consist of a single word. For any such language, the ratio of $|\min DFA|$ to $|\min NFA|$ will be less than $2$, so such a family of languages must satisfy the property. Since there are countably many finite strings over any alphabet, and since we're considering any possible subset thereof, we get an uncountable number of language families in this manner.

FWIW, to get these examples, my thinking was that we're looking for languages that involve doing something which an NFA can't do much better than a DFA. Accepting some random string, and nothing else, is notable in this regard. I guess more generally, there's an informal notion of "straightforwardness of the DFA" that seems to be related to what's being asked.

You know, come to think of it, I think we can generalize this a bit more: any family of languages with the following form should work: $L\_n = \\{s\_0s\_1...s\_i\\}L$ for $n \geq 0$, where $L$ is any regular language and $s\_n$ is any finite string. Suppose for $L$ that $|\min DFA| = x$ and $|\min NFA| = y$. Then the family $L\_n$ should always have $|\min DFA| / |\min NFA| \leq x/y$.

I don't know whether this is pertinent, interesting or useful, but I thought if nothing else this might revive the question.
> 2 votes

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


title: A containment result in complexity

text:
# Question
Title: A containment result in complexity
A question on the interesting result in http://arxiv.org/pdf/1110.6126v1.pdf

It is shown $\Pi\_2^P \not\subset P^{NP}$. But http://en.wikipedia.org/wiki/Polynomial\_hierarchy says $\Pi\_2^P = CoNP^{NP}$.

Does this mean an oracle in NP under which $P$ is not $CoNP$ has been shown?

Could someone elaborate?

# Answer
> 4 votes
Aaronson's result shows that $\Pi\_2 \not\subset P^{N\\!P}$ relative to a random oracle with probability 1. As he mentions, it had already been known that $N\\! P != \mathrm{co}N\\! P$ (and so $P \neq N\\!P$ and $P \neq \mathrm{co}N\\!P$) relative to a random oracle with probability 1: see the paper by Bennett and Gill. An oracle with respect to which $P \neq N\\!P$ (and so $P \neq \mathrm{co}N\\!P$) had been constructed earlier by Baker, Gill and Solovay. The construction is standard, and you can find many references online.

---
Tags: complexity-theory
---


title: A simple question on #P

text:
# Question
Title: A simple question on #P
Wiki (http://en.wikipedia.org/wiki/Sharp-P) says 'In computational complexity theory, the complexity class #P (pronounced "number P" or, sometimes "sharp P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP'.

Is there a counting version for CoNP problems?

# Answer
> 4 votes
Expanding on Timot's comment, $\\# P$ consists of all functions which can be expressed as the number of accepting computations of some non-deterministic Turing machine running in polynomial time. It is also the class of all functions which can be expressed at the number of non-accepting computations of some non-deterministic Turing machine running in polynomial time (exercise).

If $f \in \\# P$ then $\\{ x : f(x) \geq 1 \\} \in N\\! P$ and $\\{x : f(x) = 0 \\} \in \mathrm{co}N\\! P$; and vice versa, if $L \in N\\!P$ ($L \in \mathrm{co}N\\!P$) then it can be expressed in the form $\\{ x : f(x) \geq 1 \\}$ ($\\{ x : f(x) = 0 \\}$) for some $f \in \\# P$.

---
Tags: complexity-theory
---


# Question
Title: Recurrence relation for time complexity $T(n) = T(n-1) + n^2$
I'm looking for a $\Theta$ approximation of $$T(n) = T(n-1) + cn^{2}$$

This is what I have so far:

$$ \begin{align\*} T(n-1)& = T(n-2) + c(n-1)^2\\ T(n) &= T(n-2) + c(n-1) + cn^2\\\\[1ex\] T(n-2) &= T(n-3) + c(n-2)^2\\ T(n) & = T(n-3) + c(n-2)^2 + c(n-1)^2 + cn^2 \\\\[1ex\] T(n-3) &= T(n-4) + c(n-3)^2 \\ T(n) &= T(n-4) + c(n-3)^2 + c(n-2)^2 + c(n-1)^2 + cn^2 \end{align\*} $$

So, at this point I was going to generalize and substitute $k$ into the equation.

$$T(n)= T(n-k) + (n-(k-1))^2 + c(k-1)^2$$

Now, I start to bring the base case of 1 into the picture. On a couple of previous, more simple problems, I was able to set my generalized k equation equal to 1 and then solve for $k$. Then put $k$ back into the equation to get my ultimate answer.

But I am totally stuck on the $(n-k+1)^2$ part. I mean, should I actually foil all this out? I did it and got $k^2-2kn-2k+n^2 +2n +1 = 1$. At this point I'm thinking I totally must have done something wrong since I've never see this in previous problems.

Could anyone offer me some help with how to solve this one? I would greatly appreciate it. I also tried another approach where I tried to set $n-k = 0$ from the last part of the equation and got that $k = n$. I plugged n back into the equation towards the end and ultimately got $n^2$ as an answer. I have no clue if this is right or not.

I am in an algorithms analysis class and we started doing recurrence relations and I'm not 100% sure if I am doing this problem correct. I get to a point where I am just stuck and don't know what to do. Maybe I'm doing this wrong, who knows. The question doesn't care about upper or lower bounds, it just wants a theta.

# Answer
> 10 votes
Just continue your reasoning as follows.

\begin{eqnarray} T(n) &=& T(n-1) + cn^2 \\ &=& T(n-2) + c(n-1)^2 + cn^2 \\ &=& \ldots \\ &=& T(n-n) + c(1^2) + c(2^2) + \ldots cn^2 \\ &=& T(0) +c\sum\_{1\leq i\leq n} i^2. \end{eqnarray}

Do you know how to simplify this using the addition formula for the first $n$ squares?

# Answer
> 2 votes
sometimes formulas are hard to remember, integration could be handy -- $$\sum\_{i=1}^n i^2 \approx \int\_1^n i^2 di = \frac{1}{3}i^3 \bigg\]\_1^n = \frac{1}{3}(n^3 - 1) \leq cn^3 = O(n^3)$$

# Answer
> 2 votes
More generally, any recurrence relation of the form $T(n) = T(n-1) + f(n)$ has the solution $T(n) = \sum\_{i=0}^n f(i)$.

---
Tags: time-complexity, algorithm-analysis, proof-techniques, recurrence-relation
---


# Question
Title: Solving a complicated recurrence relation
How to solve the recurrence relation below?

$$T(n) = \begin{cases} 2T(\sqrt{n}) + \log n/\log\log n & \text{if } n \> 4\\ 1 & \text{if } n \leq 4. \end{cases}$$

Preferably by the master theorem; otherwise by any method. I know the Master Theorem fails, but is there any extension for these type of problems?

# Answer
Following Timot's suggestion, let $S(m) = T(2^m)$, so that $S$ satisfies the recurrence $$ S(m) = \begin{cases} 2S(m/2) + \tfrac{m}{\log m} & \text{ if } m \> 2 \\ 1 & \text{ otherwise.} \end{cases} $$ In fact, we'll analyze the recurrence with a base case of $m = 1$ instead, and assume the logarithm is base $2$. We have $$ \begin{align\*} S(2^k) &= \frac{2^k}{k} + 2 \frac{2^{k-1}}{k-1} + 4 \frac{2^{k-2}}{k-2} + \cdots + 2^{k-1} \frac{2^1}{1} + 2^k \\ &= 2^k \left\[ \frac{1}{k} + \frac{1}{k-1} + \cdots + \frac{1}{1} + 1 \right\] = \Theta(2^k\log k). \end{align\*} $$ Therefore $S(m) = \Theta(m\log\log m)$ and $T(n) = \Theta(\log n\log\log\log n)$.
> 1 votes

---
Tags: recurrence-relation
---


title: Convert $\sum x_i = y$ to 3-sat

text:
# Question
Title: Convert $\sum x_i = y$ to 3-sat
I have a simple looking question. What is the most efficient conversion of $\sum\_{i=1}^n x\_i = y$ to 3-sat? Here $x\_i$ is either $1$ or $0$ and $y$ is some positive integer.

Can you do better than making a SATISFIABILITY instance with $\binom{n}{y}$ clauses, each of which is the conjunction of $y$ positive literals and $n-y$ negative literals and then just feeding the whole thing into the Tseitin transform?

# Answer
Many better techniques for enforcing cardinality constraints are described in this answer. For the special case $y=1$, see also Encoding 1-out-of-n constraint for SAT solvers. Read those links; they suggest more efficient conversions, though I'm not aware of any reason to expect that they are necessarily optimal, so they don't answer your question about the most efficient conversion.
> 8 votes

# Answer
Hint: Use a circuit for computing $\sum\_{i=1}^n x\_i$. Don't forget you're allowed to add variables!
> 4 votes

---
Tags: satisfiability, sat-solvers
---


title: create divide and conquer algorithm

text:
# Question
Title: create divide and conquer algorithm
I have to create an algorithm for homework, but cant figure out where to start.

The divide and conquer algorithm muse be O(nlgn) and returns a pair of numbers *p* and *q* in an array *A*. *p* must appear before *q* in the array, and *q-p* must be the highest possible value

heres and example I made up:

A=\[1,4,12,5,9,1,3,8\]

the return values would be *p=1* & *q=12*

# Answer
Hint: Divide $A$ evenly into two smaller arrays $A\_1,A\_2$, and solve the problem (recursively) on $A\_1$ and $A\_2$. Can that help you find the optimum on $A$? Don't forget you're allowed to use extra processing costing up to $O(n)$.

Another hint: Suppose that $p,q$ is the optimal pair for $A$. Either $p,q \in A\_1$, or $p,q \in A\_2$, or neither of these cases is true. What can you say in the third case about $p$ and $q$?

---

As an aside, this can be solved in $O(n)$, in fact even online. We maintain the minimal element seen so far $m$, and the maximum difference $D = q-p$ over elements seen so far. Upon getting a new element $x$, we put $D = \max(D,x-m)$ and $m = \min(x,m)$, and update $p,q$ with $m,x$ if needed.
> 5 votes

---
Tags: algorithms, divide-and-conquer
---