# Question
Title: (Numerical Analysis) What is the largest double float represented for the gamma function and $n!$
Consider that \begin{align} \Gamma(n+1) = n! \end{align} for any integers. I then got the following two questions:

1. What is the largest value of $n$ for which $Γ(n+1)$ and $n!$ can be exactly represented by a double-precision floating-point number?
2. What is the largest value of $n$ for which $Γ(n+1)$ and $n!$ can be approximately represented by a double-precision floating-point number that does not overflow?

So I have been working on this question for some time now but I do not seem to be satisfied by my own answer. My thoughts so far on (1.) is that since we start getting non representable integers after $2^{53}$ my initial guess would be the largest $n$ such that $n!=\Gamma(n+1)\<2^{53}$. I found this value to be $n=18$ through MatLab simulations, I do wonder though if there are still some precisely represented for $n\>18$, and how would I go about testing that?

I have run $\Gamma(n+1) - n!$ for several $n\>18$ and they start getting some serious errors but only after $n=22$. It makes intuitive sense to me that the gamma function should produce more errors as it is a an approximation of an integral, but how am I to know that $23!$ is not also represented?

I also considered finding zeros for $$0=n! - (1+f)\cdot2^e$$ w.r.t $f$, note that $(1+f)$ is the mantissa and $2^e$ is the radix, such that the second term is in fact the positive normalized representation of the double float. My thought is that it would only be able to find a zero in case $f$ was a representable as a double float, however, I figured that this could not be done like this as $n!$ would always be either true or a rounding to a double float, so in any case MatLab would always be able to find a representable $f$ that produced a zero.

I am not sure how to continue with this exercise, any good pointers?

# Answer
> 0 votes
Nice one. Using the standard ieee 754 double precision floating point format, we can exactly represent integers less than $2^{53}$, multiplied by a power of 2. When we try to find the largest n where n! can be represented that way, then for example the factor 12 of 12! equals $3 \cdot 2^2$. If my calculator gets it right then the largest n is 22, with $22! ≈ 1.124 \cdot 10^{21}$; 22! has the factor $2^{19}$, and $22! / 2^{19} \< 2^{51}$.

# Answer
> 0 votes
Consider the table below, showing naturals and the binary representation of their factorial with trailing bits stripped off.

IEEE single/double/quadruple precision are able to represent $13!$/$22!/37!$ exactly.

$$\begin{array} &0! & 1 & 1 \\ 1! & 1 & 1 \\ 2! & 1 & 1 \\ 3! & 2 & 11 \\ 4! & 2 & 11 \\ 5! & 4 & 1111 \\ 6! & 6 & 101101 \\ 7! & 9 & 100111011 \\ 8! & 9 & 100111011 \\ 9! & 12 & 101100010011 \\ 10! & 14 & 11011101011111 \\ 11! & 18 & 100110000100010101 \\ 12! & 19 & 1110010001100111111 \\ 13! & 23 & 10111001100101000110011 \\ 14! & 26 & 10100010011000011101100101 \\ 15! & 30 & 100110000011101110111011101011 \\ 16! & 30 & 100110000011101110111011101011 \\ 17! & 34 & 1010000110111111011101110110011011 \\ 18! & 37 & 1011010111110111011001100101001110011 \\ 19! & 41 & 11011000000101011100100110000011010001001 \\ 20! & 44 & 10000111000011011001110111110010000010101101 \\ 21! & 48 & 101100010100000111011111010011011010111000110001 \\ 22! & 51 & 111100111011101010010011000010101100111110000011011 \\ 23! & 56 & 10101111001011100001100110101111110001010010011001101101 \\ 24! & 58 & 1000001101100010100100110100001111010011110111001101000111\\ \cdots\end{array}$$

---

Regarding the non-overflowing value, it suffices to accumulate the base-2 logarithms of the naturals until you reach $128/1024/16384$. This can be done by brute-force. We have

$$\begin{array} &\log\_234! \sim 127.79512061296911\\ \log\_2170! \sim 1019.3694529277266\\ \log\_21754! \sim 16378.090470312889\\ \end{array}$$ and larger values will overflow.

---

My old TI SR-56 supported factorials up to $69!$ (overflow at $10^{100}$).

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


title: Spatial embedding of graph

text:
# Question
Title: Spatial embedding of graph
Given a graph $(V,E)$, I'm interested in embedding it into a Euclidean space $\mathbb{R}^n$ such that each vertex $v\in V$ becomes a point $x\_v\in\mathbb{R}^n$ and $d(x\_v,x\_u) \leq 1$ (Euclidean distance) iff $(v,u) \in E$.

Is this embedding always possible given high enough dimension $n$? If so, given a graph, can we estimate the upper bound for $n$ (as a function of $|V|$, or something similar) such that the above embedding is possible?

# Answer
Your parameter is known as *sphericity*, first defined by Maehara, Space graphs and sphericity.

Maehara showed that every graph has such an embedding. Given a graph $G = (V,E)$, embed $x \in V$ into the $V$-indexed vector $v\_x$ given by $v\_x(x) = M$, $v\_x(y) = 1$ if $(x,y) \in E$, and $v\_x(y) = 0$ if $(x,y) \notin E$.

If $(x,y) \notin E$ then $\\|v\_x - v\_y\\|^2 \geq 2M^2$, considering coordinates $x,y$.

In contrast, if $(x,y) \in E$ then $\\|v\_x - v\_y\\|^2 \leq 2(M-1)^2 + |V|-2$.

When $M$ is large enough, $2M^2 \> 2(M-1)^2 + |V|-2$, and so we can normalize the vectors so that they satisfy your condition.

The minimum dimension needed to embed a graph is known as its *sphericity*.

Maehara, Dispersed points and geometric embedding of complete bipartite graphs later showed that the sphericity of the complete bipartite graph $K\_{n,n}$ is between $n$ and $\tfrac32 n$.

Some other results are cited in Bilu and Linial, Monotone maps, sphericity and bounded second eigenvalue.
> 13 votes

---
Tags: complexity-theory, graphs, np-hard, max-cut
---


# Question
Title: Maxcut problem of spatial embedding graphs
Given a graph $(V,E)$, I'm interested in embedding it into a Euclidean space $\mathbb{R}^n$ such that each vertex $v\in V$ becomes a point $x\_v\in\mathbb{R}^n$ and $d(x\_v,x\_u) \leq 1$ (Euclidean distance) iff $(v,u) \in E$.

I know that Maxcut isn't NP-hard for planar graphs. But what if I consider graphs that can be embedded as above in $\mathbb{R}^2$, do we know if Maxcut is NP-hard in this case? What about the above embedding in $\mathbb{R}^3$?

# Answer
> 2 votes
A graph with $d = 2$ representation is called a unit disk graph.

The max-cut problem on unit disk graphs is NP-hard \[1\], even if the planar representation is given as an input.

---
Tags: complexity-theory, graphs, max-cut
---


# Question
Title: Understanding proof that no DFA can recognize L with fewer than 2^k states
Let Σ = {a, b} and L = {ww | w ∈ Σ∗ and w is of length k}. Show that for each k, no DFA can recognize L with fewer than 2^k states.

What I understand is that we prove this by contradiction. Assume that L has less than 2^k states i.e L has 2^k -1 states. We then use the pigeonhole principle which would mean that two of these strings would have to be in the same state meaning that if we append a new string to both of these strings that are currently in the same state, these new strings should either both be accepted or rejected. This is where we want the contradiction. But the question is how to prove this mathematically?

If we take Wi and Wj two distinguishable string which ends at the same state q then after adding some string X, both WiX and WjX should end at the same state. But how can I prove that both does not end at the same state to get the contradiction?

# Answer
Alternatively, you can use Myhill–Nerode theorem.

For each $x, y \in \Sigma^k$, $x \ne y$, we have $x \not \sim\_L y$ because $xx \in L$ but $yx \notin L$. Therefore, we have $|Q(M)| \ge |\Sigma^\ast/{\sim\_L}| \ge |\Sigma|^k = 2^k$ for a DFA $M$.
> 1 votes

# Answer
You need to be more specific about what $2^k$ strings you are applying the pigeonhole principle to. This proof will not work with arbitrary strings e.g. in the case $k=4$, we have that $W\_i=aab$ and $W\_j=abb$ are different but neither is the prefix of a word in $\mathcal L$, so they might as well take you to the same state (one where no accepting state is reachable).

I take it that there are also restrictions on $k$ (it must be even), because in the case $k=3$ we have that $\mathcal L=\emptyset$ and $\emptyset$ can be recognised by a DFA with one state (a non-accepting state with a self-loop).

At some point you may need to bear in mind that $W\_i$ and $W\_j$ could be of different lengths.
> 0 votes

# Answer
So the answer is according to pigeonhole principle, two different strings end at the same state. Let say Wi and Wj end at the same state(say q). Since DFA don't have memory and only depend on the current state( and not on how the current state was reached), M will give the same answer(either accept or reject) on string WiU and WjU no matter what U is(where U is any string). Now if we find a string U such that WiU ∈ L and WjU ∉ L or vice versa then M gives the same answer(either both accept or reject) resulting in contradiction and proving M does not recognize L with fewer than %2^k% states
> 0 votes

---
Tags: automata, finite-automata, proof-techniques, mathematical-analysis
---


# Question
Title: most cost-effective route w.r.t. gas in a labelled graph
Consider a car that can hold gas to travel a distance of $c \in N$ kilometers (its capacity) on a full tank that's initially empty. The car starts in node $s \in V$ of a graph. Each vertex $V\_i$ of the graph has a gas station where the car can (not necessarily fully) refuel at price (i.e. cost) $p(V\_i) \in R\_{\>0}$ per kilometer. Each edge $E\_j$ has associated a distance $d\_j \in N (d\_j\le c)$ kilometers between its vertices. The goal is to travel to a target vertex $t$ at a minimum sum of costs for the refuels.

Question: Is this optimization problem polynomially solvable? Or is its decision version NP-complete?

To more formally express the cost (i.e. the objective function), we're looking for a path $P$ and an associated refueling schema $F$ where the $x$th vertex on the path is $V(P\_x)$ and the $x$th refueling on the path is $F\_x \in N$ so that the capacity constraint $c$ is met. The cost for refueling at vertex $V(P\_x)$ is then $p(V(P\_x))F\_x$. We are to minimize $\Sigma p(V(P\_x))F\_x$

I hope and think the informal formulation is straightforward and won't lead to ambiguities under normal interpretations (the car is not allowed to run out of gas before reaching a vertex), whereas a more formal problem statement might be tedious.

Obviously, another variant where not each vertex has a gas station can be reduced to this variant by contracting vertices without a gas station or by setting the price in such vertices high enough.

If we can answer this question, interesting further research might be how its variants behave, namely with graphs of fixed treewidth or allowing negative prices $p\_i$ or fractional distances $d\_j$. If we can't find a polynomial algorithm for the main problem, can we then find one that's superpolynomial (say exponential) only in the size of the capacity $c$? (i.e. polynomial in the value of $c$. Going ahead a bit too much, such might be a nice example of a parameterized algorithm).

# Answer
The problem is polynomial-time solvable.

A solution can be represented by a sequence of points $F = ((u\_1, f\_1), \dots, (u\_k, f\_k))$ where $u\_i$ is a vertex and $f\_i$ is the amount of refuel (possibly $0$) at the vertex. Also, let $b\_i$ be the gas amount before the refuel $i$, and $a\_i = b\_i + f\_i$ be the gas amount after the refuel.

We show that there is an optimal solution that, in every refuel, either the gas tank was empty before the refuel or the gas tank is full after the previous refuel. That is, $$\tag{\*} \forall 1 \le i \le k, \\; b\_i = 0 \lor a\_{i-1} = C$$ Proof: Suppose for the contrary, that the lexicographically smallest optimal solution doesn't satisfy the condition above. Let $i$ be the last refuel with a condition violation. There are two cases:

* Case $p(u\_{i-1}) \ge p(u\_i)$: we decrease the previous refuel and increase the current refuel by $b\_i \> 0$. The new solution is lexicographically smaller and the cost is equal to or better than the current solution, contradicting the assumption that the current solution is the smallest.
* Case $p(u\_{i-1}) \< p(u\_i)$: we increase the previous refuel and decrease the current refuel by $C - a\_{i-1} \> 0$. The cost of the new solution is better than the current solution, contradicting the assumption that the current solution is optimal.

Let $d\_{u,v}$ be the shortest path distance from $u$ to $v$ in the original graph. Define a graph $G'$ on vertices $\\{ (u, 0), (u, C) \mid u \in V \\}$ by edges: $$ \begin{align} e^1\_{u,v} &= ((u, 0), (v, 0), d\_{u,v} p(u)) & d\_{u,v} \le C \\ e^2\_{u,v} &= ((u, C), (v, C), d\_{u,v} p(v)) & d\_{u,v} \le C \\ e^3\_{u,w,v} &= ((u, C), (v, 0), (d\_{w,v} + d\_{u,w} - C) p(w)) & d\_{u,w}, d\_{w,v} \le C \le d\_{w,v} + d\_{u,w}\\ e^4\_u &= ((u, 0), (u, C), C p(u)) \\ \end{align} $$

1. $e^1\_{u,v}$: At $u$, refuel the amount just to make $v$, then move to $v$.
2. $e^2\_{u,v}$: Move from $u$ to $v$, then refuel to the full capacity.
3. $e^3\_{u,w,v}$: Move from $u$ to $w$, then refuel the amount just to make to $v$, then move to $v$.
4. $e^4\_u$: At $u$, refuel to the full capacity.

The answer is the shortest path distance from $(s, 0)$ to $(t, 0)$.

Proof: Let $((u\_1, f\_1), \dots, (u\_k, f\_k))$ be the optimal solution, satisfying the condition (\*).

We say a point $1 \le i \le k$ is a *stop* if $b\_i = 0 \lor a\_i = C$. For a stop $i$, define $c\_i = \begin{cases}0 & \text{ if } b\_i = 0 \\ C & \text{ otherwise}\end{cases}$.

Let $d(x,y)$ to denote the shortest distance from $x$ to $y$ in $G'$, and let $D\_i = d((u\_1, 0), (u\_k, c\_k))$. By induction, we prove $D\_k + (a\_k - c\_k) p(u\_k) \le \sum\_{i=1}^k f\_i p(u\_i)$, assuming the last point is a stop.

Proof sketch for each case:

* $b\_k = 0$ and $b\_{k-1} = 0$: Use $e^1\_{u\_{k-1},u\_k}$.
* $b\_k = 0$ and $a\_{k-2} = C$: First use $e^4\_{u\_{k-2}}$ if $b\_{k-2} = 0$. Then use $e^3\_{u\_{k-2},u\_{k-1},u\_k}$.
* $a\_{k-1} = C$ and $a\_k = C$: First use $e^4\_{u\_{k-1}}$ if $b\_{k-1} = 0$. Then use $e^2\_{u\_{k-1},u\_k}$.
> 1 votes

---
Tags: graphs, np-complete, dynamic-programming, polynomial-time, parameterized-complexity
---


# Question
Title: Difference Between Residual Neural Net and Recurrent Neural Net?
What is the difference between a **Residual** Neural Net and a **Recurrent** Neural Net?

As I understand,

Residual Neural Networks are very deep networks that implement 'shortcut' connections across multiple layers in order to preserve context as depth increases. Layers in a residual neural net have input from the layer before it and the optional, less processed data, from *X* layers higher. This prevents early or deep layers from 'dying' due to converging loss.

Recurrent Neural Networks are networks that contain a directed cycle which when computed is 'unrolled' through time. Layers in recurrent neural network have input from the layer before it and the optional, *time dependent* extra input. This provides situational context for things like natural language processing.

Therefor, a recurrent neural network can be used to generate a basic residual network if the input remains the same with respect to time.

Is this correct?

# Answer
> 4 votes
The answer is YES, they basically are the same according to this paper

The figure above shows how they compared both and how a ResNet can be reformulated into a recurrent form tat is almost identical to a RNN.
For more info you can read the paper and get deeper.

# Answer
> 0 votes
I believe this is true:

* **Recurrent neural networks (RNN)** generally refer to the type of neural network architectures, where the input to a neuron can also include additional data input, along with the activation of the previous layer. E.g. for real-time handwriting or speech recognition.
* **Residual neural networks (ResNet)** refer to another type of neural network architecture, where the input to a neuron can include the activations of two (or more) of its predecessors. E.g. for non-realtime handwriting or speech recognition.

So, there is a difference but maybe these implementations can be considered equivalent, especially if we are performing non-real-time data analysis.

---
Tags: neural-networks
---


# Question
Title: What is the time complexity of determining maximal overlaps between bitmap images?
Given two bitmap images (two arbitrarily sized two-dimensional matrices of integer values ranging from 0 to some maximum number), I want to determine their maximum overlaps.

An overlap is a relative positioning of the images (a translation of the second image) producing a nonempty intersection on which both images are the same.

For instance, the images $\left\langle \begin{bmatrix}0 & 1\\0 & 1\end{bmatrix}, \begin{bmatrix}1 & 1\\1 & 1\end{bmatrix} \right\rangle$ have overlaps $\\{ (1,-1), (1,0), (1,1) \\}$, with intersection sizes $1,2,1$, respectively, so only $(1,0)$ is maximal.

It seems to me we can create a fast algorithm based on generalizing suffix trees to "subimage trees", built with a floodfill algorithm.

Is this a viable approach? Is it better than alternatives?

Is this problem discussed in the literature? What is its time complexity?

(My apologies for asking several related questions at once.)

# Answer
For a pair of matrices $A, B$, $B$ maximally overlaps $A$ at a position if and only if certain two rectangular sub-matrices of $A$ and $B$ match.

It is not clear how to use the *two-dimensional suffix tree* for this problem, because this data structure can only process **square** sub-matrix matching queries.

An answer is to use the fingerprinting-based algorithm. By generalizing Rabin-Karp algorithm, any rectangular sub-matrix pattern matching query can be answered in constant time.

More specifically, a matrix $A \in \mathbb{Z}^{n \times m}$ is represented by a fingerprint $h(A) = \sum\_{i=1}^n \sum\_{j=1}^m A\_{i,j} X^{i-1} Y^{j-1}$ in two randomly-chosen variables $X, Y$ in a big enough finite field. By pre-computing all "prefix" values of forms $h(A\[1:i,1:j\])$ and $X^iY^j$, any fingerprint of a rectangular sub-matrix can be computed in constant time.
> 2 votes

---
Tags: algorithms, time-complexity, suffix-trees, digital-image-processing
---


# Question
Title: Why is the language containing the Turing machines which only accept their own encoding not applicable to the diagonalization proof?
I saw this question and asked myself why the original problem is not solvable through diagonalization. Let $$L = \bigl\\{\langle M \rangle \mid L(M) = \\{\langle M\rangle\\}\bigr\\}$$ Take the complement $\overline{L}$. Suppose there is a Turing Machine $M$ which decides this language. We get the following two cases:

* $\langle M \rangle \in \overline L \implies M \text{ accepts } \langle M \rangle \implies \langle M \rangle \notin \overline{L}$
* $\langle M \rangle \notin \overline L \implies M \text{ does not accept } \langle M \rangle \implies \langle M \rangle \in \overline{L}$

Is this a valid proof?

# Answer
> 0 votes
If $\langle M \rangle \in \overline{L}$ then by definition of $M$, $M$ accepts $\langle M \rangle$, and so $\langle M \rangle \in L(M)$. This is not the same as $L(M) = \\{\langle M \rangle\\}$, and so we cannot conclude that $\langle M \rangle \in L$. It could be, for example, that $M$ accepts other inputs.

If $\langle M \rangle \notin \overline{L}$ then by definition of $M$, $M$ does not accept $\langle M \rangle$, and so $\langle M \rangle \notin L(M)$. In particular, $L(M) \neq \\{ \langle M \rangle \\}$, and so by definition of $L$, $\langle M \rangle \in \overline{L}$. So in this case we do get a contradiction.

The conclusion is that $\langle M \rangle \in \overline{L}$, and this does not directly lead to any contradiction.

---
Tags: computability, undecidability, diagonalization
---


# Question
Title: Do tasks that take up more memory/space always take more time?
Apologies if this is a trivial question - but I can't seem to find a direct answer to this. Say program A manipulates some data, and program B does the same manipulation, except it operates on a deep copy of the data (so now there are two identical versions of the data in memory during execution).

Since B essentially uses twice as much space by copying the data, does it necessarily follow that it will take longer to run? And if so, if two scripts like in the above example do the same thing but arbitrarily take up different amounts of space, what is the relationship between space and and time here?

# Answer
This question seems to have many open ends from my perspective. But here is my take on this.

Firstly, the time complexity would not change since you said the programs do the **same** computation(feel free to correct me). The time taken to deepcopy would just be something like an initialisation factor and not the actual computation. The running time would increase but whether the time complexity should increase is a problem specific analysis.(For example: A performs linear search and B copies the data and performs linear search. How would you find the time complexity in this case may vary as per your analysis.)

Secondly, you said 2 programs. This means you have 2 independent processes and both of them have their respective copies of data in the memory(ideally).So both of them actually operate on deep copies to begin with and I am assuming by deep copying you mean an explicit copy operation in the program. If they used a shared memory then locking would come into picture and still a copy would mean an explicit copy operation.

Let's assume we have a python script which performs a deepcopy and some operations on it. Yes the running time and space needed for that process would be greater than the one which doesnt copy.

Now assume that you have 2 C programs and in one of them you are creating a copy of the data and assiginig it to a const variable, in such a case the copying would be handled at compile time and there would be no difference in run times.

Using more space doesn't necessary mean the time required would be more. There are many factors affecting it like caches and dedicated hardware for computaion which would help in keeping execution efficient. For example, If one program operates using purely cpu and another one offloads a part of the computation to the gpu, in this case you need to copy data from the main memory to gpu, process it further and return it back to the main memory. These are more tasks but can actually take less time as compared to purely cpu operations.

Hope this gives you some insight.
> 1 votes

---
Tags: complexity-theory, time-complexity, asymptotics, space-complexity
---


# Question
Title: Entropy of $\{X_1,\ldots,X_T\}$ where $X_1,\ldots,X_T \in_R [Q]$
I have a noiseless T-user multiple access channel. Let $\[Q\] = \\{1, \dots , Q \\}$. The users send symbols $X\_i ∈\[Q\], i = 1, \dots , T$ . The channel is defined as follows $$(X\_1, X\_2, \dots , X\_T) → Y$$

$Y=\cup\_{i=1}^T X\_i$, $X\_i$ are i.i.d uniform

For example: $(1, 2, 3) → \\{1, 2, 3\\}$, $(1, 1, 2) →\\{1, 2\\}$

How to find $I(X\_1, \dots , X\_T; Y )$ ?

Actually I can't even understand what is the distribution of $Y$.

# Answer
Since $Y$ is determined by $X\_1,\ldots,X\_T$, the mutual information is just the entropy of $Y$.

We can compute the probability that $Y = \\{i\_1,\ldots,i\_\ell\\}$ as follows. There are $S(T,\ell)$ ways to partition $\[T\]$ into $\ell$ non-empty subsets (without order on the subsets); these are Stirling numbers of the second kind. There are $\ell!$ ways to assign $i\_1,\ldots,i\_\ell$ to the $\ell$ parts. In total, the probability is $\ell! S(T,\ell)/Q^T$. Therefore $$ H(Y) = \sum\_{\ell=1}^{\min(Q,T)} \binom{Q}{\ell} \frac{\ell! S(T,\ell)}{Q^T} \log \frac{Q^T}{\ell! S(T,\ell)}. $$
> 1 votes

