title: Not able to convert from NFA to DFA

text:
# Question
Title: Not able to convert from NFA to DFA
I have a simple problem of making a DFA which accepts all inputs starting with double letters (aa, bb) or ending with double letters (aa, bb), given $\Sigma =\\{a, b\\}$ is the alphabet set of the given language.

I tried to solve it in a roundabout way by:

1. Generating a regular expression
2. Making its corresponding NFA
3. Using powerset construction to deduce a DFA
4. Minimizing the number of states in DFA

**Step 1:** *Regular expression* for given problem is (among countless others):

```
((aa|bb)(a|b)*)|((a|b)(a|b)*(aa|bb))

```

**Step 2:** *NFA* for given expression is:

(source: livefilestore.com)

In Tabular form, NFA is:

```
State    Input:a     Input:b
->1        2,5         3,5
  2        4           -
  3        -           4
 (4)       4           4
  5        5,7         5,6
  6        -           8
  7        8           -
 (8)       -           -

```

**Step 3:** Convert into a DFA using powerset construction:

```
Symbol, State       +   Symbol, State (Input:a) +   Symbol, State (Input:b)
   ->A, {1}         |        B, {2,5}           |        C, {3,5}
     B, {2,5}       |        D, {4,5,7}         |        E, {5,6}
     C, {3,5}       |        F, {5,7}           |        G, {4,5,6}
   (D), {4,5,7}     |        H, {4,5,7,8}       |        G, {4,5,6}
     E, {5,6}       |        F, {5,7}           |        I, {5,6,8}
     F, {5,7}       |        J, {5,7,8}         |        E, {5,6}
   (G), {4,5,6}     |        D, {4,5,7}         |        K, {4,5,6,8}
   (H), {4,5,7,8}   |        H, {4,5,7,8}       |        G, {4,5,6}
   (I), {5,6,8}     |        F, {5,7}           |        I, {5,6,8}
   (J), {5,7,8}     |        J, {5,7,8}         |        E, {5,6}
   (K), {4,5,6,8}   +        D, {4,5,7}         +        K, {4,5,6,8}

```

**Step 4:** Minimize the DFA:

I have changed K-\>G, J-\>F, I-\>E first. In the next iteration, H-\>D and E-\>F. Thus, the final table is:

```
  State    +   Input:a     +   Input:b
   ->A     |      B        |      C
     B     |      D        |      E
     C     |      E        |      D
    (D)    |      D        |      D
    (E)    |      E        |      E

```

And diagramatically it looks like:

(source: livefilestore.com)

...which is not the required DFA! I have triple checked my result. So, where did I go wrong?

Note:

* -\> = initial state
* () = final state

# Answer
You are fine up to step 3 (the DFA) but your minimization is incorrect.

It's clear that the minimized DFA is not right, because both the inputs `ba` and `ab` (which are not in the original language, nor are they accepted by the DFA in step 3) lead to final state `E`.

Looking at your minimization steps, it seems that you have unified final and non-final states; for example J (final) -\> F (not final) and I (final) -\> E (not final). Merging a final state with a non-final state changes the language accepted by the automaton, leading to the acceptance of incorrect strings as noted above.
> 5 votes

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


# Question
Title: "Definition of NP via relations and quantifiers; not via NTMs"
I have the following question on an assignment, and despite asking my prof, I can't get a grasp on it..

> Let $L\_1, L\_2$ be languages in ${\sf NP}$. Using the definition of ${\sf NP}$ via relations and quantifiers (not the non-deterministic Turing machines) prove that the following language is in ${\sf NP}$: $L=\\{ x | x \in L\_1 \text{ or } xx \in L\_2 \\}$, where $xx$ is two concatenated copies of $x$.

Her notes say the following on this:

> Let $L\subseteq\Sigma^{\*}$. We say $L\in{\sf NP}$ if there is a two-place predicate $R\subseteq\Sigma^{\*}\times\Sigma^{\*}$ such that $R$ is computable in polynomial time, and such that for some $c,d\in\mathbb{N}$ we have $\forall x\in\Sigma^{\*},x\in L\iff\exists y\in\Sigma^{\*},|y|\leq c|x|^d$ and $R(x,y)$.

I would imagine that this is a well known definition (though possibly worded differently)... but I don't know where else I can get details on it. My textbook has a somewhat similar definition, but it doesn't talk about this $c,d\in\mathbb{N}$ stuff..

> A ***verifier*** for a language $A$ is an algorithm $V$, where $$A=\\{w\mid V\text{ accepts }\langle w,c\rangle\text{ for some string c}\\}.$$ We measure the time of a verifier only in terms of the length of $w$, so a ***polynomial time verifier*** runs in polynomial time in the length of $w$. A language $A$ is ***polynomially verifiable*** if it has a polynomial time verifier.

The $y$ in the first definition is supposed to be analogous to $c$ in the second; it is a **certificate** or **witness** used by the verifier. But that's all I can understand between the two.

Now... what I ***think*** I know about this question is that $R(x,y)$ is supposed to be a verifier for $L$, while $R\_1(x,y\_1)$ is a verifier for $L\_1$ and $R\_2(x,y\_2)$ is a verifier for $L\_2$. She said something about $y=\langle y\_1, y\_2\rangle$ being an encoding of the two certificates for the verifiers $R\_1$ and $R\_2$. But from there I'm lost. I have no idea how to answer this question even after asking for help two or three times.

Anybody here able to help? Thanks in advance.

# Answer
> 4 votes
I think I just realized, after finding a similar problem online, that this is asking to simply show that ${\sf NP}$ is closed under union. Can anybody give any insight into whether or not this is a proper solution, or if I'm missing anything? I mostly understand my answer, but I don't really know what I'm doing with the $c$ and $d$ constants... I put them in there because I feel like I'm going to need to.

> This question is asking to prove that ${\sf NP}$ is closed under union. It is the same as asking if $L=L\_{1}\cup L\_{2}$ is in ${\sf NP}$.
>
> Since $L\_{1}$ and $L\_{2}$ are both in ${\sf NP}$, it follows that they both have polynomial time verifiers $R\_i(x\_i,y\_i)$ that evaluate to true when $y\_{i}$ is a valid certificate/witness for $x\_i\in L\_i$, where $i\in \\{1,2\\}$.
>
> To show that $L=L\_1\cup L\_2$ is also in ${\sf NP}$, we need to construct a polynomial-time verifier $R(x,y)$. The certificate $y=\langle y\_1,y\_2 \rangle$ for $L$ will be an encoding of the two certificates $y\_1$ and $y\_2$ in such a way that $R(x,y)$ evaluates to true when $\displaystyle\bigvee\_{1\leq i\leq 2} R\_i(x,y\_i)$ evaluates to true.
>
> Given that $R\_{i}(x\_i,y\_i)$ for $i\in\\{1,2\\}$ are polynomial time verifiers with running time $O(c\_i|x\_i|^{d\_i})$ for some $c,d\in\mathbb{N}$, $R(x,y)$ will have a running time of at most $O(2\cdot max(c\_i)|x|^{max(d\_i)})$, which is still polynomial. Therefore, $L\in {\sf NP}$.

---
Tags: complexity-theory, closure-properties
---


# Question
Title: Is the open question NP=co-NP the same as P=NP?
I'm wondering this based on several places online that call $\sf NP=$ co-$\sf NP$ a major open problem... but I can't find any indication as to whether or not this is the same as $\sf P=NP$ problem...

# Answer
No. It is another open problem and certainly related, but different. The complexity class co-$\mathsf{NP}$ is the set of languages whose complements are in $\mathsf{NP}$; that is, the set of decision problems for which a "no" answer has a deterministic polynomial-time verifier. So for example, the question "Is this SAT formula unsatisfiable?" If the answer is "no", then there is some satisfying assignment of the variables that proves this; that's the certificate for the verifier.

It is possible that $\mathsf{P} \neq \mathsf{NP}$, yet $\mathsf{NP} = $co-$\mathsf{NP}$.

But on the other hand, if $\mathsf{P} = \mathsf{NP}$, then $\mathsf{NP} = $co-$\mathsf{NP}$ for sure. This is because if a language is in $\mathsf{P}$, then its complement is also in $\mathsf{P}$, so if $\mathsf{P} = \mathsf{NP}$, then that goes for every language in $\mathsf{NP}$ as well.
> 28 votes

# Answer
One good way to answer this question is to use the polynomial hierarchy (PH) (see also here). The polynomial hierarchy is a hierarchy of complexity classes that generalizes the classes ${\sf P}$, ${\sf NP}$ and ${\sf co-NP}$ to oracle machines and use as a **scale** to measure complexity of problems.

It is known that If ${\sf NP}={\sf co-NP}$ or ${\sf P}={\sf NP}$ then the polynomial hierarchy collapses to its **first** level.
> 4 votes

---
Tags: complexity-theory, complexity-classes, p-vs-np
---


title: A variant of the busy beaver function

text:
# Question
Title: A variant of the busy beaver function
Reading this question "Natural RE undecidable problems but not Turing-complete" the following language came to my mind:

If $\Sigma(\cdot)$ is the busy beaver function (maximum attainable score among all halting 2-symbol n-state Turing machines of the above-described type, when started on a blank tape), define the function:

$$BB(\langle M \rangle) = \begin{cases} 1 & \text{$\langle M \rangle$ computes $\Sigma(\cdot)$}\\ 0 & \text{ otherwise} \end{cases}$$

Now define the language:

$L = \\{ \langle M \rangle \\; | \\; \langle M \rangle \mbox{ halts and } BB(\langle M \rangle) = 0 \\}$

> Is $L$ recursively enumerable? (it should be r.e.: just simulate in parallel M with all TMs of the same length, and if $M$ halts and another $M'$ halts with a higher score add M to the enumeration).
>
> Can we reduce the halting problem to $L$ ? (it seems that it cannot "capture" the halting of the busy beavers)

# Answer
I can't believe I didn't see this before — but yes, with an oracle for $L$ you can solve the halting problem. Obviously an oracle for $L$ gives us 'recursively' all non-Busy Beaver halting machines, so the question is 'can we figure out recursively in $L$ what the busy beavers are?'. Define $\Sigma\_2(n)$ as the count function of the 'second busiest beaver'; that is, the second-highest attainable score among all halting two-symbol $n$-state TMs. The trick here is that there's a recursive function $f()$ such that $\Sigma(n)\leq\Sigma\_2(f(n))$ (it's almost certain that $f(n)=n+1$ will do the trick, in fact, but that requires knowing that the BB function is strictly increasing) : given a machine $M$ of size $n$ that prints $\Sigma(M)$ 1s on its tape and then halts, there's some $c\gt 1$ and two machines each of size $\leq cn$ that print exactly $\Sigma(M)$ 1s and exactly $\Sigma(M)+1$ 1s, respectively, on their tapes — and this holds true for a 'busy beaver' machine $M$ *even though we don't know $M$ explicitly*. This means that having a bound on the 'second busy beaver' function for $f(n)$ gives a bound for the busy beaver function on $n$; but then having this, it's easy to solve the halting problem for a TM $M$ of size $n$ - if $\langle M\rangle\in L$ then say that $M$ halts; otherwise, find the longest-running machine of size $f(n)$ in $L$ (which can be done recursively since there are only finitely many machines of size $\leq f(n)$) and simulate $M$ for as many steps as that machine takes to halt. If $M$ doesn't halt within that time then $M$ can't possibly halt.
> 3 votes

# Answer
This is a reworked version of Steven's good answer, with an explicit reduction from the Halting problem.

Given $\langle M \rangle, w$ build $M'$ that runs $M$ on $w$ and if it halts goes to the right of the tape, writes a 0 and halt.

If $M'$ halts, $BB(M')=0$ because there is an equivalent TM of the same size that writes a 1 and halts; so we can use the decider for $L$ to check if $M$ halts on $w$ ($M$ halts on $w$ iff $M' \in L$)

... it turned out that the question is indeed trivial :-)
> 3 votes

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


