# Question
Title: Halting problem - What if the halting algorithm gave more than one output?
Sorry I don't know how silly a question this might be, but i've been reading up on the halting problem lately, and understand the halting problem cannot possibly output a value that is "correct" when fed a machine that does the opposite of itself. This therefore proves the halting problem cannot be solved by contradiction.

What if you were to give the halting algorithm 3 possible outputs, something like:

* Yes
* No
* Non-deterministic (for paradox's like this one)

You could argue then that for a non-deterministic output it would then do something entirely different, but this would be okay because it is still non-deterministic behavior. For a simple algorithm input, such as a `while True: pass` it would be incorrect to output non-determinism, since it will always be No.

I was wondering if this would change its solve-ability, or would it still be un-solvable?

Thanks for any responses

# Answer
> 1 votes
*It doesn't matter if and when some newly defined machine $M$ outputs an extra value - the original machine $H$ of the halting problem still leads to a contradiction.*

---

The proof of the halting problem relies on showing that if we assume there is an oracle machine $Q$ solving the halting problem that we can construct a machine $H$ that uses $Q$ such that a logical contradiction results, proving that $H$ cannot be constructed. But if $H$ cannot be constructed then either the act of constructing $H$ from $Q$ is impossible (i.e. mathematics as a whole is inconsistent and we can just go home) or $Q$ is impossible.

Of course you can imagine you can construct another machine $M$ from $Q$ which gives an answer that is not contradictory - the simplest such machine is $M=Q$. However, this is completely irrelevant: for proof by contradiction it is enough that it is possible to construct a single contradiction because once there is even a single contradiction it all collapses. Therefore it does not matter how many non-contradictory examples you construct - they do not make the contradiction go away.

This is because in mathematics you cannot "replace" anything like you could replace a flat tire: the halting problem uses a machine $H$ to construct a contradiction. If you now use a machine $M$ that causes no contradiction then it no longer is the "**h**alting problem" but the "**m**alting problem" - something completely different. Therefore no matter what you do, the solvability of the halting problem does never change.

So yes, you can construct your new machine $M$ such that it doesn't lead to a contradiction - but it doesn't change the solvability of $H$.

---

So it doesn't even matter how you construct $M$. But let's consider it anyway.

* If there exists $F$ such that $Q=F^{-1}\circ M$ (and thus $M=F\circ Q$) on a sufficiently large domain (necessarily countably infinite, but that's not sufficient) then $M$ is an oracle machine like $Q$, so it can be input to the halting problem and still lead to a contradiction.
* If such an $F$ doesn't exist then $M$ does not fulfill the premise of the halting problem because $M$ is no oracle machine. Then the halting problem does not apply to $M$ \- but that does not mean that the halting problem is "solved" - it simply doesn't apply in this case.

The reason why other commentators are asking for your precise definition of $M$ is because depending on that definition it falls into one or the other case and they don't know which one.

But as per the above considerations that is irrelevant.

---

> Say you do construct $M$ from $F$ and $Q$, how do you then construct $H$ that results in a contradiction on the new oracle machine?

The construction is simple: if $H=G\circ Q$ then $H'=G\circ Q'$ where $Q'=F^\*\circ M$ where $F^\*$ could be defined e.g. as $F^\*(\textrm{"maybe"})=\textrm{"no"}$ (several other constructions are possible: one could renumber the indices, asking for the $n$th value that doesn't provide "maybe", just like we can ask for the $n$th prime number - either way, the "maybe" can be eliminated).

**But the critical question is: is $M$ (and therefore $Q'$) still an oracle?**

If $M$ is no longer an oracle then the halting problem does not apply. And if it is an oracle the halting problem still leads to a contradiction.

The halting problem asks for a an oracle $Q$ which can determine for **all** functions whether they halt.

That is, the function is supposed to be total, producing always 0 "yes" or 1 "no" but never $\bot$ (not halting).

Your machine $M$ is equivalent to taking a "partial oracle" $P$ that is partial, ocasionally producing $\bot$ and declaring that $M$ knows when $P$ would produce $\bot$ and return "maybe" instead.

Conversely, for your machine $M$ we can construct $P$ by having it do an endless loop whenever it encounters "maybe".

Some such provers $P$ (and associated $M$) can be constructed. For example:

* if there exists $n\in\mathbb{N}$ such that $M(k)=\textrm{"maybe"}$ for all $k\>m$ then it's no oracle (or a rather poor one) because it decides only finitely many cases.
* But even if it decides infinitely many cases it still might be no oracle: let's say $M(2\cdot k)=\textrm{"maybe"}$ for all $k\>m$ so it ignores only the even ones - but the functions associated to the odd numbers could all be defined as $F\_{2\cdot k+1}(n)=n+k$ which trivially halts.

To them the halting problem does not apply because they do not promise computing all functions.

---

Ultimately, it comes down that we can compute only functions which we can describe by a finite program, so we can give them a number $n\in\mathbb{N}$ to identify them.

However, the functions go $f:\mathbb{N}\rightarrow\mathbb{N}$. There exist $\mathbb{N}^\mathbb{N}=\mathbb{R}$ such functions, but the computable functions can address only $\mathbb{N}$ of them.

The halting problem is asking about whether we can identify the subset of $\mathbb{N}$ representing functions that terminate - and answers in the negative, stating that an oracle being capable of deciding this cannot be represented by a finite number, i.e. needing an infinitely large program.

1. So if you have infinitely many memory and time you could construct an oracle that can decide whether an arbitrary program terminates or not.
2. In practice one can only construct a "partial oracle" that can be represented by a finite number. The halting problem doesn't apply - but it also can decide only a limited (albeit infinite) number of functions.
3. What remains are partial oracles that cannot decide everything (hence the halting problem doesn't apply) yet still need an infinite description - which is the worst of both worlds.

# Answer
> 1 votes
Suppose we allow an algorithm to return "Yes, it halts", "No, it doesn't halt", or "I don't know". Then the proof no longer applies; and in fact this modified version of the halting problem is decidable. For instance, a very simple algorithm could always output "I don't know", and it'd never be wrong. Unfortunately, that very simple algorithm probably isn't very useful.

If this is what you meant by "non-determinism", then it is possible but not useful.

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


# Question
Title: How to build a TM which decides $L_k := \{(\langle M \rangle ,x)\in HP : |(\langle M \rangle ,x)| \le k \}$
For a specific natural $k$ we define the language of couples $(\langle M \rangle, x)$ such that $M$ stops on $x$ and the couple's encoding is bounded by $k$ i.e $L\_k := \\{(\langle M \rangle ,x)\in HP : |(\langle M \rangle ,x)| \le k \\}$ This language is finite thus in $R$. I wish to understand how to build (Not formally) a TM, $\tilde{M}$ which decide this language. Since the only given information is that the encoding is bounded, I tried to think about "Pigeonhole" claim, i.e define $\tilde{M}$ which simulate $M$ computation on $x$ and remembering the configurations made by $M$ or by counting steps made by $M$ during the simulation in order to determine that $M$ is stuck in a loop. Since $M$ is deterministic, if $\tilde{M}$ "see" the same configuration twice, it guarantees that $M$ entered a loop, but I can't explain why the finite encoding of $(\langle M \rangle,x)$ promises that a configuration will repeat itself.

# Answer
You cannot construct an explicit algorithm/TM which will decide the language $L\_k$. Regarding your attempt at the proof: you are right that there is no guarantee that the configuration will repeat because these machines are not given to be *space bounded*.

The TM $M\_k$ to decide $L\_k$ will have all the tuples (which are finite in number) which are accepted *hard coded* in it. The TM will basically perform a search in a look up table: if that tuple is found then accept it, else reject. We don't care how these tuples are actually obtained.

We can perhaps even prove that a general method to construct such TM $M\_k$ for each $L\_k$ cannot exists: Suppse there exists, then for a given input $\<M,x\>$, find the length of input, let it be $k$ and construct the TM $M\_k$. Simulate $M\_k$ over $\<M,x\>$. This will act as a decider for Halting Problem: which we know is undecidable. Hence, the assumption that we can have such a method is false.
> 1 votes

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


# Question
Title: MST with degree constraints on some node
While preparing for an algorithms exam I came across the following problem in a practice test:

Let $G = (V,E)$ be a connected, undirected graph with weighted edges (all weights are rational numbers but not necessarily all unique) and let $v$ be some node in $G$.

Design an algorithm that finds a minimum spanning tree of $G$ where $\deg(v)=2$ if one exists or indicates if there is no such tree.

Full credit will be given for solutions with the same time complexity as Prim's algorithm ($O(|E| + |V|\log |V|)$). Partial credit will be given for solutions whose time complexity is $|V|\cdot$Prim, and minimal credit will be given for solutions with greater time complexity.

The first step in any solution must be to use Prim or Kruskal's algorithm to find the target weight for such an MST. From there, though, I've tried a number of different methods of approaching this problem but all the successful ones require halting an existing MST algorithm before it's done, i.e. prioritizing all $v$'s edges, running Kruskal until $v$''s degree is two, then deprioritizing them and continuing the algorithm, etc.

The problem is that my professor flat-out refuses to accept answers that involve stopping an algorithm in the middle, insisting that this would require one to re-prove the correctness of the entire algorithm.

Does anyone have a solution? The problem has been eating at me for a few weeks now and I haven't been able to find an answer on the internet anywhere. The professor said she won't tell us the answer and I suspect she intends to put this question on this or future exams.

Thanks very much in advance for your time.

# Answer
Here's an algorithm that just reduces to MST; no need to modify Prim's or some other algorithm. The idea is simple: remove $v$, compute the MSTs of the resulting components of the graph, and then stitch them together with $v$. The interesting case is when removing $v$ doesn't disconnect the graph.

I'll assume the input graph $G$ is connected, although it would not be difficult to generalize this idea to computing a minimum spanning forest. Also, obviously the degree of $v$ needs to be at least 2.

### Algorithm

Start by removing $v$ and all incident edges; call this $G'$. Now compute the number of connected components in $G'$. This can be done with DFS or something similar.

**More than 2 components**: If $G'$ has more than 2 connected components, no solution is possible.

**Exactly 2 components**: If $G'$ has exactly two connected components, then we can construct a solution by using $v$ as the "bridge" between the two components: just connect the MSTs of the components with the cheapest edges through $v$.

**Exactly 1 component**: If $G'$ has exactly one component, we can compute $T' = \text{MST}(G')$, and then we just need to stitch $v$ into $T'$ using two edges.

1. Find the cheapest edge incident on $v$ and add this to $T'$. Call this $T''$. Now we have a spanning tree, but not necessarily minimum.
2. Iterate over all other edges incident on $v$. For each of these, we will try to construct a MST where $d(v) = 2$. If we don't find one, then no solution is possible.
    * Consider some incident edge $(u,v)$ which is not the lightest edge on $v$.
    * Observe that if we added this edge to $T''$, it would create a cycle.
    * If $(u,v)$ is the heaviest edge on this cycle, then skip this edge, because no solution is possible using $(u,v)$.
    * Otherwise, we can take out the heaviest cycle edge and add $(u,v)$ instead. Now we have a spanning tree where $d(v) = 2$. If this spanning tree is minimum, we're done. (We can determine if a spanning tree is minimum just by computing *any* $\text{MST}(G)$ and comparing weights. This "reference" MST only needs to be computed once.)

It's not immediately obvious that this is within cost bounds, because for each of $O(|V|)$ edges incident on $v$, we have to compute the heaviest edge in the tree on the path between $v$ and some other vertex $u$. However, these "path queries" are well studied in the literature, and can be computed in $O(\log|V|)$ by preprocessing $T''$ into a balanced lookup structure. Some examples include binary lifting, Miller-Reif rake/compress tree contraction, and Sleator-Tarjan link/cut trees. The link/cut trees are actually far more general: they handle dynamic trees too! But here we only need to preprocess a static tree, i.e. $T''$.

---

**Edit**: My original idea was to do the following, which doesn't work (thank you @VladislavBezhentsev for pointing this out in the comments!). It doesn't work because, while we know that the cheaper of $e\_1$ and $e\_2$ is certainly in the MST (by the cut property), it's not necessarily true that the heavier of the two edges is!

> (Incorrect idea): Find the two cheapest edges $e\_1$ and $e\_2$ that are incident on $v$. Add $e\_1$ and $e\_2$ to $T'$: this creates a cycle. If the largest edge on this cycle is either $e\_1$ or $e\_2$, no solution is possible. Otherwise, remove the largest edge on the cycle.
> 2 votes

# Answer
This is not a complete solution, but just an idea.

1Choose 2 edges out of $v$ (maybe using a greedy heuristic)

2 Find the MST for G - { $v$, $u$} (where $u$ is the one of the 2 selected neighbors). Then add $v$ with its 2 edges (this way v & the other node are added).

3 Repeat to reach the optimal answer.
> 0 votes

# Answer
Here is an algorithm that runs in about triple Prim's time, which is still $O(|E| + |V|\log |V|)$. The basic idea is to adapt OP's idea so as to determine or approximate the answer from the case of least degree and the case of most degree.

---

Denote the given weight function by $w\_\text{orig}$. Let $\epsilon$ be the *smallest positive* difference between two different edge weight. Let the edges that are incident to $v$ be $\mu\_1, \mu\_2, \cdots, \mu\_k$ for some $1\le k\le |E|$. .

**First run of Prim.** Define a new weight function $w\_{\text{disfavor}}$, which is the same as $w\_\text{orig}$ except that $w\_\text{disfavor}(\mu\_k)=w\_\text{orig}(\mu\_k) + \frac\epsilon 2$ for all $k$. Run Prim's algorithm on $(V,E, w\_\text{disfavor}$). Consider the edges that are incident to $v$ in the returned MST. Call those edges "required edges".

* If there are more than two "required edges", return "there is no such tree". Stop the whole algorithm.
* Otherwise, continue.

**Second run of Prim.** Define a new weight function $w\_{\text{favor}}$, which is the same as $w\_\text{orig}$ except that

* $w\_\text{favor}(\mu\_k)=w\_\text{orig}(\mu\_k) - \frac\epsilon 2$ for all $k$ such that $\mu\_k$ is a "required edge".
* $w\_\text{favor}(\mu\_k)=w\_\text{orig}(\mu\_k) - \frac\epsilon 3$ for all other $k$, i.e., such that $\mu\_k$ is not a "required edge".

Run Prim's algorithm on $(V,E, w\_\text{favor}$). Consider the edges that are incident to $v$ in the returned MST. Call those edges "selectable edges". Note that all "required edges" are "selectable edges".

* If there are less than two "selectable edges", return "there is no such tree". Stop the whole algorithm.
* Otherwise, continue.

**Third run of Prim.** Select "additional edges", which are "selectable edges" but not "required edges" so that the total number of edges that are either "required" or "additional" is 2. Define a new weight function $w\_{\text{final}}$, which is the same as $w\_\text{orig}$ except

* $w\_\text{final}(\mu\_k)=w\_\text{orig}(\mu\_k) - \frac\epsilon 2$ for all $k$ such that $\mu\_k$ is a "required edge".
* $w\_\text{final}(\mu\_k)=w\_\text{orig}(\mu\_k) - \frac\epsilon 3$ for all $k$ such that $\mu\_k$ is an "additional edge".
* $w\_\text{final}(\mu\_k)=w\_\text{orig}(\mu\_k) + \frac\epsilon 2$ for all other $k$, i.e., such that $\mu\_k$ is neither a "required edge" nor an "additional edge".

Run Prim's algorithm on $(V,E, w\_\text{final}$). Return the Obtained MST.

---

The above algorithm only applies the exact vanilla version of Prim's algorithm as a black box. This peculiar requirement by OP's professor does not seem attractive to me, although it may be interesting.

The above algorithm works still if we replace Prim with Kruskal everywhere.
> 0 votes

---
Tags: minimum-spanning-tree
---


# Question
Title: Why is it that Ternary search trees are memory efficient?
I'm trying to figure out why ternary search trees are memory efficient. I have tried to read up on this, but all articles I find only state it's memory efficient compared to tries, but not why.

I believe it has something to do with the middle node, and with its ability to handle duplicate keys in a better way than tries, but I'm still not sure.

Why are TST's more memory efficient then tries?

# Answer
**Tries**

Tries store strings character by character. See the figure below of a tree that represents the same set of 12 words.

Each input word is shown beneath the node that represents it. In a tree representing words of lowercase letters, each node has 26-way branching. Searches are very fast: A search for "is" starts at the root, takes the "i" branch, then the "s" branch, and ends at the desired node. Unfortunately, search tries have exorbitant space requirements: Nodes with 26-way branching typically occupy 104 bytes, and 256-way nodes consume a kilobyte. Eight nodes representing the 34,000-character Unicode Standard would together require more than a megabyte!

**Ternary Search Trees**

Ternary search trees combine attributes of binary search trees and digital search tries. Like tries, they proceed character by character. Like binary search trees, they are space efficient, though each node has three children, rather than two. A search compares the current character in the search string with the character at the node. If the search character is less, the search goes to the left child; if the search character is greater, the search goes to the right child. When the search character is equal, though, the search goes to the middle child, and proceeds to the next character in the search string.

The figure above shows a balanced ternary search tree for the same set of 12 words. The low and high pointers are shown as solid lines, while equal pointers are shown as dashed lines. Each input word is shown beneath its terminal node. A search for the word "is" starts at the root, proceeds down the equal child to the node with value "s," and stops there after two comparisons. A search for "ax" makes three comparisons to the first letter ("a") and two comparisons to the second letter ("x") before reporting that the word is not in the tree.

Searching for a string of length `k` in a ternary search tree with `n` strings will require at most `O(log n+k)` comparisons.

The primary challenge in implementing digital search tries is to avoid using excessive memory for trie nodes that are nearly empty. Ternary search trees may be viewed as a trie implementation that gracefully adapts to handle this case, at the cost of slightly more work for full nodes. Ternary search trees combine the best of two worlds: the low space overhead of binary search trees and the character-based time efficiency of digital search tries.

Hope it helps! Reference: Link
> 4 votes

---
Tags: data-structures
---


title: What is $2^{O(n)}$?

text:
# Question
Title: What is $2^{O(n)}$?
How can I interpret a time complexity of $2^{O(n)}$? Is it simply equal to $O(2^n)$?

I'm pretty new to this, so would appreciate any kind of help.

# Answer
> 3 votes
$O(2^{O(n)})$ means: It is $O(2^{f(n)})$ for some function f with f(n) ≤ cn for large n.

So this could be $O(2^n)$ if c = 1, or $O(2^{2n})$ = $O(4^{n})$ if c = 2, or $O(2^{100n})$ = $O((2^{100})^{n})$ if c = 100. We don't know. All we know is it grows pretty fast, and we can't simply express it as O(something).

# Answer
> 3 votes
The expression "$2^{O(n)}$" is shorthand for "$2^{f(n)}$ for some function $f(n) = O(n)$". For example, $3^n = 2^{O(n)}$. This example also demonstrates that a function which is $2^{O(n)}$ is not necessarily $O(2^n)$, though the opposite does hold.

---
Tags: time-complexity
---


title: Is a language regular

text:
# Question
Title: Is a language regular
Given a regular language $L$ (so there is an automaton $A$ which recognizes $L$), I need to determine whether $ L'$ is also regular, where $L'$ is given by $$ L' = \\{ \alpha \in \Sigma^\* \mid (\exists \beta \in \Sigma^\*)\[ |\alpha| = 2 |\beta| \wedge \alpha\beta \in L \\}.$$ As far as I understand, I have to construct an automaton $A'$ that recognizes the language $L$.

I was thinking of making the automaton so it has two pointers, one pointing at the beginning states and one at the final states, and the automaton states are the cartesian product of the automaton states from $A$, and the left pointer is going to move 2 states to the right, and the right pointer 1 state to the left. Any suggestions?

# Answer
*(I think by pointers you mean the "pebbles" that are described in Kozen's Automata and Computability.*)

The language $L'$ is regular.

You can prove that as follows: Consider the DFA $D\_1 = (Q, \delta, F, q\_0)$ for $L$. We will create another automata $D\_2 = (Q \times Q \times Q \times \\{0,1\\}, \Delta\_2, F\_2, I)$.

$I = \\{(q\_0, q, q, 0) : q,q\_0 \in Q\\}$

$F = \\{q, q\_F, q, 0 : q\_F \in F, q \in Q \\}$

Let's first understand the intuition before defining the transition function $\Delta\_2$:

* We are constructing two layers: all the transitions in the first layer will be to some state in the second layer, and all those in the second layer will be toward the first layer.
* On reading an alphabet when on a state of the form $(q\_1, q\_2,q\_2, 0)$, the state in the first entry will change as per the transition function of $D\_1$. The state in the second entry will also follow $D\_1$, but it will be *symbol agnostic*, in the sense that it can change to any state irrespective of the symbol. The third entry will remain the same. *(It is used to save the state at which we started the second pebble)*. The fourth entry will change from 0 to 1 which is equivalent to moving from one layer to another.
* When on a state of the form $(q\_1, q\_2,q, 1)$, all the transitions are $\epsilon$ transitions and move us back to $(q\_1, q\_2',q\_2, 0)$ where $q\_2'$ is a state which is reachable from the state $q\_2$ in $D\_1$.

So in this automata, we first non-deterministically choose a start state of the form $(q\_0, q, q,0)$. The state $q$ is the state from which we are reading $\beta$, and from $q\_0$ we are reading the actual input $\alpha$. As the automata reads the word, for each letter of $\alpha$, we non-deterministically choose two letters for $\beta$ and run the same automata from that state in the second component. If on reading $\alpha$ we end up in the state we started reading $\beta$ (which is chosen non-deterministically), and the second component reaches a final state in $D\_1$, then it means that the $\exists \beta : \alpha \beta \in L$. And hence we accept.

Formally, \begin{equation} \Delta\_2((q\_1, q\_2, q, 0),a) = \\{(\delta\_1(q\_1, a), \delta(q\_2, x), q, 1) : x \in \Sigma)\\}\\ \Delta\_2((q\_1, q\_2, q, 1),\epsilon) = \\{(q\_1, \delta(q\_2, x), q, 0) : x \in \Sigma)\\} \end{equation}.

---

There is an easier way (as OP described): Let $D\_1'$ be the NFA obtained by reversing all the transitions in $D\_1$ and allowing all symbols for each transitions *(i.e., make it symbol agnostic)*. Take the states to be 3-tuples from $Q \times Q \times \\{0,1\\}$. Start from $(q\_0, q\_f, 0)$ where $q\_f \in F$. On reading a letter, move from state $q\_0$ as per $D\_1$, and move two steps from $q\_f$ according to the $D\_1'$. The final states can be $(q,q,0)$ where $q\in Q$.

You can try figuring out why this works.
> 1 votes

# Answer
Take the language L and an DFA for it. For any two states $S\_i$ and $S\_j$, we can determine all the lengths of strings that would go from $S\_i$ to $S\_j$: To get there, we will have single character transitions, and loops, and in any case the possible lengths will be of the form ak + b for fixed a ≥ 1 and 0 ≤ b \< a and k ≥ $k\_0$, plus various lengths \< $ak\_0$. Then we calculate the lengths of all strings that lead from $S\_i$ to an accepting state, they will have the same form. Then we calculate the lengths of strings that the input string reaching $S\_i$ could have to be in L', these are twice the lengths of strings going from $S\_i$ to an accepting state.

For example a\*(bb)\*c: After processing zero or more a's, k characters can lead to an accepting state, k ≥ 1. After processing an even number of b's, it is 2k+1, k ≥ 0. After an odd number of b's, it's 2k, k ≥ 1. After the c, it's 0. Anything else, it is empty. So the lengths of strings that may lead to these states are 2k, k ≥ 1, or 4k+2, k ≥ 0, or 4k, k ≥ 1, or 0, or none at all.

We now split the states of the DFA to keep track of the steps needed to get there. If the number of steps is right, the state is accepting.

We now modify the DFA: We split each
> 0 votes

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


# Question
Title: Why is $NP \subseteq P \implies NP^A \subseteq P^A$ false?
My question is about why does the result of Baker-Gill-Solovay not prove that $P \neq NP$. There have been several questions on this forum about this topic perhaps but I couldn't find my specific question amongst them.

**Context**: This is what I had in mind when I first saw the Baker-Gill-Solovay result (there exists an oracle $A$ such that $P^A \neq NP^A$): I will try to give a proof for $P \neq NP$. Suppose $P=NP$ then $P^A = NP^A$ for all oracles $A$. By Baker-Gill-Solovay result we arrive at a contradiction. When I asked my prof about this he said that the implication $P=NP \implies P^A = NP^A$ is wrong. So I wanted to check why (and where) does it fail.

I think it is correct that $P \subseteq NP \implies P^A \subseteq NP^A$ for all oracles $A$ because any poly-time TM with oracle access to $A$, is also a poly-time NDTM with oracle access to $A$.

My question is: Why *(if $NP \subseteq P$ then for any oracle $A$, $NP^A \subseteq P^A$)* is false?

---

My reasoning would go as follows: $NP \subseteq P$ means that given any NDTM (which involves a guessing sequence, followed by a poly-time verification), I can replace the guessing sequence with some poly-time TM. But given a NDTM with oracle access to $A$, I **cannot** directly replace the guessing sequence with some poly-time TM (as per the hypothesis), because in this NDTM, the guessing sequence might involve the access to oracle $A$.

Following that, I want to argue why isn't it so, that given a NDTM with oracle access to $A$, I can move all these calls to oracle $A$, after the guessing sequence? That is to say - why couldn't I, using non-determinism, guess the answers to my oracle queries and in the final step, verify these particular guesses using actual oracle queries?

---

More precisely, can I not re-define the definition of $L \in NP^A$ as follows: there exists a poly-time TM $M$ and a polynomial $p$ such that $x \in L \iff \exists w$ such that $|w| \leq p(|x|)$ and $M^A(x,w) = 1$?

Apologies for being too vague in my arguments above but I have just started learning Complexity Theory.

**Edit1**: Changed the question from *given a oracle $A$, if $NP \subseteq P$ then $NP^A \subseteq P^A$* to *if $NP \subseteq P$ then for any oracle $A$, $NP^A \subseteq P^A$*

**Edit2**: My definitions are: $P^A$ is the set of languages decided by a poly-time TM with oracle access to $A$ and $NP^A$ is the set of languages decided by a poly-time NDTM with oracle access to $A$

**Edit3**: Added more context to the problem.

# Answer
> 3 votes
Your statement holds for all oracles $A$ iff $\mathsf{P} \neq \mathsf{NP}$. Indeed, if $\mathsf{P} \neq \mathsf{NP}$ then your statement vacuously holds. Conversely, if $\mathsf{P} = \mathsf{NP}$, then your statement fails for a random oracle $O$, since such an oracle satisfies $\mathsf{P}^O \neq \mathsf{NP}^O$ almost surely.

A similar argument shows that if $A$ is a $\mathsf{PSPACE}$-complete language then your statement holds, since in that case $\mathsf{P}^A = \mathsf{NP}^A$ is known to hold.

The proof that $\mathsf{P} \subseteq \mathsf{NP}$ *relativizes*, which means that it works even in the presence of an oracle. That is, the proof only uses arguments that keep holding even when the Turing machines are allowed access to an oracle. In all other cases, you cannot conclude from a statement of the form $\mathsf{A} \subseteq \mathsf{B}$ that $\mathsf{A}^O \subseteq \mathsf{B}^O$ for all oracles $O$. The two statements are about two different objects: the first one is about Turing machines without oracle access, and the second one is about Turing machines with oracle access to $O$.

This actually happens in practice, as mentioned in the comments: $\mathsf{IP}=\mathsf{PSPACE}$, but there are oracles $O$ relative to which $\mathsf{IP}^O \neq \mathsf{PSPACE}^O$.

---
Tags: complexity-theory, proof-techniques, oracle-machines, relativization
---


title: Distance queries on Tree with hotspots

text:
# Question
Title: Distance queries on Tree with hotspots
We are given a tree with $n$ vertices and some of the vertices act as a "hotspot".

We have to answer multiple queries of type $(a,b,c)$, which means we have to find the distance to the nearest hotspot from $c$ such that we do not travel through the edge between nodes $a$ and $b$.

I have tried many data structures like using lowest common ancestor and algorithms like mo's algorithm on a tree, I have also tried to process queries which are closer to root first, but none of these have given me the desired complexity for each query which is anywhere between $O(1)$ to $O(\log n)$.

Is there any better algorithm or perhaps some clever precomputation(in less time than $O(n\log n)$ that can be used to solve this problem?

# Answer
> 1 votes
You can use the top-tree data structure. It maintains a forest $F$ on $n$ nodes and supports (among others) each of the following operations in $O(\log n)$ time per operation:

* Given an unmarked vertex $v$ mark $v$.
* Given a marked vertex $v$ unmark $v$.
* Given two vertices $u,v$ that belong to two different trees in $F$, add the edge $(u,v)$ to $F$ (thus merging two trees into one).
* Given an edge $(u,v)$ of a tree in $F$, delete $(u,v)$ from $F$ (thus splitting the three into two).
* Given a vertex $v$, report the distance to the marked vertex that belongs to the tree of $v$ and is closest to $v$.

This allows you to preprocess your tree in time $O(n \log n)$: build the forest $F$ on $n$ nodes by adding the edges of the tree one by one (so that, at the end, $F$ contains the input tree), then mark each hotspot.

To answer a query $(a,b,c)$ in time $O(\log n)$ proceed as follows:

* Delete $(a,b)$ from $F$ in time $O(\log n)$.
* Find the distance $d$ to the marked vertex that is closest to $c$. This takes $O(\log n)$ time and is exactly the answer to the query.
* Re-add $(a,b)$ to $F$ in time $O(\log n)$.
* Return $d$.

# Answer
> 1 votes
Merge all hotspots into a single node $h$ (Instead of a tree - the input is now an undirected graph). The problem can now be represented as follows:

Given an undirected graph $G$ and a node $h$ (the merged hotspot), we want to answer queries $Q(c, e)$:

$Q(c, e)$: Given node $c\in G$ and edge $e\in G$, return $\mathrm{distance}(h, c)$ in $G\setminus \\{e\\}$.

This is a dynamic problem, or more specifically: an *edge-decremental single-source shortest-path distance problem* (also called *single-source edge-removal exact distance oracle*).

In \[\], the preprocessing time is $O(mn^{1.5} + n^{2.5} \log n)$ and the query time is $O(1)$. This is an All-Pairs Shortest Paths algorithm, while you require only a single-source algorithm.

\[\] improves the results to $O(\sigma^{0.5}\cdot n^{1.5})$ preprocessing time and $O(1)$ query time. $\sigma$ is the number of sources (in your case: $\sigma=1$ \- the merged hotspot).

Following \[\], you can get an $O(n^{1.5})$ preprocessing time and $O(1)$ query time using $O(n^{1.5})$ memory.

---
Tags: algorithms, graphs, data-structures, trees
---


# Question
Title: Adding a vertex in graph in adjacent matrix repersentation
In website geeksforgeeks i read that adding a vertex to graph in adjacent matrix takes O(V^2) time but i am not getting it. It requires adding a row and a column which should take linear time ? I am a beginner hence forgive me for such a question

Link:- https://www.geeksforgeeks.org/graph-and-its-representations/

# Answer
It more or less depends on the implementation. If you have implemented the matrix using linked lists (which isn't what we usually do), then adding a new vertex in $G$ will be linear in the number of vertices of $G$. But we don't usually use linked lists because then reading/checking an edge will take $V(G)^2$ time.

To allow random/constant time access of the adjacency matrix, we need to use fixed-size arrays of arrays (or matrix). Now, when you add new vertex, we are required to copy the whole matrix into a bigger size matrix: hence the quadratic time.

Generally, we use $vectors$ instead of $arrays$ which hold *extra hidden memory*, and hence it will indeed be linear time to add a vertex on average. https://www.geeksforgeeks.org/vector-in-cpp-stl/
> 1 votes

# Answer
Yes will takes *O(V2)*, Suppose you have a small graph from vertices 1, 2, 3, 4 and each vertex connected to each other, So you have

```
1 [2, 3, 4]
2 [1, 3, 4]
3 [1, 2, 4]
4 [1, 2, 3]

```

To add this graph you need to loop for each vertex and add an edge (a link) to V-1 using LinkedList

You will find that the time complexity V * (V-1) which it's *O(V2)*
> 0 votes

---
Tags: graphs
---


# Question
Title: Grammar still ambigous after removing left recursion LL(1)
I have following grammar it doesnt not have Epsilon-derivation problem I can only see left recursion:

```
S -> a b S
S -> S a b
S -> c d
S -> a d

```

in production number 2 there is left recursion which I removed and I got:

```
S -> a b S F
S -> c d F
S -> a d F
F -> a b F | EPSILON

```

But it is still ambigous?

# Answer
> 0 votes
Removing left-recursion from a grammar does not make it unambiguous. That's not the intent of removing left-recursion, and an ambiguous grammar is likely to still be ambiguous after left-recursion is removed.

In the case of your grammar, you have two productions which are inevitably ambiguous:

```
S → a b S
S → S a b

```

The first production allows an `S` to start with a sequence of `a b`, while the second production allows an `S` to end with such a sequence. However, nothing in the grammar specifies which of these two things takes priority. Since the order of grammar rules is unspecified, there are an exponential number of possible parses; although you might consider all the parses to be semantically equal, the parser needs to produce a single unique parse tree.

The solution, therefore, is to be clear about which parse tree to produce, which can be done fairly simply by creating a new outer production which handles one or the other of the alternatives. So, depending on your preference about associativity, you might use:

```
S' → S' a b
S' → S
S → a b S

```

or

```
S' → a b S'
S' → S
S → S a b

```

Alternatively, you could define a new non-terminal which just represents a sequence of `a b`:

```
S' → A S A
A → A a b
A → ε

```

In all cases, you should only consider removing left-recursion if you propose to use an LL parser. And if you plan on using an LL parser with only one token of lookahead, you'll have to deal with the prediction conflict resulting from the other rule for `S` which begins with `a` (by left-factoring, for example).

---
Tags: parsers
---


# Question
Title: Language with $\log\log n$ space complexity?
We know that every non-regular language can be recognized with $ \Omega (\log\log n) $ space complexity.

I'm looking for an example of a language which is $ \Theta (\log\log n) $ space complexity (if such exists).

# Answer
> 11 votes
I found the answer below in lecture notes of Muli Safra.

Consider the language consisting of the following strings: $$ \begin{align\*} & 0 \\$ 1 \\$ \\ & 00 \\$ 01 \\$ 10 \\$ 11 \\$ \\ & 000 \\$ 001 \\$ 010 \\$ 011 \\$ 100 \\$ 101 \\$ 110 \\$ 111 \\$ \\ &\ldots \end{align\*} $$ This language can be recognized in space $O(\log\log n)$. For each $m$ which is smaller than the width of the first block, we check that the $m$ least significant bits form a counter modulo $m$ starting at $0$ and ending at $2^m-1$. We stop when $m$ is the width of the first block.

Since this language clearly isn't regular, it requires space $\log\log n$ (see for example these lecture notes by Hansen). We conclude that the language requires space $\Theta(\log\log n)$.

# Answer
> 2 votes
There is an interesting language that is $\Theta({loglog(n)})$, I found it in the free google book preview of the book "Turing Machines with Sublogarithmic Space", Here is the language:

$C = \\{a^n|F(n)\text{ is a power of 2}\\}$

$F(n)=\min\\{i|i\text{ does not divide n}\\}$ It is $\Theta(\log\log(n))$ because of the following construction of an accepting Turing machine $M$:

On an input $w=a^n$, $M$ computes $F(n)$ in binary and check if it is power of 2.

To compute $F(n)$, $M$ writes natural numbers in Binary format one by one up to the moment it finds that the number does not divide $n$ on its tape.

To check if a number written in binary on its tape divides $n$, it suffices to use a modulo $k$ counter on the tape and go from one end of the input to the other, counting $a$ symbols.

$F(n) \le c\*\log(n)$( the proof is included in the book as lemma 4.1.2(d)) thus the space needed for storing the binary representation of $F(n)$ is $O(\log \log (n))$ and it is easy to check whether a number written in Binary format is a power of two or not, so the language $C$ is space bounded by $O(\log \log (n))$.

Other interesting property of this language is that it is not a regular language and the proof using pumping lemma is also included in the book. Any language needing strictly asymptotically less space(i.e languagues that space bounded $o(\log \log n)$) are regular.

---
Tags: formal-languages, space-complexity
---


# Question
Title: Is the following language is a context free grammar language?
The question is to determine whether L is a context free grammar language, what do you think?

# Answer
> 1 votes
Consider the word $w = 0^n1^n0^n \\# 0^n1^n0^n \in L$ for a sufficiently large value of $n$.

By the pumping lemma for context-free languages, we know that if $L$ is context-free then there are$a,b,c,d,e = \Sigma^\*$, with $|bcd| \< n$ and $|bd|\>1$ such that $w=abcde$ and, for every $i \ge 0$, $a b^i c d^i e\in L$.

Notice that neither $b$ nor $d$ can contain $\\#$, as otherwise setting $i=0$ would show that $a c e \not\in L$.

If $c$ contains $\\#$, then $b,d \in 0^\*$ and $a b^i c d^i e$ is a word of the form $0^n 1^n 0^{x + i|b|}\\#0^{y+i|d|} 1^n0^n$ with $x+|b|=n$ and $y+|d|=n$. If $|b|\>0$ you can make the first part of the word (before $\\#$) end with more than $n$ zeros by picking $i=2$, resulting in a contradiction. Otherwise $|d|\>0$ and you can make the second part of the word (after $\\#$) start with less than $n$ zeros by setting $i=0$.

If $c$ does not contain $\\#$ then $b$ and $c$ either both precede or both follow the unique occurrence of $\\#$ in $w$. If they precede $\\#$, pick $i=2$. If they follow $\\#$, pick $i=0$. In this way the first part of the word becomes longer than the second (and hence not in $L$).

# Answer
> 0 votes
This is not a CFL. We can prove this using *pumping lemma for CFL*.

We prove it as follows: Consider the string $s = 0^n1^n0^n\\#0^n1^n0^n \in L$. By pumping lemma, for a significantly large $n$, we can split the string in five parts: $u,v,w,x,y$ such that $s = uvwxy$, $|vx| \> 0$, and $uv^mwx^my \in L$ for all $m$.

Basically, you have to find out two parts of the string $s$ (at least one is non-empty), such that no matter how many times you pump it, the pumped string has to be in $L$.

It is not hard to see that no splitting satisfies the pumping lemma:

* If both $v$ and $x$ are on left side of #, then the pumped string won't stay substring of the string on right side of #.
* Work out other cases...

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


# Question
Title: Longest palindrome substring in logarithmic runtime complexity
In a palindrome of size N, the amount of candidates for the longest palindrome is N^2. Therefore, the information theoretic lower bound (IBT) should be lg(N^2), which is equivalent to a runtime complexity of lg(N).

By IBT I mean that if we use a comparison based algorithm and you think about a decision tree to apply it, the leafs of that tree will be all of the possibilities (N^2 leafs), therefore the height of that tree is lg(N^2). However, I was not able to find any algorithm that is able to solve this question in this runtime complexity; the best I have found is Manacher's algorithm that solves the question in linear time.

# Answer
If a you are given a palindrome $p$ of size $N$ (as you say in the beginning of the question), then the longest palindrome is $p$ itself and you don't need to do any computation.

If your input is not a palindrome but an arbitrary string, then you need to at least read the input and therefore $\Omega(N)$ is a trivial lower bound.
> 2 votes

---
Tags: algorithms, algorithm-analysis, decision-problem, comparison, decision-tree
---


title: Turing Machine state going to itself

text:
# Question
Title: Turing Machine state going to itself
Hey guys in a turing machine can a state go to itself by reading a letter. For example,

q2 reading a 'c' to go to itself. Is that possible?

Or does it need to read a tape alphabet, such as $ to read that c and then go back to q2?

# Answer
Yes, a state can go to itself when seeing any symbol. (As Steven's answer says, the analogous question for *head movement* \- whether the head of the Turing machine has to move at each stage, or whether it can stay put at a given moment - varies from definition to definition, but I've never seen a definition which prohibits a state from looping to itself.)

* Note that this is a particularly natural thing to allow: it's basically a "while" command.

However, as with many aspects of Turing machines, tweaking the definition to rule it out isn't significant: Turing machines which prohibit states from looping to themselves are no weaker than Turing machines which allow states to loop to themselves. This is a good exercise.
> 1 votes

# Answer
That depends on the exact definition of Turing Machine that you are using.

I am used to a definition where the transition function $\delta$ is a function from $(Q \setminus F)$ to $Q \times \Sigma \times M$, where $Q$ is the set of all states, $F$ is the set of final states, $\Sigma$ is the tape alphabet, and $M=\\{\text{left, right, stay}\\}$ specifies the movement of the head.

In this case a Turing machine can definitely have a transition of the type $\delta(q, c) = (q, \alpha, \text{stay})$ (for any $\alpha \in \Sigma$).

However, according to Wikipedia the set of allowed movements in the transition function used by the definition from Hopcroft & Ullman does not contain $\text{stay}$.

Anyway, since this can be simulated by going to a new intermediate state while moving the head (left or right), and then going back to the intended state while repositioning the head on the previous position, there is no difference in the computing power or time complexity (up to multiplicative constants) among the two definitions.
> 0 votes

---
Tags: turing-machines, automata, finite-automata
---


title: Uniquely identifying bits

text:
# Question
Title: Uniquely identifying bits
Query: Given $m$ unique integers smaller than $2^n$, can we keep at most $k$ the same bits of each number to uniquely identify them?

Is this problem NP-Hard?

For example, given the $4$ unique numbers smaller than $2^3$

```
011
100
101
110
 ^^

```

The numbers are still unique if we remove the leftmost bit from each number. So for $k = 2$, the answer is yes: we keep bits {0, 1} (the rightmost bit is here defined as the bit with index 0).

---

I want to solve the above problem as a precomputation step for integers less than 20 bits, so for my application an exponential algorithms could be allowed. Then it would be great to minimize $k$ and then break ties in such a way that the number of gaps between the indices that are kept is minimized. For example, {0, 1, 2, 5, 7} has two gaps: between 2 and 5 and between 5 and 7. This precomputation should lead to a great hash function for a set of integers. In my application the sets of integers don't change later.

# Answer
> 2 votes
Your problem is NP-hard. To see this, you can reduce it from the minimum test cover (or test collection) problem: given a set $X$ of $\ell$ elements and a collection $C = \\{C\_1, \dots, C\_k \\}$ of $k$ subsets of $X$, find a minimum *test* cover for $X$ and $C$, i.e., a subset $C'$ of $C$ that has minimum size and satisfies the following property: for every pair of distinct elements $i,j \in X$ there is a set in $C'$ that contains exactly one of $i$ and $j$.

The reduction is as follows: for each element $x \in X$ create a number of $k$ bits $b\_1,\dots,b\_k$ where $b\_i = 1$ if and only if $x \in C\_i$. There is a test-cover $C' = \\{ C\_{i\_1}, C\_{i\_2}, \dots \\}$ if and only if the $|C'|$ bits in positions $i\_1, i\_2, \dots$ suffice to distinguish all input numbers.

Since the above reduction sets $m=\ell$, the measures for two corresponding solutions of test-cover and your problem coincide, and test cover is not approximable within a factor of $o(\log \ell)$, this also shows that your problem is $o(\log m)$-inapproximable.

On the bright side, the converse reduction works too: given an instance of your problem you can create an instance of minimum test cover by considering the set $X$ containing your $\ell = m$ input numbers $x\_1, \dots, x\_m$ and $C = \\{C\_1, \dots, C\_k \\}$ as a collection of $k = n$ sets where $C\_i = \\{ x \in X \mid \text{the $i$-th bit of $x$ is } 1 \\}$. This means that the $O(\log \ell)$-approximation algorithm for minimum test-cover immediately translates to a $O(\log m)$-approximation algorithm for your problem.

See this paper and this paper.

---
Tags: algorithms, np-complete, sets, bit-manipulation
---


# Question
Title: Is the source file size smaller than the executable file size?
Wondering if compilation increases file size in general, is the source file size smaller than the executable file size?

# Answer
This is heavily dependent on the source language, target language, compiler, etc...

In general, it is possible the size of the compiled code to be both larger and smaller than the source code (but not simultaneously :p)

For example, on my machine, the following code compiles to an executable of 16456 bytes (compiled with g++ with size optimization `-Os`)

```
int main() {return 0;}

```

The following code also results in an executable of exactly the same size (16456 bytes) but its source uses 32670 bytes:

```
int main()
{
    int i;
    if(i==0) return 0;
    else if(i==1) return 1;
    else if(i==2) return 2;
    [...]
    else if(i==1023) return 1023;
    else if(i==1024) return 1024;
    else return i;
}

```
> 1 votes

# Answer
This depends on how the libraries used were linked in. If you statically link many libraries in you’ll end up with a much bigger executable. So the executable can easily exceed the size of the source code, but the individual object files (pre-linking) that go with the code just compiled may be smaller.

EDIT:

Some others considerations apart from library linkage of why "it depends":

* Comments don’t get written to the code or data sections of the executable.
* Compiling with debug yields larger files.
* Executables have some overhead as they have instructions for the loader.
* Instructions are system-dependent, e.g, 64-bit will take up more room than 32-bit
* Some languages are more verbose than others.

For example, here we compile an empty main() to illustrate.

```
$ cat empty.c
main(){}
$ gcc -g3 -c empty.c -o debug.o
$ gcc -g0 -c empty.c -o nodebug.o
$ gcc -g0 -m32 -c empty.c -o 32bit.o

```

Source code is identical, but but the 32-bit object file is smaller than the 64-bit, and the object with debug is larger than the one without.

```
$ stat -c "%n %s" *.o *.c
32bit.o 490
debug.o 12611
nodebug.o 720
empty.c 8

```

Another example: compile this other file that has a lot of comments. Our 616,334 byte source code compiles to 490 bytes of object file.

```
$ gcc -g0 -m32 -c bigcomment.c -o bigcomment.o
$ stat -c "%n %s" *.o *.c
bigcomment.o 490
bigcomment.c 616334

```
> 0 votes

---
Tags: data-compression
---


# Question
Title: Finding a closed formula for recurrence relation
I'm trying to find a closed formula for the below recurrence relation:

For the first one, $n$ is some power of 2

$$T(n) = \begin{cases} 4 & \text{if $n=1$} \\ 2T(\frac{n}{2}) +4 & \text{else} \end{cases}$$

$$T(n) = \begin{cases} 1 & \text{if $n=0$} \\ T(n-1) +3^n & \text{else} \end{cases}$$

I tried to use the substitution and tree methods but I'm not sure what I'm doing and I think I get the wrong answer.

# Answer
> 0 votes
When you are not sure of whether you get the right answer, you can write a simple program in any of your favorite languages to double check.

For example, for the first function, I became pretty confident that I got the right answer once I had run the following script in Python.

```
def T(n):
    if n == 1: return 4
    return 2 * T(n // 2) + 4

for i in range(1, 20):
    print(T(2 ** i), 2 ** (i + 3) - 4)

```

Similarly, I ran the following script for the second function.

```
def S(n):
    if n == 0: return 1
    return S(n - 1) + 3 ** n

for i in range(20):
    print(S(i), (3 ** (i + 1) - 1) // 2)

```

---
Tags: time-complexity, data-structures, recurrence-relation
---


# Question
Title: Why in a min priority queue (heap based) it is called "decrease-key" and not just "set-key"?
When you call decrease-key in a min priority queue, you are basically setting the key, you can accidentally put a higher key, right? so why isn't it called "set-key" or "update-key"? why (according to Wikipedia and other sources) a min priority queue has "decrease-key" and a max priority queue has "increase-key"? why not have both "set-key" and if you decrease it or increase it, do what you should do to keep the heap property invariant?

I mean what if I call decrease-key on a min heap and give a bigger value? Will it throw an exception? Why not just call it "set-key" and handle any kind of value?

# Answer
> 12 votes
Good question. One of the important applications of the data structure PriorityQueue is in Dijkstra's algorithm. Each node gets a distance from the initial node, which is updated when shorter paths are discovered. Hence updates only change the key in one direction.

The problem in the implementation of DecreaseKey is not that it is only decreasing (rather than updating the value). For a binary heap there are quite efficient methods both for increasing and decreasing. They both swap nodes with other nodes along a path in the tree (either upwards or downwards). The problem is actually knowing where to find the key. You cannot efficiently search for it, so a separate "index" has to be kept. When an update is done along a path, not only the decreased key is changed in the indax, but also the other keys along the path.

For abstract data structures we want to specify *only* the operations that are important in a particular context. So we have DecreaseKey only, given the Dijkstra motivation. Although for binary heaps extending the operations might be elementary, this might not be the case for other implementations of the PriorityQueue, like Leftist Heaps, Fibonacci Heaps, or Brodal Heaps.

What any particular implementation will do when the new value is in the wrong direction is up to that implementation.

# Answer
> 1 votes
The naming of the method is probably deliberate in some textbooks (e.g. CLRS) because:

1. The logic for "floating down" or "bubbling up" a key in a binary heap is straightforward if you know which direction (up/down) you are going. E.g. "bubbling up" a key is simply a recursive call on the node parents, vs floating down where you need to compare with *each child*, before proceeding recursively.
2. Many algorithms that use max / min heaps require you to only increase or decrease keys, so it's enough to provide the corresponding "floating down" or "bubbling up" method.

Note that if you wanted to implement a generic "set key" method you could simply combine these two routines to decide which direction to go based on whether or not you need to bubble up or float down the key.

To add to what Hendrick said, it's worth noting that even for e.g. Dijkstra's or Prim's algorithms where technically speaking a **decrease key** operation is enough, using a binary heap does **not** necessarily require you to keep track of the position of each key.

In these algorithms a given key is extracted from the heap **only once**. For example, in Dijkstra a graph node is only added once to the shortest paths tree, and in Prim's algorithm, an edge *may* only be added once to the minimum spanning tree.

Thus, instead of keeping track of key positions (or searching for them when the algorithm needs to decrease them), on can simply insert the **new** (in this case **lower**) **value** for the key in the heap (leading to duplicates in the heap), and then, once you extracted the "key" from the heap (technically satellite data since the key is not what you are greedily consuming), you can ignore all of its subsequent extractions (e.g. using a set with $O(1)$).

Such set and key duplicates in the heap would obviously cost you $O(n)$ in space complexity, but you could think of the combined solution as a "decrease key" method that requires **no** knowledge or tracking of positions in the heap.

---
Tags: terminology, data-structures, priority-queues
---


# Question
Title: Intersection of two particular languages
Here's the question:

> Compute the intersection of the following two languages: \begin{align} &L\_1 = \\{ a^{n+1} b^{2n} a^{n+1} \mid n \ge 0 \\} \\ &L\_2 = \\{ w \in \\{a,b\\}^\* \mid \\#\_a(w) + \\#\_b(w) \equiv 1 \pmod 2 \\} \end{align}

I'm pretty sure that $L\_2$ is just "$|w|$ is odd", which would mean the intersection of the two languages would be $L\_1$ when its length is odd, right?

What I'm confused about is that $|w|$ for every $w ∈ L1$ will always be even no matter what $n$ is.

Can someone help me find the solution? I have absolutely no clue how to do it.

Edit: #a(w) + #b(w) %2 = 1 not 0 (my bad)

# Answer
$$L\_1 = \\{a^{n+1}b^{2n}a^{n+1} \mid n \ge 0\\}$$

$$L\_2 = \\{w \mid (\\#\_a(w) + \\#\_b(w)) \bmod 2 = 1\\}$$

I assume that $\\#\_a(w)$ means the number of $a$s in $w$.

First, I would write out some $w$ in $L\_1$ and $L\_2$:

$$L\_1 = \\{aa, aabbaa, aaabbbbaaa, \ldots\\}$$

$$L\_2 = \\{a, b, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaaa, \ldots\\}$$

From this, we see that words in $L\_1$ are always even length ($(n+1) + (2n) + (n+1) = 4n + 2 = 2(2n+1)$ and odd + even + odd = even) and words in $L\_2$ are always odd length ($(a+b)\bmod2 = 1$).

This means $L\_1 \cap L\_2 = \emptyset$.

**Before OP's edit to post** ($L\_2 = \\{w \mid (\\#\_a(w) + \\#\_b(w)) \bmod 2 = 0\\}$):

First, I would write out some $w$ in $L\_1$ and $L\_2$:

$$L\_1 = \\{aa, aabbaa, aaabbbbaaa, \ldots\\}$$

$$L\_2 = \\{aa, ab, ba, bb, aaaa, aaab, aaba, \ldots\\}$$

From this, we see that words in $L\_1$ are always even length ($(n+1) + (2n) + (n+1) = 4n + 2 = 2(2n+1)$ and odd + even + odd = even) and words in $L\_2$ are always even length ($(a+b)\bmod2 = 0$).

This means $L\_1 \cap L\_2 = L\_1$ (because $L\_1 \subset L\_2$).
> 2 votes

---
Tags: formal-languages
---


# Question
Title: Induction Proof on Independent Set Variation Algorithm
So I am given this blackbox algorithm, in which given a Graph G and a integer k, it returns yes if there is an independent set of size k, no otherwise.

My algorithm is suppose to output impossible if there is no independent set of size k, or output an independent set of size k if it exists.

How might this be approached?

# Answer
> 2 votes
Let $G$ be a graph with an independent set of size $k$, and let $v$ be an arbitrary vertex. There are two potential types of independent sets of size $k$ in $G$:

* Independent sets not containing $v$: These are independent sets of size $k$ in $G \setminus \\{v\\}$.
* Independent sets containing $v$: These are formed by adding $v$ to independent sets of size $k-1$ in $G \setminus \\{v\\} \setminus N(v)$, where $N(v)$ is the neighborhood of $v$.

Using an oracle for independent set, we can find which of these cases happen.

The basic idea can be implemented in many ways. Here is a recursive implementation, which uses the oracle $O(G,k)$, which answers whether $G$ contains an independent set of size $k$.

* Procedure $I(G,k)$
* Input: Graph $G$ and integer $k \geq 1$
* Output: Independent set of size $k$ in $G$, or "No" if none exists

1. If $O(G,k)$ returns "No", then return "No".
    2. Let $v \in G$ be arbitrary.
    3. If $k = 1$, return $\\{v\\}$. Otherwise, continue.
    4. If $O(G \setminus \\{v\\},k)$ returns "Yes", return $I(G \setminus \\{v\\},k)$.
    5. Otherwise, return $O(G \setminus \\{v\\} \setminus N(v),k-1) \cup \\{k\\}$.

---
Tags: algorithms, graphs
---


title: Partitioning tuples

text:
# Question
Title: Partitioning tuples
Given are tuples $(a\_{11},\dots,a\_{1k}), (a\_{21},\dots,a\_{2k}), \dots, (a\_{n1},\dots,a\_{nk})$. We want to know if there is a partition of the tuples into two parts, so that for every coordinate $i=1,\dots,k$, the sum of each part is equal to the sum of the other part.

Has this problem been studied before? If $k=1$, it is of course the famous Partition problem. But I cannot find this generalization under the section "Variants and generalizations" in the Wikipedia page.

# Answer
> 2 votes
This is essentially the same problem as partition. Let $M$ be a large enough integer, and replace each tuple $(a\_{i1},\ldots,a\_{ik})$ with the single integer $\sum\_j a\_{ij} M^j$. You now have an equivalent instance of PARTITION.

Your problem appears in the literature, under the name *multidimensional two-way number partitioning*, in Jelena Kojić, Integer linear programming model for multidimensional two-way number partitioning problem.

---
Tags: reference-request, partitions
---


# Question
Title: Merge $k$-sorted arrays - without heaps/AVL tree in $O(n\log(k))$?
> Given $k$-sorted arrays in ascending order, is it possible to merge all $k$ arrays to a single sorted array in $O(n\log(k))$ time where $n$ denotes all the elements combined.

The question is definitely aiming towards a Min-heap/AVL tree solution, which can in fact achieve $O(n\log(k))$ time complexity.

However i'm wondering if there exists a different approach, like a merge variant which can achieve the same result.

The closest I've seen is to merge all the arrays into one array which disregards their given ascending order, than doing comparison-based sort which takes $O(n\log(n))$ but not quite $O(n\log(k))$.

Is there an algorithm variant which can achieve this result? Or a different data-structure?

# Answer
> 1 votes
For the sake of avoiding dealing with rounding in the analysis, assume for simplicity that $k$ is a power of $2$ (if it is not, you can add $d \le k-1$ dummy arrays with one $+\infty$ element each, and ignore the last $d$ elements in the final sorted vector).

You can merge your arrays two by two in a binary-tree fashion: the algorithm works in $\log k$ phases. In phase $i=0, \dots , \log k - 1$ there are $k/2^i$ sorted arrays, where the arrays of phase $0$ are the $k$ input arrays. These arrays are arbitrarily grouped into $k/2^{i+1}$ pairs and each pair is merged. The resulting arrays are moved to the next phase. At the end of the $(\log k - 1)$-th phase there is only one sorted array $A$ remaining. Return $A$.

The total amount of work on each phase (a level of the tree) is $O(n)$, and the number of phases (i.e., levels) is $O(\log k)$.

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


title: All total functions form a PRC class

text:
# Question
Title: All total functions form a PRC class
> A class of total functions is a *PRC class* if:
>
> 1. The class includes all projection functions $p\_i(x\_1,\ldots,x\_n) = x\_i$ and the initial functions $n(x) = 0$ and $s(x) = x+1$.
> 2. The class is closed under composition and primitive recursion.
>
> Prove that the class of all total functions is a PRC class.

Is it true if I say every total function is computable? And then say because the class of computable functions is a PRC class, so is the class of total functions.

# Answer
> 1 votes
You cannot say that every total function is computable, since that is not true. For example, the function $f(n)$ which returns $1$ if the $n$'th Turing machine halts and $0$ otherwise is *not* computable.

However, the question is much simpler. The definition of a PRC class specifies several closure properties, of the form: if so-and-so belong to the class, then such-and-such also belongs to the class (these include the "axioms", in which the premise is empty). Since the class of all (total) functions contains *all* functions, it automatically satisfies these constraints.

---
Tags: computability
---


# Question
Title: Is determining if a Turing Machine stops for at least one entry decidable?
I can't find how to prove the decibility with a reduction.

EDIT: I've tried the reduction from the halting problem and the aceptance problem. Stopping for at least one entry has infinite inputs (you have to check all possible inputs) but the halting problem only has one input for the TM.

I don't understand how can i formally define a machine that using a machine that checks all inputs solves all cases of the halting problem.

# Answer
> 0 votes
It is not *decidable*. You can prove that by reducing the Halting problem to it as follows: Given a tuple $(M,x)$ and the question whether $M$ halts on $x$, we can construct a Turing machine $M\_x$ which simply simulates $M$ on $x$ irrespective of the actual input $y$ of $M\_x$. It is clear that $M\_x$ will halt on any input *iff* $M$ halts on $x$.

# Answer
> 0 votes
I found the answer to my question in this similar problem Halting problem reducing to the blank tape halting problem You can just erase the 'for any input' problem using a Turing Machine that always erase the input and write w. This way you can make an equivalence between an instance (M, w) of the halting problem and an instance (M) of this problem.

---
Tags: turing-machines, semi-decidability
---


# Question
Title: Indexed family of all unary partial computable functions
Please help prove the following statement:

> The indexed family of all unary partial computable functions that have total computable extension is computable.

Definitions:

1. Total function - a function which is defined for all inputs of the right type, that is, for all of a domain.
2. A function $g$ is called an extension of the partial function $f$ if $\operatorname{Dom}(f) ⊆ \operatorname{Dom}(g)$ and $g(x) = f(x)$ for any $x \in \operatorname{Dom}(f)$, where $\operatorname{Dom}(f)$ is the domain of the function.
3. Let $S$ be nonempty countable set (possibly finite). Any surjective map $\nu\colon \omega \twoheadrightarrow S$ from the set $\omega$ of natural numbers onto the set $S$ is called an enumeration .
4. An indexed family of functions is called computable if it has at least one computable enumeration.

Additional information:

* The indexed family of all unary computable functions is not computable.

# Answer
Recall that a collection $\mathcal{F}$ of computable partial functions admits a computable numbering if there is a computable function $f : \mathbb{N} \to \mathbb{N}$ such that $\mathcal{F} = \\{\varphi\_{f(e)} \mid e \in \mathbb{N}\\}$, where $(\varphi\_e)\_{e \in \mathbb{N}}$ is a standard enumeration of the computable partial functions.

Let $\mathcal{I}$ be the collection of computable partial functions whose domain is either $\mathbb{N}$ or some $\\{0,\ldots,n\\}$.

**Claim**: $\mathcal{I}$ admits a computable numbering.

*Proof*: Let $\iota(n)$ denote the program:

1. Input $k \in \mathbb{N}$
2. For each $0 \leq i \< k$ simulate $\phi\_n(i)$.
3. Simulate $\varphi\_n(k)$ and output its output

Clearly, if $\varphi\_n$ is total, then $\varphi\_{\iota(n)} = \varphi\_n$. Otherwise $\varphi\_{\iota(n)}$ is defined in some initial segment of $\mathbb{N}$. Thus, $\iota$ is a computable numbering of $\mathcal{I}$.

Let $\mathcal{C}$ be the collection of partial computable functions admit a computable total continuation. It is easy to see that $\mathcal{C}$ is also the class of partial computable function admitting an extension in $\mathcal{I}$. As the domain of a partial computable function is c.e., we can then show:

**Claim**: $\mathcal{C}$ admits a computable numbering.

*Proof*: Let $\langle \ , \ \rangle$ be a standard pairing function. We define $c : \mathbb{N} \to \mathbb{N}$ by letting $c(\langle e, n \rangle)$ be the program:

1. Input $k \in \mathbb{N}$
2. Simulate $\varphi\_n(k)$
3. Simulate $\varphi\_{\iota(e)}(k)$ and output its result.

Now $c$ is a computable numbering for $\mathcal{C}$. To see this, we first note that $\varphi\_{c(\langle e,n\rangle)}$ is the restriction of $\varphi\_{\iota(e)}$ to the set $\operatorname{dom}(\varphi\_n)$. This establishes $\varphi\_{c(\langle e,n\rangle)} \in \mathcal{C}$ for any $e, n$. Conversely, assume that $f$ is a partial computable function with a total computable continuation $g$. Let $f = \varphi\_n$ and $g = \varphi\_e$. Then $f = \varphi\_{c(\langle e, n\rangle)}$, so we do get indeed each member of $\mathcal{C}$ in the range of $c$.
> 1 votes

---
Tags: computability, enumeration
---


# Question
Title: Algorithm to generate combinations of n elements from n sets of m elements
Suppose I have 3 sets of 2 elements: `[A, B], [C, D], [E, F]`, and I wanted to generate all possible combinations of 1 element from each set, such that the result of the algorithm would be:

```
[A, C, E], [A, C, F], [A, D, E], [A, D, F], [B, C, E], [B, C, F], [B, D, E], [B, D, F]

```

What algorithm can I use to generate all combinations. Keep in mind that I'm looking for an algorithm that will work on any number of sets that have any number of elements, the above is just an example. Also, remember that I'm looking for an algorithm to actually generate the combinations, not just count them.

# Answer
> 2 votes
You can use recursion.

```
def recursive_generate(S):
    IF #S = 1:
        s <-- the single set in S
        return {{item} | item \in s}
    END IF
    S' <-- {}
    s <-- some selected set from S
    FOR item in s:
        For r in recursive_generate(S\{s}):
            S' <-- S' \union (r \union {item})
        END FOR
    END FOR
    RETURN S'

```

A python implementation:

```
def rec_gen(x):
    if len(x) == 1:
          return [[item] for item in x[0]]
      appended = []
      for s_el in x[0]:
          for next_s in rec_gen(x[1:]):
              appended.append([s_el] + next_s)
      return appended

given_s =[['A', 'B'], ['C', 'D'], ['E', 'F']]
print(rec_gen(given_s))

```

# Answer
> 3 votes
If you have $n$ sets of $k$ elements, your problem is equivalent to that of generating all numbers with up to $n$ digits in base $k$ (where the $i$-th digit of a number represents the index of the element to select from the $i$-th group).

This can easily be done by starting from the number $(00\dots000)\_k$ and iteratively adding $1$. Let $d\_i$ be the $i$-th least significant digit. Start from $i=1$ and do the following: if $d\_i \< k-1$ the next number is obtained by increasing $d\_i$ by $1$. Otherwise set $d\_i =0$, increase $i$ by $1$ and repeat. When $i$ reaches $n+1$ you know that you have already generated all the numbers and you can stop.

This procedure takes $O(k^n)$ time (assuming that $k$ fits in a constant number of memory words). To see this notice that you need to update $d\_1$ every time you increment the number, $d\_2$ changes only every $k$ increments, etc. In general $d\_i$ changes every $k^{i-1}$ increments.

Since the total number of increments is $k^n$, the total number of operations is: $$ O\left(\sum\_{i=1}^n \frac{k^n}{k^{i-1}} \right) = O\left(\sum\_{i=1}^n k^{n-i+1} \right) = O\left(k \cdot \sum\_{i=0}^{n-1} k^i \right) = O\left(k \cdot \frac{k^n - 1}{k-1} \right) = O(k^n). $$

This time complexity is asymptotically optimal because $\Omega(k^n)$ is a trivial lower bound (as there are $k^n$ distinct combinations to return).

A pseudocode:

```
A = An array of n integer elements, indexed from 1;
for i=1,...,n: A[i]=0;

while true:
    //A contains a n digit number in base k. Do something with it

    i = 1;
    while i<=n and A[i]==k-1:
        A[i]=0;
        i=i+1;

    if i>n:
        return;  //We have already seen all n-digits numbers in base k
    else:
       A[i]=A[i]+1;

```

---
Tags: combinatorics
---


# Question
Title: If $L1⊆L2$, and $L1\not∈RE$, is it possible that $L2∈RE$
If $L1⊆L2$, and $L1\not∈RE$, is it possible that $L2∈RE$ ?

Also I find it hard to find languages that are not in RE at all, I've heard about Arithmetical hierarchy but we didn't really learnt it in class so I guess the solution shouldn't necessarily be correlated to Arithmetical hierarchy.

I know that the $A\_{TM}=\\{(〈M〉,w): M\ accepts\ w\\}$ where M is a Turing machine then $\overline {A\_{TM}}\notin RE$, but it doesn't seem to help.

# Answer
Yes. Actually, it is even true that for every language $L\_1$ there is a language $L\_2 \supseteq L\_1$ such that $L\_2$ is regular.

Proof: Pick $L\_2 = \Sigma^\*. \square$
> 1 votes

---
Tags: formal-languages, turing-machines, computability
---


# Question
Title: Can we use the same reduction L1 -> L2 for coL1 -> coL2
does L1 ≤ p L2 yield that coL1 ≤ p coL2 for the same reduction?

# Answer
Yes. If $f$ is a polynomial-time computable function such that $x \in L\_1 \iff f(x) \in L\_2$ then

$x \in \text{co}L\_1 \iff x \not\in L\_1 \iff f(x) \not\in L\_2 \iff f(x) \in \text{co}L\_2. $
> 0 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: proving $E_{TM}$ is undecidable using the halting language
How to prove that:

$E\_{TM} = \\{\langle M\rangle\mid M \ is\ a\ TM\ and\ L(M)=\emptyset\\}\notin R$ (is undecidable)

using the language:

$H\_{halt}=\\{(⟨M⟩,w):M\ halts\ on\ w\\}$.

I tried to prove by contradiction that assuming $E\_{TM}\in R$ I have a Turing machine which decides $E\_{TM}$ and to construct with it a turing machine which decides $H\_{halt}$ but I don't know how to do so.

# Answer
> 1 votes
Suppose that there is a Turing machine $T$ that decides $E\_{TM}$.

Given a turning machine $M$ and an input $w$ you can construct a new Turing machine $M^\*$ that decides whether $(M,w) \in H\_{halt}$. $M^\*$ operates as follows:

* It first constructs a new Turing machine $M'$ that ignores its input, simulates $M$ on input $w$ and, once the simulation is complete, accepts.
* It simulates $T$ with input $M'$ to decide whether $M' \in E\_{TM}$.
* If $M' \in E\_{TM}$ then $M'$ does not accept any input, which implies that $M$ cannot halt on input $w$. In this case $M^\*$ rejects.
* If $M' \in E\_{TM}$ then $M'$ accepts at least one input (and hence all inputs), meaning that $M$ must halt on input $w$. In this case $M^\*$ accepts.

# Answer
> 0 votes
You are right, *assuming $E\_{TM}\in R$* you *have Turing machine $T$ which decides $E\_{TM}$ and you can construct* with it a Turing machine which decides $H\_{halt}$:

If we have $T$ which decides $E\_{TM}$ and suppose we want to decide whether $M$ halts on $x$. Construct a Turing Machine $T\_{M,x}$ which irrespective of its input $y$ simulates $M$ on input $x$: if the simulation halts (and $M$ either accepts or rejects $x$), then $T\_{M,x}$ accepts its input, otherwise, it never halts.

You can convince yourself that if $M$ halts on $x$, then $L(T\_{M,x}) = \Sigma^\*$, and if it doesn't then $L(T\_{M,x}) = \phi$.

Now you can figure out why this acts as a decider for the Halting problem.

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


# Question
Title: Converting Mathematical Statements to SAT Formulas
Is it possible to write a mathematical statement (like Goldbach's conjecture, for example) as a nontrivial 3-SAT formula that is satisfiable iff that statement is true? iff it is false? iff it is independent of the axioms of ZFC? So, for any statement, you would have (at most) 3 formulas, for which only one can be satisfiable. Is there any work in this field (you can use the Pythagorean Theorem as a more simpler example)?

# Answer
If you want to know whether there exists a general method/algorithm which can convert any given mathematical statement (by which you mean statements written in logic (say first-order logic, second-order logic ... etc)) to a SAT formula which is True *iff* that statement is True, then the answer is No.

The reason being that evaluating whether an SAT formula is true or false is *decidable* (in exponential time if not faster), whereas these logics are usually *undecidable*. So, no such algorithm can exist.

Of course, there are logics which are decidable, and the statement of those logic can be converted to SAT formula (maybe trivial ones like True or False as mentioned by @D.W) by a specific algorithm. See: http://www.lsv.fr/~haase/documents/h18.pdf
> 2 votes

# Answer
It depends on the mathematical statement. If it has the form

$$\exists x\_1 \in S\_1 \cdots \exists x\_n \in S\_n . \varphi(x\_1,\dots,x\_n)$$

where $\varphi(x\_1,\dots,x\_n)$ is some condition on $x\_1,\dots,x\_n$ and $S\_1,\dots,S\_n$ are finite sets, then yes, it can be expressed as a 3CNF formula in a straightforward way.

However, statements like $\exists x \in S\_1 \forall y \in S\_2 . \varphi(x,y)$ or $\exists x\_1 \in \mathbb{R} \cdots \exists x\_n \in \mathbb{R} . \varphi(x\_1,\dots,x\_n)$ are harder.

There is a trivial sense in which the answer is yes: every mathematical statement is either true or false, so it corresponds to either the 3CNF formula $\text{True}$ (i.e., $(x\_1 \lor \neg x\_1)$) or the 3CNF formula $\text{False}$ (i.e., $(x\_1) \land (\neg x\_1)$). This reduction is nonconstructive and might not be computable, though.

You might be interested in https://en.wikipedia.org/wiki/Existential\_theory\_of\_the\_reals.

Undecidable is a property of languages, not of mathematical statements. Perhaps you mean "independent of the axioms of ZFC".
> 1 votes

---
Tags: satisfiability
---


title: binary representation of ip prefixes

text:
# Question
Title: binary representation of ip prefixes
How does an ip prefix

```
90.0.0.0/4

```

translate to

```
0101∗

```

in binary

and

```
10.0.0.0/2

```

to this:

```
00*

```

I'm trying to understand it since a while now but I am unable to derive the logic.

# Answer
> 1 votes
For a netmasked IP address xxx.xxx.xxx.xxx/N, convert each xxx octet in the address to binary. The masked address is the leftmost N bits with all other bits replaced with zeroes.

So 10.0.0.2/2 becomes 00001010 00000000 00000000 00000010 which is then masked to 00000000 00000000 00000000 00000000, because 00 are the leftmost 2 bits.

90.0.0.0/4 becomes 01011010 00000000 00000000 00000000 which is then masked to 01010000 00000000 00000000 00000000, because 0101 are the leftmost 4 bits.

---
Tags: computer-networks, binary, network-topology, tcp, ip
---


# Question
Title: What is the big-$O$ notation of a summation of a log?
For: $$\sum^{n+m}\_{i=n} \log(i)$$ I'm wondering what the big O notation is and how to prove it... I believe that we can also write this as $$\log(n) + \log(n+1) + \log(n + 2) + \ldots + \log(n+m)$$

also $$\log(n+m)!/\log(n-1)!$$

Thanks

# Answer
> 3 votes
Recall that the sum of $\log$'s is equivalent to the $\log$ of products.

That is:

$$\log(xy) = \log x + \log y$$

Thus we can change your function:

$$ \begin{align} \sum\_{i=n}^{n+m} \log i &= \log \prod\_{i = n}^{n + m} i\\ &= \log (n \cdot (n+1) \cdot (n+2) \cdot \ldots \cdot (m-1) \cdot m )\\ &= \log (m!\ /\ (n-1)! )\\ \end{align} $$

Then we can similarly use the division rule to get these back out:

$$ \log (m!\ /\ (n-1)! ) = \log (m!) - \log((n-1)!) $$

Then using Stirling's Approximation we can immediately see:

$$ \log (m!) - \log((n-1)!) = O(m \log m) $$

You might be able to do better though by taking more precise bounds to get:

$$ \begin{align} \log (m!) - \log((n-1)!) &\leq em^{m + \frac{1}{2}}e^{-m} - \sqrt{2\pi}(n-1)^{n- \frac{1}{2}}e^{1-n}\\ &= \vdots \end{align} $$

# Answer
> 2 votes
O((m +1) log(n+m)). It’s obviously an upper bound. But also most values have a logarithm close to the maximum, so it’s also a good lower bound.

In your particularly simple case, the Stirling formula will give you a better result, but you asked for big-O only.

---
Tags: big-o-notation
---


# Question
Title: Two-way finite automaton: How does the automaton remember the state
I have been going through a theory of Two-way finite automatons and I did not understand the given example when there were a **DFA A = (Q, Σ, δ, q1, F)**. the **2-DFA B = (Q ∪ Q| ∪ Q|| ∪ {q0, qN, qF}, Σ ∪ {#}, δ|, q0, {qF})** and a following language
**L = { #u# | uu ∈ L(A)}**.
In following paragraph I will describe how would it works, if we are reading a word that belongs to the language.
In the first procedure automaton B follows the states of automaton A, when it reach right '#', it stops, **remember** the accepting state and starts to move back through the copied states of automaton A: Q| as long as it come to right '#'. Afterwards it starts moving on through the copied states Q|| of automaton A, and once it reaches out the right '#' checks if it is the saved accepting state. Image below shows the movements where qN is a failing/non-accepting state and +1 movement of head to right and -1 movement of the head to left.

## Question

How does the 2-DFA remember that it reached out during first walk through the states of automaton A the accepting state for the second walk?

# Answer
> 1 votes
Here is a simpler example, for NFAs.

We will show that if $L\_1,L\_2$ are regular languages over disjoint alphabets $\Sigma\_1,\Sigma\_2$, then so is the following language over $\Sigma = \Sigma\_1 \cup \Sigma\_2$: $$ L = \\{ xyz : x,z \in \Sigma\_1^\*, y \in \Sigma\_2^\*, xz \in L\_1, y \in L\_2 \\}. $$ Here is the idea. Start with DFAs $A\_1,A\_2$ for $L\_1,L\_2$. We will construct a DFA for $L$ which acts as follows. It starts by simulating $A\_1$. When it encounters a symbol from $\Sigma\_2$, it *remembers* the state that $A\_1$ is in, and switches to $A\_2$. When it encounters a symbol from $\Sigma\_1$, it switches back to $A\_1$, assuming that $A\_2$ is at an accepting state. It goes to a failure state if it encounters a letter from $\Sigma\_2$ again.

Here are the details, showing how we implement remembering the state of $A\_1$.

Let $A\_1 = \langle Q\_1,\Sigma\_1,q\_{01},\delta\_1,F\_1 \rangle$ and let $A\_2 = \langle Q\_2,\Sigma\_2,q\_{02},\delta\_2,F\_2 \rangle$. We construct a new DFA $A = \langle Q,\Sigma,q\_0,\delta,F \rangle$ as follows:

* The set of states is $Q = (Q\_1 \times \\{1\\}) \cup (Q\_1 \times Q\_2) \cup (Q\_1 \times \\{2\\}) \cup \\{q\_f\\}$. States in the first part will be used to simulate $A\_1$ before a symbol from $\Sigma\_2$ is ever encountered. States in the second part will be used to simulate $A\_2$ while *remembering* the state of $A\_1$. States in the third part will be used to simulate $A\_1$ after reading the $y$ part. The final state will handle various modes of failure.
* The initial state is $(q\_{01},1)$.
* The transition function is defined as follows:

+ If $\sigma \in \Sigma\_1$ then $\delta((q,1),\sigma) = (\delta\_1(q,\sigma),1)$: we just advance $A\_1$.
    + If $\sigma \in \Sigma\_2$ then $\delta((q,1),\sigma) = (q,\delta\_2(q\_{02},\sigma))$: we *remember* the state of $A\_1$, and advance $A\_2$.
    + If $\sigma \in \Sigma\_2$ then $\delta((q\_1,q\_2),\sigma) = (q\_1,\delta\_2(q\_2,\sigma))$: we advance $A\_2$, while keeping the state of $A\_1$ intact.
    + If $\sigma \in \Sigma\_1$ and $q\_2 \notin F\_2$ then $\delta((q\_1,q\_2),\sigma) = q\_f$: the $y$ part is not in $L\_2$, so we signal failure.
    + If $\sigma \in \Sigma\_1$ and $q\_2 \in F\_2$ then $\delta((q\_1,q\_2),\sigma) = (\delta\_1(q\_1,\sigma),2)$: we go back to simulating $A\_1$.
    + If $\sigma \in \Sigma\_1$ then $\delta((q\_1,2),\sigma) = (\delta\_1(q\_1,\sigma),2)$: we just advance $A\_1$.
    + If $\sigma \in \Sigma\_2$ then $\delta((q\_1,2),\sigma) = q\_f$: the input is malformed, so we signal failure.
    + For all $\sigma$, $\delta(q\_f,\sigma) = q\_f$.
* The final states are $(F\_1 \times \\{1\\}) \cup (F\_1 \times F\_2) \cup (F\_1 \times \\{2\\})$. The first part handles the case $y=z=\epsilon$, the second handles the case $y\neq\epsilon$ and $z=\epsilon$, the third handles the case $y,z \neq \epsilon$.

Hopefully this explains how a DFA can commit a piece of information to memory. Since a DFA has only finitely many states, it can only store a constant amount of information.

---
Tags: automata, regular-languages, finite-automata, chomsky-hierarchy
---


# Question
Title: What is the 2's complement answer of 16.5?
According to this post it is saying Two's complement is only for integers, but in Wolframalpha is is saying the Two's complement of 16.5 is 0010000.1, how?

# Answer
It seems that WolframAlpha is using fixed-point representation. In effect, it is doubling your number and then representing it as two's-complement.

In more detail, WolframAlpha is guessing that you are interested in fixed-point representations of the form $$ xxxxxxx.x $$ in binary, that is, 8 bits in total, with the "decimal" point at the fixed position between the 7th and 8th bits. Using two's complement, you can represent all numbers from $-64$ (represented as $1000000.0$) to $+63.5$ (represented as $0111111.1$).
> 1 votes

---
Tags: floating-point, number-formats
---


title: Best case for sorting algorithm

text:
# Question
Title: Best case for sorting algorithm
Given this sorting algorithm:

```
Sort(A, n):
    if (n == 1)
     return
    isSorted = true
    for i=1 to n-1 do:
        if (A[i] > A[i+1]):
            isSorted = false
            temp = A[i]
            A[i] = A[i+1]
            A[i+1] = temp
    end for
    if (isSorted)
         return
    else
         Sort(A, n-1)

```

I'm required to find the upper bound for the best case. My question is - is the best case considered when the array length is 1? Or when the array is already sorted and then the loop runs only once? Or both cases?

Also, I need to find a recursive formula for the worst case. I got to this formula:

if n $\neq1$
$F(n) = F(n-1) + n - 1$
else
F(n) = 1

Is it correct?

# Answer
> 1 votes
We usually measure the running time of algorithm as a function of the length of the input.

For example, when we say that an algorithm runs in time $O(n\log n)$, what we mean is:

* For every input of length $n$, the algorithm runs in time $O(n\log n)$.

This is an example of worst-case complexity. In your case, you are looking for a function $T(n)$ which satisfies the following:

* For every input of length $n$, the algorithm runs in time *at least* $T(n)$.
* Furthermore, for each $n$ there exists an input of length $n$ on which the algorithm runs in time $T(n)$.

To answer your particular questions: the answer should be a function of $n$; and we are looking for the "best-case scenario" of the algorithm for each input length $n$. Whether this best-case scenario is the one you said or not, depends on the algorithm. There might be algorithms for which your best-case scenario is actually a worst-case input (we can construct such algorithms artificially).

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


# Question
Title: Understanding lexical grammar for multi-line comments in JavaCC
I'm struggling to understand why this piece of lexical grammar works for multi-line comments in JavaCC (posted here):

```
 "/*" (~["*"])* "*" (~["*","/"] (~["*"])* "*" | "*")* "/"

```

As I read it, the parser scans the input /\*, and then zero or more optional occurrences of * can appear, followed by a \*, and then zero or more optional occurrences of * and /, then zero or more occurrences of * followed by * or \*, ended by a /. Specifically, this part boggles my mind:

```
 (~["*","/"] (~["*"])* "*" | "*")*

```

I'd appreciate some help understanding this.

# Answer
Let's write this in a more manageable way. I'll use $x$ for any symbol other than $/$ and $\*$. Your expression is $$ /\* (/+x)^\* * (x(/+x)^\** + \*)^\* / $$ Now let us apply the following identity to the part "$\*(x(/+x)^\**+\*)^\*$": $$ r(sr)^\* = (rs)^\*r $$ We get $$ /\* (/+x)^\* (\*x(/+x)^\*+\*)^\* \*/ $$ It's clear what the outer parts $/\*$ and $\*/$ do, so let's focus on the inner part $$ (/+x)^\* (\*x(/+x)^\*+\*)^\* $$ which captures all strings not containing the substring $\*/$. Using the identity $$ (rs+r)^\* = (r^+s)^\* $$ we can simply it to $$ (/+x)^\* (\*^+x(/+x)^\*)^\* $$ Essentially, each run of stars is "guarded" by a following $x$.
> 1 votes

---
Tags: lexical-analysis
---


title: Big O Notation of $n^{0.999999}\log(n)$

text:
# Question
Title: Big O Notation of $n^{0.999999}\log(n)$
I'm taking the MIT Open Courseware for Introduction to Algorithms and I'm having trouble understanding the first homework problem/solution.

We are supposed to compare the asymptotic complexity (big-O) for different functions:

$f\_1(n) = n^{0.999999}\log(n)$
$f\_2(n) = 10000000n$

$f\_2(n)$ is obviously O(n), but the big-O given for $f\_1(n)$ confuses me and I don't follow the given solution.

The solution says $f\_1(n)$ has less Big-O complexity than $f\_2(n)$:

"recall that for any $c \> 0$, $log(n)$ is $O(n^c)$.

Therefore we have: $f(n) = n^{0.999999}log(n) = O(n^{0.999999}n^{0.000001}) = O(n) = O(f\_2(n))$"

I do not understand the logic underlying the solution. I may be forgetting something simple? Can someone break it down for me? Thanks!

# Answer
> 7 votes
If $g = O(g')$ and $h$ is nonnegative then $h \cdot g = O(h \cdot g')$ — in English, if $g$ grows slower than $g'$ then multiplying by a positive function doesn't affect that fact. (If you aren't sure about this, do the proof with quantifiers).

Since $\log(n) = O(n^{0.000001})$, $n^{0.999999} \cdot \log(n) = O(n^{0.999999} \cdot n^{0.000001})$. Since $n^{0.999999} \cdot n^{0.000001} = n$, we have $f\_1(n) = O(n)$.

While it is true that $f\_2(n) = O(n)$, this is not relevant here. What you need is $n = O(f\_2(n))$, which is also true.

Intuitively, a higher exponent trumps a logarithm. A multiplicative constant is not significant.

# Answer
> 0 votes
If we consider really large numbers like $10^{1000}$ then $n\log n$ will be equal to

$$n\log 10^{1000} = 1000n\log 10 = 2302n \< 1000000n.$$

Thus even for really really big $n$s, $n\log n\<1000000n$.

This I guess is a layman logic, and theoretically, infinite $n$ should give $n\log n\>10000000n$. But not really.

# Answer
> 0 votes
Just use the definition, i.e., check if $\lim\_{n \to \infty} f\_1(n) / f\_2(n) \< \infty$. Computing this, you'll see that $0 \< \infty$ and you are done.

---
Tags: algorithms, asymptotics
---


# Question
Title: All problems about Turing machines that involve only the language that the TM accepts are undecidable
I came across the below statement in the classic text "Introduction to Automata Theory, Languages, and Computation" by Hopcroft, Ullman, Motwani.

`All problems about Turing machines that involve only the language that the TM accepts are undecidable`

They say that the above theorem is per Rice theorem which states that:

*"Every nontrivial property of the RE languages is undecidable."*

How are these two statements equivalent? The former deals only *problems* while the later deals with *non trivial property*.

# Answer
> 1 votes
There are a few keywords in the excerpt from the said text book - *non-trivial, problem, property*.

Now what is a problem, assuming we are not dealing with combinatorial optimization problems,i.e. we are dealing with only questions which have an YES or NO answer to them. When you ask a YES or NO question to an input string if the answer is YES you place it in a set $L$ and if the answer is NO you just discard it. Now this set $L$ is the language or the problem. It contains all those strings which which satisfy our YES or NO question.

> All non-trival *problems* about *Turing machines* that involve *only the language that the TM accepts* are undecidable

Here the author is talking about YES or NO questions (with respect to Turing machines) only involing the *language that the Turing machine accepts*,i.e. the Recursively Enumerable language(RE), which means that our "problem" set shall contain only RE languages. Now a trivial problem is one in which the our YES or NO question is either satisfied by all input or satisfied by none of the input. So a non-trivial problem is one which is neither empty nor it has all possible inputs.

> Rice Theorem: "Every nontrivial property of the RE languages is undecidable."

Property of RE languages is a set of RE languages having the said property.

Non-trivial property: The property is either satisfied by all concerned languages or by none.

So "nontrivial property of the RE languages" becomes the set of RE languages and it is neither empty nor it has all possible RE languages.

By the above argument we can say that the two statements are equivalent.

(In fact property and problem are the same thing, they both are set of strings after all. Now we might think that property is a set of languages, although while it is true, it is inconvenient to represent languages in a set(as languages can be infinitely long), rather what is done is instead of the language , we represent the corresponding Turing Machine with a suitable encoding)

---
Tags: turing-machines, rice-theorem
---


# Question
Title: what is CFG of $\{a^i b^j c^k \mid k = |i-j| \}$
what steps should I take to find out what is the *context free grammar* of

$L(w) = \\{a^i b^j c^k \mid k = |i-j| \\}$

# Answer
> 0 votes
Use the fact that CF are closed under union, and start by considering cases, whether $i\ge j$ or $j\ge i$.

In the first case we get the language $L\_1 = \\{ a^i b^j c^k \mid k+j=i\\}$, which is the same as $L\_1 = \\{ a^{k+j} b^j c^k \mid k,j \ge 0\\}$.

Make a grammar for $L\_1$, and then consider the second case.

---
Tags: context-free
---


# Question
Title: Time complexity analysis of 2 arbitrary algorithms - prove or disprove
We are given 2 algorithms A and B such that for each input size, algorithm A performs half the number of steps algorithm B performs on the same input size.

We denote the worst time complexity of each one by $g\_A(n),g\_B(n)$

Also, we know there's a positive function $f(n)$ such that $g\_A(n)\in\Omega(f(n))$

Is it possible that $g\_B(n)\in\Omega(f(n))$? Is it necessary?

It seems naive to think that it's necessary, but I can't figure out to contradict it.

# Answer
It is possible. Example $g\_A(n)=1$, $g\_B(n)=2$, and $f(n)=1$.

It is also necessary, since $g\_B(n) = 2 g\_A(n) \in\Omega(f(n))$.

To see that $ 2 g\_A(n) \in\Omega(f(n))$ you can use the definition of $\Omega(\cdot)$.

From $g\_A(n) = \Omega(f(n))$ you know that here is some $n\_0$ and some $c\>0$ such that, $\forall n \ge n\_0$, $g\_A(n) \ge c f(n)$. This implies that, for the same value of $n\_0$ and $c$, $2 g\_A(n) \ge 2 c f(n) \ge c f(n)$, i.e., $ 2 g\_A(n) \in\Omega(f(n))$.
> 1 votes

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


title: Proper network address

text:
# Question
Title: Proper network address
Which of the following are proper network (not host) addresses?

1. 192.168.23.0/24
2. 193.205.16.132/26
3. 172.16.4.0/20
4. 10.57.13.64/28

How can I tell? What is a **proper** network address?

Is a proper network address when the IP address is the same as the network address? For example in the first one that is the case.

# Answer
> 0 votes
I think proper here just means that the IP address in CIDR notation is the first address in the range specified by the IP address and its prefix.

This is the case for 192.168.23.0/24 and 10.57.13.64/28 and not the case for 193.205.16.132/26 (whose first address in the network range is 193.205.16.128) and 172.16.4.0/20 (whose first address is 172.16.0.0).

---
Tags: computer-networks
---


# Question
Title: Context free grammar for $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$
I try to find a context free grammar for the language $L = \\{u\\#v \mid u,v \in \\{a,b\\}^\* , \vert u \vert\_a \neq \vert v \vert\_a \text{ or } \vert u \vert\_b \neq \vert v \vert\_b\\}$. There is a hint in the task that one should first construct the context free grammar for cases such as $L\_1 = \\{u\\#v \mid u,v \in \\{a,b\\}^\* , \vert u \vert\_a \> \vert v \vert\_a\\}$ and later combine all of these.

I would appreciate a hint to come up with $L\_1$. I do not know how construct $u\\#v$ such that $u$ and $v$ are free independent from each other except of the fact that $u$ has more $a$'s than $v$. I tried to build my language around the $\\#$ and also tried to move the $\\#$ in the direction of the most appearing $a$'s but none of my attempts worked.

What is the proper way to tackle such constructions in general?

# Answer
I'll just show how to build a grammar for $L\_1 = \\{ u\\#v, |u|\_a \> |v|\_a \\}$. Then it'll be straightforward to combine 4 similar grammars into a grammar for $L$.

The idea is to write $u\\#v$ as $xay\\#v$ with $x,y,v \in \\{a,b\\}^\*$ and $|y|\_a = |v|\_a$. The construction of $y\\#v$ is handled by the non-terminal $Z$ which "grows" it from the center.

$$ \begin{align\*} S &\to aS \mid bS \mid aZ \\ Z &\to bZ \mid Zb \mid aZa | \\,\\# \end{align\*} $$
> 2 votes

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


# Question
Title: Is it possible to design a Turing Machine without extra symbols for this language?
Is it possible to design a Turing Machine for the language defined as L = {0n1n | n \>= 0} with only the symbols in the set of {blank, 0, 1}?

# Answer
Yes, listing out all the transitions would be tedious so I'll just give you the high level algorithm (the idea is to iteratively match the first 0 with the last 1, while deleting both of them). Starting from the first symbol on the tape do the following:

* If the current symbol is $\varepsilon$: accept
* If the current symbol is $1$: reject
* Delete the current symbol (by writing $\varepsilon$)
* Move right until you find the next $\varepsilon$ symbol
* Move left (the head is now on the last non-blank symbol, if any)
* If the current symbol is $\varepsilon$: reject
* If the current symbol is $0$: reject
* Delete the current symbol (by writing $\varepsilon$)
* Move left until you find the previous $\varepsilon$ symbol
* Move right (the head is now on the first non-blank symbol, if any)
* Repeat
> 1 votes

# Answer
Sure, the idea is basically that you're going to turn the first 0 into blank, and then go search for the last 1 and turn it in into blank, then go back to the beginning and proceed recursively in the same fashion.

Here's an implementation on the online turing machine simulator
> 1 votes

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


# Question
Title: What is an example of a Monte-Carlo algorithm for finding a Hamiltonian path?
I've recently been made aware that there exist Monte-Carlo algorithm(s?) for determining whether a Hamiltonian path exists in a graph. I am struggling to figure out how it would work. What is the random element?

# Answer
> 3 votes
There are several such algorithms for various graph problems; for Hamiltonian path one example is due to Björklund \[1\]. These algorithms are often algebraic and the "random element" stems from the application of the Schwartz–Zippel lemma. Usually, the algorithms work so that the graph property we are interested in is somehow represented as a (multivariate) polynomial with the property that that a solution exists precisely when the polynomial is not identically zero.

---

\[1\] Björklund, Andreas. "Determinant sums for undirected hamiltonicity." SIAM Journal on Computing 43.1 (2014): 280-299.

---
Tags: probabilistic-algorithms, hamiltonian-path, monte-carlo
---