# Question
Title: How does the computer determine whether a number is smaller or greater than another?
It might sound like a stupid question but I'm really curious to know how a computer knows that $1\<2$? Also, how does a computer know that the order of integer is $1,2,3,4,5,\ldots$ and alphabet is A,B,C,D,...? Is it somewhere stored in the hardware or does the operating system provide this kind of information?

# Answer
> 34 votes
First your integer numbers are converted into binary numbers. For example, the integer 2 is converted to 0010.

The CPU uses a digital comparator:

> A *digital comparator* or magnitude comparator is a hardware electronic device that takes two numbers as input in binary form and determines whether one number is greater than or less than or equal to the other number.
>
> Comparators are used in central processing units (CPU) and microcontrollers.
>
> Source: https://en.wikipedia.org/wiki/Digital\_comparator

In comparator hardware some gates are used (AND, OR, NAND, NOR, XOR, etc). These gates take binary inputs and give result in binary. The output can be seen from a truth table.

```
Inputs           Outputs
A   B     A>B    A=B    A<B
0   0     0       1      0
0   1     0       0      1
1   0     1       0      0
1   1     0       1      0

```

Here `0` & `1` are electronic voltages for the gate.
`1` \- Represents some threshold voltage which indicates some positive voltage.
`0` \- Represents the voltage below than the threshold.

E.g. suppose a comparator works on 5 volt (it is consideration for explanation) then:
Voltage more than 3 volt can be considered as `binary-1`.
Voltage below than 3 volt be considered as `binary-0`

If a gate gets one input as 3.5 volt and another input as 2 volt then it considers as, it takes one input as binary 1 & another input as binary 0.

These sequences of 1's & 0's are provided very fastly through the switching circuit.

The operation of a two bit digital comparator can be expressed as a truth table:

```
 Inputs                            Outputs
   A1   A0  B1  B0  A>B    A=B   A<B
    0   0   0   0    0      1     0
    0   0   0   1    1      0     0
    0   0   1   0    1      0     0
    0   0   1   1    1      0     0
    0   1   0   0    0      0     1
    0   1   0   1    0      1     0
    0   1   1   0    1      0     0
    0   1   1   1    1      0     0
    1   0   0   0    0      0     1
    1   0   0   1    0      0     1
    1   0   1   0    0      1     0
    1   0   1   1    1      0     0
    1   1   0   0    0      0     1
    1   1   0   1    0      0     1
    1   1   1   0    0      0     1
    1   1   1   1    0      1     0

```

To quote from Wikipedia:

> Examples: Consider two 4-bit binary numbers A and B such that
> Here each subscript represents one of the digits in the numbers.
>
> ## Equality
>
> The binary numbers A and B will be equal if all the pairs of significant digits of both numbers are equal, i.e.,
> . . .
>
> Since the numbers are binary, the digits are either 0 or 1 and the boolean function for equality of any two digits and \> can be expressed as
>
> is 1 only if and are equal.
>
> For the equality of A and B, all variables (for i=0,1,2,3) must be 1. So the quality condition of A and B can be implemented using the AND operation as
> The binary variable (A=B) is 1 only if all pairs of digits of the two numbers are equal.
>
> ## Inequality
>
> In order to manually determine the greater of two binary numbers, we inspect the relative magnitudes of pairs of significant digits, starting from the most significant bit, gradually proceeding towards lower significant bits until an inequality is found. When an inequality is found, if the corresponding bit of A is 1 and that of B is 0 then we conclude that A\>B. This sequential comparison can be expressed logically as:

# Answer
> 16 votes
It doesn't just "know", it checks every time. Basically, it does the same thing you would do: in order to compare, it checks (from the left) which number has the first digit that is larger than the corresponding one in the other number. Of course you have to add leading zeroes to the shorter number.

Letters are just numbers for the computer. Humans have assigned numbers, e.g. ASCII or Unicode, to letters so that number comparisons give the "correct" order for letters, too.

# Answer
> 9 votes
It's not the operating system that compares integers, the CPU is taking care of it. It's made on logical gates level, please refer to these slides to see how it can be done.

About the alphabet, in ASCII alphanumeric and other special characters are represented as integers so comparing them is also an integer comparison operation, which is performed by the CPU.

# Answer
> 5 votes
Actually, and in order to obtain the full image of it, I think it would be quite helpful to see with your own eyes the datapath of an actual CPU, for example MIPS:

As you may see, there is actually a second output from the ALU, which is a signal called Zero. It exists in order to perform fast branch operations, after determining **whether the two operands of the comparison are equal to zero or not**, as most comparisons within a program are about branches. Therefore, when you create a branch possibility in your code like:

if(a \< b) {...}

This is translated into machine code, in mips for example: **blt s0,s1,If** $~\Rightarrow$ if a \< b execute the instructions in the brackets, else continue with the execution outside the if{}. Specifically this instruction is a pseudo-instruction, which means that is translated into two other (simple) MIPS instructions $~\Rightarrow$
**slt at,s0,s1** and then **bne at,zero,If** (slt: Set Less Than & bne: Branch on Not Equal).

Notice that signal zero is one of the inputs of the AND gate that determines where the Program Counter (PC) will take its value from: Assuming that Branch signal is '1', as we have a branch operation

* **Zero = 0** $\Rightarrow$ The result of the subtraction was not equal to zero, so the Multiplexer will choose the address from Branch target and the execution will continue from the instruction that the branch leads.
* **Zero = 1** $\Rightarrow$ The result was 0 (a = b) and so the MUX chooses the address from the adder where is calculated the address of the next instruction in normal execution (serial). No jump is executed as the condition (a \< b) is invalid.

Hope I helped you see "under the bonnet". Feel free to ask for further analysis on this matter. Many things we take for granted, CPUs do them in a very fascinating way!

# Answer
> 2 votes
If you want to know about how an actual CPU does it, it's something like this.

A CPU operates on numbers of only up to a certain size. Nowadays that's usually 64-bit integers (we'll ignore floating-point numbers; the idea will be similar).

So we should recognize that