# Question
Title: anonymous lambda functions (functional programming)
What are anonymous (lambda) functions? What is the formal definition of an anonymous function in a functional programming language?

In my simple terms, when I am programming in scheme/lisp I would say an anonymous (lambda) function is a function that is not bound to an identifier.

Is that all that you can say formally about a lambda function? I think there is more detail that can be added to this simple definition. Please elaborate, and thank you!

# Answer
> 10 votes
In my opinion, that's all you can really say about them.

The idea is that in a higher-order language, a function is just another kind of value. The same way you can have (3+4) without an identifier in C, you can have (lambda (x) +(3 x))) without an identifier in scheme.

The key here isn't that there's anything special about anonymous functions. It's only the restrictions of other languages that require functions be treated differently from any other value. The special definitions are for procedural languages which don't allow them, not for functional languages with do.

# Answer
> 11 votes
In the lambda calculus, *all* functions (terms) are anonymous. This is an essential property of the lambda calculus: you can compose complex functions from simpler ones without giving them names.

In programming languages, it is in most cases desirable to give names to functions, because this is the way we think and it makes code readable for humans. But compilation eventually removes the names when producing an executable (if we disregard debugging information).

If a language allows expressing anonymous functions (that is functions without names), it can give an advantage to both programmers and compilers: Programmers can often write shorter code, and compilers can better optimize, knowing that an anonymous function is used just at the given place and not anywhere else.

# Answer
> 1 votes
It depends on which part of your question you put the emphasis. If it is specifically the property of being anonymous for anonymous functions, then indeed the only answer is that they are unbound *values*. If you are talking about functions in general, anonymous functions are probably the most visible manifestation of the use of lambda calculus in a functional setting, for applicative languages.

In fact, from the lambda calculus point of view, lambda expressions are the very syntactic construct used to create bindings. Recall the notation used in lambda calculus:

$\lambda f.\lambda x. f x$

where $f$ and $x$ are bound within the inner expression $f x$. Each lambda expression there defines the binding, and thus acts as a local context for name bindings.

A language usually offers ways, such as `let` (ML like languages, scheme), or `define` (scheme) to create bindings usable at the top level (or within syntactic constructs more complex than functions, like modules or objects), but the only needed tool for bindings is the lambda at lower levels.

If you look at languages like scheme or lisp dialects, their very fundation is lambda calculus, and many special forms are really sugar coated lambdas.

For concatenative languages, the story is slightly different. Lambdas are not necessary, and actually counter-productive. What's the point of defining anonymous lambdas, when everything is a *function*?

There is somehow a duality between these two kind of manguages. The later is focused on point free function combination and thus tries to represent everything as functions, while the former works on a more elaborated calculus, and makes an effort to have functions as first class values, like any other values of the language. In this respect, one could see lambdas as the result of that effort.

Some pointers on the topic introduced (poorly) in this answer:

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


# Question
Title: Prove that $\{0^n 1^{n\cdot m} : n,m \in \mathbb{N}\}$ is not context-free
This is a homework problem I have spent several hours on. A "hint" is given that we may use this fact: If $n,j,k \in \mathbb{N}$ satisfy $ n \geq 2$ and $1 \leq j+k \leq n$, then $n^2+j$ does not evenly divide $n^3+k$.

I cannot find any way to apply this fact. It leads me to believe I should use the string $0^{p^2}1^{p^3}$ or something like that, but I am really just not sure. The pumping lemma has given me trouble since the non regular language version.

Even small hints greatly appreciated at this point.

# Answer
> 5 votes
If you use the pumping lemma on the word $w=0^{p^2} 1^{p^3}$, consider the partition $w=xyzuv$, where $|yzu|\le n$ and $|yu|\>0$ ($n$ being the length of $w$). It is easy to prove that from all the cases (that is, from all the possibilities for $y$ and $u$), the only non-trivial case is when $y=0^i$ and $u=1^j$, in which case the hint you mentioned finishes the job.

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


# Question
Title: Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j}
Can someone help with this:

$L=\\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\\}$

I'm trying to write a grammar for this language? I don't know how to do this. I tried this:
$S \rightarrow aaAb \mid aA \\ A \rightarrow aA \mid a$

# Answer
> 9 votes
Consider the two languages:
$L\_1 = \\{a^ib^j \mid i, j \ge 0 \text{ and } i \> 2j\\}$
$L\_2 = \\{a^ib^j \mid i, j \ge 0 \text{ and } i \< 2j\\}$

Convince yourself that $L = L\_1 \cup L\_2$.

