title: Multi-line fitting problem

text:
# Question
Title: Multi-line fitting problem
Given a set of `n` points, and a number `k` decide whether there exist `k` straight lines such that all of the points are covered. Here a point is *covered* by a line if that point lies on that line.

I can formulate an ILP for the same. The problem seems to be hard. I want to formally prove its NP-Completeness.

Note that, for `k=1`, the problem is in P. Simply find the liner regression/line fitting and test whether the error is zero. Even when `k=2`, the problem still seems to be hard. Is it really so? And what about the general case? What are the candidate problems for the reduction?

# Answer
The general case of this problem is NP-complete, as shown by Meggido and Tamir \[N. Megiddo and A. Tamir. *On the complexity of locating linear facilities in the plane.* Oper. Res. Lett., 1:194–197, 1982.\]. Their reduction is from 3SAT, in the usual way: some points in the construction represent clauses, others variables, which are all carefully arranged together with some additional points such that the relation between clauses and variables in 3SAT is represented in the instance. I suggest you read the paper for more details.

Note that if $k$ is constant the problem can be solved in polynomial time: we only need to consider the lines that contain at least two of our points, of which there are $O(n^2)$. So, there are only $O( {n^2 \choose k})=O(n^{2k})$ sets of lines we need to test, which can be done in $O(n)$ time for each set, giving an algorithm that takes $O(n^{2k+1})$ time in total.

While the brute-force approach above is already polynomial for a constant $k$, there are better algorithms. In fact, this problem is fixed parameter tractable in $k$: Afshani et al. give an algorithm with a $O^\*((Ck/\log k)^{k})$ time algorithm, where $C$ is some constant and the $O^\*(\cdot)$ notation ignores polynomial factors. However, this particular algorithm may not be very practical. Depending on the application, formulating this problem as an ILP or set cover instance can be more efficient.
> 6 votes

# Answer
Consider all pairs of points in turn and detect all those that are collinear with them. This takes time $O(n^3)$ and will generate up to $\dfrac{(n-1)n}2$ subsets. This reduces the question to a set cover decision problem.

---

For $k=2$, an easy solution in $O(n)$ is given by @JohnL: Pick $3$ points. One of the lines must cover $2$ of them. Check if the remaining $n−2$ points are collinear. (More precisely $n-m$, removing all points collinear with the first two.)
> 4 votes

# Answer
As pointed out in this answer, the problem is hard. Moreover the problem is infact APX-hard (see here). Also, the problem is commonly known as the point-line-cover (PLC) in the literature.

This does infact provide an interesting insight by showing an easy reduction to set-cover problem which is well studied and have a simple simple greedy algorithm that has a $\log n$ approximation factor (see here) or a factor $f$ where $f$ is frequecy of an element in the subsets (see here).

A practical approach for problem can be as follows: apply one of the approximation schemes mentioned above, let us call it $\mathcal{A}$. Let $k'$ be the number of subsets returned by $\mathcal{A}$. If our input $k$ for the set-cover decision problem with $k \ge k'$, we return 'yes'. While if $k\log n \< k'$ return 'no'. Otherwise we apply brute-force or some FPT scheme mentioned here.
> 1 votes

---
Tags: np-complete, computational-geometry
---


# Question
Title: Computing the error bound of floating-point expression
How should I compute the maximum absolute and relative error of the following IEEE-754 floating-point expression?

```
a.y + (x - a.x) * ((b.y - a.y) / (b.x - a.x))

```

Also, we assume, that

* the optimizer leaves the expression in the specified form
* the default rounding mode (round to nearest even)

# Answer
IEEE 754 gives you the maximum relative error of each operation. You have three differences with a maximum relative error each. Multiplication and division adds the maximum relative error of each operand, plus the maximum relative error of the multiplication and division.

Then you have a final addition. If the right hand side is very close to the negative of the left hand side of the "+" then the relative error is unlimited. You'd need to analyse how close to -a.y the right hand side can be.

For absolute error, you convert the relative error of the right hand side into an absolute error.
> 0 votes

# Answer
Let the absolute errors on all variables be equal to $\delta$.

The absolute errors on the differences are $2\delta$ and the relative errors on the second term is

$$\frac{2\delta}{x-a\_x}+\frac{2\delta}{b\_y-a\_y}+\frac{2\delta}{b\_x-a\_x}$$

So the final absolute error,

$$\delta\left(1+2\frac{(x-a\_x)(b\_y-a\_y)}{b\_x-a\_x}\left(\frac1{x-a\_x}+\frac1{b\_y-a\_y}+\frac1{b\_x-a\_x}\right)\right)$$

or

$$\delta\left(1+2\left(\frac{b\_y-a\_y}{b\_x-a\_x}+\frac{x-a\_x}{b\_x-a\_x}+\frac{b\_y-a\_y}{b\_x-a\_x}\frac{x-a\_x}{b\_x-a\_x}\right)\right)$$
> 0 votes

---
Tags: floating-point, error-estimation
---


# Question
Title: Assignment problem with maximal partitioning
Recently I came across a problem I don't get may hands on:

Given p binary positions.

Let s be the number of "set-bits" (1 \< s \< p * 2^(p-1) - 1).

I need the maximal set of assigments that alltogether set s bits.

Example: p = 3, s = 8. ==\> A "maximal" set: {(0,0,1), (0,1,0), (1,1,0), (0,1,1), (1,0,1)}

At the whole 8 bits are set.

"Maximal": There is no other set with 8 bits set, that has more than 5 elements.

What I need is an algorithmic way to construct a maximal set.

Apart from that: get the number of elements of the maximal set without constructing it.

Any ideas appreciated!

NB: The problem is from partitioning a set most evenly.

The limits for s:

0 and p * 2^(p-1) are trivial, greater is handled by inverted symmetric.

# Answer
> 0 votes
You can greedily add elements from least bits set to most until you have more than $s$ total bits and then remove one of the elements (based on their number of set bits) to fix it.

To only count the number of elements you can sum $ \binom{p}1 + 2\binom p 2 + 3\binom p 3 + ...$ until it is greater than $s$, then figure out (using division) how many elements of the greatest bit count you need to remove to get a number less than $s$. If you find that to be $x$ $k$-weight elements the answer would be $\binom p 0 + \binom p 1 + ... + \binom p k - x$.

---
Tags: algorithms, optimization, sets, assignment-problem
---


# Question
Title: The value of $r$, with $r≤ b$, that minimizes the expression $(b/r)(n+2^r)$ in the analysis of the radix-sort algorithm
In chapter 8 of the book "*Introduction to Algorithms*" by Cormen, Leiserson, Rivest, and Stein, lemma 8.4 is proved. (my question is after the proof of the lemma)

> Given $n$ $b$-bit numbers and any positive integer $r≤b$, RADIX-SORT correctly sorts these numbers in $Θ((b/r)(n+2^r))$ time if the stable sort it uses takes $Θ(n+k)$ time for inputs in the range $0$ to $k$.
>
> Proof:
>
> For a value $r≤b$, we view each key as having $d=⌈b/r⌉$ digits of $r$ bits each. Each digit is an integer in the range $0$ to $2^r-1$, so that we can use counting sort with $k = 2^r-1$. (For example, we can view a 32-bit word as having four 8-bit digits, so that $b = 32$, $r=8$, $k = 2^r-1 = 255$, and $d = b/r = 4$.) Each pass of counting sort takes time $Θ(n+k)=Θ(n+2^r)$ and there are $d$ passes, for a total running time of $Θ(d(n+2^r))= Θ((b/r)(n+2^r)).$

goes on... and in this part I will ask my question. In the quote I will mark the points of the question.

