title: Weighted closest-pair-of-points problem

text:
# Question
Title: Weighted closest-pair-of-points problem
I want to solve the following optimisation problem (an approximation or heuristic would be helpful as well).

I have two sets of points in the plane:
$P=\left\\{ p\_{1},p\_{2},\dots,p\_{N}\right\\} $ and $Q=\left\\{ q\_{1},q\_{2},\dots,q\_{M}\right\\} $.

Each point has a value/weight, i.e there is a function $v:P\cup Q\rightarrow\mathbb{R}$ which assigns a weight/value to each point.

I want to find a pair of points, one in $P$ and one in $Q$, which maximizes the function $f:P\times Q\rightarrow \mathbb{R} $,
$ f\left(p,q\right)=v\left(p\right)+v\left(q\right)-\alpha\cdot d\left(p,q\right) $

where $d$ is the Manhattan distance between the points. So on one hand I want points with a high value, on the other hand I want them to be close together. $\alpha$ is just a constant which I will determine according to the specific application and it assigns a "relative importance" of the distance relative to the weights.

The choice for Manhattan distance is because I want to use this with actual geographical points which are connected by actual road networks.

Does anyone have a suggestion how to solve this without an exhaustive search over all pairs? even an approximation or heuristic suggestion would be helpful.

Thank you!

# Answer
> 2 votes
## Suggested solution: use a k-d tree

I recommend you use a k-d tree to store the points of $Q$, with $k=3$ (3 dimensions). The three dimensions of each point are the $x$-coordinate, the $y$-coordinate, and the $v$-value (the value/weight of the point).

Store all of the points of $Q$ in a k-d tree. Then given a point $p$, you can use the structure of the $k$-d tree to find the point $q \in Q$ that maximizes $f(p,q)$ in a relatively efficient way -- more efficient than naively testing each possible point $q \in Q$. Then, you can iterate through the points of $P$, and for each point $p \in P$, use this procedure to find the point $q \in Q$ that maximizes $f(p,q)$. Keep track of the best pair you've seen, and this will solve your problem.

I guess I'd better describe how to use the k-d tree. Recall that each node in the k-d tree splits by a binary condition of the form $x \le c$ or $y \le c$ or $v \le c$, where $c$ is some constant (all points that satisfy the condition are stored in the left subtree of that node and all points that don't satisfy the condition are stored in the right subtree). Each point $q \in Q$ is stored somewhere in the tree. So, any node $s$ in the k-d tree corresponds to a subset $S\_s \subseteq Q$ of points from $Q$, namely, the points that appear somewhere in the subtree rooted at $s$. Due to the splitting criteria, each set $S\_s$ has the form $Q \cap R$ where $R$ is some axis-aligned 3-dimensional rectangle. For a particular node $s$, define

$$\begin{align\*} s.x\_\text{max} &= \max\\{q.x : q \in S\_s\\}\\ s.x\_\text{min} &= \min\\{q.x : q \in S\_s\\}\\ s.y\_\text{max} &= \max\\{q.y : q \in S\_s\\}\\ s.y\_\text{min} &= \min\\{q.y : q \in S\_s\\}\\ s.v\_\text{max} &= \max\\{v(q) : q \in S\_s\\}\\ s.v\_\text{min} &= \min\\{v(q) : q \in S\_s\\} \end{align\*}$$

As you form the k-d tree, precalculate the above 6 values for every node and store them in that node of the k-d tree, so they're available for ready lookup.

Define $R\_s = \[s.x\_\text{min},s.x\_\text{max}\] \times \[s.y\_\text{min},s.y\_\text{max}\] \times \[s.v\_\text{min},s.v\_\text{max}\]$. We can see that $S\_s = Q \cap R\_s$. It will be helpful to define

$$d(p,R\_s) = \min \\{d(p,r) : r \in R\_s\\}.$$

Note that you can efficiently calculate $d(p,R\_s)$, given the point $p$ and the 6 values associated with $s$. (Basically, this involves a case analysis through 27 cases, depending upon where $p$ is relative to $R\_s$. The running time to compute $d(p,R\_S)$ is $O(1)$.)

Let's fix a point $p$. I'm going to describe an algorithm to find the point $q \in Q$ that maximizes $f(p,q)$, by recursively searching the k-d tree for $Q$ in a suitable way. The idea is that we'll recursively visit the nodes of the k-d tree, but pruning the traversal when we reach a node that cannot possibly hold any point $q \in Q$ that will be better than the best seen so far.

To help us prune the traversal, notice that we can bound the maximum possible value of $f(p,q)$ over all $q \in S\_s$, as follows:

$$f(p,q) \le v(p) + s.v\_\text{max} - \alpha \cdot d(p,R\_s) \text{ for all } q \in S\_s.$$

Thus, whenever our recursive traversal reaches a node $s$ of the k-d tree, we'll use the above bound to figure out whether there is any possibility that exploring the subtree rooted at $s$ could possibly yield some improvement over the best result seen so far. If not, we'll prune the traversal and won't visit any of the children or descendants of $s$.

Thus, the algorithm looks something like the following:

```
def findbestpoint(p):
    bestsofar := -infinity
    visit(p, root of k-d tree for Q)
    return bestsofar

def visit(p, s):
    if v(p) + s.v_max - alpha * d(p,R_s) <= bestsofar:
        return
    update bestsofar based upon the point q stored in node s (if any)
    if s is a leaf:
        return
    visit(p, s.rightchild)
    visit(p, s.leftchild)

```

Given a k-d tree for $Q$ and a point $p \in P$, this algorithm computes $\max \\{f(p,q) : q \in Q\\}$. It will visit some of the nodes of the k-d tree but not all of them. So, iterate through the points $p \in P$ and call `findbestpoint()` on each one.

The above is correct but not necessarily optimal in performance. As an optimization, I suggest that at nodes that split on the $x$-coordinate or $y$-coordinate, you should choose the order of the recursive traversal to prefer the subtree that contains $p$; and for nodes that split on $v$-value, always prefer the subtree with the larger $v$-value. In other words, I suggest you replace the last two lines of `visit(p, s)` with

```
    if the condition associated with s is a split on the v-value:
        visit(p, s.rightchild)
        visit(p, s.leftchild)
    else if p satisfies the condition associated with s (i.e., p is contained within the subtree rooted at s.leftchild):
        visit(p, s.leftchild)
        visit(p, s.rightchild)
    else:
        visit(p, s.rightchild)
        visit(p, s.leftchild)

```

This will choose a traversal ordering that is more likely to help you prune many unpromising nodes.

As another optimization, rather than resetting `bestsofar` to $-\infty$ on each call to `findbestpoint`, I suggest you initialize it to $-\infty$ once and then don't reset it again. This will enable you to prune more effectively, and since you only want to find one pair $p,q$ that maximizes $f(p,q)$, this optimization is valid.

As yet another optimization, you can choose the order in which you iterate through the points of $P$ based on some heuristic. For instance, you could try sorting $P$ by value and iterating through $P$ in order of decreasing value; or you could use value minus $\alpha$ times the distance to the centroid of $Q$, or something like that. Basically, you want to first try values of $P$ that are more likely to yield you a large $f(\cdot,\cdot)$ value, as that will make the pruning more effective.

I have no theoretical guarantees on the asymptotic running time of this algorithm. However, when the set $Q$ is large, I expect this will give significant improvements. Once you understand how k-d trees, it should be relatively easy to code this up and give it a try.

Note that you can always choose whether to store $Q$ in the k-d tree and iterate through $P$ (as outlined above) or whether to store $P$ in the k-d tree and iterate through $Q$. I suggest you store the larger set in the k-d tree and iterate through the smaller set.

## A better algorithm using k-d trees

The idea above can be generalized further, to obtain an algorithm that might be even more efficient, at the cost of making the algorithm more complicated and more tedious to implement.

The algorithm above explores pairs $p,s$ where $p$ is a point and $s$ is a node in the tree (summarizing some subset of points from $Q$). In the refinement, we'll explore pairs $s,t$ where $s$ is a node in the k-d tree for $P$ and $t$ is a node in the k-d tree for $Q$ (so $s$ summarizes some subset of $P$ and $t$ summarizes some subset of $Q$). This will expose further opportunities for pruning.

Assume we have built a k-d tree for $P$ and a k-d tree for $Q$, augmented with the information listed above. For simplicity of exposition, assume we're using one of the variants of the k-d tree data structure where the points of $P,Q$ are stored in the leaves of the tree; the internal nodes don't store points. (You can generalize the ideas here to the case where each internal node also stores a point from $P$ or $Q$; the extension is messy but not conceptually difficult.)

Also, if $s$ is a node in the k-d tree for $P$ and $t$ is a node in the k-d tree for $Q$, define

$$d(R\_s,R\_t) = \min \\{d(r\_1,r\_2) : r\_1 \in R\_s, r\_2 \in R\_t\\}$$

to be the distance between the two rectangles $R\_s,R\_t$. This is the distance between the "closest point of approach" between the two rectangles. For example, if the two rectangles $R\_s,R\_t$ overlap, $d(R\_s,R\_t)=0$. This distance is a property solely of the rectangles $R\_s,R\_t$ and doesn't have anything to do with the points $p,q$ that are contained within them. Given the descriptions of $R\_s,R\_t$ (i.e., the 6 values stored in the nodes $s,t$), you can compute $d(R\_s,R\_t)$ in $O(1)$ time via an ugly but straightforward case analysis.

Now notice that

$$f(p,q) \le s.v\_\text{max} + t.v\_\text{max} - \alpha d(R\_r,R\_s)$$

for all $p \in R\_s, q \in R\_t$. This gives us an upper bound on the value of $f(p,q)$ over all class of possible pairs $p,q$ of points. Conceptually, the node $s$ summarizes a bunch of points $p$ (the set $S\_s \subseteq P$), and the node $t$ summarizes a bunch of points $q$ (the set $S\_t \subseteq Q$); the above bound lets us upper-bound the best possible $f(\cdot,cdot)$ value, among all pairs of points $p,q$ in these sets.

Based on this insight, we can get a recursive algorithm to find the best pair of points:

```
def findbestpair():
    bestsofar := -infinity
    visitpair(root of k-d tree for P, root of k-d tree for Q)
    return bestsofar

def visitpair(s, t):
    if s.v_max + t.v_max - alpha * d(R_s,R_t) <= bestsofar:
        return
    if s is a leaf and t is a leaf:
        let p := the point contained within s
        let q := the point contained within t
        if f(p,q) > bestsofar:
            bestsofar := f(p,q)
    else if s is a leaf:
        visit(s, t.rightchild)
        visit(s, t.leftchild)
    else if t is a leaf:
        visit(s.rightchild, t)
        visit(s.leftchild, t)
    else:
        visit(s.rightchild, t.rightchild)
        visit(s.leftchild, t.leftchild)
        visit(s.leftchild, t.rightchild)
        visit(s.leftchild, t.leftchild)

```

We can see that this explores pairs $s,t$ (corresponding to a set $S\_s \times S\_t$ of points), pruning when we can prove that none of the pairs $(p,q) \in S\_s \times S\_t$ will have a larger value of $f(p,q)$ than the best we've seen so far.

