# Question
Title: Explaining SAT to high school science teachers
I am a high school sophomore who is interested in computer science. I developed a cool algorithm for #SAT, and I'm implementing and doing a science fair project on it. My adviser, who is the best science teacher at my school and is also the AP Comp Sci teacher, told me that she has absolutely no idea what my project is about, and that I need to be able to briefly explain her why #SAT is important in under 5 minutes. I told her SAT reduces to #SAT and tried to explain why SAT is important: I gave her some examples of NP problems, explained her how problems in NP reduce to SAT, and explained how with binary search you can reduce certain optimization problems to SAT, which allows you to fold proteins and make powerful AI models. Unfortunately, she didn't understand me at all. Could you give me a few pointers?

P.S. My adviser asked me what useful problems reduce to #SAT that don't reduce to SAT (assuming some problems in #P are harder than their corresponding NP versions). All I could come up with was finding how many models for a given data set are better than a given model (assuming each parameter of the model is smaller than a given number of bits). I looked for other ones on the web but I couldn't find anything I could understand. Are there any other good applications?

# Answer
> 6 votes
The permanent is #P-complete, even when restricted to $\\{0,1\\}$-valued matrices. The permanent can be used to compute certain parameters in statistical mechanics, see for example this paper on the dimer covering problem. Since I'm not a physicist, I cannot comment on whether these theoretical statistical mechanics problems are really useful; I suspect that they are not directly useful, but the area itself could lead to useful insights. It could also be the case that some of these parameters are useful on their own, but you'll have to consult with an expert.

Your 5 minute pitch could go something like this:

> Statistical mechanics is a beautiful and deep part of physics and chemistry which studies how the emergent behavior of large systems results from microscopic physical laws operating on individual elements. It explains phenomena such as the laws of gasses, magnetization, and transitions between different phases of matter. Statistical mechanics is intimately connected to probability theory, computer science, operations research, and data science.
>
> Many important quantities in statistical mechanics can be formulated as instances of #SAT. An algorithm for solving #SAT exactly or approximately can thus be used to predict physical and chemical phenomena.

This might somewhat overstate the case, but that's how sales pitches go.

# Answer
> 1 votes
This question seems to mix up SAT and #SAT a bit in its wording. Yes, the two are tightly coupled. #SAT is simply defined as the complexity class associated with *counting* the number of solutions to a SAT problem and widely *conjectured* to be much harder, but maybe surprisingly, it hasn't been proven. #SAT is not even studied very much in college level complexity theory, it's more of an advanced theoretical research topic.

One way to motivate the importance of #SAT is via Toda's theorem which won a 1998 Gödel prize for it's deep significance. From Wikipedia:

> Thus Toda's theorem implies that for any problem in the polynomial hierarchy there is a deterministic polynomial-time Turing reduction to a counting problem.\[1\]

Also, since SAT and #SAT are not even proven to have different complexity, a reasonable case can be made that understanding #SAT complexity might lead to some insight on the P vs NP problem, which has *loads* of information and motivation.

---
Tags: algorithms, satisfiability
---


# Question
Title: Is Universality Theorem applicable to Halting problem?
This is Universality theorem In the `Computability, Complexity and Languages book written by Davis in page 70`:

> If $\phi^{(n)}(x\_1,...,x\_n,y) = \psi\_P(x\_1,...,x\_n)$ $where$ #$(P) = y$
>
> **Theorem 3.1 (Universality Theorem):** for each $n\>0$ the function $\phi^{(n)}(x\_1,...,x\_n,y)$ is partially computable.

From what I understand of this theorem, the universal program is more like an interpreter it takes $x\_1,...,x\_n$ as input and $y$ as a program number and simulates what program with number $y$ does on the $x\_i$s.

Since there is no program for halting problem so there is no $y$ for it to be passed to $\phi^{(n)}(x\_1,...,x\_n,y)$ so I think this theorem is not applicable to halting problem.Is it right?

# Answer
By this book notation we have

$Halt(x,y)$ $\iff$ Program number $y$ eventually halts on input $x$.

Since there $Halt(x,y)$ is not computable predicate (theorem 2.1 page 68) there is no program that check if program number $y$ halts in input $x$ (for every $y$ and $x$), but this not mean that there is no program that run program number $y$ on input $x$!

By using universal program $\phi(x,y)$ we can run program number $y$ on input $x$. This means that $Halt(x,y)$ is r.e.

+if you think a bit more you can observe that program number y can get stuck in loop on input x, and that's why $Halt(x,y)$ is not computable.
> 1 votes

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


# Question
Title: Are there criteria that will make: $A \subseteq B$, $A$ unrecognizable imply $B$ unrecognizable?
Let $A \subseteq B$, and A is unrecognizable. I know in general that doesn't mean B is unrecognizable. However, are there some limitations we could put on A and B that would make it true? The only thing I could come up with was A=B. Plus, we could say B is unrecognizable as part of our assumptions, but that's not really helpful.

(recognizable means recursively enumerable, in case you use different terminology)

# Answer
The condition about $B$ can be transformed into a condition about $B\setminus A$, as follows. If $B\setminus A$ is decidable, then $B$ is unrecognizable. Indeed, if you could recognize $B$, you could determine whether a word $w$ is in $B\setminus A$. If it is, then it's not in $A$, otherwise it is. So $A$ would be recognizable as well.

Note, however, that the converse does not work - there are sets $C,D$ such that $C\cap D=\emptyset$, both $C$ and $D$ are not recognizable, and $C\cup D$ is unrecognizable as well.
> 3 votes

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


title: Binary digit problem?

text:
# Question
Title: Binary digit problem?
Question:

> If a system has $32k$ bytes and each such byte has unique address(so $32k$ addresses), what is the smallest possible bits that can be use by every byte for the address ? All the bytes use the same number of bits for the address.

I thought the answer can be found by finding the value to which $2$ can be raised such that it equals $32,000$. I got $2$ raised to $ \sim 14.96$ gives $32,000$. But a byte only has $8$ bits so this can't make any sense.

Can anyone give any pointer on how to solve this problem ?

# Answer
The system has 32.000 bytes and each byte must have its own unique address:

32.000 unique addresses

**How many bits to represent these?**

$2^{15} = 32768$, so if we let addresses be 15 bit we have the address space $\[0,32767\]$.
> 1 votes

---
Tags: computer-architecture, combinatorics, memory-management, arithmetic
---


# Question
Title: Minimal DFA that accepts binary strings whose decimal equivalent is divisible by 32
I thought the answer would be 32 for remainder $0,1,2,\dots, 31$. But answer given as $6$. and explanation is given as if the number is $2^n$ then number of states required would be $n+1$.

# Answer
The idea of using remainders is perfect for the general problem of "Recognize base-$b$ strings representing a number divisible by $k$" for some general, fixed $b$ and $k$. However, it's not optimal for certain combinations of $b$ and $k$ where you can tell that the number is divisible by $k$ "just by looking at it." For example, if I asked you to recognize decimal numbers divisible by $100\\,000$, you wouldn't be messing around with remainders: you'd use a nice textual property of decimal numbers divisible by powers of ten.
> 1 votes

# Answer
Binary numbers that are divisible by 32 are ending in zero's. You can just keep track of how many consecutive zero's we have seen. If you want to answer the same question for the decimal alphabet, yes, then you need to worry about remainders modulo 32. The phrase "decimal equivalent" is a bit confusing here: divisibility of a number does not change when choosing another representation.

After building the automaton you can minimize it using standard constructions, to see if you cannot do with less states. Perhaps the same approach works for $2^n$, but then you not have a single "concrete" automaton. Alternatively you might use the theory of Myhill-Nerode equivalence classes of the language, to show the number of states is at least a certain number.
> 1 votes

# Answer
Binary string whose decimal equivalent is divisible by 32 is the following language

$L=\\{ w \in \\{0,1\\}^\* | w=xy$ and $ x\in \\{0,1\\}^\*$ and $(y=100000$ or $y=000000) \\}$

If you try to construct the minimal DFA for it you'll find that after the initial state we have new state only when read another 0 and by reading 5 zeros we won't get new states.
> 1 votes

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


# Question
Title: Artificial intelligence - bridge and torch problem
I am doing a artificial intelligence course as part of my computer science degree.

I am stuck on a question about searching. The question is a version of the Bridge and torch problem.

Five people need to walk from this side to the other side of a bridge at night. The bridge is not in a very good condition and will hold at most 3 people at a time. They discover that they only have one torch. This means that after one,two,or three people have crossed the bridge, somebody (one, two, or three people) will have to come back with the torch so that the next persons can cross safely. Each of the five people (Anna, Brett, Charles, David, and Ernest) take a different time to cross the bridge. Whenever 3 people cross they can only go as fast as the slowest person in the group. Since the torch has limited battery life they need to figure out which is the fastest way to get all 5 of them across the bridge. The times each take to get across are:

```
1. Anna: 5 Minutes
2. Barry: 7 Minutes
3. Charles: 1 minute
4. David: 2 minutes
5. Ernest: 9 minutes

```

I am asked how big the search space is of the problem. This is where I am getting stuck. There are 5 people, and two sides of the bridge where they can be. There is also a variable amount of people that can cross at a time (1-3 people).

My state representation is $\\{ A, B, C, D, E \\}$ representing the first letter of each person, with this being the set of people on the left side of the bridge. Hence, my goal state is $\\{ \\}$ - all people on the right side of the bridge.

I've also worked out the sequence of moves that leads to the optimal solution - my issue is just the size of the search space.

How do I go about calculating the size of the search space?

# Answer
Before you can calculate the size of the \[thing\], you need to decide exactly what the \[thing\] is.

In this case, you've decided that the state space is the set of people on the left side of the bridge. The people on the left can be any subset of the people, so any subset of $\\{A, B, C, D, E\\}$. The number of subsets of an $n$-element set is a well-known fact you should recall from your discrete mathematics classes.

Note that people moving across the bridge is not part of the state: it's a transition from one state to another (also known as an action). If you included that information in the state, you'd just make the search take longer. For example, instead of having the state "$A$, $B$, and $E$ are on the left" transitioning to "$A$ and $E$ are on the left", you'd have it transition to "$A$ and $E$ are on the left and $B$ is on the bridge", which would then have no choice but to transition to "$A$ and $E$ are on the left" (and nobody is on the bridge). Adding a bunch of states that have only one successor is only going to slow down your search.
> 2 votes

---
Tags: complexity-theory, combinatorics, artificial-intelligence, search-problem
---