1. A CPU is storing numbers up to (say) 64 bits long in binary, in some format (probably 2s-complement but it doesn't matter too much what).
2. A CPU can't natively do anything with numbers bigger than that. We have to write software algorithms if we want to compare bigger numbers.

OK, so say we have two numbers that each fit in a normal-size 64-bit integer. Say $a$ and $b$. How does the processor compare them? Usually, it will subtract one from the other (that's a single native operation that is implemented in hardware).

Now the processor has stored a single number $a-b$. Again, this number is at most 64 bits, so it fits in a "register" that's 64 bits long, which is where we store our numbers for calculation. Now it just checks if $a-b$ is less than zero. It does this with a single native operation that could work, on the circuit level, like the comparison algorithms that the other answers have described. It will look a lot like those, but all implemented in circuits (because the number is at max 64 bits, this is a certain-size circuit that we can hardwire and stick on the CPU.) Depending on how the CPU stores numbers, it might be even faster because it might be that all negative numbers have the first bit set to one, or something like that. Either way, there's only 64 bits total, so we can definitely check if this number is negative.

If it is, then we know $a \< b$; if not, then we know $a \geq b$.

Now, for bigger numbers, we have to implement something in software that will use these small comparisons as subroutines.

# Answer
> 1 votes
To answer this question let me first point out that there are at least two levels on abstraction for the comparison numbers on a computer, the **machine-level**, and the **software level**.

**Comparing numbers on the machine level**

In today's computer the CPU has a rich set of instruction. These instructions include for example loading a memory cell into a register, incrementing a register, adding two registers, and many many more. There have also to be instructions for *conditional jumps*. For example the processors in Intel's x86 family support the instructions `jnz` (jump if not zero), `jne` (jump not equal), and so on. If those would be missing then the CPU would not be Turing-complete. The variables from which the conditional jump depends are stored in the registers. Thus, these instructions are hard-wired in the architecture of the CPU as a circuit build from logical gates. This is the only way how the CPU can *compare* two numbers.

**Comparing numbers on the software level**

If you compare two numbers, say in a c++ program, then this is translated into machine code and therefore carried out on the machine level. However, such an comparison can be more complex. It really depends on the data type you used how the comparison is translated into machine code. Just one example, the numbers you want to compare are from the 64 Bit words but your machine has only works with 32 bits. Then this number does not fit in a register, hence the compiler will break down the comparison into a sequence of comparisons on the machine code level. The same applies for more complicated data types/data structures, representing for example rational numbers, or strings, or characters. Hence when you have to compare two characters, this is to translated by software (operating system, compiler, interpreter,...) into machine code. The actual translation depends on the encoding of the character/number.

As a final remark I want to point out that standard CPUs can also work with different representations of numbers (signed integers in 1- or 2-complement representation, floats). Also comparisons might be carried out in other parts of the computer such as the GPU.

# Answer
> 0 votes
other answers are good, just throwing another one out there for further consideration/insight with a CS flavor/twist. one can construct an FSM, a finite state machine, that can compare two binary numbers of any length, starting pairwise from the most significant bits and working to least significant bit (LSB). it can also be used to conceptualize the digital comparator given in another answer, yet the FSM does not require finite length binary numbers. it can even work on integers with binary fractions after the LSB. it has an inductive and recursive flavor and can be proven correct by simple induction. it runs as follows:

* input the top two binary digits as a pair (a,b)
* if a=1 and b=0 the left number is larger.
* if a=0 and b=1, the right number is larger.
* otherwise the numbers are "equal up til now", advance to next pair.

in other words the largest number is the one with the first occurrence of a bit that is one and the other is zero, after an initial run of zero or more identical 1's. a finite-length digital comparator made of gates or 1-bit comparators can be seen as based on fixing the length of this FSM operation to some fixed number of bits. (yes there is a strong correspondence between all finite circuits and "fixing the length" of FSM computations.)

this may seem like a theoretical exercise but actually, the logic in software to represent *arbitrary precision* numbers operates something analogous to this FSM, except encoded in a computer loop that can be seen as looping over or simulating the steps of the FSM (an efficient implementation might track via an index the location of the MSB).

---

also, lets reasonably interpret/generalize this question as *not limited to integers*. the question refers to integers but the title only refers to numbers. surprisingly nobody else mentioned floating point arithmetic so far.

basically that works by comparing the *exponent* and the *mantissa* where a number is in the form $a \times 10^b$, $a$ the mantissa, b the exponent. the mantissa can be normalized to a number where the first digit is always nonzero. then to compare two numbers the logic first compares the exponents $b$, and if they are unequal, it can return a result without comparing the mantissas (using say the comparator circuit). if the exponents are equal, it compares the mantissas.

---
Tags: computer-architecture, reference-question
---


# Question
Title: Clarification with Kuhn-Munkres/Hungarian Algorithm
I have been attempting to get my mind around the Kuhn-Munkres/Hungarian Algorithm. I have been using the following statement of the algorithm which I found here.

Based on my readings on the algorithm, my understanding is that the improvement of the feasible vertex labeling in step 2. is supposed to be such that $G\_l \subset G\_l'$.

The part I'm getting stuck on is that it seems to me that it is possible for there to be an edge $xy$ in $G\_l$ with $y \in T$ but $x \not \in S$ resulting in the fact that $$ l'(x) + l'(y) = l(x) + (l(y) + \alpha\_l) \not = w(xy) $$ and so $ xy \not \in G\_l'$ and $G\_l \not \subset G\_l'$.

Can anyone point out where I'm going wrong?

# Answer
> 3 votes
You are right that $G\_{l'}$ is not necessarily a superset of $G\_l$. However, you can still prove that the algorithm runs in strongly polynomial time. You have the following invariants:

* all edges in $M$ remain edges of $G\_{l'}$
* we don't remove vertices from $S$ and $T$ until we increase the size of the matching $M$, at which point $S$ and $T$ are reset (step 1); so the size of $S$ and $T$ is monotonically increasing until the size of $M$ is increased by 1
* after updating the labels to $l'$, the size of $T$ is increased by at least 1 in the next step

What can you conclude from this? The size of the matching $M$ never decreases. At each iteration we either increase the size of $T$, or we update the labels, which will cause us to increase the size of $T$ in the next iteration. So after $2n$ iterations, the size of $T$ will be $n$. Since $T$ cannot grow anymore, we will have to increase the size of $M$. But the size of $M$ is at most $n$, so the algorithm will finish after at most $O(n^2)$ iterations. An iteration can be executed in time $O(m)$, so the total running time is bounded by $O(n^2m)$.

BTW the sets $S$ and $T$ are a bit mysterious in this description of the algorithm. Here is how we usually think about them. Orient all edges in $G\_l$ as follows: the edges in $M$ go from $Y$ to $X$ and all other edges go from $X$ to $Y$. Then $x$ is an unmatched vertex, $T$ is computed to be the set of vertices in $Y$ reachable from $x$ by a directed path, and $S$ is the set of vertices in $X$ reachable from $x$ by a directed path. If $T$ contains an unmatched vertex, we have found an odd-length alternating path, and we can augment the matching (increase its size by reversing the direction of the edges along the path). Otherwise, we can change $l$ so that the size of $T$ increases.

---
Tags: algorithms, bipartite-matching
---


# Question
Title: For what values of A and B is the gap-VC-[A,B] problem NP-HARD?
For which values $A,B$ is the problem $\mathsf{gap\mathord-VC}\mathord-\[A,B\]$ NP-hard? VC is the vertex cover problem. I am given three options: $B=\frac{3}{4},A=\frac{1}{2}$ or $B=\frac{3}{4},A=\frac{1}{4}$ or none.

I would to review what I think that I need to do, I'm not sure that the way I think of it is correct. This is what I think: I need to decide if it NP-hard to approximate the VC to $\frac{1}{2}$, i.e., can I build an NP Turing machine that would return Yes iff for a given graph, it can guarantee that it has less than $\frac{1}{4}V$ vertices that cover the whole graph? Maybe even for $\frac{1}{2}V$ vertices?

<sub> This is a question from a past midterm that I'm solving now in order to prepare myself for my own midterm in a "Computational Complexity Theory" course. </sub>

# Answer
Vertex cover has an easy $2$-approximation, so gap-VC-\[$1/4,3/4$\] is easy. The best unconditional hardness result is by Dinur and Safra, which gives $1.3606$ hardness. Since $(3/4)/(1/2) = 1.5 \> 1.3606$, their method definitely doesn't imply gap-VC-\[$1/2,3/4$\]-hardness. Assuming the Unique Games Conjecture, the hardness of vertex cover is $2-\epsilon$, but this doesn't necessarily imply that gap-VC-\[$1/2,3/4$\] is hard - you'd have to look at the proof to determine that.

In summary, I have no idea what the correct answer is, and I'm not sure that anyone else knows which answer is correct (unconditionally).
> 2 votes

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


# Question
Title: Finding the greatest $k$ numbers with a certainty of $p$
Given $n \in \mathbb{N}$ pairwise distinct numbers. I want to do as few comparisons per number as possible - and every number should experience roughly the same amount of comparisons as another number - and find the greatest $k \leq n$ numbers, e.g. $k = \frac{n}{10}$. In order to minimise the number of comparisons per number, I allow an error, say I am okay if I know that the result is correct with only a probability of $p$.

I study mathematics and only had a very shallow introduction to algorithms so far, and the only relevant algorithms we discussed would be sorting algorithms. QuickSort comes to mind, but firstly I am not sure how I would implement my "tolerance of an error" and secondly, I think the fact that I only need the greatest $k$ numbers and I don't want to sort them, there might be more efficient algorithms.

Any basic approach would be a great help already, I'll gladly do the maths on my own.

Thanks in advance for any help.

# Answer
> 7 votes
I propose the following algorithm. You take some random element $p$ of your input as pivot element for $k=n/10$. Next, you scan through all your data and split it into a list of elements $\le p$ and a list with elements $\>p$.

*Case 1:* The list with the larger elements contains more then $k$ elements. Then take this list and repeat.
*Case 2:* The list with the larger elements contains less than $k$ elements, say $m$. The repeat with the other list, but set $k=k-m$.
*Case 3:* Otherwise you are done.

This is very easy to implement and should find the solution quickly. (You said you want to do the math by yourself ;) )

**Remark:** There is a classic $O(n)$ algorithm for this. You can determine the $k$-th biggest element in $O(n)$ by the algorithm of Blum et al. and then use this element as pivot. However, I think the the constant in the $O(n)$ makes this variant slower then the above solution. Especially if you are fine with an imprecise solution.

# Answer
> 5 votes
Use the selection algorithm to find the $k$th greatest element, and then run through your set of numbers to keep only the elements greater than this $k$th element.

The time complexity of this algorithm is $O(n)$. This means that there is a constant $c$ such that the number of comparisons and the number of computation steps are eventually bounded by $cn$ where $n$ is the number of elements.

# Answer
> 5 votes
Here's something more complicated, which performs $n + o(n)$ comparisons, and achieves an approximately correct list with high probability.

Suppose you want to partition a set $V$ of $n$ elements into a disjoint union $L \cup S$ of a set of larger elements and a set of smaller elements, where every $s \in S$ is bounded above by every $\ell \in L$, and where where $\\# L \approx \sigma n$ for some constant $0 \< \sigma \< 1$. Then with only a constant (or smaller than constant) probability of failure, we can select $L$ in such a way that it contains all of the $\sigma n$ largest elements of $V$, together with only a constant (or decreasing) fraction of extraneous elements.

### Algorithm

1. Obtain a sample $X$ of $N$ randomly selected elements, for some $0 \< N \< n$ which we will specify later. Sort them. This takes time $O(N \log(N))$.
2. For some parameter $\delta \> 0$, find a pivot $x^\ast$, chosen to be the $(\sigma + \delta/2) N^{\text{th}}$ largest element of $X$. (If there are multiple elements with the same value, put all of the copies of the value of $x^\ast$ which precedes the $(\sigma + \delta) N^{\text{th}}$ largest element into $L$; put the rest of the values, including $x^\ast$ itself, into $S$.)
3. Compare all of the remaining elements of $V \smallsetminus X$ to $x^\ast$. If they are larger, put them in $L$; otherwise, put them in $S$.

Let $M$ be the set of the $\sigma n$ largest elements of $V$. We will consider the probability that $L$ contains all of the elements of $V$, but no more than $\delta n$ additional elements of $V$ beyond that.

### Probabilistic and run-time analysis.

The probability that any particular element of $X$ is in $M$ is, by definition, $\sigma$. In particular, by the Hoeffding bound, the probability that $X$ contains as many as $(\sigma + \delta/2)N$ elements of $M$ scales as $$ \Pr\biggl\[ \\#(X \cap M) \geqslant (\sigma + \delta)N \biggr\] ~~\leqslant~~ \exp\Bigl( -\delta^2 N/2\Bigr),$$ and that therefore $$ \Pr\biggl\[ x^\ast \in X \cap M \biggr\] ~~\leqslant~~ \exp\Bigl( -\delta^2 N/2\Bigr). $$ Because $L$ is constructed to be all of the values which are larger (or at least succeed) $x^\ast$ in $V$, it follows that $M$ is a subset of $L$ provided that $x^\ast \notin M$. Then, we have $$ \Pr\biggl\[ M \not\subseteq L \biggr\] ~~\leqslant~~ \exp\Bigl( -\delta^2 N/2\Bigr), $$ for any $\delta \> 0$. We want more than this, however: we would like the number of extraneous elements in $L$ not to be too large. The *expected* number of elements in $L$ is going to be $(\sigma + \delta/2)n$, but we're interested in the probability with which it is less than $(\sigma + \delta)n$, as well as being at least $\sigma n$. That is, we want to know the probability with which the number of elements is bounded by $\delta n/2$ from the expected value, which is $$ \Pr\biggl\[ |\\# L - \sigma n | \geqslant \delta/2 \biggr\] ~~\leqslant~~ 2 \exp\Bigl( -\delta^2 N/2\Bigr). $$ If we want this probability of failure to be at most some value $0 \< p \< 1$, we then require $$\begin{equation} p \geqslant 2\exp\Bigl( -\delta^2 N/2\Bigr) ~~\implies~~ N \geqslant \frac{2\ln(2/p)}{\delta^2}\\;.\end{equation}$$ If we choose $N$ to be at least this large, then with probability $(1-p)$, the set $L$ will contain all of the elements of $M$, but no more than $\delta n$ elements more than that — it will be a *modest overestimate* of the set $M$.

The above also holds if $p$ or $\delta$ are decreasing functions of $n$, so that the notion of just *how* modest an overesitmate $L$ is, or how high a probability of success we can achieve, can be tuned to a limited extent. However, in order to compete with the deterministic, linear-time selection procedures, we require the sort-time of the set $X$ to be $o(n)$. If we set $N = \bigl\lceil \ln(1/p)/2\delta^2 \bigr\rceil$, we then have $$ O(N \log(N)) ~=~ O\left( \log(1/p) \delta^{-2} \Bigl\[ \log \log(1/p) + \log(1/\delta) \Bigr\] \right) ~\subseteq~ o(n) . $$ The remaining run-time is taken up by comparisons of the other elements of $V$ with the pivot $x^\ast$, which is an unavoidable overhead, but is at most $n$ comparisons. Then there are a total of $n - N + O(N \log (N)) = n + o(n)$ comparisons made, where $x^\ast$ is subject to the most comparisons (at most $n + o(n)$ comparisons), all of the other $N-1$ elements of $X$ are subject to at most $N \in o(n/\log(n))$ comparisons each, and every remaining element is compared only once.

### Examples & Remarks.

If we're content to achieve a constant but small probability of failure $0 \< p \ll 1$, and overestimate by some constant fraction $0 \< \delta \< 1$ of the elements of $V$, then the bound on $N$ gives us some constant size of sample which is enough to achieve this; this gives the smallest possible number of comparisons, $n + \theta(1)$, and also where the number of comparisons is closest to being uniform for all elements. For other cases, where we only require $N \log(N) \in o(n)$, here is a range of possibilities.

Suppose that we wanted to have the probability of success increase with $n$, for instance $1/p \in O(n^t)$ for some fixed $t \> 0$. To have $N \log(N) \in o(n)$, we require $$ t \delta^{-2} \Bigl\[ \log (t) + \log \log(n) + \log(1/\delta) \Bigr\] ~\in~ o(n / \log(n)) . $$ (We can neglect all of the contributions of $t$ to this.) From the above, we clearly have $\delta^{-2} \in o(n / \log^2(n))$, so we may consider $1/\delta \in o(\sqrt{n} / \log(n))$; this gives us $$ O(N \log(N)) ~\subseteq~ o\left( n \log(n) / \log^2(n) \cdot \Bigl\[ \log(n) - \log \log(n) \Bigr\] \right) ~=~ o(n). $$ This is a sufficient condition. Then, with probability of failure $p \sim 1/n^t$, we can obtain a list $L$ which contains all of $M$, and any number of extraneous elements which scales faster than $\log(n)/\sqrt{n} \cdot n = \sqrt{n} \log(n)$. It's not hard to show that if we want $t = 0$ (that is, $1/p$ is constant), we get a modest improvement so that we require a number of extraneous elements scaling faster than $\sqrt{n \log(n)}$. If we choose for $1/\delta$ to grow substantially faster than $\Omega(\sqrt n)$, for instance $\delta \sim n^{-2/3}$, we can even achieve probabilities of failure which shrink exponentially quickly, as a trade-off for an increasing number of comparisons (but which is still asymptotically just larger than $n$).

You can also easily modify the algorithm to obtain a list which with high probability contains *only* elements among the highest $\sigma n$ elements of $V$, while omitting only $\delta n$ of them, or to identify in the list $L$ constructed above an element which with high probability is one of the $\sigma n$ elements of $V$; the analysis is similar in either case. If you want a more sophisticated result than this, which might achieve $n - o(n)$ comparisons (or even $n - O(n)$ comparisons), you will have to specify precisely what sort of error conditions are acceptable.

---
Tags: algorithms
---


title: How do I structure hexagon edge data?

text:
# Question
Title: How do I structure hexagon edge data?
In my program, it draws them by offsetting every other row by half of the width, as pictured above. Each tile can be referenced by coordinates, also shown above.

I want to know how many blue tiles are accessible from a certain starting tile and a series of "roads." In this example, three blue tiles can be reached.

How would I represent roads? This is what I would need to know about it:

* how it is rotated (for drawing)
* which hexagons it borders
* which other roads it touches, if any
* where it should be drawn

I assume I could use recursion to to count the accessible blue squares if the above conditions are met.

# Answer
> 3 votes
Let us first calculate the coordinates $C(m,n)$ of the center of hexagon $(m,n)$. We assume that the origin is at the center of hexagon $(0,0)$ and that the hexagon radius (distance from center to vertex) is $r$. A short calculation shows that hexagon $(1,0)$ has its center at $$C(1,0) = a = (\sqrt{3} r, 0)$$ and hexagon $(0,1)$ has its center at $$C(0,1) = b = (\sqrt{3} r/2, 3 r/2).$$ Therefore, hexagon $(m,n)$ has its center at $$C(m,n) = m \cdot a + n \cdot b = (\sqrt{3} r (m + n/2), 3 r n / 2).$$ Notice that we should allow negative $m$ and $n$ if we want to cover the whole plane.

To get from the center $C(m,n)$ to one of the adjacent centers we need to add to $C(m,n)$ one of the vectors $a$, $b$, $-a$, $-b$, $a - b$, or $b - a$. (If we add $a + b$ or $-a-b$ we go too far). If we travel *half* the distance we will end up exactly in the midpoint of a side. Therefore, midpoints of sides have coordinates of the form $$C(m+1/2, n), C(m,n+1/2), C(m-1/2,n), C(m,n-1/2), C(m+1/2,n-1/2), C(m-1/2,n+1/2).$$ We have discovered how to encode sides: just use half-integer coordinates. But this is silly, it is better to multiply everything by two, which leads to the following system.

We represent *both* hexagons and sides as pairs of integers $(m,n)$. When $m$ and $n$ are both even this encodes a hexagon whose center is at $$C(m/2,n/2) = (m \cdot a + n \cdot b)/2.$$ If either $m$ or $n$ is odd then $(m,n)$ represents a side of a hexagon whose midpoint is at $C(m/,n/2)$.

It is also easy to tell which two hexagons a given side belongs to: the side $(2 i + 1, 2 j)$ belongs to hexagons $(2 i, 2 j)$ and the side $(2 i + 2, 2 j)$, while the side $(2 i, 2 j + 1)$ belongs to hexagons $(2 i, 2 j)$ and $(2 i, 2 j + 2)$.

Similarly, the sides of hexagon $(2 i, 2 j)$ are: $(2 i + 1, 2 j)$, $(2 i - 1, 2 j)$, $(2 i, 2 j + 1)$, $(2 i, 2 j - 1)$, $(2 i + 1, 2 j - 1)$ and $(2 i - 1, 2 j + 1)$.

We now have a good system for representing hexagons and sides as pairs of integers. We still need to solve the original problem, namely which blue hexagons are reachable from a starting hexagon by traveling along certain "black" paths. This is a graph-theoretic reachability problem if we think of sides as edges in a graph and their endpoints as vertices of a graph (as we reach each black side we verify whether it belongs to a blue hexagon). Many algorithms are known on how to solve this. Let me know if you need more details.

# Answer
> 0 votes
You could represent a road as a list of the two faces involved. Given a road and a hexagon, you can explicitly calculate the roads next in order clockwise or counterclockwise on the hexagon. That way you can find all the neighbours on both sides.

This suggestion is attributed to the hypermap community by Gonthier et al., where it is called "dart" or "flag" (see pages 18-19).

---
Tags: data-structures, graph-traversal
---


# Question
Title: A question about parallel algorithm complexity
When in a Parallel algorithm we say:

> "This algorithm is done in $O(1)$ time using $O(n\log n)$ work, with $n$-exponential probability, or alternatively, in $O(\log n)$ time using $O(n)$ work, with $n$-exponential probability."

Then Can we Implement this algorithm for a Quad-Core Computer (and just 4 threads) with $n=100,000$?

The other question is what is the "$n$-exponential probability" in this sentence?

Thanks.

# Answer
You are probably in the realm of asynchronous parallel computations where units of work are performed by processors at their pace and communication is performed explicitly. This model is a good approximation to many real life parallel computers such as PC clusters or multicore CPUs.

You have an algorithm that can be represented as $O(n \log n)$ units of work each taking constant time or as $O(n)$ units of work each taking $O(\log n)$ time. Here $n$ is a parameter that characterizes the size of the problem.

The units of work can be executed on a parallel computer with a fixed number of sequential processing elements (e.g. processor cores). It depends on the algorithm whether the work units can complete while other work units have not started, or whether the computations will have to interleave.

In a practical computer interleaving can be achieved through pre-emption and context switches.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, parallel-computing
---


title: Space complexity below $\log\log$

text:
# Question
Title: Space complexity below $\log\log$
Show that for $l(n) = \log \log n$, it holds that $\text{DSPACE}(o(l)) = \text{DSPACE}(O(1))$.

It's well known fact in Space Complexity, but how to show it explicitly?

# Answer
So here is the main idea behind this fact. Let us denote by $C$ all possible configuration of the $l(n)$-space bounded TM. Notice that $|C|\le 2^{c\cdot l(n)}$, where $c$ is a constant depending on $M$.

We assume that the input tape is a two-way tape. Let $w$ be a word of size $n$, such that for all smaller words $u$ we have $l(w)\>l(u)$. When the head moves from position $i$ to position $i+1$ on the input tape, or vice versa, we record the current configuration of the computation in the *crossing sequence* $C\_i$. Assume we have $i\neq j$ with $C\_i=C\_j$. Then we define as $w'$ the word obtained from $w$ by deleting everything between the characters number $i$ and $j$. We observe that $w'$ is a shorter word which uses the same amount of space. Contradiction, there is no such $w$.

If $l(n)\in o(\log\log n)$ then you have $o(\log n)$ configurations and $o(n)$ crossing sequences. Hence two crossing sequences are the same.

Notice that if your input tape is 1-way, then even with $o(\log n)$ space you are doomed.
> 6 votes

# Answer
The (I think) original proof is by Hartmanis, Lewis & Stearns, conveniently available for free :).

My rough understanding of it is that it goes via equivalence to the class of regular languages in the sense that you only need a constant amount of space to decide a regular language (just whatever state it's up to, basically), so they're decidable in $DSPACE(O(1))$, but if you want to decide anything *non-regular*, then you need $\Omega(\log\log n)$ space, so there's an "empty" gap, even with that extra bit of space ($o(\log\log n)$), it's so tiny that you can't do anything new with it.
> 3 votes

---
Tags: complexity-theory, regular-languages, space-complexity, lower-bounds
---


# Question
Title: How many edges must a graph with N vertices have in order to guarantee that it is connected?
> **Possible Duplicate:**
> Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected

At lesson my teacher said that a graph with $n$ vertices to be certainly connected should have
$ {\frac{n(n-1)}{2}+1 \space }$ edges showing that (the follow is taken from the web but says the same thing):

> The non-connected graph on n vertices with the most edges is a complete graph on $n-1$ vertices and one isolated vertex. So you must have $ 1+ {\frac{n(n-1)}{2} \space}$ edges to guarantee connectedness.

**My idea:** a complete graph $K\_{n-1}$ with $n-1$ vertices has ${n-1 \choose 2}$edges, so ${\frac{(n-1)\*(n-2)}{2}}$ edges, added to the edge to connect the complete graph to the isolate vertex,

so shouldn't be ${\frac{(n-1)\*(n-2)}{2}}+1$ edges?

What am I doing wrong?

Thanks.

# Answer
> 6 votes
Don't know why I didn't just give an answer, rather than a comment, but for posterity:

Your reasoning is correct, the $n$ vertex graph with the maximal number of edges that is still disconnected is a $K\_{n-1}$ with an additional isolated vertex. Hence, as you correctly calculate, there are $\binom{n}{2} = \frac{(n-1)(n-2)}{2}$ edges.

Adding any possible edge must connect the graph, so the minimum number of edges needed to guarantee connectivity for an $n$ vertex graph is $\frac{(n-1)(n-2)}{2}+1$.

Contrary to what your teacher thinks, it's not possible for a simple, undirected graph to even have $\frac{n(n-1)}{2}+1$ edges (there can only be at most $\binom{n}{2} = \frac{n(n-1)}{2}$ edges).

The meta-lesson is that teachers can also make mistakes, or worse, be lazy and copy things from a website.

For an extension exercise if you want to show off when you tell the teacher they're wrong, how many edges do you need to guarantee connectivity (and what's the maximum number of edges) in a

1. Simple, directed graph?
2. A directed graph that allows self loops?

# Answer
> 13 votes
The formula is worthless without a proof.

Suppose we have a graph on $n$ vertices which is not connected. Then it is possible to divide into two disjoint subgraphs, say one with $i$ vertices and another with $n - i$ vertices. The component with $i$ vertices has at most $i (i - 1)/2$ edges, while the component with $n - i$ vertices has at most $(n - i) (n - i - 1)/2$ edges (this happens when the two components are complete graphs). Therefore we have at most $$i (i - 1)/2 + (n - i) (n - i - 1)/2 = i (i - n) + n (n - 1) / 2$$ edges. The number of edges has a fixed part $n (n - 1) / 2$ and a variable part $i (i - n)$ which depends on $i$. We would like an upper bound for the variable part. By using the method of completing the square we can write it as $$i (i - n) = (i - n/2)^2 - n^2/4.$$ As a function of $i$ this is a parabola whose minimum is at $i = n/2$. Thus, to get the largest possible value in the allowed range $0 \< i \< n$ we should plug in the value of $i$ which is furthest away from the minimum. This happens when $i = 1$ or $i = n - 1$, and both give us the same estimate: $$i (i - n) = (i - n/2)^2 - n^2/4 \leq (1 - n/2)^2 - n^2/4 = 1 - n.$$ We may thus estimate the number of edges as $$i (i - n) + n (n - 1)/2 \leq (1 - n) + n (n - 1)/2 = (n-1)(n-2)/2$$ We conclude that the number of edges in a disconnected graph with $n$ vertices is at most $(n - 1)(n - 2)/2$. This is a tight upper bound which is achieved when one of the subgraphs is a point and the other a complete graph on $n-1$ vertices.

---
Tags: graphs
---


title: Equality of NSpace and coNSpace classes

text:
# Question
Title: Equality of NSpace and coNSpace classes
I'm trying to decide which of the following statements are true:

1. $\mathsf{NSpace}(\log \log n) = \mathsf{coNSpace}(\log \log n )$
2. $\mathsf{NSpace}(\lg^2n) = \mathsf{coNSpace}(\lg^2n)$
3. $\mathsf{NSpace}(\sqrt n) = \mathsf{coNSpace}(\sqrt n)$

I thought immediately that (1) is correct since $\lg \lg n \< \lg n$, and since $\mathsf{NL} = \mathsf{coNL}$, I thought that the statement yields from it. I thought that since we don't know if $\mathsf{P} = \mathsf{PSPACE}$, we can't say anything about a class which is bigger than $\lg n$ and a subset of $P$.

But it is exactly the opposite. (1) is not necessarily true while (2) and (3) are necessarily true. Why is that?

The question is from a past midterm that I'm solving now.

# Answer
> 5 votes
I can't think of any counter-example for (i) right now. But (ii) and (iii) are true due to the Immerman–Szelepcsényi theorem\[1\], according to which $\text{NSPACE}(s(n)) = \text{co-NSPACE}(s(n))$ for all $s(n) \geq \log(n)$.

\[1\]: Wikipedia - Immerman–Szelepcsényi theorem

---
Tags: complexity-theory, space-complexity
---


# Question
Title: In a 32-bit floating number with normalized mantissa and excess-64 exponent base 16, the number $16^{-65}$ denotes
In a 32-bit floating number with normalized mantissa and excess-64 exponent base 16, the number $16^{-65}$ denotes

1. Floating point overflow.
2. Negative floating point overflow.
3. All 0's in the exponent and mantissa fields.
4. The minimum representable positive number .

I think that minimum representable number should be $1 \times 16^{-63}$ because the minimum mantissa should be 1 and and the possible exponent range in bias form is from 1 to 127 (where 1 corresponds to most negative exponent i.e. -63, and 127 corresponds to most positive exponent i.e. 63)

So according to me, the answer is: A positive floating point underflow. Please correct me if i am wrong. The IEEE-754 representation is confusing me.

Someone also told me something along the lines of " the mantissa part is always taken as 0.M if the base is something other than 2". However I don't have any reference for this statement.

# Answer
The format you are using is not IEEE-754 but an IBM FP format. The mantissa is fractional, so the binary representation 0001\_0000\_0000\_0000\_0000\_0000 means 0.1 (base 16). With a zero value in the exponent field, the exponent would be -64. So you can see that $16^{-65}$ would be the smallest *normalized* positive value ($1 * 16^{-1} * 16^{-64}$)
> 1 votes

---
Tags: numerical-analysis, floating-point, rounding
---


# Question
Title: LTL: Show $\neg(aUb) \Leftrightarrow \neg b U (\neg a \land \neg b) \lor G \neg b$
I got as far as \begin{align} w \vDash \neg (a U b) &\Leftrightarrow \neg (w \vDash a U b) \Leftrightarrow \neg (\exists\_{i\geq0} : w^i \vDash b \land \forall\_{0\leq k \< i} : w^k \vDash a) \\ &\Leftrightarrow \forall\_{i\geq0} : \neg(w^i \vDash b) \lor \exists\_{0\leq k \< i} : \neg(w^k \vDash a) \end{align}

but got stuck.

If you could offer some advice as on where to start I would very much appreciate it. Thanks in advance

# Answer
> 4 votes
$aUb$ means that $a$ holds up to (and not necessarily including) the first point where $b$ holds, which must exist. There are two ways in which this can fail: $b$ never holds, or the first time that $a$ fails precedes the first time in which $b$ is true. The first case is handled by $G \lnot b$. The second case is handled by $\lnot b U (\lnot a \land \lnot b)$ (why?).

---
Tags: logic, linear-temporal-logic
---


title: Finding reachable vertices

text:
# Question
Title: Finding reachable vertices
I'm trying to solve a graph problem ( it's not for homework, just to practise my skills ).

A dag $G(V,E)$ is given, where $V$ is the set of vertices and $E$ the edges. The graph is represented as an adjacency list, so $A\_i$ is a set containing all the connections of $i$.

My task is to find which vertices are reachable from each vertex $v\in V$.

The solution I use has a complexity of $O(V^3)$, with transitive closure, but i read that in a blog it can be faster, although it didn't reveal how. Could anyone tell me an other way ( with better complexity ) to solve the transitive closure problem in a dag? Thanks in advance.

# Answer
> 2 votes
Here is an $O(VE)$ algorithm, which is substantially better than $O(V^3)$ if the graph is sparse. First do a topological sort, in time $O(V+E)$. Now work your way backwards, storing which vertices are reachable. At a vertex of outdegree $d$, this requires $O(dV)$ work, so in total you get $O(VE)$.

---
Tags: graphs
---


# Question
Title: Question about Prims algorithm where weights are between 1 and some constant W
I came across a couple of solutions to one of the problems that is in the CLRS textbook (pg. 637 23.2-5 edition 3). I am wondering if anyone can make a clarification as to the stated running time of the solution.

Q: Given that we know the edge weights on a graph are between $1$ and some constant $W$, how fast can we make Prim's algorithm run?

Solution:

* Uses an array of linked lists where each index corresponds to a given weight \[$1\dots W + 1$\]
* Each link linked lists contains a series of vertices with the weight of the index as their key

The run time given is $O(E)$

They break it down as follows:

$O(1)$ to find the vertex with smallest weight \- I understand this part since we scan at most $W$ array slots to find a non-empty list and $W$ is constant.

$O(1)$ for decrease key \- This makes sense as far as the actual removing of a link from one list and inserting it into another

My question is about the decrease key step. Say for example we pull the node $A$ from the 3rd slot, that is the next node to be processed. We look at $A$'s adjacency matrix and see that it has edges to $B, C, F$. Since we are using linked lists we have no choice other than to look at all array slots from $4$ to $W$ and see if we can find the vertices listed in the linked list for that particular index. Then delete the vertex from its current list and add it to the correct list if we find it. Possible search time = $O(V)$ \[since we store vertices in the linked lists and could search all before finding our desired vertex\] not $O(1)$.

Since each decrease key takes $O(V)$ and we process all vertices running time = $O(V^2)$.

If anyone could let me know where I am going astray in my analysis I would greatly appreciate it.

# Answer
> 2 votes
The solution is to preprocess the adjacency matrix so that each vertex now has a list of adjacent vertices. When decreasing keys, you address each edge at most twice, so this part of the algorithm runs in $O(E)$.

The basic observation here is that you can implement a priority queue in $O(W)$ if the number of different weights is $W$. You have to be careful to maintain an array mapping the vertices to their current location in the priority queue, but then all operations are indeed $O(W)$.

---
Tags: algorithms, graphs, runtime-analysis, spanning-trees
---


# Question
Title: $\ell_1$ Minimization of Probability Distribution and KL-Divergence
Suppose through $\ell\_1$ minimization I obtained two sparse probability distributions $P, Q$ which may contain many zero terms. Then I would like to compute the KL-Divergence of them $D(P || Q) = \sum\_i {p\_i\log(\frac{p\_i}{q\_i})}$. However, since the probability distribution is sparse, it might occur that $p\_i \not= 0$ and $q\_i = 0$. In that case, KL-Divergence is not well defined. One solution is to incorporate Dirichlet Prior. However, I am afraid by doing so the sparsity of the probability distributions is violated. Is there any other way to compute the KL-Divergence of the two probability distributions?

# Answer
> 2 votes
Have you looked into Jensen-Shannon Divergence? It avoids the situation you described by adding a midpoint. Formally we have, $$\mathrm{JSD}(P||Q) = \frac{1}{2} \mathrm{KL}(P||M) + \frac{1}{2} \mathrm{KL}(Q||M)$$ where $M = \frac{1}{2}(P + Q)$. Informally, JSD is nice when you want to compare distributions that seem to have the same shape, but dont completely overlap.

---
Tags: machine-learning, information-theory
---


title: K-Clique in Connected Graphs

text:
# Question
Title: K-Clique in Connected Graphs
A question about the clique problem (specifically k-clique). Is there any algorithm that takes advantage of the properties of connected graphs to find cliques of a given size `k`, if such cliques exist?

# Answer
> 5 votes
As pointed out in the previous answer, you cannot do very well if you simply assume that your input is a connected graph. However, you can do better if you make certain assumptions on your graph's structure. That is, one can ask: given a class of graphs $\mathcal G$, will the clique problem be solvable in polynomial time, assuming that all inputs are contained in $\mathcal G$?

The answer turns out to be positive for a nice class (or should I say classes) of graphs: graphs whose treewidth is bounded by a constant.

Without getting into too much detail (see http://en.wikipedia.org/wiki/Tree\_decomposition for more details), the tree-width of a graph is a measure of how much it "resembles" a tree. Trees have a treewidth of 1, whereas cliques have a treewidth of $n-1$ (where $n$ is the number of vertices).

The clique problem is $\mathcal O(t^t n)$ on graphs whose treewidth is at most $t$.

Treewidth is believed to be the "right" measure for graphs problems (although more complex measures do exist): Courcelle's Theorem (see http://en.wikipedia.org/wiki/Courcelle's\_theorem) states that any graph property that can be succinctly expressed via some logical parameters can be solved in polynomial time on graphs with treewidth bounded by a constant. This includes vertex cover, clique, independent set, and many others.

This means that many NP-hard graph problems are fixed parameter tractable, with treewidth being the parameter.

Hope this helps.

# Answer
> 4 votes
This seems like a fair/good question to me, but I think the answer must be negative. Here's my argument.

Suppose you had an algorithm $A$ for solving CLIQUE on connected graphs (somehow taking advantage of the connectivity property). Then I can construct an algorithm $B$ for solving CLIQUE on general graphs that is essentially no slower than $A$. I'll just find the connected components of the graph in linear time, then call $A$ on each connected component. The running time will be linear in the input plus the time of all the calls I make to $A$. In particular, if my input happens to be a connected graph already, then my general algorithm $B$ runs in time $O(|V| + |E| + Time(A))$.

This argument tells us two things. First, the best possible algorithm $A$ for your problem gets no more than an additive linear speedup over the best possible algorithm $B$ for CLIQUE applied to your problem, so we've bounded the "advantage" of knowing the input is connected to at most additive linear. Second, your problem is NP-hard because we can reduce CLIQUE in polynomial time to a polynomial number of calls to your problem. This unfortunately means that additive linear speedup is probably not much of an advantage in the scheme of things.

*Edit* \- This only referred to CLIQUE and not $k$-CLIQUE (where we fix $k$ and only let the input vary with the size of the graph). The answer depends slightly on $k$ because for *e.g.* $k=2$ the connected-graph algorithm runs in constant time (the answer is yes). However, the answer is largely the same -- for moderately large values of $k$, your running time of algorithm $A$ will be $O(g(k)(|V|+|E|))$ for some very large constant $g(k)$ (unless P\poly=NP); and then it doesn't matter much if algorithm $B$ loses another $|V|+|E|$ for scanning the input first.

---
Tags: algorithms, graphs
---


# Question
Title: How come this turing machine running time is $O(n^{1+\log_2 2006}\cdot \log_2n)$
Given a deterministic Turing machine with an input tape and a work tape. The work tape is restricted to $\log\_2 n+100$ cells ($n$ represents the input length) and its tape alphabet is of size $2006$. Moreover, the Turing machine has $27$ states.

I wonder how come the running time of such machine is $O(n^{1+\log\_2 2006}\cdot \log\_2n)$ (The answer is the correct choice for this multiple choices question out of an exam I practise)

# Answer
This bound comes from the number of possible configurations. If you do more steps than you have configurations, you are in a cycle.

So let us quickly get a bound for the number of configurations. You have $100+\log n$ possible positions for the head on the work tape and $n$ positions for the head on the input tape. The work tape can contain $2006^{100+\log n}$ different words. Furthermore there are 27 states. Combining everything gives $$ \begin{align} 27n \cdot (100+\log n) \cdot 2006^{100+\log n}&=27\cdot2006^{100}(100n+n\log n) n^{\log 2006}\\ &=O((100n+ n\log n) n^{\log 2006})\\ &=O(\log n\cdot n^{1+\log 2006})\\ \end{align}$$
> 4 votes

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


# Question
Title: For what special cases does this vertex cover algorithm fail or work?
I'm trying to find a polynomial time algorithm for finding the minimum vertex cover for a graph. I've written the algorithm below; I know this problem is $\mathsf{NP}$-hard, which means there are probably some graphs for which this algorithm will not work.

I need some help in finding the flaw in this algorithm and also, an indication for what restrictions should be imposed on graphs such that this algorithm works.

In the algorithm below I have a graph $G=(V,E)$. I also define the $\text{priority}(v)$ function; in rough terms, it is the number of edges that are covered by vertex $v$. The function has the property that

$$\sum\_{v \in V} \text{priority}(v) = \text{number of edges}.$$

In other words, an edge is counted as covered by only one of its vertices, not both.

```
Define degree : V -> NaturalNumbers
degree(v) = number of edges connected to v, for all v in V

Define priority : V -> NaturalNumbers
Initialize priority(v) = 0 for all v in V

For all (u, v) in E:
    If degree(u) >= degree(v):
        priority(u) = priority(u) + 1
    Else
        priority(v) = priority(v) + 1

Define S as the solution to the vertex cover problem
Initialize S to the empty set

For all v in V:
    If priority(v) != 0:
        Add v to the set S

Output S as the solution

```

# Answer
> 7 votes
Trying to take "high priority" i.e. high degree vertices over their neighbors will not work in all cases. This algorithm chooses $n-1$ for $C\_n$ (Cycle Graph on $n$ vertices). It should choose either $(n-1)/2$ or $n/2$ if its odd or even. It also fails for Perfect Graphs.

I'm pretty sure this gives a $O(\log n)$ approximation too. If you order vertices by degree and greedily select vertices until all edges are covered, it is basically the same greedy algorithm as $O(\log n)$ set cover.

---
Tags: algorithms, graphs, np-complete, np-hard
---


# Question
Title: Concluding $SPACE(n^2) \neq SPACE(n^7)$ from universal turing machine running time
Let $M\_U$ be an universal Turing machine which fulfills the following condition:

> If $M$ running $x$ takes $f(x)$ space, then $M\_U$ running on $\langle \langle M\rangle,x\rangle$ takes $(f(|x|))^3+2\cdot|x|+|\langle M\rangle|$ space.

Why can we conclude from the above that ${\sf Space}(n^2) \neq {\sf Space}(n^7)$?

# Answer
I assume with ${\sf SPACE}$ you mean ${\sf DSpace}$. As usual for these types of hierarchy question you can use a *diagonalization* argument.

So build a machine $D$ that takes its input $w$ and then executes $M\_u(\langle w ,w \rangle)$. While executing $M\_u$ it checks also how much space is used and how many steps the machine $M\_u$ has done. Then the result of $D$ is the following:

* if $D$ used more than $n^2$ space than reject,
* if $D$ does more than $2^{cn^2}$ steps then accept (in this case the simulation detected a cycle if $\langle w \rangle$ would be a $n^2$ space bounded TM),
* if none of the above occurred, then accept if $M\_u$ rejected, and reject if $M\_u$ accepted.

You can say that $D(w)$ *anti-simulates* the machine $M\_u(\langle w ,w \rangle)$, if $\langle w \rangle$ is in ${\sf DSpace}(n^2)$. Clearly, $\langle D\rangle$ is in ${\sf DSpace}(n^7)$. However, it cannot be in ${\sf DSpace}(n^2)$. If it would be then you get a contradiction at $D(\langle D \rangle)$.
> 3 votes

---
Tags: complexity-theory, space-complexity
---


title: Directed union-find

text:
# Question
Title: Directed union-find
Consider a directed graph $G$ on which one can dynamically add edges and make some specific queries.

### Example: disjoint-set forest

Consider the following set of queries:

```
arrow(u, v)
equiv(u, v)
find(u)

```

the first one adds an arrow $u→v$ to the graph, the second one decides if $u↔^\*v$, the last one finds a canonical representative of the equivalence class of $↔^\*$, i.e. a $r(u)$ such that $u↔^\*v$ implies $r(v)=r(u)$.

There is a well-known algorithm using the disjoint-set forest data structure implementing these queries in quasi-constant amortized complexity, namely $O(α(n))$. Note that in this case `equiv` is implemented using `find`.

### More complex variant

Now I'm interested in a more complex problem where the directions do matter:

```
arrow(u, v)
confl(u, v)
find(u)

```

the first adds an arrow $u→v$, the seconds decides if there is a node $w$ reachable from both $u$ and $v$, i.e. $u→^\*←^\*v$. The last one should return an object $r(u)$ such that $u→^\*←^\*v$ implies $r(u) \bullet r(v)$ where $\bullet$ should be easily computable. (In order to, say, computes `confl`). The goal is to find a good data structure such that these operations are fast.

### Cycles

The graph can contain cycles.

I don't know if there is a way to efficiently *and incrementally* compute the strongly connected components, in order to only consider DAGs for the main problem.

Of course I would appreciate a solution for DAGs, too. It would correspond to an incremental computation of the least common ancestor.

### Naive approach

The disjoint-set forest data structure is not helpful here, since it disregards the direction of the edges. Note that $r(u)$ cannot be a single node, in the case the graph is not confluent.

One can define $r(u)=\\{v ∣ u→^\*v\\}$ and to define $\bullet$ as $S\_1\bullet S\_2$ when $S\_1 ∩ S\_2≠∅$. But how to compute this incrementally?

Probably that computing such a big set is not useful, a smaller set should be more interesting, as in the usual union-find algorithm.

# Answer
(**Edit**: completely rewrote my answer now that my understanding of the problem is (I hope) clearer.)

It sounds like this problem can be reduced to incrementally constructing and improving an approximation of the transitive closure of the graph, as the graph is built and searched.

$r(u)$ is, abstractly, the set of all nodes which are reachable from both $u$ and $v$ for every $v \ne u$ in the graph. (Of course, not all $u, v$ pairs will necessarily have a node that can be reached from both of them.) Unlike the case in union-find, this set can't be represented as a canonical representative node in the graph, because there may be nodes that are reachable from both $u$ and $v$, and from both $u$ and $w$, that are nonetheless not reachable from both $v$ and $w$.

Say you maintain, for every $u$, a set of nodes reachable from $u$ (I'll call this $R(u)$). These sets would of necessity be an extra data structure for each node, or at least, a set of extra "shortcut" edges in the graph. If you don't care about retaining the specified structure of the graph, there would be no need to distinguish between these edges and the specified edges.

I don't have any ideas offhand for a data structure that captures this that is more efficient than the general case (e.g. a bit vector or hash table,) but you *can* update these sets incrementally:

Each time you add an edge from $u$ to some other node $v$, you set $R(u) = R(u) \cup R(v)$.

Implement `confl` by first trying $R(u) \cap R(v)$; if that's non-empty, return true. But if it *is* empty, do two parallel breadth-first searches from $R(u)$ and $R(v)$ until you either exhaust both reachable sets or find a node in common. While you do this, also update $R(u)$ and $R(v)$ (and the $R$'s of all the intermediate nodes you find) to include the reachable nodes that you found. ~~and if you do find a node in common, set R(u) = R(v) = R(u) \cup R(v)~~.

`find(u)` just returns $R(u)$. The problem is that `confl` is not implemented purely in terms of `find`. I don't see how it could possibly be unless the algorithm was non-incremental (i.e. pre-compute all the $R$ sets of all nodes with the transitive closure of the graph.) However, the incremental approach should still give you fairly good amortized cost, although I have no idea if it approaches $O(\alpha(n))$ offhand. (It probably doesn't. A false answer from `confl` requires that you start up two BFS'es even when your $R$ sets are saturated; this also seems unavoidable unless the algorithm is made non-incremental.)

This sounds a lot like it might be a special case of La Poutré and van Leeuwen's methods for maintaining transitive closure of a graph.

I realize this doesn't fully answer the question, but perhaps it serves to clarify it, and someone who has more experience with graph algorithms can give a better data structure for encoding the $R$ sets.
> 4 votes

---
Tags: algorithms, graphs, search-algorithms, union-find
---


# Question
Title: Creating artificial NP-Complete problems
Stephen Cook's proof of the NP-completeness of SAT is constructive. Given a Turing machine $M$, one can create a logical formula that is satisfiable if and only if $M$'s computation halts in an accepting state. This suggests that we could take a logical formula and create a Turing machine $M'$ whose computation is described by that formula, thereby creating an artificial problem solved by $M'$. Is it possible to use existing NP-complete problems to create other NP-complete problems? Can this be automated?

# Answer
Dodging any questions about whether this is "interesting" or "artificial" (or whether Computer Science really needs any more NP-complete problems than it already has), the answer is "yes". Pick a structure-preserving mapping between some set of strings and problem instances of 3SAT. Show that the mapping can be computed in polynomial time (i.e., it is a polytime reduction). Then, deciding if a string is in your set of strings is NP-complete. Repeat as desired (the composition of polytime reductions is a polytime reduction.)

If you wanted to automate this process of creating new NP-complete problems, then it would likely be more efficient to construct the mappings from some base set of polytime mappings, using methods known to preserve polynomial time, rather than picking an arbitrary mapping and proving that it is a polytime reduction.

Note that this is not quite what you suggest in your question. You *can* take a logical formula and build a Turing machine corresponding to it, but that in itself doesn't lead to an NP-complete problem. For instance, 2SAT instances can be decided in polynomial time. And a *particular* formula will only correspond to a particular machine, whereas you need a *set* of formulas (or machines) to define a complexity class; so to make new problems in NPC, you really need to show how one set can be converted into another (i.e. a polytime reduction), even if your sets are sets of logical formulas.
> 3 votes

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


# Question
Title: How do we prove that $L_E = \{ \langle A, B \rangle : L(A) = L(B) \}$ is neither regular nor context-free?
Let $A$ and $B$ be two deterministic finite automata. How do we prove that $L\_E = \\{ \langle A, B \rangle : L(A) = L(B) \\}$ is neither regular nor context-free?

Intuitively, I feel that $L\_E$ should not be context-free because we must try each string $\in \Sigma^\*$ (where $\Sigma$ is the alphabet) and check if the string $\in L(A)$ or $\in L(B)$. However, this reasoning sounds informal to me. How do I formalize this proof?

# Answer
> 2 votes
One possible way, is to use the pumping lemma, but one needs to be careful about the details. For simplicity let's discuss only the pumping lemma for regular languages (but I believe a similar method can be used when considering the CFL-pumping lemma).

Let's assume that $\langle A \rangle$ is a well-defined way to encode DFAs, that begins with describing the number of states, then list the transition for each state, etc. Also assume that any string that is not "well formatted" under this encoding just describes a DFA that rejects all words.

Let $n$ be the pumping length.

Let $A=B$ be a $2^n$-state DFA that accepts all words. The encoding of $A$ begins with stating it has $2^n$ states, that is the first part is of length $\log(2^n)=n$ bits at least.

Now let's use the pumping lemma on $w=\langle A,B\rangle$ (which is longer than $n$, so the pumping lemma applies). We can split $w$ into $xyz$ such that $|xy|\le n$, that is, the part we pump "lies" in the part that describes the amount of states in $A$. Now, we pump the word *down*. That is, consider the words $w'=xz$ which should be also in $L\_E$ by the pumping Lemma.

However, we can interpret $w'$ as being $w'=\langle A',B\rangle$ where $A'$ is a *malformed* encoding (it begins with stating the DFA has less then $2^n$ states, but then it describes transitions of $2^n$ states, which is inconsistent with the claimed number of states).

Therefore, by our assumption $L(A')=\emptyset$ while $L(B)=\Sigma^\*$. Thus, $\langle A',B\rangle \notin L\_E$ and we reached a contradiction.

# Answer
> 2 votes
**Nonregularity - trivial way:**

Assuming you encode the pairs as $a \sharp b$ where $a,b$ encode automatas, there are infinitely many Myhill-Nerode classes corresponding to prefixes $a \sharp$. In other words, after reading the $\sharp$ symbol there is an unbounded number of possibilities to remember.

**Nonregularity - by nuke:**

Assume that the first automaton does not accept anything. By taking a quotient, we can assume the input consists only of the second automaton. We are therefore given a graph and have to check whether an accepting state is reachable. This is effectively the graph reachability problem on a bounded degree graph, which is $\mathsf{NL}$-complete and by the space hierarchy theorem not in $\mathsf{DSPACE}(O(1))$, which is known to be the set of regular languages.

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


title: Why is the clique problem NP-complete?

text:
# Question
Title: Why is the clique problem NP-complete?
> **Possible Duplicate:**
> Is the k-clique problem NP-complete?

I've been lately reading about the clique problem, specifically, the variety of the clique problem of deciding whether a given graph $G$ with $n$ nodes has a clique of at least size $k$.

Why is this problem $NP$-complete? Could one solve this problem in polynomial time by trying out each possible group of $k$ nodes in the graph and checking if this group is a clique?

Wouldn't this algorithm run in time $O(\binom{n}{k})$ or $O(\frac{n!}{(n-k)!k!})$ or $O(n^2)$?

# Answer
> 15 votes
The 3-clique problem is, given a graph, does it have a clique of size 3? This is solvable in polynomial time. Likewise, for any fixed $k$, the $k$-clique problem (given a graph, is there a clique of size $k$) is solvable in polynomial time.

But in the clique problem, we are given both the graph and $k$ and asked if there is a clique larger than size $k$. This problem is NP-Complete. For example, let's suppose someone sets $k = \frac{n}{2}$. Then the running time you give is definitely exponential.

This should make intuitive sense -- in the $k$-clique problem, if I fix $k$ to be, say 1000, ($k$ being a constant with respect to $n$.) then as graphs get really really large (like trillions of nodes), I still only have to check every set of 1000 nodes. But in the clique problem, as the graph gets really gigantic, the sets I have to check might get gigantic too.

(*Edit*. To finish answering the question, clique is NP-hard because for example 3SAT can be reduced to it in polynomial time, and clique is in NP. However, $k$-Clique (for any given $k$) is *not* NP-hard).

---
Tags: np-complete
---


title: Does this DFA have a solution?

text:
# Question
Title: Does this DFA have a solution?
I am trying to create a DFA that can recognize strings with alphabet $\\{a,b,c\\}$ where $a$ and $c$ appear even number of times and where $b$ appears odd number of times.

I am wondering that this may only be expressed with other methods such as Turing machine or context-free languages.

You might find it fun to think of the solution.

# Answer
This is doable with a DFA. Hint: We need to keep track of three things simulataneously:

1. The parity of a's (have we seen an odd or even number of a's so far?)
2. The parity of b's
3. The parity of c's

So there are 8 possibilities for what we've seen so far:

1. Even number of a's, even number of b's, even number of c's.
2. Odd number of a's, even number of b's, even number of c's.
3. Even number of a's, odd number of b's, even number of c's.
4. ...

Does that help?
> 5 votes

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


# Question
Title: Count unique increasing subsequences of length 3 in $O(n\log n)$
**Problem**: Given an array of $n$ integers, $A\[1 \dots n\]$, such that any integer occurs *at most* 2 times in the array, we have to find the number of *unique* increasing subsequences of length 3 (duplicate subsequences must be counted only once). In other words, we have to count the number of unique integers $A\[i\], A\[j\], A\[k\]$ such that $A\[i\] \< A\[j\] \< A\[k\]$ with $i \< j \< k$.

I have been stuck on this for quite a while now. I did look up this question which tests for the existence of such a triplet. But I think my question is different because it needs the count, and because it needs unique triplets (upto 1 repetition of any number is allowed).

**Idea:** $O(n^2)$ algorithm. For each number, we can scan the remaining array and find out how many unique numbers are greater than it and occur after it. This can be done in $O(n^2)$ by naive brute force. For every pair of numbers ($O(n^2)$), we now have the number of possible triplets that can be formed by using the pair as the first two numbers of the triplet (since we know how many are greater than the second number).

Unfortunately, $O(n^2)$ is too slow, and I need a faster solution - $O(n\log n)$ or $O(n)$. Space complexity also has to be sub-quadratic. I was thinking along the lines of sorting a copy of the array to find out the relative rank of each element, but could not go any further. Any help or hints are greatly appreciated!

# Answer
Here is an algorithm to count distinct subsequences of length $3$ in time $O(n \log n)$, regardless of how many times any value $a$ occurs in $A\[j\]$.

First, create a binary search tree $T$ containing all possible values $a = A\[j\]$, storing at each node how many times it occurs in $A$, and how many nodes there are which follow it in the tree (are further to the right) representing larger values $A\[k\]$. Note that with each insertion (and later, removals), the tally of further-right values will become out of date for many of the nodes. However, we can maintain these values for each node lazily, by maintaining at each parent node a count of the pending counter updates for its left and right subtrees. (When we later traverse to a child node, its own counter of larger elements, and its pending-update counters for its children can be adjusted by the amount indicated by its parent.) Similarly, any insertions or removals in the right subtree of a node leads to a pending update for the left subtree. This should also be implementable for balanced trees as well, such as AVL trees or red-black trees. We will henceforth suppose that as we traverse any particular node that its counter is thereby kept up-to-date, though it may become out of date in between visitations. Constructing $T$ takes time $O(n \log n)$.

We traverse $A$ once more, creating a tree $F$ which also contains values $a = A\[j\]$ and the number of nodes to the *left* of each node, similarly to $T$. (We also maintain a separate counter at each node of $F$ of how many nodes have been added to its left since the last time we look up the node in the tree; this uses a similar update method as the total-counter, though because we would clear this counter each time the node is visited, in practise we just use the pending-update value for its parent node.) At the same time we will be *disassembling* the tree $T$, and counting distinct increasing subsequences in $A$ of length 3 by considering, using $F$ and $T$, how many different values of $a'$ and $a''$ can serve as the *first* and respectively *third* value in an ordered triple $(a',A\[j\],a'')$. We do this as follows.

Set $N := 0$. For each $1 \leqslant j \leqslant n$ in order, do the following:

* Let $a := A\[j\]$. Decrement the occurance counter of $a$ in $T$. This takes time $O(\log n)$.
* Search for $a$ in $F$. If it is not present, insert it, and set $$\text{incr} := \\#(\text{nodes left of $a$ in $F$}) \cdot \\#(\text{nodes right of $a$ in $L$}).$$ Otherwise, if $a$ is already present, set $$\text{incr} := \\#(\mathop{\*}\text{newly added}\mathop{\*} \text{ nodes left of $a$ in $F$}) \cdot \\#(\text{nodes right of $a$ in $L$}).$$ This takes time $O(\log n)$ as well.
* Add $\text{incr}$ to $N$.
* If the occurances counter of $a$ in $T$ has dropped to $0$, remove $a$ from $T$. This takes time $O(\log n)$.

\[*Edited to add*: as Peter Shor notes in the comments, rather than storing in $T$ the number of times $a$ occurs in $A$, we can simply store the last index $1 \leqslant j \leqslant n$ such that $a = A\[j\]$ for the purposes of this algorithm. Then, rather than actually removing $a$ from $T$, we can just perform the decrement of the further-right tallies for all of the nodes to its left. The decrease in arithmetic and tree-modification operations would give rise to some modest savings in run-time.\]

The total run-time of this algorithm is $O(n \log n)$. In each iteration of the loop above, we only count the number of ways in which *elements smaller than $a$ which haven't been used yet as a subsequence starter* can be combined with *elements larger than $a$ which still have at least one occurance later in the list*, with $a$ itself in the middle. Thus, we count the number of "newly possible" subsequences there are for each $A\[j\]$ as new first elements are made available for each remaining available third element, and accumulating them for $1 \leqslant j \leqslant n$.
> 7 votes

---
Tags: algorithms, arrays, subsequences
---


# Question
Title: Mean number of edges between two equal partitions
For a random undirected graph with $n$ nodes, where each node has $k$ incident edges ($nk/2$ edges in total), the vertex set is partitioned into two sets each having $n/2$ nodes.

> What is the order of the number of edges that start in one partition and end in the other?

My back of the napkin calculation is half of total number of edges, $nk/4$. If I place randomly an edge it has $1/4$ chance of having both ends in one partition, $1/4$ chance of having both ends in the other partition and $1/2$ chance of having the ends in both. I find it surprising that it could be half.

# Answer
Your thinking is correct. To verify your claim you can check this lecture notes on the probabilistic method by Matousek and Vondrak. More specifically check the proof of **Theorem 3.3.1** stating that any graph with $m$ edges contains a bipartite subgraph with $\frac{m}{2}$ edges.
> 4 votes

---
Tags: graphs, random-graphs
---


title: B-tree branching factor boundaries

text:
# Question
Title: B-tree branching factor boundaries
A BTree has a $k$ value that determines that every node has $k$ to $2k$ children. When a node has $2k$ keys it needs to be split into two nodes.

Let's say I want to create a $k/(2k-x)$ tree. (like a 2-3 tree that follows the BTree rules, but isnt $k/2k$)

What is the possible range of $x$? The tree must follow the behavior of a BTree, meaning it needs to hold keys and split accordingly.

# Answer
More exactly, a B tree has an $m$ value such that the number of children is between $\lceil\frac m2\rceil$ and $m$ children. That differs from your numbers for odd $m$. For $m=3$ the bounds are $2$ and $3$, which is the 2-3-tree you refer to.

As far as I know (I tried this several years ago) these numbers are the smallest interval for which the split and merge operations can work. You can try yourself. If a node has $m$ children, I can add $1$ and the node must be halved. Thus this satisfy the $\lceil\frac m2\rceil$ bound? Check for $m$ odd and even separately.
> 3 votes

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


# Question
Title: Implications of polynomial time reductions
I'm reviewing for finals and have a sample problem that I **think** I understand, but would like someone to bless my understanding or smack me and tell me why I'm wrong.

I'm presented with a problem $\Pi$ of unknown complexity class. If I can transform $\Pi$ to some problem $X$, where $X \in {\sf P}$, what does that tell me about $\Pi$?

I think allows me to conclude that $\Pi \in {\sf P}$, right? If I can reduce $\Pi$ to another problem that's deterministically solvable in polynomial time, and the transformation itself can be done "easily" in polynomial time, then I can conclude that $\Pi$ is deterministically solvable in polynomial time, and therefore that $\Pi \in {\sf P}$ correct?

Conversely, given the same input, transforming $X$ to $\Pi$ in polynomial time allows me to conclude nothing meaningful, since nothing is known about $\Pi$ right?

# Answer
> 3 votes
In essence, you are right. Given a problem $\Pi$, if you can find a poly-time reduction from $\Pi$ to any problem $x\in P$, then you have proof that $\Pi\in P$ as well.

A reduction from problem $A$ to $B$ is basically a function that transforms any input of $A$ into an input of $B$, such that the solutions agree. That means, you can use any algorithm for $B$ to solve $A$.

For the second part, if you can reduce a problem $x\in P$ to $\Pi$, then $\Pi$ might be in $P$, or not. However, if you can find a way to reduce *all* problems in $P$ (or equivalently, *some* $P$-complete problem), then you have shown that $\Pi$ is $P$-hard.

# Answer
> 4 votes
Right, if you have an algorithm A that reduces $\Pi$ to $x$ in polytime, and you can solve $x$ is polytime using some algorithm B, then you can solve $\Pi$ in polytime by applying first A and then B.

Using polytime reductions on a problem in P however is rather boring, since you can solve the instance during the reduction and map every instance of $x$ to either a trivial yes or a trivial no answer. Normally you restrict yourself to logspace reductions for problems from P.

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


title: Running Time of Modular Exponentiation

text:
# Question
Title: Running Time of Modular Exponentiation
I am trying to understand why the modular exponentiation algorithm has a running time of about $\log(n)$ where $n$ is the exponent. Here is the algorithm:

```
function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

```

I think it has something to do with the number of bits for the binary representation of the exponent. What is also an intuitive numerical example?

# Answer
> 6 votes
The main idea is that $a^x \cdot a^x = a^{2x}$.

Now, in order to get, say, $a^{10}$ you can do $res = res * a$ for 10 times. On the other hand you can do compute $a^2=a\cdot a$, then $a^4=a^2\cdot a^2$, then $a^8 = a^4 \cdot a^4$, and get the final result by multiplying $a^8$ with $a^2$. That is, we "break" the computation in a similar way to the binary representation of the exponent.

Let me give do the example in more details, and then give the general statement. note that $10 = 1010\_{(2)}$, and can think of each '1' bit as an element we need to multiply in order to get the final answer (here $a^8$ for the 4th bit, and $a^2$ for the 2nd lsb bit. The power is the same as the "value" of that bit in binary..).

Generaly, in order to compute $a^{exp}$, consider $exp\_{(2)}$: the MSB is always 1, and you will have to compute the element $a^{2^{\lfloor \log exp \rfloor}}$, which will take you $\log exp$ (modular) multiplications, and generate $a^2, a^4, a^8, a^{16}, ..., a^{2^{\lfloor \log exp \rfloor}}$. Finally, with another up to $\log exp$ multiplication you will multiply all the elements that correspond to a '1' bit in the binary representation of $exp$.

---
Tags: algorithms
---


# Question
Title: Mental poker: proving dealt hand is fair
I have just read mental poker, described in this fascinating paper(PDF) by cryptographic greats Adi Shamir, Ron Rivest, and Leonard Adleman.

Assuming I have a website, (TTP) how can I prove to the player that the hand dealt to him is fair? Most importantly how can I prove that I didn't bruteforce until an unfair hand is dealt to him to gain house edge, are there any C# implentations of such code?

# Answer
I found out you can prove a hand is fair with the following method:

Every user has a randomly generated "secret" in an input field he can personally edit, before each card is picked all the secrets are sent to the server and hashed seperately, then all the secrets are hashed into a single hash which is used as a seed for the random functions.

Then all the players hashes are sent to every player and being displayed on that players screen, when it is safe, every player is also shown all the other players secret phrases this way: A) Every player knows that the secrets weren't changed after the game since they have the hashes B) It is impossible for them to find the secrets and get an unfair advantage before it is safe to reveal the secrets C) They can now know that every card is dealt fairly
> 1 votes

