# Question
Title: Finding solution to Mv=v over $\mathbb{Z}$={0,1} for matrix M given a set linearly independent v
Under mod 2 arithmetic ($\mathbb{Z}$={0,1}), given a set $V$ of $n$x$1$ linearly independent vectors $\\{x\_1,...,x\_n\\}$ I'd like to find a $n^2$ binary matrix $M$ such that $Mv=v$ where $v \in V$ and $M\bar{v}\neq \bar{v}$ for $\bar{v}\not \in V$.

I supposed it would also be helpful to know the technical term for a matrix that acts as an identity exclusively for given set of vectors when multiplied by any member of that set.

# Answer
It is not possible. Such matrices don't exist. We always have $Mv=v$ whenever $v=0$ (the all-zeros vector). No set that contains the all-zeros vector is linearly independent, so surely $0 \notin V$. Therefore, no matter what $M$ you choose, when we set $v=0$, we discover $Mv=v$ for some $v \notin V$, which violates your requirements. In other words, no matrix $M$ can satisfy the requirements.

Another proof of impossibility: suppose $u,v \in V$; if $Mu=u$ and $Mv=v$, then by linearity $M(u+v)=(u+v)$, but by linear independence, $u+v \notin V$.

Or, to put it another way, the kernel of a matrix/linear map is always a linear subspace.
> 1 votes

---
Tags: arithmetic, linear-algebra, modular-arithmetic
---


# Question
Title: How to construct complement of NFA universality?
Given an input NFA, can one construct an NFA that is universal (that is, accepts all its inputs) if and only if, the input NFA isn't universal?

I tried to use the fact that NFA-universality is PSPACE-complete, and the fact that PSPACE = coPSPACE. I am also interested in the details of a simple construction.

# Answer
> 2 votes
Consider the language $ALL\_{NFA} = \\{\langle A\rangle: \text{$A$ is an NFA with $L(A) = \Sigma^\*$}\\}$.

If you want a non-PTIME reduction from $\overline{ALL\_{NFA}}$ to $ALL\_{NFA}$, then you can simply do the following naive approach. On input $\langle A\rangle$ for the reduction, the reduction checks whether $L(A) \neq \Sigma^\*$, and outputs an NFA $B$ that accepts all its inputs only when $L(A)\neq \Sigma^\*$. Clearly, this works but comes at a high cost: we are deciding $\overline{ALL\_{NFA}}$ to output the NFA $B$ accordingly. As the non-universality check can be performed in PSPACE, the latter reduction is a PSPACE reduction. More abstractly, if you don't care about the complexity of the reduction, you can use the fact that every non-trivial language is $R$-hard (see my answer here).

I am not aware of a simple PTIME reduction from $\overline{ALL\_{NFA}}$ to $ALL\_{NFA}$. There is ofcourse a PTIME reduction that goes through Savitch's theorem which states that for any function $f\in \Omega(log n)$, it holds that $NPSPACE\[f(n)\]\subseteq SPACE\[f^2(n)\]$. Indeed, it is well-known that the latter theorem implies that PSPACE = NPSPACE, and since PSAPCE = coPSPACE, we get in total that NPSPACE = coNPSPACE. The latter allows us to show that $ALL\_{NFA}$ is PSPACE-complete -- membership in PSPACE follows from Savitch's theorem and the fact that $\overline{ALL\_{NFA}}\in \text{PSPACE}$, see for example here. Then, PSPACE-hardness is well-known and can be shown directly, see for example here. Putting everything together, we get the exsitence of a PTIME reduction from $\overline{ALL\_{NFA}}$ to $ALL\_{NFA}$. Is there a simpler direct redcution? Who knows, maybe (and I would like to see one), but I suspect that the output NFA of that reduction needs to be at least of quadratic size, but I am not sure. I tried to use Savitch's theorem to show the latter, but then noted that Savitch's theorem has no known tight lower bound -- see here.

---
Tags: complexity-theory, finite-automata, space-complexity, nondeterminism, polynomial-time-reductions
---


# Question
Title: Does there exist terminology to discern NFA states and NFA-transformed-into-DFA state?
I can't find this from surface search in the literature

When one observes/simulates NFA after processing several characters, one has to consider both "internal states of NFA" (individual nodes) and "state of the whole NFA" - which nodes are active - that can be seen as state of DFA that that automata is equivalent to.

**Is there an already existing different terminology for at least one of these?** so that I can stop confusingly referring to both as "NFA state"/"state of NFA"

# Answer
For the first term we simply use the word "state". For the second term, using "state of the NFA" is confusing because we read it as "one of the NFA's states". If you are not sure which terminology to follow, then you can state explicitly what you mean, or define a term clearly before using it.

So for an NFA $A = \langle \Sigma, Q, Q\_0, \delta, F \rangle$, a subset $S\subseteq Q$ of states, and a finite word $u\in \Sigma^\*$, you can:

* **Write it explicitly:** $T$ is the set of states that $A$ can reach upon reading $u$ from some state in $S$.
* **Extend $\delta$ to set of states and words, and then use it** (quoting from what we usually write in papers):

> we sometimes extend $\delta$ to sets of states and finite words.
> Then, $\delta: 2^Q\times \Sigma^\* \to 2^Q$ is such that for every $S \in 2^Q$, finite word $u\in \Sigma^\*$, and letter $\sigma\in \Sigma$, we have that $\delta(S, \epsilon) = S$, $\delta(S, \sigma) = \bigcup\limits\_{s\in S}\delta(s, \sigma)$, and $\delta(S, u \cdot \sigma) = \delta(\delta(S, u), \sigma)$. Thus, $\delta(S, u)$ is the set of states that $A$ may reach when it reads $u$ from some state in $S$.

and from this point, you can write $T = \delta(S, u)$. In fact, in the literature, the term $\delta(S, u)$ is usually used, and it is not hard to guess what it means. So the answer to your question is yes, the terminology exists.
> 1 votes

# Answer
I will share a pedantic answer:

The first concept is called simply "state".

Strictly speaking, the second concept does not exist, and reflects a misunderstanding of NFAs. NFAs are nondeterministic. This means that, at each step of execution, the NFA chooses one state to transition to (not a set of states; one state). The choice is nondeterministic, so you can think of it as magically making a "lucky choice" if any exists.

Now, we know that nondeterministic execution is equivalent to cloning many copies of the NFA, where each copy follows a different execution trace; and thanks to the subset construction, this is in turn equivalent to some DFA where each state of the DFA corresponds to a set of states of the NFA. That is where the set of states comes from.

Therefore, if you needed to discuss both concepts, one possibility would be to refer to a "NFA-state" or "state of the NFA", vs a "DFA-state" or "state of the DFA obtained by the subset construction".

Ultimately, you can use any terminology you want, so long as it is understandable by the reader. You might want to explain your terms before first use.
> 0 votes

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


# Question
Title: Asking server for range of documents -- how to ask as few times as possible based on what is already in memory?
I have a server. It has e.g. one million documents. My website has a spreadsheet. Each page has space enough for e.g. 50 rows. As I scroll down, I will want to request the rows from the server, and I will cache the range I asked for in memory.

However, if I scroll up again (or place the scrollbar arbitrarily), I only want to ask for the subset of documents that I have not yet cached. Thus, I will possibly ask the server several times for different smaller ranges until I have been able to complete my target range.

This must be a well-known fragmentation problem, but I don't know.

Which data structures and algorithms is the best to use in this case?

# Answer
There are things unclear in your question, but lets assume some things first.

If you want to deploy a caching mechanism you need consider the size of the cache and in what size chunks you want to cache the data.

Secondly, you need to understand the temporal and spatial locality of your data. For example, if you have a database which has a primary key and the results are sorted by the same in your website, you could prefetch some extra data along with the request to minimize the calls to your server. However if it is non-indexed data, something like hashes, then it would depend on the request, if the user scrolls down /up you may have cache hits and if its a random request you may not.

Thirdly, based on what you asked it seems like a case of the optimal page replacement algorithm(feel free to correct me), which is non implementable. You can never predict what data is going to be requested, which is why we have the locality of reference to help reach near optimality in most cases. You will have to decide cache eviction/cache replacement policy(Why is this needed? If we assume what you want is possible then eventually your whole database is going to be stored on the cache, then why would you store it on the server in the first place?). Stack based algorithms are generally used like LRU, LFU and its variations. At some point your cache will fill up and you will need to decide which existing cached data to remove.

You only need to worry about all these if you yourself are going to implement a caching mechanism. For data structures you can use anything from a simple array to a self balancing tree to a hashtable. Since caching is all about reducing the retrieval time, you need to understand that only the complexity of operations on data structures don't matter. Sometimes an operation might have a higher growth rate but may be faster at runtime.

Look up how in memory databases work, for example Redis.
> 0 votes

# Answer
To get the best performance you need to measure: What is the time for one request requesting n rows? Quite often there is a fixed time per request, plus a much smaller time for any item of data.

With that information you can for example request the data you need plus some extra data if you expect the user might scroll the screen, as long as it doesn’t add too much to the time taken. And when the user starts scrolling the screen you can anticipate this and load the next bit of data.
> 0 votes

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


# Question
Title: Help with understanding Check Digit Validations
I'm not sure if I'm posting in the correct section, but I wanted to learn about CDVs, how the weightings work, and the computation.

I'm reviewing how a system is configured and looking to add a new range of numbers, but it fails validation, someone mentioned that it's probably linked to the weightings.

The CDV is using the Modulus 11 computation.

Thanks in advance.

# Answer
> 0 votes
There are many possible algorithms for checksums and "check digits". We can't answer those questions without knowing which one is being used in your setting.

I suggest doing some more background reading on the subject. See, https://en.wikipedia.org/wiki/Check\_digit, https://en.wikipedia.org/wiki/Checksum, https://en.wikipedia.org/wiki/Luhn\_algorithm, https://en.wikipedia.org/wiki/Damm\_algorithm, https://en.wikipedia.org/wiki/Verhoeff\_algorithm.

---
Tags: algorithms
---


# Question
Title: Optimal upper bound on the number of states in the complement of an NFA
I have my own version of `lex` and I would like to add the complement operation. Derived from that I can then add the intersection and difference also. My version also supports the generation of NFAs (Non-deterministic Finite Automaton) and of course I try to keep the automatons as small as possible.