---
Tags: information-theory
---


# Question
Title: Why is $\mathsf{P} \subseteq \oplus \mathsf{P}$?
I have a very basic question. $\mathsf{P}$ is the class of decision problems solvable in polynomial time by a Turing machine. $\oplus \mathsf{P}$ is the class of decision problems solvable by an NP machine such that

1. If the answer is 'yes,' then the number of accepting paths is odd.
2. If the answer is 'no,' then the number of accepting paths is even.

How do you show that $L \in \mathsf P \implies L \in \oplus \mathsf P$? i.e., that $\mathsf{P} \subseteq \oplus \mathsf{P}$.

# Answer
> 4 votes
You can think of a deterministic Turing machine as a nondeterministic Turing machine which doesn't make any nondeterministic choices, and so has a unique execution path. Consequently, a deterministic Turing machine has at most one accepting path. It accepts an input if there is an accepting path, and it doesn't accept an input if there is no accepting path. In particular, it accepts an input iff the number of accepting paths is odd.

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


# Question
Title: How do I find the regular expression for- All binary numbers greater than 110011
I am trying to solve a problem set to practice for an exam. How can I approach questions like these ? Is there a way to verify solutions or is it just trial and error ?

# Answer
If a number is more than 6 bits long (not counting leading zeroes) then it is certainly larger than your number. Otherwise, it is one of finitely many numbers, preceded by an arbitrary number of leading zeroes.
> 2 votes

---
Tags: regular-expressions, binary, lexical-analysis
---


# Question
Title: Is there a quantifier more powerful than the other to determine FOL connector?
So basically we have 2 types of quantifier in first order logic, they are universal quantifier and existential quantifier. Usually we use implies connector(-\>) when we have universal quantifier in front of our formula and use conjunction connector(∧) when we have existential quantifier in front of our formula.

1. If we have both quantifiers in front of our formula, which connector we should choose? (e.g. implies or conjunction) Or can it be both? (i.e. can be any connector between implies and conjunction but only pick one, or must use both of them?)
2. Does the order matter? (i.e. does it affect the decision of connector we should used if we put universal quantifier first then existential quantifier or vice versa?)

Example :

Everyone knows someone who hates either Joe or Judy

∀x∃y(knows(x,y)-\>(hates(y,Joe) V hates(y,Judy)))

Does above FOL equivalent to :

∀x∃y(knows(x,y)∧(hates(y,Joe) V hates(y,Judy)))

Or Neither of them meet the FOL criteria because we must use both connectors?

# Answer
> 0 votes
Observe, first, that the First-Order Logic (FOL) version that you have defined in the first statement adds some (syntactic) constraints and it turns out that this is a *fragment* of FOL, called *guarded fragment* \[1\]. In particular, such fragment answers the question:

> What precisely are fragments of classical first-order logic showing "modal" behaviour?

which is related to Modal Logic (ML). Moreover, ML is the fragment of FOL which is invariant under bisimulation \[1\].

---

In your example, to prove, then, that

$$ \forall x \exists y (knows(x,y) \to (hates(y,Joe) \lor hates(y,Judy))) \\ \leftrightarrow \\ \forall x \exists y (knows(x,y) \land (hates(y,Joe) \lor hates(y,Judy))). $$

is not true, you can use the following argument as a counter-example. Imagine a scenario where $\neg knows(x,y)$ holds, for all $x$ and for some $y$, which (trivially) implies that

$$ \forall x \exists y (knows(x,y) \to (hates(y,Joe) \lor hates(y,Judy))) \\ \equiv \\ \forall x \exists y (\neg knows(x,y) \lor (hates(y,Joe) \lor hates(y,Judy))) $$

holds too, but

$$ \forall x \exists y (knows(x,y) \land (hates(y,Joe) \lor hates(y,Judy))) $$

does not since it requires $knows(x,y)$ to hold, for all $x$ and for some $y$. Therefore, the equivalence does not hold.

---

Finally, "everyone knows someone that hates Joe or Judy" is equivalent to

$$ \forall x \exists y (knows(x,y) \land (hates(y,Joe) \lor hates(y,Judy))). $$

An intuition behind why this is the case is because "everyone *knows* $\ldots$" implies that, in the context, the resulting FOL formula must guarantee such a fact, which would not always be the case with the other (implicative) formula.

---

**References**

\[1\]: H. Andréka, J. van Benthem and I. Németi. Modal languages and bounded fragments of predicate logic. Journal of Philosophical Logic, 27:217–274, 1998. URL https://link.springer.com/content/pdf/10.1023/A:1004275029985.pdf

# Answer
> 0 votes
Let me write short definitions in hope it will be helpful: $$(\forall x\in X) R \Leftrightarrow (\forall x)(x\in X\Rightarrow R)$$ $$(\exists x\in X) R \Leftrightarrow (\exists x)(x\in X\land R)$$ As for order, then it matter. We have $$(\exists x)(\forall y)R \Rightarrow (\forall y)(\exists x)R$$ but not reverse.

---
Tags: logic, discrete-mathematics, first-order-logic, propositional-logic
---


# Question
Title: Proving that a specific Turing machine accepts a regular language
Calling all math buffs! ;)

A Turing machine has two states - one accepting and one non-accepting. Furthermore, the Turing machine cannot overwrite blank symbols. (Note: It's assumed that the blank symbol surrounds the input on the band and isn't itself part of any input string)

Show that the given Turing machine can only accept a regular language.

Could anyone please help me out? I can't come up with anything... (Which is unusual for me!)

# Answer
> 1 votes
As it turns out, the problem is invalid - there can be Turing machines with the given specifications that can accept a non-regular language. Consider the following thought experiment:

* Consider a word consisting of a's and b's, in which no b comes before any a. Let there be an additional character c in the beginning of the string.
* Now imagine a Turing machine that iterates through the c, then the a's, and replaces the first b with a character that makes the machine go to the right in the accepting state, r for instance. The machine goes to the left after writing this character.
* It now comes upon the last a, which it replaces with a character that makes it go the the left, l for instance. The machine goes to the right after writing this character.
* The machine then goes back and forth, replacing r's with l's and l's with r's, depending on which direction it is going.
* It will halt and accept once it reaches the initial c. (Which it will have replaced with a corresponding symbol in the very beginning of the process)

In this way, the Turing machine will accept the language of words, which contains a subword consisting of a c, followed by n a's, followed by at least n+1 b's. This is obviously not regular, because DEA's can't count. (Or more formally, use the pumping lemma to increase the number of a's to be greater than the number of b's)

Sorry for all of the confusion - this was actually a homework question! (And I assumed that it would be valid)

---
Tags: turing-machines, regular-languages
---


title: Why use the Y combinator for recursion?

text:
# Question
Title: Why use the Y combinator for recursion?
The Y combinator is defined as $$Y=\lambda f.(\lambda x. f (x x))(\lambda x. f (x x))$$ It has the following useful property: $$Y g = g (Y g)$$ for some expression $g$. It can be easily used to implement a recursive function, e.g. factorial:

```
Y = lambda f : (lambda x : f(lambda v : x(x)(v)))(lambda x : f(lambda v : x(x)(v)))
F = lambda r : lambda n : 1 if n == 0 else n * r(n - 1)
fact = Y(F) # same as F(Y(F)), therefore the r in the body becomes Y(F) which is fact
print(fact(5))

```

The above code outputs 120, as expected. (The Y combinator in the code differs from the one at the start of the question. This is because the one at the start would cause a recursion depth exception. They are equivalent in the lambda calculus nonetheless)

---

An alternative method, which is the topic of my question, is as follows:

```
F = lambda r : lambda n : 1 if n == 0 else n * r(r)(n - 1)
fact = F(F) # r gets substituted with F, therefore the expression in the body becomes F(F) which is fact
print(fact(5))

```

This once again outputs 120, but is more readable and straightforward in my opinion.

---

If the second method works, then what is the point of using the Y combinator? Wikipedia says this about the second method:

> …The self-application achieves replication here, passing the function's lambda expression on to the next invocation as an argument value, making it available to be referenced and called there.

> This solves it but requires re-writing each recursive call as self-application. We would like to have a generic solution, without a need for any re-writes:…

It then proposes the first method as a better solution. What do they mean by *generic solution*?

# Answer
One way of thinking about why $Y$ would be preferable is that it separates 'content' from 'plumbing'. Typical notation for recursive definitions in practical languages is something like:

$$\mathsf{fact} = λn. \mathsf{if}\ n = 0\ \mathsf{then}\ 1\ \mathsf{else}\ n * \mathsf{fact} (n-1)$$

It is desirable to just be able to factor out the body with minimal changes, like:

$$λ \mathsf{fact}\ n. \mathsf{if}\ n = 0\ \mathsf{then}\ 1\ \mathsf{else}\ n * \mathsf{fact} (n-1)$$

We get this simply by adding an argument with the same name as the desired recursive definition; there's no need to change the body. So, it is purely (as can be) the 'content' that distinguishes your recursive definition. Then $Y$ takes care of the 'plumbing' necessary to make $\mathsf{fact}$ actually work like a recursive call and so on.

Your alternate definition has moved some of the plumbing into the content function, by inlining the part where $\mathsf{fact}$ is passed a copy of itself. This replaces $Y$ with the simpler $λf. f f$, but it complicates the content with some of the details of how the looping is being achieved. These details would need to be copied into every content function.

So, $Y$ is preferable in the sense that it confines the implementation details of looping into one function, so that the 'bodies' of recursive definitions can be written in the straight forward way.
> 4 votes

---
Tags: lambda-calculus, functional-programming
---


# Question
Title: How to reduce Turing machines that accept a finite language to Turing machines that accept a regular language?
I'm trying to prove $\mathsf{FIN} \leq\_T \mathsf{REGU}$, where

$$\mathsf{FIN} = \\{ \langle M \rangle \mid M\text{ is a Turing machine}, L(M) \text{ is a finite language}\\},$$ $$\mathsf{REGU} = \\{\langle M \rangle \mid M\text{ is a Turing machine}, L(M) \text{ is a regular language}\\},$$ $\langle M\rangle$ is the encoding of $M$, $\\,$$L(M)$ is the language accepted by $M$ and $\leq\_T$ means Turing reduction.

What I have done so far is this:

$ w \in \mathsf{FIN}$ $\implies$ $| L(M\_w)| \< \infty$ $\implies$ $\exists n \in \mathbb N: L(M\_w) = \\{w\_0, \ldots, w\_n \\}$ $\implies$ $\exists\\,\text{DFA} \ A: L(A) = L(M\_w) $

What I want to show now: *"to decide if a language is regular is at least as hard as deciding wether it is finite"*. That's where I'm stuck.

# Answer
> 1 votes
First note, that for a regular language, however encoded, it is decidable wether it is finite or not. So you can use the language $REGU$ as an oracle for $FIN$ in the following way: To check if $\langle M \rangle \in FIN$ you ask the oracle $\langle M \rangle \in REGU$? If the answer is no, you can be sure that $\langle M \rangle \notin FIN$ as every non-regular language is infinite. If the answer is yes there is a proof (e.g. an NFA $\mathcal{A}$) that shows that $M$'s language is regular. Then you run your procedure to check whether $\mathcal{A}$ is finite (this is, as mentioned above decidable).

# Answer
> 1 votes
### The simple obvious approach

To prove $\mathsf{FIN} \leq\_T \mathsf{REGU}$, what we can do is to find a "computable" mapping that maps

* any finite language to a regular language and
* any infinite language to a nonregular language.