---
Tags: probability-theory, cryptography, board-games
---


# Question
Title: How to find recurrences where Master formula cannot be applied
Given: $T(n) = T(\sqrt{n}) + 1$ (base case $T(x) = 1$ for $x\<=2$)

How do you solve such a recurrence?

# Answer
> 7 votes
For the recurrence, $$ T(n) = T(\sqrt{n}) + 1 $$ Let $n = 2^{2^{k}}$, therefore we can write the recurrence as:

$$ T(2^{2^{k}}) = T(2^{2^{k-1}}) + 1 \\ T(2^{2^{k-1}}) = T(2^{2^{k-2}}) + 1 \\\ldots\\\\\ldots\\ T(2^{2^{k-k}}) = 1 $$

, i.e. $ k * O(1) $ work or linear in $k$. We can express $k$ in terms of $n$: $$ \log{n} = 2^{k} \\ \log{\log{n}} = k $$

Hence, the recurrence solves $T(n) = O(\log{\log{n}}) $

---
Tags: complexity-theory, algorithms
---


title: Distributed 6-color Vertex Coloring

text:
# Question
Title: Distributed 6-color Vertex Coloring
I am trying to understand the distributed 6-color algorithm for vertex coloring (on page 10).

Here is a short description

Idea of the algorithm: We start with color labels that have $\log n$ bits. In each synchronous round we compute a new label with exponentially smaller size than the previous label, still guaranteed to have a valid vertex coloring.

