# Question
Title: Is there a basic proof that there exists some edit distance between two strings?
Title says it all pretty much. I do realize that often edit distance is defined as the minimum number of operations needed to transform one string to another, but I want something to point to that's even more general than that.

I recently saw a brain teaser that claimed that some string was connected in a network to another as "friends" given an edit distance of one. It then went on to claim that friends of friends, friends of friends of friends, etc. (with no given upper bound on the degree of separation), were also in the network of that original string. I can't see how this definition of network doesn't include every possible string, and so I think the brain teaser is ill-formed. Given sufficient edits, a string can transform to any other string, right? -- but is there a name for that observation? I think this is so fundamental as to be near-impossible to Google, but there is always the distinct possibility of me being an idiot.

# Answer
> 4 votes
Given two strings $v,w \in \Sigma^\*$ with $m = |v| \geq |w| = n$ (w.l.o.g.), align them like so:

$\qquad\displaystyle\begin{array}{ccccccc} v\_1 & v\_2 & \dots & v\_n & v\_{n+1} & \dots & v\_m \\ w\_1 & w\_2 & \dots & w\_n & - & \dots & - \end{array}$

This alignment implies an edit distance of

$\qquad\displaystyle 0 \leq d\_{\text{edit}}(v,w) \leq d\_{\text{Ham}}(v,w\[1..n\]) + (m-n)$.

In particular, there *is* an alignment for any two strings. Note furthermore that there are only finitely many alignments of $v$ and $w$ (we forbid columns $\genfrac{}{}{0pt}{}{-}{-}$), so one with minimal score (which is the edit distance) must exist.

Hence, any two strings have finite edit distance and the graph is connected.

# Answer
> 5 votes
There is trivially an edit distance between any two strings. The worst possible case is that you delete all of the characters of the original string, and then insert all the characters of the target string.

# Answer
> 1 votes
The Wikipedia page for edit distance discusses the fact that it is a metric and also gives some upper bounds http://en.m.wikipedia.org/wiki/Edit\_distance . For example LCS (longest common subsequence) which has only insertion/deletion operations is bounded by the sum of the lengths of the two strings, and Hamming distance (only substitution allowed, and defined for strings of the same length) will be bounded by the length of the string. The bounds are reached if the strings have no common letters. So yes, every two strings have a (bounded) edit distance. (The correctness of the algorithms computing minimal distances surely constitutes a proof of the existence of an edit distance for any pair of strings anyway).

Looking into the notion of metric/ metric spaces will give you the generalization you want.

---
Tags: strings, string-metrics, edit-distance
---


# Question
Title: NP-Complete algorithm defined on a fixed size array
Given an array, say A, with a finite definite length like N (e.g. 1000) can we define a problem to be NP-Complete without any intentional injection of NP-Completeness by something else :

for example questions like this are not acceptable:

"Solve this, NP-Complete, problem using A as an auxiliary array."

---

Please note that N is a predefined constant.

# Answer
If the entries of the array are from a finite domain $D$, then every problem (i.e. language) you consider, is restricted to a finite set of inputs, and is thus finite, and in particular, regular. So for this case, no. Nothing will be NP-complete (unless $P=NP$)

If the entries are unrestricted, for example if every cell can contain a number in $\mathbb{N}$, then looking at an array of length 1000 provides no restrictions. For example, you could consider the problem "Does the contents of the first cell, in binray, represents an encoding of a satisfiable CNF formula"?

This is just a rephrasing of the SAT problem, which is NP-complete.
> 2 votes

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


# Question
Title: Performance impact due to time required for shuffling in Quicksort
As a programmer with non CS background, I am learning algorithms.

When explaining the performance of quicksort in an Algorithm book and also elsewhere on the web, I do not see any reference to the time/space needed for shuffling. I *do* understand that shuffling is important to have the $O(n\log n)$ performance, but shuffling itself would have a complexity of $O(n)$. Why does this become irrelevant in the total performance?

# Answer
Here's a little more detail than Dave Clarke's answer.

Remember that $O(n\log n)$ means that there are constants $c\_1$ and $n\_1$ such that, for all $n\geq n\_1$, the running time of the sorting phase is at most $c\_1n\log n$ steps.1 Similarly, the running time of the shuffling phase is at most $c\_2n$ steps, for all $n\geq n\_2$. That means that, as long as $n\>n\_1$ and $n\>n\_2$, the total running time is at most $c\_1n\log n + c\_2n$. As long as $n\ge2$, $\log n\ge1$ (I'm assuming logs to base 2; if you want to take logs to some other base $b$, you need $n\ge b$), we have \begin{equation\*} c\_1n\log n + c\_2n \le c\_1n\log n + c\_2n\log n = (c\_1+c\_2)n\log n\\,, \end{equation\*} as long as $n\ge \max\\,\\{n\_1, n\_2, 2\\}$.

We conclude that the total running time is $O(n\log n)$.

---

1 Strictly speaking, this is something like the expected running time: as is well known, the worst-case running time is actually $O(n^2)$.
> 2 votes

# Answer
The short answer is that the $O(n\log n)$ component dominates the $O(n)$ component, hence the $O(n)$ part can be ignored in the statement of complexity.
> 6 votes

---
Tags: time-complexity, runtime-analysis, quicksort
---


title: Is my understanding of kernels correct?

text:
# Question
Title: Is my understanding of kernels correct?
System: Application

OS: Scheduler, VMM, IPC, FS Drivers, dispatchers, VFS

The above would be a monolithic kernel. In a monolithic kernel all core OS functions are separate from user spaaaaaace. Functions such as the FS are handled completely by the kernel. This leaves the end user/dev open to write applications that rely solely on the kernel to emulate and process the functions. The BSD tree, AIX, and HP-UX are good examples of monolithic kernels.

System: Application

User Mode: Application IPC, Unix Server, Drivers, File Server

OS: Basic IPC, VMM, Scheduling

This is a microkernel. A microkernel is responsible solely for physical emulation of the machine code. It provides a more secure functionality, but also allows for better hardware processing. User spaaaaaace is where drivers are handled, sometimes grating DMA. Also, it can improve computing processing time if the user spaaaaaace is streamlined for direct machine emulation. JXOS and various nanokernels are good examples.

System: Application

User Mode: Drivers, Unix Server, Application IPC

OS: Microkernel, Kernel Drivers, IPC, HAL

This is a hybrid kernel. A hybrid kernel is mix between a monolithic kernel and a microkernel. Software drivers are handled in user mode, but hardware drivers are handled by the kernel. This allows for a lot of flexibility in design, as some packages and application functions can run directly against the kernel. However, this leaves the kernel open to a lot of security vulnerabilities. The most well-known hybrid kernel is Windows NT.

My architect was testing my knowledge of kernels, and this is what I sent him. He said that I wasn't wrong, I just have a very different approach to it. When interrogated about it, he just told me it was different. How is it different? Does it look different?

# Answer
> 1 votes
Right as far as it goes, but the differences aren't *that* clear cut. E.g. in Linux (quite monolithic) you'll find FUSE (Filesystems in USErspace). In Unix (monolithic) the graphics system is X, and that one (while userspace) is (or was) granted direct access to interrupts and I/O under Linux at least. It is quite common to have IPC in userspace, while in Windows (was once a microkernel, now a strange hybrid) it is completely part of the sort-of microkernel.

Just for laughs, a while back the "monolithic" Linux kernel was *smaller* than the Mach "microkernel" alone...

---
Tags: computer-architecture, os-kernel
---


# Question
Title: How can I debug my pseudocode algorithm?
The algorithms for the problem I am working on become more and more complex as I try to improve their performance. They already span several pages with cases and sub-cases, and will probably become even longer. I am worried that there might be mistakes that are difficult to notice.

As a programmer, I am used to writing detailed test-cases to test my programs, but the algorithm is written in pseudo-code (it is not easy to implement). What ways can you recommend for testing the algorithm?

# Answer
> 7 votes
This is an excellent question: how do we know that a complex piece of mathematics is correct? The (by now) traditional point of view is that if we succeed in *proving* something then it must be correct. Unfortunately, this point of view is a tad naive. Indeed, published papers often contain wrong results, and these can remain unnoticed for decades. Some high-brow examples can be found in Voevodsky's talk, and this is a notorious issue especially in cryptography and distributed computing, two fields with extremely complicated definitions and proofs.

The most stunning example, however, must be the gap in the proof of the classification of finite simple groups: the result was announced in 1983, but only in 2004 did Aschbacher and Smith publish two monographs (!) covering one of the cases. In 2008 a further gap was filled by Harada and Solomon who found, quoting Wikipedia, "a case that was accidentally omitted". Should we believe the proof now, then?

Another problem which has seen its share of wrong proofs is the four color theorem. The first two proofs, dating to 1879 (Kempe) and 1880 (Tait), were found wrong in 1890 and 1891, respectively. In 1977 Appel and Haken announced a solution, containing a very length case analysis. It was not surprising, then, that a small error was found around 1986. While the error was corrected, doubts remained. The matter was finally put to rest in in the computerized formal proof by Gonthier et al. (2005), formalizing the earlier "second generation" proof of Robertson, Sanders, Seymour and Thomas from 1996.

What is a computerized formal proof? The idea is that if you had a *completely* formal proof of each and every statement, then as long as we trust our proof system, then we can be sure that the result is correct. (Unfortunately, as Gödel showed there is no hope in showing that the proof system is consistent, so this is an article of faith.) As Russell and Whitehead exemplified in their Principia Mathematica, writing formal proofs is difficult. Instead, the idea is to use a *proof assistant* which gets *hints* and converts them, somehow, to a formal proof which can then be independently checked. There are several of these proof systems around, but the most popular nowadays seems to be Coq.

What if the reviewers don't believe your proof? This is the situation that Thomas Hales found himself in after proving (or so he claims) the Kepler conjecture on sphere packing. The reviewers gave up after spending a year of reviewing, saying that while they were unable to find any mistake, they are not completely certain that the proof is correct. In response, Hales decided to formalize his proof, starting up the *Flyspeck* project, now in its eleventh year. In a few more years the proof would probably be complete. Clearly this amount of effort is unreasonable for the everyday mathematician.

Can proof assistants be improved? Voevodsky has been developing Homotopy Type Theory, a Coq overlay for algebraic geometry, and claims that he is using it daily to verify his proofs. Last year Gonthier et al. formalized the proof of the Feit–Thompson theorem in group theory in Coq, thus laying the ground for formalized group theory results. Yet even these projects are missing a lot of background which will be needed to formalize research in theoretical computer science. Even after such a framework has been developed, it will still be rather time-consuming to turn the commonplace sloppy TCS proofs into formal attire.

So what are you to do? In your particular case, you are designing an algorithm, so you have the distinct advantage of being able to *test* your algorithm. (The Curry–Howard correspondence shows that *every* proof corresponds to an algorithm, but in your case the relation is clearer.) Perhaps there is a trivial algorithm which is very slow, and you could compare it to your algorithm. Or perhaps it is an NP-type problem, in which the solution is easy to verify but hard to find.

Do people actually verify their algorithms usually? I doubt it, unless they are in a field such as computational geometry in which their algorithms are actually being used. What people usually do is *do their best to check their proofs*, crossing all *t*s and dotting all *i*s. That means avoiding phrases such as *it is easy to see that*. Having done that, they kindly ask a few other people to read through their proofs. Then they submit the paper to a journal, and if they're lucky then the referees will do another pass.

Even after all this, mistakes are occasionally found, but this is just part of life. Usually, these mistakes can be corrected easily, demonstrating that our formal sense of certainty is limited: true mathematics "works" even if not completely valid formally, as has been argued by a few philosophers, most of them coming from the ranks of practicing mathematicians. Wrong algorithms point the way to correct algorithms, as they bring new ideas. So don't worry too much, just do your best.

# Answer
> 2 votes
If you are working on "improving performance" of *pseudocode*, I'd tell you to forget about that. War stories of people optimizing the wrong part of a program are a dime a dozen. Perhaps the most hilarious one involved an early FORTRAN compiler for Unix. The programmer noticed a function he estimated would be called each 10 or so compilations, and took a week making it faster. The result was fast enough, and was shipped. This was still AT&T internal, so each time the compiler crashed the programmer got an email with the details. Some two years later, and a few million compilations, the compiler crashed in the "optimized" function. It turned out it would crash *each time it was called*. *Measure* before going on "improving performance". Programmers are normally wide off the mark on where the resources are spent. And it just might be that the straightforward code is performant enough, better spend your time at the beach (or wherever else you like). Performance improvements make the code harder to understand (and convince yourself/others it is correct!) and maintain, most "simpler" rewriting to get better code is done automatically by the compiler nowadays; and except for extreme cases your time is much more valuable than the computer's.

---
Tags: algorithms, software-testing
---


# Question
Title: Where should we place action symbols in a grammar?
In the following grammar that is used for math expressions(and other grammars) how do I know where should I place action symbols(@add, @mul, @pushID)? Is there a algorithm for it?

```
E -> TE`
E'-> +T @add E'|ϵ
T -> FT`
T'-> xF @mul T'|ϵ
F -> (E)|@pushID id

```

For example why @add is between `+T` and `E'` and not after `E'`? I searched for it's algorithm but didn't find anything useful.

# Answer
Generally, there isn't an algorithm for placing the action symbols. You always need logic in there.

In your case, you want to take the action @add right after you read the second operand of +. The derivations are leftmost, which means that the leftmost rules are going to be expanded and evaluated before the right rules. That said if you have an input of id1 + id2 * id3, the @add action symbol will be useful after id2 because up to then you have the two operands that you want to add. Exactly the same with the @mul, which is useful after id3.

Another issue is the precedence rules of the operations. We want multiplications execute before additions. The above example should be executed as id1 + (id2 * id3). Your grammar takes that into account :) . Let's see the syntax tree and I'm sure that will explain everything to you:

Now you can see the actual sequence of the rules, the precedence of Multiplication and why the position of action symbols isn't something fixed.

In another grammar, somebody would first read the id and after that have an action symbol to take it into the symbol table (usually in programming languages like Fortran).

Don't hesitate to comment me if I did not cover you.
> 3 votes

---
Tags: formal-grammars, compilers
---


# Question
Title: Permute the subintervals of an interval partition to most closely align with a model partition
You are given two things: A fixed initial 'model' partition of an interval, e.g.

```
I------I---I-----I-------I----...

```

where each `-` or `I` represents an element in a discrete time series and the `I`s are the partition boundaries. This can also be represented as a sequence of subinterval lengths, i.e. 7, 4, 6, 8, ...

Then, you're given a new set of subinterval lengths; and the task is to arrange these in such a way as to get as many coincident `I`s as possible. Or equivalently, you are given a new partition on an interval of the same length (though, critically, the new partition may have greater or fewer elements) and the task is to shuffle the subintervals around to maximize alignment. So if the model was

```
I------I---I-----I-------I----I

```

and you are given 2, 11, 5, 12, i.e.

```
I-I----------I----I-----------I

```

then the solution would be 11, 2, 12, 5,

```
I----------I-I-----------I----I
           *             *

```

achieving alignment at 2 locations (marked with an asterisk, compare to model).

There is an additional constraint: The locations of the aligned subintervals must be distributed approximately randomly throughout the length of the solution. The simplest means of getting a partition with at least some alignment to the model would be to build the new partition segment by segment, drawing without replacement from the collection of test segments, aligning where possible. But this would strongly bias the occurrences of alignment towards the beginning of the time series, and is therefore not allowed. There is of course also the brute force O(n!) enumeration but my series are little too long for that.

Naturally a solution that finds the optimal permutation would be great, but one that is efficient and gets a permutation with a substantial fraction of the possible alignment would also be good. My current version is a variation on the 'simple' algorithm derived above, except only drawing from a small subcollection of subintervals so as to avoid bias. I know it can be improved upon!

# Answer
You can use integer linear programming (ILP) to solve this. In particular, here is how to use an ILP solver to test whether there exists a way to permute the second partition so that you find $k+1$ alignment points (including the two endpoints). Given an algorithm for this decision procedure, you can use binary search to find the optimal alignment.

Call a "block" the (non-empty) sequence of consecutive intervals between two alignment points. The left and right endpoint of the interval are automatically alignment points. If there are $k+1$ distinct alignment points (including these two endpoints), there will be $k$ blocks.

Let $\ell\_1,\ell\_2,\dots,\ell\_n$ be the set of lengths of the first set of subintervals, and $\ell^\*\_1,\ell^\*\_2,\dots,\ell^\*\_{n^\*}$ be the lengths of the second set of subintervals. These are constants provided as input.

Introduce zero-or-one unknowns $x\_{i,j}$ (for $1\le i\le n$ and $1 \le j \le k$), with the intent that $x\_{i,j}=1$ means that the $i$th subinterval (of length $\ell\_i$) from the first partition will end up in the $j$th block. Similarly, introduce zero-or-one unknowns $x^\*\_{i,j}$, with the intent that $x^\*\_{i,j}$ means that the $i$th subinterval (of length $\ell^\*\_i$) from the second partition will end up in the $j$th block.

Now we get a set of linear inequalities, as follows:

* $\sum\_i \ell\_i x\_{i,j} = \sum\_i \ell^\*\_i x^\*\_{i,j}$, for all $j$. (This is two ways of representing the length of the $j$th block.)
* $\sum\_j x\_{i,j} = 1$ (each subinterval from the first partition ends up in exactly one block) and $\sum\_j x^\*\_{i,j} = 1$.
* $x\_{i,j} = 1 \land x\_{i+1,j}=0 \implies x\_{i+1,j+1} = 1$ (i.e., each block starts where the previous one ended). This can be expressed as the ILP constraint $x\_{i,j} - x\_{i+1,j} \le x\_{i+1,j+1}$. Similarly for the $x^\*$'s.
* $x\_{i,j} = 1 \land x\_{i'',j} = 1 \land i \< i' \< i'' \implies x\_{i',j}=1$ (i.e., the subintervals in a block are consecutive). This can be expressed as the ILP constraint $x\_{i,j} + x\_{i'',j} - 1 \le x\_{i',j}$ for all $i,i',i''$ with $i \< i' \< i''$. Similarly for the $x^\*$'s.
* $x\_{1,1} = 1$, $x^\*\_{1,1} = 1$, $x\_{n,k}=1$, $x^\*\_{n^\*,k}=1$.

Of course, in the worst case ILP can take exponential time, but ILP solvers are pretty good and often perform well on many real-world problems, so it is probably worth a try.

(You could also try coding this up using a SAT solver, but you'd need to implement arithmetic, so a front-end like STP would probably be a better bet than a plain SAT solver.)
> 2 votes

---
Tags: algorithms, permutations, partitions
---


title: Counting approximate solutions

text:
# Question
Title: Counting approximate solutions
Many of us are familiar with the $P$ class. Counting solutions is believed to be a difficult task and that is why we usually end up approximating the number of solutions (we relax the accuracy of the counting). I want to ask, if relaxing the quality of the solutions counted has been addressed as a problem. Is there for example, any algorithms able to answer the question: How many vertex covers there are, with 3 times the cardinality of the minimum vertex cover? Is the problem $P-$ complete?

# Answer
Let $(G,k)$ be an instance of vertex cover, where $G$ is a graph on $n$ vertices, and $k$ is the threshold. Suppose furthermore that the minimum vertex cover of $G$ has size either at most $k$ or at least $ck$ for some $c \> 1$; this version is already NP-hard.

Consider $n$ copies of $G$, with the addition of a clique of size $n^D$. If $G$ has a minimum vertex cover of size $\ell \leq k$ then the new graph has a vertex cover of size $n\ell+1$, and at most $\binom{n^2}{3nk+3} \binom{n^D}{2nk+3} \leq n^{(6+2D)nk + 6+3D}$ vertex covers of size $3(n\ell+1)$. If the minimum vertex cover of $G$ is $\ell \geq ck$ then the new graph has a minimum vertex cover of $n\ell+1$, and at least $\binom{n^D}{2n(ck)+3} \approx n^{2Dcnk+3D}$ vertex covers of size $3(n\ell+1)$. We can choose $D$ so that $2Dc \> 6+2D$, and then the gap between the two cases is roughly $n^{(2Dc-2D-6)nk-6} = e^{\Omega(n\log n)}$.

This reduction shows that it is NP-hard to approximate the number of vertex covers of thrice the minimum size within $e^{O(n\log n)}$. The interested reader can get even better results by slightly tweaking the construction.
> 5 votes

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


# Question
Title: Reconstruct directed graph from list of ancestors for each node
I have a problem that I encountered that boils down to the following:

Considered this directed graph I found on Google:

I have the following information available to me

```
Node: Ancestors

1 : 3
2 : 1 3 5 7
3 : Null
4 : 3 5
5 : 3
6 : 1 2 3 4 5 7
7 : 1 3
8 : 1 2 3 4 5 6 7

```

How can I re-construct the original graph in a reasonably efficient manner? I basically have large sets of data that I would like to have visualized as branches and merges(similar to a code repository, but not quite).

Note: While I believe my data shouldn't be disjoint, I'm somewhat certain my data is incomplete and will produce disjoint graphs, or at the very least have many separate "roots". There is no ordering to the data, everything must be considered random, the lists can also be thought of as sets.

# Answer
> 4 votes
Such a list can yield more than one graph. Consider `4: 1 2 3`, `3: 2 1`, `2: 1`. One graph is $1\to 2, 2\to3, 3\to4$. A second graph is $1\to 2, 2\to3, 3\to4 , 2\to4$.

# Answer
> 1 votes
A naive but simple solution that only works for a *complete* ancestor relation:

## Preliminaries

* Model:

+ A directed graph $G=(V,E)$ is isomorphic to a relation $R(G)=(V,\<\_{E}), u \<\_{E} v \equiv (u,v) \in E$.
    + The ancestor relation is the transitive closure of the relation $R(G)$ corresponding to your target graph $G$ (there are several candidates for $G$ which you have no informatio to distinguish between, see further notes in this section). In particular, for each pair $(u,w) \in R^{q+1}$, the closure relation contains $(v,w) \in R^{q}$ for each $(u,v) \in R$.
* Your graph must be directed (cf. comment by DavidRicherby), otherwise there is no unique solution. This shouldn't be a problem, as a graphical representation of timed branch and merge operations is cycle-free by nature.
* The graph to be reconstructed must not contain any forward (='shortcutting') edges . To see this, assume it does contain one such edge $e$. The ancestor relations of this graph ad the same graph with $e$ deleted are the same.
* The ancestor relation must be complete. Otherwise you wouldn't catch all forward (='shortcutting') edges in the ancestor relation's graph. You can compute the transitive closure of the ancestor relation beforehand, however, with Floyd-Warshall (sloppily phrased, the inversion of hte thinning operation). Thus you are guaranteed the correct result if your (incomplete) ancestor relation contains each predecessor relationship.

## Algorithm 1

Reconstruct $R$ by iterative thinning.

Setup a $n \\,x\\, n$-matrix $A=(a\_{ij})\_{i,j=1\dots }$ to represent the ancestor relation: $a\_{ij} = 1$ if $i$ is an ancestor of $j$, 0 otherwise. Copy $A$ into a new $n \\,x\\, n$-matrix $B$ and iterate over each tuple $(k,l,m) \in \\{1,\ldots,n\\}^3$. if $a\_{kl}=1, a\_{lm}=1$ and $a\_{km}=1$, set $b\_{km} := 0$. You'll end up with the adjacency matrix of your graph.

## Efficiency 1

This naive approach requires $O(n^3)$ due to the iteration over all tuples.

## Algorithm 2

This algorithm pursues the same idea more efficently at the cost of simplicity.

* Create the topologically sorted graph $G=(V,E)$ from the ancestor relation. In a nutshell this means assigning numbers from $\\{1,\dots k\\}, k \leq n$ as 'levels' to the nodes in the graph. the closer a node is to one of the graph's minimal elements, the smaller its level.
* Observation: if the absolute level difference (call that 'level distance', formally a mapping $d: E \to \mathbb N, d((u,v)) = |level(u)-level(v)|$ ) of the endpoints of an edge is 1, then this edge belongs to the target graph.
* Order the edges of the graph in a descending way according to the level distance of their respective endpoints.
* Iterate over this list. Let $e=(u,v) \in E$ be the currently inspected edge. iterate over all $w \in V: (u,w) \in E, d(u,w) = 1$ and $z \in V: (z,v) \in E, d(z,v) = 1$. if $(w,v) \in E$ or $(u,z) \in E$, delete $e$.
* You'll end up with the desired graph.

## Efficiency 2

* Topological sorting takes $O(|V|+|E|)$
* Edge sorting takes $O(|E| \log |E|)$.
* The iteration is bound by $(O(|V|\cdot |E|)$ (check $O(|E|)$ edges, at each check compute up to $O(|V|)$ immediate level predecessors/successors. The structure to access precisely these edges incident to a given vertex can be added during edge sorting at no extra cost).

---
Tags: algorithms, graphs, sets
---


# Question
Title: How to prove the following properties of Small-step semantics?
I have to prove the following 2 properties of the Small-step semantics of the WHILE programming language:

* If $\langle C\_1; C\_2, s\rangle \rightarrow^k s'$ then there is a state $s''$ and natural numbers $k\_1$ and $k\_2$ such that $\langle C\_1;s \rangle \rightarrow^{k\_1} s''$ and $\langle C\_2; s'' \rangle \rightarrow^{k\_2} s'$ where $k\_1 + k\_2 = k$.
* If $\langle C\_1, s \rangle \rightarrow^k s'$ then $\langle C\_1; C\_2, s \rangle \rightarrow^k \langle C\_2, s'\rangle$.

I am not quite sure which kind of induction I should use. I am not asking for a full proof, I would rather appreciate some hints on which kind of induction I should use in this case. Thanks in advance!

# Answer
> 0 votes
I suggest to proceed by induction on $k$. For the inductive basis and step you'll have to look at all the possible cases that the relevant reduction step $\langle C, s \rangle$ can be derived.

---
Tags: proof-techniques, operational-semantics
---


# Question
Title: Quantum algorithms and quantum computation
Is my (very high-level) understanding correct here regarding quantum algorithms —

Quantum computers can process a massive amount of operations in parallel to the nature of qubits and their ability to have states that are superpositions of $|0\rangle$ and $|1\rangle$.

Yet when we measure the qubits all the possible states collapse into a single state of either $|0\rangle$ or $|1\rangle$, which seems to negate the potential benefits of parallel operations. All we really know are the probabilities that the states will end up as.

However, we can exploit quantum properties to increase the probability that we end up with a certain result. I believe Shor's algorithm is based on exploiting quantum properties too, although I'm not sure in what way?

*e.g.* in a quantum walk, quantum interference means the walk spreads faster than a classical random walk and hence can out-perform classical walks.

That is my very high level understanding of what is going on with quantum algorithms. Am I correct, 'sort-of' correct, or way-off? Can someone clarify my understanding?

# Answer
> 7 votes
This is more-or-less a reasonable description of quantum computation. A few remarks are in order:

1. Regarding "quantum parallelism":

> Quantum computers can process a massive amount of operations in parallel \[...\] Yet when we measure the qubits all the possible states collapse into a single state of either $|0\rangle$ or $|1\rangle$, which seems to negate the potential benefits of parallel operations. All we really know are the probabilities that the states will end up as.

This description, as it stands, applies *equally well* to randomized computation. We don't assume that random bits have any special sort of state-space, of course — we can just flip coins rather than having to carefully manipulate ions, or photons, or what-have-you — but the mathematics behind probability distributions and quantum states are nearly identical. (Try out some computations involving probability vectors some time, replacing the unitary transformations with **stochastic** transformations.)
2. Regarding "quantum properties":

> However, we can exploit quantum properties to increase the probability that we end up with a certain result. I believe Shor's algorithm is based on exploiting quantum properties too \[...\] *e.g.* in a quantum walk, quantum interference means the walk spreads faster than a classical random walk and hence can out-perform classical walks.

We do increase the probability that we observe a given result — but this is a consequence of the fact that we *decrease* the probability of seeing *unhelpful* outcomes. Classical probability distributions "interfere constructively" too, though we just call it cumulated probability — one thing which is special to quantum computation is the fact that **destructive** interference (partial or total cancelling of amplitudes) occurs.

This can be seen as one of the reasons why quantum computation is more powerful: the existence of amplitudes which *would* cancel if you simply added them, means that amplitudes *sometimes do* cancel when the computation calls for transitions involving both of those amplitudes. This is something which simply doesn't happen with probability distributions — in fact, it doesn't even happen in nondeterministic Turing machines.

The trick, of course, is to find the particular ways in which you can conspire to have unhelpful outcomes partially cancel (or indeed, to determine which outcomes could be helpful to you, in order to arrange for the *other* outcomes to cancel). Simply recognising that amplitudes can possibly cancel is not in itself enough to figure out how to compute more quickly.
3. Regarding Shor's algorithm:

> I believe Shor's algorithm is based on exploiting quantum properties too, although I'm not sure in what way?

Shor's algorithm is an example of an algorithm which uses the quantum Fourier transform (or QFT), a unitary transformation which broadly speaking is helpful to find/expose periodic patterns. The fact that it can be performed unitarily means that certain simple periodic patterns which would otherwise be difficult to determine in a small number of trial calculations can be quickly discovered by looking at bulk properties.

Using QFTs to expose periodic properties is one particular trick in the bag of quantum algorithms; there are others as well.

---
Tags: quantum-computing, random-walks
---


title: Partition overlapping polygons

text:
# Question
Title: Partition overlapping polygons
On the following picture, we have overlapping polygons: we know the positions of vertices and the edges for each polygons, and the intersections are exactly known (vertices at the intersection are represented on the figure). Is it possible to 'partition' the domain spanned by the union of these polygons into 'disjoint' polygons (with contacts only at the boundary)? To be more precise, I'd like to associate to all edges the surfaces for which the edge is contained in its boundary.

Please advise if I'm not clear enough and thanks in advance for any suggestions!

# Answer
First algorithm that came into my mind:

```
P = initial set of polygons
for every pair (p,q) of polygons in P
  if p intersects q
    remove p and q and insert the three polygons that make up p union q
repeat until P can't be grown anymore

```

If vertices have integer coordinates. You can use a matrix $M$ (initially $0$) and use the following algorithm:

```
for every polygon
  for every point p = (x,y) in the polygon
    M[y,x] += 1

```

A disjoint polygon is then a contiguous sub-area of the matrix. The entries in the sub-area are all equal.

One way to speed up the first algorithm is first to compute AABB's for each of the polygons and use a quadtree or some BSP data structure.
> 1 votes

---
Tags: algorithms, computational-geometry
---


title: How to compute a curious inverse

text:
# Question
Title: How to compute a curious inverse
Let $M$ be a square matrix with entries that are $0$ or $1$ and let $v$ be a vector with values that are also $0$ or $1$. If we are given $M$ and $y = Mv$, we can computer $v$ if $M$ is non-singular.

Now let us take the second bit (from the right) of the binary representation of each $y\_i$ as another vector $z$. So $z$ also has entries which are $0$ or $1$. If $y\_i$ has fewer than two bits we just let $z\_i=0$.

> If we are given $z$ and $M$, how (and when) can you find a $v$ so that $Mv$ would produce $z$ under this operation?

Here is an example

$$M = \begin{pmatrix} 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1\\ \end{pmatrix} , v = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 1\\ \end{pmatrix} \implies Mv=\begin{pmatrix} 1 \\ 2 \\ 2 \\ 3\\ \end{pmatrix} .$$

So in this case

$$z = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 1 \\ \end{pmatrix}. $$

---

Is this problem in fact NP-hard?

# Answer
> 2 votes
This problem can be cast into a familiar form: it's an example of what is known as a *0-1 linear programming* problem. You have a set of variables $v\_1, v\_2, \dots v\_n$ subject to constraints of the form $m\le a\_1v\_1+a\_2v\_2+\cdots +a\_nv\_n\le M$. In your particular problem, we also have $a\_i \in \\{0, 1\\}$. You are looking for any *feasible* solutions, namely tuples $(v\_1, \dots, v\_n)$ which satisfy all the constraints.

For example, suppose we have $$ M = \left( \begin{array}{cccc} 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 \end{array} \right), \quad{\text{and}}\quad z= \left( \begin{array}{c} 0\\1\\0\\1 \end{array}\right) $$ then you want $$ v= \left( \begin{array}{c} a\\b\\c\\d \end{array}\right) $$ such that $Mv$ will be, in binary (with the lower-order bit unspecified) $$ Mv=\left(\begin{array}{c} c \\ a+b+d \\ a + b + c \\ b + c + d \end{array}\right) =\left(\begin{array}{c} \mathtt{0\\\_}\\ \mathtt{1\\\_}\\ \mathtt{0\\\_}\\ \mathtt{1\\\_} \end{array}\right) $$ From this we have the constraints $$ \begin{array}{c} 0\le a, b, c, d\le 1\\ 2\le a + b + d\le 3\\ 0\le a + b + c\le 1\\ 2\le b + c + d\le 3 \end{array} $$ and you want to find $a, b, c, d$ such that all the constraints are simultaneously satisfied. We've moved into 0-1 LP land because there are established procedures for solving problems like this, though sadly there's nowhere near enough room in this post to introduce them, so you'll have to do the legwork yourself. Be aware that problems like this are very compute-intensive (by which I mean NP-hard) and as far as I know you're not going to get anything like an elegant formulation of the form "This can be solved if and only if $z$ is of the form ..."

By the way, the example I used does indeed have a solution, $v$, and in this particular case is unique, though in general you'll have several solutions (if there are any at all).

---
Tags: algorithms, np-hard, linear-algebra
---


# Question
Title: What does Tarski's Fixed-Point theorem give us that that Y-Combinator does't
I'm taking a graduate course on the theory of functional programming, based on Paul Taylor's "Practical Foundations of Mathematics." I understand the statement of Tarski's theorem about how for any $\omega$-compelte poset $X$, and any $\omega$-continuous function $T:X\rightarrow X$, that $T$ has a fixed point which is the join of (The statement and proof can be found here).

What I want to know is, how is this applicable, other than being a proof that the Y-combinator exists? It just seems to me that it says "we can use recursion to build a function that is defined for all natural numbers", where we could use some other recursive type for numbers. Doesn't the existence of the Y-combinator show the same thing?

# Answer
> 9 votes
If by Tarski's fix point theorem you mean the Knaster–Tarski fixpoint theorem, then it's widely applicable and very general. All you need is a complete lattice and a monotone function on the lattice. There are many rather different examples of those. Tarski-Knaster is for example used in the coinductive definition of bisimilarity. Another application is to construct models of logical formulae (e.g. for logics with fixpoints, such as the modal $\mu$-calculus and the various fixpoint logics that are used to characterise complexity classes). It is also used in set theory and in program analysis.

The Y-combinator on the other hand is a specific piece of syntax in the $\lambda$-calculus. You don't need to prove the existence of the Y-combinator.

---
Tags: lambda-calculus, recursion, type-theory, partial-order, lattices
---


# Question
Title: grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)
Consider two sets: the set of validities of propositional logic and the set of validities of monadic predicate logic. Call the first set $VP$ and the second set $VQM$. Both of these sets are decidable, so there are Turing machines that recognize both them and their complements.

I'm interested in how the decidability of these two sets translates into grammars for them, along the lines of the Chomsky hierarchy. I have three questions:

(1) Are there context-sensitive grammars that generate $VP$ and $VQM$? The answer would be yes if the Turing machines that recognized these sets were linearly bounded, but I don't think they are.

(2) If these languages *aren't* context-sensitive, can *anything* be said about a grammar that generates them?

I would have a better grasp of the second question if I understood something about grammars *between* the top two levels of the Chomsky hierarchy, context-sensitive and unrestricted.

(3) There is a natural class of automata between linear-bounded Turing machines and unrestricted Turing machines: polynomially bounded TMs, exponentially bounded TMs, etc. Do these classes of TM track anything on the grammar side of the Chomsky hierarchy? If not, is there *any* structure to the gap between context-sensitive grammars and full-on unrestricted grammars?

(Just to be clear: I'm *not* talking about a grammar for propositional logic, but a grammar for its validities.)

EDIT: I thought I'd add a comment about why I'm interested in these questions. I know there is an unrestricted grammar that generates the (recursively enumerable but not recursive) set of validities of (full-on, polyadic) predicate logic. But since $VP$ and $VQM$ are not just recursively enumerable but recursive, I was wondering if the grammars that generate them might have more structure, in the Chomsky-hierarchy sense, than the grammar that generates the validities of all of predicate logic. **In other words, I'm wondering if there is a *grammatical* way of detecting the difference between sets of validities that are recursive (as in the case of propositional and monadic predicate logic) and sets of validities that are merely recursively enumerable.** What can be said about grammars of recursive but not recursively enumerable languages? Most references on the Chomsky hierarchy say nothing about this gap, but I don't know if that means there's nothing to be said.

# Answer
There is a linear space deterministic algorithm for deciding whether a given propositional formula is tautological. The algorithm goes over all truth assignments and verifies that the formula evaluates to TRUE under all of them.

Regarding monadic predicate logic, Lewis (journal version) determined that the nondeterministic *time* complexity is $2^{\Theta(n/\log n)}$, but I'm not sure if the nondeterministic *space* complexity is known. Perhaps you could sift through the papers citing Lewis.
> 1 votes

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


title: Algorithm to decide if $n \le m!$

text:
# Question
Title: Algorithm to decide if $n \le m!$
This is an assignment of an introductory course of complexity theory and I need to *find* a way to do the following:

Given $n,m \in \Bbb N$, is $n \le m!$ ?

The idea is to provide a **Post Machine** that can decide this in an *efficient way*, using $n,m$ in a binary codification.

We know that the factorial isn't efficient, so the problem actually is just to find a way to decide this, if it's possible.

I know how to compare if $n\le m$, but the factorial is my problem. **I don't how how to compute $m!$ with a Post Machine**, if possible, in polynomial-time.

I guess that the most simple way to do this is comparing $n$ with factorials of numbers that are lower than $m$, but the factorial it's still my problem.

My question, is there an algorithm that can help me?

# Answer
Here is a different solution than the one I suggested in the comments. Compute the sequence of factorials $1!,2!,3!,4!,\ldots$ until you get a number which is at least $n$. Since $(k+1)!/k! = O(\log (k!))$, you only compute numbers of magnitude $O(n\log n)$ and so of length $(1+o(1))|n|$ (here $|n|$ is the length of $n$ encoded in binary). Having found the least $k$ such that $n \leq k!$, we know that $n \leq m!$ iff $m \geq k$.

Since the sequence of factorials grows so fast, the running time isn't too bad — it's quasilinear in $|n|$ (at least in the RAM model). I'll let you work that out.
> 4 votes

---
Tags: algorithms, decision-problem, integers
---


title: number of different undirected graphs?

text:
# Question
Title: number of different undirected graphs?
The question is:

How many different undirected graphs are there with n nodes and no parallel edges but may include self-loops?

I've been wracking my brain over this for hours now. Basically, I know that for 1 vertex, there are 2 graphs. For 2 vertices, there are 8 graphs. For 3 vertices, there are 64 graphs. However, I can't connect these numbers without my answer for 1 vertices not working. For example, the equation number of graphs equals $2^{3n-3}$ works for 2 and 3 vertices, but not for 1. Any opinions on the connecting equation?

# Answer
> 4 votes
Undirected graphs with self-loops on $n$ vertices have $\binom{n}{2} + n = \binom{n+1}{2}$ potential edges. Therefore the are $2^{\binom{n+1}{2}}$ different graphs. For $n = 1,2,3,\ldots$, this is $$ 2^1, 2^3, 2^6, 2^{10}, 2^{15}, 2^{21}, 2^{28}, 2^{36}, 2^{45}, 2^{55}, \ldots $$

---
Tags: graphs
---


# Question
Title: Is it theoretically exist a computer that never affected by computer virus?
Is it theoretically exist a computer that never affected by computer virus?

just wonder if there could be a revolution on the computer?

# Answer
> 5 votes
Do you mean "that cannot be affected" or "that was never affected"? Then, under what conditions? Do you mean malware in general or a more restrictive notion of virus? And then, what is virus or malware? Is code for automatic update of your OS considered malware or not? Maybe you do not want to update your OS. Maybe someone has taken control of the updating service to introduce undesirable features in your system.

The main problem with your question is probably the word "theoretically". What is a theoretical computer? If it is a Turing Machine, the answer is clearly yes: they do what their finite control says they should do. Period.

Is there a fully precise theoretical model of a real computer. That is doubtful, if only because it is a complex physical objet and there is a limit to our ability to fully model such an object, since our knowledge of physics is not complete ... though I doubt that is the main issue.

Assuming we could completely model the physical computer with a formal system, do we fare better? Now we have (or shall have) all these great tools for proving theorems about computers and programs. But this has limitations too. Gödel says that not all true facts are provable, especially in a theory that can model that much computation. But even without falling in this black hole, do we fare better? No because before proving anything about the computer we need to model precisely what a computer is, and also what it means to be affected by a virus. Even if we have a perfect and total proof system (which we do not), how do we prove that our theoretical specification of the problem is accurate with respect to the physical problem with real computers. Bugs are not the exclusive privilege of programs and proofs, you can also have them in specifications, and some may be hard to eradicate. If your child *specifies* he wants a train as a gift when it is actually a car that he wants, what are the formal tools that will identify the specification error - short of implementing and observing that things do not behave as expected.

Coming back to a more practical view. Some machines are harware protected with encryption keys that allow only trusted software. First, many people consider this as malware by itself, as it is often used against the owner of the computer. Then encryption can be broken by mathematical or social means. And the protection may possibly also be circumvented by other means.

A computer that stays off-line and does not access foreign data is unlikely to be affected. Then, there are different ways of accessing foreign data that may be more or less risky. Using foreign code is likely to be more risky. So the question cannot be independent of defining the conditions in which the computer is used.

However, even off-line, there is always the risk that the computer was born affected by malware (to avoid the restrictive concept of virus).

You should read Ken Thomson's 1984 Turing lecture: **Reflections on Trusting Trust**.

Either you trust others to some extent, or you rebuild most of the technology from scratch by yourself, with no interference from others. May be not starting at stone age, but far enough ... assuming you do not have bugs in your own code (but if not intentionally malicious, they are less likely to be as much a problem).

# Answer
> 2 votes
I believe No.

With my knowledge about new generation malware those are "metamorphic and polymorphic" in nature change their code as they propagate. I think no such machine can be possible to make (even theoretically) that can detect all possible variants of a malware.

Below I try to justify. I hope my answer help you up to some extend.

**What is metamorphic malware?:** To change code structure at each infection metamorphic malware employee the Mutation Engine (black-part) that use obfuscation techniques like: garbage code insertion, register/variable usage exchange, instruction replacement, instruction permutation, code transposition etc. You can picture it as below:

Source of Image: Momentum

Change in order of color represents 'instruction permutation', change in size shows insertions/deletion 'garbage code instruction', I didn't shown cnage in color (you can find in next-slides) show will represent code tranformation e.g. $MOV a, b$ can be replace by $PUSH b$ followed by $POP a$.
Malware Obfuscation Techniques: A Brief Survey

**\[ANSWER\]**

So theoretically, a new generation malware can change their structure arbitrarily complex way and can avoid detection (this problem is like compare two codes those instructions are different but perform same behaviour -- and that is unsolvable).

> ### Code obfuscation techniques for metamorphic viruses, Journal in Computer Virology
>
> “… we prove that reliable static detection of a particular category of metamorphic viruses is an NP-complete problem. Then we empirically illustrate our result by constructing a practical obfuscator which could be used by metamorphic viruses in the future to evade detection…”

This implies that we can't make a signature based antivirus that can't detect all possible varients of a malware efficiently (I have played with more than 2500 malware samples with 14 antivirus and no one could detect more than 76% malwares).

Now other techniques are "dynamic" analysis and detection. Read Ether: Malware Analysis via Hardware Virtualization Extensions ACM CCS 2008: "Dynamic analysis of malware itself a open problem because of limited test coverage. Malware may evade detection and analysis by simply not performing malicious behaviour during the dynamic analysis (it may stay inactive until certain condition satisfy)". You can read also 6 Antivirus Open Problems.

One point to keep in mind the new generation malware are complex and hide their malicious code in encrypted form (there are key encryption techniques those are irreversible without decryption key). So malware carries both legitimate and malicious behaviour.

Dynamic behaviour itself depends on dynamically input values (domain of input is infinitely large) so making all possible test-cases are impossible. Remember we having debugging tools but none-of-debugger runs automatically, we have to explicitly apply intelligent to debug codes. So I believe via dynamic analysis even theoretically still detection of malware is impossible.

Any detection technique either dynamic or static try to find similarity between signature (one program's behaviour or some part of code) and a malware thread (other program target). And as we know "the problem whether or not two Turing machines accept the same language is unsolvable.". That I implies that we can write a general solution of detecting new generation malware. A general solution is possible when you have arbitrary infinite signature repository to identify arbitrary any form of malware's variant.

---
Tags: terminology, security
---


# Question
Title: Reduction from Partition problem to 3-Partition problem
I'm trying to show how to reduce the Partition problem to the 3-Partition problem.
I'll first describe the problem using the definitions and notations I'm familiar with (I hope they're legit), and will then ask my question.
So, the Partition problem is as follow:
Given a multiset of integers $X$, we have to decide whether or not $X$ can be **partitioned** into two sub-sets $A,B$ such that $\sum\_{x\_i\in A}x\_i=\sum\_{x\_i\in B}x\_i$.
In the 3-Partition problem, given a multiset of integers $Y$, we have to decide whether or not $Y$ can be **partitioned** into **three** sub-sets $A,B,C$ such that $\sum\_{x\_i\in A}x\_i=\sum\_{x\_i\in B}x\_i=\sum\_{x\_i\in C}x\_i$.

I want to show a reduction $Partition\leq \_p 3Partition$, That is, to show that given $X$ as input for the Partition problem, I can build $Y$ as input for the 3-Partition problem, s.t. $X$ can be partitioned to two iff $Y$ can be partitioned to three.
So given $X$, let $\sum\_{x\_i\in X}x\_i=m$, and define $Y$ as:
$Y=\left \\{ x\_1, x\_2,...,x\_n,\frac{m}{2}|x\_i\in X \right \\}$.

Proof:
The first direction is easy: suppose that $X$ can be partitioned to two sub-sets $A,B$ s.t. the above conditions hold, then $Y$ can be partitioned to three: $A,B,C$, while $C=\left \\{\frac{m}{2} \right \\}$.
I'm stuck with the second direction: suppose that $Y$ can be partitioned to three, **why does that guarantee that $X$ can be partitioned to two?**

b.t.w, how can I be sure that $\frac{m}{2}$ is an integer? do I even have to pay attention to it?

# Answer
> 4 votes
To answer your bolded question: The sum of the numbers in $Y$ is $\frac{3m}2$. Thus $A$, $B$, and $C$ each need to be of size $\frac m2$. This can only be achieved by partioning as in the first direction.

Regarding your second question: You can not be sure that $\frac m2$ is an integer and you have to pay attention to it, in order to get a formally correct reduction.

The easiest way to address this is by having your reduction function distinguish two cases: If $\frac m2$ is an integer, it proceeds as you describe. If $\frac m2$ is not an integer, it exploits the fact that in this case the answer to the original question ("Can $X$ be partitioned?") is easy. I'll leave it as an exercise to figure out the details of this case.

---
Tags: reductions
---


# Question
Title: Are instructions defined as expressions with side-effects?
Can we define instructions as expressions with side-effects?

# Answer
> 1 votes
The answer is no. But this is hardly enough.

I think you put your finger on a slightly sore but important point of computer science and programming. We can pretty well define what is an expression because that is well formalized in mathematics. But we somehow wave our hands on what constitutes the essence of instructions, or side-effects. "Side-effect" is itself a strange word, with an almost negative connotation, which says a lot about mixed feelings on the issue. I do not mean that instructions have not been well formalized with precise semantics (they have), but they often seem perceived more as a necessary evil than as a desirable tool. And this is not easily explained. Maybe it is that, unlike expressions, they do not have an obvious counterpart in mathematics. There may be other issues.

But let's try to see the difference.

Mathematically, expression are precisely defined syntactic structures, often called well formed formulae. From a computational point of view, these expression are operateur operand structures, that are interpreted in some domain of value (for operands) and of functions (for operators). And an expression is just supposed to apply the functions to the values in the order specified by the structure and come back with the result (this is pretty close to the abstract mathematical notion). As in mathematics, a function is supposed to be just a mapping, giving a result in a given range.

I would define an instruction as a syntactic writing meant to specify a modification in an environment. What then is an environment? An environment is something that can be modified, and that can thus memorize information (I should add transmit information, but let's stay simple). A typical and very simple environment is the state of the finite control of a Finite Automaton (FA). It can be changed, and the change is memorized and can be used later on. A transition of a FA is an instruction, since it changes the environment. In the case of a Turing Machine the environment is constituted of the state of the finite control, the tape content, and the position of the head on the tape. The **content of the environment** is precisely what is often called an **instantaneous description** of an automaton.

Since **a side-effect is a modification of an environment**, one could say that **an instruction is a syntactic structure meant to specify a side-effect**.

Note that the concept of environment (thus of side-effect) is itself relative. It may be internalized so that we do not even have to know it exists. For example, the evaluation of an expression may be done by a device operating with a succession of instructions modifying a small environment, until the end result is obtained. The modifications and the environment itself can then be forgotten, and only the result is kept. There may have been temporary "local" side-effects, but they are irrelevant outside the evaluation of the expression. That is actually what happens in the computer. But we still say that the evaluation of the expression has no side-effect (none remains).

An environment can include places to store values (what is usually called a variable). An instruction may be an assignment of a value in some variable, and the value itself may be specified with an expression. Conversely, the expression can include variables, and is evaluated by replacing the variables by their current value in the environment. So the two concepts interact, and are really two faces of a computational coin.

Note in passing that we have considered that some environments are more transient than others (for evaluating an expression). That means that we may actually consider many environments. Managing environments is actually a major issue in programming language design, and in programming, particularly to make side-effects as transient as possible to make program analysis and maintenance easier.

Coming back to our computational coin, the two faces appear in various guises:

* denotational semantics vs operational semantics;
* lambda-calculus, combinatory logic or recursive funtion theory vs Turing Machines, automata and rewriting systems;
* evaluation of expressions vs execution of instructions;
* functional programming vs imperative programming;
* regular expressions vs finite automata.

Sometimes, the same text can allows both readings. A context-free grammar can be seen as a set equations between expression valued in sets of strings (denotational view) or as a string rewriting system (operational view).

Of course, in programming languages, things are made more complicated by the mixing of expressions and instructions. Instructions use values that are obtained by evaluation expressions. That is not too bad. What is worse is that the evaluation of some expressions may cause side-effects. This is because programming languages often allow implementing functions with instructions as described above, but without restricting the side-effects to a local environment that disappear when the function terminate.

It may also happen that a function will not always return the same result when called with the same arguments, because it uses internally values provided by an outer environment that may be subjected to side-effects. Though it is sometimes put to good use by programmers, this may be a reason for the distrust of side-effects, as it seems to depart from our mathematical understanding of functions.

---
Tags: programming-languages
---


title: Solving System of Equations

text:
# Question
Title: Solving System of Equations
(Re-posted from StackOverflow as suggested)

I have the following problem.

The functions $f(x),g(x)$ are defined as $$ f(x) = \begin{cases} f\_1(x) & 0 \leq x \leq 10, \\ f\_2(x) & 10 \< x \leq 20, \\ 0 & \text{otherwise}, \end{cases} \qquad g(x) = \begin{cases} g\_1(x) & 0 \leq x \leq 5, \\ g\_2(x) & 5 \< x \leq 20, \\ 0 & \text{otherwise}, \end{cases} $$ In addition, we require the constraints $$ \int\_0^{20} f(x) dx \geq K, \quad \int\_0^{20} g(x) dx \geq Q, \quad f(x)+g(x) \leq R \text{ for all $x$}. $$ where $K,Q,R$ are parameters.

I assume there is quite some elaborate theory behind it, and was wondering if anybody could point me in the right direction to devise an algorithm that can generate $f\_1(x), f\_2(x), g\_1(x), g\_2(x)$?

I would like to add that for a given $K$ and $Q$, the interest is to keep $R$ as low as possible.

# Answer
Let $X$ be a random variable distributed uniformly over $\[0,20\]$. Your constraints imply $$ \mathbb{E}\[f(X)\] \geq \frac{K}{20}, \qquad \mathbb{E}\[g(X)\] \geq \frac{Q}{20}. $$ We conclude that $$ \mathbb{E}\[f(X)+g(X)\] \geq \frac{K+Q}{20}, $$ and so there is some point $x \in \[0,20\]$ such that $f(x) + g(x) \geq (K+Q)/20$. In particular, $R \geq (K+Q)/20$. This bound is tight, as shown by the functions $$ f(x) = \frac{K}{20} \mathbf{1}\_{x \in \[0,20\]}, \qquad g(x) = \frac{Q}{20} \mathbf{1}\_{x \in \[0,20\]}. $$
> 1 votes

---
Tags: algorithms
---


# Question
Title: Number of descendants of each node in a DAG
1) Is there a better algorithm than the naive O(|E|.|V|) to compute the number of descendants of each vertex in a DAG?

2) Is there an online algorithm to do so, assuming that nodes are added one by one and connect to a non empty subset of the existing nodes?

Context: I'm interested in the case where m = O(n), millions of vertices, tens of millions of edges typically. Alternatively, counting the number of descendants which are also sinks would be useful.

---

A probabilistic approach would be min-hashing, as a way to represent the set of descendants of every node. The union of the min-hash structure is trivial, and the cardinality of the union can be estimated from the number of coincidences in the min-hashes.

However, I'm not sure how well behaved that would be when propagating up the DAG, intuitively it looks like errors would compound pretty fast.

---

Very related: https://cstheory.stackexchange.com/questions/553/what-bounds-can-be-put-on-counting-reachable-nodes-in-a-dag And actually a duplicate of: https://cstheory.stackexchange.com/questions/18787/what-is-the-fastest-deterministic-algorithm-for-incremental-dag-reachability

# Answer
1. Topologically sort the nodes in your DAG.
2. For each node `N`, set `N.QueryCount = 0`.
3. For each node `N`, in reverse topological order:
    * Set `N.Descendants = {N} U {C.Descendants | C in N.Children}`.
    * Yield `(N, N.Descendants.Count)` from the algorithm.
    * If `N.Parents` is empty, you can dispose of `N.Descendants`.
    * For each `C` in `N.Children`, increment `C.QueryCount`. If `C.QueryCount == C.Parents.Count`, you can dispose of `C.Descendants`.

This of course is expensive if your node degrees are large. Worst case complexity may not be significantly better than your unspecified "naive algorithm."

The issue is that this is a very difficult problem to solve. Suppose there is a DAG with millions of nodes, millions of edges, etc. I show you this portion of the graph:

```
A--> B
 \-> C

```

How many descendants does `A` have? The number of descendants of `B` plus the number of descendants of `C` minus the number of common descendants of `B` and `C`. It's the third term that creates the difficulty. You can't know just the number of descendants of `B` and `C` \- you need to also know what the descendants are.
> 5 votes

# Answer
Listing all the descendants of all vertices can produce output of the size `O(n²)`, for example if the graph is a linear graph then the vertex without incoming edge has `n - 1` descendants, the following vertex `n - 2` and so on.

This leaves the question if you can determine the number of descendants without enumerating them. I can not give a proof but I am pretty confident the answer is no. Assume a vertex `x` has children `u` and `v` then you have to find the cardinality of the intersection of the sets of descendants of `u` and `v` but there is just nothing you know about that set - `u` and `v` may not share a single descendant or they may have the same set of descendants.
> 2 votes

---
Tags: graphs
---


# Question
Title: Edges in and out of cycles and their relation to connectivity of the graph
We know that if an edge is a part of a cycle in an undirected connected graph $G$, then if we remove that edge the graph is still connected.

Is the opposite true? If an edge is **not** a part of a cycle in a connected graph $G$, and we remove that edge, then the graph we get is disconnected?

P.S.: I think that it is true, and the direction for a proof is to look at one vertex it connects, and the edges that connect the vertices with it as on component, and the other end as another component, and showing that if we cut out that edge, we get two components, such that the graph is not connected. What do you think?

# Answer
Yes. Let $G$ be a graph, and suppose that the edge $ij\in E(G)$ is not on any cycle. This implies that every path $P$ from $i$ to $j$ in $G$ uses the edge $ij$, since, otherwise, $P\cup \\{ij\\}$ is a cycle in $G$. In particular, removing $ij$ from $G$ disconnects $i$ from $j$.

These kinds of edges are called bridges.
> 5 votes

---
Tags: graphs
---


title: Automatic seat assignment algorithm

text:
# Question
Title: Automatic seat assignment algorithm
I am looking for articles relating to algorithms that deal with automatic selection of seating assignment. I need an algorithm (preferably more than one) that can automatically select a seating place while enforcing certain constraints that are predefined. Originally I was planning on having the seats selected on the fly, meaning whenever a new person comes, the system selects the optimal seat for him based on the seats which were already taken, but I guess it is not a must. if there is a more general algorithm that can also present an approach fit for my problem that is also great.

Lets call the seated people "players" , and our seating domain lets picture as a 2d matrix. lets say we have several groups among our "players" and you can set your "players" anywhere within the matrix as long as they are not seated next to other "players" from their own group . I am not claiming there is a perfect solution, I am looking for articles that are dealing with some approach for giving a solution - if you can direct me to an article or even give me a name for that kind of problem it is also good for me.

Thanks, Olaf

# Answer
You could start your investigation from an online bipartite matching \[PDF\] point of view.

In specific, in this case, you know one side of the bipartition, namely the seats and their properties, and then you will get orders on-the-fly (online). The performance you are looking to analyze is the number of matched buyers in the online algorithm versus the number of matched buyers if you'd know the buyers in advance (offline).
> 1 votes

---
Tags: algorithms, optimization
---


# Question
Title: I need clarification about DFA's and DFA acceptable languages
In class yesterday we went over DFA's and DFA acceptable languages. An example of a language that is not DFA acceptable was given as $\\{ ab, aabb, aaabbb, aaaabbbb, \ldots \\}$. The reason given was that the machine would need an infinite amount of states.

But wouldn't a simple DFA that has only one state that is a final state and loops back to itself on all inputs accept that language?

Also in class we discussed how the complement of a DFA acceptable language is also DFA acceptable simply by swapping the final states and the non-final states. But if you had the language $L = \\{ a \\}$, over the alphabet $\\{ a, b \\}$, then obviously $L$ is DFA acceptable, but the complement of $L$ is $\\{ a, b \\}^\* - \\{ a \\}$, which includes $\\{ ab, aabb, aaabbb, \ldots \\}$.

I think I must be misunderstanding something crucial here.

# Answer
> 5 votes
> $Doubt-1$: "But wouldn't a simple DFA that has only one state that is a final state and loops back to itself on all inputs accept that language?"

No, the DFA you are thinking about as below: accepts $(a + b)^\*$ that is "all possible string consists of symbols '$a$' and '$b$', including $ε$ string".

```
     __
     ||  a, b
     ▼|
––►((Q<sub>0</sub>))

<sub>Q<sub>0</sub> is both initial and final state</sub>

```

Language accepted by this DFA is superset of language $L = \\{ a^nb^n$ | $n \> 0 \\}$ and hance also accepts all strings in $L$.

The concept you are missing is: "An automata $A$ for some language $L$ must accept $\textit{exactly}$ language $L$, neither a subset nor a superset of $L$".

Hance DFA above is not a finite representation of language $L = \\{ a^nb^n$ | $n \> 0 \\}$.

> $Doubt-2$: "Also in class we discussed how the complement of a DFA acceptable language is also DFA acceptable simply by swapping the final states and the non-final states".

**Note**: To construct new complement DFA $D$, old-DFA $A$ must be a complete, means there should all possible outgoing edge from each state (or in other words δ should be a complete function). Read "Complement DFA for Regular Expression $(00 + 1)^\*$" to learn how to consturct complement DFA.

> $Doubt-3$: But if you had the language $L = \\{ a \\}$, over the alphabet $\\{ a, b \\}$, then obviously $L$ is DFA acceptable, but the complement of $L$ is $\\{ a, b \\}^\* - \\{ a \\}$, which includes $\\{ ab, aabb, aaabbb, \ldots \\}$.

As you already know complement of a regular language is regular (DFA exists for regular language and you know how to make DFA for complement regular language), so new language $L^" $ = $\\{ a, b \\}^\* - \\{ a \\}$ is a regular language.

And language $L^" $ is a superset of language $\\{ a^nb^n$ | $n \> 0 \\}$.

The concept you are missing is that you don't know:

> $Doubt-4$: *"What is called regular language?"* And Why a languages like $(a + b)^\*$ is regular? But language $\\{ a^nb^n$ | $n \> 0 \\}$ is *not* a regular language\**

A language (a set) $L$ is called Regular Language, if its require bounded (finite) amount of information at any instance of time while processing a strings in language $L$.

**What is *bounded* information?**
For example: Consider a fan switch for `on-off`. By viewing fan-switch we can say whether fan is in `on` or `off` state (this is bounded or limited information).
But we can not know that how many times a fan has been on-off in past! (to memorized, it requires a mechanism to store *unbounded* amount of information to count how many times – e.g. some kind of meters, we have in our car/bike).

To understand how states are uses as memory element read this answer, you may also like to read: How to write regular expression for a DFA

Language $\\{ a^nb^n$ | $n \> 0 \\}$ is **not** a regular because here $n$ is unbounded. To verify string in language $a^nb^n$ we have to remember how many '$a$' has been came and this required a infinite memory to count because number of '$a$' s in string that can be infinity large.
(hence an automata can only capable to process strings of $a^nb^n$ if it has infinite memory e.g PDA).

Whereas $(a + b)^\*$ is of-course a regular by its nature, because there is bounded restriction that "string consists of only symbol '$a$' and '$b$'". And strings of this language can be easily processed (or recognized) by an automata in which we have finite memory that is **finite automata**. Yes, in finite automata we have finite memory in terms of states (The word "Finite" significance of the presence of 'finite amount of memory' in the form of finite number of states $Q$).

Summarize:

*Memory in finite automata is present in the form of states $Q$ only and according to automata principal: any automata can have only finite set of states. hence finite automata has finite memory, this is the reason automata for regular language is called finite automata. You can think a finite automata like CPU without memory, that has finite register to remember its internal states*.

Finite State –► Finite Memory –► Only language can be process for which finite memory need to store at any instance of time while processing the string: –► that language is called Regular Language

Absence of external memory is limitation of finite automate –► or we can say limitation of class of language defined by finite automata that is called Regular language.

**Side note:**:
* Also a language { anbn | 10\>100 n \> 0 } is regular, a large set but regular because $n$ is bounded, hence finite automata and regular expression is possible for this language – finite set is always regular. * There are infinite sets those are regular. Regular language of subset of all possible infinite set. Check this Venn-diagram.

So, if any time you need to proof that a language $L$ not a regular – before the go to use "formal tools" likes pumping lemma, first try to proof using fundamental definition of regular language.

# Answer
> 1 votes
Let me summarize the answers given in the comments to the question.

An automaton $A$ accepts a language $L$ if it accepts each word in $L$ and rejects each word not in $L$. Each automaton $A$ accepts a unique language $L$ which consists of all words accepted by $A$. Therefore, while the one-state automaton accepting $\\{a,b\\}^\*$ does accept all the words in $L = \\{a^n b^n : n \geq 0\\}$, it does not accept $L$ since it also accepts other words such as $b$.

For completeness, here is the proof that an automaton for $L$ would require infinitely many states, or more formally, that no DFA accepts $L$. Suppose there was some DFA $A$ accepting $L$. Let $s\_n$ be the state that $A$ is in after reading $a^n$. I claim that $s\_n \neq s\_m$ for all $n \neq m$. Indeed, starting at $s\_n$ and reading $b^n$, the automaton $A$ ends up in an accepting state since $a^n b^n \in L$. If $s\_m = s\_n$ then this means that $A$ would accepts $a^n b^m \notin L$. This contradiction shows that $s\_n \neq s\_m$ for all $n \neq m$, and so $A$ must contain infinitely many states, which it can't since DFAs have finitely many states. So no DFA accepts $L$.

For a generalization, check out the Myhill–Nerode theorem.

# Answer
> 1 votes
Acceptance of a Language $L$(regular): means there is a finite accepter that accept all strings $w$ belongs to L and reject all strings not in $L$.

An example of a language that is not DFA acceptable is $L=\\{ab,aabb,aaabbb,aaaabbbb,…\\}$.The question is why: there can be a finite accepter for all the strings w belongs to L but that finite accepter can also accept those strings that do not belong to L. So according to the definition of acceptance, there can't be a finite accepter for $L$.

Finite accepter (DFA and NFA) can't accept these language because to accept these kind of languages the machine need infinite memory to store number of $a$'s and $b$'s(Since number of a and b is unbounded, we require storing an unbounded amount of information). But Finite automata do not have temporary storage capability. There is a more capable Automata named Pushdown Automata that can recognize this language.(This language is known as context free language)

The language $L=\\{a\\}$ is definitely DFA acceptable because there can be a finite accepter that only accept the string $a$. But complement of $L$ not only includes $ab,aabb,aaabbb,…$ these strings. It also includes strings $b$, $aab$, $abb$,$aabbb$ etc. And simply by swapping the final states and the non-final states of the DFA for $L$ you can get a finite accpter that accepts the language which is complement of $L$ .

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


title: NDFA associated with language L

text:
# Question
Title: NDFA associated with language L
Let A = $(Q, \Sigma, \delta, S, F)$ be a deterministic finite automaton associated with the language $L \subseteq \Sigma^\*$

> $L' = \\{y \in \Sigma^\*:\exists x\in L. |x| = |y|\\}$
>
> $L \subseteq L'$

How do I show that there exist a NDFA associated with L' ?

# Answer
Hint: Replace every transition labelled $a \in \Sigma$ with a transition labelled $\Sigma$.
> 3 votes

# Answer
Here is a proof using the closure properties of regular languages. Let $\pi: \Sigma^\* \to a^\*$ be the monoid homomorphism defined by $\pi(u) = a^{|u|}$. I let you verify that $L' = \pi^{-1}(\pi(L))$. Since regular languages are closed under homomorphisms and inverses of homomorphisms, $L'$ is regular.
> 2 votes

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


# Question
Title: Sub language is not Turing-recognizable, or could it be?
Let A and B be languages with A ⊆ B, and B is Turing-recognizable. Can A be not Turing-recognizable? If so, is there any example?

# Answer
> 18 votes
This is something that confuses many students. The point here is that being subset of another language does not imply much about their difficulty of computation. You can always consider the trivial language $\emptyset$ and $\Sigma^\*$ and any other language is between them w.r.t. set inclusion.

Therefore just knowing that a language contains or is contained in a easy to compute language doesn't say anything about the difficulty of computing it.

# Answer
> 1 votes
When a Turing-recognizable language $X$ is *not* decidable, it implies that it is not co-Turing-recognizable (in other words: $X^c$ is not recognizable). Since $X^c$ is a perfectly valid subset of $\Sigma^\*$, this supports the fact that for a language $A \subseteq B$ where $B$ is Turing-recognizable, $A$ may very well not be.

# Answer
> -2 votes
Your discussion successfully confused me :(

"Can A be not Turing-recognizable?"

**I feel A is always Turing-recognizable**. Here is my thinking,

Since B is Turing Recognizable =\> There is some TM which accepts all the words of language B =\> There is a TM which accepts (all the words of language A + some other words) =\> There is a TM which accepts all the words of language A =\> A is Turing Recognizable.

Is this wrong? Can there be any case where A is Non-TRL while B is TRL. **Kindly help**

# Answer
> -4 votes
In this case A couldn't be Turing-recognizable. Take this as an example:

language B is the union of a language t.r (C) and a language not t.r(A). you can create a turing machine that recognizes B. A is not t.r and A ⊆ B.

is that right? i dont know if it is..so.. =)

---
Tags: computability
---


# Question
Title: Best solutions to 6 degrees of separation
From purely my knowledge of computer science a simple breadth first search from root A in search of node B, while keeping track of the depth of the tree, would be the most effective way to check whether A and B have 6 degrees of separation. If I simply wanted to check whether B is within 6 degrees I could also limit my depth to 6.

I have heard however that there are better ways of doing this using bidirectional methods which involve some heuristics. I was wondering if someone could explain the most effective way of doing this and compare space and time complexity between the different approaches. Thanks!

And as a followup, what would be a good algorithm for finding the degree of separation between two arbitrary nodes A and B and the path between them?

# Answer
You could possibly save some space using a "meet in the middle" approach. Make a list of all nodes at distance at most 3 from A, and another list of all nodes at distance at most 3 from B. If the lists intersect, then A and B are at distance at most 6. In the fact, it is enough to construct one of the lists and then generate the other list, testing whether each element belongs to the first list.

To determine whether the lists intersect, you have two options: either sort the first list, or put it into a hash table. The second uses more space but it's faster. (You will need counterparts of these, a balanced binary tree or a hash table, to generate the lists in the first place.)

Practically speaking, you would apply the following optimization: first determine all nodes at distance 1 from A and all nodes at distance 1 from B, and check whether the lists intersect. Then check all nodes at distance 2 from A against all nodes at distance 1 from B. Then check all nodes at distance 2 from A against all nodes at distance 2 from B. And so on. If the distance is less than 6, then you potentially save a lot of time and space.
> 9 votes

---
Tags: algorithms, graphs, search-algorithms
---


# Question
Title: How to prove that "Total" is not recursive (decidable)
$\mathrm{Halt} = \\{ (f,x) | f(x)\downarrow \\}$ is r.e. (semi-decidable) but undecidable.

$\mathrm{Total} = \\{ f | \forall x f(x)\downarrow \\}$ is not r.e. (not even semi-decidable).

I need some help in proving that $\mathrm{Total}$ is not recursive (decidable).

I know the diagonalization proof for the halting problem, I just need the same kind of proof for $\mathrm{Total}$. I'm posting the proof for the halting problem for reference:

## Undecidability of the halting problem

Assume we can decide the halting problem. Then there exists some total function $\mathrm{Halt}$ such that $$ \mathrm{Halt}(x,y) = \begin{cases} 1 & \text{if $\phi\_x(y)$ is defined}, \\ 0 & \text{if $\phi\_x(y)$ is not defined}.\end{cases} $$

Here, we have numbered all programs and $\phi\_x$ refers to the $x$'th program in this ordering. We can view $\mathrm{Halt}$ as a mapping from $\mathbb{N}$ into $\mathbb{N}$ by treating its input as a single number representing the pairing of two numbers via the one-one onto function $$ \mathrm{pair}(x,y) = \langle x,y \rangle = 2^x (2y + 1) – 1 , $$ with inverses $$ \begin{align\*} \langle z \rangle\_1 &= \exp(z+1,1), \\ \langle z \rangle\_2 &= ((( z + 1 ) // 2^{\langle z \rangle\_1}) – 1 ) // 2 \end{align\*} $$ Now if $\mathrm{Halt}$ exists, then so does $\mathrm{Disagree}$, where $$ \mathrm{Disagree}(x) = \begin{cases} 0 & \text{if $\mathrm{Halt}(x,x)=0$, i.e., if $\phi\_x(x)$ is not defined}, \\ \operatorname\*{\mu}\_y (y=y+1) & \text{if $\mathrm{Halt}(x,x)=1$, i.e., if $\phi\_x(x)$ is defined}. \end{cases} $$

Since $\mathrm{Disagree}$ is a program from $\mathbb{N}$ into $\mathbb{N}$, $\mathrm{Disagree}$ can be reasoned about by $\mathrm{Halt}$. Let $d$ be such that $\mathrm{Disagree} = \phi\_d$, then

$$\mathrm{Disagree}(d)\text{ is defined} \Leftrightarrow \mathrm{Halt}(d,d) = 0 \Leftrightarrow Φ\_d(d)\text{ is undefined} ⇔ \mathrm{Disagree}(d)\text{ is undefined}.$$

But this means that $\mathrm{Disagree}$ contradicts its own existence. Since every step we took was constructive, except for the original assumption, we must presume that the original assumption was in error. Thus, the halting problem is not decidable.

# Answer
> 1 votes
A set $A$ is recursive iff $A$ is recursive enumerable and $A^c$ is recursive enumerable. You know that $Halt$ is recursive enumerable but not recursive so $Halt^c$ must not be recursive enumerable. You can show that $Total$ is not recursive enumerable (and therefore not recursive) by showing that it is reducible from $Halt^c$.

Formally, to show that $Halt^c \leq\_M Total$ you need to find a total computable function $f$ such that $$x \in Halt^c \Leftrightarrow f(x) \in Total$$

# Answer
> 1 votes
We would like to modify the proof above by defining $$ \mathrm{Disagree}(x) = \begin{cases} 0 & \text{if $\mathrm{Total}(d)=0$}, \\ \operatorname\*{\mu}\_y (y=y+1) & \text{if $\mathrm{Total}(d)=1$}, \end{cases} $$ where $\mathrm{Disagree} = \phi\_d$. The problem is, how can a program know its own number? This is taken care of by the recursion theorem, a classical theorem in recursion theory. The idea extends further to prove Rice's theorem, a generalization of the undecidability of both $\mathrm{Halt}$ and $\mathrm{Total}$.

I should mention that $\mathrm{Total}$ is in fact harder than $\mathrm{Halt}$: even given an oracle to $\mathrm{Halt}$, $\mathrm{Total}$ is undecidable. In terms of the arithmetical hierarchy, $\mathrm{Halt}$ is $\Sigma\_1$-complete and $\mathrm{Total}$ is $\Pi\_2$-complete.

---
Tags: computability, undecidability, halting-problem
---


# Question
Title: a regular language so that $unary(L) \notin $Context Free Languages
I need a regular language $ L\subseteq \\{0,1\\}^{\*} $ so that $unary(L)$ is not context free.

unary of $L$ is defined by: $$unary(L) = \\{0^{1x} : x \in L \\}$$

Example $L = \\{0, 11\\} $ $\rightarrow unary(L) = \\{00, 0000000\\}$

Any help would be great.

# Answer
Let $L = 10^\*$ and observe that $$\text{unary}(L) = \\{ 1, 11, 1111, 11111111, \dots\\} = \\{1^{2^i} \mid i \in \mathbb{N} \\}.$$

Can you prove the rest yourself?
> 3 votes

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


# Question
Title: find function which is in o(log^k(n)) for fixed value of k and in ω(1)
I need to find a function $f$ which is in $o(\log^{k} n)$ for fixed value of $k$ with $f = \omega(1)$. I know that for little $o$ the function should be strictly less than $c\log^k n$ for all $c$ and large enough $n$; and for little $\omega$ it should be strictly greater than $c\cdot 1$ for all $c$ and large enough $n$, but I am stuck here. How does one usually solve such type of problems?

# Answer
> 0 votes
Hint: Try $f(n) = \log\log n$.

---
Tags: asymptotics
---


# Question
Title: Dynamic programming VS Greedy Algroithms
I have two `True or False` questions in my practice test that are related but I am unsure about:

```
1. If an optimization problem can be solved using a greedy algorithm,
there must be a solution for this optimization problem using dynamic programming as well.

2. If an optimization problem can be solved using dynamic programming,
there must be a solution for this problem using a greedy algorithm as well.

```

I think the answers are `1. True` and `2. False` is this correct?

# Answer
> 2 votes
Sounds about right, however informal the statement; dynamic programming is more powerful than greedy algorithms so if a problem should require it, a greedy algorithm won't be enough. And in the case in which a greedy algorithm can solve the problem, there will also be a correct dynamic programming solution since dynamic programming involves solving problems by optimizing overlapping subproblems. Suppose a greedy algorithm suffices, then the local optimal decision at each stage leads to the optimal solution and you can construct a dynamic programming solution to find the optimal solution. However, greedy algorithms are generally faster so if a problem can be solved with a greedy algorithm, it will typically be better to use.

---
Tags: algorithms, dynamic-programming, greedy-algorithms
---


title: asymptotic growth of n^log log n

text:
# Question
Title: asymptotic growth of n^log log n
I'm ordering functions by their asymptotic growth for an assignment and I have verified I have the correct order by using limits, but I'm trying to understand why $n^{log\ log\ n}$ is between $n^3$ and $2^n$. It seems like it should be closer to the order of $n^n$. Can anyone provide some insight on this.

# Answer
> 2 votes
It could help if you wrote $n^{\log\log n}$ as $2^{\log n\log\log n}$. Then it should be clear that $2^{\log n\log\log n} = o(2^n)$. The morale of this is that the base of an exponent doesn't count as much as the exponent itself.

# Answer
> 1 votes
First, $3 \in O(\log\log(n))$ so $n^3 \in O(n^{\log\log(n)})$ and after taking the log of both $2^n$ and $n^{\log\log(n)}$ we see that $\log(\log(n))\times \log(n) \in O(n\log(2)) = O(n)$

To help with the argument of why $\log(\log(n))\times \log(n) \in O(n\log(2)) = O(n)$ take: $$\lim\limits\_{n\rightarrow\infty} \frac{\log(\log(n))\times \log(n)}{n}$$ and apply L'Hôpital's rule to get $$\lim\limits\_{n\rightarrow\infty} \frac{1 + \log(\log(n))}{n} = \lim\limits\_{n\rightarrow\infty} \frac{1}{n} + \lim\limits\_{n\rightarrow\infty}\frac{\log(\log(n))}{n} = 0 + 0 = 0$$

---
Tags: asymptotics
---


# Question
Title: Complexity as it relates to verifiers of languages
So I've been thinking about verifiers and a possible relation between a language's class and it's verifier complexity. From the book, "NP is the class of languages that have polynomial time verifiers". Is there an analog statement that can be said about a P-class verification complexity? Because P is a subset of NP, I understand that the statement of NP still applies to P. Still, my intuition is that there is something more that can be said about a verifier for P that relates to oracles. Is there more that can be said?

# Answer
> 4 votes
It is an open question whether $P=NL$, where $NL$ is the class of languages verifiable in logarithmic space. It is known that $NL \subseteq P$ (why?), and strongly suspected that $NL \neq P$, but we don't know for sure.

---
Tags: time-complexity, np-complete
---


title: Can a Turing Machine have fewer states?

text:
# Question
Title: Can a Turing Machine have fewer states?
I am currently learning about Turing Machines, I am curious if a Turing Machine can have fewer states ? Can it be done like a Transition Graph where you can have multiple states at once ?

I got this TM off of a youtube video sorry for bad hand writing, but could I just merge some of the states like you would do in Transition Graph, so instead of having 5 states it would have 4 states ? TM are more advanced so I don't know if you are even able to do this...thanks!

how could I make this into 4 states TM instead of 5 states ? in TG if would take 5 seconds do it...

# Answer
> 1 votes
It is undecidable to check whether a turing maching has a smaller encoding than a given one. Hence there cannot be any such concept as a transition graph.

If you simply want a smaller turing maching for your example, I would guess no, from a quick glance of it.

# Answer
> 0 votes
The language of your Turing Machine is : $ \\{ a^nb^n | n \> 0 \\}$. What about this?

I think language of this Turing Machine is : $ \\{ a^nb^n | n \> 0 \\}$ but with the condition of $A,B \notin \Sigma$.

---
Tags: turing-machines
---


# Question
Title: Constructively deciding whether a decidable predicate holds universally
I am trying to obtain the proof of the proposition:

$(\forall x \in \mathbb{N}, P(x)) \vee (\neg \forall x, P(x))$

given that the property $P$ is decidable for every $x \in \mathbb{N}$, i.e.

$\forall x \in \mathbb{N}, P(x) \vee \neg P(x)$

This is easy to prove (even without using the decidability of $P$) if I include the law of excluded middle, i.e.,

$\forall P, P \vee \neg P$.

However, I am trying to obtain a constructive proof for the same. Is the proposition true without including the law of excluded middle? If so, how do I prove it? This seemingly simple property is needed to prove something about a complex system, and I am trying to not use the law of excluded middle unless it's absolutely necessary.

The best I could come up with is the following:

$\forall y, (\forall x \le y, P(x)) \vee \neg (\forall x \le y, P(x))$

I do not know how to proceed beyond this (or if this is even useful).

Any help would be appreciated.

# Answer
> 12 votes
You are asking for a constructive proof of the Lesser limited principle of omniscience (LLPO), which states (in one of its forms) that for a decidable proposition $P$ on natural numbers $$(\forall n \in \mathbb{N} \\,.\\, P(n)) \lor \lnot \forall n \in \mathbb{N} \\,.\\, P(n).$$ That's exactly your problem. It is well known that LLPO is not provable constructively.

Unless you have some further conditions on $P$ which you did not tell us about, you're stuck.

# Answer
> 5 votes
From a proof of $Q \lor \neg Q$ you can extract a witness saying whether $Q$ or $\neg Q$. From a proof of $\forall M~ (Q \lor \neg Q)$, you can extract an algorithm mapping $M$ to whether $Q$ or $\neg Q$.

$P(M,x)$ could be "Turing machine $M$ does not stop within $x$ steps on the empty input", which is indeed decidable; but then $\forall x~P(M,x)$ means "Turing machine $M$ never stops on the empty input. Since you made no hypothesis on $M$, $(\forall x~P(M,x)) \lor \neg \forall x~P(M,x))$ means that you can decide the termination of $M$.

Note: there is the converse — if $P$ is a decidable property such as $A(x)=\mathit{true}$, then you can prove $\neg \neg P \Rightarrow P$. I reckon that, for instance, Georges Gonthier sometimes proves complicated properties with double negations added everywhere (so with classical-like reasoning), then concludes by this trick. This gives you the ease of proving in classical logic but still an intuitionistic result (without assuming excluded middle).

---
Tags: logic, proof-techniques, first-order-logic
---


title: 3SAT to CNF-SAT reduction

text:
# Question
Title: 3SAT to CNF-SAT reduction
I am trying to prove that 3SAT is polynome time reducable to CNF-SAT, but I don't know how to do this. A formula F is in 3SAT iff f(F) is in KNFSAT, but since 3SAT is a part of KNFSAT, every formula that is in 3SAT will automatically be in CNF-SAT. Is my conclusion correct? And how do I actually show this in a correct manner?

# Answer
Yes, going from 3SAT (also called 3CNFSAT) to CNFSAT (also called just SAT) is trivial. The function $f$ you are looking for is just identity, i.e., $f: x \mapsto x$, and then you are done, because, obviously, if the boolean formula $\phi$ is satisfiable (and in conjunctive form where each clause has at most three literals), i.e., in 3SAT, then $f(\phi)=\phi$ is also satisfiable and in conjunctive form, i.e., in SAT.

Usually, people are more interested in the other direction: Given a formula $\phi$ in conjunctive form, find a formula $g(\phi)$ which is equisatisfiable to $\phi$ (and thus one obtains a suitable reduction). For this, see Boolean satisfiability problem.
> 4 votes

---
Tags: complexity-theory, reductions, satisfiability, 3-sat
---


title: Classfication of randomized algorithms

text:
# Question
Title: Classfication of randomized algorithms
From Wikipedia about randomized algorithms

> One has to distinguish between **algorithms** that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time, and **probabilistic algorithms**, which, depending on the random input, have a chance of producing an incorrect result (Monte Carlo algorithms) or fail to produce a result (Las Vegas algorithms) either by signalling a failure or failing to terminate.

1. I was wondering how the first kind of "**algorithms** use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time?
2. What differences are between it and Las Vegas algorithms which may fail to produce a result?
3. If I understand correctly, probabilistic algorithms and randomized algorithms are not the same concept. Probabilistic algorithms are just one kind of randomized algorithms, and the other kind is those use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time?

# Answer
> 12 votes
1. An example of such an algorithm is randomized Quick Sort, where you randomly permute the list or randomly pick the pivot value, then use Quick Sort as normal. Quick Sort has a worst case running time of $O(n^{2})$, but on a random list has an expected running time of $O(n\log n)$, so it always terminates after $O(n^{2})$ steps, but we can expect the randomized instance to terminate after $O(n\log n)$ steps, always with a correct answer.
2. This gives an subset of Las Vegas algorithms. Las Vegas algorithms also allow for the possibility that (with low probability) it may not terminate at all - not just terminate with a little bit more time.
3. These in turn are really just a type of Monte Carlo algorithm, where the answer can be incorrect (with low probability), which is at least conceptually different to maybe not answering.

There's a whole bunch of detail I've left out of course, you might want to look up the complexity classes ZPP, RP and BPP, which formalise these ideas.

# Answer
> 10 votes
The two terms *randomized algorithms* and *probabilistic algorithms* are used in two different contexts. *Randomized algorithms* are algorithms that use randomness, in contradistinction with *deterministic algorithms* that do not. *Probabilistic algorithms*, for example probabilistic algorithms for primality testing, are algorithms that use randomness and could make an error with some (hopefully) small probability.

An important distinction has to be made between *Monte Carlo algorithms* and *Las Vegas algorithms*. Las Vegas algorithms are randomized algorithms that always return the correct answer, but their running time depends on the coin tosses. An example is integer factoring algorithms – they always return the correct factors, but their running time depends on the randomness. When stating the running time of a Las Vegas algorithm (say a factoring algorithm), we actually state the *expected* running time; if we are unlucky, the algorithm could run for longer.

Monte Carlo algorithms, on the other hand, are randomized algorithm whose running time is set ahead of time. Such algorithms can make a mistake, but usually the error probability is very low. A good example is probabilistic primality testing. These algorithms are very fast but could make an error. However, the error probability is slow low that in practice, they never make a mistake.

Every Las Vegas algorithm can be converted to a Monte Carlo algorithm by stopping execution after a long enough time, so Las Vegas algorithms are in some sense "better" than Monte Carlo algorithms.

---
Tags: algorithms, terminology, randomized-algorithms, nondeterminism, machine-models
---