You can apply similar optimizations to those mentioned above (e.g., when $s$ is a leaf that splits on $x$-coordinate or $y$-coordinate, first try the child of t that $s$ is contained in; when $s$ is a leaf that splits on $v$-value, first try the child with the larger $v$-value; and symmetrically when $t$ is a leaf).

I would conjecture that if the size of the both sets is large enough, this might perform better than the solution mentioned above. However, I have no proof, and the only way to know for sure is to implement it and give it a try on your data set.

## A connection to computational geometry

I also noticed that your problem is related to the following classical problem:

* Given a set of discs in the 2-D plane, determine whether any pair of discs overlap.

and the following version of the problem:

* Given a set of discs in the 2-D plane, determine the pairs of discs that are closest (where the distance between two discs is given by the closest point of approach, i.e., the minimum distance between any point in the first disc and any point in the second disc).

These are classic problems in computational geometry which I think have sub-quadratic time algorithms (by sweepline methods or something, if I recall correctly). Unfortunately your problem seems harder those questions about discs, so I don't know whether those methods will transfer over.

Here is the connection. Define $w:P \cup Q \to \mathbb{R}$ by $w(p) = v(p)/\alpha$ and $w(q) = v(q)/\alpha$. Define $g:P \times Q \to \mathbb{R}$ by

$$g(p,q) = d(p,q) - w(p) - w(q).$$

Your problem is equivalent to asking for the pair of points $p \in P,q \in Q$ that minimizes $g(p,q)$, as $f(p,q) = - \alpha \cdot g(p,q)$.

Next, treat each point $p$ as being associated with a disc centered at $p$ and having radius $w(p)$; and similarly for each point $q$. In this way if all of the $w(\cdot)$ values are positive, we obtain a collection of discs in the two-dimensional plane. Notice that if two discs $p,q$ don't overlap, then $g(p,q)$ denotes exactly the distance between those two discs. This condition is equivalent to requiring that $g(p,q)$ be positive for all $p,q$.

In summary, if we were promised that $v(p)$ was positive for all $p,q$ and that the maximum value of $f(p,q)$ was negative, then your problem would be equivalent to finding the closest pair of discs in the 2-D plane.

Of course, in your problem, we're *not* promised any of those things. Therefore, your problem is harder. However, if you were really eager on trying to find the best possible algorithm, you could explore the literature to find algorithms for finding the closest pair of discs and see if any of them can be generalized to your setting.

---
Tags: algorithms, time-complexity, optimization, computational-geometry, search-problem
---


# Question
Title: Modelling using propositions, syntax and standards
One of the first programs I wrote when learning Java was a console application modelling the operation of an elevator. I'm trying to teach myself propositional logic and so I thought, why not use the same example?

So, suppose I have been given the task of modelling the main functions of an elevator system using propositions and predicates...

* Opening and closing doors (allowing entrance and exit at appropriate times)
* Storing and responding to floor requests from users
* Processing information from sensors (elevator load, floor position and speed sensors)
* Displaying status information on the displays (at each floor and in the cab)

My Google searches have returned very little in the way of useful insight into how this should be done or any standards that might exist. What would be the best way to do this?

Would something like this be appropriate?:

$$ F = requestedFloor, L = loadSensor(load), C = loadSensor(capacity) $$ $$ F ∧ L \< C → move(F) ∧ display: print(currentFloor) $$ $$ floorSensor(currentFloor) \< F → move(up)$$ $$ floorSensor(currentFloor) \> F → move(down)$$

Which is simple enough, right? If there is a floor requested and load is less than capacity then move to that floor. Also, print the floor to the display.

If anyone has any suggestions or can provide some examples of how I might model this I'd love to hear them.

# Answer
> 2 votes
Generally you have:

* Some boolean variables that collectively represent the current state, say $s,t,u$.
* Some boolean variables that collectively represents the inputs, say $i,j,k$. For instance, you might have one variable per sensor (assuming each sensor returns a boolean value).
* Some boolean variables that collectively represents the inputs, say $o,p,q$. For instance, you might have one variable per actuator (assuming each actuator can be either on or off).
* Some boolean variables that collectively represent the next state. You could give them a different name (e.g., $x,y,z$), but often, to help us remember the relationship to the variables for the current state, we used primed versions of the variables for the current state. So, the next state might be represented by $s',t',u'$.

Now, we introduce a predicate $\Psi(s,t,u,i,j,k,o,p,q,s',t',u')$ to represent the transition relation. The idea is that if this is true, it means the following: if you're in state $s,t,u$ and you receive inputs $i,j,k$, then you output $o,p,q$ AND transition to the state $s',t',u'$. You can use boolean logic to express the predicate $\Psi(s,t,u,i,j,k,o,p,q,s',t',u')$ as a boolean formula, using AND, NOT, OR, implication, etc.

Then you also need to describe the initial state of the system. For instance, it might be $(s,t,u)=(T,F,T)$.

As you can see, the notation can get a bit much. Often we collect all the variables associated with the current state into a vector $s$ of variables, $s=(s\_1,\dots,s\_k)$ where the state is $k$ bits (it is represented by $k$ boolean variables), and collect all of the variables associated with the input into a vector $i$ of variables, $i=(i\_1,\dots,i\_m)$; you similarly collect all the output variables into a vector $o=(o\_1,\dots)$; and the next state is given by a vector $s'=(s'\_1,\dots,s'\_k)$ represents the next state.

As a generalization, you can consider variables that have more than two possible values (they aren't restricted to be booleans). Booleans are convenient for digital logic implementation, but more general variables can enable a specification that is easier to think about and understand.

So, basically, yes, this is compatible with the kind of approach you were showing.

---
Tags: logic, software-verification, higher-order-logic
---


title: Gray Code Generation

text:
# Question
Title: Gray Code Generation
I am trying to generate a $n$-bit gray code where I can specify two strings $s$ and $t$ that must be consecutive in that gray code. I know that there are ways to generate specific codes (such has the Binary Reflected Gray Code and the Recursive Partition Gray Code), but I need to be able to construct one given any two strings as described above. Is there a way to do this? Or a result that guarantees that this is possible? I am almost certain it is, but haven't been able to find anything.

# Answer
Yes. It's always possible, if $s,t$ are at hamming distance one from each other. Let $s,t$ be your two strings at distance one from each other. Then there exists a Gray code sequence where they are adjacent in the Gray code sequence, say $s$ appears right before $t$. Now you immediately obtain a valid solution. Find where $t$ appears in the Gray code sequence, and start going through strings in the Gray code sequence until you get back to $s$. This will have the property you want, as a Gray code sequence is a cyclic sequence where every adjacent pair of strings has hamming distance one.

How do you find that Gray code sequence? There are many possible methods, but here's one easy one. Note that if you have a mapping $f$ on strings that permutes the order of the bits, and you apply $f$ to each element of a Gray code sequence, you obtain another Gray code sequence. The same is true for a mapping $g(x)=x\oplus c$ that xors the input with a constant string $c$. These two facts are enough. Start with any Gray code sequence of your choice; let its first two strings be $a,b$. Let $s,t$ be your two strings that have Hamming distance one. Now you can choose $f,g$ so that $g(f(a))=s$ and $g(f(b))=t$ (namely, choose $f$ to move the bit position where $s,t$ differ to the bit position where $a,b$ differ; and then choose $g(x)=f(a) \oplus s$). This choice of $f,g$ induces a new Gray code sequence: you start with your original Gray code sequence, and apply $f$ to each element of it, then apply $g$ to the result of it. The result is a new Gray code sequence whose first two elements are $s,t$. Thus, if you can iterate through the original Gray code sequence, you now have an easy way to iterate through the new Gray code sequence: you just start iterating at its 3rd element, skipping its first two elements (which will be $s,t$).

The requirement that $s,t$ have Hamming distance one is critical, as otherwise there is a trivial counterexample. Consider 2-bit strings. Suppose the two strings you already have are 00 and 11. Then you want to visit the two strings 01 and 10. However, it doesn't matter what order you visit them in: you won't obtain a solution of the form you want. In particular, there are only two possible sequences (01,10 or 10,01), and neither one has the hamming-distance-one property you wanted.
> 3 votes

---
Tags: graphs, data-structures
---


# Question
Title: Halting problem reducing to the blank tape halting problem
I was going through my book of proof and I find very confusing its definition, so I would like someone to help me in understanding this.

* The blank tape problem takes a machine and an empty tape and tells if this machine halts or not
* We prove it is unsolvable by proving it reduces to the halting problem

Whenever I read online, I read that we we write the input on the tape and we run this on the halting problem.

* How do we construct the reduction?
* Why do we write the input on the tape?
* Isn't this all about having an empty tape?

**update**: I think my misunderstanding is in the definitio of input and tape

# Answer
Short version first: The typical reduction for this problem assumes that we can decide the blank tape halting problem, but this gives us a way to decide the halting problem (which in this situation we already know is undecidable). It does so by taking the input to the normal halting problem, and making a *new* TM that always starts with a blank tape, and writes the normal halting problem input to the tape as its first set of steps - so if this modified machine halts when starting with an empty tape, the normal halting problem input halts with whatever its input. Therefore we can't decide the blank tape halting problem.

Now, with some formality.

We have two languages:

* $HALT\_{TM} = \\{\langle M,w\rangle \mid M \text{ is a Turing Machine that halts on input } w\\}$
* $BLANKHALT\_{TM} = \\{\langle M\rangle \mid M \text{ is a Turing Machine that halts on input } \varepsilon\\}$

> **Lemma.** $BLANKHALT\_{TM}$ is undecidable.

*Proof.*
We already know that $HALT\_{TM}$ is undecidable. We show that $BLANKHALT\_{TM}$ is also undecidable by reduction from $HALT\_{TM}$ (i.e. we show that if we could decide $BLANKHALT\_{TM}$, we could decide $HALT\_{TM}$).

Assume (for contradiction) that $BLANKHALT\_{TM}$ is decidable, and we therefore have a Turing Machine $T$ that decides it. Using $T$, we can construct a Turing Machine $R$ that decides $HALT\_{TM}$ where $R$ is:

* On input $\langle M, w\rangle$
    1. Construct a new Turing Machine $M\_{w}$ that does the following:
        + Starts with a blank tape (or rejects otherwise).
        + Write $w$ to its tape.
        + Moves its head back to the start, and from here just copies what $M$ does.
    2. Run $T(\langle M\_{w}\rangle)$, if $T$ accepts $\langle M\_{w}\rangle$, accept, otherwise reject.

But this would decide $HALT\_{TM}$, which we know is undecidable, so $T$ can't exist and $BLANKHALT\_{TM}$ is also undecidable. $\Box$

Again, note precisely what each machine is doing:

* $R$ decides $HALT\_{TM}$, with input $\langle M,w\rangle$.
* $T$ decides $BLANKHALT\_{TM}$ by assumption.
* $M\_{w}$ is basically a wrapper for the input $M$ given to $R$ that starts with a blank tape, but as its first actions writes the other input $w$ to its tape - so it starts with a blank tape, but it really does what $M$ does on input $w$.

Note that we "run" neither $M$ nor $M\_{w}$, we just construct their descriptions, and give those as input strings to $R$ and $T$ respectively.
> 9 votes

---
Tags: turing-machines, halting-problem
---


title: What is the case 2 in master theorem?

text:
# Question
Title: What is the case 2 in master theorem?
I am confused about the statement of the Master theorem in CLRS book.

Here is the link of the book CLRS.

In page 94, the theorem, in case 2, states that:

2. If $\displaystyle f(n)=\Theta(n^{\log\_ba})$, then $T(n) = \Theta(n^{\log\_ba}\lg n)$.

What if $T(n) = T(n/2) + \Theta(\lg n)$? We have $f(n)=\Theta(\lg n)\neq\Theta(1)$.

I found the slides of the CLRS book in MIT website here where the statement of the theorem looks different in case 2 (page 5).

If $\displaystyle f(n)=\Theta(n^{\log\_ba}\lg^k n)$, then $T(n) = \Theta(n^{\log\_ba}\lg^{k+1} n)$.

What am I missing here?

# Answer
> 5 votes
There are several different versions of the Master Theorem. This situation is common in mathematics: a well-known theorem may have several common versions, for example the Chernoff–Hoeffding bound(s). Perhaps one version is the original, and another is a widely known strengthening; or perhaps one version is the original, and another is the one appearing in textbooks, which is slightly weaker (since the proof of the complete theorem is too long or too difficult). Sometimes an apparently weaker version of the theorem is equivalent to the full theorem with a short proof (for example, Hilbert's Nullstellensatz).

As Raphael mentions in his comment, here you are encountering two common versions of the Master Theorem, one of which is stronger and can handle your case. If you were writing a paper, I would recommend citing a source which states (and preferably proves) the version of the theorem you use.

---
Tags: algorithms, master-theorem
---


# Question
Title: Halting Problem and Turing Degree and Reduction?
This is a Local Olympiad question on computation and computer science on 2013. How can explain it and says some hint for understanding such an example question.

> for $ A \subseteq \mathbb{N}$ we have $a=deg\_T(A)=\\{B | B \equiv\_T A \\} $ and $D=\\{deg\_T(A)| A \subseteq \mathbb{N} \\}$. For $(D, \leq)$ that has $A \leq\_T B$ iff $ a \leq b$. which of the following is false:
>
> 1) $(D, \leq)$ is a distributive lattice
>
> 2) $(D, \leq)$  is bounded (has minimum and maximum)
>
> 3) $(D, \leq)$ is a half disjunctive lattice. (may be I worded this statement poorly, sorry)
>
> 4) he maximum elements of $(D, \leq)$ is a degree of Halting Problem .