Let $i$ be the smallest index where $c\_v$ and $c\_p$ differ; the new label is $i$ (as a bitstring) followed by the bit $c\_v(i)$ itself

```
Grand-parent 0010110000 -> 10010 -> …
Parent       1010010000 -> 01010 -> 111
Child        0110010000 -> 10001 -> 001

```

The problem I cannot understand this example. Let's take Grand-parent($c\_p$ = 0010110000) and parent($c\_v$ = 1010010000), on the round when $c\_v$ receives $c\_p$, so we need to change $c\_v$. They differ in 5th bit, counting from 0 (5 in binary is 101), so according to definition, $c\_p$ is "$101$"+$c\_p\[5\]=1010$, but in example it's 01010, what I get wrong?

# Answer
The labels $c\_v$ and $c\_p$ are relative. So when a node (parent in your example) having $c\_v = 1010010000$ receives from its parent (grandparent in your example) an id $c\_p = 0010110000$, the difference, as you correctly point out, is in the fifth position.

Now, the total number of bits in the original ids is 10, so representing any index (0-9) will require 4 bits. So, the new id will have 4 bits from the position difference + 1 bit for the differing bit. Now, $$(5)\_{10} = (0101)\_2$$

Note, we use 4 bits as discussed above, so that all new ids, can have the same number of bits. Then, $c\_v(5) = 0$ is concatenated towards the LSB side, giving the new id: $01010$.
> 7 votes

