# Question
Title: Which language families admit inductive definitions?
I am self-learning about formal languages. I learned that the family of the regular languages can be defined inductively, in terms of the operations they are closed under (namely the smallest fix-point). This definition doesn't rely on regular grammars or finite state machines.

I wonder which other families of formal languages can be defined inductively; in particular, I am interested in the classic classes of the Chomsky hierarchy but also the (semi-)decidable languages.

# Answer
We can study families of languages in terms of their closure properties, it then makes sense to consider languages which generate the family under those closure properties.

Some work in this area has been done (particularly for cones/AFLs) and there may be known results for some or all of the families of languages that you mention but the only result which I know off the top of my head is for the context-free languages:

The context-free languages are the smallest cone generated by the Dyck language on two symbols.

For a proof of this theorem and some similar results for other language classes within context-free see Berstel's book which is now freely available on his website here.
> 4 votes

# Answer
the recursively-enumerable languages are literally ***recursively*** *enumerable*. this was proven originally mainly with the Lambda calculus which has a 1-1 correspondence with recursively enumerable languages. in other words all legal Lambda Calculus expressions (which can be defined as a closed set of recursive construction operations) correspond to the recursively enumerable languages. all other languages you list are a subset of recursively-enumerable so therefore also can be generated recursively.
> 1 votes

---
Tags: formal-languages, reference-request
---


title: Conditional RB Tree union

text:
# Question
Title: Conditional RB Tree union
**Input:** 2 RB Trees A B, so that both values in a certain range, so that B's range is smaller than A in both sides. Ex. B's range can be \[100...200\] and A's range is \[0...1000\]
**Output:** Unite A and B to one RB Tree AB.

How can I unite these 2 trees in $O(log(n))$ time and with additional space $O(1)$?

I have tried splitting tree A into 3 trees A1,A2,A3, so that: A1 \< A2 , B \< A3
A2 contains all that values that are equal-bigger than Min(B) and smaller-equal to Max(B). I did it using the RB Tree Split algorithm, and all the splitting sums up to $O(log(n))$ time.

Now I know what to do with A1 and A3 but what should I do with A2 and B? I know I should use the fact that **B contains A2's range** but how does it help me?

# Answer
> 3 votes
You can't. As shown by Brown and Tarjan on the first page of "A Fast Merging Algorithm", merging two sequences with overlapping ranges has a worst-case bound of $\Theta (m \lg (n/m))$ comparisons.

---
Tags: algorithms, graphs
---


# Question
Title: Finding all (weighted) cycles through a given vertex
For a connected undirected graph $G$, given a particular vertex $v$, is there a known (efficient) algorithm to find all simple cycles in $G$ that contain $v$?

In my case, I have weights for every edge. Ideally I'd like to be able to compute, for every $v \in V(G)$, the product of the edge weights over all cycles that go through $v$. Doing this to some level of approximation would still be very helpful.

Is this a known result? Any pointers would be very helpful.

# Answer
> 3 votes
## Enumerating all cycles might take exponential time

There cannot be any efficient algorithm for enumerating all cycles that contain $v$. There could be exponentially many algorithms that go through $v$. Therefore, any algorithm for enumerating all cycles could potentially take exponential time.

If the graph is very small and efficiency is not important, you could enumerate all cycles that go through $v$ using depth-first search or breadth-first search starting from $v$. Or, you could use Johnson's algorithm: see Find the Simple Cycles in a Directed Graph.

## You can't compute the cycle-sums you want efficiently

Now for some more bad news. You want to compute the sum over all simple cycles, of the sum of edge-weights in the cycle. Unfortunately, this cannot be done efficiently, either. This problem is #P-hard, which means there is no hope for a polynomial-time algorithm for it.

Here's a proof of #P-hardness, by reduction from the problem of counting the number of simple paths from $s$ to $t$ (which is a #P-complete problem). Let $G$ be a graph, and vertices $s$ and $t$ be specified. Add new vertices $u,v$ and edges $(t,u)$, $(u,v)$, and $(v,s)$. Label each edge with the weight 0, except that the edge $(u,v)$ will be labelled with weight 1. Now suppose you had an efficient algorithm to compute the sum over all simple cycles, of the edge-weights in that cycle, for the resulting graph. Then its output would be exactly the number of simple cycles in this graph, or equivalently, exactly the number of simple paths from $s$ to $t$ in $G$. Thus, any polynomial-time algorithm for your problem would immediately imply a polynomial-time algorithm for counting the number of simple paths from $s$ to $t$; since the latter is #P-hard, your problem must be #P-hard, too.

For more details on #P-hardness of counting simple paths, see, e.g., https://cstheory.stackexchange.com/q/20246/5038, https://stackoverflow.com/a/5570751/781723, How hard is counting the number of simple paths between two nodes in a directed graph?.

So, the bad news is: there is no efficient algorithm for your problem, and I can prove it.

Time to look for some alternative: e.g., find some way to avoid solving your problem, or hope that your graph will be extremely small (so that exponential-time algorithms are acceptable), or look for an approximation algorithm, or something. But you're not going to find an algorithm to solve your problem that is efficient on general graphs.

## Other miscellaneous comments

It's important to phrase your question so you ask for what you *really* want. It sounds like what you *really* want to know is whether it's possible to compute the sum of the edge weights over all cycles that go through $v$. If that's what you really want, don't ask whether it's possible to enumerate all cycles through $v$; ask whether there's an algorithm to do what you really want. There might be a better way to do what you really want, without enumerating all cycles.