### The wanted mapping

If words in a regular language are ordered by length, the differences between lengths of adjacent words are bounded. In fact, we can see immediately that they are bounded by the pumping length of that language as in the pumping lemma for regular languages.

The idea to design the mapping is, when the words in the given language become longer, we will ensure the differences between different lengths of the corresponding words become bigger so that they cannot be bounded eventually.

Given a language $L$, we can map it to $$f(L)=\\{w\in \Sigma^\*\mid w \text{ has a prefix }u\in L\text{ such that } |w|=|u| + |u|^2 \\}$$ where $|\cdot|$ is the length of a string. Let us prove $f$ can be the wanted mapping.

**Claim.** $L$ is finite $\iff$ $f(L)$ is regular.

**Proof.** "$\implies$": If $L$ is finite, then $f(L)$ is finite as well. Hence $f(L)$ is regular.

"$\impliedby$": This is an application of the pumping lemma. Suppose $f(L)$ is regular. Let $p$ be a pumping length for $f(L)$. For the sake of contradiction, assume $L$ is not finite. Then there must be a word $u\in L$ with $|u|\ge p$.

Consider $w=uu^{|u|}\in f(L)$. Since $|w|\ge p$, the pumping lemma says $w=xyz$ for some strings $x,y,z$ such that $1\le|y|\le p$ and $xy^2z\in f(L)$. Since $$|xy^2z|=|y| + |w| = |y| + (|u| + |u|^2),$$ we know $$|u| + |u|^2\<|xy^2z|\<(|u|+1) + (|u|+1)^2.$$ Since the length of every word in $f(L)$ is of the form $i + i^2$ for some natural number $i$, we must have $xy^2z\not\in f(L)$, which contradicts the fact $xy^2z\in f(L)$. $\quad\checkmark$

### From Turing machine $M$ to $M'$

Given a Turing machine $M$, let us construct Turing machine $M'$.

On input string $w$, $M'$ will try searching a prefix $u$ of $w$ such that $|w|=|u| + |u|^2$. This can be done by letting $u$ loop through each prefix of $w$, or just checking whether $|w|=\lfloor\sqrt{|w|}\rfloor+\lfloor\sqrt{|w|}\rfloor^2$.

* If there is no such prefix, $M'$ rejects.
* Otherwise, $M'$ has found $u$ as such. $M'$ will continue to run in the same way as $M$ runs given $u$ as the input.