I think $deg\_T$ means Turing Degree and $\leq\_T$ means Turing Reduciblity.

Edit 1:

# Answer
> 5 votes
To complete LogicLove's answer, the solution for (1) can be found in a math.se question.

As there are pairs of degrees which have no greatest lower bound, the conditions for a distributive lattice can't be met.

# Answer
> 0 votes
(2) and (4) are false as explained by Yuval's Comment.

> The lattice of Turing degrees has a minimum (the recursive degree) but no maximum, since the jump of any degree (i.e., the corresponding halting problem) is larger than the degree.

(3) is true, because the Turing Degrees form an upper semi-lattice.

I have no idea for (1).

---
Tags: computability, turing-machines, computation-models, halting-problem, lattices
---


title: Average case lower bound for sorting

text:
# Question
Title: Average case lower bound for sorting
The $\Omega(n\lg{n})$ lower bound for sorting in the comparison model is well known. Is there a similar average case lower bound for sorting in the comparison model and if so, which random distributions does it apply to?

# Answer
In the Sedgewick-Bentley talk "QUICKSORT IS OPTIMAL" they give an (informal) proof that Quicksorts average case is optimal.

So the average case lower bound for sorting is $\Omega(n\lg{n})$.
> 2 votes

---
Tags: complexity-theory, sorting, lower-bounds
---


# Question
Title: Halting problem reduction to Halting for all inputs
I was going through my book of revision and I would like someone hints on this.

* The Halt for All Input problem (HAI) takes a machine and tell if this machine halts or not for any input
* We prove it is unsolvable by proving it reduces to the halting problem

The book says:

* Build a $M'$ that does the follwoing
* $M'$ erases its input (?)
* $M'$ writes I on its tape (did we not just erased this?)
* $M'$ simulates $M$

Can someone explain this reduction?

# Answer
There are a couple of points here. First, you're confusing the direction of the reduction: You're reducing HALT to HAI, not the other direction. Then, your book suggests the transformation $(\langle\\,M\\,\rangle, x)\rightarrow\langle\\,M'\\,\rangle$ where $\langle\\,M\\,\rangle$ is the description of a TM $M$, $x$ is a string, and $\langle\\,M'\\,\rangle$ is the description of a TM:

```
M'(y) =
   erase the input y
   write x on the tape  // second point: we're erasing and writing different strings
   simulate M on x

```

Now if $M$ halts on input $x$, then $M'$ will halt on every input $y$ and so will be an instance of HAI. Conversely, if $M$ fails to halt on $x$, then $M'$ will not halt on any input $y$ and so will not be in HAI.

From here, we can see that HAI is undecidable. If it were, then we could decide whether $M'$ would halt or not, and hence we'd be able to decide whether $M$ halted on $x$. In other words, we'd have a decider for HALT, which we know is impossible.
> 3 votes

---
Tags: turing-machines, halting-problem
---


# Question
Title: Subset Sum algorithm, why not split by 3+?
A classic algorithm for Subset Sum is to first split the input into two sets (A and B), evaluate the sums of the subsets of each, sort those sums for each A and B, then cleverly filter whole ranges of combinations by comparing the highest and lowest sums from each A and B.

Do we know (or does someone have an argument) why not to split the input into 3 or more sets rather than two?

I presume that there would be a combinatorial proof that doing so would either require the same or more number of steps.

# Answer
> 2 votes
First of all, let me mention that the algorithm you mention is attributed to Horowitz and Sahni (1974), whose algorithm achieves time $O(2^{n/2})$ and space $O(2^{n/2})$. A major improvement due to Schroeppel and Shamir (1981) reduces memory consumption to $O(2^{n/4})$ while keeping the same running time; this algorithm divides the input into *four* sets.

The topic is of interest to cryptographers, and there has been a recent line of improvements: Howgrave-Graham and Joux (2010), Becker, Coron and Joux (2011), Dinur, Dunkelman, Keller and Shamir (2012) and Austrin, Kaski, Koivisto and Määttä (2013), which seems to be the latest word on the subject; the authors of the last paper are actually not cryptographers.

---
Tags: combinatorics
---


# Question
Title: Is a stack machine with a forward read iterator Turing complete?
It is well known that a machine with a single stack as only unlimited storage is not Turing complete, if it can only read from the top of the stack. I want a machine which is (slightly) more powerful than a stack machine, but still not Turing complete. (I wonder whether there exists a non-Turing complete machine, which can deterministically simulate any non-deterministic pushdown automata with an only polynomial slow-down.) The most benign (straightforward) extension that came to my mind was a (single) forward read iterator.

Let me elaborate the implementation details, to make it clear what I mean by a forward read iterator. A singly linked list can be used for implementing a stack. Let the list be implemented by a pointer `pTop`, which is either zero, or points to an `SList` node. An `SList` node consists of a payload field `value` and a pointer field `pNext`, where `pNext` is either zero, or points to an `SList` node. Let the forward read iterator be implemented by a pointer `pRead`, which is either zero, or points to an `SList`node. The pointers `pTop` and `pRead` cannot be accessed directly, but can only be used via the following methods:

* `Push(val)` creates a new `SList` node `n` with `n.value = val` and `n.pNext = pTop`, and sets `pTop = &n`.
* `Pop()` aborts if `pTop == 0` or `pRead == pTop`. Otherwise it reads `val = pTop->value` and `pTopNext = pTop->pNext`, frees the `SList` node pointed to by `pTop`, sets `pTop = pTopNext` and returns `val`.
* `ReadBegin()` sets `pRead = pTop`.
* `ReadNext()` aborts if `pRead == 0`. Otherwise it reads `val = pRead->value`, sets `pRead = pRead->pNext` and returns `val`.
* `ReadFinished()` returns `true` if `pRead == 0`, and `false` otherwise.

# Answer
Your model is Turing-complete, unfortunately.

You can simulate a queue in your data structure using the following algorithm. It introduced 3 new stack symbols: $d, x, y$.

`Enqueue(val)` is just `Push(val)`.

For `Dequeue()`:

1. `ReadBegin()`.
2. Count the number of anything else - number of $d$ in the whole stack (which should be always non-negative). Push $y$ or pop $x$ for every $d$, and push $x$ or pop $y$ for anything else. Always prefer pop to push. Finally there won't be any $y$ in the stack and the result will be the number of $x$ on the top of the stack.
3. `ReadBegin()`.
4. While `pTop` is a $x$:
    1. Repeat `ReadNext()` until it returned something other than $x$ and $d$.
    2. `Pop()`.
5. Push a $d$.
6. The last result of `ReadNext()` is returned as the result of `Dequeue`.

The proof is straightforward. Check the revision history for a more complicated version firstly reducing it to a two-way version.
> 6 votes

# Answer
Your model is Turing complete (unlike what I previously thought), see user23013's answer a sketch of the proof (the essence is you can simulate a queue, and queue automata are Turing complete).

There are several ways to weaken you model to drop to equivalence with linear bound automata or lower.

Ginsburg, Greibach & Harrison \[1\] give a machine called a "Stack Automaton" which is a PDA with two additional capabilities:

1. The input head can move left an right (so it can scan previously seen parts of the input).
2. The read/write head on the stack can scan through the stack in read-only mode, but pushing and popping still only occur at the top. Note the key difference here with your model, which confused me earlier: the stack only has one head/pointer that it can move up and down the stack, whereas yours has two, which is enough to make your model Turing complete. They also give another model \[2\], where the input can only be read left-to-right, but the additional read-only stack scanning is still available.

In Figure 2 of \[1\] they give the containment (proved in Section 5 of the same, perhaps with some parts in \[2\]) and two-way nondeterministic stack automata languages are strictly contained in $\mathrm{R}$. However they are equivalent to nondeterministic linear bound automata, so they recognise context sensitive-languages.