# Question
Title: Shortest path where weights are computationally expensive to calculate
Suppose we have a function, CalculateEdgeWeight, which is computationally expensive. We want to find the shortest path between two nodes $s$ and $t$ in a simple edge-weighted digraph $G= (V,E)$ where weights of $ij \in E$ are calculated with CalculateEdgeWeight($ij$).

Is there a shortest path algorithm that does not require the knowledge of all edge weights by the end of the algorithm so that the use of CalculateEdgeWeight is minimized? What if we have bounds on the possible weights?

# Answer
No, you may have to examine all of the edges. Consider a graph where $V=\\{s,t,v\_1,\ldots , v\_n\\}$ and $E=\\{(s,v\_1),\ldots,(s,v\_n),(v\_1,t),\ldots,(v\_n,t)\\}$. If $W(s,v\_i)=1$ for all $i$, the problem is finding $i$ so that $W(v\_i,t)$ is minimal. And we can not find the minimal $W(v\_i,t)$ without examining all of them.

Dijkstra's Algorithm/$A^\*$ use a "greedy" strategy, in which they do not necessarily examine all edges but only those on a path from the source that is at most as long as the shortest path. You could further improve this by using bidirectional (meet-in-the-middle) variants.

You could also use $A^\*$ with a heuristic to take any bounds on the edge weights in to account. If you have a lower bound on the edge weights, you can first use BFS to compute minimum length path, and then use that times the lower bound to get a lower bound on the actual distance from any vertex to the goal.
> 2 votes

# Answer
The problem you are concerned with has been examined also in the literature. See the paper Szepesvári, C. 2004. Shorteset path discovery problems: A framework, algorithms and experimental results. Association for the Advancement of Artificial Intelligence 2004, pp. 550--555.. In this paper, the following is said at the very beginning:

> In this paper we introduce and study Shortest Path Discovery (SPD) problems, a generalization of shortest path problems: In SPD one is given a directed edge-weighted graph and the task is to find the shortest path for fixed source and target nodes such that initially the edge-weights are unknown, but they can be queried. Querying the cost of an edge is expensive and hence the goal is to minimize the total number of edge cost queries executed.

Note that this work assumes edge costs to be unknown. A practical application of this theoretical assumption arise (as mentioned above) in those cases where querying the cost of an edge is very expensive ---as in your case. The algorithms considered in this paper are sound and they attempt at reducing the number of *queries*.

It seems, however, that your question also refers to the applicability of *typical* search algorithms such as A$^\*$. Recall that A$^\*$ expands all nodes $n$ such that $f(n)\<f^\*(s)$ where $f(n)=g(n)+h(n)$. In other words, it has to expand necessarily all nodes with an $f$-value which is lower than the cost of the optimal solution. The answer provided by Tom van der Zanden goes in this direction indeed. However, truth is that A$^\*$ also generates (thus, it evaluates and stores in OPEN) a number of nodes with $f(n)\geq f^\*(s)$ which are absolutely unnecessary.

This problem is of importance since the number of nodes generated grows exponentially with the depth of the search traversed. In your case it is twice importance because that extra amount of nodes have to be evaluated (and this requires *querying* a function its edge cost). A number of strategies have been proposed to save those extra generations in the context of A$^\*$. For a good introduction and a plausible solution to this problem see: Meir Goldenberg, Ariel Felner, Nathan Sturtevant, Robert Holte, Jonathan Schaeffer. Optimal-Generation Variants of EPEA$^\*$, Proceedings of the Fifth International Symposium on Combinatorial Search, (SoCS-2013), July 2013 In case this paper fits your needs check the publications page by Ariel Felner because he also contributed with an additional paper.

Hope this helps,
> 3 votes

---
Tags: shortest-path
---


# Question
Title: Prove that a language is not regular with process of elimination
When deterministic automaton, I need to prove that you can't implement the language in it, because the language is not regular.

Easiest way to prove that a language is regular, is just by making an automaton for it. But if the automaton is not regular, you can't just say that it's not regular because you couldn't build an automaton for it.

So I am wondering, how to prove that a language is not regular the simplest way?

Given language:

$$ L = \\{a^n b^n | n \> 0\\} $$

Definition: The language accepts series of `a`'s and `b`'s where the amount of `a`s equals to the amount of `b`s. This is not a regular language.

How can you prove that it's not a regular language?

From what I remember (I didn't understand it much), you had to take a sub-langauge of that language, and mark it as `W`

So $$ W = \\{a^i\\} $$

Then select 2 words from W and mark them as `w1` and `w2`

$$ w1 = a^i $$ $$ w2 = a^j $$

**where i != j**

And then I don't really remember what to do.

# Answer
> 2 votes
A simple technique is using the pumping lemma:

For any regular language $L$ there exists an integer $n$ such that for all $x \in L$, with $|x| \geq n$ there exists $u,v,w \in \Sigma^\*$, such that,

* $x = uvw$
* $|uv| \leq n$
* $|v| \geq 1$
* for all $i \geq 0: uv^iw \in L$

**Assumption: Suppose your language is regular.**

Consider $s = a^nb^n$. Clearly $s \in L$ and $|s| \geq n$. We get that $uvw = a^nb^n$ and we know that $|uv| \leq n$, i.e $v$ can only contain $a$'s and since $|v| \geq 1$ it must contain at least one $a$. According to the last condition of the pumping lemma, $uv^0w \in L$ but this is clearly not the case. We now have a contradiction as we assumed the language to be regular:

**The assumption must be wrong implying non-regularity of the language**

# Answer
> 0 votes
What you are suggesting is the Myhill–Nerode criterion, which is more natural, and in many cases simpler, than the standard pumping lemma which for some reason has become the undergraduate hallmark of the subject.

Consider your two words $a^i$ and $a^j$. Suppose we are given some DFA for the language. Can the DFA be at the same state after reading $a^i$ and $a^j$? It cannot, since if it were, the DFA would behave the same after seeing the word $b^i$, say reaching some state $q$; but since $a^ib^i \in L$, $q$ must be accepting, while since $a^jb^i \notin L$, $q$ must be rejecting! We conclude that the DFA must be at *different* states after reading $a^i$ and $a^j$.

We can consider the infinitely many words $a^1,a^2,a^3,\ldots$. The argument above shows that any DFA for $L$ must reach a different state after reading them. So it must have infinitely many states. Contradiction.

In contrast to the pumping lemma, which doesn't always "work" (i.e., there are non-regular languages which satisfying the pumping lemma), the Myhill–Nerode criterion is a complete characterization: if a language is not regular, then you can always find an infinite list of mutually inequivalent words (two words $w\_1,w\_2$ are inequivalent if for some word $x$, either $w\_1x \in L$ while $w\_2x \notin L$, or $w\_1x \notin L$ while $w\_2x \in L$), which proves that the language is not regular.

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


# Question
Title: Is there $L$ such that $L$ and $\bar L$ are context free, but $L$ is not deterministic context free?
The usual candidates for context free languages whose complement is also context free, but they are not regular are the Deterministic Context Free Languages ($DCFL$).

For example, $L=\\{a^nb^n\mid n\in\mathbb N\\}$ is such language.

> *Is there a language, $L\in CFL\setminus DCFL$ such that $\bar L\in CFL$?*

---

Since $DCFL$ is closed under complement, this is equivalent of asking whether $$CFL\cap co\text{-}CFL = DCFL$$

# Answer
> 3 votes
See here:

> For every finite, non-unary alphabet, the language of all palindromes is not in DCFL, but in the intersection of coCFL and CFL.

---
Tags: formal-languages, context-free, closure-properties, nondeterminism
---


title: CPU time and execution time

text:
# Question
Title: CPU time and execution time
Why should computer designers trade off clock rate against cycle count? Can somebody explain this sentence for me? Shouldn't it be that when the clock rate increases the cycle count decreases?

I don't understand why the cycle rate and the cycle count are not proportional.

# Answer
> 1 votes
I am not sure I understand the question.

When designing a CPU, you decide how many pipeline stages it will have and accordingly how much work is done at each stage.

Often, all the parts of the CPU work at the same frequency (well, this is not really true, but...), so the most complex part will be what limits the frequency that the CPU will be able to achieve.

Some CPUs are optimised for high frequency and have many pipeline levels (ex : Intel Pentium IV, AMD Steamroller). Good for number crunchers.

Some CPUs are optimised for lower frequencies but cram more work for each pipeline level (ex. : Intel Core, Apple A8...). This option is often more power efficient.

Deeply pipelined CPUs waste more cycles than narrow ones when the pipeline must be emptied : mispredicted branch, interrupt... The number of cycles wasted is higher, but as the frequency should also be higher, the delay for each cycle should be a bit shorter than for a short-pipelined CPU.

\[Maybe you should give more context to your question. This answer was probably not what you were looking for ;-)\]

---
Tags: computer-architecture
---


# Question
Title: What is considered arithmetic when dealing with bits?
In a recent homework question we were asked to implement a program that would use only bitwise operations. From our notes, this includes & | ^ ~ \>\> \<\< and \>\>\>. We are not allowed to use arithmetic operations, or loops.

Since immediately addition can be defined with the above accepted operators, what constitutes "arithmetic"? Would unary operations be allowed?

For example, I could define incrementation and decrementation using ~ and the unary -, and recursively call both until the decremented number reached 0, meaning both numbers were added (think addition in brainfuck). Is this arithmetic?

# Answer
> 1 votes
A program that uses only bitwise operations is just that – a program which only uses bitwise operations. Bitwise operations are universal, that is, you can define any function using them. What makes things interesting is that we care about the *complexity* of implementing a given function using only bitwise operations.

In particular, suppose that we only care about the complexity up to multiplicative constants (i.e. we only care about the big O). Any operation which can be implemented using a *constant* number of bitwise operations is *admissible* – the resulting notion of complexity is the same (up to multiplicative constants). So if you can implement addition using a *constant-size* formula, then you are welcome to use addition.

The constraint doesn't mean that at no point of your program are you allowed to compute by chance some arithmetic function – it just means that the basic operations you are allowed are only the bitwise ones.

---
Tags: terminology, arithmetic
---


# Question
Title: What is the advantage of Day-Stout-Warren algorithm for balancing BST?
While reading about Day–Stout–Warren algorithm for balancing BST which takes any BST and transforms it into a balanced BST in `O(n)` time.

In my opinion I can achieve absolutely the same with these simple steps:

* convert BST into array using inorder traversal. This will give me an array in increasing order and can be completed in `O(n)`
* create a binary search tree by selecting the middle element in array in O(1), put it as a root, and recursively do the same for a right part of an array (putting the value as a root for a right subtree) and the same for the left part. This will also run in O(n)

So in my opinion I can achive absolutely the same in O(n). What is the advantage of DSW algorithm in comparison to this one?

# Answer
> 3 votes
The Wikipedia article states:

> The algorithm \[...\] is in-place.

You algorithm requires at least twice as much space. This is a significant drawback on huge data sets.

A further possible advantage (I did not check) lies in the *constant factors* of the runtime function. Intuitively, you always construct a perfectly balanced BST so you may well do (lots) more work than DSW, even if you are still linear. Again, even a factor of magnitude $\< 10$ is significant on huge data sets.

In my opinion, this question is more interesting: why use simple BST + DSW instead of using balanced BSTs in the first place? (The answer is hinted at in the article, too.)

---
Tags: algorithms, data-structures, optimization, binary-trees, search-trees
---


# Question
Title: Changing variables in recurrence relations
Currently, I am self-studying Intro to Algorithms (CLRS) and there is one particular method they outline in the book to solve recurrence relations.

The following method can be illustrated with this example. Suppose we have the recurrence

$$T(n) = 2T(\sqrt n) + \log n$$

Initially they make the substitution m = lg(n), and then plug it back in to the recurrence and get:

$$T(2^m) = 2T(2^{\frac{m}{2}}) + m$$

Up to this point I understand perfectly. This next step is the one that's confusing to me.

They now "rename" the recurrence $S(m)$ and let $S(m) = T(2^m)$, which apparently produces

$$S(m) = 2S(m/2) + m$$

For some reason it's not clear to me why this renaming works, and it just seems like cheating. Can anyone explain this better?

# Answer
> 18 votes
It's certainly not cheating. Think in calculus how substitution may be used to solve a tricky integral. The substitution makes the equation more manageable for manipulation. Additionally, substitution may transform somewhat complex recurrences into familiar ones.

This is exactly what occurred in your example. We define a new recurrence $S(m)=T(2^m)$. Remember that $T(2^m) = 2T(2^\frac{m}{2}) + m$. Notice that, $S(m/2) = T(2^\frac{m}{2})$. If this particular point is still unclear, let $k =m/2$ and notice all we are doing is this $S(k) = T(2^k)$. Now, we can express $S(m)$ by expanding it to: $$ S(m) = 2S(m/2) + m.$$ Solving for $S$ we see that it resolves to our familiar friend $O(m \log m)$. Now that we've solved $S$ we want to express this in terms of $T(n)$. To do this, merely plug back in our original value for $m$ and we have $T \in O(\log n \log \log n)$.

# Answer
> 7 votes
What $S(m) = T(2^m)$ means is that $S$ and $T$ are two different functions which produce the same result while taking inputs as $m$ and $2^m$ respectively.

Function $S$ can be considered as an operator with two internal steps (otherwise, composition of functions):

1. $S'$ operator: Input:$m$, Output:$2^m$
2. $T$ operator(original function): Input:output of first part, Output: As defined originally.

Therefore then transitions are:

$$m\to 2^m\to T(2^m) = S(m)$$ $$\tfrac{m}2\to2^{m/2}\to T(2^{m/2}) = S(\tfrac{m}2)\\,.$$

---
Tags: asymptotics, recurrence-relation, mathematical-analysis, landau-notation
---


# Question
Title: Expressiveness of modern regular expressions
I recently discussed with a friend about a website that proposed regex challenges, mainly matching a group a of words with a special property. He was looking for a regex that matches strings like `||||||||` where the number of `|` is prime. I immediatly told him that won't ever work because if such a language was regular, the translation of pumping lemma would gives the fact that for a prime $p$ large enough, it exists $k \leq p$ such that $p + nk$ is prime for all $n \geq -1$, and well this is not likely to be the case at all (repartition of primes, triviality of such an unknown and crushing property, ...)

But then someone came with the solution : NOT MATCHING `(||+?)\1+` This expression tries to match the capture group (that can be `||`,`|||`,`||||` and so on of $k \geq 2$ occurences of `|`) $n \geq 2$ times. If it matches, it means that the number represented by the string is divisible by $k$, and hence is not prime. Otherwise, it is.

And I felt stupid, because it became obvious that grouping and backreference allows regex to be actually a lot more expressive than...regular expression, in the theoritical sense. Now they even added lookarounds and other operators I didn't know about when I used to do real regex.

According to Wikipedia, it is even more expressive that languages generated by a context-free grammar. So here is my question :

* can we represent any algebraic language (generated from a context-free grammar) with modern regular expression engines
* is there a more general description, or at least an upper bound on the complexity of what kind of languages can be described by a modern regex ?

More pragmatically, is there any serious theory behind it or are we just adding any new features as it comes each time it seems implementable to the initial block of real regular expressions based on finite automata ?

I know that "modern regex" isn't very specific while the question is, but I mean at least with backreferences, and possibly more. Of course, if you have partial anwsers assuming certain restrictions on this "modern regex" language, feel free to post it.

# Answer
> 5 votes
The word problem of regular expressions with backreferences is NP-complete; citing Aho (1990) via Blaisorblade/Charles Stewart.

I don't know the whole set of operators some flavors of regexps have, but several are no more powerful than regular; they have probably been added as syntactic sugar.

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


# Question
Title: Finding the k-shortest path between two nodes
Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the $2^{nd}$-shortest path, the $3^{rd}$-shortest, and so on.

Questions:

> Is there an efficient algorithm to get the i-th-most-shortest-path between two nodes in a weighted graph?
>
> Is there an efficient algorithm to get the k-most-shortest-paths between two nodes in a weighted graph?

An answer to either one is OK, though I wonder if an answer to the second question can be done more efficiently than $k$ calls to an answer to the first question.

# Answer
In the *$k$ shortest path problem*, we wish to find $k$ path connecting a given vertex pair with minimum total length. Eppstein \[1\] has an algorithm running in $O(m+n \log n + k)$ time to find the $k$ shortest paths (allowing cycles) between a pair of vertices in a digraph. With the techniques of the paper, one can also find all path shorter than some given threshold, within the same time bounds. There is a vast literature on the subject, the Eppstein paper includes many references and discussion.

If you disallow cycles, you might want to look at the algorithm of Hershberger et al. \[2\].

---

\[1\] Eppstein, David. "Finding the k shortest paths." SIAM Journal on computing 28.2 (1998): 652-673. \[CiteSeerX\]

\[2\] Hershberger, John, Matthew Maxel, and Subhash Suri. "Finding the k shortest simple paths: A new algorithm and its implementation." ACM Transactions on Algorithms (TALG) 3.4 (2007): 45. \[CiteSeerX\]
> 5 votes

---
Tags: algorithms, graphs, shortest-path, graph-traversal
---


# Question
Title: Is there an algorithm to find all the shortest paths between two nodes?
Given a directed graph, Dijkstra or Bellman-Ford can tell you the shortest path between two nodes.

What if there are two (or n) paths that are shortest, is there an algorithm that will tell you all such paths?

Edit:

I have just thought up a possible solution. Could you just do a Bellman-Ford but when relaxing edges, if (distance\[u\] + w == distance\[v\]) then add u to the **set** of predecessors of v? Does this work?

# Answer
> 4 votes
For the $k$ shortest paths, there are algorithms; see for instance here.

Enumerating *all* shortest paths is, however, an inherently costly thing; there may be superexponentially many such paths.

# Answer
> 2 votes
## Building a shared struture to make explicit enumeration optional, but easy.

I think there are several ways to interpret your question, like other questions about algorithms giving all solutions to some problem. This may be the case here as you ask for all solutions, but not specifically for an enumeration of these solutions, which you can easily get however from the approach given below.

To take a well known example, when parsing Context-Free languages, you may be interested in getting just one parse tree, or in getting all parses. The number of parse trees can actually be infinite, or exponential when you exclude derivation loops (non-terminals deriving on themselves). You might even want to know only that there is such a parse-tree, i.e. be interested only in recognition, but let us ignore that.

Now, one possibility is to enumerate all parse trees, which may be infinite or exponential, even with the best enumeration cost amortization techniques.

Another possibility is to produce a structure (called a shared parse-forest in the case of parsing) that can generate any parse-tree, with a cost linear in the size of the parse-tree being produced. This is actually what is done by most general CF parsers. In the case of Context-Free languages, this structure can be produced with cubic time and space complexity, even when the number of parses is infinite.

Hence, while enumerating all solutions to a problem may have a very high cost, it may be possible to produce at relatively low cost a structure that can easily enumerate all solutions. Such a structure may be a convenient representation if you actually intend further processing to select the most appropriate solutions according to further criteria.

Another possibility is to analyze the structure to see whether enumeration is tractable or not, before attempting to do it.