My question thus is: what is the most optimal known upper bound on the number of states in the NFA that accepts the complement of another NFA? Of course going through the conversion to a DFA (Deterministic Finite Automaton) and then interchanging accepting and rejecting states, gives an exponential upper bound. Are there any better known upper bounds? Preferably polynomial or even linear of course.

If no better upper bound is known, has it been shown that for some family of languages the lower bound is exponential or otherwise super polynomial?

# Answer
> 6 votes
In the paper *State Complexity of Concatenation and Complementation of Regular Languages* by Jirásek, Jirásková, and Szabari (LNCS Volume 3317, 2005, doi 10.1007/978-3-540-30500-2\_17) very precise bounds for complexities for complement on non-deterministic automata are obtained. We do not need full details, but the authors cite an earlier report by one of them, stating:

**Theorem 2.** For any positive integer $n$, there exists a binary NFA $M$ of $n$ states such that any NFA for the complement of the language $L(M)$ needs at least $2^n$ states.

So it seems there is no better bound for complementation than via deterministic automata. At least in general.

# Answer
> 2 votes
One of the classical ideas in automata theory is showing that going from an NFA to a complementing one involves an exponential blow-up. Here is one way to do it:

Consider the alphabet $\Sigma = \\{ 0, 1\\}$, and for every $n\geq 1$, consider the language $$L\_n = \\{ w\in \Sigma^\*: w \text{ has an infix }u \in 0 \cdot (0\cup 1)^{n-1} \cdot 1 \cup 1 \cdot (0\cup 1)^{n-1} \cdot 0\\}$$

Thus, $L\_n$ consists of all words $w$ that contain two letters that are $n$-distant apart and are different. Clearly, $L\_n$ can be recognized by an NFA $A\_n$ of size $\theta(n)$ as follows. $A\_n$ guesses when an infix $u$ in $0 \cdot (0\cup 1)^{n-1} \cdot 1 \cup 1 \cdot (0\cup 1)^{n-1} \cdot 0$ starts. Then, it remembers the first letter of $u$, and finally checks whether the $n$'th letter after is different than the one we remembered.

Now consider the complement language $\overline{L\_n}$. It is not hard to see that $\overline{L\_n} \cap \Sigma^{2n} = \\{ u\cdot u: u\in \Sigma^n \\}$. We show next that every NFA $B\_n$ that recognizes $\overline{L\_n}$ has at least $2^n$ states (intuitively this is true as $B\_n$ has to remember the last $n$ letters read):

Assume towards contradiction that $B\_n$ is an NFA that has strictly less than $2^n$ states and recognizes $\overline{L\_n}$. Then, consider the words $x\_1 = u\_1\cdot u\_1,x\_2 = u\_2\cdot u\_2, \ldots, x\_{2^n} = u\_{2^n} \cdot u\_{2^n}$, where $u\_1, u\_2, \ldots, u\_{2^n} \in \Sigma^n$ are all words of length $n$ over $\Sigma = \\{ 0, 1\\}$. As for all $i\in \[2^n\]$, $x\_i$ is accepted by $B\_n$, and $|B\_n| \< 2^n$, it follows that there are $i\neq j \in \[2^n\]$ and two accepting runs in $B\_n$ on $x\_i$ and $x\_j$, where both runs pass through the same state after reading the first $n$ letters. So we have two runs $r\_i$ and $r\_j$ of the form:

$$ r\_i = q^i\_0 \xrightarrow{u\_i} q \xrightarrow{u\_i} q^f\_i$$ $$ r\_j = q^j\_0 \xrightarrow{u\_j} q \xrightarrow{u\_j} q^f\_j$$

where $q^i\_0$ and $q^j\_0$ are intial states of $B\_n$, and $q^f\_i$ and $q^f\_j$ are accepting states of $B\_n$. Now one can take the runs $r\_i$ and $r\_j$ and obtain the following accepting run in $B\_n $ from them:

$$ q^i\_0 \xrightarrow{u\_i} q \xrightarrow{u\_j} q^f\_j$$

So on the one hand, $u\_i\cdot u\_j \in L(B\_n) = \overline{L\_n}$, and on the other hand, as $u\_i\neq u\_j$, it follows that $u\_i\cdot u\_j$ has two letters that are $n$-distant apart and are different, and thus $u\_i\cdot u\_j \in L\_n$ and we've reached a contradiction.

---
Tags: finite-automata, nondeterminism, lower-bounds
---


# Question
Title: Reduction from dominating set to disconnected dominating set
Consider an undirected graph $G = \langle V, E\rangle$, and a set $S\subseteq V$ of vertices. We say that $S$ is a *dominating set*, if for every vertex $v\in V$, it holds that $v\in S$, or $v$ has a neighbor in $S$. We say that $S\subseteq V$ is a *disconnected dominating set* if it is a dominating set and the subgraph of $G$ induces by $S$ is not strongly connected (that is, has at least two strongly connected components).

In the dominating set problem, we are given an undirected graph $G$ and an integer $k$, and we need to decide whether $G$ has a dominating set of size at most $k$.

In the disconnected dominating set problem, we are given an undirected graph $G$ and an integer $k$, and we need to decide whether $G$ has a disconnected dominating set of size at most $k$.

Can we show that the disconnected dominated set problem is NP-hard by a suggesting a PTIME reduction from the dominating set problem?

I was suggested and thought about duplicating the input graph $G$.

# Answer
> 3 votes
Consider an undirected graph $G = \langle V, E\rangle$, and consider a dominating set $S\subseteq V$ in $G$. If you mean by "$S$ is disconnected" that the subgraph induced by $S$ is not strongly connected, then the following is a trivial reduction from dominating set:

On input $\langle G, k\rangle$, the reduction outputs $ \langle G', k+1\rangle$, where $G'$ is obtained from $G$ by adding a new isolated vertex (a vertex that does not touch any edge).

Correctness follows from the fact that a dominating set must contain all isolated vertices, and I leave the details to you.

---
Tags: graphs, np-complete, reductions, np-hard, polynomial-time-reductions
---


title: Maximum sum staircase complexity

text:
# Question
Title: Maximum sum staircase complexity
Given an $n \times n$ matrix of integers, I would like to find the optimal dividing line that maximizes the sum of the integers on the same side as the top left corner. The dividing line should be connected and made up of only vertical and horizontal parts. For example:

The complication is that the number of horizontal parts is restricted to be at most $k$, for some integer parameter $k$. In the picture above there are 4 horizontal parts. The line can start at any point on an edge and end at any point at a different edge.

Without this restriction I believe one can find the optimal partition using dynamic programming in $O(n^2)$ time. How quickly can my version be solved?

# Answer
It can be solved in $O(n^2 k)$ time using dynamic programming. Let $A\[1..n,1..n\]$ be the matrix. Define $T\[i,j,\ell\]$ be the maximum possible sum of the top-left corner, for any dividing line that divides $A\[i..n,j..n\]$ using at most $\ell$ horizontal parts. Then there is a simple recurrence relation for $T\[i,j,\ell\]$, e.g.,