---
Tags: algorithms, distributed-systems, colorings
---


# Question
Title: If P = NP, why wouldn't $\emptyset$ and $\Sigma^*$ be NP-complete?
Apparently, if ${\sf P}={\sf NP}$, all languages in ${\sf P}$ except for $\emptyset$ and $\Sigma^\*$ would be ${\sf NP}$-complete.

Why these two languages in particular? Can't we reduce any other language in ${\sf P}$ to them by outputting them when accepting or not accepting?

# Answer
As there are no strings in $\emptyset$, any machine that computes it always rejects, so we can't map Yes-instance of other problems to anything. Similarly for $\Sigma^{\ast}$ there's nothing to map No-instances to.
> 28 votes

# Answer
You need a polynomial reduction from the problem $A$ to the problem $B$ if you want to prove that $B$ is "harder" than $A$. We build a polynomial reduction by transforming any instance $x$ of $A$ into an instance $f(x)$ of $B$ such that $x∈A$ iff $f(x)∈B$.

The function $f$ must and can be polynomial. If $\mathsf{P}=\mathsf{NP}$ and $A$ is a NP problem, then $f$ can itself solve the problem $A$ of the problem and embed any $x∈A$ into some element $y$ of $B$ and any $x\notin A$ into some element $z$ that is not in $B$.