> For given values of $n$ and $b$, we wish to choose the value of $r$, with $r ≤ b$, that minimizes the expression $(b/r)(n+2^r)$. If $b \< ⌊\lg n⌋$ **(question : what is the motivation that led to the choice of this inequality?)**, then for any value of $r \leq b$, we have that $(n+2^r)=Θ(n)$. Thus, choosing $r = b$ yields a running time of $(b/b)(n+2^r)=Θ(n)$, which is asymptotically optimal. If $b \geq ⌊\lg n⌋$, then choosing $r= ⌊\lg n⌋$ gives the best time to within a constant factor, which we can see as follows. Choosing $r = ⌊\lg n⌋$ nc yields a running time of $Θ(bn(\lg n)$. As we increase $r$ above $⌊\lg n⌋$, the $2^r$ term in the numerator increases faster than the $r$ term in the denominator, and so increasing $r$ above $⌊\lg n⌋$ yields a running time of $Ω(bn/\lg n)$. If instead we were to decrease $r$ below $⌊\lg n⌋$, then the $b/r$ term increases and the $n+2^r$ term remains at $\Theta(n)$.

# Answer
For fixed $n$, let $f(r)=(b/r)(n+2^r)$ where $r\>0$.

Since $f(r)\>(b/r)n$, $\ f(0^+)=\infty$.
Since $f(r)\>(b/r)2^r$, $\ f(\infty)=\infty.$ Hence there exists $m$ such that $f(r)$ reaches its global minimum at $r=m$. By the extreme value theorem, we have $$f'(m)=0,$$ which means $-\frac b{m^2}(n+2^m)+\frac bm(2^m\log\_e2)=0$. $$n=2^m(m\log\_e2-1).$$

---

What we are interested in is what happens when $n$ goes to infinity. So we consider $m$ as a function of $n$ that is determined by the equation above.

As $n$ goes to infinity, we see that $m$ must go to infinity as well. Taking $\log\_2(\cdot)$ of both sides, we get $$\log\_2n=m +\log\_2(m\log\_e2-1).$$ Since $\lim\_{m\to\infty}\frac{\log\_2(m\log\_e2-1)}{m}=0$, we see that $$\lim\_{n\to\infty}\frac{m}{\log\_2n}=1$$

Recall that $f(r)$ takes the minimum value at $r=m$ for a fixed $n$. That is why the book checks the value of $f(r)$ at or near the point $r=\log\_2n$.
> 0 votes

---
Tags: algorithm-analysis, optimization, asymptotics, radix-sort
---


# Question
Title: Resources for connections between dependent type theory and LCCC
Can someone recommend introductory articles/papers on the connections between dependent type theory and locally cartesian closed category? Many Thanks!

# Answer
> 1 votes
The original interpretation of dependent type theory in lcccs by Seely suffers from coherence problems. There are a range of techniques with have been invented to solve them. In most cases the interpretation of a type $\Gamma \vdash A \textit{ type}$ is no longer an object in the slice $\mathbf S/\Gamma$ over the interpretation of $\Gamma$, instead the interpetation of $A$ will be a fibered functor $A:y(\Gamma)\to \partial\_1$ where $\partial\_1$ is the codomain fibration of the base. The fibered Yoneda lemma tells us that there is an equivalence $$Fib\_\mathbf S(y\Gamma,\partial\_1) = \mathbf S/\Gamma$$ The extra data which a fibered functor $A:y(\Gamma)\to \partial\_1$ carries around is a choice of pullbacks of its display map in $\mathbf S/\Gamma$, and this is what is needed to solve the coherence problem. You asked for references, so here are some:

* *On the interpretation of type theory in locally cartesian closed categories* by Martin Hoffman explains the coherence problem in Selly's semantic and explains how one can solve it.
* More generally, the constructions in Hoffman's paper is just a way to associate a model of dependent type theory to a lcccs. You may want to read about such models in general. There are many different ones, but they are all essentially equivalent. E.g. there are categories with families, categories with attributes and split comprehension categories.
* The later chapters of Jacobs *Categorical Logic and Type Theory* talk about comprehension and split comprehension categories. They do not discuss the canonical splitting of the self-indexing $\partial\_1$ though.
* *Natural Models of Homotopy Type Theory* by Awodey discusses the interpretation of $\Sigma,\Pi$ and extensional equality in a category in a really nice way.
* *Categories with Families Unityped, Simply Typed, and Dependently Typed* by Castellan, Lairambault, Dybjer discusses in detail the 2-equivalence between the 2-category of lcccs and the 2-category of democatric categories with families which admit $\Pi,\Sigma,=,\mathbf 1$. I believe they also show that the syntax of Martin-Löf dependent type theory yields a 2-initial (in the non-strict sense) category with families. Together with the 2-equivalence to lcccs one can conclude that the category of contexts of MLTT with $\Pi,\Sigma,\mathbf 1,=$ is 2-intial in lccc.
* The shorter article *The biequivalence of lccc and MLTT* by Clairambault, Dybjer is only about the relation between lcccs and MLTT, so it is exactly what you are looking for.

---
Tags: type-theory, category-theory, dependent-types
---


# Question
Title: Why does a CRC detect burst errors of longer than r+1 bits independently of burst length?
In this question it is stated that a CRC detects burst errors of length greater than the CRC length with probability $1-2^{-r}$, where $r$ is the length of the CRC.

Why is there no dependence on the length of the burst?

# Answer
The CRC could have any of $2^r$ possible values. If you have an error burst where k \>= r bits have random bit values, then the CRC of these k bits has one of $2^r$ possible values (because the CRC has r bits), of which one is correct. So you get the correct CRC by pure coincidence with probability $2^{-r}$.

For smaller errors (less than r bit) we would try to design the CRC so it cannot ever be correct.
> 0 votes

# Answer
There is a dependence on the length. For an *n*-bit CRC and a *k*-bit burst error, the probability of a false positive is *(2max(k – n, 0) – 1) / (2k – 1)*. One minus that is the probability of a *k*-bit burst error detection.

In the limit, you get *1 – 2-n*.
> 1 votes

---
Tags: error-correcting-codes, crc
---


# Question
Title: Finding equal-sum subsets from two arrays
Consider the following problem: You are given two integer arrays $A$ and $B$ of size $N$ and $M$, respectively. You are guaranteed that $1 \<= A\[i\] \<= M$ and $1 \<= B\[i\] \<= N$ for all $i$ (so each array's elements is at most the other array's size). The sizes of the arrays, $N$ and $M$, may be up to $100,000$. Construct two nonempty subsets, one from $A$, and one from $B$, that have the same sum. (Here subsets means sub-multi-set). **There is apparently an $O(N + M)$ solution to this problem, but I don't know what it is.**

My idea: First, I don't know if it is provable that two equal-sum subsets always exist... anyways:

1. Sort both arrays, which takes $O(N + M)$ time if we use counting sort, as the array elements are small.
2. Iterate through each array, and observe that all the possible subset sums will form contiguous ranges, so collect all contiguous ranges of possible subset sums. To do this, simply maintain the prefix sum $psum$ of the array so far, and then consider the current element $curr$. If $curr \<= psum$, that means for any number $x \in \[psum - curr, psum\]$, we can also make the sum $x + curr$. If $curr \> psum$, then we cannot make any sum $x \in (psum, curr\]$.
3. After collecting all the ranges, iterate through them and find any two ranges that intersect from both arrays. Then, take a subset sum that both arrays can create, and the task reduces to finding a subset of the array which sums to that subset sum (which I also don't think can be done efficiently).
4. Another problem is, I found that the number of contiguous ranges of subsets can be quite large, growing quicker than $O(N)$ or $O(M)$.

**So, I'm stuck.**

I'm guessing that the conditions $1 \<= A\[i\] \<= M$ and $1 \<= B\[i\] \<= N$ allows for some mathematical proof that two equal-sum subsets always exist. I'd be very interested as to a proof of this, or any solutions to the problem that achieve close to the desired time complexity. I hope my line of reasoning has been clear so far.

# Answer
### The outline of some ideas.

Since it is too slow to run through all subsets, we may restrict to subarrays of $A$ and $B$. The sum of numbers in a subarray can be computed readily as **the difference of two prefix-sums**.

Towards two subarrays of equal sums, we would like to generate many pairs of prefix-sums, one from $A$ and the other from $B$ such that the difference in each pair is as small as possible. Then we might squeeze out two subarrays of equal sums when we have enough pairs with small differences.

### A proof for the existence of two equal-sum subarrays

Let us use prefix sums and pigeonhole principle to prove that amazing fact.

Let $p\_A$ be the prefix sums of $A$, i.e. $p\_A\[i\]$ is the sum of the first $i$ numbers in $A$ for $0\le i\le N$. Ditto for $p\_B$, the prefix sums of $B$.

Assume $p\_B\[M\]\ge p\_A\[N\]$. If not, switch $A, N$ with $B, M$ respectively.

For each $i$, $1\le i\le N$, let $$d(i)= p\_B\[g(i)\]-p\_A\[i\]$$ where $g(i)$ is the smallest $k$ such that $p\_B\[k\]\ge p\_A\[i\]$. $g(i)$ is well defined since $p\_B\[M\]\ge p\_A\[N\]\ge p\_A\[i\]$.

For all $1\le i\le N$, $d(i)$ is one of $0,1,\cdots,N-1$ since

* $d(i)\ge0$ by definition.
* Since $g(i)$ is the smallest, we have $p\_B\[g(i)-1\]$ $\<p\_A\[i\].$ So $d(i)$ $=(p\_B\[g(i)-1\] +B\[g(i)\])-p\_A\[i\]$ $\< B\[g(i)\]$ $\le N$.

There are two cases.

* $d(i)=0$ for some $i$.
The sum of the first $g(i)$ elements of $B$ is the same as the sum of the first $i$ elements of $A$.
* $d(i)$ is never $0$.
One number from $1$ to $N-1$ must appear at least twice among $d(i)$'s, thanks to the pigeonhole principle. That is, there exist $e,f$ such that $d(e)=d(f)$. WLOG, $e\<f$.

The equality means the sum of numbers from the $e+1$-th number to the $f$-th number in $A$ is the same as the sum of numbers from the $e+1$-th number to the $f$-th number in $B$.

In both cases we have obtained two equal-sum subarrays.

### Time-complexity analysis

The proof above implies an $O(M+N)$ algorithm immediately.

* Prefix sums for $A$ can be computed in $O(N)$ time. Ditto for $B$.
* The array $g$ can be computed in $O(M+N)$ time using two-pointer technique.
* $e$ and $f$ can be found in $O(N)$ time or $O(M)$ time.
> 2 votes

---
Tags: algorithms, time-complexity, arrays, mathematical-analysis, subset-sum
---


# Question
Title: Multiple post-fix expressions for an in-fix expression
Today I was learning to convert post-fix expressions to in-fix expressions and vice versa. What I want to know is **whether a post-fix expression can have more than one infix representations**.

For example, if I consider the following in-fix expression:

```
A+B-D/X

```

I get these post-fix expressions:

```
ABDX/-+

```

and

```
AB+DX/-

```

I didn't use the stack table method for solving these. I did these conceptually and both these expressions evaluate to

```
A+B-D/X

```

post-fix expression. I even verified my result with this site and both the post-fix expressions evaluate to:

```
A+B-D/X

```

# Answer
> 1 votes
(A+b)-c and a+(b-c) are not the same. Not with integers (one expression might overflow while the other one doesn’t), not with floating-point numbers ( different rounding errors).

Only the second postfix expression is correct.

# Answer
> 1 votes
As pointed out in the comments by this user, under the standard rules of operator precedence and operator associativity every expression has a unique expression tree representation. Now every ordered tree (including expression tree) results into unique sequences while traversing the tree in inorder or in preorder or in postorder. Now the inorder traversal of the expression tree gives us the infix expresion similarly postorder traversal gives the postfix expression.

Because of the one-to-one correspondence between a expression and its expression tree under the perview of operator precedence and operator associativity, you *cannot get more than one infix expression for a postfix exppression*. But you can always have two expressions which are equivalent in the sence that they evaluate to same result but they are not considered equal. `(10 + 20) + 30` and `10 + (20 + 30)` are equivalent but not same and have two different postfix expressions namely `10 20 + 30 +` and `10 20 30 + +`. Also, under the standard rules of operator precedence and operator associativity `10 + 20 + 30` corresponds to `(10 + 20) + 30`.

---
Tags: stacks
---


# Question
Title: 64-bit Xorshift with 2^96 or 2^128 period
Can we create Xorshift generator, as Marsaglia in "Xorshift RNGs" does, using 64-bit numbers, but with period 2^96 or 2^128?

He proposed PRNG with period 2^96:

```
t=(xˆ(x<<3))ˆ(yˆ(y>>19))ˆ(zˆ(z<<6));x=y;y=z;return(z=t);

```

But this works on 32-bit ints, as I think. I can't generalize his work to create similar thing working on 64-bit numbers, but I think it could be possible. He created it probably using matrices in 3.1 and precomputed triples in 3. But I'm still not sure how to do it.

Quality of such PRNG doesn't matter. It just have to has period guaranteed.

# Answer
> 0 votes
If you only care about the period and not about randomness, use a 96-bit or 128-bit counter.

If you care about randomness, use any decent PRNG. It doesn't matter which you pick.

If you don't want it to repeat in your lifetime, a random 128-bit value from a decent PRNG is incredibly unlikely to ever repeat within your lifetime.

# Answer
> 0 votes
I cracked this problem a little bit. In fact, not using xorshift, bit using LFSR. As I wrote in the comments I want to use it as an alternative to the counter. LFSRs are in fact used as a counters, beacuse have simpler feedback logic than natural binary counters or Gray-code counters, and therefore can operate at higher clock rates.

We can consider something as simply as that for 64-bit counter:

```
uint64_t lfsr = 123;
lfsr = -(lfsr & 1) & 0x800000000000000D ^ (lfsr >>= 1);

```

Now we can aplly it using only 32-bit ints:

```
uint64_t result = 0;

uint32_t lfsr_low = 123;
uint32_t lfsr_hi = 0;
unsigned tmp = 0;

tmp = lfsr_low & 1;
lfsr_low = -tmp & 13 ^ (lfsr_low = ((lfsr_hi & 1) << 31) | (lfsr_low >> 1));
lfsr_hi = -tmp & 0x80000000 ^ (lfsr_hi >>= 1);

result = ((uint64_t)lfsr_hi << 32) | lfsr_low;

```

We can do the same with 128-bit LFSR on 64-bit ints. Anyway, it would be faster to use just two different 64-bit LFSRs to get period 2^128, for example:

```
lfsr_1 = -(lfsr_1 & 1) & 0x800000000000000D ^ (lfsr_1 >>= 1);
lfsr_2 = -(lfsr_2 & 1) & 0x800000000000000E ^ (lfsr_2 >>= 1);
lfsr_2 += lfsr_1;

```

It is still slower in my tests than counter, even 128-bit counter implemented on 64-bit ints, but it works. lfsr\_2 could have period 2^128-2^65+1. This is because adding or xoring two PRNG generators with period p\_1 and p\_2 should give a generator with period p\_1\*p\_2. Until their bits are not correlated in such a way, they will cancel out each other. For 4-bit LFSRs:

```
lfsr_1 = -(lfsr_1 & 1) & 9 ^ (lfsr_1 >>= 1);
lfsr_2 = -(lfsr_2 & 1) & 12 ^ (lfsr_2 >>= 1);
lfsr_2 += lfsr_1;

```

I got period not equal to 2^8-2^5+1, but 210. So there is some risk of pathological behavior, and perhaps even falling such a system in a very short cycle. It's hard to estimate.

---
Tags: pseudo-random-generators
---


# Question
Title: How can I find 2 median values of an array which is an union of 2 arrays in O(log n)?
So I have 2 sorted arrays which will have the same length and what I need to do is sort the union array (the union of the two sorted arrays) and then find two median values, I need to do this in O(log n). I was able to come up with finding the median in log(n) but that is without sorting the arrays, I could use one of the sorting algorithms but then the time complexity will be more than log(n).

My way for finding the median in log(n):

1. divide the array in half
2. Go to the result index (it will be the number we get after dividing the array in half)
3. Same thing as above but add 1 to the index number.

Again this will be log(n) if the union of the 2 arrays were sorted but in this is not the case here. I think binary search could be used but I am not 100% sure exactly how to use it in this problem.

# Answer
> 2 votes
The general idea of the algorithm is pretty straightforward, it basically boils down to the dichotomic search idea by cutting your problem in half at each step. But the parity of the length of the arrays introduces some noisy intricacies.

## Notations

* $X$ and $Y$ two sorted arrays of the same size (their starting index is 0).
* $n = |X| = |Y|$ the arrays' size
* $m = \bigg\lfloor \dfrac{n}{2} \bigg\rfloor$ the middle index
* $x = X\[m\]$ and $y = Y\[m\]$ the middle values
* Note that, since the two arrays are the same length, there is a unique pair of median values.

## The basic idea

At each step of the algorithm, we are discarding the same number of values to the left and right of the merged sorted arrays : the medians are preserved. For example :

The mathematical proof would be cumbersome to write.

## The algorithm

Let's assume that $n$ is **odd**. If :

* $x = y$ then they must be our two medians. If we sorted the merged array, those values would necessarily appear next to each other in the middle of it.
* $x \< y$ the problem can be reduced. It is the same as to find the two medians of the arrays $X\[m:n\]$ and $Y\[0:m + 1\]$ (I use the Python's slice notation here, endpoint is excluded).
* $x \> y$ is the symmetrical case, we should consider the outer part $X\[0:m+1\]$ and $Y\[m:n\]$.

Note that at each step, $X$ and $Y$ are always of the same length. As you can see, we can recursively apply this process until the two arrays are of total size of 4 or 2, they are the base cases.

If $n$ is **pair**, we have to be careful about the next endpoints we consider as the two medians, as they aren't a *true* middle in the two arrays. Let be $m^- = m - 1$, $~x^- = X\[ m^- \]$ and $~y^- = Y\[ m^- \]$. If :

* $x = y$ then the two medians must be the two medians of $\[x^-, x\],~\[y^-, y\]$ : it is one of our base case.
* $x \< y$ then we should consider $X\[m - 1:n\]$ and $Y\[0:m + 1\]$
* $x \< y$ we should consider $X\[0: m + 1\]$ and $Y\[m - 1: n\]$

As you can see, we carry the two middle elements to the next iteration !

## Naive first implementation

If we implement the above algorithm in Python :

```
def is_odd(n: int) -> bool:
    return n & 1

def base_case_medians_2(a: int, b: int) -> tuple[int, int]:
    """ Returns the two medians (ordered) of the 2 given values. """
    return (a, b) if a < b else (b, a)

def base_case_medians_4(a: int, b: int, c: int, d: int) -> tuple[int, int]:
    """ Returns the two medians (ordered) of the 4 given values. """
    return ((c, d) if b >= d else (b, c) if b <= c else (c, b)) if a <= c else ((a, b) if b <= d else (a, d) if a <= d else (d, a))

def medians_recursive_naive(X: list, Y: list) -> tuple[int, int]:
    """ Returns the two medians of the merged (assumed sorted and of the same size) given arrays.
        Runs in quasilinear time as unecessary copies of the arrays are made. """
    n = len(X)

    # Recursion's base cases
    if n == 1:
        return base_case_medians_2(X[0], Y[0])
    elif n == 2:
        return base_case_medians_4(X[0], X[1], Y[0], Y[1])

    m = n // 2
    x, y = X[m], Y[m]

    # Branch on the parity of the arrays' size
    if is_odd(n):
        if x == y:
            return (x, y)
        elif x < y:
            return medians_recursive_naive(X[m:], Y[:m + 1])
        else:
            return medians_recursive_naive(X[:m + 1], Y[m:])
    else:
        if x == y:
            return base_case_medians_4(X[m - 1], x, Y[m - 1], y)
        elif x < y:
            return medians_recursive_naive(X[m - 1:], Y[: m + 1])
        else:
            return medians_recursive_naive(X[: m + 1], Y[m - 1:])

```

As the code shown above, an iteration takes $O(n)$ as copies of the arrays are made when forwarded to the next recursion call, but copies are unecessary if we instead keep track of the start and end indices of the two subarrays we consider.

## Achieving logarithmic complexity

So, if we use instead indices, our function signature would look like :

```
def medians_recursive(x_start, x_end, y_start, y_end):

```

But, this recursive algorithm could be simplified into an iterative algorithm :

```
def medians_iterative(X: list, Y: list) -> tuple[int, int]:
    """ Returns the two medians of the merged (assumed sorted and of the same size) given arrays.
        Runs in logarithmic time. """
    x_start, x_end = 0, len(X)  # note that the `end` is excluded
    y_start, y_end = 0, len(Y)

    # Algorithm's main loop, cut in half (almost) the arrays at each iteration
    while x_end - x_start > 2:
        x_mid = (x_start + x_end) // 2
        y_mid = (y_start + y_end) // 2
        x, y = X[x_mid], Y[y_mid]

        odd = is_odd(x_end - x_start)
        if x == y:
            return (x, x) if odd else base_case_medians_4(X[x_mid - 1], x, Y[y_mid - 1], y)
        elif x < y:
            x_start = x_mid + odd - 1
            y_end = y_mid + 1
        else:
            x_end = x_mid + 1
            y_start = y_mid + odd - 1

    # Base cases
    if x_end - x_start == 1:
        return base_case_medians_2(X[x_start], Y[y_start])
    else:
        return base_case_medians_4(X[x_start], X[x_start + 1], Y[y_start], Y[y_start + 1])

```

# Answer
> 1 votes
I'm assuming the two arrays are of size $n$ each. Now to unite them into a single sorted array one can use the merge procedure from Merge Sort (see here). This runs in $\Theta(n)$ which is asymptotically tight, that is you can not do better as you have to observe all the elements from both arrays. Thus $O(\log n)$ is not possible.

Probably what you are asking is that, you need to obatain the median (or medians) of the union array in $O(\log n)$, which actually does not require you to actually merge two arrays. The idea is similar to the Binary Search technique, you need to throw away half of the array in each iteration. Suppose the two arrays are called $A$ and $B$. You compare $A\[mid\]$ with $B\[mid\]$, if they are the same, you return any one of them as your median (or both as two medians). If not, lets assume without loss of any generality, that $A\[mid\] \< B\[mid\]$, then your median can not be in $A\[1:mid\]$. You discard the left half of $A$, that is, $A\leftarrow A\[mid+1:n\]$ and repeat this process. Eventually one of the array will exhaust, then simply return the median of the other one.

Detalied descriptions along with coded solutions are avilable here and here.

---
Tags: algorithms, algorithm-design
---


# Question
Title: Can we solve a decision problem with two identical answers like $false\equiv(\lambda f.\lambda y.y)$ or $0\equiv(\lambda f.\lambda n.n)$?
as the title says

Can we solve a decision problem with two identical answers like $false\equiv(\lambda f.\lambda y.y)$ or $0\equiv(\lambda f.\lambda n.n)$?

if no why? and if yes then why can't we decide whether a lambda term is in normal form or not?

thanks

# Answer
> 1 votes
This does not work in lambda calculus. One of the rules for evaluating lambda calculus terms is α-conversion, which allows variable names to be changed at any time for any reason, as long as they do not conflict. There's no way that a program can arrange to put certain variable names in certain places as a kind of signal, because they could be arbitrarily renamed.

In general, if two answers are identical, they are the same answer, so your question is asking whether a decision problem can be answered with the same answer twice, e.g. can the halting problem be "solved" by a solver that outputs "no" if the program halts and "no" if the program does not halt. This is trivially possible, and provides no useful information because it does not actually tell us the answer.

---
Tags: lambda-calculus, normal-forms
---


# Question
Title: SAT with every variable occuring exactly once
With the Circuit-SAT problem, I often see the "split" gate (I don't know the official name of it). This gate has a truth table of:

$$ \begin{array}{|c |c c|} 0 & 0 & 0\\ 1 & 1 & 1\\ \end{array} $$

And it has a symbol of this:

This gate allows us to use variable names more than once when we translate circuits to CNF.

I was wondering if the case where we didn't use this gate is still NP-complete. In other words, if we used every variable exactly once, would SAT still be NP-complete?

# Answer
> 1 votes
Each variable would appear *twice* \- once as an output to a gate and once as an input.

It is trivial to start from the output and trace backwards, setting variables as you go, with a simple greedy algorithm. If the output has to be 1 then set it to 1. If the output of an AND or OR gate is 1 or 0, set all inputs to that same value; if the output of a NOT gate is 1 or 0, set the input to the opposite value. Go backwards from the circuit's output to the inputs until they are all set.

Without any splits in the circuit it is impossible to come to a situation where one path says an input should be 1 and another path says it should be 0, which would require backtracking to find an alternative solution. This can't happen because there is only one backwards path from the output to any variable.

---
Tags: satisfiability, circuits
---


# Question
Title: Reference request for book on design patterns with foreword by Christopher Alexander
I do recall having found a book on software design patterns with a foreword by Christopher Alexander. Now, as is well known Alexander is credited as the creator of the concept of design patterns and design languages. In this particular text, he also described how he first came to know his work was being used in computer science. Does someone know what is that book, and what edition?

# Answer
Could it be *Patterns of Software* by Richard P. Gabriel (Oxford University Press, 1996)? Here's an excerpt from the foreword by Christopher Alexander:

> A year or two ago, I was astonished to get several letters from different people in the computer science field, telling me that my name was a household word in the software engineering community: specifically in the field of object-oriented technology. I had never even heard of object-oriented programming, and I had absolutely no idea that computer scientists knew my work, or found it useful or interesting; all this was a revelation to me. It was a pleasant revelation, but one that I did not really grasp at first; nor did I think much about it. I assumed the people who wrote to me were exaggerating anyway, out of politeness.
>
> Then, one of these people, Marc Sewell from IBM in Atlanta, came to see me and told me much the same, to my face, in a discussion over coffee. Naturally, I assumed he too was exaggerating. When I expressed my surprise and doubts about the depth of this “alexandrian patterns movement,” he told me that in any given issue of The Journal of Object-Oriented Programming, there was almost certain to be some mention of my name. To prove it the next day he came with the current issue of The Journal of Object-Oriented Programming. There was in it, an article by Richard Gabriel, the essay that appears in this book as the chapter entitled “The Bead Game, Rugs, and Beauty."
> 0 votes

---
Tags: reference-request, design-patterns
---


# Question
Title: Given a bipartite graph G and an integer l, how many edge subsets of size l are there such that the degree of each vertex is odd?
Given a bipartite graph $G=(V,E)$ and an integer $l$, how many edge subsets ($E'\subseteq E$) of size $l$ are there such that the degree of each vertex in the resulting subgraph $G'=(V,E')$ is odd?

I have not been able to come up with anything smarter than explicitly enumerating all possible subsets and checking whether they satisfy the criteria, but the complexity of this approach is $O(E^l)$, which is exponential in $l$.

I encountered this problem when I was trying to simplify calculations of expectation values of certain operators relevant for Quantum Computing. These expectation values are exponentially hard to evaluate with my current algorithm, but I am not sure if it has to be that way, so I was trying to simplify it, and this is one of the key problems that I need to solve for that.

Does anyone know if there is a polynomial-time algorithm for this problem?

# Answer
I don't know whether this can be solved in polynomial time, and I don't know a faster way to get the exact count, but I can propose a way to approximate the number with close to $O^\*(E^{|l|/2})$ time, which is a bit better than $O(E^{|l|})$. This is not very satisfying and not a very good answer, so I hope someone else will have a better solution.

Let $GF(2)$ denote the integers modulo 2 (i.e., the values 0 and 1, with an addition operator that adds modulo 2). Introduce variables $x\_e$, one for each edge $e$, taking values in $GF(2)$, with the intended meaning that $x\_e=1$ means that edge $e$ is included in the subset, and $x\_e=0$ means that $e$ is not included.

Given a vertex $v$, note that the degree of $v$ is odd iff

$$\sum x\_e = 1,$$

where the sum is taken over all edges $e$ that are incident on $v$. (Since we are working in $GF(2)$, the sum is implicitly modulo 2.) This is a linear equation on the variables $x\_e$. Looking at all of the vertices, we obtain one linear equation per vertex in the graph.

Putting all of this together, we obtain $|V|$ linear equations over $|E|$ variables, with arithmetic done in $GF(2)$. So, introduce a $|E|$-vector $x$ that is the concatenation of all the $x\_e$'s, and introduce a $|V| \times |E|$ matrix $M$ to represent all of the linear equations. Then we have the system of linear equations

$$Mx=1,$$

where here $1$ represents the $|E|$-vector containing all 1's.

Now your problem comes down to: how many choices of $x$ are there, such that $Mx=1$ and $\text{wt}(x)=l$?

The approach will be to let $x=(y,z)$, where each of $y,v$ are $|E|/2$-vectors, and let $M=(M\_1,M\_2)$, so that the problem becomes to count $y,z$ such that $M\_1y = 1 + M\_2z$ and such that $\text{wt}(y) + \text{wt}(z) = l$.

For each $m$ such that $(1-\epsilon)l/2 \le m \le (1+\epsilon)l/2$, we'll do the following. Enumerate all $y$ such that $\text{wt}(y)=m$, compute $M\_1y$ for each such $y$, and store it in a hashtable keyed on the value $t=M\_1y$ (and keeping a count of how many $y$'s yield the value $t$). Then, enumerate all $z$ such that $\text{wt}(z)=l-m$, compute $u=1+M\_2z$, and look $u$ up in the hashtable. Sum up all the counts from matches in the hashtable. The total running time is $O(|E|^{(1+\epsilon)l/2})$.

This doesn't capture all matches, but I believe it'll give a reasonable approximation, as the overwhelming majority of $x$'s such that $\text{wt}(x)=l$ satisfy $x=(y,z)$ with $\text{wt}(y) \le (1+\epsilon)l/2$ and $\text{wt}(z) \le (1+\epsilon)l/2$.

This seems related to the problem of finding low-weight codewords for a linear code, except that here you want to count the number of codewords of weight $l$, rather than finding one codeword of weight $\le l$. I'm not sure whether any of the known algorithms for finding low-weight codewords can be adapted to your setting, but you could explore the literature on that problem and see if any of those techniques can be used for your goal.
> 1 votes

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


# Question
Title: Which combinatorial problem is reminiscent to mine?
I am trying to understand which combinatorial problem best fits the one I have. I am mostly asking from the perspective of being pointed towards relevant literature. I will explain the problem with an example.

Consider the set $S = \lbrace{a^1, a^2, a^3, b^1, b^2, b^3, b^4, c^1, d^1, d^2, d^3, d^4 \rbrace}$. So note that $S$ is like a multi-set but elements of the same type can be distinguished. We are given a tuple of sets $U$ which specifies which elements of $S$ are needed and their quantity. Consider this example where $U = (\lbrace{2a, 1b, 1c \rbrace}, \lbrace{1a, 3d\rbrace}, \lbrace{2b, 3d\rbrace} )$, so the first order (set) of $U$ (i.e., $\lbrace{ 2a, 1b, 1c \rbrace}$) is asking for 2 elements of $a$, 1 element of $b$ and 1 element of $c$ respectively. We can get those 2 elements of $a$ by selecting any 2 from ${a^1, a^2, a^3, a^4}$, likewise we can choose anyone one from $b^1, b^2, b^3, b^4$ for $b$, and similarly for $c$. For example we may choose to satisfy the first order $\lbrace{2a, 1b, 1c \rbrace}$ by assigning it ${a^3, a^4, b^2, c^1}$, however by doing so these elements of $S$ are no longer available for satisfying subsequent orders of $U$. There are costs associated with how we choose to satisfy each order. For example, it can cost us differently had we chosen to satisfy $\lbrace{2a, 1b, 1c \rbrace}$ with say ${a^1, a^2, b^1, c^1}$ instead.

I know that I have not described much about the cost function, but just given the constraint set I am wondering which well-studied combinatorial problem is reminiscent or equivalent to mine. I am ultimately interested in either online algorithms or heuristics for satisfying the orders in $U$ with low cost. I am interested to explore literature related to this problem (if available) with different cost functions and under different assumptions (such as those typical in online settings) so please feel free to suggest if you think a certain problem, paper or application is related to the problem I described.

I am **NOT** interested in a Mixed Integer programming formulation for this problem.

# Answer
This sounds like it can be framed as an instance of the assignment problem, assuming the costs are computed as a linear function of a cost for assigning each individual item to a particular order.
> 0 votes

---
Tags: algorithms, approximation, heuristics
---


# Question
Title: I'm completely stumped by these questions for a Computer Organization assignment
My Professor for my Computer Organization class gave us a few questions about caches on an assignment. I'm completely stumped by most of them. I've watched a few videos on caches on YouTube by Intermation, read the textbook, and even asked my friend (the Professor's office hours are not today). The textbook our Professor gave us does not have examples similar to the questions in the assignment. Given an address and the mapping scheme, and told which bits are used for what, I can map it to a value in the cache.

Here are the questions I don't know how to do:

1. Assume a 2-way set associative cache with 4 one word blocks. Consider the following word address sequence:

0, 1, 2, 3, 4, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0

a. Assuming an LRU replacement policy, which accesses are hits?

b. Assuming an MRU (most recently used) replacement policy, which accesses are hits?

c. Describe an optimal replacement policy for this sequence, which accesses are hits using this policy?

2. Caches are important to providing a high-performance memory hierarchy to processors. Below is a list of 32-bit memory address references, given as word addresses.

0x03, 0xb4, 0x2b, 0x02, 0xbf, 0x58, 0xbe, 0x0e, 0xb5, 0x2c, 0xba, 0xfd

a. For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with 16 one-word blocks. List if each reference is a hit or a miss, assuming the cache is initially empty.

b. For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with 8 two-word blocks. List if each reference is a hit or a miss, assuming the cache is initially empty.

P.S. If you think this is cheating, I'll happily take this question down.

# Answer
This community is not for assignment solving. Anyway, I will drop some hints that should help you get started.

1. Cold Misses: It happens when your cache does not contain any block, typically after the system is powered on.
2. Counters: These are separate structures associated with each block, that can be used to track down usage patterns.

Hope that helps.
> 1 votes

---
Tags: cpu-cache
---


# Question
Title: How to calculate the size of main memory if the cache is 4-way set associative memory, cache memory size is 256KB and number of tag bits is 8
I'm trying to calculate the main memory size, and the only information given is the size of the cache, which is 256 KB, and the number of tag bits, which is 8. Cache is a 4-way set associative memory.

I'm wondering why block size information is missing in this question, because without it, I'm not able to calculate the number of blocks, number of sets, block offset, etc., which will eventually help me calculate the size of main memory.

Is there any way that I could find the block size with the given information above? I'm thinking that the cache size and number of tag bits do give something important, but I'm stuck. Any help will be appreciated.

# Answer
> I'm not able to calculate the number of blocks, number of sets, block offset, etc., which will eventually help me calculate the size of main memory.

None of that is required.

Your cache size is $256KB$, which means it can store sequence of $\log\_2(2^8.2^{10}) = 18$ bits (assuming it is byte addressable). You will need $\log\_2 4 = 2$ of these bits to access a particular block in the $4$-way set. Hence, set number and block offset together take $16$ bits and as mentioned in your question, tag takes $8$ bits; which makes the total address space consist of $24$ bits.

Therefore, main memory size is $2^{8+16}B = 2^{24}B = 16MB$.
> 0 votes

---
Tags: computer-architecture, cache
---


title: Is $n^n$ is a big-oh n factorial

text:
# Question
Title: Is $n^n$ is a big-oh n factorial
Is it true or false that $n^{n} \in \mathcal{O}(n!)$ ? Any suggestions how to prove/disprove this statement?

# Answer
> 2 votes
$$\frac{n^n}{n!}=\frac{n\cdot n\cdot n\cdots n\cdot n}{n(n-1)(n-2)\cdots 2\cdot 1}=\frac nn\frac{n}{n-1}\frac{n}{n-1}\cdots\frac n2\frac n1\>1\cdot1\cdot1\cdots1\cdot n$$ is sufficient.

(In fact, by the same argument the ratio is $\Omega(n^k)$ for all $k$, and $n^n\notin O(n^kn!)$.)

# Answer
> 1 votes
$\lim\_{n \to \infty} \frac{n^n}{n!} = \lim\_{n \to \infty} \prod\_{i=1}^n \frac{n}{i} \ge \lim\_{n \to \infty} \prod\_{i=1}^{\lfloor n/2 \rfloor} \frac{n}{i} \ge \lim\_{n \to \infty}2^{\lfloor n/2 \rfloor } = +\infty.$

# Answer
> 0 votes
Exact estimation, from both sides, can be obtain from $$\left(\frac{n}{e} \right)^n\< n! \< e\left(\frac{n}{2} \right)^n$$ i.e. $$\frac {2^n}{e} \cdot n!\<n^n\<e^n \cdot n!$$

# Answer
> 0 votes
By Stirling's Approximation,

$$n^n = O\left(\frac{n! \cdot e^n}{\sqrt{n}}\right)$$

$$\lim\_{n \to \infty} \frac{e^n}{\sqrt{n}} = \infty$$

Meaning that $n^n$ isn't $O(n!)$, however you do have that $n!$ is $O(n^n)$.

# Answer
> -1 votes
$n! = 1 \cdot 2 \cdot 3 ... \cdot n ≤ 1 \cdot n \cdot n ... \cdot n = n^{n-1} = n^n / n$. Or $n^n ≥ n \cdot n!$. So clearly not O (n!).

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Let $L$ the language over $\{a,b\}$ of words that contains the same number of occurrences of $a$ and $b$. Which of the following languages is regular?
The options are:

(a) $L \cap a^{\ast}b^{\ast}$

(b) $(L \cap a^{\ast}b^{\ast}) \cup a^{\ast}b^{\ast}$

(c) $L \cup a^{\ast}b^{\ast}$

(d) $(L \cap a^{\ast}b^{\ast}) \cup b^{\ast}a^{\ast}$

My doubt is: We don't know what exactly $L$ is, it could be $a^{n}b^{n}$ or $b^{n}a^{n}$, we for sure know that $L$ is either of the two!

The way I think is, when we look at the first option the resultant language can be either $\epsilon$ or $a^{n}b^{n}$ because $L$ can be either of the mentioned choices, which also means that we can't deduce it properly, similarly i cannot decipher the other options.

Can someone explain why each option is either correct or wrong choice? Given that the correct option is $(b)$

# Answer
> 1 votes
(b) is the only correct answer and this follows directly from the well known proof, $L\_1 = \\{a^n b^n : n \in \mathbf{N}\\}$ is not regular. You can refer to the second page of this resource, for example.

---

(a) We start of by noting that $L' = L \cap a^\*b^\*$ is equivalent to $L\_1$, which is not regular.

(b) $L\_1 \cup a^\*b^\*$ is equivalent to $a^\*b^\*$ which is regular. This can be easily verified by constructing a single state automaton accepting any number of $a$s and $b$s.

(c) We prove this using pumping lemma. Let $x = b^na^n$. Clearly, $x \in L', |x| \geq n$.
Let $uv = b^j$ for some $j \in \mathbf{N}, 0 \leq j \leq n, v = b^k$ for some $k \in \mathbf{N}, 0 \< k \leq n$.
If $L'$ was regular, then $uv^2w = b^{n+k}a^n \in L'$, which is not true. Thus, $L'$ is not regular.

(d) Here, $L' = a^nb^n \cup b^\*a^\*$. Apply the same proof as in (c) for the string $x = a^kb^k, k \in \mathbf{N}$.

---
Tags: regular-languages, regular-expressions
---


# Question
Title: if f(n),g(n) =! 0 , for every n > 0 , and f(n) = Ω(g(n)) , then does this mean that 1/f(n) = O(1/g(n))
Basically what i am trying to prove is this : $f(n),g(n) \neq 0\quad , n\>0 \ \ \ \ and f(n)=Ω(g(n)) \ \ \ , \ then \frac{1}{f(n)}=O(\frac{1}{g(n)}) $

I guess that if we take the definition of $f(n) = Ω (g(n))$ , which means that $f(n) \ge cg(n) $ for every $ n \ge n0$ and then flip the relation so that it becomes $\frac{1}{f(n)} \le \frac{1}{c} \frac{1}{g(n)}$ then we can say that the statement is true , however i am not sure if this is correct or not . Can anyone help me prove it correctly or disprove it ? Thank you .

# Answer
$$\forall n\>n\_0:f(n)\ge c\\,g(n)\>0\implies\frac1{f(n)}\le \frac 1c\frac1{g(n)}$$ is true.

Just a remark: $n\_0$ must be taken larger than any root of $f$ and $g$. A pathological counter-example is

$$1=\Omega\left(\sin\left(\frac{n\pi}2\right)\right).$$
> 0 votes

---
Tags: asymptotics, correctness-proof, big-o-notation
---


# Question
Title: Silly question: what counts as a "unit of work" when computing big-Oh time complexity
I am going through a fairly non-rigorous textbook called 'Cracking the code interview' and I am bothered by this terminology called "unit of work".

It says in the textbook that certain operations take constant work, where as others take variable amount of time.

For example, adding/subtracting/multiplying/dividing two numbers take constant work. Similarly, a comparison statement also takes constant work. Lookup are also constant.

Whereas other operations such as for-loop takes a variable amount of work. For example, if a FOR-loop is to be run from $i = 0$ to $i = n-1$, and assuming whatever inside of the FOR-loop takes constant amount of time, then the total amount of work is proportional to $n$. That is, FOR-loop takes $O(n)$ time.

Something that doesn't really make sense to me is the smallest unit that can be defined as "work" in big Oh runtime analysis. What is this unit based off of? Adding two bits together? Adding two integers together?

Stemming from it are two related concerns:

1. certainly multiplication takes more "work" than addition. Division takes more work than subtraction. So what is the smallest unit of work here? Is the time to add two numbers a smaller amount of work than multiplying two numbers? That is, is the work of multiplication proportional to the time of addition?, $\text{work}\_{\times} = c \times \text{work}\_{+}, c \> 0?$
2. For example, are things like multiplication truly independent of the input? $k \times n = n + n + \ldots + n$ ($k$ times). So why is it considered a constant amount of work? Doesn't the same logic also apply to other programs? Say if I have $n$ conditional statement checking if a value is smaller or greater than a number $n$. Then this "constant" operation can still depend on how large my $n$ is (depending on how i implement this comparison).

Thanks for your patience.

# Answer
> 2 votes
We assume an efficient implementation of standard arithmetic operations (since a stupid implementation could be replaced with a better one). Of course, if the numbers were of unlimited size, the amount of time wouldn't be constant. But it would still be constant per bit (at least for addition and comparison).

So if we pretend that all numbers are a constant size ("one unit of storage") and we pretend that all additions are constant time ("one unit of work"), we get the same relationship between input size and processing time as we would if we worked it out measuring space in bits and processing time in single-bit operations: time is linear in input size.

Complexity analysis is not about nanoseconds. You can't figure out how many nanoseconds an algorithm will take just by looking at the algorithm. What we can figure out is what happens to the time if you increase the problem size. Twice as long is twice as long regardless of what the measurement unit is. The measurement unit is irrelevant as long as we use the same one throughout.

Now, if we were really doing arbitrary precision arithmetic, multiplication and division would take polynomial time. But for most algorithms, taking that into account would massively complicate the analysis without adding much new information. So it's convenient to pretend multiplication and division are linear time.

# Answer
> 1 votes
> Something that doesn't really make sense to me is the smallest unit that can be defined as "work" in big Oh runtime analysis. What is this unit based off of? Adding two bits together? Adding two integers together?

It depends on the computational model you choose. It is obviously not true that two numbers can be added together in constant time regardless of their size. If you think about it in terms of the most elementary operations, those on individual bits, adding two $n$-bit numbers would require $O(n)$ elementary operations. And multiplying two $n$-bit numbers would use $O(n^2)$ elementary operations if you do it using long multiplication. You can easily try this out for yourself using pen and paper.

The problem with this viewpoint is that it makes analyzing algorithms very tedious. Any time we would add two numbers $a$ and $b$ we would have to figure out that they would have $\log{a}$ and $\log{b}$ bits respectively and that the addition would take $O(\log{a}+\log{b})$ time. This would make the analysis much more tedious, and result in running time with lots of $\log$s in them.

It is also not very realistic, because real-world computers do not work with individual bits, but instead have words of some natural size (e.g., $8$, $32$ or $64$ bits) and their elementary operations work on those words (in a single processor clock cycle, which is what we might consider an elementary unit of time). Thus, real-world computers can compute the addition (or multiplication or ...) of two $8/32/64$-bit integers in constant time. If we want to do artihmetic on larger integers, it would take more of these elementary operations. E.g., adding two $64$-bit integers on a $32$-bit machine would require two additions of $32$-bit integers plus a possible carry operation.

The most commonly chosen model for analyzing algorithms is the RAM model. The RAM model is a theoretical abstraction of this real-world computer. It wouldn't make sense to fix our word size to any constant, because it is unreasonable to use a computer with 8-bit words to do computations with an exabyte-scale database. The RAM model states that on an input of size $n$ (bits), we presume that the word size of our computer is $O(\log n)$ bits and that we can do artithmetic operations on integers of this size in constant time. Essentially, we presume that our computer "grows" with the size of the input and assume that we can manipulate a pointer to the input in constant time (it would be rather strange to try and handle a very large input, so large that our physical bus size is smaller than required to address the input).

> certainly multiplication takes more "work" than addition

This is not something we care about in the RAM model, at least for the integers with at most $O(\log{n})$ bits on which we can do artihmetic operations in constant time. The constant for multiplication might be higher than the constant for addition, but it's still a constant and the entire point of big-$O$ notation is to hide constants.

> For example, are things like multiplication truly independent of the input?

So, no. In the RAM model, if you have a really large number it can no longer be manipulated in constant time. In the RAM model, if we are analyzing an algorithm for e.g. sorting, our input will have $\Omega(n)$ bits, which means that we can manipulate numbers with up to $O(\log n)$ bits in constant time. This is convenient, because we can have a for-loop over the elements of the input and not have to worry about the time required to increment the iterator or the time required to check whether the iterator has exceeded the upper bound of the for loop, etc... This all falls within the bounds of manipulating integers with $O(\log n)$ bits in constant time.

However, once you start dealing with large numbers, much larger than the input size, this starts to break down. Consider e.g., the problem of computing the $k^\textrm{th}$ prime number. The input is just the number $k$, which has $\log{k}$ bits and this is the size of the input. This means that the largest number we can manipulate in constant time is $O(\log\log{k})$ bits -- much smaller than the $k^\textrm{th}$ prime number that we are trying to calculate.

Let's consider a simpler problem, where the input is two numbers $a,b$ given in binary and we have to compute $a+b$. If the size of our input is $n$ bits, we can solve this problem in $O(n/\log n)$ time: We can manipulate blocks of $\log n$ bits in constant time (by the RAM model), and we have to add $n/\log n$ of those blocks (with a possible carry operation between blocks) to get the final result.

This is also where you start seeing differences between simple operations such as addition and "more complex" operations such as multiplication. If we consider the variant of the previous problem where we would instead have to multiply $a\times b$ it would require more time than $O(n/\log n)$ (the precise time depending on which multiplication algorithm you choose; there are algorithms that are vastly more efficient than the long multiplication example considered previously). Many programming languages have bignum libraries that implement various algorithms for dealing with large integers that have to be represented using multiple words.

> I am going through a fairly non-rigorous textbook called 'Cracking the code interview'

The main takeaway point of this (for your upcoming interview) is that you can treat arithmetic operations as taking constant time, *unless* the problem deals with particularily big numbers with a very succinct input. E.g., computing $\pi$ up to some number of decimal places, computing the $k^\textrm{th}$ prime number, etc,...

# Answer
> 1 votes
When deriving an asymptotic estimate, the unit of work is *not defined* and *need not be defined*. All that matters is that the time a basic operation takes be bounded and independent of the number of data elements ($n$).

For instance, when evaluating a sorting algorithm, we usually care about the number of comparisons and the number of data moves, whichever is larger. These can depend on the length of the keys, but is does not matter as long as the key length is bounded (i.e. does not depend on the number of keys to be sorted).

The rationale is

* that ancillary operations, such as conditional branches, will not be performed more than comparisons or moves, and it is of no use to evaluate their number precisely;
* that the asymptotic behavior is defined to an unknown constant factor, and we usually don't care about that constant;
* a unit of work would be highly dependent on the machine architecture, clock speed and numerous implementation details, making its use highly "non portable".

**Application:**

a. Bubblesort on $n$ $32$ bits integer keys can perform $O(n^2)$ comparisons and swaps and is an $O(n^2)$ algorithm.

b. Bubblesort on $n$ keys of length up to $10$ characters can perform $O(n^2)$ comparisons and swaps and is an $O(n^2)$ algorithm.

c. Bubblesort on $n$ keys of length up to $10000$ characters can perform $O(n^2)$ comparisons and swaps and is an $O(n^2)$ algorithm.

d. Bubblesort on $n$ keys of length up to $n$ can also perform $O(n^2)$ comparisons and swaps, but these in turn cost $O(n)$ bounded-time operations (comparison and move of single characters). Hence the algorithm complexity is $O(n^3)$.

Note that it would be wrong to say that a. or b. is faster than c., they just have the same asymptotic complexity. You don't know, and don't want to know if the machine processes faster integers or strings of $10$ characters than those of $10000$. (Imagine a special vector machine with registers holding $10000$ characters.)

---
Tags: time-complexity, asymptotics, reference-request, runtime-analysis, big-o-notation
---


# Question
Title: Prove that the subtree rooted at any node $x$ in a red black tree contains at least $2^{bh(x)} - 1$ internal nodes
To prove this, Introduction to Algorithms by Cormen et al., makes the assumption that the node has two children.

> For the inductive step, consider a node $x$ that has positive height and is an internal node with two children. Each child has a black-height of either $bh(x)$ or $bh(x) - 1$, depending on whether its color is red or black, respectively. Since the height of a child of $x$ is less than the height of $x$ itself, we can apply the inductive hypothesis to conclude that each child has at least $2^{bh(x) - 1} - 1$ internal nodes. Thus, the subtree rooted at x contains at least $(2^{bh(x) - 1} - 1) + (2^{bh(x) - 1} - 1) + 1 = 2^{bh(x)} - 1$ internal nodes, which proves the claim.

How does this extend to red black trees in general? The author defined red black trees using these five properties, none of which stops a black node from having only one child.

> A red-black tree is a binary tree that satisfies the following red-black properties:
>
> 1. Every node is either red or black.
> 2. The root is black.
> 3. Every leaf (NIL) is black.
> 4. If a node is red, then both its children are black.
> 5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

# Answer
> 1 votes
You can check your reference, but every internal node (node with assigned key), with no internal child/children is by default has leaf node (NIL) as child/children.

---
Tags: trees, binary-trees, red-black-trees
---


# Question
Title: CFG for the given language $L = \{~ a^\ell a^n b^m c^m d^n e^\ell ~|~ \ell,n,m \geq 0 \}$
I am writing this CFG to solve the problem:

$S \to ASBSC$

$A \to aAe ~|~ ε$

$B \to aBd ~|~ ε$

$C \to bcC ~|~ ε$

Is this correct or not?

# Answer
Strings in your grammar could potentially terminate with a sequence of $bc$s because of the following, which is not desired.

$S \rightarrow ASBSC$

$C \rightarrow bcC \ | \ \epsilon$

---

The correct grammar in this case would be:

$S \rightarrow aSe \ | \ A \ | \ \epsilon$

$A \rightarrow aAd \ | \ B \ | \ \epsilon$

$B \rightarrow bBc \ | \ \epsilon$
> 0 votes

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


title: Why is this not a proof of P # NP

text:
# Question
Title: Why is this not a proof of P # NP
Suppose that there is a set of strings such that for each n there is at most one string |w| = n. For any given n there is a 50:50 chance that such a string exists. These string can be arranged in a lookup table such that the binary value of the string is interpreted as an index, the table entry indicates yes/no i.e. the existence or non-existence of the string.

Example:

```
string      existence

```

---

```
0000        no
0001        no
0010        yes
0011        no
1000        no
1001        no
1010        no
1011        no

```

In this example there is one string of length n = 4, namely '0010'. For some values of n the entries will be all 'no'.

Suppose further that some random process running in the background is filling these tables. A program P(n) is supposed to indicate if a string of length n exists. It is apparent that no polynomial algorithm can always correctly answer the question as the existence/non-existence of a given string is completely random. It can query only n^c entries, for some c, of all the 2^n entries. However an NP program can query all the entries in the table in parallel.

Why is this not a proof that P # NP?

# Answer
Polynomial time means a runtime that is a polynomial in the length of the input. The input is an encoding of the problem instance as a sequence of symbols from some finite alphabet. A problem that is solvable in polynomial time with respect to one encoding may not be with respect to another. (Technically the encoding is part of the problem statement, so those are two different problems, but they tend to be conflated in informal descriptions.)

You need to encode your table as a sequence of symbols. For example, it could be encoded as `NNYNNNNN`.... But then the problem is solvable in polynomial time—linear time, in fact—by scanning the input looking for the symbol `Y`. You could also encode it as a list of strings that exist in the table, but then the problem is again solvable in polynomial time, though the method is different.

If you could come up with an encoding for which you could show that a polynomial-time solution is impossible, but a parallel (angelically nondeterministic) solution is possible, then you really would have shown that P≠NP, but it is not so easy to do that. It's not good enough to make the relationship between the input and the table so complicated that you can't think of any efficient way to solve the problem. You have to prove that there is no way to do it that you haven't thought of.
> 3 votes

---
Tags: complexity-theory, time-complexity, polynomial-time
---


# Question
Title: The book says 27 terminals but I only see 10. Where are they?
On page 103 of Mike Sisper's Introdution to Theory of Computation, it says that the grammar has 27 terminals (26 being the letters of the English Alphabet and 1 being the space character) but in the rules above, I don't see those 27 terminals. I only see 10 which are "a", "the", "boy", "girl", "flower", "touches", "likes", "sees", and "with".  So my question is, what does the book mean? Is this an error?

# Answer
The author defines terminals in the following way.

> The string consists of variables and other symbols called terminals.

When you are writing grammar for a human language, it is better to treat letters as symbols rather than words (sequence of letters) which although correct tend to be in thousands. One concern remains which is generation of new nouns. How would generate X Æ A-12 in the latter case, unless you are constantly updating the massive corpus, that you call the alphabet?

$G\_2$ is however just a toy example spanning a small fragment of the English language, in which case $\Sigma\_1$ = {a, the, boy, girl, flower, touches, likes, sees, with, ␣} would be as fine as $\Sigma\_2$ = {a, b, $\ldots$ , z, ␣} if not more.
> 1 votes

---
Tags: computability, automata, context-free, formal-grammars, pushdown-automata
---


# Question
Title: Modify Turing’s proof of the undecidability of the halting problem
Modify Turing’s proof of the undecidability of the halting problem to show there is no Turing machine P with the following two properties:

* For all Turing machines M, if M() accepts then P(⟨M⟩) accepts, while if M() rejects then P(⟨M⟩) rejects.
* P(x) halts for every input x. (In other words, if M() runs forever, then P(⟨M⟩) can either accept or reject, but it cannot run forever.)

Hey how can I address this question using the original proof of undecidability. The proof needs to be done using a Turing machine that is a decider. But the behavior of P isn't specify when it is looping forever, it can either accept or reject. That's the part I'm confuse about.

# Answer
> 1 votes
### A proof of the halting problem

Here is a proof for undecidability of the halting problem.

Towards a contradiction, suppose there is a Turing machine (TM) $H$ such that for all TMs $M$ and all strings $w$, $H(\langle M, w\rangle)$ will output string "HALT" if $M(w)$ halts while $H(\langle M, w\rangle)$ will output string "RUN FOREVER" if $M(w)$ runs forever.

We construct a machine $G$ such that for all TMs $M$, $G(\langle M\rangle)$ does the following two steps.

1. The simulation step.
Simulates $H(\langle M, \langle M\rangle\rangle)$, which will output either "HALT" or "RUN FOREVER"
2. The negation step.
If the output is "HALT", runs forever.
If the output is "RUN FOREVER", halts.

Let us run $G(\langle G\rangle)$. There are two possible result of the simulation step.

* The simulated $H$ outputs "HALT".
Then in the negation step, $G$ will run forever.
Hence the entire run of $G(\langle G\rangle)$ ends up with running forever. By the assumption on $H$, $H(\langle G, \langle G\rangle\rangle)$ should output "RUNS FOREVER". However, the simulated $H$ outputs "HALT".
* The simulated $H$ outputs "RUNS FOREVER".
Then in the negation step, $G$ will halt.
Hence the entire run of $G(\langle G\rangle)$ ends up with halting. By the assumption on $H$, $H(\langle G, \langle G\rangle\rangle)$ should output "HALT". However, the simulated $H$ outputs "RUNS FOREVER".

There is a contradiction in both cases.

### A proof of the nonexistence of $P'$

Towards a contradiction, suppose there is a TM $P'$ with the following two properties.

1. For all TMs $M$ and all strings $w$, if $M(w)$ accepts then $P'(\langle M,w\rangle)$ accepts, while if $M(w)$ rejects then $P'(\langle M,w\rangle)$ rejects.
2. $P'(x)$ either accepts or rejects for every input $x$.

We construct a machine $Q$ such that for all TMs $M$, $Q(\langle M\rangle)$ does the following two steps.

1. The simulation step.
Simulates $P'(\langle M, \langle M\rangle\rangle)$, which will either accept or reject.
2. The negation step.
If the simulated $P'$ accepts, rejects.
If the simulated $P'$ rejects, accepts.

Let us run $Q(\langle Q\rangle)$. There are two possible result of the simulation step.

* The simulated $P'$ accepts.
Then in the negation step, $Q$ will reject.
Hence the entire run of $Q(\langle Q\rangle)$ ends up with rejecting. By the assumption on $P'$, $P'(\langle Q, \langle Q\rangle\rangle)$ should reject. However, the simulated $P'$ accepts.
* The simulated $P'$ rejects.
Then in the negation step, $Q$ will accept.
Hence the entire run of $Q(\langle Q\rangle)$ ends up with accepting. By the assumption on $P'$, $P'(\langle Q, \langle Q\rangle\rangle)$ should accept. However, the simulated $P'$ rejects.

There is a contradiction in both cases.

---

The proof above is basically the same as the first proof. The difference is that "HALT" and "RUNS FOREVER" are replaced by "accept" and "reject".

### The nonexistence of $P$

The nonexistence of $P'$ above implies the nonexistence of $P$ as stated in the question.

I will leave this implication for you to work out.

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


title: Interesting applications of union-find

text:
# Question
Title: Interesting applications of union-find
I've been trying to find interesting applications of union-find that are lesser known. Here are some popular algorithms based on union-find that I know:

* Kruskal's algorithm for MST
* Tarjan's off-line lowerst common ancestors (LCA) algorithm
* Solving range minimum queries using union-find by reduction to LCA (with $O(m+n)$ bound given by \[Tarjan & Gabow '83, see \]
* Finding connected components
* Various textbook examples

**Question**: What are some interesting use-cases of union-find inside a larger, more complicated algorithm that are lesser-known?

# Answer
> 2 votes
Here are two additional interesting uses of union find in formal methods and programming languages, that are perhaps lesser-known at an undergraduate level.

* Decision procedure for the quantifier free fragment of theory of equality for uninterpreted functions in Satisfiability Modulo Theory (SMT) solving (https://www.cs.utexas.edu/~isil/cs389L/lecture11-6up.pdf). In this particular case, we are given (quantifier-free) logical formulas that range over constant symbols, (possibly uninterpreted) function symbols, and equality. We are asked to decide whether such a formula is satisfiable.
* Tarjan's algorithm for dominator tree construction and path expression computation over a directed graph (https://dl.acm.org/doi/pdf/10.1145/322261.322273) all use ideas or variants of the union-find data structure.

The bottom line is, in each case above we seek to partition some particular set of elements into equivalence classes. Union-find is very effective in keeping track of the equivalence class each object belongs to and updating such information.

---
Tags: algorithms, data-structures, reference-request, union-find
---


title: pumping lemma misunderstanding

text:
# Question
Title: pumping lemma misunderstanding
given this information of a language I need to determine if the language is regular or not:

I thought to Assume by way of contradiction that L6 satisfies the conditions of the pumping lemma. Let p be the pumping constant. Consider the word w = 0^(P-1)1... Clearly w ∈ L6. Thus, by the pumping lemma, there exist x, y, z ∈ Σ^\* such that w = xyz, |xy| ≤ p, |y| \> 0 where: x = 0^m,
y =0^(p-1-m)1,z = etc, the part that left of t he word. if we take i = 1000 for example we get that xy^1000z not in L because we get the following expression: 000000(00000...001)^1000...z (not in L6), but the solution that provided to similar question shows this:

where am I wrong in my attitude to the question?

# Answer
> 1 votes
The language is regular because of the restriction $i\_2 \< 99$ which makes everything finite. Once you have 99 initial zeroes, it doesn't matter how many more you have. So the pumping lemma isn't going to help. There are a few ten thousand states. Try figuring out what they are.

---
Tags: pumping-lemma
---


# Question
Title: Execution of instruction in MIPS on various parts of the clock cycle
I've recently learnt the execution of MIPS instruction set using single cycle processor. However I'm not getting one thing. Since one clock cycle is needed for the complete instruction we only have one positive clock edge. When the clock is made high on the first time in this rising PC value is written but we may have other write operations also like Reg Write or Mem Write. But the rising edge is gone and we've to wait for the next cycle to write. So how in one cycle both writes are possible for a single instruction ?

# Answer
> 0 votes
A single clock signal can trigger many, many independent actions. And the processor is pipelined, which means in one cycle it will execute different parts of different instructions.

---
Tags: computer-architecture, mips
---


# Question
Title: Why does the non-adjacent sum problem have optimal substructure?
In my algorithms class, my professor presented the problem of finding the largest sum of non-adjacent elements in an array. For example, if we have $\[1,4,3,8,5\]$ the largest sum of non-adjacent elements is $4 + 8 = 12$. My professor said we can solve this problem via dynamic programming since it exhibits optimal substructure.

However, I don't understand why this is true. From what I understand, a problem exhibits optimal substructure if an optimal solution can be found by combining optimal solutions to its subproblems. For example, the problem of finding the shortest path between two vertices $A$ and $C$ in a graph has optimal substructure since if $A\rightarrow B \rightarrow C$ is the shortest path from $A$ to $C$, $A \rightarrow B$ is the shortest path from $A$ to $B$.

Why does this apply to the above subproblem? Consider finding the largest sum of non-adjacent elements in $\[1,2,3,4,5\]$. The optimal solution is $1 + 3 + 5 = 9$, but the optimal solution to $\[1,2,3,4\]$ is $2 + 4 = 6$. So the optimal solution to the subproblem of the $4$ element array is not used to construct the optimal solution to the $5$ element array. Is there something I'm missing here?

# Answer
Notice that if in your 5 element array, if the last element is 0 or 1, then the optimal solution will be the optimal solution for your example 4 element array.

My point here is that the largest sum in $A\[0,..., n-1\]$ will either be $A\[n-1\]$ plus the largest sum in $A\[0,..., n-3\]$ (we skip $A\[n-2\]$ since it is adjacent to $A\[n-1\]$) or it's the largest sum in $A\[0,..., n-2\]$ (here we choose to skip $A\[n-1\] $). As you can see, the solution is dependent on the solutions of two sub-problems. We will choose whichever of the two yields a larger sum.
> 1 votes

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


# Question
Title: Do reductions (in NP and other classes) follow a linear path?
NP has several complete problems, which reduce to one another. In this sense, they are all "equal" in terms of hardness.

There are other problems in NP that are also "equal" to one another; for example, all the languages containing only a single string are equal. All of these are in P as they are finite.

Let's define a set, $G$, where every entry is a symbol that represents a set of equal problems (in NP). For example, one of the entries can be the set of NP-complete problems. Another can be the set of languages with just a single string.

Is there always an ordering of $G$ where every consecutive entry reduces to the next? This is the sense of the word "linear" I am using in my question's title.

# Answer
If P is not equal to NP there exists an infinite number of pairwise incomparable NP intermediate problems.

https://doi.org/10.1016/0020-0190(82)90113-2
> 3 votes

---
Tags: np-complete, reductions, np
---


# Question
Title: Ranked voting method where unranked candidates on a preference list aren't taken to be the least preferred?
Say there are 5 candidates, A, B, C, D, and E. An election is held using a ranked voting method. That is to say, each voter submits a preference list (the order in which they prefer candidates). E.g. A \> B \> C \> D \> E could be my preference list.

For most election schemes, a voter is allowed exclude candidates from their preference list. This usually means that the excluded candidates are their least preferred (with no particular preference between them). E.g. A \> B \> C implies that both D and E are equally worse than all the other candidates. I will call this the **Bottom Interpretation (BI)**.

However, I think there's another plausible reason one should be able to exclude a candidate: if they are not familiar with that candidate, and therefore do not know how much they prefer it with respect to the candidates they do know. For example, if D and E are movies I haven't watched, then I want excluding them from my list (A \> B \> C) to signify that they could potentially be ranked anywhere in my list, not necessarily at the bottom. I will call this the **Partial-Ordering Interpretation (POI)**.

Is there any election scheme that uses **POI** when deciding its winner/ordering for the candidates? For an example of what a election scheme that does this should look like:

* 99 voters say A \> B \> C \> D, leaving out E
* 1 voter says that E \> A, leaving out the rest

In this case, a scheme that uses **POI** will decide upon a final ordering of E \> A \> B \> C \> D. On the other hand, a scheme like instant-run-off voting (IRV) will decide on a final ordering of A \> B \> C \> D \> E, because IRV uses **BI**..

# Answer
I think I realized an answer. The Schulze Method traditionally uses **BI**. But it can be easily modified to use **POI** instead. All that needs to be done is, when counting how many pairwise preferences there are for candidate A over B, instead of using **BI** (unranked = preferred less), you use **POI** (unranked = no preference). Then the rest of the computation goes on as normal.
> 0 votes

---
Tags: sorting, permutations, partial-order, ordering, voting
---


# Question
Title: Generalization of computability to continuous for loops?
A computable function, formulated in the sense of mu recursion, can compute a for or do loop over some (possibly infinite) integer range.

I was wondering if a suitable generalization exists that allows the computation of a real-domain function $f$ where $f(x)$ can be calculated given the values of $f(y)$ for all real $y\<x$. This seems natural to ask, given that it is relevant if you want to describe e.g. a real-world physical system as an algorithm.

# Answer
> 3 votes
First of all, despite claims by several people here, there are models of computation which support computation on topological spaces. The "countable vs. uncountable" distinction is a red herring, arising from being familiar only with notions of computation on discrete spaces. A good introductory text on the topic of computable analysis is Klaus Weihrauch's Comuptable analysis – an introduction.

Your idea is very closely related to the principle of **open induction**, which states: if an *open* subset $S \subseteq \[0,1\]$ satisfies $(\forall y \in \[0,1\].\\, y \< x \Rightarrow y \in S) \Rightarrow x \in S$ then $S = \[0,1\]$. In words: if an open $S$ has the property "if all numbers smaller than $x$ are in $S$ then so is $x$" then $S$ is the whole interval.

It is easy enough to speculate a functional version of open induction, which we could call **open recursion** (caveat – I am speaking off the top of my head here): given a map $$h : \Pi (x : \[0,1\]) \\, (f : \[0,x) \to \mathbb{R}) .\\, \Sigma (\epsilon \> 0) (g : \[0, x + \epsilon) \to \mathbb{R}) . \\, g{\restriction}\_{\[0,x)} = f$$ there is a unique map $\mathcal{O} h : \[0,1\] \to \mathbb{R}$ such that $ \mathcal{O} h (t) = h \\, t \\, ((\mathcal{O} h){\restriction}\_{\[0,t)}) $ for all $t : \[0,1\]$, where $f{\restriction}\_{\[0,t)}$ is the restriction of $f$ to the interval $\[0,t)$.

The principle of open induction holds in classical mathematics (exercise), from which it follows that open recursion is valid as well (another exercise). That is, the notation $\mathcal{O} \\, h$ is well-defined for any $h$.

Now, the interesting question is whether we can *compute* with open recursion. In An induction principle over real numbers explained how to compute with open induction. I am fairty sure that her method can be adapted to open recursion, but it would take more time to write up the details than I can invest in answering this question. I would be very interested to hear, however, if my hunch is correct.

# Answer
> 0 votes
AFAIK, there are no modelizations of physical systems with functions of infinitely many independent variables (which would be your generalization of *complete induction*, I guess).

Instead, models that predict the current value of a continuous signal based on previous "samples" (and some smoothness property) evoke ordinary or partial differential equations. These are solved by analytical techniques when possible using symbolic integration, for which we do have discrete algorithms, or by numerical methods, for which we also have discrete algorithms.

---
Tags: turing-machines, computability, church-turing-thesis, physics, mu-calculus
---


# Question
Title: Given a boolean circuit that computes a boolean function, can we always find an equivalent circuit with optimal size?
Let's say that we have a decision problem $P$. Let's also say that $I\_n$ is the set of all instances of size $n$ that exist for this problem, and that its cardinality is finite.

There is a sequence of bits that uniquely represents each instance (of that size) of the problem. Each of these sequences has $b(n)$ bits (for the sake of simplicity, let's say that $b$ is a linear function, but it could also be polynomial, exponential or even double exponential, depending on the problem). We could say, for example that all instances of size 4 are represented with 8 bits, instances of size 5 are represented with 10 bits, etc... The bits are completely independent of each other: there are no cases in which any information about the value of a bit can be obtained from another bit. Also, for each configuration of those bits, there is a corresponding instance of the problem. There are no two configurations which represent the same instance of the problem and there is no configuration that does not represent a problem. So, let's say that there is a bijection between configurations of those $b(n)$ bits and instances of size $n$. We had previously said that the cardinality o $I\_n$ is finite, but now we can even say that $|I\_n| = 2^{b(n)}$, since that is the number of possible configurations for a sequence of $b(n)$ bits, and each configuration corresponds to an instance of the problem.

For each $n \in \mathbb{N}$, there exists a circuit $C\_n$ that receives $b(n)$ bits as its input and outputs the result ($1$ for **YES**, $0$ for **NO**) of the corresponding instance of problem $P$. I don't know if it is relevant to my question, but these circuits use only $AND$ and $OR$ gates. Also, let's say that "creating"/"describing" the circuit for size $n$ can be done in $O(n)$ for this particular problem $P$.

My question is: **Given the circuit $C\_n$ can we find an equivalent circuit $C^{\prime}\_n$ which is optimal, or can we derive some information about the circuit complexity of the problem $P$?** In this context we will say that a circuit is optimal if it has the least possible number of gates that is required to compute the corresponding boolean function.

My instincts tell me that we should be able to use Quine-McCluskey to find an optimal equivalent circuit (even if doing so would be unfeasible for large $n$), and that we could establish lower bounds for the circuit complexity of the problem $P$ by looking at the way in which the size and depth of the circuit $C^{\prime}\_n$ changes as $n$ increases. However, it also seems like this would be "too easy" and that there must be a reason why it does not work that way.

# Answer
The problem is $\Sigma\_2^P$-complete, which means that it is hard -- it is even "harder" than NP-complete problems. In particular, there is unlikely to be any polynomial-time algorithm. See https://en.wikipedia.org/wiki/Logic\_optimization#Boolean\_expression\_minimization.

However, there are many heuristic methods. See https://en.wikipedia.org/wiki/Logic\_optimization.
> 1 votes

---
Tags: complexity-theory, optimization, circuits, lower-bounds, boolean-complexity
---


# Question
Title: Halting problem unsolvability leads to a contradiction - where's the mistake?
You are all familiar with the halting problem so I won't repeat it.

Suppose $H$ is a Turing machine which takes as input an encoding of another Turing machine $M$, then searches all possible proof strings until it finds a proof that $M$ halts or a proof that $M$ does not halt. *Of course, if there is no such proof then it will search forever, so I do not claim that $H$ decides the halting problem.*

Suppose $Q$ is the usual counterexample that first invokes $H$ on $Q$ as a subroutine (this is possible using quine techniques). Then if $H$ reports that $Q$ doesn't halt, it halts. If $H$ reports that $Q$ does halt, it enters a trivial infinite loop.

Now consider what the subroutine $H$ returns. If $H$ would report that $Q$ would halt, that would mean it had found a specific proof that $Q$ would halt, despite the fact that $Q$ obviously would not halt and we could see it enter a trivial infinite loop after a finite number of steps. Assuming that the proof system is consistent, we can be certain that there is no proof that $Q$ halts. Likewise, we can be certain that there is no proof that $Q$ does not halt.

Since there is no proof that $Q$ halts and no proof that $Q$ does not halt, we can be certain that $H$ will never find either one, therefore the $H$ subroutine of $Q$ will continue searching proofs forever, QED. We have proved that $Q$ does not halt.

***Wait, what?*** The fact there is no proof gives a proof. Of course, if there is a proof, that proof is wrong. What's going on here? Where is the error in my reasoning?

(Credits to raoof for the "proof" sketch)

# Answer
This is a very natural question, and it hinges on a logical subtlety: when you describe the machine $H$'s behavior as

> search\[ing\] all possible proof\[s\] until it finds a proof that $M$ halts or a proof that $M$ does not halt,

what exactly do you mean by "proof"? The only way you derive a contradiction is if there is some system $T$ such that (i) by "proof" you mean "proof in $T$" and (ii) the argument of your post goes through in $T$. However, one crucial assumption you've made about proofs in your post is that they are **correct**: we never prove false halting or non-halting facts. This means that the argument of your post **can't** go through in the same theory that it implicitly talks about, by (a consequence of) Godel's second incompleteness theorem. So you don't get a contradiction at all.

At the end of the day, what you're essentially doing is proving that the halting problem is **creative**.

---

The following might help clarify the situation. Let $T$ be a "reasonable" theory (e.g. any consistent r.e. extension of Robinson arithmetic), and let $A\_T,B\_T$ be the "$T$-solvable parts" of the halting problem: $A\_T$ is the set of machines $T$ proves halt, and $B\_T$ is the set of machines $T$ proves don't halt. Then we have:

* $A\_T$ and $B\_T$ are disjoint r.e. sets, and the halting problem is a proper subset of $A\_T$.
* If $T$ is $\Sigma\_1$-sound, then $A\_T$ is exactly the usual halting problem.
* Meanwhile, since Robinson arithmetic is $\Sigma\_1$-complete, we have by mere consistency of $T$ that $B\_T$ is disjoint from the true halting problem.
* But **(almost) none** of the above is provable in $T$ itself, since $T$ doesn't even know that $T$ is consistent.
> 1 votes

# Answer
> Of course, if there is no such proof then it will search forever.

This is your mistake: since we permit $H$ to loop forever, the language accepted by $H$ is recognizable but not necessarily decidable. The conventional proof is that Halting Problem is undecidable – that no $H$ exists that can accept or reject any input TM in finite time.

The existence of the Universal Turing Machine proves the Halting Problem to be recognizable, as one can simply simulate any input TM and accept the ones that halt in finite time.
> -2 votes

# Answer
The "halting problem" is about finding a Turing machine X that DECIDEs whether another Turing machine Y halts with input Z, for every Y and Z. You were instead talking about a Turing machine that RECOGNIZEs whether another Turing machine halts. That is a very different problem. And building a halting recognizer is trivial and doesn't lead to conflicts (well, it's an awful lot of work to build it, but not difficult).

For a DECIDER to exist, it must be true that for every Turing machine Y and input Z either there is a proof that Y halts on input Z, or there is a proof that Y doesn't halt on input Z. And that isn't true.
> -2 votes

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


# Question
Title: Faster finding of a subset of bits with all combinations in the bitstrings
Assume that I have a bunch of bitsets (strings on $\\{0,1\\}$) of the same length, e.g.:

```
101110001
001001101
010101010
101001001
101010101

```

I want to find the largest set of bits (indices, not necessarily consecutive) that takes all possible values in these bitsets. In the example above:

```
101|11|0001
001|00|1101
010|10|1010
101|00|1001
101|01|0101

```

the fourth and the fifth bits take all possible combinations `00` (2nd bitset), `01` (5th), `10` (3rd), `11` (1st), so they fit. Clearly, there is no set of bits of length $3$ that takes all possible values (in this case, we only have 5 bitsets, so it's impossible to get $2^3=8$ combinations), so bits $4$ and $5$ answer the question.

I have a lot of bitstrings ($3 \cdot 10^7$) and bits ($100$), and the answer has $\approx 10$ bits, so brute force is out of the question. Based on how the bitstrings are generated, there is a lot of permutational symmetry, so some simple prunings (e.g. if bit $i$ only takes value $1$ (and never takes value $0$), then we never consider any set of bits containing $i$) probably won't work. What can I do?

As an easier version, I'm also interested in the case when there are $3 \cdot 10^5$ bitstrings, $60$ bits, and the answer is $\approx 8$. For this, I'm currently running the bruteforce, and, assuming that the answer is $8$, I expect that computation to finish in a few days (I know that there is a set of size $8$, and I expect and need to show that there is no set of size $9$).

# Answer
> 1 votes
This problem sounds very hard, especially at the scale you're dealing with.

One approach might be to try using a SAT solver. I don't know whether this will be even remotely feasible to solve with SAT, but you could give it a try.

Let boolean variable $x\_{j,k}$ represent whether bit index $j$ is the $k$th one selected (for $j=1,\dots,60$ and $k=1,\dots,8$). Let $y\_{s,\ell}$ (for $s \in \\{0,1\\}^8$ and $\ell=0,\dots,\lg(3 \cdot 10^5)$) be boolean variables defined so that $y\_{s,0},\dots,y\_{s,\lg(3 \cdot 10^5)}$ is the binary representation of an integer $i$ so that the $i$th bitstring has the value $s$ in the selected indices (as determined by the $x$'s).

You can write CNF clauses that represent the conditions for $x,y$ to represent a valid solution to your problem. In particular:

* For each $k$, exactly one of $x\_{1,k},\dots,x\_{60,k}$ is true. (This can be expressed in CNF; see Encoding 1-out-of-n constraint for SAT solvers .)
* For each $j,j',k,k'$ with $j\ge j'$, $k\<k'$, add the clause $\neg x\_{j,k} \lor \neg x\_{j',k'}$.
* For each $s,i,k$, add the CNF clause

$$(y\_{s,0} \ne i\_0) \lor \cdots \lor (y\_{s,\lg(3 \cdot 10^5)} \ne i\_{\lg(3 \cdot 10^5)}) \lor \bigvee\_j x\_{j,k}$$

where $i\_0,\dots,i\_{\lg(3 \cdot 10^5)}$ is the binary representation of $i$ and $j$ ranges over all bit indices such that the $j$th bit of the $i$th bitstring is equal to $s\_k$. Notice that each term of the form $(y\_{s,\ell} \ne i\_\ell)$ takes either the form $y\_{s,\ell}$ or $\neg y\_{s,\ell}$ according to whether $i\_\ell$ is 0 or 1, and thus is a known literal in either case, so this does indeed have the form of a CNF clause.

Now run a SAT solver on this problem instance. This will try to find a combination of 8 bit positions that is a valid solution. Of course if you try a solution with 8 bit positions, you can next try to find one with 9 bit positions, etc., and if you don't find a solution with 8 bit positions, you can next try to find one with 7 bit positions, etc., iterating to find the maximum number of achievable bit positions.

For your smaller problem instance, we'll obtain a CNF formula with about $2^8 \times 3 \cdot 10^5 \times 8 \approx $ 600 million clauses and about 632 variables. Each clause will have about 49 literals in it, on average. This is a monstrously large CNF formula, so I don't know whether a SAT solver will have any hope of finding a satisfying assignment for it, but you could try and see.

---
Tags: combinatorics, bit-manipulation
---


# Question
Title: Why aren't promise problems just decision problems; can't we encode the promised inputs in the alphabet?
I don't really understand why promise problems are classified differently than decision problems.

Consider this problem as an example. Given some real number between $0$ and $1$, determine if it greater than $\frac{1}{2}$ or not.

In this problem, that the real number is between $0$ and $1$. Let's say our alphabet is $\\{0, 1, 2\\}$. Then we can say that our input is encoded like so:

> $0$ represents $0$, $1$ represents $\frac{1}{2}$, and $2$ represents $1$

From these 3 cases, we can define any input to represent

$$ \frac{1}{n} \sum\_{i=1}^{n} R(x\_i) $$

where $x\_i$ represents the letter at index $i$ of the input, and $R$ is the transformation that takes $0$ to $0$, $1$ to $\frac{1}{2}$, and $2$ to $1$.

So what is the need to define "Promise-Problems?"

# Answer
> 2 votes
In the example you've given it's simple to encode inputs such that they must satisfy the promise. However, in many cases it's hard to do that. Look at the following promise problem, for example: given a SAT instance which has either 0 or 1 solutions, return YES iff it has a single solution.

If there is some encoding for that promise which has polynomial length, can produce all possible inputs for the problem, and can be parsed in polynomial time, then for a given SAT instance, you could add a single trivial solution to it, and an encoding which produces that would be a coNP certificate for the SAT instance, which is impossible assuming $\text{NP}\neq\text{coNP}$.

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


# Question
Title: context-free shuffle for two-letter alphabets
The operation of shuffle takes two words and merges their symbols, keeping the symbols of each of the strings in the right order. It can be recursively defined by $x \parallel \varepsilon = \varepsilon \parallel x = x$ and $ax \parallel by = a (x \parallel by) \cup b (ax \parallel y)$. Here $a,b\in \Sigma$ and $x,y\in \Sigma^\*$. For languages $K\parallel L = \bigcup\_{x\in K, y\in L} x\parallel y$.

It is known that the context-free languages are *not* closed under shuffle. An interesting question is raised in a recent arxiv overview paper *Decision Problems on Copying and Shuffling* 2302.06248 by Halava etal. Do we need more than two symbols for a counter example for shuffling two context-free languages?

> **Problem 6.** Give an example of two context-free languages $L\_1, L\_2 \subseteq \\{ a, b \\}^\*$ such that $L\_1 \parallel L\_2$ is not context-free.

# Answer
> 5 votes
Two letters should be sufficient as the following example shows: let $L\_1=\\{a^nba^n\mid n\geq1\\}$ and $L\_2=\\{b^nab^n\mid n\geq1\\}$. Then we have $$(L\_1\\|L\_2)\cap a^\*b^\*a^\*b^\*=\\{a^mb^{n+1}a^{m+1}b^n\mid m,n\geq1\\}\\,.$$ This equation holds, since we can only map the letters of a word from $L\_1\subseteq a^\*ba^\*$ to the first three blocks of $a^\*b^\*a^\*b^\*$ and, similarly, the letters of a word from $L\_2\subseteq b^\*ab^\*$ to the last three blocks.

The right-hand side of this equation is not context-free. Since the intersection of a context-free language with a regular language always is context-free, the language $L\_1\\|L\_2$ cannot be context-free.

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