Two-way and nondeterministic stack automata and two-way deterministic stack automata seem to be equivalent, however changing the input head to one-way makes a significant difference. The set of one-way nondeterministic stack automata languages is a strict subset of context-sensitive languages (I can't put my finger on exactly where yet), and the set of one-way deterministic stack automata (which are equivalent to your model) languages is a strict subset of the set of one-way nondeterministic stack automata languages.

A weaker type again, which falls below these are non-erasing stack automata, which can only write to the stack.

Hopcroft & Ullman show that the languages recognised by non-erasing deterministic stack automata corresponds to $\mathrm{DSPACE}(n\log n)$ and non-erasing nondeterministic stack automata corresponds to $\mathrm{DSPACE}(n^{2})$.

**Addendum**

After some more digging, these lecture slides suggest that one-way non-erasing deterministic stack automata are strictly weaker than the two-way version, so recognise something less than $\mathrm{DSPACE}(n\log n)$.

I also found further Hopcroft & Ullman \[4,5\] papers, which may provide a few more clues, but it seems to be tangential at this point. \[5\] at least proves some equivalences of some Stack Automata with LBAs.

**References**

1. Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison, "Stack Automata and Compiling". Journal of the ACM, 14(1):172–201, 1967.
2. Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison, "One-Way Stack Automata". Journal of the ACM, 14(2):389–418, 1967.
3. John E. Hopcroft, Jeffrey D. Ullman, "Nonerasing Stack Automata". JCSS, 1(2):166–186, 1967.
4. John E. Hopcroft, Jeffrey D. Ullman, "Deterministic Stack Automata and the Quotient Operator", JCSS, 2:1-12, 1968.
5. John E. Hopcroft, Jeffrey D. Ullman, "Two results on one-way stack automata", Symposium on Switching and Automata Theory (SWAT - but not that SWAT), 1967.
> 5 votes

---
Tags: computation-models, turing-completeness, linked-lists, stacks
---


# Question
Title: Does inserting and immediately removing a node change a red-black tree?
I have the following problem:

> Does inserting a node into a red-black tree and then immediately deleting it always result in the original tree? Prove that it does or give a counter-example if it does not. Does deleting a leaf node from a red-black tree, then reinserting the same node always result in the original tree? Prove that it does or give a counter-example if it does not.

I have used several demos, but none of them have made much sense to answer this question. I havent been sure as to yes or no, I am still new to binary trees.

# Answer
It's not obvious that there is a "correct" answer to this question, as there are multiple insertion/deletion algorithms for red-black trees. Tarjan explicitly explains this in his book *Data Structures and Network Algorithms*, where he demonstrates (in section 4.2) update algorithms that require $O(1)$ rotations and references algorithms that require $\Omega(\lg n)$ rotations.

This is also mentioned in Hize's "A Simple Implementation Technique for Priority Search Queues" and Driscoll et al.'s "Making Data Structures Persistent"
> 2 votes

# Answer
Deleting the same node immediately after inserting will not always result in the original tree. As a counterexample, you can try inserting 4,7,10,23,5 (in this order). Now insert 65 and delete it. The tree before inserting 65 will be different from the tree after deleting 65. The reason is basically that if any property is violated in a RB treen then it rearranges itself to restore the property which changes its structure.
> 0 votes

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


title: NFA not accepting a certain string

text:
# Question
Title: NFA not accepting a certain string
I am trying to make a non-deterministic NFA that does not contain a string "101".

How do I make my NFA so that it does not have this string?

My attempt:

# Answer
I'll give you a recipe for constructing automata for $\Sigma^\* \setminus F$ for any regular $F \subseteq \Sigma^\*$.

1. Construct a (complete) DFA $A\_F$ for $F$.
2. Construct the complement automaton $\overline{A\_F}$.
3. Optional: minimise.

The first step is particularly easy (if maybe time consuming) for finite $F$. The second one is standard (flip accepting and non-accepting states) and should be covered by any textbook on this subject.

Of course, step 1 may blow up the size of the automaton (going from an easy-to-design NFA to DFA); this can in particular be the case for finite sets. In your particular case, though, you never get more than five states.
> 0 votes

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


# Question
Title: NP-complete problems not "obviously" in NP
It occurred to many that in all the $\textbf{NP}$-completeness proofs I've read (that I can remember), it's always trivial to show that a problem is in $\textbf{NP}$, and showing that it is $\textbf{NP}$-hard is the... hard part. What $\textbf{NP}$-complete problems are these whose polynomial-time verifiers are highly non-trivial?

# Answer
> 19 votes
There are at least four such $NP$-complete problems listed in the appendix of Garey and Johnson's *COMPUTERS AND INTRACTABILITY: A Guide to the Theory of NP-Completeness*.

> **\[AN6\] NON-DIVISIBILITY OF A PRODUCT POLYNOMIAL**
>
> INSTANCE: Sequences $A\_i = \langle (a\_i\[1\],b\_i\[1\]), ..., (a\_i\[k\],b\_i\[k\]) \rangle,\ 1 \leqslant i \leqslant m,$ of pairs of integers, with each $b\_i\[j\] \geqslant 0,$ and an integer $N$.
>
> QUESTION: Is $\displaystyle \prod\_{i=1}^m \left( \displaystyle\sum\_{j=1}^k a\_i\[j\] \cdot z^{b\_i\[j\]} \right)$ *not* divisible by $z^N - 1$?
>
> *Reference:* \[Plaisted, 1977a\], \[Plaisted, 1977b\]. Transformation from 3SAT. Proof of membership in NP is non-trivial and appears in the second reference.

The other three I found in the appendix are:

* **\[LO13\] MODAL LOGIC S5-SATISFIABILITY**
* **\[LO19\] SECOND ORDER INSTANTIATION**
* **\[MS3\] NON-LIVENESS OF FREE CHOICE PETRI NETS**

# Answer
> 4 votes
Here is a problem from the database theory, more specifically, from the serializability theory.

In Serializability by Locking (Page 237), it says that

> Regarding the complexity of safety, Papadimitriou et al. \[14\] showed that it is $\textrm{NP}$-hard to test if a transaction system is not $SSR$-safe, and conjectured that the problem is $\textrm{NP}$. From Theorem 3 (In this paper), it follows that this is true.

The $SSR$-safe problem can be found in the paper "Some Computational Problems Related to Database Concurrency Control" by Papadimitriou et al. Unfortunately, I have no access to it.

# Answer
> 2 votes
For me, Integer Linear Programming (and the related Quantifier Free Presburger Arithmetic) are in this class.

A naive approach to an $n$-dimensional ILP problem is to iterate through all length $n$ vectors of integers. But this is an unbounded process.

You have to use some number theory to prove that there is a polynomial upper bound on the size of solutions, meaning that if a solution exists, there is always a polynomially-sized solution, which acts as a certificate.

More information can be found in the answer to a question I asked a while back.

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


title: Transforming NFA into DFA

text:
# Question
Title: Transforming NFA into DFA
In the examples I was given I have the following NFA diagram:

Then it gives the conversion process

Could someone explain to me the process of obtaining the second column:

{1,2,4} = a{1, 2, 3, 4}, b{1, 4, 5}

# Answer
> 1 votes
This is the standard procedure for converting NFAs to DFAs. The first row should be read as "If you know you're in one of the states $0$, $1$ and $4$ and you read an $a$, you'll have to be in one of the states $1$, $2$ and $4$; if you read a $b$, you'll have to be in one of $1$, $4$ and $5$." The other rows are similar.

# Answer
> 0 votes
You should do

$$\begin{align\*}\delta\_d(\\{1, 2, 4\\}, a) &= \delta(1, a) \cup \delta(2, a) \cup \delta(4, a)\\ &= \\{1, 2, 3, 4\\}\\\\[2ex\] \delta\_d(\\{1, 2, 4\\}, b) &= \delta(1, b) \cup \delta(2, b) \cup \delta(4, b)\\ &= \\{1, 4, 5\\} \end{align\*}$$

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


# Question
Title: Algorithm for fastest division below threshold
Take a number `i`. You need to split it in two pieces as many times as necessary so that all splits are less than or equal to `j`. How does one obtain this with the minimum number of splits? Examples:

Splitting it in half is optimal here:

```
i = 4, j = 2
4 -> 2, 2 // (1 split)

```

However, splitting in half is not optimal here:

```
i = 9, j = 3
9 -> 5, 4 // Split nine in half
5 -> 3, 2 // Then you have to split the 5
4 -> 2, 2 // and the 4 (3 splits)

```

The optimal solution here would be:

```
i = 9, j = 3
9 -> 6, 3
6 -> 3, 3 // (2 splits)

```

Is there some straightforward way to obtain the optimal split without brute-force iteration?

# Answer
The optimal strategy is the greedy one: repeatedly split chunks of size $j$. This strategy results in $\lceil \frac{i}{j} \rceil - 1$ splits. We can prove that this strategy is optimal by induction on $i$. The strategy is clearly optimal for $i \leq j$. Now suppose that we split $i \> j$ as $i = i\_1 + i\_2$. In total, this choice will use up at least this many splits: $$ 1 + \lceil \tfrac{i\_1}{j} \rceil - 1 + \lceil \tfrac{i\_2}{j} \rceil - 1 = \lceil \tfrac{i\_1}{j} \rceil + \lceil \tfrac{i\_2}{j} \rceil - 1. $$ Let $\alpha = i/j$, $\alpha\_1 = i\_1/j$, $\alpha\_2 = i\_2/j$, so that $\alpha = \alpha\_1 + \alpha\_2$. To complete the proof, notice that $\lceil \alpha\_1 \rceil + \lceil \alpha\_2 \rceil \geq \lceil \alpha \rceil$, and so the quantity above is always at least $\lceil \tfrac{i}{j} \rceil - 1$, as claimed.

I have described one optimal strategy. Using the proof above, we can actually describe *all* optimal strategies. Splitting $i$ to $i\_1+i\_2$ is optimal iff $\lceil \frac{i\_1}{j} \rceil + \lceil \frac{i\_2}{j} \rceil = \lceil \frac{i}{j} \rceil$. When does that happen? Define $$ i = aj-b, \quad i\_1 = a\_1j-b\_1, \quad i\_2 = a\_2j-b\_2, $$ where $0 \leq b,b\_1,b\_2 \< j$. A splitting is optimal iff $a\_1 + a\_2 = a$. Notice that $$ i\_2 + i\_2 = (a\_1+a\_2)j - b\_1 - b\_2. $$ This shows that the splitting is optimal iff $b\_1 + b\_2 = b$ (rather than $b + j$).
> 8 votes

# Answer
For a given $i,j$ you want the end result to be $\lceil i/j\rceil$ pieces of size $j$ and at most one piece of size $\<j$. No matter how you decide to do the splits, this separation will require at least $\lceil i/j\rceil-1$ splits. The simplest way to do this is to split $i$ into pieces of size $j$ and $i-j$. Then split the $i-j$ piece into pieces of size $j$ and $i-2j$. Rinse and repeat.
> 4 votes

# Answer
As others have noted, the optimal strategy is to repeatedly chop pieces of size $j$ off the number, until what's left is no greater than $j$. This will require $\lceil i/j \rceil - 1$ splits, and yield $\lceil i/j \rceil$ pieces.

An easy way to see that this method is optimal it to first note that, since each split turns one piece into two, and so increases the total number of pieces by one, the final number of pieces you're left with is always one plus the number of splits.

Next, observe that, if you have $k$ pieces of size at most $j$, their total size is obviously at most $jk$. Thus, if $k \< i/j$, then $jk \< i$, and so $k \< i/j$ pieces of size at most $j$ cannot possibly sum to $i$. Therefore, the smallest number of pieces that can sum to $i$ must be at least $i/j$, and the optimal number of splits must thus be at least $i/j - 1$.

Obviously, you cannot make just part of a split, so the number of splits must be an integer. The smallest integer greater than or equal to $i/j - 1$ is, by definition, $\lceil i/j - 1 \rceil = \lceil i/j \rceil - 1$.
> 4 votes

---
Tags: algorithms
---


# Question
Title: C program - Visually display Graph and checking for Hamiltonian Paths?
I have a very large graph in my c program with a list of nodes and edges. I want to print out the visual representation of this. What is the best way to go about this?

Additionally what's the best way to go about checking if said graph is hamiltonian and printing out a hamiltonian path? I can't find a decent algorithm.

# Answer
> 2 votes
Graphviz should do what you want.

http://www.graphviz.org/

You can you use it as program or as a library.

If you use as a program, then you just need to write a file of your graphs in the dot language and run graphviz on it.

Now, for the hamiltonian problem, you should know that this problem is NP-complete. Brute force is the most obvious solution. But you dont want that.

There is no general solution in polynomial time.

You could find a good solution for specific cases.

---
Tags: graphs, hamiltonian-path
---


# Question
Title: Reduce our problem to a known np-complete problem
Subgraph isomorphism

We have the graphs $G\_1=(V\_1,E\_1), G\_2=(V\_2,E\_2)$.

Question: Is the graph G\_1 isomorphic with a subgraph of $G\_2$ ?

(i.e. is there a subset of vertices of $G\_2, V \subseteq V\_2$ and subset of the edges of $G\_2 E \subseteq E\_2$ such that $|V|=|V\_1|$ and $|E|=|E\_1|$ and is there a one-to-one matching of the vertices of $G\_1$ at the subset of vertices $V$ of $G\_2 f:V\_1 \to V$ such that $\\{u,v\\} \in E\_1 \Leftrightarrow \\{ f(u),f(v) \\} \in E$)

In order to show that the problem is in NP, could we say the following?

A non-deterministic Turing machine can first "guess" which subgraph $G$ of $G\_2$ is isomorphic with $G\_1$ and then verify that $G$ is isomorphic with $G$ in $O(V\_1+E\_1)$ steps, since if we assume that the graphs are represented as adjacency lists, $G\_1$ will have $O(V\_1+E\_1)$ elements.

Or could I improve something?

I want to show that the problem is NP-complete, reducing the clique problem to it (Hint: assume that the graph $G\_1$ is complete)

Could you give me a hint how we could reduce the clique problem to our problem in order to show that the latter is NP-complete?

# Answer
The **hint** tells you pretty much everything:

Consider an arbitrary graph $G\_{2}$ on $n$ vertices. Also per the suggestion of the hint, let $G\_1$ be the complete graph on $k$ vertices, for some $k \le n$.

*Is $G\_{1}$ is isomorphic to a subgraph of $G\_{2}$?*

* If yes, what does that tell you about $G\_{2}$?
* How can you use that to solve the max-clique problem?
> 5 votes

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


# Question
Title: Why does my answer sheet say the set of computable functions is uncountable?
I'm trying to understand why I can't find room for the set of computable functions in the hotel of the Hilbert's Hotel Paradox.

I was thinking that, because Gödel numbering, I could consider the set of computable functions as numerable (and with cardinality equal to $\mathrm{card}(\mathbb N)$). However, I have an answer sheet that says otherwise, and makes a proof of that I'm pretty sure that is wrong. At least I don't trust it:

> Suppose that the computable functions set is enumerable, and $f\_n$ is a function of the set. Consider $g(n)=f\_n(n)+1$, its not in the set, therefore contradiction. Because that proof then the computable functions aren't countable, so they can't fit in the Hilbert Hotel.

# Answer
There are countably many computable functions. If $f\_n$ is a complete list of all (total) computable functions, then the function $g(n) = f\_n(n)+1$ cannot be any of the functions on the list, and so is not computable. This is one way to construct an uncomputable function.
> 0 votes

---
Tags: computability, enumeration
---


# Question
Title: Maximizing the minimum of $k$ submodular functions
Let $f(X)$ be a monotone submodular function from $2^{\\{1, \ldots, n\\}}$ to $\mathbb{N}$ and consider the problem of maximizing it subject to a cardinality constraint $|X| \leq m$. By using the greedy algorithm, it is possible to obtain a $1-1/e$ approximation (see, for example, these lecture notes).

But now suppose $f\_1(X), \ldots, f\_k(X)$ are monotone submodular functions and we want to maximize $\min(f\_1(X), \ldots, f\_k(X))$ subject to the same cardinality constraint. Is it still possible to obtain a constant factor approximation?

# Answer
> 3 votes
Krause, McMahan, Guestrin and Gupta, who call this problem *Robust Submodular Observation Selection* show that is is NP-hard to approximate this problem to within *any* constant.

---
Tags: algorithms, approximation
---


# Question
Title: Product of a Transition System and a Finite Automaton
Dealing with a question that asks me to compute the product of the following transition system and finite automaton.
Compute the product between the transition system *TS* and the finite-word automaton *A* depicted below.

Can't seem to find a good example on how to do this so I sort of just freestyled my answer. The best I found was in *Principles of Model Checking* but the book didn't really explain how the product was derived (it just provided a *TS*, *FA* and product), so I had to "guess" the logic.
Can anybody have a quick look at my solution and see if there are there any obvious mistakes I have made?

Also I can't figure out whether or not I should indicate any terminal states. I know that a *TS* doesn't have any terminal states, but an *FA* can - so what about the product?

# Answer
> 9 votes
In Section 4.2.2 of the book "Principles of Model Checking", there is a definition (Definition 4.16; Page 165) of "Product of Transition System and NFA". You are right about the states (i.e., $S \times Q$) of the product but make mistakes about its transition relation. Below I focus on the transition relation.

> **Definition 4.16** Product of Transition System $TS = (S, Act, \to, I, AP, L)$ and NFA $\mathcal{A} = (Q, \Sigma, \delta, Q\_0, F)$. The transition relation $\to'$ of their product is the smallest relation defined by the rule $$\frac{s \to^{\alpha} t \\; \land \\; q \to^{L(t)} p}{(s,q) \to'^{\alpha} (t,p)}$$