$$\begin{align\*} T\[i,j,\ell\] &= \max(T\[i+1,j,\ell)+A\[i,1\]+\dots+A\[i,j\],U\[i,j,\ell\])\\ U\[i,j,\ell\] &= \max\\{T\[i+1,j',\ell-1)+A\[i,1\]+\dots+A\[i,j'\] \mid j' \< j\\}). \end{align\*}$$

Notice that

$$U\[i,j,\ell\] = \max(U\[i,j-1,\ell\],T\[i+1,j-1,\ell-1)+A\[i,1\]+\dots+A\[i,j-1\]).$$

Then, it is easy to fill in all entries of $T$ and $U$ in $O(n^2k)$ time, as long as you fill them in the right order. Please check all of the details, as I haven't checked the details carefully.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Is there such a thing as $coW[1]$-hardness?
I have a problem $\mathsf{A}$ and I would like to analyze its (parameterized) computational complexity.

I found a parameterized reduction from the complement of the independent set ($\mathsf{coIS}$) problem (i.e. given a graph $G$ and an integer $k$, is there **no** independent set of size $k$ in G?), such that there is a parameter $\kappa$ to my new problem $\mathsf{A}$ that only increases by a constant in regards to $k$.

Formally, I have found a reduction function $R$, that takes as input an instance $(G, k)$ of $\mathsf{coIS}$, where $G$ is an arbitrary undirected graph and $k \in \mathbf{N}$ is some integer, and outputs an instance $(I, \kappa)$ of problem $\mathsf{A}$, such that:

1. $(G, k) \in \mathsf{coIS} \Leftrightarrow (I, \kappa) \in \mathsf{A}$ (alternatively: $(G, k) \not\in \mathsf{IS} \Leftrightarrow (I, \kappa) \in \mathsf{A}$).
2. $R$ runs in $f(k) \cdot |G|^{\mathcal{O}(1)}$ time, where $f$ is some computable function (in our case, $f$ is polynomial).
3. $\kappa \leq h(k)$, where $h$ is some computable function.

From this, I infer that problem $\mathsf{A}$ is coNP-hard. However, I would also like to make a statement about the parameterized complexity of problem $\mathsf{A}$. My intuition tells me that problem $\mathsf{A}$ is $coW\[1\]$-hard when parameterized by $\kappa$.

However, I have not been able to find any reference to the class $coW\[1\]$ in the literature or in any previously asked question. Given that my understanding of the class $W\[1\]$ and the $W$-hierarchy is somewhat primitive, I don't know if the notion of $coW\[1\]$ makes any sense. I could well imagine that $W\[1\] = coW\[1\]$ holds, but I don't know how one would prove such a statement.

# Answer
The paper *The Parameterized Complexity of Local Consistency* by Gaspers and Szeider discusses coW\[1\]- and coW\[2\]-complete problems. This is maybe a starting point.
> 3 votes

---
Tags: complexity-theory, reductions, complexity-classes, parameterized-complexity
---


# Question
Title: Cache Miss in First Private Cache but Hit in Shared LEvel 2 Cache: Does it Result in a Penalty?
In the context of Shared Memory Multiprocessor (SMP) systems with different cache levels, if a cache miss occurs in the first private cache but is followed by a hit in the second shared cache, would this situation lead to a penalty or delay in data retrieval?

So far all question's I've solved involve a data or instruction cache and some information about the byte, then assembly code. Everything I have to do is analyse miss rate or hit rat or CPI etc. So my question is what about the case I am mentioning here. How would someone go about solving it, what type of information is needed in order to solve it? (I'm prepareing for an Exam).

# Answer
If another thread has modified the logical memory belonging to that cache line then there will be a delay.

It is unlikely that the processor can move data directly from one private cache to another. So if the data is changed in processor B’s private cache, that processor needs to be notified, then it writes the cache line to the shared cache, then processor A reads it from there. So a delay.

To detect the situation, one method is to empty the shared cache when a line is modified in the private cache. That’s no problem since the data must not be used anyway. So A will try to read from the next cache level, and things are handled there where it is less time critical.

There are also usually instructions that force writing data to memory, and you would use them for data that is supposed to be changed.
> 0 votes

---
Tags: memory-management, cpu, cpu-cache, memory-hardware, virtual-memory
---


# Question
Title: How to topologically classify points in 3d space generating a surface?
Say I have N points sampled on a surface in 3 dimensions (ie. points on the surface of a sphere, 1-torus etc.). Is there an algorithm that would be able to count the number of holes in the surface formed by those point (ie. zero holes for the sphere, 1 hole for the 1-torus etc)?

Edit: As a constraint, the points that make up the surface are expected to have an equilibrium distance that is in general much smaller than the dimensions of the surface. For instance, if the points make up a sphere of radius 40, we can expect each point to have neighbours within a distance of 2 units from each other, although this equilibrium distance is noisy (ie. fluctuates randomly with 2 as mean and small std).

# Answer
> 1 votes
You are looking for persistent homology, a branch of computational topology that studies precisely the question you asked.

Roughly, the idea is as follows. Pick a "resolution radius $r$", draw a ball of radius $r$ around each sample point, and compute the resulting homology, let's write it as $H\_r$ (homology "counts holes" and gives you other information about the space). Depending on the chosen resolution, you get the relevant information. Persistent homology studies, among other things, how to efficiently compute the $H\_r$'s, say as $r$ increases.

---
Tags: computational-geometry, topology
---


# Question
Title: Direct construction of NFA for the difference of regular languages
Let $A$ and $B$ be regular languages. Let $C$ be their difference, i.e $C = B \setminus A$.

Given NFAs for $A$ and $B$, is it possible to directly construct an NFA for $C$ without (implicitly or explicitly) converting them to DFAs first?

# Answer
> 3 votes
The short answer is "yes".

Probably the easiest way to explain it is with an example; turning this into a formal algorithm should be straightforward.

The first NFA, $M$, accepts the language $(a\cup b)^\*$:

$$q\_0 = \epsilon \cup a q\_0 \cup b q\_0$$

with the start state being $q\_0$.

This is probably not notation that you're used to, but the reason for using this will become clear soon; it's basically saying the same thing as the context-free grammar:

$$ S \rightarrow \epsilon $$ $$ S \rightarrow a S $$ $$ S \rightarrow b S $$

You can see how this is also a description of a NFA. Each term on the right-hand side is either a transition $aq\_i$, which means read an $a$ and go to state $q\_i$, or $\epsilon$ which means that the state is a final state.

The second NFA, $M$, accepts the language $(a\cup b)^\*aa(a\cup b)^\*$, that is, any string which contains $aa$. The start state is $q\_1$; I've used unique state names for reasons that will become obvious in a moment. I deliberately picked an NFA which has some nondeterminism just to show that this works for that case.

$$q\_1 = a q\_1 \cup b q\_1 \cup a q\_2$$ $$q\_2 = a q\_3$$ $$q\_3 = \epsilon \cup a q\_3 \cup a q\_3$$

We would like to construct a NFA which accepts the language:

$$Q\_0 = q\_0 \setminus q\_1$$

expanding one level gives:

$$Q\_0 = (\epsilon \cup a q\_0 \cup b q\_0) \setminus (a q\_1 \cup b q\_1 \cup a q\_2)$$ $$ = \epsilon \cup a (q\_0 \setminus (q\_1 \cup q\_2)) \cup b (q\_0 \setminus q\_1)$$ $$ = \epsilon \cup a Q\_1 \cup b Q\_0$$

where:

$$Q\_1 = q\_0 \setminus (q\_1 \cup q\_2)$$

Note that we already had a state which handled the $b$ transition correctly. For the $a$ transition, we didn't, so we introduced one.

We continue:

$$Q\_1 = q\_0 \setminus (q\_1 \cup q\_2)$$ $$= (\epsilon \cup a q\_0 \cup b q\_0) \setminus (a q\_1 \cup b q\_1 \cup a q\_2 \cup a q\_3)$$ $$= \epsilon \cup a (q\_0 \setminus (q\_1 \cup q\_2 \cup q\_3)) \cup b (q\_0 \cup q\_1)$$ $$= \epsilon \cup a Q\_2 \cup b Q\_0$$

where:

$$Q\_2 = q\_0 \setminus (q\_1 \cup q\_2 \cup q\_3)$$

continuing again, going a little more slowly this time:

$$Q\_2 = q\_0 \setminus (q\_1 \cup q\_2 \cup q\_3)$$ $$= (\epsilon \cup a q\_0 \cup b q\_0) \setminus ((a q\_1 \cup b q\_1 \cup a q\_2) \cup (a q\_3) \cup (\epsilon \cup a q\_3 \cup b q\_3))$$ $$= a (q\_0 \setminus (q\_1 \cup q\_3)) \cup b (q\_0 \setminus (q\_1 \cup q\_3))$$ $$= a Q\_2 \cup b Q\_2$$

Note that we used the fact that $\epsilon \setminus \epsilon = \varnothing$.

So in summary, we have the following NFA with start symbol $Q\_0$:

$$Q\_0 = \epsilon \cup a Q\_1 \cup b Q\_0$$ $$Q\_1 = \epsilon \cup a Q\_2 \cup b Q\_0$$ $$Q\_2 = a Q\_2 \cup b Q\_2$$

You can verify for yourself that this accepts the language.

There are several things to notice about this.

First off, the process must terminate; there are only a finite number of possible transition states which could be created.

Secondly, the running time could be exponential in the worst case; each transition state is of the form $\bigcup\_i q\_i \setminus \bigcup\_j q\_j$ where the left-hand side of the set minus is a subset of the states from the first machine and the right-hand side is the same for the second machine. There is a finite number of such subsets, but there could be exponentially many in general, and sometimes there will be. And the reason is...

...the final answer is a DFA! It's not hard to see that this will always be the case. Your question only asked for a method that didn't convert the two NFAs to DFAs *first*, and you never said anything about not constructing a DFA for the final answer.

Basically what we've done here is folded the NFA-to-DFA conversion algorithm together with the DFA difference algorithm, so one algorithm does both. I think this satisfies the requirements of your question.

# Answer
> 1 votes
Let $N\_A$ and $N\_B$ be NFAs for the languages $A$ and $B$, respectively. Note that $B\setminus A = B\cap \overline{A}$. Hence, to obtain an NFA $N\_C$ for $C = B\cap \overline{A}$, one needs to complement $N\_A$, but you don't have to complement $N\_B$ as the product construction for intersection can be easily adapted to nondeterministic automata. To sum up, the best you can do is the following: determinize $N\_A$ and turn it into a complementing DFA $D$ for $\overline{A}$, and then use a product construction of $N\_B$ and $D$ to get an NFW $N\_C$ for $ L(N\_B)\cap L(D) = B\cap \overline{A}$.

Note that there is no way around determinizing $N\_A$ as if you fix $B$ to $\Sigma^\*$, then $B\setminus A = \overline{A}$, and the best known way to complement NFAs is by first determinizing them. The latter is justified by examples in which there is an exponential gap between the NFA complexity of a language and its complement. For example, see here and here.

# Answer
> 0 votes
There's no known way to complement an NFA without first converting to a DFA, which is a simpler operation than what you need here: complementing and then intersecting.

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


# Question
Title: How to write down a program of a Turing Machine with just two states that, when given the empty tape as inputs, halts after 6 steps
I’m definitely not a computer science expert, but I find this topic extremely interesting - due to this interest, I’ve recently enrolled in a class about Turing Machine.

The lecturer assigned to us an exercise and one of the questions is: ‘Write down a program of a Turing Machine with just two states that, when given the empty tape as inputs, halts after 6 steps (please note: the last step will be the one at which the machine halts. Use the simulator at http://morphett.info/turing/turing.html to count the steps. If the machine halts after 5 steps it’s enough: don’t agonise over this exercise)’. Despite professor’s suggestion, I’m agonising, and the fact that the answer (that will be evaluated) is due by tomorrow does not help. I didn’t find anything online, and the blank tape halting problem confused me more. I’m gently asking you the same question, hoping someone will help me. The best I got are programmes that loop or halt after only 2 steps. I’m using this notation: for ‘current state’ and ‘new state’ I use 0,1,2,…; for the ‘current symbol’ and ‘new state’ I use 0,1,\_(blank); for the ‘direction’ I use r(right),l(left),\*(do not move).

I thank in advance who will respond for the patience. I hope my question doesn’t seem too naïve or stupid.

# Answer
It is impossible, unless your professor defined the semantics of a Turing machine in a non-standard way, or perhaps you meant at most two non-final states? Here is why:

Every Turing machine $M$ has at least two states: an accepting state $q\_{acc}$, and a rejecting state $q\_{rej}$. Whenever $M$ reaches $q\_{acc}$ or $q\_{rej}$, it halts immediately and accepts or rejects, respectively. The latter implies that every Turing machine $M$ with only two states must have $q\_0 \in \\{ q\_{acc}, q\_{rej}\\}$, where $q\_0$ is the initial state of the machine, and thus such machines either accept all inputs or reject all inputs, and they always halt after 0 steps.

If you meant at most 2 states that are not final, that is, do not equal $q\_{acc}$ or $q\_{rej}$, then you can do the following. Define a non-final state $q\_0$, and let the input alphabet of the machine include the numbers in $\\{1, 2, 3, 4, 5 \\}$. Then, the machine operates as follows: $q\_0$ is the initial state of the machine, and $\delta(q\_0, b) = (q\_0, 1, L)$, where $b$ stands for an empty cell (blank symbol). Then, define $\delta(q\_0, i) = (q\_0, i+1, L)$, for all $1 \leq i \< 5$, then define $\delta(q\_0, 5) = (q\_{acc}, 5, L)$.

I assumed that the machine's tape is left bounded, and if this is not the case, it is easy to modify the solution by alternating between two non-final states $q\_0$ and $q\_1$ while moving between two adjacent tape-cells, upon reading increasing numbers, and I leave the details to you.

**Edit:** if the machine has a stop action in its transition function (indicating that the head of the machine stays in the same cell-tape and does not move left or right), then you can take the above solution and replace going left with the "stop action".
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Thread safety due to no runtime allocation of memory, why?
I was watching a presentation related to the MuJoCo simulator (and other topics which were more relevant for the presentation itself) and at one moment in the presentation it is mentioned that MuJoCo has thread safety due to not having memory allocation in runtime.

Why is thread safety ensured because of this? Memory might not be allocated in runtime, but still various threads might try to access the same resource, no?

# Answer
> 1 votes
They seem to believe that runtime memory allocation causes thread safety to be lost. But the only problem is that you need to synchronise allocation and deallocation of memory, so if two threads need the same memory at the same time, one allocates and the other waits until it has been allocated.

Once that memory is allocated you have the same problem as with fixed memory to keep your access to the memory thread safe.

---
Tags: memory-management, simulation, threads
---


title: How do you bit-shift in RISC-V?

text:
# Question
Title: How do you bit-shift in RISC-V?
In the following video on computer organization:

https://youtu.be/DoR505t8-7I?t=114

the instructor displays the following:

and says that the hex string `0xFFFFFF00` is equivalent to -256. After doing a calculation to see this represented in two's complement, this makes sense to me. For my question below it'll help to represent this bitwise as

```
1111|...|1111|0000|0000

```

Also, these instructions are in RISC-V so they are stored in the little-endian system, so in memory this is actually stored as

```
0000|0000|1111|...|1111

```

The second line calls for a left logical shift of `0xFFFFFF00` and I can't quite understand how it's supposed to turn into `0xFFFFF800`. If we shift in the little-endian bit picture, you would get

```
0000|0001|1111|...|1110

```

and this is so far from the given value that I'm sure this is not how it's supposed to be done. But also if we bit shift in the picture before writing it in little-endian, we would get

```
1111|...|1111|1110|0000|0000

```

and this is `0xFFFFFE00` not `0xFFFFF800`. Am I making a mistake here, is the prof making a mistake, or does the endian system somehow also flip the bits?

# Answer
> 1 votes
I'm just now realizing that I neglected to notice the 3 in the second line of code, indicating that the bits are shifted three times. I guess in RISC-V we shift in some way so that you can think about the usual representation rather than little-endian, and therefore the bit shift looks like this

```
1111|...|1000|0000|0000|

```

and indeed that is `0xFFFFF800`.

# Answer
> 0 votes
When you shift, you don’t shift memory, you shift values. The result of shifting 0xffffff00 left by one bit position is the same whether the processor is bigendian or littleendian.

Shifting to the left by k bits multiplies by 2^k, shifting to the right divides by 2^k (roughly. Signed integers can be interesting).

---
Tags: memory-management, numeral-representations
---


title: Scheduling problem on bipartite graph

text:
# Question
Title: Scheduling problem on bipartite graph
Consider a bipartite graph $G=(U, V, E)$. Each $v \in V$ represents a soccer team, and each $u \in U$ represents a mini-tournament which needs to be scheduled. Tournament $u$ is adjacent to team $v$ if $v$ plays in that tournament $u$. Each tournament uses a full day.

If $u\_i$ and $u\_j$ share no common neighbor, these two tournament can be scheduled on the same day. Similarly, one can schedule multiple tournaments in one day if there is no such conflict.

Is there a way to compute the minimum number of days required to complete all the tournaments and the corresponding scheduling?

# Answer
> 1 votes
While this seems like homework, since it was asked 8 years ago it is probably past the point that the question asker can benefit from this for that course.

Build a graph $G\_2 = (U, E\_2)$ of where the vertices of $G\_2$ are only the $u$-vertices from your original graph. And join an edge between any two tournaments $u\_i, u\_j$ if they are in conflict (i.e. if there exists some $v\_k$ adjacent to each of $u\_i$ and $u\_j$ in your original graph).

This is normally called the *conflict graph* of a set of objects - in this case, your set of objects are tournaments, some of which are in conflict with others.

A **minimum colouring of this $G\_2$ graph will provide the minimum number of tournament days** to complete all of them. Each colour corresponds to a day, so two tournaments with the same colour in an optimal colouring would be an example of two tournaments that play on the same day.

**Extra Aside**: This can be used to show your problem is NP-hard. Consider any graph colouring instance - then you can make all the vertices of this instance a set of $U$-nodes, and for every edge in the graph colouring instance, create a $v$-node adjacent to these two edge endpoints. This constructs a rather simple (but somewhat larger) instance of your tournament problem. The problem size would still be O(n+m) and so this is a polytime construction.

# Answer
> 0 votes
So here, it looks as though $u \in U$ is a vertex representing the team and $v \in V$ is an edge between the vertices representing the matches possible.

If we can generate a Bipartite Graph, the edges ${ v\_i, ...v\_j}$ going across are all non-conflicting matches. Those edges for this matching ( $M\_1$) can be held on that day. Next, we remove ${ v\_i, ...v\_j}$ and check to see if we can get more Bipartite Graphs. The edges going across are similarly the non-conflicting matches.

Not sure if this is what you asked for.

---
Tags: graphs, scheduling
---


# Question
Title: what is the smallest 3-CNF possible that enforces the boolean expression: a = b + c?
What is the smallest 3-CNF system of equations possible that enforces the boolean expression: a = b + c for boolean variables a, b, c?

'Smallest' can be defined as: (1) Number of 3 CNF clauses. (2) Number of new variables introduced in the clauses.

We are interested in both cases.

# Answer
To begin with, note that $b+c$ can be expressed as the disjunction $b\lor c$. To enforce equation, you need to express "$a$ iff $(b\lor c)$", and that can be encoded as the following CNF formula: $$ \phi = (\neg a \lor b \lor c) \wedge ((\neg b \wedge \neg c) \lor a)$$

Indeed, I used the fact that $A\to B \equiv \neg A \lor B$ and applied that twice. $\phi$ is not in CNF form, but you can simplify it to: $$ \phi = (\neg a \lor b \lor c) \wedge (\neg b \lor a) \wedge(\neg c \lor a) $$

Note that $\phi$ can be read as "c implies a, and b implies a, and a implies at least one of b or c". Can you prove that it is minimal?
> 3 votes

---
Tags: boolean-algebra
---


# Question
Title: Is there a [non-comparative] sorting algorithm, sorting an array in $o(n \log n)$?
We have shown that any comparative sorting algorithm has the worst-case complexity of $\Omega(\log (n!)) = \Omega(n \log n)$, as it has to cover all the ways a permutation can be, and according to the pigeonhole principle, there is a case where more than or equal to half of the currently unknown permutations would be unknown after each comparison; but that doesn't apply on non-comparative sorting algorithms. For example, counting sort can sort an array in $O(n + w)$, where $w$ is the maximum element of the array. But all these algorithms are based on at least one another parameter, that are independent of $n$, or at least $n$ doesn't force any upper-bound for those parameters to exist, and can be as large as anything. Is there a non-comparative one, that we can guarantee the worst-case complexity of $o(n \log n)?$

# Answer
Radix sort can sort an array in $O(n.w)$ where $w$ is the key length. As $w$ is $O(\log n)$, this means it can sort an array with the performance of $O(n \log n)$. In fact, every non-comparison sort in the form of $O(n.w)$ or $O(n.k/d)$ is $O(n \log n)$.

https://www.drdobbs.com/architecture-and-design/the-fastest-sorting-algorithm/184404062
> 1 votes

---
Tags: asymptotics, sorting
---


# Question
Title: Is "super-exponential" a precise definition of algorithmic complexity?
I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity.

For instance, if an algorithm runs for $nC(n-1)$ steps, where $C(\cdot)$ is the Catalan number, is this algorithm super-exponential in $n$?

# Answer
> 14 votes
"Super-exponential" just means more than exponential, so a function is super-exponential if it grows faster than any exponential function. More formally, this means that it is $\omega(c^n)$ for every constant $c$, i.e., if $\lim\_{n\to\infty} f(n)/c^n=\infty$ for all constants $c$.

Conversely, a function is "sub-exponential" if it is $o(c^n)$ for every constant $c\>1$, i.e., $\lim\_{n\to\infty} f(n)/c^n=0$ for all constants $c\>1$.

Asymptotically, the $n$th Catalan number is $\Theta(4^n\\, n^{-3/2})$. This is $o(4^n)$, so the Catalan numbers are not super-exponential; it is $\omega(2^n)$, so they're not subexponential either. The Catalan numbers are just exponential.

An exception to the above definitions is that, in some contexts, functions of the form $b^{n^k}$ for constants $b,k\>1$ are considered to be exponential, even though $$ \lim\_{n\to\infty}\frac{b^{n^k}}{c^n}=\lim\_{n\to\infty}b^{n^k-n\log\_b c}=\infty\\,.$$ For example, the complexity class **EXP** is defined as the class of languages decided by Turing machines running in time $O(2^{n^k})$ for any $k$. Thanks to Yuval Filmus for pointing this out.

# Answer
> 5 votes
> Using **David's definition**; a function is super-exponential if it grows faster than any exponential function. More formally, this means that it is $\omega(c^n)$ for every constant $c$, i.e., if $\lim\_{n\to\infty} f(n)/c(n)=\infty$ for all constants $c$.

---

The $n$-th formula of Catalan Numbers is given by Wikipedia as;

$$ C\_n \approx \frac{4^n}{n^{3/2}\sqrt \pi} $$

Than we have;

$$4^n \> \frac{4^n}{n^{3/2}\sqrt \pi} \> 2^n$$

---

By the definition of super-exponential time, $4^n$ not super-exponential time, this implies $C\_n$ also not super-exponential time. Since we have;

$$\lim\_{n \rightarrow \infty} \frac{f(n)}{4^n} = \infty,$$ with super-exponential growing function $f$.

This implies that Catalan numbers are exponential, not super-exponential.

---

* 1. Note: Answer updated after David's comments.
* 2. Note: In, Analytic Combinatorics, Sedgewicks says that Catalan Numbers is roughly comparable to an exponential, $4^n$, modulated by a subexponential factor. here $1/\sqrt{π n^3}.$

# Answer
> 1 votes
The term 'superexponential' is *not* a precise description of algorithmic complexity, but it always suggests a growth greater in order than a simple exponential function of form $b^n$ for some $b \> 1$. There are three main levels of superexponential growth:

1. Beyond the class **E**, the class of all problems with *simple exponential* complexity. A problem in **E** has complexity upper-bounded by an expression of the form $b^n$ where $b \> 1$.
    * Two exponential functions with different bases are of different orders of growth. Namely, $2^n$ is little-o of $e^n$, which in turn is little-o of $10^n$. Using the properties of change of bases, simple exponential time is $2^{O(n)}$ time.
    * Factorial $n!$ time is superexponential under the first definition, but not in the latter two. It is often categorized separately from exponential algorithms. Also, $(n + 1)!$ is of different orders of growth than $n!$.
    * The asymptotic formula for Catalan numbers would fall under this category. Even if the function is not of a simple exponential form, it is still upper bounded by a simple exponential function $4^n = 2^{2n}$.
2. Beyond the class **EXPTIME**, the *full exponential* complexity class. The complexity of a problem in **EXPTIME** is upper-bounded by an expression of the form $b^{g(n)}$ where $b \> 1$ and $g(n)$ is polynomial growth.
    * Factorial growth is slower than $n^n$ growth. However, $n^n$ can be converted to an exponential expression $e^{n \ln n}$, and the exponent exhibits polynomial-order growth. Thus, factorial time is **EXPTIME**, but is still upper-bounded by an expression requiring only one font size.
    * The doubly exponential expression $2^{2^x}$ is superexponential under the second definition as well as the first, but not the third. You need three font sizes to write down this expression or an upper bound. This function, however, does not involve any higher hyperoperators aka 'superexponentiation'.
3. Being **nonelementary**, meaning that the expression for the upper bound cannot be done with nested exponents at all.
    * In fact, the word 'superexponent' may refer to tetration, which is used in an actual mathematics journal (Nick Bromer, 1987).
    * Professor Brailsford from a Computerphile video about primitive recursion and the Ackermann function, discussed that one indication of a function that *has* to be done recursively is when the function starts behaving superexponentially (Computerphile, 2014, 12′45″). By superexponential, he means the third definition. It is not the growth rate of $n^n$ (he said "which would be exponential"), but is $\underbrace{n^{n^{n^{\cdot^{\cdot n}}}}}\_n$.

---
Tags: time-complexity, terminology, asymptotics, runtime-analysis
---


# Question
Title: Reducing from the complement of the Halting Problem
Consider the halting problem $HALT\_{TM} = \\{\langle M, w\rangle: M \text{ is a TM that halts on input } w\\}$,

and some undecidable Language $L$ of the form $L = \\{\langle M\rangle: M \text{ does a thing} \\}$.

If I want to reduce the halting problem to $L$, from what I understand, I have to construct a Turing Machine $M'$ which takes the input $\langle M, w\rangle$, and if $M$ halts on $w$, $M'$ does the thing, otherwise, $M'$ does not do the thing.

Now, I want to reduce the complement of the halting problem to $L$. Meaning, I need to construct a Turing Machine $M''$ with the following:

* If $M$ halts on $w$, then $M''$ does not do the thing.
* If $M$ does not halt on $w$, then $M''$ does the thing.

The first part seems simple to implement, if $M$ halts on $w$, then $M''$ can be forced to enter into an infinite loop. But then, I need $M''$ to do the thing whenever $M$ does not halt on $w$, which from my understanding is the very definition of the halting problem - since I don’t know whether $M$ will ever halt on $w$, I cannot ever do the thing. Does that mean a reduction is not possible, or is my approach/understanding wrong?

# Answer
For the question to be understandable, you should indicate that "a machine does a thing" actually means that "a machine performs some finite computation and then halts". Anyway, this should clarify the reduction concept to you:

Note that by reducing from the complement of the halting problem, that is from $\overline{HALT\_{TM}} = \\{ \langle M, w\rangle: \text{$M$ is a TM that does not halt on $w$} \\}$, then you (by you I mean the reduction) need, upon getting in put of the form $\langle M, w\rangle$, to construct, halt and output a description of a machine $\langle M''\rangle$ such that $\langle M'' \rangle\in L$ only when $\langle M, w \rangle \in \overline{HALT\_{TM}}$. That is, $M''$ "does a thing" iff $M$ does not halt on $w$.

There is a fine line here that you need to understand. You (the reduction) does not simulate the run of $M$ on $w$ indefinitely, and in fact, you have to halt on any input of yours. Instead, you construct a machine $M''$, based on the description of $M$ and $w$. Now $M''$ need not be a decider machine, and we don't care as long as we (the reduction) always halt and output its description. So the reduction is usually not the one that simulates the run of $M$ on $w$, it just outputs a description of $M''$, and $M''$, upon reading one of its inputs, can simulate the run of $M$ on $w$, or do whatever it is defined to do.

**Note:** if the reduction somehow wants to simulate the run of $M$ on $w$, then it must do that for a finite number of steps as it must eventually halt. Anyway, this is usually not the case. The right way to think of the reduction is as a black box (a TM), that gets $\langle M, w\rangle$ as input, runs for a finite number of steps, and then outputs $\langle M'' \rangle$.
> 1 votes

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


title: Interpretation of co-NPCompleteness?

text:
# Question
Title: Interpretation of co-NPCompleteness?
Given a Problem $A$ that has an answer $true$ if and only if both conditions $1$ and $2$ are $false$, for some conditions 1 and 2.

Whether condition $2$ is $true$ can be tested with certainty in deterministic polynomial time. Thus, we can say that answer to an instance of $A$ is $false$ in polynomial time (in case condition $2$ holds). If condition $2$ is $false$, we still need to test condition $1$.

Checking if condition $1$ is $true$ is an NP-complete problem.

Can we thus conclude that the original problem $A$ with both conditions is coNP-complete?

# Answer
> 4 votes
As far as I understand your problem statement is as following:

> Given a Problem $A$ that has an answer $true$ if and only if both (some) conditions 1 or 2 are $false$.

We have a decision problem $A(w) = \overline{B(w)} \wedge \overline{C(w)}$, where $B$ and $C$ correspond to the conditions 1 and 2 respectively.

> Whether condition 2 is $true$ can be tested with certainty in polynomial time.

$C \in P$.

> Checking if condition 1 is $true$ on $A$ is an NPComplete problem (if we consider all possible instances of $A$).

$B \in NP$ and $B$ is $NP$-hard.

(Please, correct me if I misunderstood the problem statement)

So, let's rewrite the statement using the language notation: $L\_B \in NP$, $L\_C \in P$, and $L\_A = \overline{L}\_B \cap \overline{L}\_C$.

By definition $L\_A \in coNP$ if $\overline{L}\_A \in NP$. But $\overline{L}\_A = L\_B \cup L\_C$ (De Morgan law). Since we are given that $L\_B \in NP$ and $L\_C \in P$, $L\_B \cup L\_C$ is in $NP$ as well. So, $L\_A$ is in $coNP$.

Now, take $\overline{L\_C} = \emptyset$ which is clearly is in $P$, and so is $L\_C = \Sigma^\*$. For any $NP$-complete language $L\_B$, $L\_B \cup L\_C = \Sigma^\*$. But $\Sigma^\*$ is not $coNP$-complete.

# Answer
> 1 votes
Let $C\_1$ and $C\_2$ be languages representing the conditions $1$ and $2$, respectively. Then, $C\_1 \in \text{NP-complete}$ and $C\_2 \in \text{PTIME}$, and by writing down formally what you mentioned, we get $A = \overline{C\_1} \cap \overline{C\_2}$.

Now you can use the following claim:

**Claim:** A language $L$ is NP-complete iff $\overline{L}$ is coNP-complete.

So to understand whether $A$ is coNP-complete or not, you can check whether its complement is NP-complete. In your case, $\overline{A} = C\_1 \cup C\_2$, and since $C\_2$ can be any problem in $PTIME$, then $\overline{A}$ can be a "very simple language". I leave the details to you.

**Note:** the important thing here is the above claim. To understand coNP-completeness, it is sufficient to understand NP-completeness.

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


title: Median of two sorted arrays

text:
# Question
Title: Median of two sorted arrays
Two sorted arrays `A` and `B` are given having size `l` and `m` respectively. Our task is to find the median of these two sorted arrays combined. Suppose the length of the combined array is `n` i.e. `n = l + m`.By definition the median will be greater than half of the elements and less than the other half.

Suppose `A[i]` is the median. Then since A is sorted so

```
                            A[i] >= A[k] for all k = 0 to i - 1

```

and it will also be greater than **`j = ⌈n/2⌉- (i - 1)`** elements in `B` as `i + j` must be equal to `⌈n/2⌉`.

```
                      A[i] >= B[k] for all k = 0 to ⌈n/2⌉- (i - 1)

```

If `A[i]` is not the median, then depending on whether `A[i]` is greater or less than `B[j]` and `B[j + 1]`, you know that `A[i]` is either greater than or less than the median.

Thus binary search for A\[i\] can be done here. Following is the pseudo code I have found from a website:

```
                MEDIAN-SEARCH(A[1 . . l], B[1 . . m], left,right)

                 if left > right:
                   MEDIAN-SEARCH(B, A, max(1, ⌈n/2⌉ − l), min(m, ⌈n/2⌉))

                 i = ⌊(left + right)/2⌋

                 j = ⌈n/2⌉ - i

                 if (j = 0 or A[i] > B[j]) and (j = m or A[i] <= B[j + 1])
                   return A[i]

                 else if (j = 0 or A[i] > B[j]) and j != m and A[i] > B[j + 1]
                   return MEDIAN-SEARCH(A, B, left, i − 1)

                 else
                   return MEDIAN-SEARCH(A, B, i + 1, right)

```

The initial call to find median will be

```
                 MEDIAN-SEARCH(A[1..l], B[1..m], max(1, ⌈n/2⌉ − m), min(l, ⌈n/2⌉))

```

My question here is:

1. I am not able to visualize intuitively how **`left`** and **`right`** initial values are being used in the code above.
2. What will be time complexity of the algorithm? Will it be `log O(N)`? or will it be `log O(max(l, m))`?

# Answer
> 0 votes
The source hinted that it is by the definition of median and outlined how to verify an element in $O(1)$.

If $l \> m$, $left = \lceil (l - m) / 2 \rceil$, $right = \lceil (l + m) / 2 \rceil$. Else, $left = 1$, $right = l$.

The median is guaranteed to be found in $A\[left..right\]$ using that range, or if not then trivially found in $B$.

As this is essentially a binary search, it runs in $O(log(min(l, m))$.

If $A$ and $B$ are not sorted, you can combine both and run quickselect in $O(log(max(l, m))$ instead.

---
Tags: algorithms, divide-and-conquer, binary-search
---


title: Idea for Improving Heapsort

text:
# Question
Title: Idea for Improving Heapsort
i have an idea of enhancing the heapsort by finding the max and min simultaneously and then swapping the max into the last node, and then the min will be swapped into the second to the last node, and then they will be removed or pop. and then they will be sorted in the array, the max will be at the last element, and the min will be at the beginning element.

question:

1. is this applicable?
2. will this improve the heapsort?
3. what are the steps or ways i must do in order to implement this?(java)

# Answer
> 1 votes
It doesn't matter how you pop, either min first, max first, or alternating. It is still $O(\log n)$ for each pop.

---
Tags: algorithms, heap-sort
---


title: Greedy Maximum Bipartite Matching

text:
# Question
Title: Greedy Maximum Bipartite Matching
To find the maximum matching on a bipartite graph, I propose the following greedy algorithm: At each iteration, pick an unmatched vertex with the smallest degree and match it to one of it's neighbours if possible. Remove the 2 matched vertices and all of it's edges from the graph and repeat till the graph is empty.

I've tried finding a counter example for this greedy algorithm, but am not able to come up with one.

Could someone provide me with a counter example? Thanks!

# Answer
> 1 votes
Here's a counter example on codeforces. However if it's *complete* bipartite matching, we can use the greedy Nobel winning algorithm in Economics.

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


# Question
Title: Weighted bipartite maximum cost with a fixed number of vertices
Having a complete bipartite graph with parts $A$ and $B$, which is edge-weighted, is there a way to compute a subgraph with the maximum sum of all weights and:

1. Only a constant number $n$ of vertices from $A$ are used.
2. At most one edge points to each of the vertices in $B$.

In essence, which nodes from $A$ and which remaining edges to remove from the complete bipartite graph to get a graph with the maximum possible sum of its weights satisfying constraints 1 and 2.

In the example above, $n=2$ and $w\_1 + w\_2 + w\_3$ is the maximum sum of weights which satisfies the two constraints.

# Answer
> 1 votes
The problem is $\mathsf{NP}$-hard by a reduction from Exact Cover by 3-Sets:

> **Instance**: a set $X = \\{ x\_1,x\_2,...,x\_{3n}\\}$ and a family $F = \\{ ( x\_{i\_1}, x\_{i\_2}, x\_{i\_3}) \\} $ of 3-elements subsets of $X$ (triples);
> **Question**: Is there a subfamily $F'$ of $F$ such that every element in $X$ is contained in exactly one triple of $F'$.

To reduce it to your problem, the family $F$ corresponds to set $A$ such that each set in $F$ corresponds to a vertex in $A$. The set $X$ corresponds to set $B$ such that each element of $X$ corresponds to a vertex in $B$. Let $a \in A$ be the vertex corresponding to a set $S \in F$ and let $b \in B$ be the vertex corresponding to an element $x\_i \in X$. Then the edge $(a,b)$ has unit weight if $x\_i \in S$, else it has weight $0$.

It is easy to see the following claim:

*Claim:* There exists a feasible solution for $(X,F)$ if and only if the cost of the instance $(A,B)$ is $3n$ (which is maximum possible for the constructed instance).

Thus, the bipartite matching problem stated in the problem definition is $\mathsf{NP}$-hard.

---
Tags: graphs, combinatorics, matching, bipartite-matching, clustering
---


title: Adding O(x)+O(x-1)+O(x-2)+

text:
# Question
Title: Adding O(x)+O(x-1)+O(x-2)+
I have a function $f$ such that is the sum of big O terms, such as

$$f=\left\[\sum\_{i=1}^x \frac{1}{i}\right\] +O\left(\frac{\ln^4 x}{x}\right)+O\left(\frac{\ln^4 x-1}{x-1}\right)+O\left(\frac{\ln^4 x-2}{x-2}\right)+\ldots$$

where $x$ is a positive integer. Am I correct in that I can simply write

$$f=\left\[\sum\_{i=1}^x \frac{1}{i}\right\] + O\left(\frac{\ln^4 x}{x}\right)$$

because I just need to write the bigger value for the big O, in this case being $\frac{\ln^4 x}{x}$?

Any intuitive, even informal answer would be welcome.

# Answer
It is not correct because you don't have a constant number of terms in your sum. Indeed, your sum has $\ln^4 x$ terms (assuming it stops when the numerator is $0$).

Actually the smaller terms may have an impact. However we can bound it.

Let's start by rewriting the sum: $$\sum\_{i=0}^{\ln^4 x -1} \frac{\ln^4 x-i}{x-i} = \sum\_{i=1}^{\ln^4 x} \frac{i}{x-\ln^4 x + i} . $$

Now, we have: $$\sum\_{i=1}^{\ln^4 x} \frac{i}{x-\ln^4 x + i} \leq \sum\_{i=1}^{\ln^4 x} \frac{i}{x-\ln^4 x } = \frac{1}{x-\ln^4 x }\sum\_{i=1}^{\ln^4 x} i = O\left( \frac{\ln^8 x}{x-\ln^4 x} \right) \ ,$$ where we used a smaller denominator in order to have the inequality and then we used the Gauss formula for the sum of the first $\ln^4 x$ integers and passed to the asymptotic notation in order to get rid of constants and lower-order terms.

Now, this term is actually $O(1)$, so this sum has no impact on the overall asymptotic value of: $$\sum\_{i=1}^{x} \frac{1}{i} \geq 1 \ .$$
> 1 votes

# Answer
You can’t add an infinite number of big-Os.

O(f(x)) is limited by f(x), multiplied by some constant c. If you have 100 Big-Os then they all have different constants, so you can just take the largest.

But with an infinite number of Big-Os, these constants could grow without any limit, so there is no single c that limits the infinite sum.

For a particular sum, if you have the actual terms, and not just big-O, then you may be able to prove some bound. For example if you can show that there is a constant c that works for all terms. But not if all you know is that each term is limited with *some* constant.
> 1 votes

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


title: Problem about $NP \neq coNP$

text:
# Question
Title: Problem about $NP \neq coNP$
I need to show that assuming $NP \neq coNP$ then there are 2 non-trivial languages $A$ and $B$ ($A,B \neq \emptyset, \Sigma^\*$) in $NP \cup coNP$ such that there's no polynomial time reduction from A to B and there's no polynomial time reduction from B to A.

I tried doing this:
Let $A$ be non-trivial language such that $A \in NP \implies \bar{A} \in coNP$, let's suppose to the contrary that there is a polynomial reduction such that $A \leq\_p \bar{A}$.
From $A \leq\_p \bar{A}$ it follows that $\bar{A} \leq\_p A$. Since $A\in NP$ we can conclude that $\bar{A} \in NP$.
Then by definition if $\bar{A} \in NP \implies A\in coNP$. Therefore $NP = coNP$. Contradiction.

I also tried picking 2 languages from $NP\cup coNP$ such that $A$ is NP-complete and $B$ is $coNP$ and to show that if one of the cases ($A \leq\_p B$ or $B \leq\_p A$) is true then it leads to a contradiction, but I got stuck showing that the case $B \leq\_p A$ where $B \in coNP$ and $A \in NP-complete$ yields contradiction.

I'll appreciate any insights, thanks.

# Answer
The first attempt is not really helpful because you can pick a nontrivial language $A\in \text{P}$ (a too easy language), and in this case, one can easily obtain a PTIME reduction from $A$ to its complement. Can you tell why? So this gives no contradiction. What you need to do is aim to the big fish, languages that are complete in NP, and those that are complete in coNP -- your second attempt.

So consider an $\text{NP-complete}$ language $A$, for example $A = SAT$, and consider its complement $\overline{A}$, which is $\text{coNP-complete}$. If by contradiction there is a PTIME reduction from $A$ to its complement, that is $A\leq\_p \overline{A}$, then the fact that $A$ is $\text{NP-hard}$ and transitivity of PTIME reductions, imply that $L \leq\_p \overline{A}$, for every language $L\in \text{NP}$. Now as $\overline{A}\in \text{coNP}$, we get that $L$ is in $\text{coNP}$ as well. So we've shown that $\text{NP}\subseteq \text{coNP}$, and thus reached a contradiction.

So what you were missing is the following standard claim:

**Claim:** If $A \leq\_p B$, and $B$ is in $\text{NP}$ ($\text{coNP}$), then $A$ is in $\text{NP}$ ($\text{coNP}$, respectively).

The intuition is that if you want to collapse one class into another, for example collapse $\text{NP}$ into $\text{coNP}$ and show that $\text{NP}\subseteq \text{coNP}$, then it is sufficient to find a problem in $\text{coNP}$ that is harder than an NP-complete problem (one of the hardest problems in $\text{NP}$).
> 2 votes

---
Tags: np-complete, polynomial-time-reductions
---


# Question
Title: NFA for the language that accepts binary strings ending with 00
This is the question:

> 1.7. Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0,1}.

> a. The language {w| w ends with 00} with three states

This is how my professor answered it:

But this is the answer I found on web:

But I think the second one should be the correct answer.

# Answer
The first answer is incorrect. The automaton does not accept, for example, the input word $0100$. In fact, the first automaton misses at least all words in the language that are not of the form $1^\*0^\*$.

The second answer is correct. It is not hard to prove it. Can you try?
> 2 votes

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


title: Graph containing a cycle of $2k$

text:
# Question
Title: Graph containing a cycle of $2k$
Given an undirected graph $G=(V,E)$, and a parameter $k\in \mathbb{N}$ such that $k\geq 2$, how can I show that if $|E|\geq |V|^{1+\frac{1}{k}}$, a cycle $C$ exists in $G$ such that $|C|\leq 2k$?

The only initial idea I have is that as $|E|\geq |V|^{1+\frac{1}{k}}$, I know that the maximal degree of a vertex is at least $|V|^\frac{1}{k}$. But I fail to see how I reach a cycle, let alone one of a specific length (at least) $2k$.

I have also been hinted that $\frac{|V|^{1+\frac{1}{k}}}{2}$ edges should suffice, but seems to be hard for me to tackle as well.

# Answer
> 2 votes
I can prove the claim for graphs with $|E| \ge |V|^{1+ 1/k} + |V|$

Let $n = |V|$ and $m=|E|$ and $D = \left\lceil n^{\frac{1}{k}} \right\rceil$. As long as $G$ contains a vertex $v$ with degree at most $D$, delete $v$. You are left with a graph $G'$ in which all vertices have degree at least $D+1$.

The graph $G'$ cannot be empty, since otherwise the number of edges in $G$ would be at most $n \cdot D \< n \cdot (n^{\frac{1}{k}} + 1) = n^{1+1/k} + n$.

Suppose towards a contradiction that $G$, and hence $G'$, contains no cycle of length at most $2k$ and let $s$ be an arbitrary vertex of $G'$. Build a BFS tree $T$ of $G'$ rooted in $s$, and recall that the depths (in $T$) of the endvertices of all non-tree edges differ by most $\pm 1$.

Then all vertices at depth at most $k-1$ in $T$ have no incident non-tree edge (since otherwise there would be a cycle of length at most $(k-1) + 1 + k = 2k$).

The root of $T$ has at least $D+1$ children, and every other vertex at depth $1, \dots, k-1$ has at least $D$ children. Hence the number of nodes of $T$ is: $$ 1 + (D+1) \sum\_{i=1}^{k} D^{i-1} = 1 + (D+1) \frac{D^k - 1}{D-1} \> D^k \ge n, $$ which is a contradiction.

---
Tags: graphs, graph-traversal
---


# Question
Title: Big O Notation, Why do we ignore everything inside the log?
Okay, so I understand implicitly why we might write `f(n) = log 3n = O(log n)` but I don't really understand why lets say `f(n) = log 3n^2 = O(log n)`. Then what am I suppose to do with `f(n) = log n!` does this also just equal O(log n)?

Or do I need to write it out explicitly like with `f(n) = 2^(2n^3 + log_2 n) = O (2^(2n^3 + log_2 n))` as none of the parts could be removed and still get the same runtime.

# Answer
By the properties of logarithms: $$\log 3 n^2 = \log 3 + \log n^2 = \log 3 + 2 \log n = O(\log n)$$ and, using $n! \le n^n$ for $n \ge 1$: $$ \log n! \le \log n^n = n \log n = O(n \log n). $$ This latter bound is asymptotically tight since $n! \ge \left( \frac{n}{3} \right)^{n/3}$: $$ \log n! \ge \log \left( \frac{n}{3} \right)^{n/3} = \frac{n \log n}{3} - \frac{n \log 3}{3} = \Omega(n \log n). $$
> 3 votes

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


# Question
Title: Visualising pseudo-tree with two parents per node
I have an algorithm that recursively connects together pairs of nodes into new nodes. It looks like the Huffman code algorithm, except that a node can be re-used after it has been part of a merge. The result is a graph where each node has two parents, but can have any amount of children.

Is there a term for such a graph? It isn't technically a tree -- and has none of the special properties of a tree -- but it does look very related to one, which makes me think someone has explored this kind of generalisation. A pseudo-tree? A multi-parent tree?

The reason I ask is because it's easy to find tree drawing software out there (e.g. ETE3, which seems like it only supports binary trees), but searching for "graph visualisation" gives way too general results (e.g. for social network analysis).

---

Example, drawn manually:

# Answer
In graph theory, a tree is is usually defined as a connected *undirected* graph with no cycles. One would also call a directed graph a tree if the underlying undirected graph is a tree. The concept of nodes having "parents" is more a technique for working with trees as data structures in computer science. For an undirected graph, the concept of a "parent" only makes sense when there is a special node, called the "root" because a tree has the special property that there is a unique path between any two nodes. Thus, each non-root node has a unique neighbor that is closer to the root, which is the "parent". This implicitly gives you a way to direct the edges: direct all edges away from the root. (You could also direct all edges towards the root). This means that rooted trees are directed graphs where every node has in-degree 1, except for the root which has in-degree 0. The term "pseudotree" is already used to mean a directed graph where every node has in-degree 1, or in the undirected case, a graph that is a tree plus one more edge.

The graphs you are describing are quite unlike trees in a graph-theoretic way, so I doubt they would have been studied has a generalization of trees. That being said, my understanding of the process by which you are creating these graphs implies that there will never be a directed cycle. These are called Directed Acyclic Graphs (DAGs for short) and are quite important in computer science. Furthermore, your graphs have the property that the in-degree of a node is at most 2. I don't know if these have been studied but the keywords that you should search for are "Directed Acyclic Graphs" and "bounded in-degree".
> 1 votes

# Answer
I am not familiar with any standard name for graphs with this property. There are many more properties that one could imagine than names.

I would suggest that you use standard graph visualization software. You should be able to find many options, with a bit more searching. See, e.g., https://en.wikipedia.org/wiki/Graph\_drawing, Graphviz, and many more.
> 0 votes

---
Tags: graphs, trees, graph-drawing
---


# Question
Title: Is the Language of all encodings of Turing Machine that at least halts on one input and outputs 0 semi-decidable?
I need to prove if the following Language is or is not semi-decidable. **A := {w ∈ {0,1}^\* | there exists an input x on which M\_w produces the output 0}** Where A is the language of all the encoding w ∈ {0,1}^\* of all Turing machines which at least halts on at least one input x (might also accept it) and produce the output 0.

In my opinion, this language is **semi-decidable** because to me, it looks like a modified version of the **Halting problem**. My way of showing that this language is semi-decidable would be by using a Universal Turing machine which takes an input of the form w#x where w is the encoding of a TM and x the inputs that M\_w take. The problem is I am not really sure if I am on the right track, the language is semi-decidable at all, and also not really sure if the Universal Turing machine is the right way to show the A semi-decidable is. I really do not have any experience working with Universal Turing machines, saw only 1 or 2 problems online using it. How can I prove it?

Extra question: Am I wrong for thinking that this language is Undecidable? We can prove it by many to one reduction of the Halting problem on the empty string(which is undecidable) to the Language A.

# Answer
Since it seems like you are really uncertain about your own solution. Let's verify it step by step:

1- A is undecidable.

To prove this statement, it is enought to show that there is a mapping reduction from the following set to A:

Halt = { | M is a Turing machine which halts on }

For any Turing machine M, we define M' as:

For input w:

1- Run M on .

2- Give 0 as output.

It is pretty clear that M' belongs to A if and only if M belongs to Halt.

By undecidability of Halt, A is also undecidable.

2- A is semi-decidable.

To prove this. Consider the following set:

AMAI = {\<M,w,s\> | M,w and s belong to N}

We can make an enumerater to enumerate all members of AMAI. We use this enumerater to enumerate A as well:

For each \<M,w,s\>:

1- Run M on w by s computational steps of M.

2- If M halts on w in at most s computational steps and M gives 0 as output, print \<M,w\>.

So A is semi-decidable.
> 1 votes

---
Tags: computability, reductions, undecidability, halting-problem, semi-decidability
---


# Question
Title: How to check for correct order in a fill-in-the-blanks exercise
Suppose the following fill-in-the-blanks exercise:

\___ \___ and \___ \___ went to the \___.

Suppose the correct solution here is "John Smith and Mike Jones went to the pub". In other words: `[John, Smith, Mike, Jones, pub]`.

But the following alternate solution should count as well - the persons are swapped but they are the correct people: `[Mike, Jones, John, Smith, pub]`. But, this next one definitely should *not* count as correct: `[Mike, Smith, John, Jones, pub]` because the names and surnames are mixed up.

OK. In order to make this work, I could hard-code two alternate orderings like so, and check the answers provided against them:

```
[
    [John, Smith, Mike, Jones, pub],
    [Mike, Jones, John, Smith, pub]
]

```

but this does not scale well. What if the sentence gets longer and their names and surnames appear again? What if another person joins? The number of combinations would grow quickly.

How should I approach this problem?

# Answer
We could use `[[John, Smith], [Mike, Jones], pub]`. Therefore, we know `[John, Smith]` should be treated as one, as well as `[Mike, Jones]`.

We would also know to only use these where there are two blanks in a row, when they obey part of speech rules, and not to reverse the order.
> 0 votes

---
Tags: algorithms
---


# Question
Title: fast estimation of the amount of unique combinations
Let's say I have a set of two columns - Name, Surname. I have a list of possible values for

* *Name* -\> Jacob, John
* *Surname* -\> Mayerson, Kindle.

I want to generate a set of unique combinations for columns Name and Surname. The result looks like this.

```
--------------------
| Jacob | Mayerson |
| Jacob | Kindle   |
| John  | Mayerson |
| John  | Kindle   |
--------------------

```

The way I currently do that is I generate a pair of (name, surname), put it into a set and if the size of the set increases, it means that the combination is unique and thus I can go and generate the next one. If I generate the combination and it does not increase the size of the set, then I try to generate the next combination until it increases the size of the set.

If user asks for 10 unique rows, then it is obviously impossible to generate 10 unique combinations from the available set of values. But in order tell the user that, right now I am making `num_of_requested_rows * 2` attempts to generate a unique combination, before I notify the user that it is impossible to generate the requested amount of rows.

It can be time consuming, because user might wait for minutes before being notified that it is impossible to generate the requested amount of rows.

*Thus I have been wondering if there is some more effective way for the generator to fail fast - before even it tries to generate the unique combinations.*

I know it is possible to calculate the amount of all possible combinations (permutations basically) using factorials. But the problem is that I can have not just two columns, but three, four, five etc. columns with the potential value set ranging from 10 to thousands of values. For example I can have an integer range from 1 to 100m and so on, while also having a combination with a column that has just a hundred of possible values. And calculating the factorial for such case is also a resource heavy operation.

So my question is - it is even possible to do? Or I have no choice but to use my current approach?

# Answer
> 0 votes
Let $n$ be the number of unique names, and $m$ be the number of unique surnames. Since we have $n$ unique names, and each of them may choose $m$ unique surnames, we will have $nm$ unique name-surname combinations.

---
Tags: algorithms, combinatorics, python
---


# Question
Title: Diffucuty in understanding code after a recursive call
This is an example algorithm of a recursive insertion sort I'm trying to understand. I've have tried understanding this with the help of print statements (which I've commented).

```
def ins_sort_rec(seq, i):
    if i == 0:
        return
    # print(f"{'    ' * i} starting at depth {i}")
    ins_sort_rec(seq, i-1)
    j = i

    while j > 0 and seq[j-1] > seq[j]:
        seq[j-1], seq[j] = seq[j], seq[j-1]
        j -= 1
    # print(f"{'    ' * i} ending at depth {i}")

```

ins\_sort\_rec(\[3, 1, 2, 18, 14, 7\], 5)

The print statements have given an output like so:

```
                 starting at depth 5
             starting at depth 4
         starting at depth 3
     starting at depth 2
 starting at depth 1
 ending at depth 1
     ending at depth 2
         ending at depth 3
             ending at depth 4
                 ending at depth 5

```

The problem I'm facing is visualizing the call stack. Doesn't it again call recursively again when the function is called from the call stack and when is the code after it executed.

Btw I'm self learner just getting started with data structures and algorithms and finding it difficult to understand recursive call (within a recursive call, as I see it).

Any advice that'll put me in the right direction for understanding recursive calls, especially if there is code after a recursive call will be truly appreciated.

# Answer
> 0 votes
Insertion sort relies on the previous $i-1$ elements to sort the $i$-th element. In your recursive algorithm, it starts at $5$th element, but it relies on the previous $5-1$ elements, going all the way to the first, which we can trivially sort by doing nothing, then going back up to the $5$th element again.

---
Tags: algorithms, sorting, recursion, python
---


title: Shortest algorithm

text:
# Question
Title: Shortest algorithm
Suppose I write an algorithm to perform a computation but I get the intuition that my algorithm is a bit too long, however, it is not immediately obvious to me what a shorter algorithm might be. Is there a way for me to prove the (non-)existence of a shorter algorithm that performs that task - *without* necessarily having to write out the shorter algorithm (if it exists)?

# Answer
The algorithm is not asymptotically solved when we have not found the tight bound, i.e. the lower bound being equal to the upper bound. It is possible to solve this asymptotically for most algorithm, but absolute shortest algorithm is undecidable according to Rice's theorem.

Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a syntactic property (for instance, does the program contain an if-then-else statement). A property is non-trivial if it is neither true for every program, nor false for every program.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Is my mathematical representation of search in binary search tree correct?
You are given the `root` of a binary search tree (BST) and an integer `val`.

Find the node in the BST that the node's value equals `val` and return the subtree rooted with that node. If such a node does not exist, return `null`.

I have came up with a recursive solution in python, but I also want to document down the mathematical representation. I came up with the following, am I correct notation wise?

$$ f(v, x) = \begin{cases} \emptyset & \text{if } v = \emptyset \\ f\Big(\ell(v), x\Big) & \text{if } g(v) \> x \\ f\Big(r(v), x\Big) & \text{if } g(v) \< x \\ v & \text{otherwise} \end{cases} $$

where

* $\emptyset$ is the empty tree, or `None` in Python
* $v$ is a node in the tree
* $\ell(v)$ is the left child of $v$
* $r(v)$ is the right child of $v$
* $g(v)$ is the value of node $v$, and $x$ is the target value to search for.

In this formulation, the function $f$ takes two arguments: a node $v$ and a target value $x$. The function $\ell(v)$ returns the left child of the node $v$ and $r(v)$ returns the right child. Depending on the comparison of the value of node $v$ and the target $x$, the function $f$ recursively calls itself on either the left child or the right child of $v$. If $v$ is empty, it returns $\emptyset$. If the value of node $v$ equals the target $x$, it returns $v$ itself. This function could be seen as a search algorithm on a binary tree.

# Answer
> 0 votes
It is correct, but it could be made more readable.

$$ search(node, val) = \begin{cases} \emptyset & \text{if } node = \emptyset \\ search(node.left, val) & \text{if } node.val \> val \\ search(node.right, val) & \text{if } node.val \< val \\ node & \text{otherwise} \end{cases} $$

---
Tags: algorithms, data-structures, trees, recurrence-relation, recursion
---


# Question
Title: Prove that determining if a PDA has an infinite language is decidable
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser): Given $$\text{INFINITE}\_{\text{PDA}} =\\{\langle M\rangle \mid M\text{ is a PDA }\text{and L(M) is infinite}\\}$$

Prove that $\text{INFINITE}\_{\text{PDA}}$ is decidable.

The following is my solution:

```
On input <M>:
1. Repeat until there are transitions:
   a. Mark current state and delete the transition that moved you to the state
   b. If an already marked state is reached, accept
2. If no other transition exists, reject

```

Can this be considered a valid solution? I think the fact that we are checking if a cycle exists in the PDA is sufficient to prove that the language is infinite am I correct? I believe there could be a PDA that has a loop in a non-accepting branch of the computation and my algorithm would still say it has an infinite language which is wrong, am I correct?

# Answer
I'm not sure whether I understood your solution right. Here is my suggestion:

For code of M:

1- Find all paths from start state to an accept state which every state occurs only once.

2- Check whether in states that occurs in paths, There are states that are connected together with a path which doesn't appear in the main path from start state to accept state?

If there are, accept. OTHERWISE, reject.

With this algorithm, If the language is infinite, Then there are definitely states and strings that transition function allows a loop with them. If it doesn't, Since M has finite number of states, There are only finitely many strings which are accepted by M.

Also since we just look for paths from start state to accept stats that each state appears at most once, We won't have any loop in performance of this algorithm. Because there are only finite paths that satisfy this requirement.
> 1 votes

---
Tags: turing-machines, computability, context-free, decidability
---


title: Decidability terms clarification

text:
# Question
Title: Decidability terms clarification
I just need some clarification regarding the different terms we use in theoretical computer science, especially regarding decidability.

1. **Decidable:** A language $L$ (a set of strings) is decidable if there exists a Turing machine $M$ that, for any input string $w$, halts on w and correctly decides whether $w$ belongs to $L$ or not. In other words, for any input $w$, $M$ will either accept or reject $w$, and it will always provide a definite answer in a finite amount of time.
2. **Semi-decidable:** A language $L$ is semi-decidable if there exists a Turing machine $M$ that, for any input string $w$, halts and accepts $w$ if w belongs to $L$. However, if $w$ does not belong to $L$, $M$ may run forever without halting, or it may reject $w$. In other words, it can recognize members of $L$, but it may not necessarily reject non-members.
3. **Undecidable:** A language $L$ is undecidable if there is no Turing machine that can decide whether any given input string $w$ belongs to $L$ or not. In other words, there is no algorithm that can always provide a correct yes-or-no answer for membership in $L$.
4. **Not semi-decidable:** This term refers to languages or problems for which there is no Turing machine that can recognize all members of the language, meaning there is no Turing machine that will halt and accept all strings in the language, and some strings in the language may cause the machine to run forever without halting.
5. **Not decidable:** Is this the same as undecidable? Or does it specifically imply that it is not decidable but we cannot make a statement on whether a language $L$ is semi-decidable or not.

The main issue I have is the difference between undecidable and not decidable languages. For example, we have the special Halting Problem: $$K := \\{w ∈ \\{0, 1\\}^∗| w\\#w ∈ H\\}$$ where $H$ is the general Halting Problem. Now the problem is that we know that $K$ is undecidable. Is it the same as saying that $K$ is not decidable?

This problem might seem basic, but because both terms are used I would appreciate some clarification on this.

# Answer
Undecidable means "not decidable". They are synonyms. The definition is: we say that $L$ is undecidable if $L$ is not decidable.
> 1 votes

---
Tags: turing-machines, undecidability, decision-problem, halting-problem, semi-decidability
---


# Question
Title: Proof that the K coloring problem is weakly or strong NP-complete?
As far as I know, the K coloring problem is NP-complete. However, I'm a bit confused about how to determine whether a problem is weakly or strongly NP-complete.

* If an NP-complete problem is decidable by a pseudo-polynomial time algorithm, it is called weakly NP-complete.
* If an NP-complete problem's unary version is NP-complete, then it is called strongly NP-complete.

**Is there a straightforward proof that the K coloring problem is weakly or strong NP-complete?**

# Answer
There are no obvious integers involved in an instance of the $K$-coloring problem (where $K$ is part of the problem and not of the input).

The length of the encoding of an instance of $K$-coloring is the length of the encoding of the graph. The standard reduction from 3-SAT shows that the problem is (strongly) NP-complete.

Even if $K$ were part of the input, this would have no effect on the asymptotic size of the encoding of the input (since only $K \le n$ makes sense, where $n$ is the number of nodes of the graph).
> 1 votes

---
Tags: complexity-theory, graphs, np-complete, colorings, pseudo-polynomial
---


# Question
Title: Is it possible to find reductions from problems in $\mathsf{NP}$ to SAT based solely on the certificate verification algorithm?
The following problem has made me ask this question:

> Given a boolean formula $\varphi(X)$ decide if there exists a quantification of $\varphi(X)$ with $k$ $\forall$ quantifiers that holds true. Assume that $k$ is bounded with $\mathcal O(\log n)$.

To clarify, the order of the quantifiers is arbitrary. I.e. the resulting formula is of the form $Q\_{a\_1}x\_{b\_1}\ Q\_{a\_2}x\_{b\_2}\cdots Q\_{a\_n}x\_{b\_n}:\varphi(x\_1,x\_2,\cdots,x\_n)$ where each $Q$ is either $\exists$ or $\forall$, and there is no connection between $a\_i$ and $b\_j$ for any $i,j$.

This problem is clearly in $\mathsf{NP}$: first the proof would show the QBF with $k$ $\forall$-quantified variables, then it would expand it into an unquantified formula with at most polynomial ($2^k$) blowup and show that this new formula is satisfiable.

However, in the worst case there are $\omega(poly(n)\cdot n^{\log n})$ candidate quantifications of $\varphi(X)$ and therefore it seems non-trivial to find a poly-time reduction.

But maybe there is an easier method? Is it possible to find a poly-time reduction to SAT based solely on the proof verification algorithm?

# Answer
Finding a reduction to SAT is easy but tedious. Write down a description of polynomial-time Turing machine $T$ that checks the certificate (as you have argued in your question, such a Turing machine exists), then encode $T$ into a SAT formula $\psi$ that has a variable for each input symbol of the certificate (plus additional variables as needed) such that $\psi$ admits a satisfying assignment iff there is a way to chose the symbols of the certificate and a corresponding valid computation path that causes $T$ to accept.

This can be done following the construction used by the proof of the Cook–Levin theorem.
> 1 votes

---
Tags: reductions, np, satisfiability, polynomial-time, polynomial-time-reductions
---