In the question asked, Raphael's answer tells you that the number of minimal paths may be exponential. So finding all minimal paths may be a good candidate for such a shared structure solution approach. Actually, I believe it is generally applicable to dynamic programming algorithms (possibly with some restrictions), so it should apply to Dijkstra's algorithm. Let $c(N,N')$ denote the length of the shortest path from $N$ to $N'$.

Basically, the idea is that, if a node $N$ is on a minimal path from source $S$ to target $T$, then any other path from $S$ to $N$ placing $N$ at the same distance from $S$ can be used to build a minimal path from source $S$ to target $T$. The same is true for $N$ and $T$.

A way to proceed is to compute the minimal distance from $S$ to all other nodes. Then you initialise a set $U$ of *useful* nodes with the node $T$, a set $E$ of useful edges as empty, and a set $V$ of *visited* nodes as empty.

Now for each node $N$ in $U$, you consider each node $N'$ connected to $N$ that is at a shorter distance from $S$. If $c(S,N')+c(N',N)=c(S,N)$ then you add $N'$ to $U$ (unless it is already in $U\cup V$) and you add a directed edge $(N',N)$ to $E$. Otherwise you do nothing. When all adjacent nodes $N'$ have been considered, the node $N$ is tranferred from the *useful* set $U$ to the *visited* set $V$, and you loop, looking at another node from $U$.

You stop when $U$ is empty, which eventually occurs, since no node is added to $U$ a second time.

The shared structure is a graph composed of all nodes in $V$ and all directed edges in $E$. It necessarily contains $S$ and $T$. The set of minimal solution is precisely the set of directed paths from $S$ to $T$ in that graph. They are easily followed since they are directed. Whether you enumerate those paths, or do anything else with them, is another story. Note that, up to the fact that its edges are directed, this graph is smaller than (or at worse equal to) the initial graph being analyzed, so that it is tractable.

Let $v$ and $e$ be respectively the number of nodes and edges. Each edge of the original graph is considered at most twice, and when it is processed the node $N'$ at the upstream end may have to be searched in $U\cup V$ at a cost $O(\log v)$. This gives a total extra cost of $O(e\log v)$, in addition to the initial computation of distances with Dijkstra's algorithm.

There are probably better ways of doing this, but that is the solution that came to me. Hopefully there are no bugs. I do think there is a more general way to describe such techniques, but my memory is what it is.

---
Tags: algorithms, graphs, shortest-path, enumeration
---


title: 4-color to 3-color polynomial reduction

text:
# Question
Title: 4-color to 3-color polynomial reduction
I know a simple reduction from 3-color to 4-color. But how do you reduce 4-color to 3-color ?

I have been searching for the right way to make this reduction for a while now. I would love some pointers.

# Answer
> 5 votes
For a more general reduction, László Lovász \[1\] proved that

> COLORABILITY reduces to 3-COLORABILITY

The COLORABILITY problem is defined as follows:

> *Input:* A graph $G$ and a positive integer $k$.
>
> *Problem:* Is $G$ $k$-colorable?

That is, the reduction given by László Lovász is applicable to any $k$ ($k \ge 4$).

However, this reduction *is* quite intricate. You can find an excellent explanation by Vašek Chvátal here. Please free feel to ask if you have some difficulty in understanding this reduction.

---

\[1\] Coverings and coloring of hypergraphs, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., Winnipeg, Man., 1973.

# Answer
> 3 votes
Here is a summary of the solution of the homework problem for the "New CS 473" class in Spring 2015 at UIUC (Question #4 here).

Let a 4-coloring consist of colors $\\{0, 1, 2, 3\\}$, and $\\{0, 1, 2\\}$ for a 3-coloring.

For any graph $G = (V\_G, E\_G)$, construct a new graph $H = (V\_H, E\_H)$ such that:

* $H$ has one "ground vertex" $x \in V\_H$.
* $\forall v \in V\_G$, create a "vertex gadget" which consists of vertices $v^{+}, v^{-}$ such that $(v^+, x), (v^-, x) \in E\_H$, but $(v^+, v^-) \notin E\_H$. In a 3-coloring, $v^+, v^-$ are either colored 0 or 1. There are 4 valid states, which correspond to the different colorings of $v \in V\_G$.
* $\forall (u, v) \in E\_G$, create an "edge gadget" in $H$, which consists of 7 vertices: $a^+, b^+, c^+, a^-, b^-, c^-, d$, and create the following edges (each item is a vertex, and has an edge to each of the vertices in the list after the $\rightarrow$). I duplicated edges for lower items that are already presented in higher items for ease of verification by the reader.
    + $x \rightarrow v^+, v^-, u^+, u^-, d$
    + $u^+ \rightarrow a^+, x$
    + $u^- \rightarrow a^-, x$
    + $a^+ \rightarrow b^+, c^+, u^+$
    + $a^- \rightarrow b^-, c^-, u^-$
    + $c^+ \rightarrow a^+, b^+, d, c^-$
    + $c^- \rightarrow a^-, b^-, d, c^+$
    + $d \rightarrow x, c^+, c^-$
    + $b^+ \rightarrow a^+, c^+, v^+$
    + $b^- \rightarrow a^-, c^-, v^-$
    + $v^+ \rightarrow b^+, x$
    + $v^- \rightarrow b^-, x$.

If $H$ is 3-colorable, then any 2 vertex gadgets connected by an edge have different states. If $u^+, v^+$ are the same color, then $c^+$ is the same color $\rightarrow d$ must be colored 0 or 1, so either $c^+, c^-$ has the color of $x \rightarrow$ either $v^+, u^+$ are not the same color, or $v^-, u^-$ aren't $\rightarrow$ we have created a proper 4-coloring of $G$.

If $G$ is 4-colorable, then $\forall u \in V\_G$, give color 0 or 1 to the corresponding vertices in $H$ such that $u.color = 2 \times u^+.color + u^-.color$. Therefore, each edge gadget has a valid 3-coloring (can see that 3 of $\\{u^+, u^-, v^+, v^-\\}$ are the same color, or 2 of them are color 0 and the other 2 are color 1). Therefore, this is a proper 3-coloring of $H$.

Therefore, $G$ is 4-colorable $\Leftrightarrow$ $H$ is 3-colorable.

# Answer
> 2 votes
Here's a construction that does the reduction.

See diagram:

The idea is to construct a graph that is 3-colourable iff an original graph is 4-colourable. So, replace each node by a pair of nodes. Add one instance of 3 nodes, completely connected, forcing all three colours to be there, RGB. For a given XY edge, the construction will be colourable in 3 colours iff X!=Y.

A, F, E and J will be either B or R (4 combination matching to 4 colours in the original graph). C will be non-A, and H will be non-F. D can only be G if A!=E. I can only be G if F!=J.

Hence there's D or I being G only if X != Y. But you need D or I being G in order to color K and L. So, if you can colour the construction below, X and Y are of two different colour, for a given coding of the four colour in pairs of (R,B).

It follows that if you can colour the whole resulting graph in 3 colours, after apply the same construction to all edges, you can also colour the original graph in 4 colours.

======= Previously suggested reading: (which yes, was a weak answer)

https://math.stackexchange.com/questions/294674/polynomial-time-reduction-at-least-as-hard-as-3-color-and-4-color

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


# Question
Title: Versions of NP with different logical unifiers
One formulation of NP is this: a language is in NP if it can be solved in polynomial time by an algorithm that has access to a special "Nondeterministic Bit" function, which branches the world into two alternate universes, writes a $1$ on the worktape in the first universe and a $0$ in the second, finishes the computation in each universe, and then returns the OR of the computation value of each universe.

If we replace the OR in this formulation with an AND, we get coNP.

I'm wondering what complexity class is described if we use the other nontrivial symmetric binary logical operators.

$\text{OR} \to NP$

$\text{AND} \to coNP$

$\text{XOR} \to \\,?$

$\text{NAND} \to \\, ?$

$\text{NOR} \to \\,?$

$\text{EQUALS} \to \\, ?$

# Answer
> 4 votes
In the case of XOR or EQUALS, you get the class $\oplus$P, which includes the graph isomorphism problem.

In the case of NAND or NOR, I believe that you get PSPACE. Indeed, PSPACE is an upper bound, and you should be able to solve QBF in this model.

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


# Question
Title: Why Halting problem is Recursively Enumerable?
If we take this definition as R.E. set definition (`Computability, Complexity and Languages book written by Davis in page 79`)

> $Definition.$The set $B\subseteq N$ is called r.e. if there is partially computable function $g(x)$ such that
>
> $B = \\{x \in N | g(x) \downarrow\\}$

Halting problem is set of $(x,y)$ which program with number $y$ halts on $x$, I really can't understand when there is no program for Halting problem then what $g(x)$ is going to be applied for it?

# Answer
If you want to understand Halting Problem is r.e. by Davis Book notation and you are looking for g(x) you can think of universal program! universal program is the function $\phi (x,y)$ that is the program which run program number $y$ on input $x$. This program is equal to partially computable function g(x) (see page 30 definition of partially computable). As Ran G mentioned, it is possible program y on input x never halt! That's the reason it is partial function not computable function(i.e. it is both partial and total)

+If function g(x) be computable then the set B will be computable or in the other words it is decidable.
> 1 votes

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


title: Logical Reduction

text:
# Question
Title: Logical Reduction
Reducing one computable problem to another by providing an algorithm which transforms an instance of one problem to one of the other (and limiting the time or space of that algorithm) is clear to me. However, I fail to understand how reductions via logic work, e.g. a reduction in FO. My biggest problem is that the structures themselves would have to be encoded as a structure to be accessible to such a reduction. Could someone provide me with an example of a reduction in logic?

If it is not clear what I am talking about, maybe an example helps: Reducing SAT to 3SAT can be done in PTIME, so there should be an LFP reduction as well. How would the formula in LFP look like which performs the transformation of an instance of SAT to an instance of 3SAT?

# Answer
David Richerby already answered the question partially but I had the chance to ask the professor for logic at my university today. He showed me one kind of logical reduction.

Given two problems, $X$ and $Y$, to reduce $X \leq\_\text{FO} Y$: Let $\tau$ be the signature of the instances in $X$ and $\sigma$ the signature of instances in $Y$. Let $\mathfrak{A} = (A, \tau)$ be an instance of $X$. The FO-reduction from $X$ to $Y$ is defined as a set of $\text{FO}(\tau)$-formulas $\delta(\overline{x}), \left( \varphi\_i(\overline{x}) \right)\_{i \in \sigma}$, where $\overline{x}$ are tuples of variables of any fixed size.

Then $\mathfrak{B} = (B, \sigma)$ is defined as $B = \\{\overline{a} \in A \mid \mathfrak{A} \models \delta(\overline{a})\\}$ and for all $i \in \sigma$, $i^\mathfrak{B} = \\{\overline{a} \in A \mid \mathfrak{A} \models \varphi\_i(\overline{a})\\}$.

One advantage of this reduction is that if it is correct, one can also use the transformation to find a formula which decides $X$ (assuming one has a formula $\psi$ for $Y$). This is done by relativizing the quantifiers ($\exists x \vartheta(x)$ is replaced by $\exists \overline{x} \vartheta(\overline{x}) \land \delta(\overline{x})$) and symbols from $\sigma$.
> 2 votes

# Answer
Logical reductions work in essentially the same way as computational ones. In computational reductions, you show how to *compute* an instance of the target problem; in logical reductions, you show how to *define* it. In practical terms, that's often almost the same thing since, for example, you reduce clique to independent set just by saying "Swap edges and non-edges", rather than defining an algorithm that actually does that.

When you're dealing super-formally with computational reductions, your input is normally assumed to be a string in some fixed alphabet, though one often just assumes it to be "a graph" or "a Boolean formula". The details of the encoding of such objects as strings are usually not important.

Typically, when you're dealing with logical reductions, your input is assumed to be a relational structure of some appropriate vocabulary, rather than a string. (Strings can, themselves, be represented as relational structures, should you need to do that.) You typically have to be very precise about what the vocabulary is since, otherwise, it's impossible to write formulae. So, for example, to reduce clique to independent set, you'd say that your graph is defined as a binary relation $E$, denoting the edges, and the edge relation of the new graph is defined by the formula $\phi(x,y)\equiv \neg E(x,y)$.

As for writing an LFP formula to reduce SAT to 3SAT, that's, er, left as an exercise to the reader. I'd be surprised if one could formally describe such a reduction in less than a couple of pages.

That's a bit of a cop-out, I admit, as was choosing a near-trivial example. The first obvious difficulty in more complicated examples is producing an instance $J$ with a larger universe than the original instance $I$. To deal with this, elements of the universe of $J$ are represented by tuples of $I$-elements. Writing $n$ for the size of $I$'s universe, the simple case of needing $J$ to have $n^k$ elements is dealt with by using $k$-tuples. For more complicated cases, there are a variety of techniques. If you have a linear order available, you can restrict components of the tuples using that (e.g., "the second element of the pair must be one of the first four elements of the order" gives you a universe of size $4n$). Any definable set can be used in a similar way. Another trick is to produce $J$ plus a lot of garbage and somehow define away the garbage. For example, you might define $J$ in a way that causes it to have multiple garbage components but be able to say "I'm only interested in the component that contains this special vertex."
> 4 votes

---
Tags: reductions, logic
---


title: Making a finite automata

text:
# Question
Title: Making a finite automata
How can I make a finite automaton which does not end in string ab.

With the alphabet a,b

I made 3 states. For the first one it is accepting states and thus accept the empty string.

So here is a table I made. State 1 is initial state

```
        input   goes to state input goes to state

```

State 1

```
         b       1             a      2

```

state 2

```
          b       3             a       2

```

state 3

```
            b       3              a      3

```

But will it work?

# Answer
> 4 votes
Here is your suggested automaton, if I understand your transitions correctly (initial state is 1)

This automaton will only accept $\epsilon$, and words consisting of a number of $b$'s

**Hints to make one that accepts your language:**

Make sure that it accepts $\epsilon, a, b$ and make sure that you "move away" from accepting states when seeing a $b$ after an $a$ (keep in mind that $aabb$ is also a string in the language, i.e the second $b$ should make the machine go to an accepting state).

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


title: Understanding Gustafson's Law

text:
# Question
Title: Understanding Gustafson's Law
Wikipedia says about Gustafsons's law that:

> It may even be the case that $\alpha$ diminishes as $P$ (together with the problem size) increases.

I'm not understanding how $\alpha$ can ever change given it's definition:

$$ \alpha= a / (a + b)$$

I thought that $a$ and $b$ are constants independent of the problem size.

What am I missing?

# Answer
> 5 votes
First I suggest you to read the original article "Reevaluating Amdahl's Law" (CACM'1988) by John L. Gustafson when you have difficulty with the wiki article. Notice that I will use the notations from the original article: $s$ for serial time; $p$ for parallel time; $N$ for number of processors.

In the original article, the author mentioned that Amdahl's Law is based on an **unrealistic assumption** that *"$p$ is independent of $N$"*, where $p$ is the amount of time spent (by a serial processor) on parts of the program that can be done *in parallel*.

Then, the author pointed out two key observations:

> 1. In practice, the problem size scales with the number of processors.
> 2. As a first approximation, we have found that it is the **parallel or vector** part of a program that scales with the problem size.

More explicitly, times for vector startup, program loading, *serial* bottlenecks and I/O that make up the $s$ (*serial*) component of the run do not grow with problem size; however, the amount of work that can be done *in parallel* varies linearly with the number of processors.

As a result, as $N$ (the number of processors; together with the problem size) increases, the portion of parallel time ($p$) increases according to the two observations given above, and the portion ($\alpha$) of serial time ($s$) diminishes (in most/common cases).

# Answer
> 0 votes
The easiest way to understand it is to realize that the **Percentage of serial work** is a function of the problem size - it's not a simple constant value independent of problem size.

If the beginning of a parallel job requires $1000$ instructions of setup no matter what the problem size, yet we can keep feeding it larger problem instances, then the percentage of serial work effectively goes to zero.

Imagine that the amount of serial work is $\mathcal{O}(n \log n)$, but the size of parallelizable work is $\mathcal{O}(n \times n)$. This might match up with getting ready to process an $n \times n$ matrix on $n$ processors. Eventually, the amount of serial work is negligible compared to the parallelizable work.

I have gone through the process of deriving **Gustafson's law** from **Amdahl's law**. It's just an algebraic re-arrangement of the original statement of **Amdahl's law**.

---
Tags: parallel-computing
---


# Question
Title: Birkhoff-von Neumann theorem for bistochastic digraphs
A weighted digraph (with loops) is *bistochastic*, iff

1. the weights are non-negative,
2. for all non-sink nodes, the sum of the edge weights of the out-edges is $1$, and
3. for all non-source nodes, the sum of the edge weights of the in-edges is $1$.

The Birkhoff-von Neumann theorem for a bistochastic matrix states that a bistochastic matrix is a convex combination of permutation matrices. It would be nice to characterize the bistochastic digraphs with a given underlying digraph in a similar way as a convex combination.

---

**Attempted reduction to the Birkhoff-von Neumann theorem:** If the underlying digraph has no source and sink nodes, then we can conclude from the Birkhoff-von Neumann theorem that the convex combinations of the *in-degree = out-degree = 1* subdigraphs with n-nodes give all possible bistochastic digraphs (because a $n\times n$ permutation matrix corresponds to a *in-degree = out-degree = 1* digraph with $n$-nodes, and only subdigraph can occur in the convex combination since no edge can be canceled out).

If the number of source nodes is equal to the number of sink nodes, then connecting each sink with exactly one source allows to reduce the problem to the previous case (because the weight of the newly added edges can only be 1). But if the number of source nodes is different from the number of sink nodes, then I guess that there exists no bistochastic digraph for that underlying digraph. The weights seem to define a flow on the digraph, so the min-cut max-flow theorem should help.

Even so this reduction seems to work, the case distinctions feel less attractive than the Birkhoff-von Neumann theorem. I would prefer to reduce it completely to the Birkhoff-von Neumann theorem (by connecting each sink with each source?), or reduce it completely to the min-cut max flow theorem (or something similar).

# Answer
> 2 votes
From Roger A. Horn "Topics in Matrix Analysis", section 3.2 page 164-165.

> A matrix $Q$ is said to be *doubly substochastic* if its entries are nonnegative and all its row and column sums are at most one.

The doubly stochastic matrix $\begin{bmatrix} Q & I-D\_r\\I-D\_c & Q^T\end{bmatrix}$ is a dilation of $Q$, where $D\_r$ and $D\_c$ are diagonal matrices with the row and column sums of $Q$ respectively. This dilation allow to reduce the generalization of the Birkhoff-von Neumann theorem for substochastic matrices to the original theorem

> Every doubly substochastic matrix is a finite convex combination of partial permutation matrices.

The bistochastic digraphs are doubly substochastic matrices, so the generalized Birkhoff-von Neumann theorem can be applied directly for them. Or one can just apply the same reduction directly. This means taking the original digraph and a copy of the digraph where all edges are reversed, and connecting the sources and sinks to their copy by suitable oriented edges of weight 1.

However, it turned out that the notion of a doubly substochastic matrix is more suitable with respect to the original motivation for this question than the notion of a bistochastic digraph. It is a good thing that the above construction directly covers that case too.

---
Tags: graphs, proof-techniques
---


# Question
Title: Big O notation comparison with constant time
So, I'm new to this whole asymptomatic notation with respect to algorithms. So say you have a $f(n) = 1/n$ and $g(n) = 1$, would it be OK to say that $f(n)$ is not equal or is not an element of $O(g(n)) $? I say this because I'm actually drawing an analogy with another example. Say in my second example $f(n) = n$ and $g(n) =n^2$ then I'm sure that $f(n) = O(g(n))$.

# Answer
> 1 votes
In fact, $1/n = O(1)$. Recall the (simplified) definition of big O: for positive functions $f,g$, $f(n) = O(g(n))$ if there exists a constant $C \> 0$ such that $f(n) \leq Cg(n)$ for all $n$. In your case, the constant $C = 1$ would do since $1/n \leq 1$ for all $n$.

The fact that $f(n) = O(g(n))$ just means that $g(n)$ is an *upper* bound on $f(n)$, i.e., that $g(n)$ grows at least as fast as $f(n)$. The two functions need not have the same order of growth.

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


# Question
Title: If L1 ∪ L2 and L1 are regular, is L2 also regular?
This is a problem in a theory of computation book that's stumping me:

> Suppose that we know that $L\_1 ∪ L\_2$ and $L\_1$ are regular. Can we conclude that $L\_2$ is regular? Explain.

At first, I thought I could build the NFA that is the union of two DFAs, one which accepts $L\_1$, and one which we don't know about. Then lambda transition over to the $L\_1$ DFA. Then, the union would be regular, but we wouldn't be able to conclude anything about the $L\_2$ DFA.

I think my reasoning is poor though. Could someone please point me in the right direction?

Thank you.

# Answer
No, since $\Sigma^\* \cup L$ and $\Sigma^\*$ are regular languages, for any $L$ and there are non-regular languages, we cannot conclude anything about $L$.
> 1 votes

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


# Question
Title: Merging Sorted lists using Heap Data Structure
Suppose there are $\lceil\log n\rceil$ sorted lists of $\lceil\frac{n}{\log n}\rceil$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure)

1. $O(n \log \log n)$
2. $θ(n \log n)$
3. $Ω(n \log n)$
4. $Ω(n^{\frac{3}{2}})$

My approach:

I know complexity of heap sort is $O(n \log n)$. But little bit confused form where to start.

# Answer
> 5 votes
Hint: Try to merge the lists in the correct way, using the fact that merging lists of size $m\_1,m\_2$ costs $O(m\_1+m\_2)$. If you do this correctly, you will obtain an $O(n\log\log n)$ algorithm.

We can also get a matching lower bound. The number of possible answers is $$ \begin{align\*} \frac{n!}{(n/\log n)!^{\log n}} &\sim \frac{\sqrt{2\pi n}(n/e)^n}{\sqrt{2\pi n/\log n}^{\log n}(n/e\log n)^n} \\ &\sim \frac{(\log n)^{\log n}}{\sqrt{2\pi n}^{\log n-1}}(\log n)^n. \end{align\*} $$ The dominant term here is $(\log n)^n = \exp(n\log\log n)$, and we get an $\Omega(n\log\log n)$ lower bound in the decision tree model.

---
Tags: algorithms, heaps
---


# Question
Title: Can a propositional threshold connective be expressed by standard connectives?
We are given a finite set of propositional atoms $\\{x\_1, \dots, x\_n\\}$ and an integer $k$. Can we capture through a propositional formula $\varphi$ (built from the standard connectives $\neg, \wedge, \vee$ only) the set of all models having at most $k$ atoms valued at $1$, such that the size of $\varphi$ is polynomial w.r.t. $n$? If yes, how?

The only way I see is to define $\varphi$ as an exponential-sized DNF formula containing $\binom{n}{k}$ conjunctions of literals. For instance, for n=5 and k=2, the corresponding formula would be $(\neg x\_1 \wedge \neg x\_2 \wedge \neg x\_3) \vee (\neg x\_1 \wedge \neg x\_2 \wedge \neg x\_4) \vee (\neg x\_1 \wedge \neg x\_2 \wedge \neg x\_5) \vee (\neg x\_2 \wedge \neg x\_3 \wedge \neg x\_4) \vee (\neg x\_2 \wedge \neg x\_3 \wedge \neg x\_5) \vee \dots$

I got the following comment for the same question on https://cstheory.stackexchange.com/ but I do not have the level to understand it. I googled all keywords but I still cannot find the answer.

> $d\_H(\omega, \omega')$ equals the number of 1 bits in the pointwise XOR of $\omega$ and $\omega'$. So, compute the XORs, count the number of 1 bits, and compare the result to k. It is well known that one can count bits with log-depth circuits (hence polynomial-size formulas), and one easy way to do that is to sum the individual bits using repeated 3-to-2 carry-save addition. See en.wikipedia.org/wiki/Carry-save\_adder if you don’t know what that is. The choice of the basis of connectives is immaterial in all this, as long as it is complete

# Answer
> 4 votes
The idea is to use the following steps:

1. Construct an NC1 circuit computing the binary representation of $x\_1+\cdots+x\_n$, see for example these lecture notes (Theorem 7). This circuit implements carry-save addition.
2. Convert the NC1 circuit to a polynomial size formula, see for example these lecture notes (Proposition 1).
3. For each $k$, it is now easy to construct a polynomial size formula that tests whether $x\_1+\cdots+x\_n=k$.
4. Use up to $n$ of the formulas from the previous step to come up with your desired formula.

You can in fact implement the last two steps more efficiently, using $\log n$ rather $n$ copies of the preceding formula, by using a comparison gadget; details left to you.

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


# Question
Title: Generate Regular Grammar for a Language with Modular Condition
This is a homework problem. I've wrestled with it for quite awhile and can't come up with a valid solution. The problem is:

Find a regular grammar that generates each of the following languages: $$L = \\{ w \in {a,b}^\* \mid \text{na}(w) – \text{nb}(w) = 1 \mod 3 \\} , $$

where $\text{na}(w)$ is the number of $a$s and $\text{nb}(w)$ the number of $b$'s occurring in $w$, respectively.

It seems as though a DFA can't accept this language since any difference of $a$'s and $b$'s resulting in 1 will be in the language, but that gives an infinite number of possibilities.

Any help pointing me in the right direction for this problem would be much appreciated.

# Answer
> 3 votes
Hint: How many states do you need to keep track of $n\_a(w)-n\_b(w) \pmod{3}$, where $w$ is any prefix of the input? Consider how many possibilities this quantity has, and whether knowing the value for a word $w$ helps you calculate the value for the word $w\alpha$ ($\alpha$ being a single symbol).

---
Tags: formal-languages, regular-languages, formal-grammars
---


# Question
Title: Integer Programming - packing wolves and sheep
I'm new to linear/integer programming and I'm trying to solve a little problem I made up. I want to "pack" animals into a minimum number of bins where some of the animals cannot co-exist (wolves and sheep). Here is a picture of my little flow network that's guiding me.

* Imagine that each animal node outputs 1 animal of that type.
* The maximum each bin can hold is 2 animals
* You don't want wolves together with sheep

I've figured out how to write constraints that would allow me to minimize the number of bins if there is no distinction in input type.

What I've tried so far is the following. I take two inputs and sum them. I also take the input type and compare them so that I get either a zero or 1. At the final node, multiple the 0 or 1 with the summation and you get either the sum or nothing.

My questions come into play here in the following:

* Is there such a thing as a comparison operation that you can use in Integer Programming? I can subtract two types and if it's zero, they're the same, otherwise no. I'm not sure how one would represent this mathematically if one wanted to solve something like this in software.
* My "solution" below won't work for just one sheep node since I can't compare sheep to anything to get the sheep through. Actually, if I were to do wolf and sheep first, and then wolf, this would return 0 as well. Would I have to duplicate my little tree snippet and run through all combinations of input nodes? Is there a more scalable way to do this?

Any suggestions are appreciated.

mj

# Answer
> 2 votes
I would approach it in the following way:

Suppose that I have the following sets:

* $A$ - the set of all type of animals, i.e. $A = \\{\text{wolf},\text{sheep}\\}$
* $B$ - the set of all possible bins. $B = \\{B\_1, \ldots, B\_{n\_B} \\}$

Suppose I have the following parameters:

* $c$ - a 1-dimensional matrix of the size of $A$, indicating the number of animals, per type that exist. Example: $c = \\{2,3\\}$ would mean that there are 2 wolfs and 3 sheeps.
* $n\_B$ - the number of bins available.

And suppose I have the following variable:

* $M$ - is the integer matrix $A \times B$ that represents the number of animals per bin. Rows are animals, columns are bins. $M(\text{wolf},B\_1) = 2$, for example, would mean that there are 2 wolfs in bin $B\_1$.

So, for example, the following matrix:

$$ M = \left\[ \begin{array}{ccc} 2 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right\] $$

would indicate that there are 2 wolfs in $B\_1$, 1 in $B\_2$ and 1 sheep in $B\_3$.

Your model would be:

$$ \begin{align} & \text{Minimize} & & U = \sum\_{i = 1}^{n\_B} 1 & \text{such that} \sum\_A M\_{ab\_{i}} \> 0 \\ & \text{subject to} & & \sum\_A M\_{ab} \leq 2 & \forall b, \\ &&& \prod\_A M\_{ab} = 0 & \forall b, \\ &&& \sum\_B M\_{ab} = c\_a & \forall a, \\ \end{align}$$

where $a$ is an element of $A$ and $b$ an element of $B$ and $b\_i$ is the element of set $B$ at position $i$.

The OBJECTIVE FUNCTION U is the sum of all bins that are actually being used, and it is this sum that you want to minimize. There might be more elegant ways of defining that, but this is what I could think at the moment. Essentially you would count all bins that contain at least one animal - $\sum\_A M\_{ab\_{i}} \> 0$ represents that. In GAMS Programming language, I could represent this as what they call a dollar sign condition ($), check the language you are using to see how to impose this condition to the equation.

The FIRST CONSTRAINT indicates that there can be a maximum of 2 animals per bin - it translates to the following equations:

$$ \begin{align} & M\_{\text{wolf},B\_1} + M\_{\text{sheep},B\_1} \leq 2 &\text{(rules for bin $B\_1$)} \\ & M\_{\text{wolf},B\_2} + M\_{\text{sheep},B\_2} \leq 2 &\text{(rules for bin $B\_2$)} \\ ... \\ & M\_{\text{wolf},B\_{n\_B}} + M\_{\text{sheep},B\_{n\_B}} \leq 2 &\text{(rules for bin $B\_{n\_B}$)} \\ \end{align}$$

The SECOND CONSTRAINT limits the type of animals that can be put together - there can only be animals of one type in the bin, so that $M\_{\text{wolf},B\_1} \cdot M\_{\text{sheep},B\_1} = 0$, etc.

The THIRD CONSTRAINT limits the number of animals to be put in the bins to the number of animals available.

---
Tags: optimization, integer-programming
---


# Question
Title: How to write recurrence relation for the following scenario?
> A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function $g(x)$ for each node x. If the cost of computing $g(x)$ is **min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x}** then what is the worst case time complexity?

Since $g(x)$ is applied on the 2 halves of the binary tree, I guess the recurrence relation must look something like :
$$T(n) = 2T\Big(\frac{n}{2}\Big)+k$$
What I could understand from the question is that $g(x)$ is applied on all the $n$ nodes and instead of $k$ it must be something of the order $O(n)$ but I'm not sure what it is. Am I heading in the right direction?

# Answer
Hints:

Can you make a guess? If you can make a guess, can you prove it?

What do you know about the height of a balanced search tree?

If the entire tree has $n$ nodes, what can you say about the number of nodes in the left subtree? What is the smallest it could be? The largest it could be? What about the right subtree?

Can you derive a recurrence relation?

Imagine you treat the cost of computing $g(x)$ to be measured in dollars, and you charge \\$1 to each node in the right/left subtree (whichever is smaller) to account for the cost of computing $g(x)$. For any given node, what can you say about how many dollars it is charged?

If you know about amortized analysis, you might review that material.

It's not clear to me what $k$ represents in your proposed approach or where you got that recurrence relation. Why don't you try harder to work out what recurrence relation might be suitable and what its solution is?
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation, binary-trees
---


# Question
Title: Can number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states?
As title says, can the number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states - that is if the NFA recognizes the same language as the DFA and has $n$ states, can DFA have more than $2^n$ states?

I think it is, and this is trivially. However Wikipedia seeems to write that it is not possible to have more than $2^n$ states. So comes the question.

# Answer
it surely **can**, but it needs not. Using the powerset construction you can convert any $n$-state NFA into a DFA with at most $2^n$ states.
> 4 votes

---
Tags: complexity-theory, finite-automata
---


title: Modeling concurrent algorithms

text:
# Question
Title: Modeling concurrent algorithms
I'm working on a class library (C++) that can be thought of as a producer/consumer queue of producer/consumer queues. There are many queues of data, and the goal is to assign worker threads to process these queues, as needed, using coroutines. At any rate, the details aren't necessarily important to the question, but I'm struggling to wrap my head fully around the synchronization requirements.

I've started with a list of basic operations (like adding an element to the top level queue), along with some preconditions, postconditions, and what I'm calling "exclusions" which are things that are not supposed to happen during the operation. It seems to only scratch the surface though.

Finally, my question: Is there a way to model algorithms (either notation or diagram) that helps to tease out temporal ordering requirements? What needs to be locked when? What transactions need to be atomic? What order can reads/writes be carried out in?

# Answer
You have mentioned the temporal ordering of events, then you may have known about temporal logic \[1\] such as LTL \[2\] and CTL \[3\]. Temporal logic allows you to reason about time and thus temporal ordering of events. For instance (from \[1\]), one may wish to say that *whenever* a request is made, access to a resource is *eventually* granted, but it is *never* granted to two requestors simultaneously.

The greatest advantage of using LTL or CTL to express the properties of the system is that you can automatically verify them. This process is known as model checking \[4\].

There are quite a few of model checkers \[5\]. For instance, in SPIN, systems to be verified are described in Promela (Process Meta Language), which allows one to specify "atomic blocks" (Is this your intention of `What transactions need to be atomic?`)?

As for the producer/consumer problem, it has been extensively studied in the context of model checking. This lecture note uses it as an example for SPIN (you can easily find other resources). In addition, \[6\] verifies an edition written in SystemC, and \[7\] verifies it using TLA+.

---

\[1\] temporal logic (wiki)

\[2\] LTL (wiki)

\[3\] CTL (wiki)

\[4\] model checking (wiki)

\[5\] model checkers (wiki)

\[6\] Verifying SystemC: a Software Model Checking Approach

\[7\] An Example of Debugging Java with a Model Checker (web page)
> 3 votes

# Answer
Usually, when trying to model concurrency, I see a lightweight version of CSP being used. It models the externally relevant behavior of a pair of processes as state machines that communicate (synchronize) by performing same-actions at the same time.

http://en.wikipedia.org/wiki/Communicating\_sequential\_processes
> 2 votes

---
Tags: concurrency, synchronization, temporal-logic
---


# Question
Title: Recurrences and Generating Functions in Algorithms
Combinatorics plays an important role in computer science. We frequently utilize combinatorial methods in both analysis as well as design in algorithms. For example one method for finding a $k$-vertex cover set in a graph might just inspect all $\binom{n}{k}$ possible subsets. While the binomial functions grows exponentially, if $k$ is some fixed constant we end up with a polynomial time algorithm by asymptotic analysis.

Often times real-life problems require more complex combinatorial mechanisms which we may define in terms of recurrences. One famous example is the fibonacci sequence (naively) defined as:

$f(n) = \begin{cases} 1 & \text{if } n = 1 \\ 0 & \text{if } n = 0 \\ f(n-1) + f(n-2) & \text{otherwise} \end{cases} $

Now computing the value of the $n$th term grows exponentially using this recurrence, but thanks to dynamic programming, we may compute it in linear time. Now, not all recurrences lend themselves to DP (off hand, the factorial function), but it is a potentially exploitable property when defining some count as a recurrence rather than a generating function.

Generating functions are an elegant way to formalize some count for a given structure. Perhaps the most famous is the binomial generating function defined as:

$(x + y)^\alpha = \sum\_{k=0}^\infty \binom{\alpha}{k}x^{\alpha - k}y^k$

Luckily this has a closed form solution. Not all generating functions permit such a compact description.

> Now my question is this: how often are generating functions used in *design* of algorithms? It is easy to see how they may be exploited to understand the rate of growth required by an algorithm via analysis, but what can they tell us about a problem when creating a method to solve some problem?

If many times the same count may be reformulated as a recurrence it may lend itself to dynamic programming, but again perhaps the same generating function has a closed form. So it is not so evenly cut.

# Answer
> 11 votes
Generating functions are useful when you're designing counting algorithms. That is, not only when you're looking for the number of objects having a certain property, but also when you're looking for a way to enumerate these objects (and, perhaps, generate an algorithm to count the objects). There is a very good presentation in chapter 7 of *Concrete Mathematics* by Ronald Graham, Donald Knuth, and Oren Patashnik. The examples below are from these books (the mistakes and lack of clarity are mine).

Suppose that you're looking for the ways to make change with a given set of coins. For example, with common US denominations¹, the possible coins are $\[1\], \[5\], \[10\], \[25\], \[100\]$. To give ¢42 in change, one possibility is $\[25\]\[10\]\[5\]\[1\]\[1\]$; another possibility is $\[10\]\[10\]\[10\]\[10\]\[1\]\[1\]$. We'll write $42 \langle \[25\]\[10\]\[5\]\[1\]^2 \rangle = \langle \[10\]^4 \[1\]^2 \rangle$. More generally, we can write a generating function for all the ways to give change: $$H = \sum\_{h\ge0} \sum\_{q\ge0} \sum\_{d\ge0} \sum\_{n\ge0} \sum\_{p\ge0} \[100\]^h \[25\]^q \[10\]^d \[5\]^n \[1\]^p$$ In more technical terms, $H$ is a term in the space of power series over the five variables $\[100\], \[25\], \[10\], \[5\], \[1\]$. Define the valuation of a monomial in this space by $$\langle \[100\]^h \[25\]^q \[10\]^d \[5\]^n \[1\]^p \rangle = 100 h + 25 q + 10 d + 5 n + p$$ Then the ways to give $v$ cents in change are the number of monomials whose valuation is $v$. We can express $H$ in an incremental fashion, by first writing down the ways $P$ to give change in pennies only, then the ways $N$ to give change in pennies and nickels, and so on. ($I$ means no coin.) $$\begin{gather\*} P = I + \[1\] + \[1\]^2 + \[1\]^3 + \ldots = \frac{I}{I - \[1\]} \\ N = (I + \[5\] + \[5\]^2 + \[5\]^3 + \ldots) P = \frac{P}{I - \[5\]} \\ D = (I + \[10\] + \[10\]^2 + \[10\]^3 + \ldots) N = \frac{N}{I - \[10\]} \\ Q = (I + \[25\] + \[25\]^2 + \[25\]^3 + \ldots) D = \frac{D}{I - \[25\]} \\ H = (I + \[100\] + \[100\]^2 + \[100\]^3 + \ldots) Q = \frac{Q}{I - \[100\]} \\ \end{gather\*}$$ If you want to count and not just enumerate the ways to give change, then there is a simple way to use the formal series we've obtained. Apply the homomorphism $$S: \quad \[1\] \mapsto X, \quad \[5\] \mapsto X^5, \quad \[10\] \mapsto X^{10}, \[25\] \mapsto X^{25}, \[100\] \mapsto X^{100} $$ The coefficient of $X^v$ in $S(C)$ is the number of ways to give $v$ cents in change.

A harder example: suppose that you want to study all the ways to tile rectangles with 2×1 dominoes. For example, there are two ways to tile a 2×2 rectangle, either with two horizontal dominoes or with two vertical dominoes. Counting the number of ways to tile a $2 \times n$ rectangle is fairly easy, but the $3 \times n$ case quickly becomes nonobvious. We can enumerate all the possible tilings of a horizontal band of height 3 by sticking dominoes together, which quickly yields repetitive patterns: $$\begin{cases} U = \mathsf{o} + \mathsf{L} V + \mathsf{\Gamma} \Lambda + \mathord{\equiv} U \\ V = \substack{\mathsf{I}\\\strut} U + \substack{=\\\\:-} V \\ \Lambda = \substack{\strut\\\mathsf{I}} U + \substack{\\:-\\\=} \Lambda \\ \end{cases}$$ where the funny shapes represent elementary domino arrangements: $\mathsf{o}$ is no domino, $\mathsf{L}$ is a vertical domino on top of the left part of a horizontal domino, $\substack{\strut\\\mathsf{I}}$ is a vertical domino aligned with the bottom of the band of height 3, $\substack{\\:-\\\=}$ is a horizontal domino aligned with the top of the band plus two horizontal dominoes below it and one step to the right, etc. Here, multiplication represents horizontal concatenation and is not commutative, but there are equations between the elementary patterns that form variables in this power series. As before with the coins, we can substitute $X$ for every domino and get a generating series for the number of tilings of a $3 \times (2n/3)$ rectangle (i.e. the coefficient of $X^{3k}$ is the number of ways to tile a rectangle of area $6k$, which contains $3k$ dominoes and has the width $2k$). The series can also be used in more versatile ways; for example, by distinguishing vertical and horizontal dominoes, we can count the tilings with a given number of vertical and horizontal dominoes.

Again, read *Concrete Mathematics* for a less rushed³ presentation.

¹ <sub> I know my list is incomplete; assume a simplified US suitable for mathematical examples.² </sub>
² <sub> Also, if it comes up, assume spherical coins. </sub>
³ <sub> And better typeset. </sub>

# Answer
> 10 votes
I remember a problem I had to solve during a student programming contest in 2001. The problem was this one:

> Given masses of 1, 7, 13, ... (I don't remember which masses, but there was a finite, determinate set of masses), design a function that determines whether a given weight can be weighed on a scale with this set of masses.

I started with nested loops, but quickly hit a wall. Then I came to realize that I had to start with enumerating what can be done with the lighter masses before going on with the heavier ones. I could solve the problem with a lot of unnested loops.

Hadn't I been youthfully arrogant and self-sufficient at that time (and had I known about and practiced generating functions), I might have defined the problem with generating functions as such :

Define $f(x)$ as the OGF for the number of ways that a weight $n$ can be weighed given the set of masses.

What weight on the right pan can I weigh given a single mass of 1?

Three possibilities:

* If I put the mass on the left pan, I can weigh 1.
* If I put the mass on the right pan, I can weigh -1.
* If I don't use the mass, I can weigh 0.

So there is one way to weigh $-1$, one way to weigh $0$, and one way to weigh $1$. The generating function for this mass is something like $x^{-1} + 1 + x$, which corresponds to:

$$ \frac{1 - x^3}{x(1-x)} $$

The generating function for a single mass $m$ is $x^{-m} + 1 + x^m$, which is :

$$ \frac{1 - x^{3m}}{x^m(1-x^m)} $$

Given a multiset $M$ of masses, $f$ is expressed as the product of the single mass generating functions:

$$ f(x) = \frac{\prod\_{m \in M}(1 - x^{3m})}{x^{\sum\_{m \in M}m}\prod\_{m \in M}(1 - x^{m})} $$

Now, given a package that can perform operations on polynomials, you just have to :

* Calculate both products.
* Perform the division of these products, starting with the lowest degree. (which terminates)
* Shift the polynomial (euclidian division by $x^k$, keeping the quotient and dumping the remainder)

And you're done. Now your polynomial has the number of ways to weigh $w \ge 0$ at index $w$. The only input is the multiset of masses $M$.

I designed the algorithm using mathematically sound components. The main part of the algorithm, which is a polynomial division with lowest degree first, is linear and can be implemented by an off-the-shelf package. It may not be optimal, but it certainly performs better than what I did at the contest, and in a less error-prone way.

If you look closely at the division process, you quickly see that the remainder can be seen as the "current hidden state" at every state of the process, and the quotient as the result. The process terminates when the "current hidden state" reaches zero everywhere.

You can implement polynomials as arrays or, if they are really really sparse, as index-coefficient ordered lists, and this won't change the algorithm.

# Answer
> 3 votes
While developing an algorithm for monotone submodular maximization over a matroid, we had to solve the recurrence $$ \ell \gamma^{(m)}\_{\ell+1} = (2\ell-m) \gamma^{(m)}\_\ell + (m - \ell + 1) \gamma^{(m)}\_{\ell-1}, \quad \gamma^{(m)}\_0 = 1, \quad \gamma^{(m)}\_{m+1} = e. $$ After noticing that $\gamma^{(m)}\_\ell = m(\gamma^{(m-1)}\_\ell - \gamma^{(m-1)}\_{\ell-1})$, we reduced the problem to computing some universal sequence $\gamma^{(0)}$. The latter was accomplished using generating functions, and from there we got an explicit formula for $\gamma^{(m)}$, again using generating functions. You can find the solution in the paper if you're curious, though we never bothered to include this derivation.

# Answer
> 0 votes
Perhaps the extensive study of Quicksort, and its many variants, is the clearest example. There combinatoric considerations governed the consideration of alternatives, and analyzing the solutions to quite complex equations shows performance advantages (or not) of them.

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


# Question
Title: When states that are not accepting states become accepting states in NFA, what happens?
It is known that when NFA's accepting states are swapped with rejecting states, the recognized language is not complement of the original language. For some language, it may be the case that some strings that were recognized in the original NFA may still be recognized in the state-swapped NFA.

My question is, is there a language $L$ that in the original NFA a string is not recognized(rejected), but in the NFA where accepting states become rejecting states and rejecting states become accepting states the string is also rejected?

# Answer
> 3 votes
It depends on whether the NFA contains a path for every possible word.

If there is an input word where there is no path through the NFA at all labelled with that word, then yes, this can happen. See Hendrik Jan's answer.

On the other hand, it is often assumed that the automaton is complete: that for every possible input word, there is at least one path in the automaton labelled with that word. (For instance, this can be arranged by ensuring that for every state $q$ and every possible input letter $x \in \Sigma$, there is a transition out of $q$ labelled with $x$.) If you assume the automaton is complete, the answer is: No.

In particular, if the automaton is complete, the answer is: No, the magic of nondeterminism is that if there's any valid computation path that will end in an accept state, the string is accepted. In this case, all possible computation paths in the original NFA led to rejection (had there been any valid path the string would be accepted, so they must all reject), so in the inverted NFA, they all lead to acceptance.

# Answer
> 3 votes
Yes, there is such a situation. A string is rejected when there is no computation for that string at all. Obviously there will be no computation after swapping accepting states.

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


# Question
Title: Proving that it's decidable whether a TM ever moves on the blank input
I'm trying to understand how to prove a language is decidable, semi-decidable, co-semi-decidable, or none of the above.

I've got the problem: $$A\_{\mathrm{right}} = \\{ \left\< M\right\> | M \text{ never moves on blank input} \\}$$

and I have to prove what it is. I know that it is decidable, because if given an input where there is a blank, then it will enter a halt and will loop there forever and not move, thus it is rejected. Everything else can be accepted. I just don't know how to go about proving this with quantifiers.

Any help would be greatly appreciated.

# Answer
In order to understand what $M$ does on a blank input, one needs only examine its transition function $\delta$. As mentioned in the question, assume the starting state is $q\_0$, then there are two options: either $\delta(q\_0,\text{blank})$ moves the head (and then we can reject) or it doesn't move the head, which brings us to two other options: either it remains in state $q\_0$ (then we can accept, right?) or it moves to another state, say $q\_1$.

But, with $q\_1$ the same reasoning applies, and as Raphael suggested, we can't go on with this logic forever since the number of states is bounded by $|Q|$. So after $|Q|$ "steps" of the above reasoning we will have a conclusive answer to the question of whether the head moves or not, and we can accept or reject accordingly. Since we were successful at constructing a decider, this question (and hence the induced language $Aright$) is decidable.
> 1 votes

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


title: Arbitrary Programs that Halt

text:
# Question
Title: Arbitrary Programs that Halt
I've been learning about Theory of Computation lately, and i'm trying to link general programming with the Theory of Computation. I thought of considering any arbitrary program that halts, as an algorithm for solving some specific computational problem in the sense of Theory of Computation.

For some programs (like a calculator program, etc.), it is really easy to see them as an algorithm for solving some computational problems.

It seems to me, however, that some other programs are really not solving any computational problem.

Computational problems have instances, which can be see as the possible inputs to the algorithm that solves the problem (if the problem is computable), and for each instance there is an answer, which can be seen as the outputs to the algorithm.

But now, how could a Hello World program (prints the string "Hello World") be considered as the algorithm for solving some computational problem? What would be the computational problem, and its possible instances?

Other examples would be a program that solely does the job of establishing a connection to another computer over a network, and then proceeds to send messages to it, closing the connection in the end.

Is it really an algorithm to solve some computational problem?

So I'm thinking that programs (even considered the subset of those that halt) don't ALWAYS relate to Theory of Computation. In another words, there are some programs (mostly the ones that seems fixed procedures with no inputs) that don't represent the algorithm/solution for a problem, and hence can't be represented in a true Model of Computation like a Turing Machine.

Any opinions on the relation between programs that halt in general and Computation Theory?

# Answer
There are many issues in your question. I am no longer very expert in some of them, but let's try.

Basically, a standard program as you like it takes some input $I$, satisfying some property $P$, and does things with it so as to obtain an output $O$ satisfying some property $Q$ involving $I$ and $O$: $Q(I,O)$.

This program solves a problem corresponding to a constructive proof that $\forall I, P(I) \implies \exists O, Q(I,O)$. The problem is to find $O$ when given $I$. This may actually be read as a specification of the problem, of the program.

It is easy to apply this to a sorting program, for example.

This works nicely in functional programming.

But when you quit functional programming, things become harder to explain.

Typically, printing a string is a side effect, hence not functional.

If instead of printing you were considering just producing the string "Hello world", for whatever purpose, the you would have a functional program meeting a degenerate case of the above schema, because there is no input.

The problem reduces to: `produce the string "Hello world"` and corresponds to the specification $\exists O, O=\text{"Hello world"}$. The lack of input makes the universal quantifier unneeded.

But printing is something else, as is network reconfiguration. They are not directly functional operations.

Now, it is possible to simulate non-functional structures in a functional context by building appropriate domains of computation. But this often makes things a lot more complex. And the understanding I tried to give is no longer so obvious.

Dealing with these issues has been one of the main purposes of denotational semantics. Much of the research in language design is about bridging the gap between functional understanding and the requirements of non functional practices.
> 2 votes

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


title: Multi-qubit gates matrix representation

text:
# Question
Title: Multi-qubit gates matrix representation
Consider the gate used in Simon's Algorithm. It operates on a control register and target register, changing state like: $|\textbf{x}\rangle|\textbf{y}\rangle-\>|\textbf{x}\rangle|\textbf{y}\oplus f(x)\rangle$.

As I am working on an universal way to simulate operations on qubits, I've been using a matrix representation of gates, which allowed me to transform even pretty complicated states without much concern about transform's correctness. However, I can't really see how would I represent a gate like shown above with a matrix (or how would I build such a matrix knowing **x**, **y** and f(x)?)

How can such gates operating on multiple qubits be represented with matrices?

Alternatively, having a vector states representing x and y and knowing *f* how can I transform y? (If all qubits in x are set in equally-weighted superposition of 0 and 1, I guess I'd need to calculate f for all possible x states, but how should I apply the results to y then?)

# Answer
The first thing to recognize is that this is a permutation matrix where each row and column contains a single $1$ entry with the remaining entries being $0$. This follows from the fact that $x$ and $y$ represent classical bit strings and $f$ is a classical boolean function.

Let's take the basic case where $x$ is from the space of $n$ bit strings, $y$ is a single bit, and $\mathcal{f}$ maps $\\{0,1\\}^n$ to $\\{0,1\\}$. The operation then functions on $n+1$ bits and is represented by a $2^{n+1} \times 2^{n+1}$ matrix. If you let the binary number $xy$ index the matrix columns, then for column $xy$ set row $x(f(x) \oplus y)$ to 1 and all other rows to 0.

Let's look at an example from Deutsch's algorithm. Let $x$ be from $\\{0,1\\}$ and $f$ be bit negation, i.e. $f(0) = 1$ and $f(1) = 0$. From here we compute, for each row, the column number containing the 1.

$\begin{array}{cc} \mbox{column} & \mbox{row with 1} \\ 00 & 0(0 \oplus 1) = 01 \\ 01 & 0(1 \oplus 1) = 00 \\ 10 & 1(1 \oplus 1) = 10 \\ 11 & 1(1 \oplus 0) = 11 \end{array} $

This gives us the matrix

$ \left( \begin{array}{cc} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right) $

This generalizes to when $y$ is more than a single bit.
> 1 votes

# Answer
So basically, such gates operate on a joined register (which may be looked at as joined high-part (control) and low-part (target). Let's say that HL represents the state of such joined register (and H is the part of bits representing the control state's index before join, and L is the part representing target state's index). The matrix representation of such gate would have 1 in row **HL** and column **H(L xor f(H))** for every possible HL.
> 0 votes

---
Tags: quantum-computing
---


# Question
Title: Scalar by N component vector multiplication faster than O(N)?
Is there a way to multiply scalar by vector faster than just multiplying each element of the vector by that scalar?

It feels to me that there should be some exploit to do that. After all we will multiply two vectors elementwise in N steps. The original problem is simpler as it's only scalar by vector. Shouldn't we be able to use the sparsness in our advantage?

# Answer
> 2 votes
You seem to be focused on only one operand, the scalar. You can't get away from the fact that the other operand, the vector, contains $N$ elements and each of them need to be multiplied by the scalar. So, in general, there's nothing sparse about that. It just so happens that each of $N$ elements must get multiplied by the same number.

---
Tags: time-complexity, optimization, multiplication
---