Intuitively, the transition system TS generates atomic propositions and feeds them into the automaton $\mathcal{A}$, driving the automata running. This semantics can be used to verify if the TS satisfies some property expressed by an automaton.

Additionally, the start states of the product is $$I' = \\{ (s\_0, q) \mid s\_0 \in I \land \exists q\_0 \in Q\_0. q\_0 \to^{L(s\_0)} q \\}.$$ That is, $q\_0$ in automaton has moved one step forward, driven by the atomic propositions in $s\_0$.

---

Based on the definition above, I calculate the product as follows (please check it):

---

* For what it concerns the terminal states, please refer to "Remark 4.17" (immediately following the Definition above) in the book.
* By the way, the labels for transitions (action denoted by $\alpha$ above) in $TS$ are often ignored (because they are irrelevant).

---
Tags: automata, finite-automata, model-checking
---


# Question
Title: Regular Expressions with at least 2 0's and at most 1
I think the answer should be:

$(1+ \epsilon)000^\* + 0^\*0(1+\epsilon)00^\* + 000^\*(1+\epsilon)$

But I am not sure if this is the right answer. Can someone explain the correct answer? And if it is correct how can I shorten this up?

Also what is the nfa for the regular expression: ∅\*

i have one more problem: i can't surely understand the meaning of Σ\* symbol. As far as I understand it should be (0+1)\* if Σ = (0, 1) and (a+b+c)\* if Σ = (a,b,c) and so on. Please someone clarify this.

# Answer
Your answer is correct. You can obtain a slightly shorter expression by deleting two of the $\epsilon$ in your expression. Indeed \begin{align} (1+ \epsilon)000^\* + 0^\*0(1+\epsilon)00^\* + 000^\*(1+\epsilon) &= (1+ \epsilon)000^\* + 0^\*0100^\* + 000^\*1 \\ &= 1000^\* + 0^\*0(1+\epsilon)00^\* + 000^\*1\\ &=1000^\* + 0^\*0100^\* + 000^\*(1+\epsilon) \end{align} Finally, if you want to avoid $\epsilon$, you could use one of the expressions $$ 000^\* + 1000^\* + 0^\*0100^\* + 000^\*1 \quad \text{or} \quad 0^\*(00 + 100 + 010 + 001)0^\* $$ which might be easier to read.
> 2 votes

---
Tags: regular-expressions, formal-methods
---


# Question
Title: Is generalized XOR-SAT efficiently solvable?
I've seen how XOR-3-SAT is efficiently solvable (for instance, see the "XOR-satisfiability" section in the Wikipedia entry for Boolean satisfiability problem).

I'm wondering a basic question: **Is XOR-k-SAT efficiently solvable, for formulas with varying amounts of literals per clause?**

I'd really like to know if we can increase the amounts of literals per clause beyond 3, and if we can have mixed clause lengths.

# Answer
> 15 votes
It looks like the Wikipedia article you linked to says that XORSAT (not just 3-XORSAT) is in P. The method by which they are solving that 3-XORSAT formula in their example very easily generalizes to formulas in which the clauses can have arbitrarily large numbers of variables and differing numbers of variables.

You just look at the formula as a system of linear equations where you have an equation for each clause, and a variable for each variable. For example, the formula:

$$(x\_1\oplus x\_2\oplus\lnot x\_3\oplus x\_5)\land (x\_2\oplus x\_3)$$

has a satisfying assignment if and only if the following system of equations has a solution:

$$x\_1+x\_2+(1+x\_3)+x\_5\equiv 1 \mod 2$$ $$x\_2+x\_3\equiv 1 \mod 2$$

And we can find solutions to linear systems of equations like these in polynomial time using Gaussian elimination!

# Answer
> 9 votes
Yes. It is solvable by Gaussian elimination. Gaussian elimination can solve any system of equations that is linear modulo. XOR acts as addition modulo 2, so each XOR-SAT clause acts as a linear equation modulo 2. Consequently, Gaussian elimination can solve any XOR-k-SAT formula or any XOR-SAT formula, even if there are a varying number of literals per clause or mixed clause lengths, in polynomial time.

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Prove that this language is not context-free
I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether $L=\\{0^{2^n}∣n \geq 0\\}$ is not context-free.

There is no pattern of 0's that can be recreated by a pushdown automata but alas I need to prove this. I know you start off assuming it is by being able to create a substring $uvxyz$ where $v$ and $y$ are raised to the $i$th power where $i≥0$. I'm having trouble from there, any help in this and the understanding would be greatly appreciated.

# Answer
A unary language (a language over a unary alphabet) is context-free if and only if it is regular. The easiest way to see this is to convert a context-free grammar to a regular grammar using the fact that $xy = yx$ over a unary alphabet.

There are many ways of showing that $L$ is not regular, and so not context-free. One way is using the Myhill–Nerode criterion. Since $0^{2^n} 0^{2^n} \in L$ while $0^{2^m} 0^{2^n} \notin L$ for $m \neq n$, we see that the words $\\{ 0^{2^n} : n \geq 0 \\}$ are pairwise inequivalent, and so $L$ is not regular.

A proof using the pumping lemma is also not too difficult. Given a pumping length $n$, choose $m$ so that $2^{m-1} \> n$, and consider the word $0^{2^m} \in L$. According to the pumping lemma you can write $0^{2^m} = xyz$ with $|xy| \leq n \< 2^{m-1}$ and $|y| \geq 1$ so that $xz \in L$. But $xz = 0^{2^m-|y|}$ cannot be in $L$ since $2^{m-1} \< 2^m-|y| \< 2^m$. This contradiction shows that $L$ is not regular.
> 0 votes

---
Tags: complexity-theory, context-free, automata
---


# Question
Title: What is the relation between NC and P/poly?
I am unable to see a clear explanation of how the classes NC and P/poly intersect or not. (and if they do intersect then how and where? and if not then what is the proof?)