It is clear that we can construct $M'$ from $M$ algorithmically. A word $w$ is accepted by $M'$ if and only if $w$ has a prefix $u$ such that $\vert w\vert=\vert u\vert+\vert u\vert^2$ and $M$ accepts $u$. That is, $L(M') = f(L(M))$. thanks to the claim above, we know $\langle M\rangle\in\mathsf{FIN}$ $\iff$ $\langle M'\rangle\in\mathsf{REGU}$.

### A Turing reduction from $\mathsf{FIN}$ to $\mathsf{REGU}$

Given a string $s$, here is how we decide whether $s\in \mathsf{FIN}$ using an oracle that tells whether any given string is in $\mathsf{REGU}$, .

1. Check whether $s$ is a valid encoding of a Turing machine. If not, $s\not\in \mathsf{FIN}$.
2. Otherwise, $s=\langle M\rangle$ for some Turing machine $M$. Construct $M'$ from $M$ as described above. So, $\langle M\rangle\in\mathsf{FIN}$ $\iff$ $\langle M'\rangle\in\mathsf{REGU}$. Now ask the oracle whether $\langle M'\rangle\in\mathsf{REGU}$.
    * If yes, $s\in\mathsf{FIN}$.
    * If not, $s\not\in\mathsf{FIN}$. $\quad\checkmark$

### An exercise.

> Show that $\mathsf{REGU} \leq\_T \mathsf{CF}$, where $$\mathsf{CF} = \\{\langle M \rangle \mid M\text{ is a Turing machine, }L(M)\text{ is a context-free language}\\}.$$

The simple obvious approach is, similarly, to find a "computable" mapping that maps any regular to a context-free language and any non-regular language to a non-context-free language. If such a mapping is known to you, this exercise is easy; otherwise, it is pretty hard.

---
Tags: formal-languages, turing-machines, reductions, decision-problem
---


# Question
Title: Prove an edge that minimizes the Euclidean distance crossing a cut is in the Delaunay triangulation
Let $P$ and $Q$ be two disjoint point sets in the plane. (Think of them as a red point set and a black point set.) Let $p \in P$ and $q \in Q$ be two points from these sets that minimize the Euclidean distance $|pq|$. Prove that $pq$ is an edge of $\text{DT}(P\cup Q)$.

---

I know this property of DT, the closest neighbor b to any point p is on an edge bp in the Delaunay triangulation since the nearest neighbor graph is a subgraph of the Delaunay triangulation.

Is this sufficient to prove the proposition above?

# Answer
No, since $pq$ may not be in the nearest neighbor graph.

For example, let $P=\\{(-3,1), (-2, -0)\\}$ and $Q=\\{(2,0), (3, 1)\\}$. Then $p=(-2,0)$ and $q=(2,0)$. However, the nearest neighbor graph, which consists of edge $pp'$ and edge $qq'$, does not contain edge $pq$.

---

Here is a useful property of Delaunay triangulation.

If a circle passing through two given points doesn't contain any other given points in its interior, the line segment between the two points is an edge of a Delaunay triangulation of the given points. If, furthermore, there is no given points on the boundary of the circle, that line segment is an edge of every Delaunay triangulation.
> 1 votes

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


title: Find neighbour objects in a 3d grid

text:
# Question
Title: Find neighbour objects in a 3d grid
I have points in a 3d world where their position is defined by 3 **integers**: X, Y, Z.

I'm searching for an algorithm / data structure to store these points in a way I can quickly find (e.g.: O(log(N)) the neighbour points in any direction aligned with the world axis (X-/left, X+/right, Y-/bottom, Y+/top, Z-/front, Z+/back).

Example:

* Point 1 position: X=2, Y=1, Z=7
* Point 2 position: X=4, Y=2, Z=7
* Point 3 position: X=5, Y=1, Z=7
* Point 4 position: X=8, Y=1, Z=7

I want to find the first neighbour on the right of the point 1. The algorithm should return me the first point where X\>2, Y=1 and Z=7: it is the point 3.

# Answer
> 1 votes
As stated, your query is for a point nearest *to a coordinate plane*, in a half space. A k-D tree structure seems ideal for such queries. You will need to adapt from a standard nearest neighbor query.

# Answer
> 0 votes
I will define an $O(\log n)$ solution for X-right direction. The argument can be extended for the other directions also.

Let the input point set is: $(x\_i,y\_i,z\_i)$ for $i \in \\{1,\dotsc,n\\}$. Suppose that for the coordinate $(y\_i,z\_i)$, we have a list of points that have $y = y\_i$ and $z = z\_i$. There can be at most $n$ such lists. Sort the points in each list by their $x$-coordinates.

When, a query point $(x\_q,y\_q,z\_q)$ comes, perform a binary search in the list defined by $(y\_q,z\_q)$. This will give you the X-right neighbour of $(x\_q,y\_q,z\_q)$ in $O(\log n)$ time.

The only remaining question is how to create the lists corresponding to each $(y\_i,z\_i)$, and locating these lists efficiently. For this, maintain a hash table that stores an entry corresponding to every $(y\_i,z\_i)$. The size of the table is $\Theta(n)$ and the *key* of the hash function corresponds to the pair $(y\_i,z\_i)$. Therefore, the lists for every $(y\_i,z\_i)$ can be created in average $O(n)$ time. Moreover, locating an entry $(y\_q,z\_q)$ from the hash table also takes $O(1)$ time on average; therefore queries can be answered efficiently.

Create these hash tables and lists for the remaining directions also. The total space complexity is just $O(n)$, and the preprocessing time is $O(n \log n)$ on average.

# Answer
> 0 votes
There are a number of spatial index solutions that can be used with 3D data. Most indexes belong to one of these groups: Quadtrees, R-trees and kD-trees and Locality Sensitive Hashing.

Most of these have floating point implementations, but they should work fine (or should be easily adaptable) to **integer** coordinates.

Many implementations support nearest neighbor search with custom distance functions, so it should be possible to write a distance function that return objects only for a given **direction**, e.g. by returning very large positive distance for points from the wrong directions.

One index that works especially well with integer coordinates is the (disclaimer: self-advertisement) PH-Tree, it is somewhat related to quatrees. One property it has is that it works "naturally" with integers (it can also encode floats (without loss of precision) but that is a bit complicated).

---
Tags: algorithms, data-structures, sorting
---


# Question
Title: What is the exclusion-inclusion algorithm for TSP?
I was looking at the wikipedia page for the Travelling Salesman Problem and found a reference to another exact algorithm besides Held-Karp that's also $O(2^nn^2)$.

Specifically: "This bound has also been reached by Exclusion-Inclusion in an attempt preceding the dynamic programming approach."

Can you explain how that algorithm works?

# Answer
> 2 votes
The quoted sentence is inaccurate. There is a known inclusion-exclusion algorithm for the *Hamiltonian path problem* i.e. unweighted TSP. The algorithm can be extended to the integer-weighted case, but the runtime and space depend linearly on the maximum distance $W$ between two cities, which is exponentially large in general.

The difference between weighted and unweighted cases is often confused because sometimes "Hamiltonian path" and "TSP" are used interchangeably. The Wikipedia article mainly covers the weighted TSP.

See "Exact Exponential Algorithms" Chap.4.2.2 \[1\] for details of the inclusion-exclusion algorithm. The book states "the existence of a polynomial space algorithm solving the TSP problem in time $O^\ast(2^n)$ is an interesting open problem".

---
Tags: p-vs-np, traveling-salesman
---


title: Proving the correctness of an algorithm

text:
# Question
Title: Proving the correctness of an algorithm
What is the logic behind using a loop invariant proof for proving the correctness of an algorithm? How is it proved that using the loop invariant proof indeed proves the correctness of a loop?

# Answer
The proof of correctness of an algorithm can be seen as a succession of annotations like

```
{ P }
Statement
{ P' }

```

where it can be proven that the statement guarantees the postcondition `P'` if the precondition `P` holds.

In the case of a loop, the conditions `P` must be somewhat special because if we unroll a loop, say three times, we write

```
{ P }
Loop-body
{ P' }
Loop-body
{ P'' }
Loop-body
{ P''' }

```

The predicate must be such that it remains true across the iterations (whatever their number), hence its name, "invariant".

Example: we want to compute the sum of the integers from `1` to `n`. We will do so by accumulating integers into a single variable.

```
s= 0
i= 0
while i ≤ n:
  s+= i
  i+= 1

```

Obviously, we are computing partial sums and the invariant will express that `s` contains the `i`-th partial sum, which we denote as `S(i)`$:=\sum\_{k=0}^{i-1} k$.

```
s= 0
i= 1
{ s = S(1) = S(i) }
while i ≤ n:
  { s = S(i) }
  s+= i
  { s = S(i+1) }
  i+= 1
  { s = S(i) }
{ s = S(n+1) }

```

As you can see, we start the loop with the invariant holding, we perform some operations that invalidate it, then we restore the invariant so that another iteration can be performed in similar conditions.
> 1 votes

# Answer
## What does it mean to say a program is correct?

*When we say that a program (or a segment of code) is correct, we mean if the proper condition to run the program holds, and the program is run, then the program will halt, and when it halts, the desired result follows.*

*The proper condition to run a program is called its precondition*.

*That the program halts is called termination*.

*The desired result following a program’s termination is called its postcondition.*

***Note that program correctness is always described with respect to its precondition and postcondition I.e., correctness also depends on precondition and postcondition***.

*The pre/post-condition pair is called the program’s specification.*

*With the above terminology, we can think of program correctness as follows. Program correctness: if precondition then (termination and postcondition)*.

*So proving correctness means proving precondition ⇒ (termination and postcondition)*. *Sometimes it is convenient to prove separately the termination part and the postcondition part*. *In this case we divide the proof into two parts.* *(a) precondition ⇒ termination — this part is sometimes just called termination*,

*(b) (precondition and termination) ⇒ postcondition — this part is called partial correctness*.

*So proving correctness means proving partial correctness and termination*.

## ⋆ Proving correctness of iterative programs

Iterative programs are programs with loops. When proving that a loop (or program with a loop) is correct (with respect to some pre/post-condition pair), we prove partial correctness and termination separately. **For both parts we need a loop invariant, which describes how the variables in the loop are used to achieve the postcondition**.

◦ Loop invariants A loop invariant (LI) is a statement that is true on entering the loop, and after every iteration (assuming the precondition holds). To prove an LI, we use a form of induction, where

(a) **Basis**: we prove that the LI holds on entering the loop,

(b) **Induction Step** we prove that if the LI holds before an iteration, then it also holds after that iteration.
> 0 votes

---
Tags: correctness-proof, loop-invariants
---


# Question
Title: If two time complexity classes are equal what does that imply about the time complexity classes for corresponding proper complexity functions?
Say that two complexity classes are equal, i.e. `TIME(n) = TIME(nlogn)`. Does this imply that for some proper complexity function `f(n) >= n` we can show `TIME(f(n)) = TIME(f(n)(logf(n)))`? If so, how can we strongly argue that they are equal and one is not just strictly contained in the other?

# Answer
> 1 votes
Proving such theorems are usually done with the technique known as padding.

In your particular case, if we assume that "proper" funtions are functions we are used to (i.e, time constructible) then the statement is incorrect.

Let us assume this is note the case, and that the theorem is correct. Now, if $f(n)$ is some time-constructible function, then $TIME(f(n))=TIME(f(n)\log(f(n)))$.

Denote $g(n):=f(n)\log(f(n))$ and notice that $g(n)$ is a time-constructible function as well. Thus $TIME(f(n))=TIME(g(n))=TIME(g(n)\log(g(n)))$

But notice that $h(n):=g(n)\log(g(n))=f(n)\log(f(n))\cdot \left( \log(f(n))+\log(\log(f(n)))\right)$ is much larger than $f(n)\log(f(n))$ in the sense that $f(n)\log(f(n))=o(h(n))$.

Therefore, by the time heirarchy theorem, $TIME(f(n))\subsetneq TIME(h(n))$, but this contradicts our assumption that $TIME(f(n))=TIME(g(n))=TIME(h(n))$.

Thus we finally proved that this statement is incorrect. A similar proof may be utilized even if $TIME(f(n))=TIME(f(n)\log^\epsilon (f(n))$ for any $\epsilon \> 0$.

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


# Question
Title: Recursive Algorithm to compute Square numbers
I figured out an algorithm to compute the square of a number (power of 2) in a recursive way backwards or forward. I don't think I have ever seen this anywhere else before, so I am curious if this already exists / does it have a name?

I put comments in the code that explain the whole idea. But I will TL;DR here: TL;DR - Algorithm to compute square (power of 2) of a given number N recursively, given the property that (N+1)^2 == N^2 + 2N + 1,

and that the "forward" delta of (N+1)^2 - N^2 == N^2 + 2N + 1 - N^2 == 2N + 1,

and if we replace N with N-1, we get the "backward" delta of 2N - 1.

To be clearer: Forward delta of (N)=3 to (N+1) == 2N+1, or 7 And the Backward delta of (N)=3 to (N-1) == 2N-1, or 5

Square(3) -\> Square(4) \[ForwardDelta\]: This means that if I have Square(3) and want Square(4), we do Square(3) + ForwardDelta(3) == (9 + 7) == 16 -\> Square(4)

Square(3) -\> Square(2) \[BackwardDelta\]: This means that if I have Square(3) and want Square(2), we do Square(3) - BackwardDelta(3) == (9 - 5) == 4 -\> Square(2)

I have the code on github: https://github.com/CobraCoral/recursive\_square

And also posting here if you feel too lazy to click :)

<pre><code>#!/usr/bin/env python3
"""Computes square number of N recursively, without multiplication.

Problem: We want to know N^2 without doing N*N.

Axiom 1: Square of 0 is 0 (zero product property).
Axiom 2: Square of 1 is 1. (as 1 is the identity for multiplication).
Axiom 3: Square of -1 is 1. (as negative multiplied by negative is positive).
Axiom 4: Square of (N+1) = N^2 + 2N + 1 (the quadratic polynomial formula).

Knowing from Quadratic Formula that (N+1)^2 = N^2 + 2N + 1,
let's call X=N+1 and Y=N. We have then:
    X^2 = Y^2 + 2Y + 1

Another way to see it is by looking at the delta of two consecutive square numbers:
(N+1)^2 - N^2 = N^2 +2N +1 - N^2 => 2N + 1

So 2N + 1 is the arithmetic series of odd numbers.

The deltas of each number follow an this progression of +2 always,
starting at 1 for 1 square.

So the arithmetic progression is:
          N:    1  2  3  4  5   6   7   8   9  10
Progression:    1, 3, 5, 7, 9, 11, 13, 15, 17, 19
Therefore, for a given number N, the progression is (2*N)-1,
or in other words, 2*(N-1) + 1.
(i.e. 1 + 2+2+...+2 n-1 times).

So we see that for each number N, its power of 2 will be the power of two
of the previous number, plus a constant (always a factor of 2).

And the square of each number is always the progression, plus the previous
number squared, recursively as follows:
    Progression(N) = Progression(N-1) + 2 => (N*2-1)
         Square(N) = Progression(N) + Square(N-1), for every N.
NOTE: As we will be using recursion and we want to avoid multiplications, we will assume N>=1.

N                Prog    Square  Result
.
.
-2          =      -5,  (-5 + 9)  {  4}
-1          =      -3,  (-3 + 4)  {  1}
0           =      -1,  (-1 + 1)  {  0}
1           =       1,  ( 1 + 0)  {  1}
2           =       3,  ( 3 + 1)  {  4}  -> 3 is previous Prog (1) + 2
3           =       5,  ( 5 + 4)  {  9}  -> 5 is previous Prog (3) + 2
4           =       7,  ( 7 + 9)  { 16}  -> 7 is prev. Prog (5) + 2
5           =       9,  ( 9 + 16) { 25}  -> and so on...
6           =      11,  (11 + 25) { 36}
7           =      13,  (13 + 36) { 49}
8           =      15,  (15 + 49) { 64}
9           =      17,  (17 + 64) { 81}
10          =      19,  (19 + 81) {100}
.
.
.
etc

In this script we have a few methods to compute the above, as follows:
1) How to compute square numbers of a number, with recursion and the properties
   of the square numbers of the previous number
   (i.e. we compute N**2 by computing (N-1)**2)
2) Using recursion with memoization
3) Using tail recursion, with memoization
4) And using function decorators to decorate the non-memoized tail recursion,
with memoization.
"""
import functools

def memoization_decorator(func):
    """Add simple memoization to a function."""
    @functools.wraps(func)
    def wrapper_decorator(*args, **kwargs):
        number = args[0]
        if number in memoization_decorator.dictionary.keys():
            return memoization_decorator.dictionary[number]
        # print("recursive square : memoized", number)
        square = func(*args, **kwargs)
        memoization_decorator.dictionary[number] = square
        return square
    return wrapper_decorator

memoization_decorator.dictionary = {1: (1, 1)}

@memoization_decorator
def recursive_square(number):
    """Compute the square of N as described by the recursive algorithm."""
    if number < 1:
        print("ERROR: N must be >= 1")
        return (None, None)
    if number == 1:
        return (1, 1)
    n_minus1_prog, n_minus1_square = recursive_square(number - 1)
    n_prog = n_minus1_prog + 2
    n_square = n_prog+n_minus1_square
    result = (n_prog, n_square)
    # print("recursive", number, result)
    return result

@memoization_decorator
def recursive_square_tail(number):
    """Compute tail recursive square of N."""
    # print("recursive square tail", number)
    def recursive_square_tail_full(number, prog, square):
        if number < 1:
            print("ERROR: N must be >= 1")
            return (None, None)
        # print(".... full", number, prog, square)
        if number == 1:
            return (prog, square)
        result = recursive_square_tail_full(number - 1,
                                            prog + 2,
                                            prog + square + 2)
        # print("     tail", number, result)
        return result
    return recursive_square_tail_full(number, 1, 1)

if __name__ == "__main__":
    def doit(forward=True):
        """Compute recursion and tail recursion, and prints results."""
        if forward:
            range_is = range(1,51)
        else:
            range_is = range(50, 0, -1)
        for num in range_is:
            recur = recursive_square(num)
            tail = recursive_square_tail(num)
            fmt_short = 'n^2({:^5}) = {:>5}  ... ({:^5})'
            fmt_long = '%s       ....     %s' % (fmt_short, fmt_short)
            if recur != tail:
                print(fmt_long.format(num, recur[1], recur[0],
                                      num, tail[1], tail[0]))
            else:
                print(fmt_short.format(num, recur[1], recur[0]))
    doit()
    doit(False)
    doit()
    doit(False)

```
</code></pre>

# Answer
> 2 votes
This can be called an incremental algorithm, as it computes $n^2$ in terms of $(n-1)^2$. This is not efficient as it takes a number of operations proportional to $n$.

Honestly, I don't like much the idea of memoization because it consumes a lot of space and is of no use when you square a single number. Memoization seems to be "trendy" but should be used sparingly.

A non-recursive version is

```
N2= 0
for I= 0 TO N-1
  N2= N2 + I + I + 1

```

---

A faster solution can be built around the relations

* $(2n)^2=4n^2=(n^2+n^2)+(n^2+n^2)$,
* $(2n+1)^2=4n^2+4n+1=(n^2+n^2)+(n^2+n^2)+(n+n)+(n+n)+1$.

Now the idea is to write $n$ as a binary number and to rebuild it from left to right while computing the corresponding squares.

E.g. $11=1011\_b$ and $1\_b=1\to1$, $10\_b=2\to1+1+1+1=4$, $101\_b=5\to4+4+4+4+2+2+2+2+1=25$, $1011\_b=11\to25+25+25+25+5+5+5+5+1=121$.

This time, the number of operations is proportional to the number of bits, which can be significantly smaller.

# Answer
> 0 votes
Your algorithm (even though I believe that you've worked out yourself) seems to have been built upon already well known facts

1. Sum of first $n$ odd numbers always equals $n^2$
2. The difference of $n^2$ and $(n+1)^2$ is the sum $n+(n+1)$ see more explanation here

---
Tags: algorithms, discrete-mathematics
---


title: Is O(k*n) in this case linear?

text:
# Question
Title: Is O(k*n) in this case linear?
Problem: find sum of k element in array and it is biggest? time complexity of my algorithm is O(k\*n).Is it linear complexity?

# Answer
> 1 votes
Yes, the algorithm is linear in $k$ and linear in $n$, whatever $k$ and $n$ mean. But it is quadratic in $(k,n)$.

# Answer
> 0 votes
By definition, time complexity of a problem is defined due to its input size (please check this section on Wikipedia).
As input, you get an array of length $n$ ($O(n)$) and **ONE** number $k$ ($O(1)$), so that the input size of your problem is $O(n)$ in overall. On the other hand, the time complexity of your algorithm is $O(kn)$ so that you can't call that algorithm linear.

# Answer
> 0 votes
I'm going to challenge the premise of the question: your algorithm should be `O(n)`, so either your implementation is wrong or your analysis of the complexity is wrong. This is a solution to this that is definitely `O(n)` (or, to be more precise, $\theta(n)$ because the loop will always take exactly `n` steps):

```
public void LargestAndSum(int[] numbers, int k)
{
    int sum = 0;
    int largest = int.MinValue;
    for (int i = 0; i < numbers.Length; i++)
    {
        if (i < k)
        {
            sum += numbers[i];
        }

        if (numbers[i] > largest)
        {
            largest = numbers[i];
        }
    }

    Console.WriteLine($"Sum: {sum}. Largest: {largest}");
}

```

It's tempting to look at the `i < k` part and say "see? It's `O(kn)`!" However, this isn't true, and the reason is the following: it does the `i < k` comparison exactly `n` times. The operation in the loop happens `k` times (where $k \le n$), so that term is dominated by `n`. So there are two comparisons that will happen exactly `n` times, an addition operation that will happen $k \le n$ times, and an assignment operation that will happen at least once (in the case where the first number is the largest in the array) and at most `n` times (in the case that `numbers` is sorted in ascending order). Therefore `O(n)`.

Side note: obviously in actual production code you would want to validate that $numbers \neq null$ and $k \le n$ because it wouldn't make sense for $k \> n$. I did not include the argument validation in the code, though.

You may also want to read this Q&A on the difference between `O(kn)` and `O(n + k)`.

---
Tags: algorithms, complexity-theory, time-complexity, arrays, linear-complexity
---


# Question
Title: How to prove that regular languages are closed under reversal, inductively?
There are some threads that discuss it but I haven't came across an inductive one yet. All of them involve creating a finite automaton which I would like to avoid (as per my professors requests).

# Answer
> 1 votes
You can use regular expressions to easily solve this:

$$(L\_1\cup L\_2)^r=L\_1^r\cup L\_2^r$$ $$(L\_1\cap L\_2)^r=L\_1^r\cap L\_2^r$$ $$(L\_1L\_2)^r=L\_2^rL\_1^r$$ $$(L^\*)^r=(L^r)^\*$$

You can use these equalities when proving by induction over the number of operators in the regular expression.

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


# Question
Title: Suppose we know for certain that P = NP. Can we say that NP = co-NP?
i tried to see from my course book at university but i didn't understand much, can someone help me? even looking around on the internet I did not find anything useful

# Answer
Yes,

$NP=P=co-P=co-NP$

Where $P=co-P$ since $P$ is closed under complement (the TMs are deterministic and always halt, simply swap "reject" with "accept")
> 2 votes

# Answer
P is the class of decision problems where you can find the correct answer in polynomial time in all cases.

Now instead of X: “What is the answer” you can solve X’ “is the answer YES” or X’’ “is the answer NO” in polynomial time.

Since X, X’ and X’’ are in P, they are in NP. X’’ can be solved in nondeterministic polynomial time if the answer to X’’ is “YES”, which is exactly if the answer to X is “NO”. So be definition, X is in co-NP.
> 0 votes

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


title: Runtime of the following procedure

text:
# Question
Title: Runtime of the following procedure
I want to calculate the runtime of the following code as a function of n:

```
sum = 0
i = 1
  while (i < n)
    j = 1
    while ( j < i)
      k = 1
      while ( k < ^2)
        sum = sum + 1
        k = k+ i*i
    j = j + 1
  i = i + 1

```

If understand correctly then `i` will run from `1` to `n` and `j` from `1` to `i` in each iteration and then `k` from `1` to until it reach `n^2`

$$\ \sum\_{i=1}^n \sum\_{j=1}^i \sum\_{k=1}^{\lfloor\log\_i(n)\rfloor} i^2 $$

I'm not sure if the answer is correct because it wasn't accepted at all. So I guess something is missing?

EDIT:

I tried to work out an example:

$\ n = 5 $

\begin{array} {|r|r|}\hline i = 1 & j = 1 & k = 1,2,3,4,5,...,25 \\ \hline i = 2 & j = 1 & k = 1,5,9,13,17,21,25 \\ \hline & j = 2 & k = 1,5,9,13,17,21,25 \\ \hline i = 3 & j = 1 & k = 1,10,19,28 \\ \hline & j = 2 & k = 1,10,19,28 \\ \hline & j = 3 & k = 1,10,19,28 \\ \hline i = 4 & j = 1 & k = 1,17,33 \\ \hline & j = 2 & k = 1,17,33 \\ \hline & .. & \\ \hline & .. & \\ \hline \end{array}

# Answer
> 1 votes
The innermost loop is executed $\dfrac{n^2}{i^2}$ times, roughly (from $1$ to $n^2$ by constant steps $i^2$). The middle loop invokes it about $i$ times, which gives us $\dfrac{n^2}{i}$. Finally, the outer loop runs from $i=1$ to $n$, giving the sum $n^2H\_n$ (Harmonic number). This is $\Theta(n^2\log n)$.

Does it match the answer sheet ?

---
Tags: runtime-analysis
---


# Question
Title: solve the reccurence $\ T(n) = T(n-5) + \log n $
I tried to solve the following recurrence:

$\ T(n) = T(n-5) + \log(n) $ and $\ T(5) = 1 $

using iterative substitution:

$$\ T(n) = T(n-5) + \log(n) = \\T(n-10) + \log(n) + \log(n-5) = \\ T(n-15) + \log(n) + \log(n-5) + \log(n-10) $$

and so eventually I get for $\ i$ iterations: $$\ T(n) = T(n-5i) + \sum\_{k=0}^{\frac{n}{5}-1} \log(n-5k) $$

Then what would be the $\ O $ of this function?

# Answer
Assume that $n = 5 m$.

Then by repeated substitutions you get

$$ \begin{align} T(n) &= T(5m) = T(5) + \log(10) + \dots + \log(5m)\\ &= 1 + \sum\_{k=2}^m \log(5k) = 1 + \sum\_{k=2}^m \left(\log{5} + \log{k}\right)\\ &= 1 + (m-1)\log 5 + \sum\_{k=1}^m \log k \\ &= 1 + (m-1)\log 5 + O(m \log m) = O(n \log n) \end{align} $$ To evaluate the sum of logarithm, the Stirling Formula was used. E.g. look at https://math.stackexchange.com/a/385599/38034
> 1 votes

# Answer
As only multiples of $5$ are involved, we set $n=5m$ and rewrite the recurrence as

$$P(m)=P(m-1)+\log5m$$ with $P(1)=1$. Then obviously

$$P(m)=1-\log5+\sum\_{k=1}^m\log5k=1-\log5+m\log5+\log m!$$ or

$$T(n)=1-\log5+\frac n5\log5+\log\frac n5!=O(n\log n).$$
> 1 votes

---
Tags: runtime-analysis
---


# Question
Title: MAX-LP: maximize number of linear inequalities satisfied
Consider the following variant of linear programming, where we want to maximize the number of linear inequalities that are satisfied:

Input: linear inequalities $A\_1x\le b\_1$, ..., $A\_nx \le b\_n$; an integer $k$
Output: does there exist $x \in \mathbb{R}^d$ that satisfies at least $k$ of these linear inequalities?

To make the problem well-defined, we can assume everything is in $\mathbb{Q}$.

What is the complexity of this problem? It smells like it must surely be hard, but I cannot see how to prove it.

# Answer
> 1 votes
Indeed, this is NP-hard. It is known as the maximum feasible subsystem problem (Max-FS). Max-FS is NP-hard. There is an approximation algorithm with approximation factor 2, but it does not admit a PTAS unless P=NP.

See

The Complexity and Approximability of Finding Maximum Feasible Subsystems of Linear Relations, Edoardo Amaldi and Viggo Kann. Theoretical computer science, 147(1-2), 1995, pp.181-210.

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


# Question
Title: Maximum Intersection of Convex Partitions
Given a bounded, convex polytope $C \subset R^d$, I have $n$ partitions of the polytope $C$ into at most $m$ smaller polytopes (disjoint on all but sets of measure zero). These smaller polytopes have colors assigned to them. Given a color, I would like to find a point $p \in C$ such that $p$ is that color in the maximum number of partitions.

Is this setup similar to another problem I'm just not thinking of?

# Answer
The problem is NP-hard, by a reduction from Max-FS.

Here is the reduction. Consider any instance of Max-FS, i.e., a set of linear inequalities $A\_ix \le b\_i$ over $\mathbb{R}^d$. Choose a bounded polytope $C$ that is "large enough" (i.e., every intersection point of every subset of $d$ equalities $A\_i x = b\_i$ is in $C$). Define the $i$th partition to have two polytopes $P\_i,Q\_i$, where $P\_i = \\{x \in C : A\_i x \le b\_i\\}$ and $Q\_i = \\{x \in C : A\_i x \ge b\_i\\}$. Color every $P\_i$ red. Assign each $Q\_i$ a different, unique color. Now, the solution to your problem is a point $x$ that is contained in the largest number of $P\_i$'s, which is the point that satisfies the largest number of linear inequalities $A\_i x \le b\_i$. Thus, any efficient algorithm for your problem immediately yields an efficient algorithm for Max-FS.

Since Max-FS is NP-hard, it follows that your problem is NP-hard, too.
> 1 votes

---
Tags: optimization, computational-geometry
---


# Question
Title: Observable Markov Model: Expected number of observations
I have a question that asks me "What is the expected number of observations in a state?" with the note: $$\sum^{\infty}\_{d=1}d a^{d=1} = \frac{1}{(a-1)^2}\text{ when } |a| \< 1$$ Prior to that I have a Markov Model with 3 states and the transition probabilities as follows:

* S1: $P(S1) = 0.4$, $P(S2|S1) = 0.3$, $P(S3|S1) = 0.3$
* S2: $P(S2) = 0.6$, $P(S1|S2) = 0.2$, $P(S3|S2) = 0.2$
* S3: $P(S3) = 0.8$, $P(S1|S3) = 0.1$, $P(S2|S3) = 0.1$

Any guidance on what the note means or what I am trying to work out would be appreciated.

# Answer
> 1 votes
The note probably refers to the calculation of the expected value of a random variable $T\_{i}$ that describes the time "we stay" in the state $S\_i$.

From how I understand the question, this is exactly what you are tasked to compute. Therefore I understood the question as: "given that you are in some state $S\_i$, how many observations of $S\_i$ do you expect before changing a state?"

---
Tags: probability-theory, markov-chains
---


title: Locality Sensitive Hashing for Sets

text:
# Question
Title: Locality Sensitive Hashing for Sets
Are there locality sensitive hashes that work nicely with sets? Each set would get a hash, the order of the elements in the set does not change the hash, and sets that share more elements are closer together.

Specifically, I am working with sets that each have approximately 10 elements, and there are a total of 1000000 unique elements across all sets (so creating a vector to binary encode the presence/absence of each element in each set is prohibitive).

Any direction to an algorithm for this would be much appreciated. Thank you very much for any guidance or feedback.

# Answer
Yes. MinHash is one example of a locality sensitive hash for sets.
> 0 votes

---
Tags: sets, hash, hashing, euclidean-distance
---


# Question
Title: Order List of Sets so Adjacent Sets are Disjoint
Let $n \in \mathbb{N}$ and $G := \\{1,2,...,n\\}$. Now let $P\_2(G)$ be a power set of $G$ but only with sets of cardinality $2$, e.g. if $n = 3$ then $P\_2(G) = \\{ \\{1, 2\\}, \\{1, 3\\}, \\{2, 3\\} \\}$.

Now I'd like to order these sets in a list so adjacent sets are disjoint. This only works for $n \> 4$.

Furthermore given a partially filled list, I want to be able to increase $n$ and therefore creating more pairs which need to be appended to the end of the list. The existing order of the list cannot be altered. If collisions can not be avoided, they need to be minimal.

e.g. the partial list

({1,2}, {3,4}, {5,1}, {3,2})

for $n = 5$ is given and $n$ is increased by 1:

({1,2}, {3,4}, {5,1}, {3,2}, {6,1}, {3,5}, {6,2}, {1,4}, ...)

Can this problem be solved in polynomial time?

I thought of the following greedy algorithm:

1. pick the least used number that is not a subset of the previous set
2. if there are multiple least used numbers, pick the one that has the highest distance to its last use

# Answer
You are asking two questions. I will only answer the first. What you are looking for is a Hamiltonian path in the Kneser graph $K(n,2)$.

When $n = 5$, this is the Petersen graph, which contains a Hamiltonian path (though not a Hamiltonian cycle).

When $n \ge 6$, the existence of a Hamiltonian cycle was proved by Heinrich and Wallis, Hamiltonian cycles in certain graphs, using Ore's theorem; in fact, the special case known as Dirac's theorem suffices. Dirac's theorem states that a graph on $N$ vertices with miniimal degree $N/2$ is Hamiltonian (has a Hamiltonian cycle). The Kneser graph $K(n,2)$ contains $\binom{n}{2}$ vertices and is $\binom{n-2}{2}$-regular. A simple calculation shows that $2\binom{n-2}{2} \geq \binom{n}{2}$ when $n \ge 8$, and so $K(n,2)$ is Hamiltonian for $n \ge 8$. Since Ore's theorem has an algorithmic proof, such a Hamiltonian cycle can be constructed efficiently. For the remaining two cases, $n = 6$ and $n = 7$, Heinrich and Wallis give the following Hamiltonian cycles: $$ 25, 16, 23, 45, 12, 34, 56, 13, 24, 35, 46, 15, 26, 14, 36 \\ 25, 37, 12, 34, 56, 17, 23, 45, 67, 13, 24, 35, 46, 57, 16, 27, 36, 47, 15, 26, 14 $$
> 3 votes

---
Tags: algorithms, scheduling
---


# Question
Title: Can we enumerate finite sequences which have no halting continuation?
Note: this question has been cross-posted to Math.SE, after about a week here.

I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's *Completeness* Theorem (not Incompleteness).

Specifically, as I understand it the Completeness Theorem guarantees a finite proof for any first-order logical statement which holds in all countable models of a first-order theory. (This is my restatement of Wikipedia's "Every syntactically consistent, countable first-order theory has a finite or countable model.")

Since the statement "Program $P\_n$ (encoded by integer $n$) does not halt" can presumably be stated in first-order logic and cannot in general be proven, we need to understand why (for given $n$) it does not hold in all countable models.

Intuitively, I expect that any countable model can be encoded as an infinite program for a Turing machine, eg by listing the countable set of first-order propositions. Likewise, I expect that any such "infinite Turing machine" can be identified with a countable first-order theory, by the Church-Turing thesis plus induction.

So, just as the Completeness Theorem fails to "solve" arithmetic because of non-standard models with infinite integers (which eg satisfy otherwise unsatisfiable Diophantine equations), I'm speculating that it fails for Turing machines because of non-standard models with "infinite programs".

But by my understanding statements which are true in all models (including non-standard / infinite ones) should still be provable. So I expect that if some finite set of axioms, which "pins down" some finite set of digits of a potentially infinite program, is enough to prevent the possibility of halting, we should be able to prove it.

Or in other words, if a finite sequence does not have any continuation which encodes a halting program, that should be provable.

Does my logic hold? Or what am I misunderstanding?

The reason this is not trivially wrong by Rice's Theorem is that it's a property of the program itself, rather than the language recognized by that program, which is $\emptyset$ for the programs I'm talking about.

# Answer
> 1 votes
The language of your question confuses me a bit ("if a finite sequence does not have any continuation which encodes a halting program" - what exactly does that mean?), but I think the following is likely to clarify the situation:

Let's take as our "base theory" first-order Peano arithmetic, $\mathsf{PA}$. We could use pretty much any reasonable theory here, but $\mathsf{PA}$ has the advantage of being broadly known, so I'll use it. Let $(M\_e)\_{e\in\mathbb{N}}$ be some fixed usual enumeration of Turing machines. The following is indeed true:

* The set $$\mathsf{MustHalt}=\\{n\in\mathbb{N}: \mbox{Every model of $\mathsf{PA}$ thinks $M\_n$ halts on input $n$}\\}$$ is c.e., by the completeness theorem.
* The set $$\mathsf{Can\mbox{'}tHalt}=\\{n\in\mathbb{N}: \mbox{No model of $\mathsf{PA}$ thinks $M\_n$ halts on input $n$}\\}$$ is *also* c.e. by the completeness theorem, and disjoint from $\mathsf{MustHalt}$ (I'm assuming $\mathsf{PA}$ is consistent here obviously).
* However, the set $$\mathsf{MightHalt}=\mathbb{N}\setminus(\mathsf{MustHalt}\cup\mathsf{Can\mbox{'}tHalt})$$ is not c.e.; indeed, $\mathsf{MustHalt}$ and $\mathsf{Can\mbox{'}tHalt}$ are *computably inseparable*, and $\mathsf{MightHalt}$ is co-c.e.-complete exactly as each of the former is c.e.-complete.

The second bulletpoint above is, perhaps, an affirmative answer to your question. But the third bulletpoint should stress the difficulty of drawing strong conclusions from that: the c.e.-ness of halting prevention is not, actually, that sweeping a phenomenon (indeed by Godel's *in*completeness theorem it can't possibly be).

# Answer
> 0 votes
> Intuitively, I expect that any countable model can be encoded as an infinite program for a Turing machine, eg by listing the countable set of first-order propositions.

This is untrue, which may be a part of your confusion: in certain countable (but non-standard) models of arithmetic, even the interpretation of operators like $+$ and $\times$ may be non-computable, see for example Tennenbaum's theorem.

# Answer
> -1 votes
Not an answer, but too long to be a comment:

> Specifically, as I understand it the Completeness Theorem guarantees a finite proof for any first-order logical statement which holds in all countable models of a first-order theory. (This is my restatement of Wikipedia's "Every syntactically consistent, countable first-order theory has a finite or countable model.")

I'm not a logician so I don't know if the latter statement is *true*, but it's definitely not a restatement of the first statement.

The statement you quoted from Wikipedia says if you have countably many axioms and they're consistent then there exists at least one model of the theory with countably many elements.

What Godel's completeness theorem says that if a statement is true then it has a proof.

What you're missing to bridge the two is "a statement true in every *countable* model is true in *every* model." I don't know if this is true or not (logicians would probably know off the tops of their heads).

---
Tags: undecidability, halting-problem, rice-theorem
---


# Question
Title: Why is $\mathsf{QP}$-hardness impossible?
I found this task in an old exam and couldn't get my head around it:

> We define the class of languages $\mathsf{QP}$ as follows: $$\mathsf{QP} = \bigcup\_{k \in \mathbb N} \mathsf{DTIME}(2^{\log(n)^k})$$ Show that there is no $L \in \mathsf{QP}$ such that $K \leq\_p L$ for all $K \in \mathsf{QP}$

#### Some details on notation:

* $\mathsf{DTIME(f)}$ conatains all languages $L$ for which there exists a deterministic turing machine that accepts all $w \in L$ with max $f(|w|)$ steps.
* $\leq\_p$ is used to express polynomial reducability

#### My attempt

Suppose, there is an $L\in\mathsf{QP}$ such that $K \leq\_p L$ for all $K \in \mathsf{QP}$. Then $L \in \mathsf{DTIME}(2^{\log n^k})$ holds true for some natural number $k$. It follows, that $L'\leq L$ will also hold true for $L' \in \mathsf{DTIME}(2^{\log n^{k'}})$ with $k \< k'$. That leads to $L' \in \mathsf{DTIME}(2^{\log n^{k}})$. But this contradicts $\mathsf{DTIME}(2^{\log n^k})\subsetneq \mathsf{DTIME}(2^{\log n^{k'}})$ which has to hold true because of the time hierarchy theorem.

#### Question

If this is correct, the same thing should be possible to argue that there is no such thing as $\mathsf{NP}$-hardness?

# Answer
Let's back to the definition of many-one reduction.

Suppose, $L\_1 \le\_p L\_2$. Then, there is a function $r$ such that $L\_1(x) = L\_2(r(x))$. Moreover, $r$ is polynomial-time computable so there exists a number $l$ such that $|r(x)| \in O(|x|^l)$. Note that if $L\_2 \in \mathrm{DTIME}(f(n))$, then $L\_1 \in \mathrm{DTIME}(f(n^l))$.

Now, if a language $L \in \mathrm{DTIME}(n^{(\log n)^{k\_0}})$ is $\mathrm{QP}$-complete, the existence of the reduction implies $$\tag{1}\bigcup\_{k \ge 0} \mathrm{DTIME}(n^{(\log n)^k}) \subseteq \bigcup\_{l \ge 0} \mathrm{DTIME}(\[n^{(\log n)^{k\_0}}\]^l)$$ However, because $$\tag{2}\[n^{(\log n)^{k\_0}}\]^l \in O(n^{(\log n)^{k\_0 + 1}})$$ if we set $k = k\_0 + 2$ in the LSH of (1), we have $$\tag{3}\mathrm{DTIME}(n^{(\log\_n)^{k\_0+2}}) \subseteq \mathrm{DTIME}(n^{(\log\_n)^{k\_0+1}})$$ contradicting the time hierarchy theorem.

Why cannot the same argument be applied to other classes such as $\mathrm{NP}$? $\mathrm{DTIME}$ can be changed to $\mathrm{NTIME}$, but the issue is we don't have the relation (2). There is no $k$ such that $(n^{k\_0})^l \in O(n^k)$ for all $l \ge 0$.
> 1 votes

---
Tags: complexity-theory, turing-machines, time-complexity, polynomial-time-reductions, check-my-answer
---


# Question
Title: Misunderstanding Turing's Halting-Problem Argument
I just watched a video by Computerphile on the halting problem (https://www.youtube.com/watch?v=macM\_MtS\_w4) . I’m having some difficulty understanding the argument as it is made. Let me explain it as I see it:

So that our terminology is the same, H is a (hypothetical) program which can analyze another program to see if it halts. H+ is a modified version of H which loops forever if the analyzed program halts and halts if the analyzed program does loops forever.

In order to run H, you need to specify 2 things – a program and the input to that program. The Input to the analyzed program is necessary because the program’s behavior will depend on its input.

According to Computerphile’s explanation of Turing’s argument, we are asked to consider what would happen if H+ were to analyze H+ with H+ as its input. Since there are a lot of H+’s being thrown around, let’s define H+1 as the program that I am running, H+2 as the program being analyzed, and H+3 as the input to H+2. (Of course, H+1, H+2, and H+3 have the exact same code; they are just being used in different ways.) My question is this: if we require H+3 as an input to H+2, then shouldn’t we require an input to H+3? And if we continue the pattern and use H+4 as an input to H+3, then wouldn’t this mean that we require an H+5 as an input to H+4? And so on?

If you counter by saying that Turing’s argument doesn’t require H+3 to have an input (or that its input doesn’t have to be H+), then doesn’t this break the whole symmetry of the problem? After all, the whole point of Turing’s argument (as I currently understand it) is that if H+2 runs on H+3 and halts then it would be a contradiction to have H+1 loop forever on H+2 since H+1,H+2,and H+3 are all identical (and vice versa were H+2 to loop forever on H+3). But the situation isn’t identical. In one case H+2 is running on H+3. In the other, H+1 is running on "H+2-running-on-H+3".

I guess you could say that each H+ maybe can only look one step in front of it, so that H+1 only “sees” H+2 and H+2 only sees H+3. But then what does H+3 see? Doesn’t it need some input of its own? After all, whether or not H+3 halts depends on the program it’s given. If so, this brings it back to my first point (that we would need an H+4).

It seems to me this whole argument falls apart. Either you would need an infinite stack of H+’s which can’t happen, or you have a finite stack which because of the discontinuity at the end means that the symmetry of each level doesn’t translate to the one below it.

So what am I missing?

# Answer
"So what am I missing?"  Nothing.    Computerphile should have defined H++ by  H++(x) = H+(x,x) ,  and then run *H++* on itself.
> 4 votes

# Answer
The problem is just the number of inputs of the program H+. Let's try to rewrite it:

*H* takes an input *d* and and input *i*.
For simplicity, let's say that *H+* only takes one input *x* and calls *H* with the inputs *x* and *x*, i.e, the same input twice.
(You can think of *H+* as a program taking two inputs and discarding the second one, just uses the first and passes it to *H*, twice)

If *H* exists, *H+* exists.

If *H+* halts on input *H+*, then *H+* does not halt.
If *H+* runs forever on input *H+*, then *H+* does not run forever.

Conclusion, *H* does not exists.

You can read this also: http://www.jjinux.com/2010/05/python-halting-problem.html
> 3 votes

# Answer
Ok so you are considering the approach where H+ is a machine in the input itself. For this approach the proof is a bit long but still works.

**“What am I missing?”:** These two cases - In one case H+2 is running on H+3 and In the other, H+1 is running on "H+2-running-on-H+3" *are actually identical!* Because if you apply H+ two or more times, result is the same - 1st H+ declares halt, then in the 2nd H+, the H of it first declares infinite loop (because it’s programmed as H+), so finally 2nd H+ declares halt as well.

**Proof for this approach:**

So when H+ is given itself as input and the program to analyse, the function execution is an infinite time execution, this is because in the input itself there is an H+ machine and as the main H+ is having both input and program as H+, the input machine also must have the same, to be on the same page so that they can contradict after all. Now in the input machine, the input of this input machine is H+ as well and to that input of input machine as well there is and so on, so it's an infinite time execution.

Now, in a practical scenario input H+ will take infinite amount of time to execute because of the infinite time execution it has. However the catch is that that infinite time execution is not same as an infinite loop.

And the beauty of the proof is that the H machine in the main H+ always can give the answer!

So it tells tells what the H+ input will give and at the end it contradicts with main machine.

*The contradiction part:*

The contradiction part comes like this, suppose H+ halts -\> remeber that H of main machine is programed with H+ -\> so internal H of H will say halt, but H will say infinite loop as it behaves as H+ -\> so main H+ say halts. Now here is tha main part and it is a catch as well: H+ says the opposite. So in this case it is declaring itself to be going to an infinite loop (itself in the input), but itself in the whole machine has halted. So it's a contradiction.

**Approaches I am talking about:**

I believe there are two approaches that Turning wanted to suggest and wanted to suggest that in the both the cases there is a contradiction:

1. We consider H+ in the input as a string of 0 & 1. That is we code using TM coding.
2. We consider H+ in the input as a program.

He left the second approach as an exercise probably as I have seen only the first approach in all the books and videos including Computerphile's.

For completion let me clear first approach as well. And I will refer H+ in input as constant string A = 011011 let's say, in general A can be anything of (o|1)\*.

**1st Approach:**

*Scenario:* H+ is fed with H+ & string A as program and input respectively.

*What happens:* If internal H declares H+ on A halts, actual H+ (main machine) declares infinte loop and the other scenario when internal H declares the other.

*Contradiction:* Scenario is same for both main machine and what internal H is interpreting. That is "What does H+ do when it's given itslef as the program and A as the input?". But results are different so it's a contradiction.

*Conclusion:* H+ is an improved H machine and it's function is same as H just in a different style - "It declares whether a program on an input doesn't halt - by halting". But H+ doesn't work when it's fed itself as the program and any input from (0|1)\*. So as existence of always working H guarantees existence of always working H+, but we have just found out that H+ doesn't work always, so both H+ & H doesn't exist.

**Overall conslusion:**

You can take conclusion of the "1st approach", and apply it to the "2nd approach" as an exercise :)
> 0 votes

# Answer
I wonder if it will be easier to understand the real issue if there is a sly version of the Halts(program,input) program that instead was HaltsInUnderTenOperations(x,i).

Maybe you can use the same argument against Halts(x,i) to prove HaltsInUnderTenOperations(x,i) is not possible either, if you feed it to a program that halts it if it says no (would have taken ten or more operations) but makes it take ten or more operations if it says yes (would have halted in under ten operations).

Or rather than ten, choose an appropriately small finite number for which it would be self-evident that you can easily tell what the output of HaltsInUnderTenOperations will be - in other words, you can solve it but it is a logical contradiction and therefore an impossible program.

The fact there is nothing wrong with the program that halts or doesn't based on the simple "yes/no" input, means the program that has something wrong with it is the Halts (or the HaltsInUnderTenOperations).

This may seem confusing but it is similar to how the Busy Beaver problem is easily solvable from 1 or 2 states.
> -2 votes

---
Tags: algorithms, halting-problem
---


# Question
Title: n search operations on an arbitrary Splay tree
For an arbitrary spay tree with `n` nodes, if we perform `n` find operations, is there a way of generalizing what the tree would look like after `n` operations and proving it mathematically?

One such example (Sequential Access Theorem): if the splay tree has the elements `V1, V2,..., Vn`, where `V1 ≤ V2 ≤ ... ≤ Vn`. And the find operations are in the order: `V1, V2,..., Vn`.

# Answer
> 0 votes
AFAIK, there is no general expected form for a splay tree given some arbitrary search sequence. Despite this, it is known to perform as good as any balanced BST. For some specific kind of search sequences with special properties, splay tree is known to perform better. Although, it is open whether it performs optimally for all kind search sequence (**Dynamic Optimality Conjecture**).

As for the latter case where you search items in sorted order, you are interested with the sequential access on splay tree. This is one of the special sequence that a splay tree handles efficiently. Although the form of the tree may vary based on the tree's initial form, the way the tree changes can be characterized and analyzed. The original analysis of Tarjan can be found here. You can also check this alternative analysis if you have no access to the previous paper.

---
Tags: binary-search-trees, splay-trees
---


# Question
Title: Spanning tree that maximizes all-pairs bandwidth => Maximum spanning tree?
Let $G = (V, E)$ be a weighted, undirected graph, with $f: E \to \mathbb{R}$ its weight function. Given a path $P = (e\_1, \dots, e\_k)$, we call $\operatorname{bwd}(P) = \min\_{1 \le i \le k} f(e\_i)$ the "path-bandwidth" of $P$. Let $\mathcal{P}\_G(v, w)$ be the set of paths between two vertices $v, w \in V(G)$. Given two vertices $v, w \in V$, we call $\operatorname{bwd}\_G(v, w) = \operatorname{max}\_{P \in \mathcal{P}\_G(v, w)}{\operatorname{bwd}(P)}$ the bandwidth in $G$ between $v$ and $w$. That is, the maximum path-bandwidth of any path in $G$ between $v$ and $w$.

If $T$ is a spanning tree of $G$, $\operatorname{bwd}\_T(v, w) = \operatorname{bwd}(P)$ where $P$ is the path from $v$ to $w$ in $T$. We call $T$ a "maximum pairwise bandwidth spanning tree" (MPBST) when $\operatorname{bwd}\_T(v, w) = \operatorname{bwd}\_G(v, w)$, for all $v, w \in V$.

It is easy to show that every maximum spanning tree is a MPBST.

Experimentally the converse seems to hold: Every MPBST is a maximum spanning tree. Is this true, and if so, why?

I tried proving this using induction in the minimum symmetric difference between an MPBST and the set of all maximum spanning trees of $G$, to show via edge swaps I can make an MPBST of the same weight as the original one, but closer and closer in symmetric difference to this set. I could not finish the argument unless I assumed all weights were distinct.

# Answer
Yes, it is true that every MPBST is a maximum spanning tree.

---

Here is a characterization of maximum spanning Tree(MST). A proof for that characterization can be found here.

> Given a spanning Tree $T$ of $G$, $T$ is an MST $\iff$ for any edge $uv\notin T$, $uv$ has the minimal weight among edges in the cycle created by adding $uv$ to $T$.

---

Suppose $S$ is an MPBST. Let us prove $S$ is an MST.

Let edge $uv\notin S$. Let $P$ be the path from $v$ to $u$ in $S$, i.e., the cycle created by adding $uv$ to $S$ is $P$ followed by edge $uv$.

Since $((u,v))$ is a path from $u$ to $v$, $\operatorname{bwd}\_G(u, v)\ge\operatorname{bwd}\_{((u,v))}(u,v)=w((u,v))$.

Since $S$ is an MPBST, $$\operatorname{bwd}(\text{the path from }v\text{ to }u\text{ in }S)=\operatorname{bwd}\_S(u,v) = \operatorname{bwd}\_G(u, v)\ge w((u,v)),$$ i.e., edge $(u,v)$ has the minimal weight among edges in the cycle created by adding $uv$ to $S$. By the characterization of MST, $S$ is an MST.
> 1 votes

---
Tags: graphs, weighted-graphs, minimum-spanning-tree, spanning-trees
---


# Question
Title: Proving a reformulation of the $(\ge k)\mathit{-SAT}$ problem is in P
> Consider the $(\ge k)\mathit{-SAT}$ problem, where you are given a CNF (conjunctive normal form) formula $F$ such that each clause has at least $k$ literals, and the goal is to determine whether $F$ is satisfiable. A literal can occur at most once in a clause.
>
> Prove that the $(\ge n)\mathit{-SAT}$ problem is in $\mathsf{P}$, where $n$ is the number of input variables in the input formula.

I am having a lot of issue setting up this proof, can anyone help or guide me?

# Answer
The problem statement doesn't make clear whether literals are allowed to repeat in clauses. If literals are allowed to repeat then you can reduce 3SAT to your problem, which is thus NP-complete. This suggests that the intended interpretation is that each literal appears at most once.

Clauses which contain both a variable and its negation are always satisfied, so we can remove them. Any clause that remains forbids exactly one truth assignment. You take it from here.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Does creating a deep copy of a string of size N (in python) take space complexity O(N) or O(1)?
My question comes from solving this LeetCode question, in which we are given a string of characters with size N, and one of the solutions is to use a hashmap (dictionary in Python) to count the characters, with the character being the key, and the count being the value.

For instance, "abbcddd" results in a hashmap {'a':1, 'b':2, "c":1, "d":3}. This is the second solution given by LeetCode.

I thought the space complexity of this solution is O(N), because if the string has all unique characters, we will need the hashmap to have N keys. However, the solution says the space complexity is O(1), because

> Space complexity : O(1). The map can grow up to a maximum number of all distinct elements. However, the number of distinct characters are bounded, so as the space complexity.

Then I have this follow up question - if a problem requires me to create a deep copy of a string (or an array) of size N, does it take space O(N) or O(1)? Is it O(1) because the maximum length of the copied string/array is bounded by the original string/array?

Thanks.

# Answer
If the output of the algorithm is the deep-copied string, the complexity is O(1), because you don't count the input nor output space.

If the copy is used for internal purposes, then the complexity is at least O(N).

But this is unrelated to the LeetCode question, which does not require a deep copy. (The required space is bounded by the alphabet size.)
> 2 votes

# Answer
> I thought the space complexity of this solution is O(N), because if the string has all unique characters, we will need the hashmap to have N keys

Remember, big-O tells you the tendency as N goes to infinity. If a string has more than around 2^21 characters (assuming valid Unicode) they *can't* all be unique, by the pigeonhole principle, so as N increases beyond this point, the number of elements in the map stops growing — the definition of O(1).
> 1 votes

---
Tags: arrays, space-complexity, strings, upper-bound
---