If $B$ is either $∅$ or $Σ^\*$ then $y$ or $z$ cannot exist, otherwise the reasoning above shows that $B$ is harder than $A$.
> 5 votes

# Answer
Just a note: the previous answers are ok, however you're not too far from the correct trivial reduction:

if $\sf{P} = \sf{NP}$ then any $L \in \sf{NP}$ is Karp reducible to the language $\\{1\\}$ (just map in polynomial time every $x \in L$ to 1, every $x \notin L$ to 0), which is trivially a sparse language

The converse direction: "if an $\sf{NP}$ complete language is Karp reducible to a sparse set then $\sf{P}=\sf{NP}$" is certainly more interesting and it is known as the Mahaney's theorem:

Let $c$ be a constant and $A$ be set such that for all $n$, $A$ has at most $n^c$ strings of length $n$. If $A$ is $\sf{NP}$-complete then $\sf{P}=\sf{NP}$.
> 4 votes

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


title: Coloring a Unicyclic Graph

text:
# Question
Title: Coloring a Unicyclic Graph
I am trying to design an efficienct algorithm to color a unicyclic graph. I know if a graph does not contain any cycles (it's a tree) then it is 2-colorable. But cycles are either 2 (is even number of vertices) or 3 (is odd number of vertices) colorable. So if there contains just one cycle then the chromatic number of this unicyclic graph should be 3 (if the cycle contains an odd number of vertices).

So enough of that. on to the algorithm.

I would start at a vertex and color it color1. Now I would perform a BSF from the originator. Then each vertex that is adjacent to the originator vertex i would color it color 2, and continue this process of switching from color1 to color 2 unless if one of the vertices has an adjacent vertex that is already colored the same color. That means i found the cycle and will color that vertex color 3. If it had an adajcent vertex that was a different color than what i was going to color it then its an even number cycle and it would be 2-colorable.

So that means, each step of the BFS I would check each vertex adjacent to the vertex selected for that step of the BFS. Therefore $O(|E|)$?

is there a more efficient algorithm to color a unicyclic graph and is my time complexity correct?

# Answer
> 5 votes
**Yes**, your algorithm is correct. The maximum number of edges that a graph can have without forming a cycle is when it is a tree. Lesser number of edges is only when the graph is disconnected. We will assume that the graph is connected, without loss of generality. In such a case, there would be $|V| - 1$ edges in the graph. Any other edge will create one cycle. So, any connected graph with exactly one cycle will have $|V|$ edges.

In such a case, you are right in doing a BFS to color alternatively the nodes alternatively. What you are doing is essentially starting from a root, and all nodes at odd depth have a different color than the root, and all nodes at an even depth have the same color as the root. If you encounter any node which has 2 colored neighbours (parent is always colored, but one of the children is also colored), then you have found a cycle. As you rightly note, if the second vertex is of a different colour than what you planned, it is an even cycle, and you can just go ahead - you will get a 2-coloring. Otherwise, just assign this vertex the third color, and go on with the alternating between two colors for the rest. This gives a 3-coloring.

As for the complexity, you are doing one BFS, checking for colored neighbors while putting them in the queue. Thus, complexity is $O(|V| + |E|)$, as you are visiting every edge and vertex once. However, since $|E| = |V|$, the overall complexity is $O(|V|)$. To color $|V|$ vertices, you need at least $\Omega(|V|)$ time, and so the algorithm is **asymptotically optimal** (no asymptotically faster algorithm is possible). This algorithm is $\Theta(|V|)$.

---
Tags: graphs
---


# Question
Title: Are Turing-recognizable languages closed under intersection?
Let $A$ and $B$ be Turing-recognizable languages. Must language $C = A \cap B$ be Turing-recognizable too?

I have a hunch that it should be because we can construct an enumerator for $C$ by enumerating all the languages in $A$ and then all the languages in $B$.

However, I also know that Turing-recognizable languages are not closed under complement, and $\overline{\bar{A} \cup \bar{B}} = A \cap B = C$, which seems to suggest that Turing-recognizable languages are not closed under intersection.

There is clearly a contradiction somewhere in my reasoning. Where is it?

# Answer
> 5 votes
Indeed, the recursively enumerable languages are closed under union and intersection, but not complement. This is not a contradiction: the formula $A \cap B = \overline{\overline{A} \cup \overline{B}}$ tells that a class closed under union and complement is closed under intersection, but does not tell anything otherwise.

A similar example: the set of finite subsets of $\mathbb N$ is clearly closed under union and intersection, but not complement.

---
Tags: formal-languages
---


# Question
Title: Why does absence of strongly polynomial time algorithm for LP imply restriction to rational instances?
From Bernhard Korte, Jens Vygen, Combinatorial Optimization,

> Instances of LINEAR PROGRAMMING are vectors and matrices. Since no **strongly polynomial-time** algorithm for LINEAR PROGRAMMING is known we have to restrict attention to **rational instances** when analyzing the running time of algorithms.

I was wondering why does the absence of strongly polynomial time algorithms for linear programming imply restriction to rational instances?

# Answer
> 3 votes
A *strongly polynomial algorithm* in the context of linear programming probably means an algorithm in the arithmetic model (where numbers can be added, multiplied, compared and so on), whose running time does not depend on the magnitudes of the numbers involved. Such an algorithm could be applied directly for real numbers. Examples of algorithms of this type are the simplex algorithm and the criss-cross algorithm, both really a collection of related algorithms. However, variants of these algorithm are either known not to be polynomial-time, or (in some cases) not known and not expected to be polynomial-time.

Other algorithms for linear programming exist: the ellipsoid algorithm and the interior-point algorithm (again, there are really many variants of these algorithms). The number of iterations in each case depends on the precision needed to guarantee reaching an optimal solution, and that's why they are not strongly polynomial. While these algorithms can also be implemented in the arithmetic model, convergence is no longer guaranteed to take polynomial time.

When the inputs are rational numbers, then the number of iterations needed to converge is polynomial in the length of the input, and therefore these algorithms become polynomial-time.

---
Tags: complexity-theory, linear-programming
---


# Question
Title: Propositional formula in DNF can be decided in polynomial time?
For a given propositional formula f in DNF, one can decide in polynomial time, if the formula is satisfiable: Just walk through all subformulas (l\_1 and ... and l\_k) and check, wheter it has NO complementary pair of literals. Formula f is satisfiable iff such subformula exists.

Is my approach above correct ?

If yes, I'm wondering why all modern SAT solvers get a CNF as input format, and don't just use DNF.

# Answer
The conversion from CNF to DNF can come at an exponential cost. For example $(a\_1 \lor b\_1) \land \cdots \land (a\_n \lor b\_n)$ expands to $2^n$ many terms. As you comment, for DNF satisfiability is easy - it is falsifiability which is hard. If the problem is trivial, you don't input it to a SAT solver, and that's why SAT solvers accept CNFs instead of DNFs.

If you believe that P is different from NP, then this implies that there is no polynomial time way to convert CNF satisfiability to DNF satisfiability, since the former is NP-complete while the latter is in P.
> 10 votes

---
Tags: logic, polynomial-time
---


# Question
Title: Why is $L = \{ \langle M \rangle : L(M) = \{ \langle M \rangle \} \}$ not Turing-recognizable?
In other words, $L$ is the language of Turing machines that recognize the language consisting of only themselves.

Why is $L$ not Turing-recognizable? $L$ is clearly not decidable by Rice's Theorem, but how do I go one step further and also prove that no machine can enumerate $L$?

# Answer
Given a Turing machine $T$, use the recursion theorem to construct a Turing machine $T'$ that halts if its input $x$ is $\langle T' \rangle$, runs $T$ on $x$ if $x \< \langle T' \rangle$, and runs $T$ on $x-1$ if $x \> \langle T' \rangle$. If you could recursively enumerate $L$, then you could use this reduction to recursively enumerate all machines that never halt.
> 5 votes

---
Tags: formal-languages
---


title: Asymptotic Analysis for two variables?

text:
# Question
Title: Asymptotic Analysis for two variables?
How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables?

I know that the Wikipedia article has a section on it, but it uses a lot of mathematical notation which I am unfamiliar with it. I also found the following paper: http://people.cis.ksu.edu/~rhowell/asymptotic.pdf However the paper is very long and provides a complete analysis of asymptotic analysis rather than just giving a definition. Again the frequent usage of mathematical notation made it very hard to understand.

Could someone provide a definition of asymptotic analysis *without* the complex mathematical notation?

# Answer
Asymptotic notation for multivariable functions is defined analogously to its single variable counterpart. In the single variable case, we say that $f(n) \in O(g(n))$ if and only if there exists constants $C,N$ such that for all $n \> N$ we have $f(n) \leq Cg(n)$. In other words $f(n)$ is upper bounded by some multiple of $g(n)$ for all $n$ larger than some fixed $N$.

In the multivariate case, the definition is nearly the same, except you have a few more variables to worry about. Let's suppose $f(n,m)$ is a function of two variables. We want to bound $f$ from above by another function of two variables. So we say that $f(n,m) \in O(g(n,m))$ if and only if there exists constants $C,N$ such that for all $n\>N$ and $m\>N$ we have $f(n,m) \leq Cg(n,m)$. The definition is nearly exactly the same, except now all of our variables must be greater than our fixed constant $N$.

The wikipedia article used $\overrightarrow{x}$ to mean a vector in $\mathbb{R}^d$ which would mean that $f$ and $g$ were multivariable functions of $d$ variables (i.e. $f,g:\mathbb{R}^d \rightarrow \mathbb{R}$). Saying that $x\_i \> N$ for all $i$ meant that each component of $\overrightarrow{x}$ had to be greater than $N$.
> 10 votes

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


# Question
Title: Models of computation: the arithmetic model, Turing machine (and ...)
1. How is an arithmetic model defined?

What relations are between it and Turing machine? Are they equivalent in some sense?

Is it true that

* in the arithmetic model of computation, the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a constant unit time step to perform, regardless of the sizes of the operands.
    * in the Turing machine, the time each operation takes will depends on the storage size of the operands?

What is the point of having these two different computational models?
2. Are there other models of computation distinct from the Turing machine and the arithmetic model?
3. There are algorithms which run in polynomial time in the Turing machine model, but not in the arithmetic model. The Euclidean algorithm for computing the greatest common divisor of two integers is one example.

If an algorithm runs in polynomial time in the Turing machine, will it run in polynomial time in the arithmetic model?
4. Is an algorithm running in polynomial storage space defined the same under the Turing machine and the arithmetic model?

Thanks and regards!

# Answer
> 10 votes
*3. There are algorithms which run in polynomial time in the Turing machine model, but not in the arithmetic model. The Euclidean algorithm for computing the greatest common divisor of two integers is one example. If an algorithm runs in polynomial time in the Turing machine, will it run in polynomial time in the arithmetic model?*

Polynomial TM running time does not imply polynomial arithmetic running time, nor vice-a-versa.

The issue in the above question lies in the definition of the *running time* that we are trying to bound. If we expand, we have to say: "...runs (or doesn't run) in the number of steps that is polynomial in the length of encoded input". The catch is that the "steps" and "length of encoded input" are defined differently for the two models.

* For a Turing Machine, the encoded input is taken as some concatenation of the binary representations of the input integers with separators. A step is an action of the TM head.
* For an arithmetic model, the length of encoded input is defined as the number of numbers occurring in the input. A step is an arithmetic operation.

**1. "Polynomial time under TM, but not under AM"**

Euclid's GCD is indeed an example. For $a,b, a\>b$, input integers, regardless of the model the algorithm takes $O(\log b)$ iterations, with a division at each iteration.

* TM: Length of encoded input is then $l\_{TM} = 2\log a + 1$ where $a$ is the larger of the two integers. The division in a TM takes $O(\log^2 a)$ steps. Hence, the total number of TM steps is $O(\log^2 a\log b)=O(l\_{TM}^3)$ (conservatively speaking). That is, the polynomial $P\_{TM}(l\_{TM})=l\_{TM}^3$ in the length of encoded input bounds the TM running time.
* AM: Length of encoded input is constant $l\_{AM}=2$. The number of steps is equal to the number of divisions $O(\log b)$. Since the value of any polynomial $P(l\_{AM})$ is constant, for any choice of $P(l\_{AM})$ we can always find a problem instance that takes more divisions than $P(l\_{AM})$. That is, we cannot bound the running time with a polynomial in the length of encoded input.

**2. "Polynomial time under AM, but not under TM"**

One example is the algorithm that computes $2^{2^n}$ using repeated-squaring where $n$ is given as input in unary encoding (and we treat each unary "tick" as an input number). For both models, input length is $n$ and we need $\log 2^n = n$ multiplications and each multiplication will eventually be multiplying $2^n$-bit numbers.

* AM: $P(n)=n$ is a polynomial bound on the number of arithmetic operations
* TM: $O(n2^{2n})$ steps, since each $2^n$-bit multiplication takes $O(2^{2n})$

Drawn from a reading of Wikipedia's primary source (and corrected Wikipedia accordingly):

\[1\] Grötschel, Martin; László Lovász, Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.

# Answer
> 8 votes
*2. Are there other models of computation distinct from the Turing machine and the arithmetic model?*

* Tag-systems (and their variations: 2-tag systems, cyclic tag systems, bi-tag systems)

All those models are Turing complete (and can simulate a Turing machine with only polynomial time slowdown). A lot of information can be found in Turlough Neary's thesis "Small universal Turing Machines"

---
Tags: complexity-theory, computation-models
---