(Incidentally, if you are summing over all cycles of any length, it is important to restrict your sum to simple cycles. If you don't restrict to simple cycles, then there are infinitely many cycles and the sum is going to be either $+\infty$ or $-\infty$.)

---

For instance, it *is* possible to efficiently compute the sum of the cycle weights over all cycles of length $k$ (not necessarily simple) that go through $v$, where the weight of a cycle is the *product* of the edges in $v$. Here's how.

Here's the key idea. Let the matrix $M$ represent the adjacency matrix for the graph, i.e., $M\_{i,j}$ holds the weight on the edge $(i,j)$, or $0$ if there is no such edge. Let $e\_i$ denote the vector that is $1$ in its $i$th component and $0$ in all other positions. Let $x = M^k e\_v$. Then $x\_j$ is a sum, over all paths from $v$ to $j$ of length $k$, of the products of the weights along each such path. Thus, $x\_v$ is a sum of the weights of all of the cycles of length $k$ that go through $v$. The running time is polynomial.

Unfortunately, this is not restricted to simple cycles, so it is not what you want. Also, this approach ends up multiplying the edge weights along a single cycle, rather than adding them, so it is also not what you want for that reason. Nonetheless, it shows how some problems of this form can potentially be solved in polynomial time *without* enumerating all cycles.

---
Tags: algorithms, graphs
---


title: Real life description for (~A->A)->A

text:
# Question
Title: Real life description for (~A->A)->A
It can be shown that the logical preposition \[ :- (~A-\>A)-\>A \] is a theorem (always true). I want to know if anybody knows a real life description for the preposition above? I mean an expression in computer, economics, mathematics, politics or anything that fits in that preposition.

# Answer
> 4 votes
Since $A$ is always the same atomic statement, every direkt translation is going to be weird. Also, natural language does not do well with (nested) implications; we typically say "leads to" not "logically implies" in reality.

I suggest you transform the formula to

$\qquad\begin{align\*} &(\lnot A \to A) \to A \\ \equiv &\lnot(\lnot A \to A) \lor A \\ \equiv &\lnot(A \lor A) \lor A \\ \equiv &\lnot A \lor A, \end{align\*}$

which is, of course, a tautology (as you've stated):

> You will help me, or you won't \[, your choice\].

Coming up with more complicated sentences won't give you more (logical) meaning -- all tautologies are equivalent (in Boolean logic), after all.

# Answer
> 4 votes
Although all tautologies can be rewritten into "true", several of them are known since classic times under specific names. After all philosophers had to learn and analyse the type of arguments they were using.

With the help of google I managed to find this proposition you refer to. It is known as "Clavius's Law" or "Consequentia mirabilis".

# Answer
> 3 votes
This isn't an answer to your question, but an observation. The reason why you're having trouble thinking of a real-life example is that it's a theorem in classical Boolean logic, but not in a general topos or intuitionistic/constructivist logic.

Many theorems are of the form $P\_1,P\_2\ldots P\_n \vdash Q$. Given preconditions $P\_i$, you can conclude that $Q$ is true. For example, if you have a right-angled triangle and have constructed squares on all three sides, then the area of the square on the hypotenuse... you get the idea.

Moreover, many proofs are *constructive*, in that they specify a procedure for obtaining the "thing" which is the subject of the conclusion from the objects given in the premises.

A constructive proof can be thought of as a computer program which takes premises as inputs and produces a conclusion as an output. This is not just an analogy, by the way. The correspondence between programs and proofs can be made completely rigorous, but the details are beyond the scope of this answer.

The logic which specifies these kinds of proof is called *constructive logic* or *intuitionistic logic*. It is, in a sense, a subset of classical logic, because some theorems in classical logic are not theorems in constructive logic.

You can think of:

$$\vdash\_{Bool} P$$

as asserting that $P$ is true, but

$$\vdash\_{Con} P$$

as asserting that you can formally construct an example of $P$ being true.

An example of a statement which is true in classical logic but not in constructive logic is $\lnot \lnot A \rightarrow A$. Just because you can't construct a refutation of $A$ doesn't mean you can construct a proof of $A$. Note that the converse, $A \rightarrow \lnot \lnot A$, is a theorem; a construction of $A$ is also a construction that $A$ is impossible to refute.

(An analogy that often comes up is that if it's raining, then it's not impossible that it's raining. But just because it's not impossible that it's raining doesn't mean that it *is* raining. It's a good analogy, but don't stretch it too far.)

Raphael's proof above requires double negation elimination to be a theorem, because it simplifies $\lnot A \rightarrow A$ to $A \vee A$. In intuitionistic logic, it "simplifies" to $\lnot \lnot A \vee A$, and from this you can't necessarily conclude $A$.

(Note: The word "simplifies" is in scare quotes because in intuitionistic logic, implication is just as basic a concept as conjunction or disjunction, and arguably moreso. This is beyond the scope of this discussion.)

So the reason why you had difficulty thinking up an example is that it's harder to think up non-constructive examples than constructive examples, and this theorem doesn't have a constructive proof.

# Answer
> 2 votes
Here's a somewhat contrived example: a failed proof that the Halting Problem is undecidable.

**Step 1**. Suppose we could build a halt tester $H$ that acts as follows:

* $H$ takes as input a description, $\langle M\rangle$, of a TM $M$ and a word $x$.
* If $M$ halts on $x$, $H$ will halt and return "true".
* If $M$ doesn't halt on $x$, the behavior of $H(\langle M\rangle, x)$ is unspecified, except that it won't return "true".

**Step 2**. Use $H$ to construct a TM $P$ which acts as follows:

* $P$ takes a TM description $\langle M \rangle$ as input
* $P$ then runs $H$ on input $(\langle M\rangle, \langle M\rangle)$.
* If $H(\langle M\rangle, \langle M\rangle)$ returns "true", $P$ enters an infinite loop.

So, the action of $P(\langle M\rangle)$ will be as follows:

> If $M$ halts on input $\langle M\rangle$, then $P$ will not halt on input $\langle M\rangle$.

Now give $P$ its own description, $\langle P\rangle$. By the specification above, the action of $P$ will be:

> If $P$ halts on input $\langle P\rangle$, then $P$ will not halt on input $\langle P\rangle$.

Consequently, we can't have the case where $P(\langle P\rangle)$ halts, so to avoid this contradiction we must conclude that $P(\langle P\rangle)$ doesn't halt.

Now let $A=\`\`P(\langle P\rangle)\text{ halts''}$. We've just shown that $$(A\rightarrow \neg A)\rightarrow\neg A$$ which is your original tautology, with the terms negated.

---

If you've gotten this far and are still interested, the correct proof that the Halting Problem is undecidable relies on using a different machine $H$ to make a different $P$ such that $P(\langle P\rangle)$ halts **if and only if** $P(\langle P\rangle)$ doesn't halt. We didn't reach this contradiction here since in step 1, $H$ wasn't built to be a decider, but rather a recognizer. In fact, the program $H$ we used here is quite possible to build: it would just simulate the action of $M$ on input $x$ and if it halts, would return "true".

# Answer
> 1 votes
As noted by others, essential uses of classical logic look weird to normal people, unless it's exactly the law of excluded middle. It's easier to explain the classically equivalent, but intuitionstically valid $(A \to \lnot A) \to \lnot A$:

> Look, if we assume $A$ holds it follows that $A$ does not hold. So how could $A$ hold?

It does indeed seem hard to come up with a real-world example.

---
Tags: logic, intuition, propositional-logic
---


# Question
Title: To show that a graph-problem is in $L$ or $NL$
Consider the following problem:

$$A=\left\\{ (G(V,E),s,t)\mid\text{conditions 1, 2, 3 and 4 hold} \right\\}$$

1. $G$ is a directed graph.
2. $s,t\in V$.
3. There is a simple path from $s$ to $t$ (a simple path is a path that visits every vertex not more than once).
4. $\forall v\in V: \deg^+(v)\leq 2$ (in words: every vertex in $V$ has outdegree at most 2).

Out of the following classes: $\mathsf{L,NL,P,NP,co-NP,EXP}$, I need to determine what is the smallest class (with respect to inclusion) that has $A$ in it.

My idea is: since every vertex has outdegree at most 2, I can write a function $F$, s.t for every $v\in V$ I'll recursively call $F$ with the two adjacent vertices of $v$.

The termination condition will be either if $\deg^+(v)=0$ (we've reached a leaf node) **or** $v$ has alredy been visited (this will make sure the path is simple) **or** $v=t$ (we've found a path to $t$), thus concluding that $A\in P$ (the complexity of the described algorithm is $n\log n$).

I'm just not sure if that is the best that can be done. Can it be shown that $A$ is in $\mathsf{L}$ or $\mathsf{NL}$?

# Answer
> 5 votes
The problem is NL-complete.

The fact that it's in NL, as stated in the comments, follows from the fact that this problem is a restriction of the reachability problem for directed graphs.

To see that it's NL-hard, we can reduce from the reachability problem:

Consider a graph $G=(V,E)$ and vertices $s,t$. We transform $G$ to a graph $G'$ with out degree at most $2$, as follows.

For every vertex $v$ with out-neighbors $u\_1,...,u\_k$ ($k\ge 3$), construct vertices $v\_1,...,v\_{k-1}$ where there are edges from $v\_i$ to $u\_i$ and to $v\_{i+1}$. The incoming edges to $v$ are now directed to $v\_1$, and $v$ is removed.

It is not hard to see that there is a path from $s$ to $t$ in $G$ iff there is a path from $s\_1$ to $t\_1$ in $G'$. Also, this reduction can be implemented in log-space. Thus, your problem is NL-complete.

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


# Question
Title: Does the AND-compression of SAT depends on the number of SAT instances?
From a paper

> An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances $x\_1,\dots,x\_t$ to a single SAT-instance $y$ of size $poly(\max |x\_i|)$ such that $y$ is satisfiable if and only if all $x\_i$ are satisfiable.

My question is: Is $t$ treated as constant?

Another paper gives related definition, explicitly stating that the *strong* AND compression must be independent of $t$. .

# Answer
> 3 votes
Let me help you determine how you would answer your own question.

The way is to read the paper, and in particular, look at the theorems and the definitions of the notation and the assumptions. Don't just read the abstract. You have to read the whole paper.

For instance, you can look at Theorem 1.1, noticing the phrase "...for some $n$ and $t$..." -- to me, that suggests that $t$ is a constant in Theorem 1.

Or, you could look at Theorem 3.1, which explicitly mentions that $t$ is polynomial in $n$, where $n$ is the length of the SAT-instances, in the context of Theorem 3.1.

It's also often helpful to go back to the original paper that introduced the conjecture, and see how they formulated it. In this case, you can learn (from reading the introduction to the paper you link to) that Bodlaender \[2\] was the originator of the conjecture, and Fortnow and Santhanam \[3\] proved the conjecture under a certain assumption. The paper you link to (the Dell paper) might be assuming papers have read those prior work and are familiar with the technical details of the formulation of the conjecture. So, go read those papers, too.

Bottom line: you can't stop at reading just the abstract or just the first sentence of the introduction. You may have to dive into the details, and even into prior papers, to resolve questions like this. These papers are written for other researchers (who are comfortable doing all that).

---
Tags: satisfiability
---


# Question
Title: Counting the number of instructions in an instruction set
> An imaginary processor has the following hardware specification:
>
> * 8bit data bus
> * 12bit address bus
> * 32 × 8bit general purpose registers e.g. `S0``S1F`
>
> Briefly describe what bit fields are required within an instruction to encode the following functionality:
>
> 1. 56 different instructions
> 2. Register addressing e.g. `ADD S0, S1`, add the contents of register `S1` to register `S0`, store the result in register `S0`.
> 3. Immediate addressing e.g. `ADDI S0, 10`, add the constant 10 (base 16) to register `S0`, store the result in register `S0`.
> 4. Absolute addressing e.g. `ADDA S0, 100`, add the data stored in external memory address 100 (base 16) to register `S0`, store the result in register `S0`
> 5. If the processor uses a fixed length instruction format, briefly describe how many bits are required to represent an instruction and the bit fields used.

For (1), I know it's $\log\_2 56$ round up to 6 bits but for (2), I know the answer is 6bits+5bits+5bits, but I can't figure out why.

# Answer
An "add" instruction (e.g., ADD S0 S1B) must have 3 parts of information:

1. which instruction to do ("ADD")
2. Which is the input register (S0)
3. Which is the output register (S1B)

How many bits does each part take? Well, you correctly answered that the first part is 6 bit. Can you see why the second and third parts take 5 bits each?

For the other parts of the question, try to split to the information the instruction must have, and analyze the amount of bits each part takes, under the definitions of the specific machine in use.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: Non Turing-Recognizable from symmetric difference
I have a question about how you would find a example of a non Turing-recognizable language from the symmetric difference of two Turing-recognizable languages. I believe this is possible, but I am having problems coming up with a example in my head. Does anyone have any hints, or ideas about how to think about this?

# Answer
(Converting the comment hints and guidance into an answer)

If you take $A$ to consist of all strings, $A=\Sigma^\*$, then $A$ is decidable and recognizable. Then, we will take the second language, $B$, to be recognizable but not decidable.

Their symmetric difference will give us (by definition) $\overline B \triangleq \Sigma^\* \setminus B$.

Now, let's get concrete. The halting problem, $HP$, is a recognizable non-decidable language. If we take $A=\Sigma^\*$ and $B=HP$, then their symmetric difference is $\overline {HP}$. The last step is to show that $\overline {HP}$ is not-recognizable (but this is a very well known fact that $\overline{HP}\in coRE$ and not-recognizable, since if it was recognizable, then $HP$ would have become *decidable*, since for any input we would have a machine that says "yes" if it is the language, and another machine that says "no" if it is not).
> 1 votes

---
Tags: computability
---


title: How to Study Space Complexity

text:
# Question
Title: How to Study Space Complexity
I am working through Sipser, and I am trying to understand some of the algorithms described in Space Complexity, but I am having a hard time understanding the presentation of the material (especially Savitch's theorem). I have a very strong intuition for time complexity, but I don't understand how space complexity fits into a heirarchy of time complexity, and I think it has to do with the fact that it is all discussed in terms of Turing machines. It is hard to see how space and time are related when I'm wasting time untangling convoluted algorithms described in terms of Turing machines.

Does anyone have any advice on how to think about Turing machines vis-a-vis contemporary computation in general? It is unintuitive to think about algorithms in terms of input strings, tapes, and machines simulating machines. I don't feel like I am leveraging my existing knowledge of computers and programming to more deeply understand the proofs and algorithms being presented.

I think I just need help understanding how space varies based on the data structure of the input. For some input of size $n$, are the bits required to represent each entity of the input negligible? Say our language is a set of objects that are all of a certain type, and each object is massive. How does space usage vary vs. a similar language with very small objects?

Edit: I understand now that space complexity fits in with time complexity because they are both *resources* used to determine whether some string is a member of a language; Or in other words, whether some element belongs to a particular problem (see here).

# Answer
> 3 votes
Space Complexity measures the amount of space it takes to carry out a specific task (as a function of the input size). It is very similar to time-complexity, that measures the amount of time it would take to complete the task. In both cases, the complexity highly depends on the specific *model* of machine (RAM machine is faster than a double-tape Turing Machine, which is in turn faster than a single-tape Turing Machine).

Let's now focus on a specific simple model: Single-tape TM.

### Example: Sorting

Consider a simple task: say, sorting. The input is a list of numbers $x=\\{a1, a2, ...\\}$ and the machine should write them in order. The size of the input is $|x|=n$.

One way to perform this task on a single-tape Turing machine, is to perform a Merge Sort: we look at the first number $a1$, split the list into two list, one for numbers that are larger than $a1$ and the second list with the other numbers (and then we repeat it recursively).

But how do we implement "spitting the list into two" on a single-tape TM? A possible solution will mark the end of the input, then go over the list $n$ times, and every time it finds a number that should be on the second list, it will move it to the end of tape. So, if we started with $n$ numbers, now we have a list of $2n$ places (some of which will be empty, since we "moved" the numbers to somewhere else). If we continue with this naive approach, we will keep increasing the space in use more and more, and will get a very large space complexity (say $n^2$ if we stupidly double the space at each phase of the recursion).

But there is a more efficient way to do it: after creating two lists, we can "close the empty gaps" that occurred when we moved elements. Since we never add or remove elements, the same amount of space we started with is always big enough to keep the intermediate lists. For this approach we might need to maintain some counters that will tell us where each list begins and ends. Using smart methods, this can be done very efficiently, so that we will never use more than $\approx 2n$ cells of the tape. That is, the space complexity is $O(n)$ in this case. (see also In-place merge sort, which is not exactly what I was talking about, but might give you more intuition)

Now you can also see that Space and Time are related. If we perform the space-efficient variant, the TM needs to do some extra-work of "closing gaps", marking start and end points, keep track of counters, etc. This extra work takes time. It is very common that there is a *tradeoff* between space and time: if the algorithm is very fast, it takes a lot of memory, and if it is very space-efficient then it takes more time. For the task of sorting, see a table comparing the time and space complexity of various sorting algorithms. (Note that in that table they count the space complexity excluding the input).

### Space complexity and its relation to Time complexity

So now we can define the space complexity of "sorting" as the **minimal** space it takes to sort. That is, take the most-efficient (memory-wise) sorting algorithm. How much space does it take to sort $n$ elements? This is the space complexity of sorting.

More generally, we can define classes of tasks that take the same space complexity. For instance $DSPACE(n)$ contains all the tasks that can be solved using $O(n)$ memory. Said differently, it contains all the tasks whose space-complexity is at most $O(n)$

There is a strict hierarchy here: If we know that a task needs $O(n)$ space, it clearly cannot be in $DSPACE(1)$. More accurately, for any function $f(n)$, $$ DSPACE( o(f(n)) \subsetneq DSPACE( f(n)).$$

Finally, we can relate time and space: $$DTIME (f(n)) \subseteq DSPACE(f(n)),$$ since in $x$ time we can access at most $x$ cells of the tape. More interestingly, we know that
$$DSPACE(f(n)) \subseteq DTIME(2^{O(f(n))}).$$ That is, whatever task that we can solve using $x$ bits of memory, we can also solve using in at most $2^{O(x)}$ time-steps. This follows since a machine with $x$ memory has maximal number of $2^{O(x)}$ different configurations, so if it doesn't go into an infinite loop it must end in less than $2^{O(x)}$ time.

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


# Question
Title: What is the significance of the vector dimension in semidefinite programming relaxations?
Let's say that we want to design a semi-definite programming approximation for an optimization problem such as MAX-CUT or MAX-SAT or what have you.

So, we first write down an integer quadratic program that solves the problem exactly. For example, in the case of MAX-CUT we would write: $$ \max \sum\_{\\{u,v\\} \in E}{\frac{1 - x\_u x\_v}{2}} $$ $$ x\_v \in \\{-1,+1\\}. $$

Then we relax the program by allowing the variables to take on vector values in the sphere $S^{n-1}$, and replacing products with scalar products, obtaining a semi-definite program that can be solved precisely.

Our approximation proceeds by solving the SDP and rounding the solution to obtain a legal solution for the original problem whose distance from the SDP solution can be bounded.

My question is: **What is the importance of the dimension of the vectors?** In all the cases I have seen, the analysis would stay the same if we assume that the vectors are all unit vectors in $\mathbb{R}^2$. So why do people always take vectors in $S^{n-1}$?

# Answer
> 4 votes
Vector programs are solved by solving semidefinite programs. The basic idea is that if $v\_1,\ldots,v\_n$ are vectors, then the matrix $V\_{ij} = \langle v\_i,v\_j \rangle$ is positive semidefinite: $$ \alpha' V \alpha = \sum\_{i,j} \alpha\_i \alpha\_j \langle v\_i, v\_j \rangle = \left\\|\sum\_i \alpha\_i v\_i\right\\|^2. $$ The converse is also true: a positive semidefinite $n \times n$ matrix $V$ of rank $r$ can be written as $V = LL'$, where $L$ is $n \times r$ (this is known as the Cholesky decomposition). Furthermore, $L$ can be found effectively given $V$. If $\ell\_1,\ldots,\ell\_n$ are the $r$-dimensional rows of $L$, then $V\_{ij} = \ell\_i \ell'\_j = \langle \ell\_i, \ell\_j \rangle$. We can therefore optimize a vector program involving inner products of vectors $v\_i$ by solving a semidefinite program. Rank constraints are not convex, and so we cannot really control the dimension of the vectors other than the trivial bound $n$.

As you mention, the analysis in the particular case of MAX-CUT only uses the two-dimensional projections. This shows that even if you could somehow guarantee that $\operatorname{rank} V = 2$ (recall that the rank corresponds to the dimension), the analysis wouldn't get better. On the other hand, if you could guarantee than $\operatorname{rank} V = 1$, you will have solved MAX-CUT exactly. This shows that the latter constraint is NP-hard to realize. It is probably the case that any non-trivial rank constraint cannot be enforced in polynomial time, and any constant rank constraint is NP-hard.

---
Tags: optimization, approximation, max-cut
---


title: Size of the instance of a problem

text:
# Question
Title: Size of the instance of a problem
I am unable to find a clear definition of term "size of the instance" when considering some algorithmic problem. I came accross a definition that said, that "Size of the instance corresponds to the size of the input array of numbers (in case the input is numeric) or size of the representation of the input."

Is the **size of the instance** simply size of the input? Or is it size of all the structures used in the algorithm (in that case, it would be the space complexity, right?).

Lets explain it on a specific problem:

a) I have an array of **n** numbers and I have to sort them in non-decreasing order.

* So the size of the instance is **n** (those n numbers I have to sort - using for example BubbleSort). Is the size different for some other sort that uses some additional arrays during the sorting process?

b) Find strong components of a graph with **n** vertices and **m** edges.

* Is it simply **n+m**? Or n+2m (if I represent edges by 2\*m array)? Or do I have to consider all structures used in my algorithm (in this case it would be Tarjan, I guess).

Thank you for clarification!

# Answer
Unfortunately, there is no single definition of the size of instance. But if there were, it would be *the size of the input in bits*. Whenever we talk about Turing machines, we have to slightly change this to *the size of the input in tape symbols*.

Things get more complicated for models like the RAM machine, in which numbers are opaque. If the input consists of arbitrary-precision numbers, then the inputs size is *the number of input numbers*. This is again a variation on the earlier definition, since in this model, every memory cell contains an entire number.

Summarizing, the size of the input is always the number of cell / tape positions containing the input, but the interpretation of this quantity depends on the model.

More concretely, in your first example, the input includes the input array of length $n$ as well as the number $n$, so the input length should be at least $n+1$. The model in question here is the RAM model. If it were the Turing machine model, the size of the input would depend on the size of the integers being sorted.

In your second example, it depends on the exact encoding. In the RAM model, you can encode a graph with $n$ vertices and $m$ edge using $O(m)$ cells. In the Turing machine model, you can encode a graph using $O(n^2)$ cells or $O((m+1)\log n)$ cells, using the dense and sparse encodings, respectively. Sometimes the input encoding affects the running time, and in that case the algorithm would expect the input in some specific encoding, and you would get the input length from this encoding. Notice that I don't bother calculating the exact input length – almost always asymptotics are enough.
> 9 votes

# Answer
The size of the instance of a problem is the size of the **representation** of the input. For the Turing model, this is the number of cells used to write the **encoded** input on the tape.

Generally, we talk about bits and binary encoding of information. We could actually use any base $b$ to encode our input, for $b\geq 2$. This is the same as saying it does not matter whether we allow our Turing machine $M$ to have an arbitrary sized tape alphabet $\Gamma$, because we can construct an equivalent (computes the same function) Turing machine $M^\prime$ with $\Gamma=\\{0,1,\square\\}$ with polynomial overhead. (If $f$ is computable in time $T(n)$ by $M$ for some time-constructible $T:\mathbb{N}\rightarrow\mathbb{N}$ then $f$ is computable in time $C\log|\Gamma|T(n)$ by $M^\prime$ for some constant $C$. This means the Turing machine model is *robust*.)

The encoding is important, especially when we are considering problems that have integers as their input (e.g. Integer Factorisation).

If we use an encoding with base $b=1$, i.e. a *unary* representation, this actually changes things. In particular, the Integer Factorisation problem is not known to be computable in polynomial time (see *P versus NP*) for a binary encoding, but it can be computed in linear time if the input is given in unary encoding.

\[1\] Arora, Sanjeev, and Boaz Barak. *Computational complexity: a modern approach.* Cambridge University Press, 2009. (c.f. Exercise 1.15 and Claim 1.5)
> 4 votes

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


# Question
Title: Why do we use persistent data structures in functional programming?
Functional programming employs persistent data structures and immutable objects. My question is why is it crucial to have such data structures here? I want to understand **at a low level** what would happen if the data structure is not persistent? Would the program crash more often?

# Answer
> 21 votes
When you work with immutable data objects, functions have the property that every time you call them with the same inputs, they produce the same outputs. This makes it easier to conceptualize computations and get them right. It also makes them easier to test.

That is just a start. Since mathematics has long worked with functions, there are plenty of reasoning techniques that we can borrow from mathematics, and use them for rigorous reasoning about programs. The most important advantage from my point of view is that the type systems for functional programs are well-developed. So, if you make a mistake somewhere, the chances are very high that it will show up as a type mismatch. So, typed functional programs tend to be a lot more reliable than imperative programs.

When you work with mutable data objects, in contrast, you first have the cognitive load of remembering and managing the multiple states that the object goes through during a computation. You have to take care to do things in the right order, making sure that all the properties you need for a particular step are satisfied at that point. It is easy to make mistakes, and the type systems are not powerful enough to catch those mistakes.

Mathematics never worked with mutable data objects. So, there are no reasoning techniques we can borrow from them. There are plenty of our own techniques developed in Computer Science, especially Floyd-Hoare Logic. However, these are more challenging to master than standard mathematical techniques, most students can't handle them, and so they rarely get taught.

For a quick overview of how the two paradigms differ, you might consult the first few handouts of my lecture notes on Principles of Programming Languages.

# Answer
> 15 votes
It is *easier* to correctly work with persistent data structures than it is to work with mutable data structures. This, I would say, is the main advantage.

Of course, theoretically speaking, anything we do with persistent data structures we can also do with mutable ones, and vice versa. In many cases persitent data structures incure extra costs, usually because parts of them have to be copied. These considerations would have made persistent data structures much less attractive 30 years ago when supercomputers had less memory than your mobile phone. But nowadays the main bottlenecks in production of software seem to be development time and maintainance costs. Thus we are willing to sacrifice some efficiency in execution for efficiency in development.

Why is it easer to use persistent data structures? Because humans are really bad at tracking *aliasing* and other kinds of unexpected interactions between different parts of a program. They automatically think that because two things are called `x` and `y`, then have nothing in commmon. Afer all, it takes effort to figure out that "the morning star" and "the evening star" are really the same thing. Similarly, it is very easy to forget that a data structure may change because other threads are working with it, or because we called a method which happens to change the data structure, etc. Many of these concerns are just not present when we work with persistent data structures.

Persistent data structures also have other, technical advantages. It is typically easier to optimize them. For example, you're always free to copy a persistent data structure onto some other node in your cloud if you wish, there is no worry of synchronization.

# Answer
> 2 votes
Adding to others' answers, and reinforcing a mathematical approach, functional programming also has a nice synergy with Relational Algebra, and Galois Connections.

This is extremely useful in the area of Formal Methods.
For instance:

* Formal proofs in program verification are simplified with Extended Static Checking;
* A number of properties from Relational Algebra are useful in SAT solving, with tools such as Alloy;
* Galois Connections allow a calculational approach to software specification, as seen in this blog, with a reference to a paper, by Shin-Cheng Mu and José Nuno Oliveira.
* Galois Connections (and Functional Programming) can be used in a Design by Contract fashion, since they are a more general concept than Hoare Logic.

**Example**

The Hoare triple $\\{p\\} P \\{q\\}$ can be expressed as the contract $\[P\] \cdot \phi\_p \subseteq \phi\_q \cdot \[P\]$, where

* $\[P\]$ is the relation that denotes the semantics of program $P$;
* $\phi\_p$ (resp. $\phi\_q)$ denotes the coreflexive relation that captures predicate $p$ (resp. $q$);

This approach also allows **weakest pre-condition** and **strongest post-condition** calculation, which comes in handy in a number of situations.

# Answer
> 2 votes
> I want to understand at a low level what would happen if the data structure is not persistent?

Let's look at a pseudorandom number generator with a huge state space (like "Mersenne twister" with a state of 2450 bytes) as a data structure. We don't really want to use any random number more than once, so there seems to be little reason to implement this as an immutable persistent data structure. Now let's ask outselves what might go wrong in the following code:

```
mt_gen = CreateMersenneTwisterPRNGen(seed)
integral = MonteCarloIntegral_Bulk(mt_gen) + MonteCarloIntegral_Boundary(mt_gen)

```

Most programming languages don't specify the order in which `MonteCarloIntegral_Bulk` and `MonteCarloIntegral_Boundary` will be evaluated. If both take a reference to a mutable mt\_gen as an argument, the result of this computation can be platform dependent. Worse yet, there might be platforms where the result is not reproducible at all between different runs.

One can design an efficient mutable data structure for mt\_gen such that any interleaving of the execution of `MonteCarloIntegral_Bulk` and `MonteCarloIntegral_Boundary` will give "a correct" result, but a different interleaving will in general lead to a different "correct" result. This non-reproducibility makes the corresponding function "impure", and also leads to some other problems.

The non-reproducibility can be avoided by enforcing a fixed sequential execution order. But in that case the code could be arranged in such a way that only a single reference to mt\_gen is available at any given time. In a typed functional programming language, uniqueness types could be used to enforce this constraint, thereby enabling safe mutable updates also in the context of pure functional programming languages. All this might sound nice and dandy, but at least in theory Monte Carlo simulations are embarrassingly parallel, and our "solution" just destroyed this property. This is not just a theoretical problem, but a very real practical issue. However, we have to modify (the functionality offered by) our pseudorandom number generator and the sequence of random numbers it produces, and no programming language can do this automatically for us. (Of course we can use a different pseudorandom number library that already offers the required functionality.)

At a low level, mutable data structures easily lead to non-reproducibility (and hence impurity), if the execution order is not sequential and fixed. A typical imperative strategy to deal with these problems is to have sequential phases with fixed execution order, during which mutable data structures are changed, and parallel phases with arbitrary execution order, during which all shared mutable data structures stay constant.

---

Andrej Bauer raised the issue of aliasing for mutable data structures. Interestingly enough, different imperative languages like Fortran and C have different assumptions about the allowed aliasing of function arguments, and most programmers are quite unaware that their language has an aliasing model at all.

Immutability and value semantics might be slightly overrated. What's more important is that the type system and the logical framework (like the abstract machine model, the aliasing model, the concurrency model, or the memory management model) of your programming language offers sufficient support for working "safely" with "efficient" data structures. The introduction of "move semantics" to C++11 might look like a giant step back in terms of purity and "safety" from a theoretical point of view, but in practice it is the opposite. The type system and the logical framework of the language have been extended to remove huge parts of the danger associated to the new semantics. (And even if rough edges remain, this doesn't mean that this couldn't be improved by a "better" extension of the framework.)

---

Uday Reddy raised the issue that mathematics never worked with mutable data objects, and that the type systems for functional programs are well-developed for immutable data objects. This reminded me of Jean-Yves Girard's explanation that mathematics is not used to work with changeable objects, when he tries to motivate linear logic.

One might ask how to extent the type system and logical framework of functional programming languages to allow working "safely" with "efficient" mutable non-persitent data structures. One problem here might be that classical logic and boolean algebras might not be the best logical framework for working with mutable data structures. Perhaps linear logic and commutative monoids might be better suited for that task? Perhaps I should read what Philip Wadler has to say on linear logic as type system for functional programming languages? But even if linear logic should not be able to solve this problem, this doesn't mean that the type system and logical framework of a functional programming language couldn't be extended to allow "safe" and "efficient" mutable data structures.

---
Tags: data-structures, functional-programming, programming-paradigms, persistent-data-structure
---


# Question
Title: Find longest path between two disjoint sub-sets of vertices $V_1, V_2 \subset V$ of a Graph
I have a homework question which I would appreciate some help with:

> Let there be a DAG $G=(V,E)$ with positive weights. For every two different vertices $v\_1, v\_2$ we will define $D(v\_1, v\_2)$ to be the maximum length between $v\_1$ and $v\_2$ in the graph.
>
> For every two disjoint sub-sets of vertices $V\_1, V\_2 \subset V$ we will define "The detour length" between them to be: $w(V\_1, V\_2) = max\\{D(v\_1, v\_2) \mid v\_1\in V\_1, v\_2 \in V\_2\\}$
>
> Describe an algorithm which runs at $O(|V|\cdot |E|)$ complexity, that receives as an input $V\_1, V\_2 \subset V$ and calculates $w(V\_1, V\_2)$
>
> (Hint: You can add vertices and edges to the graph)

OK so I realize that this is a problem which is connected to finding the longest path in a DAG. I know that I can negate all the weights inside $G$ and run Bellman-Ford to find the longest path, (It will work without issues because this is a DAG). Because Bellman-Ford runs in the wanted complexity, I think this can be solved by doing some modification to B-F, but I can't seem to figure out what I can do to solve it.

Every solution I come up with will run in a higher complexity than needed - I thought about running B-F on every vertex on $V\_1$ and then calculating the max, but this isn't efficient, and also doesn't really use the hint. I also though about creating a second graph by connecting the two sub-sets but that also will run at a higher complexity because I need to run over every vertex.

Any help is appreciated, Thx!

# Answer
> 1 votes
Hopefully not giving too much away: You need to add only two nodes.

---
Tags: algorithms, graphs, data-structures, shortest-path
---


# Question
Title: Time complexity of Dynamic Array via repeated doubling
When we implement dynamic array via repeated doubling (if the current array is full) we simply create a new array that is double the current array size and copy the previous elements and then add the new one? Correct?

So to compute the complexity we have 1 + 2 + 4 + 8 + .... number of steps? Correct?

But

```
 1 + 2^1 + 2^2 + .... + 2^n  =  (2^(n-1) - 1)  ~  O(2^n).

```

However it is given that

```
 1 + 2 + 4 + ... + n/4 + n/2 + n  ~  O(n).

```

Which one is correct? And why? Thanks

# Answer
> 9 votes
Both are correct but you're using $n$ to mean two different things:

* when you say that $1 + 2^1 + 2^2 + \dots + 2^n = (2^{(n-1)} - 1) \sim O(2^n)$, you're using $n$ to mean the number of times you had to increase the size of the array;
* when you say that $1 + 2 + 4 + \dots + n/4 + n/2 + n \sim O(n)$, you're using $n$ to mean the total size of the array after you've extended it some number of times.

So, you should never just say "$n$", without saying what it means. Normally, $n$ refers to the size of the input to a problem. In this case, that would probably be the number of things you want to insert into the array. This is closest in meaning to the second case above since, when you've inserted $n$ elements, the total size of the array will be somewhere between $n$ and $2(n-1)$ (i.e., it will be $O(n)$).

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


# Question
Title: Building a Red Black tree out of a sorted array
If I have a sorted array of size $n$, can I build a Red Black tree out of it in $O(n)$ time in a different algorithm rather than splitting the tree in half every time or the straightforward way that was mentioned in one of the answers?

# Answer
This can be done in a very straightforward way: Just build an almost complete tree and make the nodes on the lowest level red.
> 3 votes

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


# Question
Title: The Gas Station Problem - fast implementation
Recently I was asking about the algorithm to solve The Gas Station Problem and I got useful answer. Unfortunately solution with transforming a graph to complete graph and then preparing another one to find the shortest path (as described in paragraph 4) is really slow in case of my constraints.

I figured out how to implement much faster version. It's way better, but has a bottleneck :-(. Let me first describe my implementation. It's really simple:

**I use BFS and relaxation method to calculate D\[destination\]\[0\]:**

```
D[v][f] - minimum cost to get from u to v with remaining f units of fuel at this city.

minFuel - minimum remaining fuel at v = max(0, f1 - distance(u,v))
maxFuel - maximum remaining fuel at v = tankCapacity - distance(u,v)

D[source][0] = 0
D[v][f] = min((u,v), f1, f2 | u->v in Edges and f1 in 0..tankCapacity and f2 in minFuel..maxFuel)
             { D[u][f1] + (f2 - f1 + distance(u,v)) * fuelRate[u] }

```

The bottleneck is because of going through all possible values (f1, f2).

Pseudocode:

```
queue.push(source);
D[source][0] = 0
visited[source] = true

while(!queue.empty)
    current = queue.pop

    foreach (current,v) in Edges
       if !visited[v]
           queue.push(v)
           visited[v] = true

        for f1 in 0..tankCapacity
           if D[current][f1] == infinity
              continue

            minFuel = max(0, f1 - distance[current,v])
            maxFuel = tankCapacity - distance[current,v]

            for f2 in minFuel..maxFuel
                toRefill = f2 - f1 + distance[current,v]
                newCost =  D[current][f1] + toRefill * fuelRate[current]
                if (newCost < D[v][f2])
                   D[v][f2] = newCost

return D[destination][0]

```

Constraints (only integers):

```
maximum vertices:      1000
maximum edges:         10000
maximum distance:      100
maximum fuel rate:     100
maximum tank capacity: 100

```

**Does anybody have an idea how to improve this algorithm to make it faster?**

# Answer
> 1 votes
Finally I had prepared a solution with good enough complexity. Friend from my college had given me some hints and I managed to implement it. Maybe it will help someone, so I decided to describe this solution here.

The idea is very simple, we use Dijkstra's Algorithm, but instead simple vertices we have pairs (v, f). v - vertex id, f - fuel in tank. This solution is much faster, because we don't need to go through all values of "f" and also when we process a vertex, it already has an optimal solution. So when we'll get to the destination vertex, we can stop further processing.

Dijkstra's Algorithm needs to get a minimum value in each iteration, so it's good to use *heap structure* for a priority queue.

**Pseudocode**:

```
D[v][f]        - minimum cost to get from source to v with f units of fuel
distance[u][v] - distance between u and v

relax(tankCapacity, u, f, newCost):
    if (f >= 0 and f <= tankCapacity and D[u][f] > newCost)
        D[u][f] = newCost
        heap_push_or_update(D[u][f])

solve(tankCapacity, source, destination):
    foreach (v, f)
        D[v][f] = infinity

    D[source][0] = 0
    heap_push(D[source][0])

    while not heap_empty()
        (v, f) = heap_pop_min();

        //don't go further than destination
        if (v == destination and f == 0)
            return D[v][0];

        //stay in the city and refill more fuel - it can improve D[v][f + 1]
        newCost = D[v][f] + fuelRate[v];
        relax(tankCapacity, v, f + 1, newCost);

        //go to the adjacent cities "u" without refilling - it can improve D[u][f - d]
        foreach (v, u) in Edges
            relax(tankCapacity, u, f - distance[v][u], D[v][f]);

```

# Answer
> 3 votes
Your recurrence relationship isn't quite right -- you need to relate the input parameter f to f1 and f2 somehow. I think you can get rid of f2 completely:

```
checkTank(f) = if f <= U then f else INF
D[v][f] = min(u, f1 | u->v in Edges and f1 in 0..tankCapacity)
             { D[u][f1] + checkTank(f - f1 + distance(u, v)) * fuelRate[u] }

```

Entries D\[v\]\[f\] for values of f which would imply putting more gas in the tank than it can hold will correctly get assigned INF by the above. (Here I assume that adding any nonnegative value to or multiplying any positive value with INF yields INF again; in an actual implementation you might want to specially check and avoid further processing of such values.)

But in any case, the algorithm in the paper is fast because they exploit a dominance rule (Lemma 2.1) that implies that an optimal solution can always be found even if you only look at O(n) particular different gas tank levels at each node, and you aren't making use of that here. If you don't make use of that same property, I think your algorithm will be at best pseudopolynomial (they say this in the paper; BTW that doesn't necessarily make it a terrible algorithm in practice) and in effect usable only with integer-weight fuel amounts.

Regarding adding the missing edges: For the case where you don't limit the number of stops, the running time is O(n^3), so it's safe to run Floyd-Warshall at the beginning to calculate the minimum path distance between all pairs of vertices that lack an edge, as it's also only O(n^3) and therefore doesn't increase the running time asymptotically.

At first glance it seems possible to accept an incomplete graph, and allow "fill stops" at which 0 fuel is filled. But this invalidates Lemma 2.1, since now there can be graphs in which an optimal path involves filling up *less than the full amount* at some node w, before travelling to some node u with higher cost, "filling up" with 0 fuel there, and then travelling on to reach (on an empty tank) some other node v with cheaper fuel than w. You can play around with Lemma 2.1 to allow arbitrarily long strings of special "0-fill" stops between "real" stops, and this works, but it doesn't buy you anything: for each vertex u, instead of having to consider all possible neighbours w of u and their distances d(w, u) to u, you'll have to consider all possible *vertices* w and the lengths of their shortest *paths* to u, which means that you might as well calculate them all at the start and make edges with their weights.

Finally you can discard/ignore/avoid calculating any edges longer than U or which violate the Triangle Inequality (in fact these constraints also apply to any edges already in the original graph).

---
Tags: algorithms, graphs, recurrence-relation, dynamic-programming
---


# Question
Title: How does one choose an optimal alphabet for finding a Huffman encoding?
Huffman encoding will perform best when the distribution of symbols of an alphabet that the string to be encoded uses is dyadic.

Given an arbitrary bit string `S`, how can we find the best alphabet for encoding? Suppose `S` is an ASCII file. Then given the regularity of 1-byte characters that such files exhibit, we would expect that an optimal, or at least pretty good, alphabet should contain, say, 8-bit or 16-bit words (which we then build codes for after constructing the Huffman tree).

Is there an algorithm for finding the optimal word width (assume we use constant-length words).

I would guess that to evaluate an alphabet, it would only be fair if we considered the costs of storing the actual encoding as well. This addresses the case where the alphabet is just one symbol - the entire original string. Technically the message would just be one bit, but the the encoding tree that's stored would have to indicate that the one bit used is a code for the original string, so we've just increased our message by two bits trivially!

(Constant-length encoding information such as width size, encoding table size, etc., need not be considered for the comparisons, of course).

# Answer
The size required to store the Huffman code table scales like the number of codewords. We expect the number of unique $k$-letter words to be exponential in $k$, in fact roughly $2^{kH}$, where $H$ in the source entropy, though since the file is not infinite, for large $k$ we will actually see less. Still, this suggests that for logarithmically large $k$, most of the $k$-letter strings will be almost unique, and so the overall compression for such a $k$ would typically be quite small. In view of that, you can just try several values of $k$, and choose the best one. After you do some such experiments, you can formulate and perhaps prove a hypothesis as to the optimal value of $k$ in different situations.
> 4 votes

# Answer
I'm having trouble answering your question for two reasons. First, the entropy changes as you change the alphabet, so the "best" alphabet depends on the correlations between characters in the class of strings that you are trying to encode, not just the "dyadicness". (This is the problem with the notion of entropy: it depends on your model of what you know about the method by which a string was generated, it is not a fundamental property of a string.) So I can't think of an algorithm that would do better than "try every character length and see which one ends up with the best result."

Second it's not clear (to me) why you are trying to choose an alphabet that gets closest to having a "dyadic" probability distribution (I had to look that term up), when in practice the main reason that people use Huffman coding is that there is an adaptive version (i.e., one that doesn't need to store the encoding,) which is "good enough", not because it is optimal. In practice (for example in the old Unix `pack` utility, or in the Huffman coding done at the end of MPEG encoding), the input alphabet size is chosen to be some "natural" size (bytes if you are encoding Unix files in the 1980s, some much larger alphabet if you know you are encoding Unicode).

If you want a non-adaptive encoding with a fixed-width alphabet (given that you are unaware that there should be any correlation between symbols) then you should use arithmetic coding, which gets closer to optimal for non-dyadic distributions.

If you have reason to believe that there are correlations between nearby characters then you might use something like PPM, and if you believe that there are likely to be repeated substrings (but not necessarily nearby) you might use some some kind of Lempel-Ziv compression. (Various kinds of Lempel-Ziv are used by Unix's `gzip` and `compress`).
> 4 votes

---
Tags: data-compression, encoding-scheme
---


# Question
Title: What does "finite state transduction" mean?
Wikipedia says, the regular languages are closed under

> arbitrary finite state transductions, like quotient K / L with a regular language.

I wonder what kinds of operations "finite state transductions" are? Btw, It links to finite state transducer, an automaton. Thanks.

# Answer
A finite state transducer is a machine model, much like a finite state automaton, but equipped with two tapes, one for input and one for output. Each specific finite state automaton defines a binary relation between input and output strings.

Your assumption is right: for each input string we look at computations that match that string and output the corresponding strings on the second tape. This process can be highly nondeterministic, as symbols can be deleted and inserted at will (when the automaton is programmed to do so). This definition is extended to languages: each transducers defines a binary relation on languages too.

Transducers can be found for a very broad class of tasks: homomorphisms, inverse homomorphisms, intersection or quotient with (a fixed) regular language. Finite state transducers are nice devices, e.g., they can be programmed to deleted every second $a$ in a string, but only for strings ending in a $b$.

The wikipedia article on FST ignores a very important basic fact on transductions. They happen to be equal to the class of operations built from homomorphisms, inverse homomorphisms and intersection with regular languages. Each family closed under these operations is called a trio, and such a class is then closed under all FST's. Examples are the family of regular languages and the family of context-free languages. So as a consequence, given a CFL, the language we obtain by erasing every second $a$ (for strings that end in a $b$) is again context-free.
> 3 votes

---
Tags: terminology, automata
---


title: Correctness of proof by induction

text:
# Question
Title: Correctness of proof by induction
Suppose a person states the following: $n^2 = (n * n), \forall n \> 0$. One can check such equality by saying, via proof by induction, that:

* for $n := 0:\ 0^2 = (0 * 0)$;
* for $n := 1:\ 1^2 = (1 * 1)$;
* and for $n := n + 1:$

$\ (n + 1)^2 = ((n + 1) * (n + 1))$

$n^2 + 2n + 1 = n^2 + 2n + 1$

As far as I understand, this states that:

* $P(n)$ is valid for some $n$ within a range, say integers greater than 0;
* $P(n)$ must be valid for the successor of any $n$ within the previous range;

Of course, it is not commonly necessary to prove such things as $n^2 = (n * n)$. And, proving it seems rather like considering that, eventually, there could be a *mysterious* value for $n$ that would make $n^2 \neq (n * n)$.

**First question**: is this *interpretation* correct?

---

Now, if one could prove $P(n): n^2 = (n * n)$ via the base and the induction cases:

* $P(n)$ is valid for $n := 0$;
* $P(n)$ is valid for $n := n + 1$;

One should also be allowed to prove it by saying that:

* $P(n)$ is valid for $n := 0$;
* $P(n)$ is valid for $n := n + 2$;
* and via $P(n)$ is valid for $n := n + 3$;
* and via $P(n)$ is valid for $n := n + 4$;
* and, in fact, via $P(n)$ is valid for $n := n + m,\ \forall m \> 0$.

**Second question**: is this *inference* correct?

---

So, if we are fine thus far, it should be the case that, eventually, a *mysterious value* $m$ could make proof by induction fail. And here comes the final question.

**Third Question**: how to prove the correctness of proof by induction?

# Answer
> 10 votes
Short answer: Proof by induction is correct because we define the natural integers as the set for which proof by induction works.

## On your interpretations and examples

Your understanding seems broadly correct, though there are a few places where your statements are not fully rigorous. Given that we're talking about logic, getting things precisely right is important.

* You should mention that you're working in the domain of integers (naturals, to be precise, which are the nonnegative integers). Induction doesn't work on many larger domains such as real numbers.
* When proving a property of the form $\forall n \gt 0, \ldots$, the case $n=0$ does not come up. The basic induction principle applies to all natural numbers: if $P(0)$ and $\forall n \in \mathbb{N}, (P(n) \to P(n+1))$ then $\forall n \in \mathbb{N}, P(n)$. Other statements such as “if $P(1)$ and $\forall n \in \mathbb{N}, (n \ge 1 \to (P(n) \to P(n+1)))$ then $\forall n \in \mathbb{N}, (n \ge 1 \to P(n))$” are also true (and easy to derive from one another).
* “$P(n)$ is valid for $n:=n+1$” is not a rigorous statement since the last occurrence of $n$ is not covered by any quantifier. The proper way to write this is “for any natural $n$, if $P(n)$ holds then $P(n+1)$ holds”.
* Regarding your second question, it isn't clear what you mean by “and, in fact, …”. It is not the case, for example, that $P(0) \wedge (\forall n \in \mathbb{N}, P(n) \to P(n+2))$ implies $\forall n, P(n)$ — these hypotheses only prove that the property holds on even integers.
* Finally, this isn't a matter of rigor, but your choice of example is odd, as $n^2$ is normally defined as $n\*n$ — so after expanding the definition, the property to prove becomes $\forall n \gt 0, n * n = n * n$, which doesn't need induction. A better elementary example would be $\forall n \in \mathbb{N}, n + 1 = 1 + n$.

## The Peano axioms

Now, to turn to why proof by induction works. It is impossible to answer this question rigorously without explicitly stating how the natural numbers are defined, or what properties of the natural numbers we define. Many definitions exist.

One definition of the natural numbers is the Peano axioms. There are many minor variants of the Peano axioms; one (which assumes equality as a preexisting notion) is:

1. $0$ is a natural.
2. For every natural $n$, $S(n)$ is a natural.
3. For every natural $n$, $0 \ne S(n)$.
4. For every natural $n$ and $m$, if $S(m) = S(n)$ then $m = n$.
5. Let $P$ be any unary predicate over the naturals. Suppose that $P(0)$ is true and that for every natural $n$, if $P(n)$ is true then $P(S(n))$ is true. Then for every natural $n$, $P(n)$ is true.

The first two axioms describe ways to build naturals. The next two axioms state that naturals built in different ways are distinct. (Exercise: find a model where all the axioms hold except for #3. Maybe a bit harder: find a model where all the axioms hold except for #4.)

As you can see, with this axiomatisation of the naturals, the induction principle is an axiom.

If you try to define the naturals as a subset of the reals, you'll run into foundational trouble: where do the reals comes from, and how do you prove properties of them? For example, it's difficult to reason about sequences of reals (or anything else) without induction.

The most common foundation of mathematics is set theory, specifically, ZF (Zermelo-Fraenkel). From ZF, a common way to define naturals is as Von Neumann ordinals:

* $0$ is the empty set: $0 := \varnothing$
* the successor of an ordinal is the union of that ordinal with the singleton containing it: $S(n) := n \cup \\{n\\}$.

The existence of the empty set is guaranteed by any set theory that proves the existence of at least one set and even a weak version of the axiom of comprehension. The existence of a successor is guaranteed by pairing to prove the existence of $\\{n\\}$ (which is an abbreviated notation for the pair $\\{n,n\\}$), and one to prove and union to deduce the existence of $n \cup \\{n\\}$. This suffices to prove the existence of all the natural numbers.

In order to prove that all the natural numbers form a set, an additional axiom is needed. It can be stated as “the natural numbers form a set”. Usually, the axiom is formulated as “the exists an inifinite set”. This more general formulation does not guarantee that the natural numbers obtained by this construction form a set — there are models of ZF where the smallest infinite set contains more than just zero and its successors, called non-standard models. I won't dwell on these models; doing logic in these models tends to be somewhat non-intuitive, but they are nice in that they allow rigorous reasoning about “infinitesimally large” integers, and from there about infinitesimally small numbers such as the $\mathrm{d}x$ in $\dfrac{\mathrm{d}x}{\mathrm{d}t}$ beloved of physicists.

Let's call a set $x$ *supernatural* (this is not standard terminology) if it contains $0$ and if for any $y \in x$, $S(y) \in x$. A supernatural set contains all the naturals, and perhaps more. A common formulation of the axiom of infinity is that there exists a supernatural set; we'll assume that. Let $\mathbb{O}$ be a supernatural set.

Now let $\mathbb{N}$ be the intersection of all the supernatural subsets of $\mathbb{O}$. Since all the supernatural sets contain $0$ and there is at least one element in the family ($\mathbb{O}$ itself), $0 \in \mathbb{N}$. For any $n \in \mathbb{N}$, $n$ is a member of each supernatural subset of $\mathbb{O}$, therefore (by definition of supernatural sets) so is $S(n)$. Thus $\mathbb{N}$ itself is supernatural. We'll call this set the set of naturals. Intuitively speaking, $\mathbb{N}$ is the smallest set containing the naturals (though without further axioms it is not necessarily unique, e.g. in nonstandard models).

$\mathbb{N}$ satisfies the induction principle. To see this, consider a predicate $P$ over the naturals, such that $P(0)$ is true and for all $n \in \mathbb{N}$, $P(n)$ implies $P(n+1)$. Let $\mathbb{N}\_P$ be the set of naturals that satisfy $P$, i.e. $\mathbb{N}\_P = \\{n \in \mathbb{N} \mid P(n)\\}$. Then $\mathbb{N}\_P$ is a supernatural set, so $\mathbb{N} \subseteq \mathbb{N}\_P$ by definition of $\mathbb{N}$.

## Other foundations of mathematics

There are foundations of mathematics that are not based on set theory. What you consider the foundations vs derived theorems is not important: as long as you prove that your foundations are equally consistent with one of the commonly accepted ones, you're doing the same mathematics as everyone else. The definition of $\mathbb{N}$ as a set of ordinals is merely one way to construct it. The Peano axioms (or any equivalent formulation) are the specification of the naturals, and it is this specification that defines $\mathbb{N}$, rather than any particular construction.

In particular, constructive foundations of mathematics tend to treat the naturals as the most fundamental notion, and the induction principle on naturals, or on some more general structures, as a foundational axiom. For example, in homotopy type theory, the Peano axioms are a consequence of the rules for constructing functions by recursion. In intuitionistic type theory with inductive types (e.g. in the calculus of inductive constructions, which is the foundation of the Coq proof assistant), the induction principle on naturals is an instance of the more general induction principle that holds on any constructed type.

---
Tags: proof-techniques, induction
---


# Question
Title: NP-complete problems and sub-expenential sized circuits
If one were to show that an NP-complete problem had $2^{n^{O(1)/\log{\log{n}}}}$ circuit complexity, what would the consequences of this be?

# Answer
If such an algorithm were found, it would violate the exponential time hypothesis. See also, for example, Are there subexponential-time algorithms for NP-complete problems?.

And of course, if this were the best possible complexity for any algorithm for this problem, you would have shown that $P \ne NP$ (and in fact that $NP \ne P/\text{poly}$). When you wrote that the problem has such-and-such circuit complexity, I don't know whether you meant (a) there exists an algorithm with that complexity, or (b) the problem has that complexity (which means there exists an algorithm of that complexity, and there is no better algorithm); this paragraph only applies if you meant (b).

Beyond that, I don't think there would be any other obvious consequences. In particular, I don't know of any significant consequences if the ETH is violated (other than the obvious one, that the theorems of the form "if the ETH holds then..." become moot).
> 2 votes

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


title: Nested loops: Still $\mathcal O(n)$?

text:
# Question
Title: Nested loops: Still $\mathcal O(n)$?
I have an algorithm similar to this:

```
i=1
while(i < n) {
  //something in O(1)
  while(i < n && cond) {
    //something in O(1)
    i++
  }
  i++
}

```

Where "cond" is some condition which can be checked in $\mathcal O(1)$. It is clear that this algorithm is $\mathcal O(n^2)$. But is it also $\mathcal O(n)$?

I'd say yes because the statement "i++" is executed $\mathcal O(n)$-times since both loops end when i reaches n.

Is it possible to rewrite the algorithm in a form with equivalent runtime so that it can be seen more clearly?

# Answer
> 6 votes
What you have there is not a true nested loop. It's one loop with, what is equivalently an if-test in there, like:

```
while(i<n){
   if(cond)
      //something Θ(1)
   else
      //some other Θ(1) thing
   i++
}

```

Notice in your case, you have the same variable for both loops with no reset.

So, to answer your question, the running time is $\Theta(n)$. In particular, it is $O(n)$.

As a commenter states, anything that is $O(n)$ is also $O(n^2)$.

---
Tags: algorithm-analysis, runtime-analysis, loops
---


title: Conditional LCS problem

text:
# Question
Title: Conditional LCS problem
A producer wants to arrange couples of boys and girls for a dance.
There are n boys arranged in a row \[A1...An\] in some certain order and n girls arranged in a different row \[B1...Bn\], also in some certain order. Only a couple in which there is a boy and a girl with exactly the same height can dance.
The height of every boy and girl is known. The producer needs to find the maximum number of couples that can dance (There might be people who can't dance).

1. Show an algorithm for the general case.
2. Show an algorithm, in which you can't change the order of the boys and the girls. In other words: If there is a couple (Ai,Bj) then there can't be (Ak,Bp) (so that k \> i, p \< j or k \< i, p \> j)

Analyze the complexity in every case.

What I know is that the solution to 1 is sorting the array in $O(nlogn)$.
My idea in approaching 2 is that it's like LCS in a static table, only with numbers and not chars, which takes $O(n^2)$.

Can 2 be done in better complexity that $O(n^2)$?

# Answer
> 2 votes
Longest common subsequence (not necessarily continuous) is the solution for the second problem, not for the first. (For the first problem it is not only slower than necessary, but also gives the wrong result. Consider e.g. $A=\[1,2\]$, $B=\[2,1\]$: LCS would give only 1 couple, while actually 2 can be formed.)

For the first problem, as @sai\_preet pointed out in a comment, you can sort both arrays and then find the couples with a procedure analoguous to `merge`. This will take $\Theta(n\log n)$ time.

---
Tags: algorithms, strings
---


title: Average between n numbers

text:
# Question
Title: Average between n numbers
Is it possible to calculate the average between n numbers in a static random access array of some size in less than $O(n)$ time? I know that the trivial approach is $O(n)$, but can I do it in less time using a data structure or a certain preparation? or both? I am asking for hints, not a solution.

Note: The array is of some length. What and I mean by between is when given 2 indexes a and b, I have to calculate the average of the sub array $\[a+1,b-1\]$. And I have to keep it updated while the data structure is managed, that's why I said it was a dynamic set, in other words a random access array. I do not know of any restrictions, just asking if it's possible in less than $O(n)$.

# Answer
I'll assume that you are computing the average of the elements of an array of fixed size and that you can change the value at some position at any moment. You want a data structure that supports the following two operations:

1. Update element at location $i$,
2. Query sum of elements in range \[$i$, $j$\].

A binary indexed tree (aka Fenwick tree) performs both in $\cal O(\lg n)$.
> 4 votes

# Answer
I am assuming that the query must be done in less than O(n) time and preprocessing can take any amount of time.

**Pre-processing:** Store the values in a Binary Tree like data structure.Every node of tree has sum of its subtree and number of children(To calculate average).So the base case is that you have n leaves having n values and we go leaves to root to construct this tree.You can do this pre-processing in O(nlogn) time.

**Query:** Now whenever you update a value you need to go to leaf along the path from top node to this leaf and the sum only changes in the nodes along this path so this takes only O(logn) time.

Correct me if I am wrong.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Question about the definition of complexity class oracles
If $B$ is a complexity class, then the class $P^B$ (for example) is defined as the set of problems that can be run in polynomial time, given an oracle to every problem in $B$. That's what they told me in my Theory of Computation class, anyways.

Per this definition, it seems to me that $P^P$ captures every decidable language. Here's why I think that:

Let $M$ be a TM that always halts. On input $x$, construct a new machine $M'$ that: (1) checks to see if the input is equal to $x$, (2) if its input is $x$ then it simulates $M$ on $x$, (3) if its input is not $x$ then it instantly rejects.

This new machine $M'$ runs in $O(n)$ time, so in the class $P^P$, we have an oracle to it. We can now consult this oracle to find out if $M'$ accepts $x$, and we learn in only $O(n)$ time whether or not $M$ accepts $x$. So we have an algorithm that decides $M$ and runs in $TIME(O(n))$, given an oracle to some countable set of problems in $TIME(O(n))$ (e.g. every $M'$, constructed with respect to every possible finite bitstring $x$).

What am I misunderstanding?

---

Here is an attempt to clarify my confusion.

This is the model that I think we are using:

There are three tapes usable by the Oracle Turing Machine: a standard worktape, an "oracle input tape," and an "oracle machine tape." The OTM can enter a special state where it takes the machine description written on the oracle machine tape, performs a magical 1-step simulation of that machine on input equal to the contents of the oracle input tape, and then writes down a $1$ or a $0$ on the worktape according to the results of the simulation.

Define: A language $L$ is in $P^P$ if there is an OTM that decides L and always halts in $p(n)$ steps on length $n$ input (for some polynomial $p$), and also for every Turing machine description $M$ used by the OTM, there exists a polynomial $q$ such that $M$ halts in $q(n)$ steps on input $M$.

Then my argument is valid, I think: every machine that we write down runs in linear time overall (even though the constant associated with that machine will grow very quickly for increasingly-long inputs).

This wouldn't be a problem if we flipped the quantifiers (i.e. "there exists a polynomial $q(n)$ such that every machine description $M$ used by the OTM halts in $q(n)$ steps). But I'm not sure that still describes $P^P$...

# Answer
Either you're misunderstanding what they said, or you're not misunderstanding anything.

If $B$ is a complexity class, then the class $P^B$ is defined as $\bigcup\_{L \in B} P^{L}$. (That applies even when $B$ does not have a complete problem.)

If $B$ is a complexity class and $K$ is complete for $B$ under polynomial-time Turing reductions, then $P^B = P^K$.

**Proof:** If those hypotheses hold then for all languages $L$ in $B$, by using the reduction to simulate oracle queries to $L$, one has $P^L \subseteq P^K$.

Thus, if those hypotheses hold then $P^K \subseteq \bigcup\_{L \in B} P^{L} = P^B = \bigcup\_{L \in B} P^{L} \subseteq \bigcup\_{L \in B} P^{K} = P^K$.

Therefore, if those hypotheses hold then $P^B = P^K$.
> 4 votes

# Answer
Let $\mathcal{C}$ be a complexity class. $\mathrm{P}^{\mathcal{C}}$ is usually defined to be the class of problems decidable in polynomial time by a deterministic machine that has an oracle for some $\mathcal{C}$-complete problem $X$. Thus, in particular, $\mathrm{P}^{\mathrm{P}} = \mathrm{P}$: you can only make polynomially many oracle calls and each one of those can be simulated in a polynomial number of steps.

Having an oracle for a single $\mathcal{C}$-complete problem is equivalent to allowing oracles for all problems in $\mathcal{C}$. By definition of completeness, any problem in $\mathcal{C}$ can be reduced in polynomial time to $X$. So, instead of calling the oracle for some problem $Y$, you perform the reduction from $Y$ to $X$ and use the oracle for that.

The reason you seem to have obtained something more powerful is that you've hidden a lot of complexity in your oracle calls. Suppose, for example, that $M$ decides an $\mathrm{EXPTIME}$-complete problem. By the time hierarchy theorem, there is no polynomial-time algorithm that, given $M$ and an input $x$, determines whether $M$ accepts $x$. This means that, when you want to call your oracle for $M(x)$, you don't know whether to call the one that accepts $x$ or the one that rejects it.

If you think in terms of having an oracle for a single complete problem, it's maybe easier to see. You now need to do the reduction yourself: that is, you need to reduce the problem defined by $M$ to your $\mathrm{P}$-complete problem $X$. But this cannot be done by the time hierarchy theorem.
> 3 votes

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


# Question
Title: Can a language be the one recognized by more than one automatons?
The language recognized by an automaton is defined as the set of strings that are accepted by the automaton.

I wonder if it is possible that the languages recognized by two automatons are the same? Note, if I am correct, the most general automatons are the Turing machines, and the languages recognized by an automaton are exactly the recursively enumerable languages.

The same question if restricted to the commonly-known subfamilies of languages and their corresponding automatons (e.g. regular languages, context-free languages, context-sensitive languages)?

Thanks.

# Answer
Yes, of course, it is possible. For instance, the process of DFA minimization works as follows: given a DFA $M$, produce another DFA $M'$ that recognizes the same language but is as small as possible. That tells you that it is possible to have two DFAs (deterministic finite-state automata) that recognize the same language.

If you want an explicit example: Let $M\_1$ be a DFA with a single state (which is accepting) and self-loops on inputs $0$ and $1$. Let $M\_2$ be a DFA with two states (which are both accepting) and edges from state $s\_0$ to $s\_1$ on inputs $0$ and $1$, and edges from state $s\_1$ to $s\_0$ on inputs $0$ and $1$. They both recognize the language $\\{0,1\\}^\*$, i.e., they are two different DFA that recognize the same language.

The same holds for other common families of languages, e.g., context-free languages and pushdown automata; context-sensitive languages and context-sensitive grammars.
> 3 votes

# Answer
If there is one automaton of some particular type that accepts a given language, there are infinitely many: take any automaton and add any pattern of states that are unreachable from the start state. (In fact, you can do it by adding reachable states in all cases I can think of.)

I don't see how you can conclude from, for example, the existence of multiple pushdown automata accepting the same language, that Turing machines are the most powerful automata. In any case, it's not true: a Turing machine with an oracle for the halting problem is strictly more powerful than an ordinary Turing machine. But these oracle Turing machines cannot decide their own halting problem (same argument as for regular TMs) so Turing machines with an oracle for that halting problem are even more powerful (same argument again). And so on, *ad infinitum*. There is no "most powerful" class of automata.
> 3 votes

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


# Question
Title: Is Hamiltonian path NP-hard on graphs of diameter 2?
Let $G$ be a graph of diameter 2 ($\forall u,v\in V: d(u,v)\leq2$).

> **Can we decide if $G$ has Hamiltonian path in poly time? What about digraphs?**

---

Perhaps some motivation is in place:

the question arises from Dirac's theorem which states that if $\forall v\in V:d(v)\geq \frac{n}{2}$ then the graph is Hamiltonian, as well as it's generalizations (the Ghouila-Houri theorem and the result from Bang-Jensen and Gutin's book).

I've shown here that these degree requirements imply that the graph has diameter 2, and was wondering if such graphs can be decided without the degree requirements (strong gut feeling: No).

# Answer
> 2 votes
Assuming you are talking about directed graphs, the work of Füredi et al. \[1\] shows that such graphs of n vertices and diameter 2 have at least ~n log (n) edges, or an average degree of ~log(n). I am aware of no subsequent result tightening this result, and the authors themselves suggest that they think this result is tight; this is quite far from the known sufficient conditions for Hamiltonian paths, which are based on a roughly linear vertex degree.

## As a result, this appears to be an open and difficult problem that would require some significant research for a solution.

\[1\] Füredi, Zoltán, et al. "Minimal oriented graphs of diameter 2." Graphs and Combinatorics 14.4 (1998): 345-350.

---
Tags: graphs, np-complete, hamiltonian-path
---


title: Maximum sub-matrix sum

text:
# Question
Title: Maximum sub-matrix sum
Given a $n\times m$ matrix $A$ of integers, find a sub-matrix whose sum is maximal. If there is one row only or one column only, then this is equivalent to finding a maximum sub-array.

The 1D version can be solved in linear time by dynamic programming. The 2D version can be solved in $\cal O(n^3)$ by looping over all pairs of columns and using the 1D algorithm on the array whose length is the number of rows in the matrix where each position $r$ holds the sum of the elements at row $r$ between the two columns.

If the matrix is given by:

\begin{pmatrix} 1 & -2 & 0 & -1 \\ 5 & 43 & 31 & 78 \\ -45 & -12 & 19 & 9 \end{pmatrix}

Then for the pair of columns $(0,2)$, the max sub-matrix sum can be found by using the 1D algorithm on the array (top to bottom):

\begin{pmatrix} 1-2+0 & = & -1 \\ 5+43+31 & = & 79\\ -45-12+19 & = & -38 \end{pmatrix} Does anybody know of a $\cal O(n^2)$ algorithm for solving this problem?

# Answer
> 2 votes
I found this: Sung Eun Bae, Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem. Read pages 18-30, where it says that there are just cubic $O(nm^2)$ and sub-cubic algorithms for this problem (in general case), for example Tadao Takaoka's $O\left(n^3 \sqrt{\frac{\log\log n }{\log n }}\right)$ algorithm.

I've also found a forum comment saying that this problem can be solved in $O(N^2\log N )$ for matrices with N non-zero elements using "funny" segment tree (you can ask commentator about details).

---
Tags: dynamic-programming, maximum-subarray
---


title: Generators of families of langauges?

text:
# Question
Title: Generators of families of langauges?
From Wikipedia's definition of regular langauges

> The collection of regular languages over an alphabet $Σ$ is defined recursively as follows:
>
> * The empty language $Ø$ is a regular language.
> * For each $a ∈ Σ$, the language $\\{a\\}$ is a regular language.
> * If $A$ and $B$ are regular languages, then $A \cup B$ (union), $A • B$ (concatenation), and $A^\*$ (Kleene star) are regular languages.
> * No other languages over$ Σ$ are regular.

The regular languages also form a (full) AFL.

Parallel to the concept of generator for a sigma algebra, do the regular languages form the minimal (full) AFL (or (full) semi-AFL, full trio, trio, ...) that contains the empty language, and $\\{a\\}, a ∈ Σ$? In other words, are the minimal (full) AFL (or (full) semi-AFL, full trio, trio, ...) generated by the empty language, and $\\{a\\}, a ∈ Σ$ exactly the regular langauges?

# Answer
For the sake of notation, let's call a family of languages $\mathcal{L}$ that contains

1. the empty set $\emptyset$ and
2. all singleton sets $\\{a\\}$, $a$ some symbol,

a *founded* family, and

$\qquad\displaystyle \mathcal{L}\_+ = \\{ L \in \mathcal{L} \mid \varepsilon \not\in L\\}$.

Let $L \in \mathrm{REG}\_+$ arbitrary. We will construct $L$ from only the empty and singleton sets using the trio operations

* $\varepsilon$-free homomorphism,
* inverse homomorphism and
* intersection with regular languages,

thus proving that (1) all founded trios also contain $\mathrm{REG}\_+$. Furthermore, (2) $\mathrm{REG}\_+$ it is a founded trio itself. Therefore, we have shown that $\mathrm{REG}\_+$ is the minimal founded trio.

---

1. It suffices to show that $\Sigma^+ \supset L$ is contained in every founded trio $\mathcal{T}$; the rest is trivial by $L = \Sigma^+ \cap L \in \mathrm{REG}\_+$.

We define for any alphabet $\Sigma$ a marked copy $\hat{\Sigma} = \\{ \hat{a} \mid a \in \Sigma \\}$ and two homomorphisms $h,g : \Sigma \cup \hat{\Sigma} \to \Sigma^\*$ by

$\qquad\displaystyle h(a) = \begin{cases} a &, a \in \Sigma \\ \varepsilon &, a \in \hat{\Sigma} \end{cases} $

and

$\qquad\displaystyle g(a) = \begin{cases} b &, a = b \in \Sigma \\ b &, a = \hat{b} \in \hat{\Sigma} \end{cases} $.

Now consider

$\qquad\displaystyle L' = \Sigma \hat{\Sigma}^\*$.

By noting that

* $\Sigma = h(L') \iff h^{-1}(\Sigma) = L'$,
    * $g(L') = \Sigma^+$ and
    * $g$ is $\varepsilon$-free,

we obtain from the trio closure properties that

$\qquad\displaystyle \Sigma \in \mathcal{T} \implies \Sigma^+ \in \mathcal{T}$.

But since $\Sigma$ is the pre-image of every $\\{a\\} \subseteq \Sigma$ with suitable constant homomorphism $h\_a(b) = a$ we have $\Sigma \in \mathcal{T}$ by foundedness and closure under inverse homomorphism.
2. We check the conditions of a founded trio for $\mathrm{REG}\_+$:

* Closure under $\varepsilon$-free homomorphism: clear since $\mathrm{REG}$ has this property and no such homomorphism can generate $\varepsilon$ from an $\varepsilon$-free language.
    * Closure under inverse homomorphism: clear since $\mathrm{REG}$ has this property and the image of $\varepsilon$ is always $\varepsilon$.
    * Closure against intersection with regular languages: clear by def.
    * Foundedness: clear by def; all required sets are regular and don't contain the empty word..

---

$\mathrm{REG}$ actually *is* the minimal "founded" trio if you add $\\{\varepsilon\\}$ to the base; a similar proof goes through.

Furthermore, $\mathrm{REG}\_+$ is *not* a full trio (cone) because of it's lack of empty words. We extend above proof by noting that containment of $\mathrm{REG}\_+$ now implies containment of $\mathrm{REG}$ (any regular language $L$ is the image of $\hat{a}L \in \mathrm{REG}\_+$ by a homomorphism that deletes only $\hat{a}$). Since $\mathrm{REG}$ is itself a cone it is also the minimal cone.

---

The properties extend to (semi-)AFLs, i.e. $\mathrm{REG}\_+$ is the minimal (semi-)AFL and $\mathrm{REG}$ is the minimal full (semi-)AFL.
> 6 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


title: Do RP algorithms exist?

text:
# Question
Title: Do RP algorithms exist?
I think I understand the RP complexity class (along with coRP, BPP, and ZPP). However, I can't seem to think of how an RP algorithm might be formulated.

How can the random coin flip possibilities allow for a guaranteed response of NO when the correct answer is NO, yet return with a probabilistic chance YES or NO when the answer is YES?

Are these actually algorithms we have examples of or is it just a theoretical class without any known examples? If there are examples, could someone please lay one out?

# Answer
> 5 votes
The algorithms you are looking for are also called one-sided-error Monte Carlo algorithms.

The idea is to randomly *guess* a witness for the input being a YES-instance. If you find one, your answer "YES" is always correct; if you don't find one, you say "NO" even though the correct answer may be "YES" (we want to restrict the likelihood of this event). If the input is a NO-instance we can never find such a witness, so we always output NO correctly.

One well-known example is the Solovay–Strassen primality test.

---
Tags: algorithms, randomized-algorithms, monte-carlo
---


# Question
Title: Embedding a general planar graph into a grid
I have here a little problem with my homework, and would appreciate some direction.

I am attempting for some time now to show that every planar graph is embeddable into a grid (As large as needs be).

I tried to make this argument inductively in many ways, but I am afraid that I don't see any good way to do that so far. My main problem is that while the subgraph may be embeddable in a grid, it might not still be possible to connect the relevant nodes to the nodes added in the inductive stage after the reorganization.

While writing this down, I thought of another possible solution which might solve it - observing the embedding to the plain as an embedding in the Cartesian plane, and moving every node to a "very close" point whose both coordinates are rational. Taking the greatest common denominator of all the coordinates, I believe that I'll find myself in a (huge) grid as required.

# Answer
There is a really neat result which answer's this question: Schnyder's Theorem. Another nice result is that of de Fraysseix, Pach and Pollack.

Here is a reference for both algorithms. The "Realizer Method" corresponds to Schnyder's Theorem and "Canonical Orderings" corresponds to de Fraysseix et al.'s approach.

These algorithms can embed any planar triangulation in an $O(n)\times O(n)$ grid. You can embed a planar graph $G$ by adding edges until you obtain a maximal planar graph $T$. Then you run any of these algorithms with input $T$. The output will be a drawing of $T$ in an $O(n)\times O(n)$ grid, which is also a drawing of $G$ in that same grid.
> 4 votes

# Answer
Do you know Fáry's Theorem? It proves that any planar graph has an embedding where each edge is a straight line. It's not too difficult to modify this to a grid, as you indicate in your last paragraph. I haven't tried it in detail, but I suspect the minutia would require a bit of care
> 2 votes

---
Tags: graphs, graph-drawing
---


# Question
Title: Choosing spanning trees to maximise node connectivity
Given: *n* variables in *X*, and *m* sets of variables where each set, *Ci* contains a subset of *X*. I am trying to generate the graph *G* = (*X*, *E*) by picking the edges in *E* given the following constraints.

* Variables in each set *Ci* must be connected by a spanning tree (no extra edges).
* The graph should prefer spanning tree configurations so that the variance of the degrees of all nodes is maximised.
* Following the previous constraint, prefer spanning tree configurations such that the degrees of nodes have greater variance, rather than average all around. So given the choice between configurations resulting in nodes of degree 1, 2, 3 vs 2, 2, 2. Prefer 1, 2, 3.

X = {x1, x2, x3, x4, x5, x6}

C1 = {x1, x2, x3}

C2 = {x2, x4}

C3 = {x4, x5}

C4 = {x3, x5, x6}

The optimal solution for the given variables is:

Each subset of variables Ci is connected by a spanning tree, and the degree of x3 is maximised. x3 has a maximised degree, and there are nodes with degrees of 1 (preferred).

There are a few things I am having trouble with.

1. Actually defining the problem: this graph is a constraint graph which is to be processed under some tree decomposition or cycle cutset algorithm. Variables in each set Ci share a common attribute. I am trying to remove redundant constraints so that I can get a favourable tree structure, under some ordering, for the next stage. I'm wondering if this preprocessing step is a known problem.
2. Efficiently implementing this preprocessing step. I am thinking that it may be able to be reformulated as trying to minimise the average all pairs shortest paths, and then if there is a tie, pick the one with the greatest variance. And if this is the case, whether there is an efficient algorithm to do this.

**EDIT**: A simpler example without cycles.

X = {x1, x2, x3, x4}

C1 = {x1, x2}

C2 = {x2, x3, x4}

There is a spanning tree between, x1 and x2 for C1.

This image shows the graph if I chose all the edges instead of just the spanning tree. It is undesirable as I am trying to minimise the edges, and there is an avoidable cycle.

If I didn't create the x2 to x3 edge, the graph would have the minimal edges satisfied, but not optimal as x2 has a degree of 2. When choosing to not create the x3 to x4 edge, x2 has a degree of 3.

If I summed the degrees in both cases they are 6. But the second case has a greater variance in the degrees (which is preferred). This is where the concept of dependency comes in, if x2 is removed in the second case, all other nodes are disconnected. In the first case, there would still be an edge between x3 to x4.

# Answer
> -1 votes
My suggestion would be to try simulated annealing. This looks like a good candidate for that heuristic. It sounds like you have some idea what the objective function you want to minimize is (that's good; you need one).

I would suggest that you use simulated annealing as follows:

* A state is a possible graph (a set of edges).
* The cost function for a state might be your objective function plus some penalty for the number of $C\_i$'s that aren't fully connected.
* To transition between states, you might randomly choose among the following options:

+ Add an edge chosen at random (or: choose a $C\_i$ that isn't fully connected, and add a randomly chosen edge between some pair of variables $C\_i$ that aren't currently in the same connected component)
    + Delete an edge chosen at random
    + Pick an existing edge $(u,v)$, delete the edge, then randomly choose some other variable $w$ that is in the same connected component as $v$ and add the edge $(u,w)$.

but of course you can play around with it and try different variations to see which works the best. This might just give you some reasonable solutions.

---

You could also try formulating this as a SAT or ILP instance, but my sense is that I would try simulated annealing first. If you're lucky, it just might work well enough that you don't need to bother with anything else.

---
Tags: graphs, spanning-trees
---


title: Compare runtime for algorithms?

text:
# Question
Title: Compare runtime for algorithms?
I try to compute the asymptotic runtime for this algorithm and compare it with other algorithm

$A = (C -(D * E ) ) mod p$

$ B = ((C * (D)^{-1} - (E * F ))$ mod p if we suppose each value A, B, C, D, E, F has O(log n) bit

My attempts were as follows

line one = $O(\log n)^2$ + log n

line two = $O(\log n)^2$ + $O(\log n)^3$ + $\log n$ + $O(\log n)^2$

Then line one + line two = $O(3\log n)^2 + O(\log n)^3 + log n$

Are attempts were correct or wrong. If it correct. can I say

T(line one + line two) = $O(3\log n)^2 + O(\log n)^3 + log n$

is better than

(Other algorithm) = $O(2\log n)^3$

# Answer
For your second question, whether a runtime of $O(3\log n)^2+O(\log n)^3+\log n$ is better than $O(2\log n)^3$, the answer is "asymptotically speaking, no". The dominant term in the first expression is $O(\log n)^3$ and the second expression is $8(\log n)^3$. Since, roughly speaking, big-O ignores constant multiples, the two expressions are asymptotically equivalent.

Your first question, whether your analysis is correct, can't be answered with certainty until you describe in more detail how you compute modular addition, multiplication, and inverse.
> 1 votes

---
Tags: algorithms, runtime-analysis
---