In $L\_1$, the number of $a$'s are *more* than double of $b$'s, so there has to be atleast one $a$ (when there are no $b$'s). Also, for every addition of $b$, atleast 2 $a$'s must be added. You can generate $L\_1$ as:

$ S\_1 \rightarrow aA \\ A \rightarrow aaAb \mid aA \mid \varepsilon $

$L\_2$ is a little more tricky. The number of $a$'s are less than double the number of $b$'s, so there can be $0$ $a$'s, but non-zero $b$'s. Consider the "base case" of $1$ $b$. The string can be either $b$ or $ab$. We will let the first rule generate this base case. After that, notice that for every addition of $b$, we can increase the number of $a$'s by *at most* $2$. So we can add $0$, $1$, or $2$ $a$'s for every addition of $b$. We'll let the second rule handle this. So, the CFG for $L\_2$ becomes:

$ S\_2 \rightarrow Bb \mid aBb \\ B \rightarrow Bb \mid aBb \mid aaBb \mid \varepsilon $

Note that CFG's are closed under union, that is, the union of two CFG's is also a CFG. So, to get the CFG for $L$, let the starting state $S$ of $L$ lead to either the starting state of $L\_1$, or of $L\_2$:

$S \rightarrow S\_1 \mid S\_2$

The rest of the rules remain the same as in the two languages. There may be a simpler grammar, but this was the first that came to mind.

# Answer
> 2 votes
Start with a grammar for $\\{a^i b^{2 i} : i \ge 0\\}$: $$ S \rightarrow a S bb \mid \epsilon $$ Now hack it so that there are more $a$ than $bb$: $$ \begin{align\*} S &\rightarrow a S bb \mid A \\ A &\rightarrow a A \mid a \end{align\*} $$ The modificaton to force more $b$ is similar, and left to you. It adds a nonterminal and three productions.

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


# Question
Title: How do I explain that a polynomial time reduction is in fact polynomial time?
I have as an assignment question to show that $QuadSat=\\{\langle\phi\rangle\mid\phi$ is a satisfiable 3CNF formula with at least 4 satisfying assignments$\\}$ is $\sf NP$-Complete.

My solution is as follows, which is pretty much copied almost 100% from a textbook example with only an extra requirement for satisfiablity at the end...

> $$QuadSat\leq\_{p} Clique$$ Let $\phi$ be a formula with k clauses such as $$\phi=\bigwedge\_{1}^{k}(a\_k\vee b\_k\vee c\_k)$$ The reduction $f$ generates the strong $\langle G,k\rangle$, where $G$ is an undirected graph defined as follows:
>
> The nodes in $G$ are organized into $k$ groups of three nodes each called the \textbf{triples}, $t\_1, \dots, t\_k$. Each triple corresponds to one of the clauses in $\phi$, and each node in a triple corresponds to a literal in the associated clause. Label each node of $G$ with its corresponding literal in $\phi$.
>
> The edges of $G$ connect all but two types of pairs of nodes in $G$: No edge is present between nodes in the same triple, and no edge is present between two nodes with contradictory labels. $QuadSat$ is satisfiable if and only if the resulting graph $G$ contains four or more $k$-$cliques$. Each unique $k$-$clique$ in $G$ represents a set of satisfying assignments to $QuadSat$.
>
> The reduction runs in polynomial time, because the construction of the graph is a polynomial function; one pass through all the triples to create all the vertices for $V$, and one pass through the same triples to create the edges.

I feel like my explanation as to why my reduction is polynomial in time is severely weak, possibly bordering on wrong. How can I explain this better?

And something else: I think this only proves that QuadSat is in NP, but not necessarily NP Complete. How can I prove this?

# Answer
Your reduction indeed shows that $QuadSAT\in NP$, since you showed a reduction **to** a problem in NP. Perhaps an easier way to have done this, is to simply show that there is a "short witness" for the membership of a formula in $QuadSAT$. In order to show NP-hardness, you must show a reduction **from** an NP-hard problem. A good candidate for that is $SAT$ (or $3SAT$).
> 5 votes

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


# Question
Title: What is the relation between functors in SML and Category theory?
Along the same thinking as this statement by Andrej Bauer in this answer

> The Haskell community has developed a number of techniques inspired by category theory, of which monads are best known but should not be confused with monads.

What is the relation between functors in SML and functors in Category theory?

Since I don't know about the details of functors in other languages such as Haskell or OCaml, if there is info of value then please also add sections for other languages.

# Answer
> 16 votes
Categories form a (large) category whose objects are the (small) categories and whose morphisms are functors between small categories. In this sense functors in category theory are "higher size morphisms".

ML functors are not functors in the categorical sense of the word. But they are "higher size functions" in a type-theoretic sense.

Think of concrete datatypes in a typical programming language as "small". Thus `int`, `bool`, `int -> int`, etc are small, classes in java are small, as well structs in C. We may collect all the datatypes into a large collection called `Type`. A type constructor, such as `list` or `array` is a function from `Type` to `Type`. So it is a "large" function. An ML functor is just a slightly more complicated large function: it accepts as an argument several small things and it returns several small things. "Several small things put together" is known as *structure* in ML. In terms of Martin-Löf type theory we have a *universe* `Type` of small types. The large types are usually called *kinds*. So we have:

1. values are elements of types (example: `42 : int`)
2. types are elements of `Type` (example: `int : Type`)
3. ML signatures are kinds (example: `OrderedType`)
4. type constructors are elements of kinds (example: `list : Type -> Type`)
5. ML stuctures are elements of kinds (example: `String : OrderedType`)
6. ML functors are functions between kinds (example: `Map.Make : Map.OrderedType -> Make.S`)

Now we can draw an analogy between ML and categories, under which functors correspond to functors. But we also notice that datatypes in ML are like "small categories without morphisms", in other words they are like sets more than they are like categories. We could use an analogy between ML and set theory then:

1. datatypes are like sets
2. kinds are like set-theoretic classes
3. functors are like class-sized functions

# Answer
> 15 votes
A Standard ML structure is akin to an *algebra*. Its signature describes an entire *class of algebras* of similar shape.

A Standard ML functor is a map from a class of algebras to another class of algebras. An analogy is, for instance, with the functors $F : {\bf Mon} \to {\bf Grp}$, which adds an inverse operation to monoids, or $F : {\bf Ab} \to {\bf Rng}$ which adds a multiplicative monoid to abelian groups to make rings.

Most of these ideas were worked out in series of papers by Burstall and Goguen in designing a specification language called CLEAR (References c5 and c6 on the DBLP page.) David MacQueen was working jointly with Burstall and Sannella at that time, and was intimately familiar with the issues. The Standard ML module system is based on these ideas.

What most people would wonder is, what about morphisms? Category theoretic functors have an object part and a morphism part. Do Standard ML functors have the same? The answer is YES and NO.

* The YES part of the answer applies if the structures are first-order. Then, there are homomorphisms between different structures of the same signature, and Standard ML functors automatically map them to homomorphisms of the result signature.
* The NO part of the answer applies when the structures have higher-order operations.

Does this mean that Standard ML is deviating from category theory? I don't think so. I rather think that Standard ML is doing the right thing, and category theory is yet to catch up. Category theory doesn't yet know how to deal with higher-order functions. Some day, it will.

# Answer
> 3 votes
There is, to the best of my knowledge, no formal relation between *functors* in category theory and *functors* in ML (SML or OCaml, they're close enough for our purpose here).

In category theory, functors are functions that operate on objects. They are one level above morphisms, which are often functions that operate on elements (many categories have objects that are sets with some algebraic structure and arrows that are homomorphisms between these structures). An ML functor is a function that operates on modules, one level above the functions that operate on core language values. I think the resemblance stops here.

ML functors were baptized by Dave McQueen in his 1985 revision of *Modules for Standard ML* (citeseerx) that appeared in the *Polymorphism Newsletter* (the original paper used the expression “parametric module” — later publications tend to use the adjective “parametrized”). Unfortunately, I can't locate a copy of that paper. In his 1986 paper *Using Dependent Types to Express Modular Structure* (citeseerx) he gives the name as established.

---
Tags: programming-languages, functional-programming, category-theory
---


# Question
Title: Are there subexponential-time algorithms for NP-complete problems?
Are there NP-complete problems which have proven subexponential-time algorithms?

I am asking for the general case inputs, I am not talking about tractable special cases here.

By sub-exponential, I mean an order of growth above polynomials, but less than exponential, for example $n^{\log n}$.

# Answer
> 73 votes
Depends on what you mean by subexponential. Below I explain a few meanings of "subexponential" and what happens in each case. Each of these classes is contained in the classes below it.

---

### I. $2^{n^{o(1)}}$

If by subexpoential you mean $2^{n^{o(1)}}$, then a conjecture in complexity theory called ETH (Exponential Time Hypothesis) *implies* that no $\mathsf{NP}$-hard problem can have an algorithm with running-time $2^{n^{o(1)}}$.

Note that this class is closed under composition with polynomials. If we have a subexponential time algorithm for any $\mathsf{NP}$-hard problem, we can combine it with a polynomial-time reduction from SAT to it obtain a subexponential algorithm for 3SAT which would violate ETH.

### II. $\bigcap\_{0 \< \epsilon} 2^{O(n^\epsilon)}$, i.e. $2^{O(n^\epsilon)}$ for *all* $0 \< \epsilon$

The situation is similar to the previous one.

It is closed under polynomials so no $\mathsf{NP}$-hard problem can be solved in this time without violating ETH.

---

### III. $\bigcup\_{\epsilon \< 1} 2^{O(n^\epsilon)}$, i.e. $2^{O(n^\epsilon)}$ for *some* $\epsilon \< 1$

If by subexponential you mean $2^{O(n^\epsilon)}$ for some $\epsilon\<1$ then the answer is yes, there are provably such problems.

Take an $\mathsf{NP}$-complete problem like SAT. It has a brute-force algorithm that runs in time $2^{O(n)}$. Now consider the padded version of SAT by adding a string of size $n^k$ to the inputs:

$$SAT' = \\{\langle \varphi,w\rangle \mid \varphi\in SAT \text{ and } |w|=|\varphi|^k \\}$$

Now this problem is $\mathsf{NP}$-hard and can be solved in time $2^{O(n^\frac{1}{k})}$.

### IV. $2^{o(n)}$

This contains the previous class, the answer is similar.

### V. $\bigcap\_{0 \< \epsilon}2^{\epsilon n}$, i.e. $2^{\epsilon n}$ for *all* $\epsilon\>0$

This contains the previous class, the answer is similar.

### VI. $\bigcup\_{\epsilon \< 1}2^{\epsilon n}$, i.e. $2^{\epsilon n}$ for *some* $\epsilon\<1$

This contains the previous class, the answer is similar.

---

### What does subexponential mean?

"Above polynomial" is not an upper-bound but a lower-bound and is referred to as *superpolynomial*.

Functions like $n^{\lg n}$ are called *quasipolynomial*, and as the name indicates are almost polynomial and far from being exponential, subexponential is usually used to refer a much larger class of functions with much faster growth rates.

As the name indicates, "subexponential" means *faster than exponential*. By exponential we usually mean functions in class $2^{\Theta(n)}$, or in the nicer class $2^{n^{\Theta(1)}}$ (which is closed under composition with polynomials).

Subexponential should be close to these but smaller. There are different ways to do this and there is not a standard meaning. We can replace $\Theta$ by $o$ in the two definitions of exponential and obtain I and IV. The nice thing about them is that they are uniformly defined (no quantifier over $\epsilon$). We can replace $\Theta$ with a multiplicative coefficient $\epsilon$ for all $\epsilon\>0$, we get II and V. Their are close to I and IV but nonuniformly defined. The last option is to replace $\Theta$ with a multiplicative constant $\epsilon$ for some $\epsilon\<1$. This gives II and VI.

Which one should be called subexponential is arguable. Usually people use the one they need in their work and refer to it as subexponential.

**I** is my personal preference, it is a nice class: it is closed under composition with polynomials and it is uniformly defined. It is similar to $\mathsf{Exp}$ which uses $2^{n^{O(1)}}$.

**II** is seems to be used in the definition of the complexity class $\mathsf{SubExp}$.

**III** is used for algorithmic upper-bounds, like those mentioned in Pal's answer.

**IV** is also common.

**V** is used to state the ETH conjecture.

Intersections (**II** and **V**) are not that useful for algorithmic upper-bounds, their main use seems to be complexity theory. In practice, you will not see a difference between **I** and **II** or between **IV** and **V**. IMHO the later three definition (**IV**, **V**, **VI**) are too sensitive, they might be useful for particular problems, but they are not robust which decreases their usefulness as classes. Robustness and nice closure properties are part of the reason why famous complexity classes like $\mathsf{L}$, $\mathsf{P}$, $\mathsf{NP}$, $\mathsf{PSpace}$, and $\mathsf{Exp}$ are interesting.

**Summary**

IMHO, the main definitions are **I** and **III**. We already have subexponential algorithms for $\mathsf{NP}$-hard problems in the sense of **III** and we cannot have them in the sense of **I** without violating ETH.

# Answer
> 38 votes
Just to list some, all with running time more or less $2^{O(\sqrt{n} \log n)}n^{O(1)}$ or $2^{O(\sqrt{n})}n^{O(1)}$:

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


title: Streaming Median

text:
# Question
Title: Streaming Median
I am looking for an efficient algorithm to find streaming data median. Median is described as the numerical value separating the higher half of a sample, a population, or a probability distribution, from the lower half.

We have stream of data in our system like 1, 10, -40, 20, 2, 6,.....Our task is find median of data as they arrive.

# Answer
> 3 votes
You can find the median approximately with this: Approximate Medians and other Quantiles in One Pass and With Limited Memory, to some degree of confidence. That algorithm works, but it's pretty slow. One of the authors of that paper, Gurmeet Manku, has some other publications that might be what you're looking for, also.

There's a stackoverflow question that seems relevant.

---
Tags: algorithms, statistics
---


title: Time complexity for modular arithmatic

text:
# Question
Title: Time complexity for modular arithmatic
I read about the time complexity for modular arithmetic in many books. There is one thing that I don't understand. I read in some books the following:

For any $a \mod N$, $a$ has a multiplicative inverse modulo $N$ if and only if it is relatively prime to $N$. When this inverse exists, it can be found in time $O(n^3)$ (where $n$ denotes the number of bits in the binary representation of $N$) by running the extended Euclid algorithm. My question revolves around extended Euclid algorithm having $O(n^3)$ complexity.

When I write in Java or C#, a line like this:

```
A = B.modInverse(N) // Java syntax

```

Can I usually say that this line has time complexity $O(n^3)$? Or is it necessary to write the code for the extended Euclid algorithm?

Secondly, does extended Euclid algorithm depend on the compiler or the computer architecture?

# Answer
> 1 votes
The running time of a library function depends on the way the library function is implemented. Moreover, oftentimes it is worthwhile to code non-optimal algorithms, since for practical $n$ they might be more efficient. One good example is matrix multiplication, where the fancy algorithms are slower in practice than optimized versions of the trivial one.

In your specific case, my guess would be that they implemented the textbook solution. You can always try looking at the source code. Another possibility is timing the function for various $n$, and see if the running time scales like $n^3$.

---
Tags: time-complexity, compilers
---


# Question
Title: What is meant by Category theory doesn't yet know how to deal with higher-order functions?
In reading Uday Reddy's answer to What is the relation between functors in SML and Category theory? Uday states

> Category theory doesn't yet know how to deal with higher-order functions. Some day, it will.

As I thought Category theory was able to serve as a foundation for math, then it should be possible to derive all of math and higher-order functions.

So, what is meant by Category theory doesn't yet know how to deal with higher-order functions? Is it valid to consider Category theory as a foundation for math?

# Answer
The issue with higher-order functions is simple enough to state.

* A type-constructor like $T(X) = \[X \to X\]$ is not a functor. It should have been.
* A polymorphic function like ${\it twice}\_X : T(X) \to T(X) = \lambda f.\\, f \circ f$ is not a natural transformation. It should have been.

If you read Eilenberg and MacLane's original category theory paper, (PDF) the intuitions they present cover those cases. But their theory doesn't. Theirs was a *great paper* for 1945! But, today, we need more.

The reaction of category theorists to these issues is a bit perplexing. They act as if higher-order operations form a Computer Science idea; they are of no consequence to mathematics. If that is so, then a foundation of mathematics would not be good enough for a foundation of computer science.

But I don't seriously believe that. I believe that higher-order functions would be quite important for mathematics as well. But they have not been seriously explored. I am hopeful that, some day, they will be explored and the limitations of category theory will be realized.
> 15 votes

# Answer
\[This second answer presents an outline of what a "Category Theory 2.0", that deals with higher-order functions properly, might look like.\]

We have known for a long time how to deal with higher-order functions in reasoning about them.

* When an algebraic structure has higher-order operations, homomorphisms don't work. We must use *logical relations* instead. In other words, we must move from "*functions* preserving structure" to "*relations* preserving structure".
* To talk about "uniform" or "simultaneously given" transformations on higher-order types, naturality doesn't work. We must use *relational parametricity* instead. In other words, we must move from "families preserving all *morphisms*" to "families preserving all *logical relations*".
* Composition of logical relations is of no consequence. The $\to$ type constructor doesn't preserve their composition, and nothing depends on it. (This observation is at logger heads with the category theorists' belief that composition is fundamental!)

A quick introduction to these issues is in Peter O'Hearn's section on "Relational Parametricity" in Domains and Denotational Semantics: History, Accomplishments and Open Problems (CiteSeerX).

I might also add that reasoning about *state* is where higher-order functions show up prominently. Automata-theorists were the first to recognize that homomorphisms don't work correctly, in a historic paper called Products of Automata and the Problem of Covering. They used terms like "weak homomorphisms" and "covering relations" to refer to logical relations. In due course, terms like "simulation" and "bisimulation" were used to refer to them. Davide Sangiorgi's survey article: On the Origins of Bisimulation and Coinduction covers all of this early history and more.

The need for relational reasoning repeatedly crops up in reasoning about state, in particular *imperative programming*. Very few people notice that the humble "semicolon" is a higher-order operation. So, you cannot get off the ground in thinking about imperative programs without knowing how to deal with higher-order functions. We keep ignoring the issues of state and imperative programming in the mistaken belief that mathematics has all the answers. So, if mathematicians don't understand state, it must be no good! Nothing could be further from the truth. State is at the heart of Computer Science. We will be advancing science in general by showing people how to deal with state!
> 10 votes

---
Tags: functional-programming, category-theory
---


title: Regular and context free languages

text:
# Question
Title: Regular and context free languages
I need to determine if the following languages are regular / context free and to explain. Please help me with that.

$$L\_1 = \\{ a^{i\_{1}}b a^{i\_{2}}b a^{i\_{3}}b a^{i\_{4}}b a^{i\_{5}}b a^{i\_{6}}b a^{i\_{7}}b a^{i\_{8}}b a^{i\_{9}}b a^{i\_{10}}b \mid i\_1 \> i\_2 \> i\_3 \> i\_4 \> i\_5 \> i\_6 \> i\_7 \> i\_8 \> i\_9 \> i\_{10} ; i\_1 \< 100 \\}$$

$$L\_2 = \\{ a^{i\_{1}}b a^{i\_{2}}b a^{i\_{3}}b a^{i\_{4}}b a^{i\_{5}}b a^{i\_{6}}b a^{i\_{7}}b a^{i\_{8}}b a^{i\_{9}}b a^{i\_{10}}b \mid i\_1 \> i\_2 \> i\_3 \> i\_4 \> i\_5 \> i\_6 \> i\_7 \> i\_8 \> i\_9 \> i\_{10} ; i\_2 \< 100 \\}$$

$$L\_3 = \\{ a^{i\_{1}}b a^{i\_{2}}b a^{i\_{3}}b a^{i\_{4}}b a^{i\_{5}}b a^{i\_{6}}b a^{i\_{7}}b a^{i\_{8}}b a^{i\_{9}}b a^{i\_{10}}b \mid i\_1 \> i\_2 \> i\_3 \> i\_4 \> i\_5 \> i\_6 \> i\_7 \> i\_8 \> i\_9 \> i\_{10} ; i\_3 \< 100 \\}$$

# Answer
$L\_1$ is finite. $L\_2$ is a concatenation of $x^\*$ and a finite language. $L\_3$ is about a hard as $\\{x^iy^j | i \> j\\}$. I'm leaving these as hints. Add a comment if you can't figure out why this is true.
> 5 votes

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


# Question
Title: Is pumping lemma for regular languages "closed" against Kleene star?
If I have an infinite language $L$ which fulfills the Pumping lemma for regular languages, does $L^\*$ also fulfill the same conditions?

# Answer
> 1 votes
In order to show the pumping property of a string like $x\_1x\_2 \dots x\_n$, where each $x\_i\in L$ you can distinguish two cases. Either $x\_1$ is "short", which means you can pump $x\_1$ completely and stay within $L^\*$, or $x\_1$ is "long" and you can pump "inside" $x\_1$.

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


# Question
Title: What is the difference between these terms?
Between my textbook and various online sources (namely wikipedia), I'm very confused... can somebody clear up which words are synonymous and which mean different things?

* Many-to-one reduction
* Mapping reduction
* Turing reduction
* Cook reduction
* Karp reduction
* Polynomial-time many-to-one reduction
* Polynomial time turing reduction

I've also seen others, but I can't recall them currently.

# Answer
> 5 votes
Let $A,B\subseteq \Sigma^\*$ be languages.

Many-to-one: A (computable) function $f:\Sigma^\*\to \Sigma^\*$ such that $\forall x\in \Sigma^\*$, $x\in A\iff f(x)\in B$. The names "Mapping reduction" and "Karp reductions", to my knowledge, refer to "Many to one". The "Many to one" means that $f$ may not be injective.

Turing reduction: we say that $A\le\_T B$ if, given an oracle to the language $B$, we can use it to solve $A$. The word "solve" here should be in the context of a specific complexity/computability class.

Turing reductions are weaker than many-to-one reductions. The latter can be viewed as Turing reductions where we are only allowed to call the oracle once - at the very end of the run.

polynomial time many-to-one reductions - simply adding a constraint that the reduction $f$ is computable in polynomial time.

polynomial time Turing reduction (= Cook reduction) - add the constraint that the oracle machine runs in polynomial time, counting each oracle call as $O(1)$.

---
Tags: complexity-theory, computability, terminology, reductions
---


# Question
Title: Why is $(\log(n))^{99} = o(n^{\frac{1}{99}})$
I am trying to find out why $(\log(n))^{99} = o(n^{\frac{1}{99}})$. I tried to find the limit as this fraction goes to zero.

$$ \lim\_{n \to \infty} \frac{ (\log(n))^{99} }{n^{\frac{1}{99}}} $$

But I'm not sure how I can reduce this expression.

# Answer
> 7 votes
$\qquad \begin{align} \lim\_{x \to \infty} \frac{ (\log(x))^{99} }{x^{\frac{1}{99}}} &= \lim\_{x \to \infty} \frac{ (99^2)(\log(x))^{98} }{x^{\frac{1}{99}}} \\ &= \lim\_{x \to \infty} \frac{ (99^3) \times 98(\log(x))^{97} }{x^{\frac{1}{99}}} \\ &\vdots \\ &= \lim\_{x \to \infty} \frac{ (99^{99})\times 99! }{x^{\frac{1}{99}}} \\ &= 0 \end{align}$

I used L'Hôpital's rule law in each conversion assuming natural logarithm.

# Answer
> 5 votes
Hint: take $99$th root of both sides.

# Answer
> 4 votes
Try a common trick: express both functions as $e^{\dots}$ and compare the exponents; if *their* ratio tends to $0$ or $\infty$, so does the original quotient (see here for the full rule).

> $\frac{(\log n)^{99}}{n^{\frac{1}{99}}} = \frac{e^{99 \cdot \log(\log n)}}{e^{\frac{1}{99} \cdot \log n}}$

---
Tags: asymptotics, landau-notation
---


# Question
Title: What is the difference between "for infinitely many n" and "for all n"?
I have read some complexity papers in which "for infinitely many input sizes" is used.

What is the difference in the computational complexity context between "for infinitely many input sizes" and "for all input sizes"?

# Answer
"for infinitely many input sizes $n$, $P(n)$ holds" means there are input sizes $n\_1$, $n\_2$, $\ldots$, (infinitely many) such that $P(n\_i)$ holds for all $i$. In other words, for every integer $k$, there is an input length $n \geq k$ such that $P(n)$ holds.

In contrast, "for all input sizes, $P(n)$ holds" means that for **every** input size $n$, $P(n)$ holds.

Typically, "for all input sizes, $P$ holds" and "for almost every input size, $P$ holds" are used interchangeably, although the latter technically means that there is a $k$ such that for all input sizes $n \geq k$, $P$ holds. (Note that the negation of "for infinitely many input sizes, $P$ holds" is "for almost every input size, $\neg P$ holds.") This is generally because in the models of computation being considered, constant factors don't matter, so from an "almost every input size" statement you can generally hardcode the solutions for all inputs of length less than $k$ in your model, and get a "for all input sizes" statement.
> 10 votes

# Answer
"For infinitely many input sizes" makes sense in many contexts. For example, when considering the running time of a TM, it may be the case that for all odd-sized inputs, the machine trivially rejects (e.g. if it's an illegal encoding of an instance). In this case, the runtime of a machine can be long only for even sized inputs (from which there are infinitely many), and we take the latter as the over-all runtime (and with some abuse, we may even consider it as $\theta$ of the runtime).
> 2 votes

---
Tags: complexity-theory, terminology
---


title: Counting Inversions Using Merge Sort

text:
# Question
Title: Counting Inversions Using Merge Sort
In Corman, Introduction To Algorithms, 3rd edition, question 2-4 it asks to count the number of inversions in a list of numbers in $\theta( n \lg n )$ time. He uses a modified Merge Sort to accomplish this. However, there is something in his algorithm which seems redundant / unnecessary to me:

```
MERGE-INVERSIONS(A, p, q, r)
n1 = q - p + 1
n2 = r - q
let L[1 ... n1 + 1] and R[1 ... n2 + 1] be new arrays
for i = 1 to n1
    L[i] = A[p + i - 1]
for j = 1 to n2
    R[j] = A[q + j]
L[n1 + 1] = infinity
R[n2 + 1] = infinity
i = 1
j = 1
inversions = 0
counted = FALSE
for k = p to r
    if counted == FALSE and R[j]  < L[i]
        inversions = inversions + n1 - i + 1
        counted = TRUE
    if L[i] <= R[j]
        A[k] = L[i]
        i++
    else A[k] = R[j]
        j++
        counted = FALSE
return inversions

```

The `counted` variable seems redundant to me and I would have written the last for loop as follows:

```
inversions = 0
for k = p to r
    if L[i] <= R[j]
        A[k] = L[i]
        i++
    else A[k] = R[j]
        inversions = inversions + n1 - i + 1
        j++
return inversions

```

What am I missing, or is `counted` really unnecessary?

# Answer
We can show that after every iteration of the `for`-loop in question, `counted` is `FALSE`. Therefore, `inversions = inversions + n1 - i + 1` is executed if and only if `j++` is executed in the same iteration (both are guarded by `R[j] < L[i]`). Since neither `i` nor `j` is changed between evaluation of the two `if` conditions, this implies that your version is equivalent.

> We perform an induction over `k`. Before the loop, `counted` is explicitly set to `FALSE`. In any given iteration, we start (by induction hypothesis) with `counted == FALSE`. If `L[i] <= R[j]`, `counted` is not changed throughout the current iteration. If the opposite is the case, `counted` is first set to `TRUE`, but reset to `FALSE` in the `else` block. For this, we note that the truth value of `R[j] < L[i]` remains unchanged from the first to the second `if`.

I guess the extra block is there for didactic reasons.
> 2 votes

---
Tags: algorithms, algorithm-analysis, sorting, program-correctness
---


# Question
Title: Showing that minimal vertex deletion to a bipartite graph is NP-complete
Consider the following problem whose input instance is a simple graph $G$ and a natural integer $k$.

> Is there a set $S \subseteq V(G)$ such that $G - S$ is bipartite and $|S| \leq k$?

I would like to show that this problem is $\rm{NP}$-complete by reducing either 3-SAT, $k$-CLIQUE, $k$-DOMINATING SET or $k$-VERTEX COVER to it.

I believe I can reduce the 3-COLORING problem to it so I would only need to see how to reduce one of the mentioned problems to it. But since that would be rather messy I am wondering if someone sees an elegant reduction to the aforementioned problems.

Also, is there a name for this decision problem?

# Answer
Your problem is a special case of a broader class of problems named *node-deletion problems*:

J. M. Lewis and M. Yannakakis, "The node-deletion problem for hereditary properties is NP-complete"

... This paper deals with the class of graph problems defined as follows:
for a fixed graph property $\Pi$, find the minimum number of nodes (or vertices) which must be deleted from a given graph $G$ so that the result satisfies $\Pi$. We call this the *node-deletion problem* for $\Pi$. Our results show that if $\Pi$ is a *nontrivial* property which is *hereditary* on induced subgraph, then the node-deletion problem for $\Pi$ is NP-hard. Furthermore, if we add the condition that testing for $\Pi$ can be performed in polynomial time, then our results imply that the node-deletion problem for $\Pi$ is NP-complete. ...

Your problem is the *node deletion problem for bipartiteness*, but (as noted by Pal), it is known today as the *Odd cycle traversal* (OCT) problem.

**EDIT**

For what regards a direct reduction, I thought of this one from 3SAT.

Given an instance of 3SAT with $n$ variables and $m$ clauses, build the following graph: add two nodes $x\_i, \overline{x\_i}$ for each variable and an edge between them. To simulate a truth assignment, add $n+1$ nodes for each variable $x\_i$ and connect them both to $x\_i$ and $\overline{x\_i}$; in this way, in order to make a bipartite graph deleting at most $n$ nodes, at least one between $x\_i$ and $\overline{x\_i}$ must be deleted . Finally for each clause $C\_j$ add 4 nodes and build an odd cycle that connects the variables in $C\_j$.

The resulting graph $G$ can be made bipartite deleting at most $n$ nodes if and only if the original 3SAT formula is satisfiable.
> 8 votes

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


# Question
Title: Minimizing the full adder - where did this XOR come from?
When minimizing the full adder, I don't understand why $A(\bar{B}\bar{C} + BC)$ reduces to $A\overline{(B\oplus{C})}.$

$(\bar{B}\bar{C} + BC)\to (B\oplus{C})$ is partially decipherable, but why is $(B\oplus{C})$ inverted to $\overline{(B\oplus{C})}?$

---

Full adder simplification:

$ \bar{A}\bar{B}C + \bar{A}B\bar{C} + A\bar{B}\bar{C} + ABC \\ = \bar{A}(\bar{B}C + B\bar{C}) + A(\bar{B}\bar{C} + BC) \\ = \bar{A}(B\oplus{C}) + A(\overline{B\oplus{C}}) \\ = A\oplus{(B\oplus{C})} $

---

### Could you help me out?

PS: I hope that this is the correct subforum of StackExchange to ask this (perhaps *Electrical Engineering* is the proper venue). I couldn't find appropriate tags on *either* site.

# Answer
> 5 votes
Hint 1: Intuitively, $\oplus$ implies exactly one of the two inputs is $1$ ($B$ and $C$ here). Whereas, $(\bar{B}\bar{C} + BC)$ implies *both* inputs are $0$ or both are $1$.

Hint 2: Start from $\overline{(B \oplus C)}$, expand it, use De'Morgan's laws, simplify and you should reach $(\bar{B}\bar{C} + BC)$.

# Answer
> 5 votes
Consider the truth table for $(\overline{B}\overline{C}+BC)$. It has 1's exactly when $B$ and $C$ get the same value, which is exactly when $(B\oplus C)$ gets 0, hence, $\overline{B\oplus C}$ is equivalent to $(\overline{B}\overline{C}+BC)$.

---
Tags: binary-arithmetic, xor
---


# Question
Title: Are co-semidecidable languages separated by decidable ones?
Can I use principles of set theory in order to solve the following question?

> For every $A,B \in \mathsf{co\text{-}RE}$ with $A \cap B = \emptyset$, there is a separating language $C$ with $A \subseteq C$ and $B \cap C = \emptyset$ so that $C$ is recursive.

# Answer
> 9 votes
This is a classical exercise in computability. Since $A,B\in coRE$, there exist TMs $M,N$ that recognize $\overline{A}$ and $\overline{B}$ respectively.

Consider the following TM $K$: Given a word $w$, run in parallel $M$ and $N$ on $w$. That is, simulate $M$ for a single step, and then $N$ for a single step, and repeat.

If $M$ accepts at any point, reject. If $N$ accepts at any point, accept. (if both accept, reject, so we first check $M$ for acceptance).

Define $C=L(K)$.

If $A\cap B=\emptyset$, then $\overline{A}\cup\overline{B}=\Sigma^\*$, so either $M$ or $N$ eventually accepts, so $K$ always halts. Thus, $C$ is decidable.

We claim that $C$ satisfies the requirements: if $x\in A$, then $M$ never accepts $x$, so $N$ accepts $x$, so $K$ accepts, so $x\in C$. Thus, $A\subseteq C$.

If, by way of contradiction, $x\in B\cap C$, then $K$ accepts $x$, which means $N$ accepts $x$, so $x\notin B$ - contradiction. So $B\cap C=\emptyset$.

We conclude that $C$ satisfies the requirements.

# Answer
> 6 votes
The thing you are trying to prove is called the "separation principle" for $\Pi^0\_1$ sets (remember co-r.e. sets are $\Pi^0\_1$ and r.e. sets are $\Sigma^0\_1$ in the arithmetical hierarchy).

The dual "reduction principle" for $\Sigma^0\_1$ sets states that given two $\Sigma^0\_1$ sets $X,Y$ whose union is $\mathbb{N}$, it is possible to find $\Sigma^0\_1$ sets $X',Y'$ with $X' \subseteq X$, $Y' \subseteq Y$, $X' \cap Y' = \emptyset$, and $X' \cup Y' = \mathbb{N}$. This is proved in the way Shaull indicates: put a number into $X'$ if it enters $X$ before $Y$, put it in $Y'$ if it enters $Y$ before $X$, and put "ties" into $X'$. Note that $X'$ and $Y'$ will be complements of each other and thus computable.

The question is then answered by starting with $\Pi^0\_1$ sets $A,B$, letting $X= A^c$ and $Y=B^c$ be the complementary $\Sigma^0\_1$ sets, and applying the reduction principle. Then you can just let $C = Y'$. A small Venn diagram calculation shows that $C$ is indeed a separating set for $A$ and $B$. For example, because $C= Y' \subseteq Y = B^c$, we have that $C \cap B = \emptyset$.

The reduction principle and separation principle are two classical principles that a class of sets may or may not satisfy. For example, the reduction principle holds for $\Sigma^0\_1$ sets, but not for $\Pi^0\_1$ sets. Dually, the separation principle holds for $\Pi^0\_1$ sets (as in the question) but not for $\Sigma^0\_1$ sets. Much more is known about which other classes of sets satisfy these principles, which date back to work of Kuratowski. For example see the Encyclopedia of Mathematics or section 7 of a classic article by John Addison, Separation principles in the hierarchies of classical and effective descriptive set theory, *Fundamenta Mathematicae* 46, 1958

---
Tags: computability
---


title: Substitution by structural recursion

text:
# Question
Title: Substitution by structural recursion
*Following the article's notation, I write $\mathcal{F}$ for the category of presheaves on a (suitable) category $\mathbb{F}$, $TV$ for the presheaf of terms, $\delta$ for the context extension, and $\bullet$ for the product of the $\mathcal{F}$-monoid.*

In Abstract Syntax and Variable Binding \[Fiore, Plotkin, Turi\], the authors set out to define substitution by structural recursion (Section 3). I was expecting to see substitution expressed as an initial algebra of some sort.

Instead, from what I understand, the authors:

1. Construct the substitution $\sigma : \delta(TV) \times TV \to TV$ by some universal construction ("Definition of substitution by structural recursion")
2. Show that it forms a substitution algebra (Theorem 3.2)
3. Show that the categories of substitution algebras and clones are equivalent (Theorem 3.3)
4. Show that the categories of clones and monoids in $\mathcal{F}$ are equivalent (Proposition 3.4)
5. Show that subtitution is the multiplication of such a monoid (Proposition 3.5)
6. Conclude that $\sigma$, the substitution, is defined by structural recursion (Corollary 3.6).

I'm failing to appreciate their motive in moving from substitution algebras to clones to monoids. Is that a natural thing to do for a mathematician?

In particular, why not stay focused on substitution algebras and, I guess, present substitution as the initial one?

Conversely, they claim that Corollary 3.6 gives a definition of substitution by structural recursion: how is that? It is just said that "$\sigma$ is the unique homomorphic extension of $V \bullet TV \cong TV$": how did they derive their example (substitution for the lambda calculus, very end of Section 3) from this statement?

# Answer
> 1 votes
A more tutorial-paced presentation of the same/related material is available in: Roy L. Crole: Basic Category Theory for Models of Syntax. Generic Programming 2003: 133-177. This should help.

---
Tags: lambda-calculus, category-theory
---


title: Context Free Grammar for language L

text:
# Question
Title: Context Free Grammar for language L
Can someone help with this:

$L=\\{a^ib^j \mid i,j \ge 1 \text{ and } i \ne j \text{ and } i\<2j\\}$

I'm trying to write a grammar for this language? I tried this:

$S \to S\_1 \mid S\_2 \\ S\_1 \to aXb \\ X \to aXb \mid aaXb \mid aab \\ S\_2 \to aYb \\ Y \to aYb \mid Yb \mid b \\ $

What do you think?

# Answer
> 3 votes
The solution in the question is correct.

The constraint $i\ne j$ is the one that gives us trouble. To get around it we have to split into two cases: (i) $i\<j$, and (ii) $i\>j$ (but still $i\<2j$)

thus
$S\to S\_{(i)} \mid S\_{(ii)}$
as the first production splits into this two cases.

Now, divide and conquer: case (i) is very simple, since we only need $i\<j$,
$S\_{(i)} \to aS\_{(i)}b \mid B$
$ B \to Bb \mid b$

This is your $S\_2$.

For case (ii), we need to $j\< i \< 2j$, so for every single $a$, the variable $C$ will generate exactly one $b$, and at a certain point we switch to the variable $D$ that will generate two $a$'s for each $b$.
$S\_{(ii)} \to aCb $
$ C \to aCb \mid D$
$ D \to aaDb \mid aab$

This is your $S\_1$.

---
Tags: formal-languages, context-free, formal-grammars, check-my-answer
---


title: Sketch an IP proof for minSAT

text:
# Question
Title: Sketch an IP proof for minSAT
I have to sketch an IP proof for the minSAT problem. The minSAT problem is define in this way:

* For a given formulae find a satisfying assignment with a min subset of variables assigned to True;

My sketched IP protocol is:

1. Prover and Verifier share the input formula
2. Prover sends to the Verifier a set of variables assigned to True, which should be the minimum
3. Verifier checks if the given set indeed satisfies the formula. If it is the case, it chooses one variable, re-computes the formula and sends the new formula to the Prover

I would iterate this process untill the Prover gives an empty set or I reach a contradiction.

My questions are:

* Is this a right protocol? If not, how can I exploit the cases in which the protocol doesn't work?
* How can I evaluate the probability of completness and soundness for this protocol?

# Answer
Your protocol is not very clear. What do you mean at step 3 by "it chooses one variable, re-computes the formula"?

I assume the verifier just sets that variable to 1 and re-computes the formula without that variable.

Then, this protocol still has some problems. Let's say that there are two sets of variables that satisfy the formula: $\\{x\\}$ and $\\{y,z\\}$. The minSat is $x$. But what happens if the prover says it is $y,z$? the verifier checks this proposed set, and sees that the set satisfies the formula; then the verifier removes one variable, say $y$, and sends the formula back to the prover. The prover will then reply with $\\{z\\}$ and the verifier will accept it.

Even if the verifier renames the variables in a random way, (say, replace $x$ with $a$ and $z$ with $b$), it's not clear that this protocol works. Still, maybe the prover is able to identify the variable that previously was $z$ from the structure of the formula, and repeat the faulty behaviour described above.

So although in the suggested protocol the prover cannot reply with a set that doesn't satisfy the formula, the prover *can* give a non-minimal set, and the verifier will (wrongly) accept it.
> 4 votes

---
Tags: satisfiability, interactive-proof-systems
---


# Question
Title: Worst case analysis of bucket sort using insertion sort for the buckets
Suppose I am using the Bucket-Sort algorithm, and on each bucket/list I sort with insertion sort (replace nextSort with insertion sort in the wikipedia pseudocode).

In the worst case, this would imply that we would have $O(n^2)$ performance, because if every element was in one bucket, then we would have to use insertion sort on $n$ elements which is $O(n^2)$.

So the first thing that comes to mind to fix the worst case running time is to not use insertion-sort, because it is $O(n^2)$. Instead we could use merge-sort or heap-sort m, because the worst case running time for both of those algorithms is $O(n\log n)$. However, if we use merge-sort and heap-sort, do they preserve the expected linear running-time of bucket-sort?

# Answer
> 5 votes
You should first understand the proof that bucket sort runs in expected linear time if insertion sort is used. At some point in the proof, the worst-case running time of insertion sort shows up. See what happens when you plug in instead the worst-case running time of any other sorting algorithm.

The reason insertion sort is used in practice is that we expect the buckets to be small, and for small lists, insertion sort is much faster than anything else. Even when implementing merge sort or quicksort, insertion sort is used when the list gets small enough (say below 20 items or so).

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


# Question
Title: Hardness of approximating 0-1 integer programs
Given a $0,1$ (binary) integer program of the form:

$$ \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x\_i \ge 0 & \quad \forall i\\ & x\_i \in \\{0,1\\} & \quad \forall i \end{array} $$

Note that the size of $A$ is not fixed in either dimension.

I believe this problem has been shown to be hard to approximate (strongly ${\sf NP}$-Complete) by Garey & Johnson. If so, is this still the case when $A, b$ have binary entries and $f(x)$ is a linear function ( $f(x) = \sum\_i c\_i x\_i$ )?

# Answer
> 5 votes
One-in-three 3SAT is NP-complete. Looking at the reduction, it inherits the APX-hardness of 3SAT. You can formulate one-in-three 3SAT as a binary integer program with binary entries, so you problem is APX-hard.

---
Tags: complexity-theory, np-complete, approximation, integer-programming
---


title: Is this a correct decider?

text:
# Question
Title: Is this a correct decider?
We are given the following language

B = {$\<M,i\>$ : M is a turing machine and $i \in \mathcal{N}$ and M accepts some string in atmost $i$ steps }

Is language B decidable ?

As per a hint from another fellow user, I decided to construct the following decider for B. Call it D.

D = On input

1. Enumerate all the strings in $\Sigma^\*$ in lexicographical order (shortlex). Let the generated sequence be $s\_1,s\_2,...$ where each $s\_k$ denotes all strings of lenght $k$
2. Simulate each string in $s\_k$ on M for atmost i steps.
3. If any of them is accepted, ACCEPT.
4. When we have finished evaluating strings for length $s\_i$, output REJECT.

Is this the correct decider for B ?

# Answer
This language is decidable.

Hint: If you are allowed to run for only $i$ steps, what can you do with input of size $j\>i$?
> 5 votes

# Answer
The solution in the question is correct.

As the comments say, with $i$ steps any TM can check only inputs of length at most $i$ (the behaviour on longer inputs will be the same as the behaviour on their prefix of length $i$). There is a finite number of those, which can be checked one by one by running $i$ steps on each.
> 1 votes

---
Tags: undecidability
---


# Question
Title: Finding the number of iterations to a recurrence
I have an algorithm where the number of items in my set decrease by $\sigma/(1+\sigma)$ on each iteration until all items are exhausted.

$$ \begin{align\*} S\_0 &= S \\ S\_{k+1} &= S\_k - S\_k \frac{\sigma}{1+\sigma} \end{align\*} $$

Here $\sigma$ is a small value.

How can I find number of iterations? I know it is a geometric series but can't seem to simplify for number of iterations.

# Answer
Presumably the correct form of the recursive step is $$ S\_{k+1} \leq S\_k - S\_k \frac{\sigma}{1+\sigma} = \frac{S\_k}{1+\sigma}. $$ Using induction, we can show that $$ S\_t \leq \frac{S}{(1+\sigma)^t}. $$ So the algorithm will end by the time $T$ satisfying $$ \frac{S}{(1+\sigma)^T} \< 1.$$ I'll let you solve this yourself.
> 4 votes

# Answer
Let $I$ denote the number of iterations and $s$ the size of your set. Then we have

$$I(s)=I(s-\frac{\sigma}{1+\sigma})+1=I(s-2\frac{\sigma}{1+\sigma})+2=\dots=I(s-k\frac{\sigma}{1+\sigma})+k$$

$s-k\frac{\sigma}{1+\sigma}=0$ when $k=s\frac{1+\sigma}{\sigma}$. Therefore

$$I(s)=s\frac{1+\sigma}{\sigma}$$
> 0 votes

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


# Question
Title: Computing inverse matrix when an element changes
Given an $n \times n$ matrix $\mathbf{A}$. Let the inverse matrix of $\mathbf{A}$ be $\mathbf{A}^{-1}$ (that is, $\mathbf{A}\mathbf{A}^{-1} = \mathbf{I}$). Assume that one element in $\mathbf{A}$ is changed (let's say $a \_{ij}$ to $a' \_{ij}$). The objective is to find $\mathbf{A}^{-1}$ after this change. Is there a method to find this objective that is more efficient than re-calculating the inverse matrix from scratch.

# Answer
> 13 votes
The Sherman-Morrison formula could help:

$$ (A + uv^T)^{-1} = A^{-1} - \frac{A^{-1} uv^T A^{-1}}{1 + v^T A^{-1} u}. $$

Let $u = (a'\_{ij}-a\_{ij}) e\_i$ and $v = e\_j$, where $e\_i$ is the standard basis column vector. You can check that if the updated matrix is $A'$ then $$ A^{\prime -1} = A^{-1} - \frac{(a'\_{ij}-a\_{ij})A^{-1}\_{\downarrow i} A^{-1T}\_{j\rightarrow}}{1 + (a'\_{ij}-a\_{ij})A^{-1}\_{ij}},$$ where $A^{-1}\_{\downarrow i}$ denotes the $i$-th column vector of $A^{-1}$ and $A^{-1}\_{j\rightarrow}$ denotes the $j$-th row vector of $A^{-1}$

# Answer
> 7 votes
A single element change, given $A$ with $A^{-1}$, may be tracked with a rank one update. So yes, absolutely, there is a better way than recalculating the inverse from scratch.

Let $\delta = a\_{ij}' - a\_{ij}$ be the change of the element $a\_{ij}$. Using $e\_i$ as the unit column vector of one in the $i$ position and zeroes elsewhere, we have $$(A + e\_i \delta e\_j^\top )A^{-1} = I + e\_i \delta e\_j^\top A^{-1}$$

$e\_i \delta e\_j^\top$ is the zero matrix, except the value of $\delta$ in the $ij$ position. Can you see here how an appropriate rank one right multiplication with $A^{-1}$ may give the desired new inverse? (Or equivalently, elementary column operations on $A^{-1}$.)

Or if you like to do row operations instead, you can use $$A^{-1}(A + e\_i \delta e\_j^\top ) = I + A^{-1}e\_i \delta e\_j^\top$$

In the first case we have the identity with a row added. This is easy to do column operations upon to have the identity back again. Do these operations on $A^{-1}$ and the result is the new inverse, as desired. The second case is the identity with a column added. In that case, you may do row operations instead. You may choose whichever is more convenient.

---
Tags: algorithms, numerical-analysis, online-algorithms
---


# Question
Title: Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?
I am trying to analyze the running time of a bad implementation of generating the $n$th member of the fibonacci sequence (which requires generating the previous 2 values from the bottom up).

Why does this algorithm have a time complexity of $\Omega(2^{\frac{n}{2}})$? Where does the exponent come from?

# Answer
> 14 votes
Expanding on Reza's answer, every recurrence of the form $T(n) = T(n-1) + T(n-2)$, with arbitrary initial values, has a solution of the form $$ T(n) = A \left( \frac{1+\sqrt{5}}{2} \right)^n + B \left( \frac{1-\sqrt{5}}{2} \right)^n, $$ for some $A,B$. Note that $|(1-\sqrt{5})/2| \< 1$, and so the second term tends to zero as $n \longrightarrow \infty$. Assuming that $T(n)$ tends to infinity, $A \> 0$ and so $$ T(n) = \Theta\left( \left( \frac{1+\sqrt{5}}{2} \right)^n \right). $$ Now $(1+\sqrt{5})/2 \> \sqrt{2}$, and so $T(n) = \Omega(2^{n/2})$.

---

Edit: This part is also covered in this answer (see under "A Shortcut").

More generally, for a recurrence of the form $T(n) = \sum\_{i=1}^k a\_i T(n-i)$, let $$ P(t) = t^n - \sum\_{i=1}^k a\_i t^{n-i}. $$ If $P$ has no repeated roots and the (possibly complex) roots are $\lambda\_1,\ldots,\lambda\_k$, then the solution is always of the form $$ T(n) = \sum\_{i=1}^k A\_i \lambda\_i^n. $$ If it does have repeated roots, say the roots are $\lambda\_1,\ldots,\lambda\_l$ with multiplicities $m\_1,\ldots,m\_l$, then the solution is always of the form $$ T(n) = \sum\_{i=1}^l A\_i(n) \lambda\_i^n, $$ where $A\_i$ is a (possibly complex) polynomial of degree smaller than $m\_i$.

In our case, $P(t) = t^2-t-1$ has no repeated roots, and the two roots are $(1\pm\sqrt{5})/2$.

The $A\_i$s depend on the initial values, and can be found by solving linear equations. For example, suppose we are given $T(0)$ and $T(1)$ for our recurrence. Then we can find $A,B$ by solving the system $$ \begin{align\*} T(0) &= A + B, \\ T(1) &= \frac{1+\sqrt{5}}{2} A + \frac{1-\sqrt{5}}{2} B. \end{align\*} $$ This works even in the case of repeated roots, and $k$ initial values always suffice. Assuming $a\_k \neq 0$, $k$ initial values are also necessary.

# Answer
> 4 votes
It's not $O(2^{n\over 2})$ is $\Theta(\phi^n)$ which doesn't belong to $O(2^{n\over 2})$ but you can say belongs to $\Omega(2^{n\over 2})$ or belongs to $O(2^n)$ (and saadtaame showed this in his answer), So be careful about abuse of notations. But why is $\Theta(\phi^n)$? as a student of CS you should try to solve it yourself but if you tried and you couldn't show it, show us your try and we can help you.

Oh Seems I forgot to say why is in $\Omega(2^{n\over 2})$ (and I think your main question was this, or totally you were wrong): $T(n) = T(n-1)+T(n-2) \gt 2T(n-2)$ and this results: $T(n) \> 2^{n\over 2}T(0)$.

# Answer
> 1 votes
The running time of the naive solution is: $$T(n)=T(n-1)+T(n-2) \lt 2T(n-1)$$ Now, $$2T(n-1)=2(2T(n-2))=2(2(2T(n-3)))=\dots=2^kT(n-k)=\dots=2^nT(0)=O(2^n)$$

The base case takes time $T(0)=\Theta(1)$. So that's where the exponent is coming from. This result is an upper bound; you can obtain a tighter bound if you solve the recurrence using generating functions for example.

# Answer
> 1 votes
you can find for **Every linear recurrence with constant coefficients** a closed form. (See the link) the Fibonacci numbers have a closed-form solution as (the approximation is for large ns):

$F\_n \times \sqrt{5} ={ \left( \frac { 1+\sqrt { 5 } }{ 2 } \right) }^{ n }-{ \left( \frac { 1-\sqrt { 5 } }{ 2 } \right) }^{ n } \simeq { \left( \frac { 1+\sqrt { 5 } }{ 2 } \right) }^{ n } \simeq (1.6180..)^n \simeq 2.89^{n/2} $

or more formaly $ F\_n \in\Omega (2^{n/2})$.

You can find more in Conceret Mathematics, by Ronald L. Graham, Donald E. Knuth and Oren Patashnik, chapter 6 : Special Numbers.

---
Tags: algorithms, algorithm-analysis, asymptotics, runtime-analysis, recurrence-relation
---


# Question
Title: Algorithm for finding optimal branch points
I'm developing software to run variations on a base process flow (see #1, below). A user specifies in a text file what steps in the process to modify. Because each step takes a long time to run, I'd like to minimize the amount of duplicate processing required. For example, if variations occur at step B, I could run step A one for all results before "branching" at step B (see #2 below). Similarly, I could branch again at step D if additional variations on step D are indicated (see #3 below).

**1) Base Process:**

```
input --> A --> B --> C --> D --> E --> result

```

**2) Modification of Step B:**

```
input --> A --> B1 --> C --> D --> E --> result1
                B2 --> C --> D --> E --> result2

```

**3) Modification of Steps B and D:**

```
input --> A --> B1 --> C --> D1 --> E --> result1
                             D2 --> E --> result2
                B2 --> C --> D1 --> E --> result3
                             D2 --> E --> result4

```

Is there a simple algorithm to determine the the common process steps and the branch points as in #3 given a base flow as in #1 and a list of steps to change, e.g.

```
Variation  StepB  StepD
   1         1      1
   2         1      2
   3         2      1
   4         2      2

```

The above example is simple but there could be hundreds of variations modifying dozens of different steps in actual usage.

# Answer
> 1 votes
If whatever happens after $B$ depends on that, you can't "reuse" any runs after a modified $B$. So the tree-like scheduling is really the best that can be done.

If the later steps are independent of (some) of the previous steps, things get more interesting... but that presumes you have a completely reliable way of determining that. The simplest way to get the most efficient runs *without* too much extra work in this case would be just to store away the results of all runs, and instead of running any of them first check if the result is already stored (memoisation). Might need to supplement with some logic to clean up (delete results that won't be used ever again, or use some heuristic to delete them).

---
Tags: algorithms, optimization, scheduling
---


# Question
Title: The exact relation between complexity classes and algorithm complexities
Are all algorithms which have polynomial time complexity belong to P class ? And P class do not have any algorithm which does have not polynomial complexity ?

Are all algorithms which have non polynomial complexity belong to NP or NP-Hard or both ?

I am just trying to understand the basic relationship.

# Answer
$P$ is defined as the class of (decision) problems that have an algorithm that solves them in polynomial time (in a TM, or a polynomially-equivalent model). Thus, $P$ contains exactly these problems, no more and no less.

As for $NP$- the situation is more delicate. A problem is in $NP$ if it has a nondeterministic algorithm that runs in polynomial time. An equivalent, more user-friendly definition, is that given a solution to the problem, you can verify it's correctness in time polynomial in the size of the problem. For example, given a graph and a path that claims to be a Hamiltonian, you can verify in polynomial time that it is indeed a Hamiltonian path. Thus, the problem of deciding if a graph has a Hamiltonian path is in $NP$.

Clarification: $NP$ is a class of *problems*, not of *algorithms*. An algorithm doesn't belong to $NP$.

Now, some problems are known not to have a polynomial time algorithm. This doesn't mean that they are in $NP$. In fact, some problems are known not to be in $NP$. For example, any $NEXP$-hard problem.

Regarding $NP$-hard problems - since we don't know whether $P=NP$ or not, we don't know if every problem outside $P$ is $NP$-hard. If $NP=P$, then every problem is $NP$-hard (except $\Sigma^\*$ and $\emptyset$).

This answer (which is by far incomplete) covers about 3 weeks of material in a basic complexity course. Perhaps consider thoroughly reading a textbook, such as Sipser's "Theory of Computation".
> 2 votes

# Answer
All algorithms that solve some decision problem in polynomial time show that their problems are in $P$. But there are certainly algorithms that don't take polynomial time for problems in $P$. You could sort by generating all $n!$ permutations of the input, and check each if it is sorted. That algorithm does take a more than exponential time, but the problem has a solution in polynomial time.
> 1 votes

---
Tags: complexity-classes, np, polynomial-time
---


# Question
Title: Time complexity of generating the first n primes and their product
Suppose that I have a turing machine that receives as input the string $1^{n\times n}$ (unary input), what is the time complexity of writing $p\_1,...,p\_n$ on the output tape, where $p\_i$ is the i-th prime number (written in binary)? And writing the first $n$ primes followed by their product (all written in binary)?

# Answer
Since the input is of length $n^2$, it makes sense that the TM must read it at least once (to learn the value of $n$), and we have a trivial lower bound of $\Omega(n^2)$. It is my understanding that what you actually ask is "*can we complete the task with $O(n^2)$ steps as well*"?

You suggest using the Sieve of Eratosthenes to mark primes. This is a clever idea. Indeed, a possible TM can run over the input. Each time it finds a `1`, it writes its index on the output tape ($p\_i$), and go through the input tape, zeroing any multiply of $p\_i$. Then it goes back to index $p\_i$ and repeat.

In order to know the index, we can assume the TM maintains a counter on the output tape (which is being "pushed" every time the TM outputs a new prime).

Now let's analyze the running time.

1. reading the input - $n^2$
2. For any prime we find (and we have $n$ of those:)
    1. mark the input tape according to the Sieve of Eratosthenes: we need to go through approximately $O(n\log n)$ numbers due to the density of primes \- $O(n\log n)$
    2. push the index and write the output - $O(\log n)$
    3. counting exactly $p^i$ steps between two indexes we zero - $O(n\log^2n)$
3. Multiplying all primes - $O(n^2\log^{1+\epsilon}n)$

so the naïve solution above takes $O(n^2) + n\times \[ O(n\log n) + O(n\log^2 n)\] + O(n^2\log^{1+\epsilon} n)= O(n^2\log^2n)$. In the above I assumed counting takes $O(n\log^2 n)$ since each step we need to subtract 1 from a $\log n$-long number, for every step in the sieve (which we bound to length $O(n\log n)$).

The time complexity of that algorithms is $O(n^2\log^2 n)$.

However, things can get better, as there are other ways of sieving. Assuming a multitape TM, the sieve of up to $k$ can be computed using $O(k/\log\log k)$ additions (thus, with $O(k\log k/\log\log k)$ bit-operations) by \[1\]. By setting $k=O(n\log n)$, we can compute the sieve with $O(n\log n)$ steps.

However, computing the multiplication of $n$ numbers (of length $\log n$) will take $n \times O(MUL\_{\log n})$ where $MUL\_k$ is the time to multiply two numbers of length $k$. According wikipedia, $MUL\_k \approx O(n\log n )$ <sup>\[2\]</sup>. This step alone is $\Omega(n^2\log n)$ and I don't see much hope to get complexity of $O(n^2)$.

---

<sub> \[1\]: A. O. L. Atkin and D. J. Bernstein, "Prime sieves using binary quadratic forms" (**free-access**), Mathematics of Computation 73 (2004), pp. 1023–1030.
\[2\]: ignoring the practically constant term of $2^{\log^\* n}$. </sub>
> 2 votes

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


# Question
Title: A Good Resource for Christofides' Heuristic
Is there an explanation Christofides's Heuristic for solving TSP which does not simply state the algorithm and go ahead to prove the bound?

To be specific: (Disclaimer : I am an engineer who knows very little about graph theory but need this for a logistics course)

* I understand that I first create an MST. So far, so good.
* Now, I need to find a perfect minimum weight matching on all odd degree nodes. I have no clue what this is; googling this tells me this is a set of edges containing maximum $n/2$ edges such that no node is shared by 2 sets. I don't see why I am doing this..... I am not even sure I understand what this statement means.
* Now, I need to merge the MST and the matchings to create a "multigraph" and then find an Eulerian tour on this. No clue what I am doing here.
* Run the shortcut algorithm exploiting the triangle inequality. (No clue what happened till now and this obviously then makes no sense either)

Can someone point me to a good resource with possible examples and illustrations for why Christofides works in a language that isn't full of graph theory terms (or alternately, provide me an answer here)?

I have already looked at :

# Answer
In the long run, it's really better to understand the graph theory terminology, but for now, here is an explanation of Christofides's algorithm. I'm not an expert in this area so I can't offer much by way of intuition. Also, I should note that by now, better algorithms are known for some variants, see for example the recent survey by Vygen.

We denote the sum of costs of a tour or of similar objects by $w(\cdot)$. Fix some optimal TSP tour $H$.

The starting point of the algorithm is a minimum spanning tree $T$. Why do we want a minimum spanning tree? Suppose that instead of a TSP tour, we're interested in a TSP path. A TSP path is a spanning tree, and while it is difficult to find an optimal TSP path, it's easy to find a minimal spanning tree. In the case of a TSP tour, we have $w(T) \leq w(H)$ as well.

If $T$ happens to be a path then, with some luck, we can get a good tour by completing it into a cycle. However, this need not be the case, and $T$ can be a complicated tree. Here we use a trick: Euler proved that every graph with even degrees can be traversed by an Eulerian circuit. While we wanted a tour and not just any circuit, this happens not to matter as we will see below.

How do we make $T$ into a graph with even degrees? The obstructions are the vertices with odd degree, so we'd like to pair them (there must be an even number of them since the sum of degrees in a graph is always even) as cheaply as possible. This is the minimum-weight matching you mentioned. We complete $T$ into an even-degree graph $T'$ by adding a matching $M$ on the odd-degree vertices, which is just a set of edges connecting pairs of odd-degree vertices. For obvious reasons, we want $M$ to have as minimal weight as possible, and such a matching can be found effectively. (As a special case, if $T$ is a path then $M$ connectes its two endpoints, and $T'$ is just a cycle.)

All vertices in $T'$ have even degree, so we can find an Eulerian tour $E$ working its way over all edges of $T'$. However, we wanted a Hamilton cycle (another name for a TSP tour). The idea now is to follow the Eulerian tour. Whenever we're supposed to visit a vertex we have already encountered, we just "skip" this edge. Eventually the tour will reach a new vertex, and then we just connect the previous vertex with the new one. The triangle inequality shows that the resulting TSP tour has weight at most $w(T') = w(T) + w(M)$.

Here is an example: suppose the Eulerian tour starts $a,b,c,a,d$. The constructed TSP tour will start $a,b,c,d$. The cost of the Eulerian tour is $w(a,b)+w(b,c)+w(c,a)+w(a,d)+\cdots$. The cost of the TSP tour is $w(a,b)+w(b,c)+w(c,d)+\cdots$. The triangle inequality shows that $w(c,d) \leq w(c,a)+w(a,d)$, i.e. if we take a detour from $c$ to $d$ via $a$, that can't be shorter than going straight from $c$ to $d$.

We already know that $w(T) \leq w(H)$. What about $w(M)$? Let $v\_1,\ldots,v\_{2k}$ be the set odd-degree vertices in $T$, in the order in which they appear in $H$ (starting at an arbitrary vertex and an arbitrary orientation). One possible way to match them is $M\_1 = (v\_1,v\_2),(v\_3,v\_4),\ldots,(v\_{2k-1},v\_{2k})$. Another possible way is $M\_2 = (v\_2,v\_3),(v\_4,v\_5),\ldots,(v\_{2k-2},v\_{2k-1}),(v\_{2k},v\_1)$. The triangle inequality (again) shows that the edge $(v\_i,v\_{i+1})$ costs at most as much as the entire stretch of $H$ from $v\_i$ to $v\_{i+1}$. Now imagine taking $M\_1$ and $M\_2$, and replacing each edge with the corresponding stretch of $H$. The result is all of $H$, and so $w(M\_1) + w(M\_2) \leq w(H)$. Since $M$ has minimum weight, $w(M) \leq w(M\_1),w(M\_2)$ and so $w(M) \leq w(H)/2$. Therefore $w(T) + w(M) \leq (3/2) w(H)$.
> 6 votes

---
Tags: algorithms, heuristics, graph-traversal
---


title: Finding the height of a d-ary heap

text:
# Question
Title: Finding the height of a d-ary heap
I would like to find the height of a d-ary heap. Assuming you have an Array that starts indexing at $1$ we have the following:

The parent of a node $i$ is given by: $\left\lfloor\frac{i+1}{d}\right\rfloor$

The $d$ children of a parent at node $i$ are given by: $di-d+1, di-d+2,\ldots di+1$

The height of a heap (which is slightly different than the height of a binary search tree) is a longest path from the root to a leaf. A longest path will always be from the last node in the heap to the root, but how do I calculate this longest path?

My first Idea is to setup a recurrence relation for the height of the tree:

\begin{equation} h(1) = 0\\ h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 \end{equation}

This seems overly-complicated and I feel like the answer is much more simple. Is there a better way to find the height of a $d-$ary heap?

# Answer
> 6 votes
A path from the last node to the leaf would always be a longest path. This is because the last node is always at the lowest level in the heap. Now, assume the root is at level $0$. Then the number of nodes at a completely filled level $i$ would be $d^i$.

Let level $k$ be the last completely filled level in the heap. So the number of nodes upto (and including) level $k$ is: $$\sum\limits\_{i = 0}^{k}d^i = \frac{d^{k+1} - 1}{d - 1}$$

Now, the last node - the $n^{th}$ node - can either be the last node at level $k$, or it can be in an incomplete level $k+1$. Taking care of these two cases, it can be seen that: $$\frac{d^{k+1} - 1}{d - 1} \le n \< \frac{d^{k+2} - 1}{d - 1}$$ $$\Rightarrow k\le \log\_d(n(d-1) + 1) - 1 \< k+1$$

Now, equality is only if the last node is the last leaf of level $k$, which also has distance $k$ from the root. If not, that is if there is a level $k+1$, then the $\log$ term would not be an integer, and applying the ceiling operator would give the right height of $k+1$. Thus, if the last element of the array is at position $n$, the height of the heap is: $$h = \lceil \log\_d(nd - n + 1) \rceil - 1$$ You can change the base of the logarithm using the change of base formula. Note that this is the same method that Yuval gives in his answer.

# Answer
> 1 votes
A different approach is to calculate the number of points $n\_d(h)$ in a saturated (maximal) $d$-ary heap of height $h$. Given $n\_d(h)$, the height of a $d$-ary heap of size $n$ is the minimal $h$ such that $n\_d(h) \geq n$. Given the formula for $n\_d(h)$, you should be able to find $h$ explicitly.

---
Tags: data-structures, recurrence-relation, heaps
---


# Question
Title: What are some problems which are easily solved by human brain but which would take more time computers?
Are there any problems which can be solved by human brain in a very less time but a computer may take a lot of time or a computer could never solve it ?

# Answer
The now standard simple example of this is CAPTCHAs which stands for "Completely Automated Public Turing test to tell Computers and Humans Apart" which was intentionally devised in the theoretical community partly to detect and deflect automated spammers. However, the technology can be subverted somewhat by some systems such as mechanical turk. The term "CAPTCHA" was coined in 2000 by Luis von Ahn, Manuel Blum, Nicholas J. Hopper, and John Langford (all of Carnegie Mellon University). CAPTCHAs have gotten increasingly visually complex over the years as computer algorithms for character recognition have improved, in other words its evolving and something of a red queen race, i.e. evolutionary "arms race".
> 2 votes

# Answer
Language processing.

Every kid learns how to use language within his first 1-3 years. Computers still don't understand simple language structures, not to mention ambiguity, sarcasm, subtleties, etc.
> 5 votes

# Answer
Facial recognition. Human does better and quicker here than computers.
> 2 votes

# Answer
If you consider **computability**, human brain is **not stronger than Turing machine**. Turing machine could have infinite memory (arbitrarily extendable tape) while our memory is not (limit in storing information).

But in some current applications it seems human brain works better according to performance than current computers like Natural language learning, Image/Voice recognition,...
> 1 votes

# Answer
Von Neumann suggested his famous computer architecture as a way to simulate the laws of (classical) physics. Furthermore, it was shown that these laws can be simulated efficiently.

If you believe that the human brain works under the constraints of classical physics (also, to an extent, under quantum physics), then the brain is no stronger than a Turing Machine.

In this sense - no, the brain cannot do anything that a computer can't.

You may want to read this.
> 0 votes

---
Tags: algorithms, artificial-intelligence, computer-vs-human
---


# Question
Title: Lossless data compression must make some messages longer?
I read on Wikipedia and in lecture notes that if a lossless data compression algorithm makes a message shorter, it must make another message longer.

E.g. In this set of notes, it says:

> Consider, for example, the 8 possible 3 bit messages. If one is compressed to two bits, it is not hard to convince yourself that two messages will have to expand to 4 bits, giving an average of 3 1/8 bits.

There must be a gap in my understand because I thought I could compress all 3 bit messages this way:

* Encode: If it starts with a zero, delete the leading zero.
* Decode: If message is 3 bit, do nothing. If message is 2 bit, add a leading zero.
* Compressed set: 00,01,10,11,100,101,110,111

What am I getting wrong? I am new to CS, so maybe there are some rules/conventions that I missed?

# Answer
You are missing an important nuance. How would you know if the message is only 2 bits, or if it's part of a bigger message? For that, you must also encode a bit that says that the message starts, and a bit that says it ends. This bit should be a new symbol, because 1 and 0 are already used. If you introduce such a symbol and then re-encode everything to binary, you will end up with an even longer code.
> 7 votes

# Answer
I think you should consider the (binary) messages of length **up to** a certain value, say $n$. Then you have $2^{n+2}-1$ messages, which you have to map onto the same $2^{n+2}-1$ messages, if you don't permit "compressed" messages with more than $n$ bits. In other words, your compression is a permutation $f$. Any word $w$ with $|f(w)| \< |w|$ is in a cycle of $f$, which contains another word $w': |f(w')| \> |w'|$.
> 4 votes

---
Tags: data-structures, data-compression
---


# Question
Title: How is the following ML Curry expression evaluated
This question is not homework but it's related to material in a general course I take about programming languages, so I don't know whats the site policy about this

In ML the following expression:

```
fun f x y z = x (y , z) = x (z, y) ;

```

Evaluates to this:

```
val ('a, ''b) f = fn : ('a * 'a -> ''b) -> 'a -> 'a -> bool

```

I understand the type inference done here, but not the structure of the expression returned.

Can someone explain how this works ?

Thanks

# Answer
> 3 votes
It seems that what you are confused about is the common practice of *Curryfication*: the function $$ (\alpha\times \alpha\rightarrow \beta)\rightarrow \alpha\rightarrow \alpha\rightarrow \mathrm{bool} $$

Is parenthesized as:

$$ (\alpha\times \alpha\rightarrow \beta)\rightarrow (\alpha\rightarrow (\alpha\rightarrow \mathrm{bool})) $$

and is equivalent to a *different* function: $$ (\alpha\times \alpha\rightarrow \beta)\times \alpha\times \alpha\rightarrow \mathrm{bool} $$

The reason for this is the following. Take a function:

$$f:A \rightarrow (B\rightarrow C)$$ This is a function that takes an element $a:A$ and returns a function $$ f\ a: B\rightarrow C$$ Apply this to an element $b:B$ and you have $$f\ a\ b:C$$

It is clear that this is equivalent to a function $f':A\times B\rightarrow C$ that takes a *pair* $(a,b):A\times B$ and returns an element of $C$. The equivalence can be explicitely written:

```
curry : ('a * 'b -> 'c) -> ('a -> 'b -> 'c)
curry f' = function x -> function y -> f' (x,y)

```

or more simply

```
curry f' x y = f' (x,y)

```

The other direction goes:

```
uncurry : ('a -> 'b -> 'c) -> ('a * 'b -> 'c)
uncurry f = function p -> let (x,y) = p in f x y

```

or simply

```
uncurry f (x,y) = f x y

```

---
Tags: programming-languages, functional-programming, typing
---


title: Algorithm for graphically spacing items

text:
# Question
Title: Algorithm for graphically spacing items
**I am developing a chart and graph library and am having trouble developing an algorithm.**

\**This is not a homework assignment for a student. See my open source project: https://github.com/eddieios/CoreChart

The algorithm is to space the Y axis labels in a given coordinate graphical space. It should space the labels at about 50 pixels apart, but have no less than 5 labels. All data points are assumed to be positive integers. The labels should be multiples of 5 (so as to have nice clean numbers). The last label can be smaller or larger than the maximum possible value, but it should be the closer of the two. The algorithm inputs are 1) the maximum possible value from the chart data, 2) the height of the graphical space. The output is a list of labels and their vertical positions.

For example:

* Maximum possible chart value = 79
* Height of graphical space = 200

Output would be:

* Label: 0, Vertical Position: 0
* Label: 20, Vertical Position: 50
* Label: 40, Vertical Position: 100
* Label: 60, Vertical Position: 150
* Label: 80, Vertical Position: 200

I have written the following code (Obj-C). But I'm having trouble handling end-cases. For example, if the maxValue = 39, then the labels are set 5 apart. The optimal case here would be to set labels 10 apart. There's something about I'm deciding how many labels there should be that isn't working for all cases.

```
int maxValue = 39;
float graphHeight = 259.0f;

int numLevels = (int)(graphHeight / 50.0f);

float offset = (int)(maxValue / (float)numLevels);
offset /= 5;
offset = (float)((int)(offset + 0.5));
offset *= 5;

CGFloat stepY = graphHeight * ((float)offset/maxValue);

for (int i = 0; i <= numLevels; i++) {
    NSLog(@"label %f position %f", i*offset, i*stepY);
}

```

# Answer
> 2 votes
One possible approach which does not require any hairy arguments is to come up with a "nicety" measure, find a range of offsets, and choose the best one. Usually rounding errors are accounted for by taking a $\pm 1$ (in your case $\pm 5$) modification from the starting point. In your case, you would calculate the nicety measure for both $5$ and $10$, and if your nicety measure is reasonable, choose $10$ over $5$.

---
Tags: algorithms
---


title: Formulas vs Circuits

text:
# Question
Title: Formulas vs Circuits
In boolean circuit complexity, a circuit is just defined by a Directed Acyclic Graphs with designated input and output nodes, where the intermediate nodes compute a specific boolean function. A circuit is called a formula if the underlying graph is a tree. i.e., the fan-out of each node is $1$. Is it true that for a formula, (given that its fan-out is already $1$, by defintion) the fan-in is also constant?

In the usual definition of formulas, this is never spelt out(Its always defined as a circuit where all gates have fan-out $1$). But somehow I seem to carry around this intuitively that formulas are always bounded fan-in. (It might be partly due to the fact that poly-sized boolean formulas correspond to $\mathsf{NC^1}$ which is a complexity class defined by bounded fan-in circuits of logarithmic depth).

So my question is, if you bound the fan-out of the circuit to be $1$, does it imply even the fan-in should be constant for every gate? I tried to use a counting argument, that says that the indegree and outdegree of the graphs must sum to the same, but somehow a water tight proof eludes me. First of all, is my intuition correct?

# Answer
> 7 votes
No. Take for example $\mathsf{AC^0}$. It is polynomial-size bounded-depth circuits. Being DAG or tree doesn't change the class. The fan-in can be arbitrarily large.

If the fan-in is bounded we end-up with $\mathsf{NC^0}$ which is much weaker. It cannot compute any function where the output depends on more than a bounded number of inputs as each gate with at least two inputs will decrease the number of usable wires by one and there is no way of increasing them.

Note also that the number of gates (ignoring single input gates like negation) in any circuit with $n$ inputs and with fan-out $1$ is going to be at most $n-1$.

# Answer
> -1 votes
Fan-in in a circuit tree or a formula (i.e. outdegree $= 1$ as you mention) is limited by the number of input variables. A node or a gate cannot connect to more than the input variables. However, note that often in many constructions, the indegree is limited to 2, and gates are combined using the simple rule $a \wedge b \wedge c$ = $(a \wedge b) \wedge c$, and similarly for all typical or associative gates. In other words, "unlimited" indegree is converted to 2-indegree with a small increase in gates.

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


# Question
Title: Process graphs and finding infinite processes
I am reading on concurrent processes and algorithms which find infinite processes by searching the process graph recursively.

Most of the material I have found is not for beginners. I am looking for references / algorithms that can help me understand:

1. What are process graphs?
2. How to search for infinite processes in these graphs?

Thanks in advance

# Answer
> 2 votes
As you propably know, a process (in terms of process algebra like CSP) can consume an input and will the behave like another process (unless it is a process that does not accept input, usually called STOP).

You can construct a graph where the nodes are the processes and the outgoing edges the input that the node can consume, directed to the node (process) that gives the new behaivior. If such a graph contains a directed path back to a starting node (i.e., a circle), you have an infinite process.

Finding a circle in a graph is a standard problem in graph theory and is usually done by DFS.

A good introduction to CSP is Tony Hoare's Book on that subject, what is easy to read also for beginners. (However, Hoare does not use the term "process graph" but talks only on "graphs".) The standard text book for CCS is Milner's "Communication and Concurrency" published by Prentice Hall.

---
Tags: reference-request, concurrency, process-algebras
---