# Answer
If you define NC as the class of problems computable using polynomial size, polylogarithmic depth circuits, then NC$\subseteq$P/poly, since P/poly is the class of problems computable using polynomial size circuits (without restrictions on the depth). Sometimes we also require the circuits to be uniform, and then we get the stronger conclusion uniform-NC$\subseteq$P. In both cases it is conjectured that the containments are strict.

In fact, since P-complete problems are complete with respect to very weak reductions, uniform-NC$\subsetneq$P if and only if a P-complete problem is not in NC. Wikipedia has a list of many P-complete problems.
> 8 votes

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


# Question
Title: What sorting algorithm should be used for this array?
I am given an array `{1, 2, 3, 5, 4, 6}` and I am asked

> What sorting algorithm might you want to use to sort the given list, and why?

Initially I think using Bubble sort would be the best option due to it's *best case* linear ($O(n)$) complexity and due to the fact that you'd only need to use 1 swap. However, the more I look at the problem I am starting to think that Insertion Sort may also be efficient in this situation.

Insertion sort and Bubble sort both have the same best, average, and worst case time complexities as well as the same space complexities. Are neither one of these algorithms the proper one to be used on this array? If not, why not?

# Answer
An *inversion* in a permutation $\pi(1),\ldots,\pi(n)$ is a pair of indices $i \< j$ such that $\pi(j) \< \pi(i)$. Denote the number of inversions by $I(\pi)$. In your example, $I(123546) = 1$. It is well-known that insertion sort runs in time $O(I + n)$ on a permutation of length $n$ having $I$ inversions. Due to this guarantee, insertion sort is asymptotically optimal when the number of inversions is small, $I = O(n)$.
> 5 votes

---
Tags: algorithms, sorting, efficiency
---


# Question
Title: What determines the "speed" of a programming language?
Suppose a program was written in two distinct languages, let them be language X and language Y, if their compilers generate the same byte code, why I should use language X instead of the language Y? What defines that one language is faster than other?

I ask this because often you see people say things like: "C is the fastest language, ATS is a language fast as C". I was seeking to understand the definition of "fast" for programming languages.

# Answer
There are many reasons that may be considered for choosing a language X over a language Y. Program readability, ease of programming, portability to many platforms, existence of good programming environments can be such reasons. However, I shall consider only the speed of execution as requested in the question. The question does not seem to consider, for example, the speed of development.

Two languages can compile to the same bytecode, but it does not mean that the same code will be produced,

Actually bytecode is only code for a specific virtual machine. It does have engineering advantages, but does not introduce fundamental differences with compiling directly for a specific harware. So you might as well consider comparing two languages compiled for direct execution on the same machine.

This said, the issue of relative speed of languages is an old one, dating back to the first compilers.

For many years, in those early times, professional considered that hand written code was faster than compiled code. In other words, machine language was considered faster than high level languages such as Cobol or Fortran. And it was, both faster and usually smaller. High level languages still developed because they were much easier to use for many people who were not computer scientists. The cost of using high level languages even had a name: the expansion ratio, which could concern the size of the generated code (a very important issue in those times) or the number of instructions actually executed. The concept was mainly experimental, but the ratio was greater than 1 at first, as compilers did a fairly simple minded job by today standards.

Thus machine language was faster than say, Fortran.

Of course, that changed over the years, as compilers became more sophisticated, to the point that programming in assembly language is now very rare. For most applications, assembly language programs compete poorly with code generated by optimizing compilers.

This shows that one major issue is the quality of the compilers available for the language considered, their ability to analyse the source code, and to optimize it accordingly.

This ability may depend to some extend on the features of the language to emphasize the structural and mathematical properties of the source in order to make the work easier for the compiler. For example, a language could allow the inclusion of statements about the algebraic properties of user defined functions, so as to allows the compiler to use these properties for optimization purposes.

The compiling process may be easier, hence producing better code, when the programming paradigm of the language is closer to the features of the machines that will intepret the code, whether real or virtual machine.

Another point is whether the paradigms implemented in the language are closed to the type of problem being programmed. It is to be expected that a programming language specialized for specific programming paradigms will compile very efficiently features related to that paradigm. Hence the choice of a programming language may depend, for clarity and for speed, of the choice of a programming language adapted to the kind of problem being programmed.

The popularity of C for system programming is probably due to the fact that C is close to the machine architecture, and that system programming is directly related to that architecture too.

Some other problem will be more easily programmed, with faster execution using logic programming and constraint resolution languages.

Complex reactive systems can be very efficiently programmed with specialized synchronous programming languages like Esterel which embodies very specialized knowledge about such systems and generate very fast code.

Or to take an extreme example, some languages are highly specialized, such as syntax description languages used to program parsers. A parser generator is nothing but a compiler for such languages. Of course, it is not Turing complete, but these compilers are extremely good for their specialty: producing efficient parsing programs. The domain of knowledge being restricted, the optimization techniques can be very specialized and tuned very finely. These parser generators are usually much better than what could be obtained by writing code in another language. There are many highly specialized languages with compilers that produce excellent and fast code for a restricted class of problems.

Hence, when writing a large system, it may be advisable not to rely on a single language, but to choose the best language for different components of the system. This, of course, raises problems of compatibility.

Another point that matters often is simply the existence of efficient libraries for the topics being programmed.

Finally, speed is not the only criterion and may be in conflict with other criteria such as code safety (for exemple with respect to bad input, or resilience to system errors), memory use, ease of programming (though paradigm compatibility may actually help that), object code size, program maintainability, etc.

Speed is not always the most important parameter. Also it may take different guises, like complexity which may be average complexity or worse case complexity. Also, in a large system as in a smaller program, there are parts where speed is critical, and others where it matters little. And it s not always easy to determine that in advance.
> 27 votes

# Answer
While everything is eventually run on the CPU*, there are various differences between different languages. Here are some examples.

**Interpreted languages** Some languages are *interpreted* rather than *compiled*, for example Python, Ruby and Matlab. That means that Python and Ruby code doesn't compile to machine code, but rather is interpreted on-the-fly. It is possible to compile Python and Ruby to a virtual machine (see next point). See also this question. Interpreted is generally slower than compiled code for various reasons. Not only can interpretation itself be slow, it is also harder to do optimizations. However, if your code spends most of the time on library functions (the case of Matlab), performance won't suffer.

**Virtual machine** Some languages are compiled into *bytecode*, an invented "machine code" which is then interpreted. The quintessential examples are Java and C#. While bytecode can be converted to machine code on the fly, the code will probably still run slower. In the case of Java, a virtual machine is used for portability. In the case of C#, there might be other concerns such as security.

**Overhead** Some languages trade efficiency for security. For example, some versions of Pascal would check that you don't access an array out of bounds. C# code is "managed", and this has a cost. Another common example is garbage collection, which saves time for the programmer but is not as efficient as hands on memory management. There are other sources of overhead such as infrastructure for exception handling or for supporting object oriented programming.

* In fact, nowadays high performance systems also run code on GPUs and even on FPGAs.
> 16 votes

# Answer
There are different factors for choosing X instead of Y, like

* Ease of learning
* Ease of understanding
* Speed of development
* Help with enforcement of correct code
* Performance of compiled code
* Supported platform environments
* Portability
* Fit-for-purpose

Some languages are suitable for developing business projects like C# or Python, but on other hand some of them are good for system programming like C++.

You must determine under what platform you are going to work and what application you are going to create.
> 5 votes

# Answer
The "fastest" programming language you can get with any platform is the assembly language for the chipset you are dealing with. At that level there is no translations. However there needs to have some knowledge of how the chipset executes instructions especially those that can do things in parallel.

The conversion from C to assembly is very "shallow" that it is near one to one but it is more readable. However it has a lot of layers above it due to the standard libraries to improve portability. There are not as many things that the compiler would need to do to get to assembly code and the stronger optimizations are generally there to make machine specific changes.

C++ adds a richer language. However because the language adds so much complexity it gets harder for the compiler to create optimal code for the platform.

Then we go to the other side of the scale. Interpreted languages. These tend to be the slowest because in addition to doing the work there is some time spent to parse the code and convert it to machine calls.

Then we have those in between. Generally they have a virtual machine layer which are optimized for the platform. And the compiler will create code for the virtual machine to execute. Sometimes this happens all at once like perl or pascal or ruby or Python. Or in several stages like java.

Some of these virtual machines add the notion of a JIT compiler which speeds up the runtime as well by creating machine level code rather than translating intermediate byte code.

Some virtual machines are low level which allow for less translation from byte code to machine code. Which speed things up while keeping portability.
> 2 votes

# Answer
A point which has not yet been mentioned is that in some languages, running the same piece of code many times will always perform the same sequence of actions; the computer thus only needs to determine once what the section of code should do. One of the major benefits of the "use strict" dialect of JavaScript is that it once the JavaScript engine figures out what a piece of code does, it can make use of that information the next time it is run; without "use strict", it can't.

For example, in the absence of "use strict", a piece of code like:

```
function f() { return x; }

```

may return a variable X in the immediate calling context, if there is one, or a variable X from an outer calling context, or it may return `Undefined`. Worse, in a loop like:

```
for (i=0; i<40; i+=1) { g(i); }

```

there is no way for the JavaScript engine to know what `g()` might do with `i` \[or to `g` itself for that matter. Since `g` or `i` could quite legitimately change `i` into a string, the JavaScript engine can't simply use a numeric addition and numeric comparison in the loop, but must on each pass through the loop check to see if either of the function calls have done anything to `i` or `g`. By contrast, in the "use strict" \[somewhat-sane\] dialect the JavaScipt engine can examine the above code and know that every pass through the loop will use the same numeric variable and invoke the same function. It will thus only need to identify `i` and function `g` once, rather than having to look them up on every pass through the loop--a major time savings.
> 2 votes

# Answer
Well there are some quite professional answers here, this one is no close to them but might be intuitive for you.

You might have heard many times that when you need to perform a task as quickly as possible you would want to write the code that executes it in assembly. That's because you execute only commands that you actually need for completing the task and nothing more. While on a high level language you could implement this task in several lines, the compiler still needs to translate them to machine language. This translation is not always minimalistic as you could write it directly. That means that the machine will spend many clocks on executing commands which you could spare.

Although compilers are very sophisticated today they are still not effective as best assembly programmers can be.

Continuing in this direction, those unneeded commands grow in their amount (usually) as the language is higher leveled. (this is not 100% true for all high level languages)

So to me, language X is faster than language Y (on runtime) if for certain piece of code, the machine code of X is shorter than Y's.
> 2 votes

# Answer
It is difficult to answer this question definitively because it is so complex and multidimensional (it's almost like e.g. comparing car brands over misc. criteria) but there are new scientific studies including of an excellent code repository known as Rosetta code, (wikipedia overview). This 2014 survey by Nanz and Furia studies this question quite definitively and scientifically based on the following typical criteria and a rare quantitative analysis of typically subjective code qualities. The abstract contains some objectively-grounded findings and generalizations. (Hopefully other studies building on these results can be done in the future.)

* RQ1. Which programming languages make for more concise code?
* RQ2. Which programming languages compile into smaller executables?
* RQ3. Which programming languages have better running-time performance?
* RQ4. Which programming languages use memory more efficiently?
* RQ5. Which programming languages are less failure prone?

> Abstract—Sometimes debates on programming languages are more religious than scientific. Questions about which language is more succinct or efficient, or makes developers more productive are discussed with fervor, and their answers are too often based on anecdotes and unsubstantiated beliefs. In this study, we use the largely untapped research potential of Rosetta Code, a code repository of solutions to common programming tasks in various languages, which offers a large data set for analysis. Our study is based on 7,087 solution programs corresponding to 745 tasks in 8 widely used languages representing the major programming paradigms (procedural: C and Go; object-oriented: C# and Java; functional: F# and Haskell; scripting: Python and Ruby). Our statistical analysis reveals, most notably, that: functional and scripting languages are more concise than procedural and object- oriented languages; C is hard to beat when it comes to raw speed on large inputs, but performance differences over inputs of moderate size are less pronounced and allow even interpreted languages to be competitive; compiled strongly-typed languages, where more defects can be caught at compile time, are less prone to runtime failures than interpreted or weakly-typed languages. We discuss implications of these results for developers, language designers, and educators.
> 1 votes

# Answer
Computer languages are just an abstraction of commands to explain the computer what to do.

You can even write in the computer language `Python` and compile it with an C compiler (cython).

**Keeping this in mind the speed of computer languages can not be compared.**

But you can compare compilers for the same language up to some extend. For example `GNU C` compiler versus `Intel C` compiler. (Search for compiler benchmark)
> 0 votes

---
Tags: programming-languages, compilers
---


# Question
Title: Partitioning planar graph cycles based on chords
Given a cycle of length \> 3 in a planar graph, I'm looking to partition it into 4 sublists of length 2 or more such that:

1. No sublist contains two vertices with a chord between them
2. The last element in each sublist is the first element in the next
3. Every element in each sublist is adjacent to its neighbors in the original cycle
4. The difference in size between the sublists is kept minimal, given constraints 1 to 3

Overall I'm not really sure if this is required to be solved using graph structures, or if it's possible to transform it into something more general.

# Answer
If the original cycle has length $n$, there is a straightforward $O(n^5)$ time algorithm: simply guess which vertex each sublist should start at.

In other words, let the original cycle go through the vertices $v\_1,v\_2,\dots,v\_n,v\_1$. Then you can choose indices $i,j,k,l$ (such that $1 \le i \< j \< k \< l \le n$), where the first sublist contains $v\_i,v\_{i+1},\dots,v\_j$, the second sublist contains $v\_j,v\_{j+1},\dots,v\_k$, and so on (assuming index arithmetic wraps around modulo $n$). There are only ${n \choose 4} \in O(n^4)$ possible choices for $i,j,k,l$, so you can exhaustively try them all and test each one to see whether it meets all your requirements, and then keep whichever one is best (according to your "difference-in-size" metric).

This proves that the problem can be solved in polynomial time.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: How to explain a language with modulo conditions is regular?
I don't want to create a duplicate question of How to prove a language is regular?, I only want to know what is a good and simple way to explain why a language like

$\qquad \displaystyle L = \\{w \in \\{a,b,c\\}^\* \mid w = ua \text{ and } |u| \equiv 2 \pmod 3 \\}$.

is regular.

# Answer
> 1 votes
The easiest way is by giving a regular expression for $L$: $$ L = (a+b+c)^2((a+b+c)^3)^\*a. $$ Here $(a+b+c)^2$ is a shorthand for $(a+b+c)(a+b+c)$, and $(a+b+c)^3$ is a shorthand for $(a+b+c)(a+b+c)(a+b+c)$.

Other ways described in the comments:

1. Give a DFA (6 states) or an NFA (4 states) for $L$.
2. Decompose $L = L' a$ and give a DFA (3 states) or an NFA (3 states) for $L'$.

---
Tags: regular-languages
---


# Question
Title: Calculating the Transfer Time for a Hard Disk
I know that transfer rate is data size over transfer speed - but according to the information given, I don't know what the data size is to calculate the transfer rate. Am I missing something or was I really not given it?

The information given is as follows:

> A number of files are stored on a 10000RPM hard disk. The platters rotate clockwise. The heads move at the speed of 250 centimeters per second. The controller overhead of the hard disk is 0.2 milliseconds per I/O request. The data transfer speed is 100 MB/s. Assume one I/O request is sent for every file. The average seeking distance is 1 centimeter. Since a sector is very small, ignore the time to rotate it through under the head. Calculate the average time to fetch data for each of the scenarios below.
>
> a. 1 file of 10 sectors is fetched. The sectors are randomly distributed on the disk.

I know I need the transfer rate to calculate fetch time - but again - I don't know the data size so I don't know how to calculate it.

# Answer
Sectors are usually 512B to 4KB. In your case, it seems that the actual time it takes to read the sectors is negligible compared to seeking (verify this!), and this could be what is meant by the following line:

> Since a sector is very small, ignore the time to rotate it through under the head.

To be sure, make the calculation with respect to the largest sector size (4KB), and check that the data transfer time is negligible. If it isn't, you are indeed missing a data point.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: If A is decidable and B is decidable, then A is Turing Reducible to B
The statement seems intuitively true but is it? If so, how can I prove this?

# Answer
One way of defining a Turing reduction (from $A$ to $B$) is as an algorithm that can decide $A$ if we have an oracle to decide $B$. The trick to notice here is that there is nothing that says you have to actually *use* the oracle.

So given that $A$ is decidable, we can take the Turing machine that decides it, augment it with an oracle for $B$, but completely ignore the oracle and just run the TM as normal.
> 2 votes

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


title: Simplifying a nested sum

text:
# Question
Title: Simplifying a nested sum
I'm trying to analyze an algorithm of a function, I can express the function in term of summation, but I have no clues on how I could simplify this summation down to get the run-time in tern of big $O$ or $\Theta$. I have this pseudo-code below:

```
f(n)
    for int i = 1 to n
        for int j = i to n
           doThis(n - j)
        end
    end
end

```

Assuming that `doThis(k)` takes $c \cdot k$ operations for some constant $c \> 0$. I can express the nested for loop in summation as follow:

$\sum\_{i=1}^n \sum\_{j=i}^n c\cdot(n-j)$

How does one simplify this summation? It has been a while since I touch math so I'm trying to get an idea here. Any help would be appreciated, thank you!

# Answer
> 2 votes
Hint: $$\sum\_{i=1}^n \sum\_{j=i}^n (n-j) = \sum\_{i=1}^n \sum\_{j=0}^{n-i} j. $$ At this point, you can either use exact formulas, or notice that for all $d \geq 0$, $$\sum\_{k=1}^m k^d = \Theta(k^{d+1}).$$ (If you don't know what a $\Theta(\cdot)$ bound is, suffice it to say that it is a "tight" $O(\cdot)$ bound.)

After you handle the inner sum, you will need to use the same trick of replacing $i$ with $n-i$ in order to handle the outer sum.

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


# Question
Title: Linear and almost-linear perfect hashing
I am trying to understand the sentence from a paper by Patrascu:

> Unfortunately, we do not have linear perfect hashing. Instead, we use a family of hash functions.... with almost-linearity

The context is a reduction between two variants of the 3-SUM problem:

* In the usual variant, 3SUM, given an array $A$ we have to find 3 indices $i,j,k$ such that: $A\[i\]+A\[j\]=A\[k\]$.
* In the other variant, Conv3SUM, we have to find 2 indices $i,j$ such that: $A\[i\]+A\[j\]=A\[i+j\]$.

Theoretically, we could reduce 3SUM to Conv3SUM if we had a linear hash function - a function $h$ such that: $h(x+y)=h(x)+h(y)$, and that maps all elements of $A$ to the range of indices $\\{0,...,n-1\\}$

The reduction is by sending every element of $A$ to an index determined by $h$, i.e. create an array $B$ such that for every $x\in A$: $B\[h(x)\]=x$

Then, if there is a solution to 3SUM on A, $x+y=z$, then on B we will have: $B\[h(x)\]+B\[h(y)\]=B\[h(z)\]$, and by the linearity of $h$ also $h(x)+h(y)=h(z)$, so this is a solution to Conv3SUM on B.

Conversely, every solution to Conv3SUM on B is trivially a solution to 3SUM on A, since every element of B is also an element of A.

Unfortunately, we do not have linear perfect hashing, so we have to use a family of almost-linear hash functions.

MY QUESTION IS: why do we have perfect almost-linear hash functions and not perfect linear hash functions? How does almost-linearity make it easier to find perfect hash functions?

# Answer
I think there is a constraint that the domain of the hashing function must be {0...n-1}, where n means the number of elements to hash. Only defining in this way , the reduction from 3SUM to Conv3SUM works.

The is an almost-linearity function in wiki. And it is easy to figure out a counter example for the existence of perfect linear hashing function.

Consider the following questions:

Let A = {1,2,3,4}, B={0,1,2,3}

1. how many triples (x,y,z) satisfy x+y=z, where x,y,z are in A and **distinct**
2. what if x,y,z are in B

The answer of the first question is

1. 1+1=2
2. 1+2=3
3. 1+3=4
4. 2+2=4

But there are only two triples in the second question. You can find out a bijective function, satisfying that linearity property, mapping A onto B .
> 1 votes

---
Tags: reductions, hash
---


# Question
Title: minimum spanning tree and minimum heavyweight spanning tree
a minimum heavyweight spanning tree is a spanning tree in which the heaviest edge is as light as possible. Formally, input : given connected undirected weighted graph, $G$. output : a spanning tree $T$ for $G$ with property that every spanning tree $T'$ for $G$ has some edge $e'$ such that $w(e')\ge w(e)$ for every edge $e$ in $T$.

1. provide a greedy algorithm to solved the problem.
2. is every minimum heavyweight spanning tree a minimum spanning tree ?

first thing comes into my mind was using Kruskal's algorithm with $O(|E| \log |V|)$ running time. If I use kruskal's algorithm for 1, the output will guarantee to be a MST, thus 2 will be true? Can someone verify this for me, thanks in advance

# Answer
> 0 votes
Hints:

1. Scaling.
2. Almost every graph would answer this.

# Answer
> 0 votes
**1-** Kruskal's algorithm can answer the first question (because it's counted as a greedy algorithm ).
**2-** For the second question i have be thinking like this : let's assume we have graph $G(V,E)$ and let's sort $E$ by Weight in non decreasing order to obtain $E=\\{e\_{0} ...e\_{n}\\}$(and we are assuming that the weight values are distinct for simplicity)
Then for us to have a minimum heavyweight spanning tree $T(V,E')$ we must select the the edges in a way that the max edge (edge with maximum weight) in $T$ must be equal to $e\_{v-1}$ in the sorted list $E$ which is at index $v-1$ in $E$ thus the edges must look like $E'=\\{e\_{0}...e\_{v-1}\\}$
...Now let's assume that we have a minimum spanning tree $T' \neq T$ with lower cost than $T$ then it must have at least one edge $e'\_j$ with lower weight than any of $E'$ which makes the sorted list $E'$ not having the lowest $V-1$ weighted edge in $E$ which leads us to constructing a tree $T''$ which don't have any $e′$ such that $w(e′)≥w(e)$ for every edge $e$ in $T$
... Thus $T$ is not a minimum heavyweight spanning tree ... this states that $T = T'$ must behold and every minimum heavyweight spanning tree must be a minimum heavyweight spanning.
**NOTE** : this is my way of thinking for a solution to the question , it might not be the right answer !

---
Tags: algorithms, graphs, greedy-algorithms, spanning-trees
---


# Question
Title: How do I manage flow control with no ELSE statement? (on Turing machine)
I have been given the problem of writing a turing machine with the commands:

```
if, while, whileNot, read X, write X, goLeft, goRight, HALT

```

The problem was simply "calculate a two's complement number, from number with \\$ on the left and # on the right, ex: $10110100#"

I started by writing this pseudocode to flip the bits:

```
whileNot read #
    if read 1
        write 0
    if read 0
        write 1
    goRight

```

But then I realized once 'write 0' executes, 'if read 0' will immediately be true and undo my work. I need a statement that is effectively 'else if read 0', is there any turing trickery that I can employ to do something like this?

# Answer
> 0 votes
The following code should work:

```
whileNot read #
    while read 1
        write 0
        goRight
    while read 0
        write 1
        goRight

```

As for implementing IF-THEN-ELSE in general, it depends on the exact semantics of your programming language, which you haven't specified.

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


title: How to compress a bit string?

text:
# Question
Title: How to compress a bit string?
I'm aware of some techniques to compress a string of characters such as Huffman coding. I need to know whether there is any technique to compress a long string of arbitrary bits? (ideally with high compression ratio).

# Answer
Suppose we could always compress a string of length $n$ bits to a string of length $n/2$ bits. Apply this compression algorithm $\log\_2 n + 1$ times, and we have reduced a string of length $n$ bits into the empty string. But does the empty string really contain within itself all the information needed to reconstruct the original $n$ bit string?

More generally, a simple counting argument shows that *arbitrary strings cannot be compressed*. For any compression algorithm $C$:

1. For every $n$ we can find a string $x$ of length $n$ such that $|C(x)| \geq n$.
2. For every $n$, at least half the strings of length $n$ satisfy $|C(x)| \geq n-1$.
3. For every $n$, at least $1-1/n$ of the strings of length $n$ satisfy $|C(x)| \geq n-\log n$.

In particular, an "arbitrary" string cannot be compressed appreciably.

What are compression algorithms good for, then?

1. Many compression algorithms are *lossy*, that is, they actually throw away some of the information. This is the case with JPEG, MP3 and MPEG, for example. The compressed picture doesn't look quite the same, but it does look very similar. This property of pictures, that a picture can look similar while differing at the bit level, is exploited by lossy compression algorithms. These algorithms isolate the important parts of the data which are enough to cause in the viewer the same sensation as the original.
2. Some compression algorithms are *lossless* but are still able to compress their input. This is because the inputs are often not random and have structure which can be exploited. For example, HTML documents are extremely non-random: for one, they don't use the entire range of characters, but only alphanumeric characters and punctuation. Even raw sound files and pictures can be compressed appreciably, since music and images one would like to compress are not arbitrary white noise, but are smooth in various ways.

After you have compressed a file once, you don't expect it to be compressible again. The aim of a good compression algorithm is to achieve a random looking output, which in particular usually cannot be compressed, as we've seen above.

There are many lossy and lossless compression algorithms out there. If you're looking for lossless compression, you can try some of them out. Many are implemented as standalone tools such as ZIP and BZIP2. Lossy compression strongly depends on the type of medium you are trying to compress. Again, standalone tools are usually available for your perusal.
> 2 votes

---
Tags: computer-networks, data-compression
---


# Question
Title: Solving cycle in undirected graph in log space?
**Setting**

Let: $$UCYLE = \mathcal \\{ \<G\> ~:~ G \text{ is an undirected graph that contains a simple cycle}\\}.$$

**My Solution**

we show $UCYLE \in L$ by constructing $\mathcal M$ that decides $UCYLE$ using $L$ space.

$\mathcal M = $"On input $\<G\>$ where $G = (\mathbb V, \mathbb E)$:

1. For each $v\_i \in \mathbb V$, for each $v\_j \in Neighbor(v\_i)$, store the current $v\_i$ and $v\_j$.
2. Traverse the edge $(v\_i,v\_j)$ and then follow all possible paths through $G$ using DFS.
3. If we encounter $v\_k \in Neighbor(v\_i) / \\{v\_j\\}$ so that there is an edge $(v\_i,v\_k) \in \mathbb E$, then ACCEPT. Else REJECT."

First we claim $\mathcal M$ decides $UCYLE$. First, if there exists a cycle in $G$, then it must start and end on some vertex $v\_i$, step one of $\mathcal M$ tries all such $v\_i$'s and therefore must find the desired vertex. Next, suppose the cycle starts at $v\_i$, then there must exists a starting edge $(v\_i,v\_j)$ so that if we follow the cycle, we come back to $v\_i$ through a different edge $(v\_k,v\_i)$, so we accept in step three. Since the graph is undirected, we can always come back to $v\_i$ through $(v\_i,v\_j)$, but $\mathcal M$ does not accept this case. By construction, neither does $\mathcal M$ accept if we come upon some $v\_k \in Neighbor(v\_i)/\\{v\_j\\}$ but there is no edge from $v\_k$ to $v\_i$.\newline

Now we show $\mathcal M \in L$. First if the vertices are labled $1,\ldots,n$ where $|\mathbb V| = n$, then it requires $log(n)$ bits to specify each $v\_i$. Next note in $\mathcal M$ we only need to keep track of the current $v\_i$ and $v\_j$, so $\mathcal M$ is $2 log(n) = O(log ~n) \in L$.

**My Problem**

My problem is how do you perform DFS on the graph in $log(n)$ space. For example, in the worst case where each vertex has degree $n$, you'd have to keep a counter of which vertex you took on a particular path, which would require $n \log(n)$ space.

# Answer
> 5 votes
The trick is to use Reingold's result that undirected reachability is in logspace. For each vertex $v$, we check whether the connected component containing $v$ contains a cycle by counting the number of vertices and edges. We do that by going over all vertices $u$, check whether $u$ is reachable from $v$, and if so, increase the vertex counter by 1 and the edge counter by half the degree of $u$. After going over all vertices, we have counted the number of vertices $V$ and edges $E$ in the connected component containing $v$. This component contains a cycle if and only if $E \geq V$.

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


# Question
Title: PSPACE languages reducible to other PSPACE languages in polynomial space
Intuitively it makes sense that all PSPACE languages are reducible to other PSPACE languages in polynomial space. But how would I go about actually showing this?

# Answer
> 2 votes
The same way that you show that any problem in **P** is polytime reducible to any other, or that any decidable language is Turing reducible to any other: solve the problem in the reduction.

Note that the claims (yours in the question and mine above) aren't quite true for many-one reductions, since you can't reduce any other language to $\Sigma^\*$ or $\emptyset$ using many-one reductions.

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


# Question
Title: Understanding an upper bound in the analysis of Karger's algorithm
I'm reading the wiki page of Karger's algorithm for a self-study of CLRS to get some and I'm confused by one of the bounds they have.

Here, under the section about finding all min cuts, they have this line $$(1-P(n))^{O(\log^{2} n)} \le (1-\frac{c}{\ln n})^{\frac{3}{c} \ln^{2} n}$$. I get that they are using the definition of big O to insert these constants, but what feels fishy to me is the choice for the constant in the exponent of $\log^{2} n$ of $\frac{3}{c}$. Why can't I just choose the coefficient to just be, $\frac{2}{c}$ and get a tighter bound? How do they know here that $\frac{3}{c}$ is the smallest coefficient that may be chosen?

I understand the rest of the argument, for the record (They're using $e^{x} \ge 1+x$)

# Answer
$$(1-P(n))^{O(\log^{2} n)} \le (1-\frac{c}{\ln n})^{\frac{3}{c} \ln^{2} n}$$

First, to get a tighter bound, you should choose $\frac{4}{c}$ or larger, instead of $\frac{2}{c}$ or smaller.

In particular, the probability for $\frac{2}{c}$ is $$\textrm{Pr}\[\textrm{miss any min-cut}\] \le O(1).$$ This does not make sense for a probability value.

Second, the larger the chosen coefficient is, the higher the time complexity of the algorithm is (to achieve a tighter bound). That is, there is a trade-off.
> 1 votes

# Answer
The point here is that at the end the argument will use a union bound over all the $O(n^2)$ min cuts. So the failure probability for a single minimum cut needs to be $o(n^{-2})$ for this to give any useful information.

An alternative would be to try and replace the union bound with a more precise argument, but since a cycle has $\Omega(n^2)$ min cuts, this won't work in general.
> 0 votes

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


title: Why does SAT not reduce to QBF?

text:
# Question
Title: Why does SAT not reduce to QBF?
So, I remember the professor saying that SAT does not reduce to QBF (Quantifier Boolean Formula)

$QBF ::= prop|-QBF|(QBFoQBF)|\exists pQBF |\forall pQBF$

So, I guess this is not NP, since solving a QBF could grow exponentially.

However, $P \subseteq NP \subseteq PSPACE \subseteq PSPACE$-complete, so shouldn't I be able to reduce NP \< PSPACE-complete, hence SAT \< QBF?

The reduction would just use the same formula of PSAT in QBF.

Am I correct?

# Answer
> 7 votes
First, be carefull, it might be that PSPACE ⊄ PSPACE-complete. If you suppose PSPACE ⊆ PSPACE-complete (thus PSPACE = PSPACE-complete since the other inclusion is true), then every problem of PSPACE is PSPACE-complete. Thus, all problems of PSPACE can be reduced to some easy problem of P (which is also in PSPACE). This is very unlikely (but not (yet) proved true or false).

Now, let us consider the reduction you propose.

If I understood well, you want to take a formula of SAT. The reduction would be to take the same formula for QBF (with, I suppose, an existential quantifier for each variable, otherwise it would not be a valid QBF formula).

This is indeed a valid reduction, and the SAT formula would be satisfiable if and only if the QBF formula was true.

By doing so, you reduce SAT to QBF. This shows that QBF is at least as hard as SAT. Since SAT is NP-complete, this shows that QBF is NP-hard.

The reduction in the other way (taking a QBF formula and making a SAT formula) is not known. This is why we do not know whether NP=PSPACE or not.

---
Tags: complexity-theory, decision-problem
---


# Question
Title: Differences between linear/nonlinear vs. deterministic/nondeterministic neural nets
When speaking of neural networks, I don't get the difference between nonlinear and non-deterministic. Basically, both say that the output of something is not directly correlated to the input?

Hope someone can illuminate me.

# Answer
> 4 votes
Non linear means that there may be a correlation with the input, but it is not a linear one. A function is say to be linear in some argument (the input) when the ratio result/argument is constant. In your case, it is the ratio output/input. Actually, the mathematical definition is a bit more general.

Non determinism is of a different nature. The input/output relation is said to be non-deterministic when one of several result may occur, without any *a priori* known cause. This is usually modelelled mathematically, either by using a relation rather than a function, of by considering a function from the input domain to the domain of subsets of the output domain.

For example: if you consider inputs and outputs in the domain of integer, for each integer input, you have a set of possible outputs that are all integers.

When this set always contains only a single element, the function is deterministic, and the set can be replaced by this unique element.

---
Tags: terminology, artificial-intelligence, neural-networks
---