# Question
Title: Why does the reduction from 3SAT to IS work?
I was reading about the reduction from *3SAT* (input: formula) to *Independent set* (input (graph, k)) in order to prove that the latter is in NP-Complete. The reduction i've seen follow the next steps:

1. For each clause at the input, create a node for every variable it contains in case it doesn't exist yet. Then, create a $K\_3$ with these nodes.
2. Create an edge between a node and its negation.

An example i found:

While proving this reduction is correct, they say:

> $\Rightarrow$) If the formula is satisfiable, there is at least one true literal in each clause. Let S be a set of one such true literal from each clause. |S| = k and no two nodes in S are connected by an edge.

I don't understand why this works. I mean, $k$ is fixed at this point (from the input) so if $k=3$ i can take $S=\\{x\_1, x\_3, x\_4\\}$. If $k=2$ i can take $S=\\{x\_2, x\_4\\}$ but if $k=1$ i can't.

Could you explain me why this works or if i am not understanding anything correctly? Thanks.

# Answer
> 4 votes
The $\Rightarrow$ implication means that you need to prove that if the given $3SAT$ formula is satisfiable then there is a maximum IS.

So assume that the formula is satisfiable.

Since the formula is satisfiable each clause has at least one literal (it may be $x\_1$ or $\overline{x}\_1$ for instance). Now I claim that according to the structure of the graph the maximum IS must have $k$ nodes where $k$ is the number of clauses.

Why?

Because each clause corresponds to a single triangle $K\_3$, and hence you can choose only one node from each triangle, where you have exactly $k$ triangles (any two nodes in the $K\_3$ are not independent - they are connected by an edge).

But which node do we choose from each gadget/triangle?

You choose those literals which are true. These literals form independent set. Indeed, if two true literals belong to different triangles then they are not connected by an edge since only $x\_i$ and $\overline{x}\_i$ may be connected by an edge. But $x\_i$ and $\overline{x}\_i$ cannot be true at the same time (remember that our IS $S$ contains only true literals).

So we have exactly $k$ nodes/true literals which indeed forms a maximum IS. Therefore if the formula is satisfiable then the graph has a maximum IS.

You also need to prove the opposite, namely, if the graph has a maximum IS then the formula is satisfiable. I think you could prove it yourself.

---
Tags: complexity-theory, reductions, 3-sat
---


title: Reduction problem to another problem

text:
# Question
Title: Reduction problem to another problem
I would like to show that a problem $A$ is $NP\text{-complete}$. So, I am trying to reduce 3-SAT problem to $A$. Reduction is kind of function, let say $f$. What is necessary complexity of $f$? Probably, it has be in $NP$. But, does it mean that $f$ must be a non-deterministic Turing machine working in polynomial time?

# Answer
> 3 votes
No, $f$ need not be a NDTM. To prove a problem is NP-complete by reducing another NP-complete problem to it requires only a Karp reduction, which is a polynomial-time deterministic reduction. So $f$ would live in the complexity class FP.

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


title: Identifying class of language

text:
# Question
Title: Identifying class of language
Let L1 be the recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

a.) L2−L1 is recursively enumerable.

b.)L1−L3is recursively enumerable.

c.)L2∩L3is recursively enumerable.

d.)L2∪L3is recursively enumerable.

***My approach:-*** I am able to falsify a,c and d option. Now for b option i took one example where my L1 is universal language so when i do L1-L3,i get the $L3^c$(L3 complement).So complement of RE but Not REC is NOT RE always.So it is not required that L1-L3 will be RE. But on the other hand if i solve b option as follow:-

```
L1-L3

```

= L1 ∩ $(L3)^c$

= REC ∩ $(RE but Not REC)^c$

=REC ∩ NOT RE

So the final expression will give me empty language and it is regular.Is it possible for the final expression to have non empty set above?

# Answer
> 3 votes
The intersection of a recursive language and a non-RE language isn't necessarily empty. Take the recursive langauge to be $\Sigma^\*$, as you've already done once.

---
Tags: turing-machines
---


# Question
Title: Difference in scale between mean page loading times and exponentially distributed page loading times?
Apologies if this is the wrong place to ask.

For my experiment, I have a single-page application and a multi-page application. I am testing them with an exponential distributed delay throttling. The idea is that individual chunks are delayed by a random number sampled from an exponential distribution. So, when a HTTP/GET request comes in, it gets split into 200 byte chunks and each chunk is delayed. Basically each request for a resource e.g. HTML/CSS/JS is a sum of exponential distributed delays.

Now, when I did a test of a 100 page loads and got the mean.

My question is why is the SPA vs MPA without delay, SPA is around 4 times faster but then SPA vs MPA with delay is only 2 times faster?

**No delay:**

**With delay:**

**Edit**: The mean exponential parameter is 1 (second). The multi-page app total size transferred is significantly smaller (58KB), than single-page app (267KB) which due to the JavaScript framework, so it is expected to load faster. SPA also has more files to download, therefore more round-trips.

To do a simulation:

1. User visits a website from his browser, he makes a HTTP request for the root HTML first, which makes subsequent requests for style sheets and scripts to load the page.
2. Taking the first request for the root HTML, (for specific details) this TCP stream is fed into a SOCKS server before going out to the web server. The stream takes 200 byte chunks at a time and delays it, (and without blocking) keeps taking another chunk and delays it. It also checks if any previous chunk will overlap, if so it will send it out the same time.
3. The web server gets the delayed request and sends a reply back (in this case the HTML file) to the SOCKS server, where it will delay it again.

At step 2, say we have a 1000 byte stream, it will take 200 byte and delay it in the background, take another 200 byte and delay that in the background too, and keep doing it. Meanwhile it will check overlaps, so if the first chunk has a delay (plus current time) that is greater than the delay (plus current time) of the second, meaning the second will get sent first. We want to delay the second chunk the same time, so it gets sent in order.

I hope that makes sense. Please let me know if it doesn't.

# Answer
The time to load a web application is a sum of multiple factors, including at least:

* The round-trip latency to initiate a TCP connection to the server (or maybe multiple connections, depending on your application and your browser) -- also called RTT time.
* The time to download all of the page and content that it causes to be downloaded.

The second factor depends on the amount of delay you're adding; the first doesn't. Also, the multi-page application might cause more TCP connections, causing more of the first type of delay; but it downloads less data, so less of the second delay.

So there's no reason to expect things to scale as simply as you are expecting. Instead, the resulting performance will be a more complicated function of page size, RTT time, and delay.

Heuristically, we can expect a RTT time of a few hundred milliseconds per TCP connection, though that will depend on how far the client is from the server. You say there's an average delay of 1 second per 200 bytes downloaded, so for the single-page application, you expect 267KB / 200bytes = 1367 seconds of delay added, on average, due to your artificial delays; for the multi-page application, you expect 58KB / 200bytes = 297 seconds of delay added, on average. Without the artificial delays, the time to download that much data might depend on the speed of your network.
> 1 votes

---
Tags: randomness, performance, experimental-analysis
---


# Question
Title: Can Chomsky Normal Form have more than one terminal?
In formal language theory, a context-free grammar G is said to be in Chomsky normal form if $$ S → A B$$ $$ A → a $$ $$S → ε $$

My question is that if $B$ in the the form of $$ B → abcd $$

where $abcd$ are terminal symbol, is this still in Chomsky Normal Form? ?

# Answer
The above given CFG cannot be in Chomsky Normal Form since the production B→abcd has multiple terminals on left hand side of the production. In order to convert the given CFG to Chomsky Normal Form, will need to replace the terminals on lhs of production B→abcd as follows - B-\>abcd B-\>FG F-\>AE G-\>CD E-\>b C-\>c D-\>d.
> 2 votes

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


# Question
Title: implementing permutation and combination recursively
I am still in the early phase of getting comfortable with solving recursive problems. I was given
`int p(int n) // number of permutations of n objects`
`int c(int n, int k) // number of unique combinations of k elements out of n elemnts`

For instance, {"abc"} as the given string, permutation will be {"abc"}, {"acb"}, {"bac"}, {"bca"}, {"cab"}, {"cba"}. However, combination (order does not matter) will be just simply {"abc"}.

A detail representation of Combination by using Pascal's Triangle from Eric Roberts' book.

I am having a hard time seeing how this pascal's triangle representation relate to the idea of combination.

My initial thought process was based on each of their formulae and using factorial to solve the problem. Clearly, that's not what I was asked to do. I was supposed to define them recursively and implement the recursive definitions for both counting techniques. So, basically, I am unable to solve the two functions without getting the help of factorial.

# Answer
The number of permutations of $n$ distinct objects is $n!$. The number of $k$ selections out of $n$ distinct objects is $\binom{n}{k}$ known also as a binomial coefficient. Recursive definition of these numbers are trivial: $$n! = n(n-1)!$$ $$\text{so if } f(n) = n! \text{ then } f(n) = n\times f(n-1), f(0) = 1$$ For binomial coefficients $${\binom {n}{k}}={\binom{n-1}{k-1}}+{\binom{n-1}{k}}$$ or $$ b(n,k) = b(n-1, k-1)+b(n-1, k)$$ where $$b(n,n)=1 = b(n,0)=1 \text{ and } b(n,k)=0 \text{ for } n \< k$$

If you want approximate value without too much computation then you may check the Stirling's approximation.

---

Proof of $${\binom {n}{k}}={\binom{n-1}{k-1}}+{\binom{n-1}{k}}$$ You can prove it using a combinatorial argument or algebraic. The algebraic one is tedious (you need to manipulate factorials). So let's consider a combinatorial proof.

Assume we have $n$ people, numbered from $1$ to $n$, and want to create a team consisting of $k$ people. There are exactly ${\binom {n}{k}}$ ways to create a team, i.e, $k$ people out of total $n$. Consider the first member, number $1$. There are two possibilities: either include her or leave her out.

* If we choose that member then we need to choose additional $k-1$ people out of remaining $n-1$ people which is equal to $\binom{n-1}{k-1}$.
* If we leave that member out then we have to select $k$ out of $n-1$ people which equal to $\binom{n-1}{k}$.

Since these both options result in different teams the total number of teams is $$\binom{n-1}{k-1} + \binom{n-1}{k} $$
> 1 votes

---
Tags: algorithms
---


# Question
Title: Domino tiling of a 2xN rectangle in O(ln n)
I solved this problem using Dynamic Programming in $\mathcal{O}(n)$ time. I found that is equivalent to the Fibonacci Numbers.

$F(0) = F(1) = 1$

$F(n) = F(n-1)+F(n-2)$

Where the $F(n-1)$ term is from fixing the left most domino vertically, and the $F(n-2)$ from fixing it horizontally (which implies that the domino under it must also placed horizontally).

Because the Fibonacci Numbers can be generated in $\mathcal{O}(\lg n)$ using

$F(2n) = F(n)F(n+1)+F(n-1)F(n)$

$F(2n+1) = F(n)F(n)+F(n-1)F(n-1)$

Then I try to find the same expression from the domino tiling. Again, I classify all possible tilings in two set. First, all tiling like the one below  Therefore, $F\_H(n) = F(i)F(n-i-2)$. Because I want to split in the middle (or close) I consider $n=2k, i=k$ and $n=2k+1, i=k$. Then

$F\_H(2k) = F(k)F(2k-k-2) = F(k)F(k-2)$ and $F\_H(2k+1) = F(k)F(2k+1-k-2) = F(k)F(k-1)$.

Then, all tiling of the form  Again, $F\_V(n) = F(i)F(n-i-1)$ and when $n=2k, i=k$ and $n=2k+1, i=k$ we have

$F\_V(2k) = F(k)F(2k-k-1) = F(k)F(k-1)$ and $F\_V(2k+1) = F(k)F(2k+1-k-1) = F(k)F(k)$

Combining all the former expressions,

$F(2k) = F\_H(2k) + F\_V(2k) = F(k)F(k-2) + F(k)F(k-1)$

$F(2k+1) = F\_H(2k+1) + F\_H(2k+1) = F(k)F(k-1) + F(k)F(k)$

However, those final expression **does not produce the same numbers**. Because they look really similar I belive my approach is not completly wrong but I can not find where I make my mistake.

## Final notes:

1. In the first classification, I fix the top most domino horizontally and if I consider a 1-tile shifted horizontal domino (left or right) under it, then the rectangle can not be tiled.
2. For the (correct) expression $F(2n+1)=F(n)F(n)+F(n-1)F(n-1)$, notice that $F(n)F(n)$ can be mapped to the second case, because $n+1+n = 2n+1$, but the other term $F(n-1)F(n-1)$ can not (at least in the same way), $(n-1)+2+(n-1)\neq 2n+1$. The same can be notice in $F(2n)$ and again one term can be mapped to the second case while the other can not (to the first case). I belive my mistake should be around the first case.

# Answer
In your second attempt you tried to fixate the $(k+1)$th term. But instead of the two cases

```
1 2 ... k k+1 k+2 ... n
           |
           |

```

and

```
1 2 ... k k+1 k+2 ... n
           -----
           -----

```

there exist a third case:

```
1 2 ... k k+1 k+2 ... n
        ----
        ----

```

So if $n = 2 k$, then you have $f(k)f(k-1)$ for the first case, $f(k)f(k-2)$ for the second one, and $f(k-1)f(k-1)$ for the third one. This gives in total:

$f(2k) = f(k)f(k-1) + f(k)f(k-2) + f(k-1)f(k-1) = f(k)\[f(k-1) + f(k-2)\] + f(k-1)f(k-1) = f(k)^2 + f(k-1)^2$.

Now this formula looks like the formula for $F(2n+1)$ that you posted.

> Because the Fibonacci Numbers can be generated in O(lgn) using
>
> F(2n)=F(n)F(n+1)+F(n−1)F(n)
>
> F(2n+1)=F(n)F(n)+F(n−1)F(n−1)

Simple reason: the formula assumes that $F(1) = F(2) = 1$ while you have $f(0) = f(1) = 1$. So after an index shift it should match.

Identical procedure for the odd case $n = 2k + 1$.

---

edit: Tried to do the index shift but failed. Reason was, that you wrote down the wrong formula for $F(2n+1)$. It should be $F(2n+1)=F(n)^2+F(n+1)^2$. Then the index shift works:

$f(2k) = F(2k+1) = F(k)^2+F(k+1)^2 = f(k-1)^2 + f(k)^2$.
> 3 votes

---
Tags: dynamic-programming, tiling
---


# Question
Title: About independent set in triangle free graphs
From Wikipedia :

> An independent set of $\sqrt{n}$ vertices in an $n$-vertex triangle-free graph is easy to find: either there is a vertex with more than $\sqrt{n}$ neighbors (in which case those neighbors are an independent set) or all vertices have less than $\sqrt{n}$ neighbors (in which case any maximal independent set must have at least $\sqrt{n}$ vertices)

Why does any maximal stable set have at least square root of $n$ vertices?

Thanks.

# Answer
> 2 votes
The point is that the graph is triangle free, so if $j$ and $k$ are both neighbours of $i$, then the edge $\\{j,k\\}$ is not in the graph. This means that $N\_i = \\{j : \text{$i$ is a neighbour of $j$}\\}$ is an independent set for any $i$.

The other fact being used is that a graph with $n$ vertices of maximum degree $\Delta$ has an independent set of size at least $\lfloor n/(\Delta+1)\rfloor$.

---
Tags: graphs
---


# Question
Title: A recursive solution to the all-pairs shortest-paths problem
I am learning All pair Shortest Path from CLRS book,but got stuck in the begining itself.I am writing my query.

According to one of the **Lemma** of shortest path -:

> All Subpaths of shortest path are shortest.

Using this lemma, we can write the **Structure of shortest path** given as-:

> Consider a shortest path $p$ from vertex $i$ to $j$ and suppose that $p$ contains atmost $m$ edges.We can decompose path $p$ into subpath $p^{'}$ i.e $ik\\,\\,(\\,\\,i\rightarrow\\,\rightarrow k )$ and one edge $(k\rightarrow j)$ From the lemma it is clear that subpath $p^{'}$is also shortest and $p^{'}$ contains atmost $m-1$ edges. so we can write as
>
> > $\delta\\,(i,j)=\delta\\,(i,k)+w(k,j)\label{eqn:1} $

where $\delta\\,(i,j)$=shortest path weight from $i$ to $j$

Allright!!!! I am Ok till here.

Now the Author has wriiten the **recursive solution to all pair shortest path** which too makes sense to me .It is given by-:

> $L\_{i,j}^{m}$=**Minimum weight of any path from vertex $i$ to vertex$j$ that contains atmost $m$ edges.**
>
> > $L\_{i,j}^{m}$=$min\_{(1\\,\leq k \leq n)}$$\\,\\,(L\_{i,k}^{m-1}\\,\\,+w(k,j)\\,\\,)$ $\\,\\,\\,(1)$

Here $k$ is used to find out all the **predecessors** of $j$.

I am still ok here,but i am stuck in the following point.

> If the graph contains no negative-weight cycles, then for every pair of vertices $i$ and $j$ for which $\delta(i,j)\leq \infty$(i.e **connected**)there is a shortest path from $i$ to $j$ that is simple and thus contains at most $n-1$ edges.A path from vertex $i$ to vertex $j$ with more than $n-1$ edge cannot have lower weight than a shortest path from $i$ to $j$ . The actual shortest path is given by

$\delta(i,j)=L\_{i,j}^{n-1}=L\_{i,j}^{n}=L\_{i,j}^{n+1}.... (2)$

I am not getting relation between this statment$((1)\\,\\,and\\,\\,(2)\\,)$ .Please help me out to derive this.

# Answer
> 3 votes
(1) tells you how to compute the shortest path.

Note that **given that the graph has no negative-weight edge**, the shortest path between two nodes is a simple path (with no cycles) which has at most $n-1$ edges. More than $n-1$ edges means a cycle which increases the path length. But we are interested in the shortest path.

(2) claims that after $n-1$ edges the shortest path length remains same: $L\_{i,j}^{n-1}=L\_{i,j}^{n}$ is read as "the shortest path from $i$ to $j$ passing through $n-1$ edges is the same as the shortest path through $n$ edges".

In fact it means that there is no need to compute $L\_{i,j}^{n},L\_{i,j}^{n+1},\dots$ since it will not lower the path between $i$ and $j$.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Generating numbers to be averaged efficiently
During my research, I had encountered the following issue. Consider the equation $$\sum\_{k=1}^K\alpha\_k P\_k = P$$

where $\sum\_{k=1}^K\alpha\_k=1$, $\alpha\_k \> 0$, $P\_k \> 0, P\>0$.

So you are given $\\{\alpha\_k\\}$, $K$ and $P$. The task is to generate randomly $\\{P\_k\\}$ such that the above equation is satisfied. I am looking for an efficient way to generate these numbers.

**My strategy**

I have one method. Basically, we generate $K$ distinct uniform numbers between $(0,1)$. Call them $\\{b\_k\\}$. Then we compute $\sum\_{k=1}^K\alpha\_k b\_k = B$. Now the sequence $\\{\frac{b\_kP}{B}\\}$ is the desired sequence.

However, if you observe, using this method, $P\_k$ can never exceed $P$ and in my work, I require some of the values to exceed $P$. E.g. if $\alpha\_1=0.5, \alpha\_2=0.5$, even $(2P,0)$ is a valid solution.

Is there a way to generate these numbers so as to circumvent this issue?

**Update:** Given $\\{\alpha\_k\\}$, it follows that $P\_k \leq P/\alpha\_{\min}$. Note: The above counter example is not valid. Apparently the algorithm works fine.

# Answer
A reasonable solution is to first generate a random point in the simplex $$ x\_1 + \cdots + x\_K = 1, \qquad x\_1,\ldots,x\_n \geq 0. $$ Check out this question for several ways to do this. Then take $$ P\_i = \frac{P}{\alpha\_i} x\_i. $$ This should give you a uniformly random point in the geometric body you are interested in $$ \sum\_{i=1}^K \alpha\_i P\_i = P. $$
> 2 votes

---
Tags: algorithms, pseudo-random-generators
---


# Question
Title: Simulating DFA operations on non-regular languages with finite final state set
A language I'm investigating is not regular since the minimal DFA for the language grows depending on input string size. However, while the number of non-final states increases, the final states are the same small strictly finite core which include the initial state.

Another question looks superficially similar, hinting that what I'm looking for might be an interpretation of this language as a generalization of a prefix-code in order to ignore the infinite non-final states.

Are there methods to treat this 'pseudo-regular' language as regular (or any other language class with efficient algorithms) for purposes of intersection and path finding from the small final state set back to the inital state, thus sidestepping the issue that the complete DFA is not finite in size?

# Answer
Your question is missing quite a few definition, but here is my interpretation.

> A language $L \subseteq \Sigma^\*$ is *finite-regular* if there exists $C$ such that for all $n$, $L \cap \Sigma^n$ is accepted by some DFA with at most $C$ final states.

Note that if the minimal DFA for a language has $m$ accepting states, then *every* DFA for the language has at least $m$ accepting states (this follows from Myhill–Nerode theory). Therefore we obtain an equivalent definition if we replace "some DFA" with "the minimal DFA".

Using the product construction, you can easily show that the class of finite-regular languages is closed under union and intersection, and more generally under monotone set operations.
> 1 votes

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


# Question
Title: Globally-optimized nearest neighbors lookup
I have a set $\mathcal{A}$ of $\mathcal{m}$ vectors in $\mathbb{R}^a$. I also have a different set $\mathcal{B}$ of $\mathcal{n}$ vectors in $\mathbb{R}^a$. These two sets are disjoint: $\mathcal{A}\cap\mathcal{B} = \varnothing$.

My goal is to find a set $\mathcal{C}$ such that $\mathcal{C} \subset \mathcal{A}$ and $\vert\mathcal{C}\vert = \vert\mathcal{B}\vert$, that minimizes the sum $$ \sum\limits\_{j}\Delta(\mathcal{C}\_{j}, \mathcal{B}\_{j}) $$ where $\Delta$ is some distance metric. All elements of $\mathcal{C}$ must be unique, and there are no restrictions on the ordering of sets $\mathcal{B}$ or $\mathcal{C}$ in the calculation of the above formula. The crucial challenge here is that we can't match two different points of $\mathcal{B}$ to the same point of $\mathcal{A}$, so you can't just assign each point of $\mathcal{B}$ to its nearest neighbor in $\mathcal{A}$.

1. Is this equivalent to an already-studied problem? If so, which problem?
2. Assuming the answer to 1 is yes, are there better approaches than the greedy one?

Answer to 2 is optional, I can do the research myself, just having difficulty nailing down an equivalent problem.

# Answer
Here's one approach -- not necessarily the fastest. This can be viewed as an instance of the assignment problem, or equivalently, finding a minimum weight perfect matching of a bipartite graph. Imagine a bipartite graph with $\mathcal{A}$ being the set of vertices on the left, $\mathcal{B}$ being the set of vertices on the right, and an edge between every pair of vertices whose weight is equal to the distance between those points. Now you are looking for a perfect matching of minimum weight. Once the graph is built, there are standard algorithms for this, such as the Hungarian algorithm or linear programming.

The first step in such an approach is to compute all-pairs distances, i.e., the distance between every point in $\mathcal{A}$ and every point in $\mathcal{B}$. This takes $O(nma)$ time. Based on your original question, it appears that $n \approx 20$, $m \approx 50,000$, and $a \approx 800$, so that part should be very fast.

Unfortunately, the Hungarian algorithm might be too slow. The running time in this setting will be $O((n+m)^3)$, which might be too slow for your needs. I think a tighter analysis shows that its running time is actually $O(n^3m)$, which might be fast enough for your needs, but I'm not certain about that.

If the Hungarian algorithm is too slow, here is a heuristic that you could try. In each stage, we'll have a non-optimal solution and iteratively try to improve it. (You can start with the greedy solution, to get the process started.) Suppose our current solution assigns $f(b\_j)$ to the point $b\_j$. Let $t$ be a threshold. Filter the graph to include only edges $(a\_i,b\_j)$ where $\Delta(a\_i,b\_j) \le \Delta(f(b\_j),b\_j) + t$, and delete all isolated left vertices. Now find a minimum weight perfect matching in that graph. That will be a new solution that is at least as good as the previous solution. In each stage, increase $t$ according to some schedule. If you keep $t$ small, this won't necessarily give you the optimal solution, but it will make the Hungarian algorithm more efficient because it works with a smaller graph.

Theoretically, you can find a value for $t$ that enables you to prove that this will find the optimal solution (namely, a lower bound for the sum can be obtained by matching each element $b\_j$ to its nearest neighbor in $\mathcal{A}$, ignoring the constraint that the elements of $\mathcal{C}$ be unique, and summing those distances; now if you let $t$ be at least the difference between the cost of the current solution and that lower bound, and apply this scheme, if it converges -- yields the same solution you started with -- then you know you've found the optimal solution). However I don't know whether that will be useful in practice.

Anyway, this is one approach. It might not be the best or fastest, because it doesn't take into account the geometrical structure. But it's something you could try, to see if it meets your needs.
> 2 votes

---
Tags: optimization, search-algorithms, np, greedy-algorithms
---


title: Why are these languages not regular?

text:
# Question
Title: Why are these languages not regular?
Show that the following languages are not regular:

$(1)\ L=\left\\{a^nb^mc^k\mid n\>k \land n,m,k\>0\right\\}$

$(2)\ L=\left\\{a^nb^mc^k\mid m\>k \land n,m,k\>0\right\\}$

I've difficulties showing that these two languages are not regular by using the Pumping Lemma. Any suggestions?

# Answer
> 1 votes
I think it is easier to prove if you first note note $$ L' = \\{a^nb^mc^k|n\leq k \land n,m,k\>0\\} = \\{a^nb^mc^k | n,m,k \geq 1 \\} - \\{a^nb^mc^k|n\>k \land n,m,k\>0\\}$$ So if $\\{a^nb^mc^k|n\>k \land n,m,k\>0 \\}$ is regular then so is $\\{a^nb^mc^k|n\leq k \land n,m,k\>0\\}$ since $\\{a^nb^mc^k | n,m,k \geq 1 \\}$ is regular and the difference of regular sets is a regular set.

But $L'$ is not regular, a contradiction. If you are NOT convinced that $L'$ is not regular then see the following proof using the Pumping lemma.

---

So, let's prove that $L' = \\{a^nb^mc^k|n\leq k \land n,m,k\>0\\}$ is not regular using the Pumping lemma in order to obtain contradiction.

**The Pumping Lemma:**

Let $L$ be a regular set. Then **there is a constant** $n$ such that if $z$ **is any word in** $L$, and $|z| \geq n$ we may write $z = uvw$ in such a way that $|uv| \leq n$, $|v| \geq 1$, and **for all** $i \geq 0$, $uv^iw \in L$.

**How to prove**

1) Select the language you wish to to prove irregular.

2) The "adversary" picks $n$, the constant mentioned in the Pumping lemma. Once it has been picked, it may not be changed (fix it).

3) Select a string $z$ in $L$. Your choice may depend implicitly on the value of $n$.

We choose $z = a^nb^nc^{n+1}$ (since $n \< n+1$, $z \in L$).

4) The "adversary" breaks $z$ into $u$, $v$, and $w$, subject to the constraints that $|uv| \leq n$ and $|v|$.

5) You achieve a contradiction to the pumping lemma by showing that **there exists** $i$ such that $uv^iw \notin L$.

Since $z = a^nb^nc^{n+1} = uvw$ and $|uv| \leq n$, $uv$ is a string consisting of only $a$s, and so is $v$. If we choose $i=n+2$ then we get $uvvw$ such that $uv^{n+2}w$ has at least $n+2$ $a$s which is greater than $n+1$ $c$s which does not belong to $L'$. But this contradicts to the Pumping lemma.

You may try to prove the second language yourself.

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: 01 Knapsack with selection of items with minimum total weight
I have a slightly modified version of a classical 01 knapsack problem. Specifically, the problem has an additional constraint which requires that if more than one feasible selection with equal value exists then the selection with minimum total weight be selected. For example, consider a knapsack with size 3 and the following set of items to choose from; tuple is defined as ("name", weight, value):

```
items = (("alpha", 3, 4), ("beta", 1, 3), ("gamma", 1, 1))

```

There exist two possible selections with total `weight <= 3 and value = 4`:

### Selection 1:

```
[alpha] with a total value of 4 and weight 3

```

### Selection 2:

```
[beta, gamma] with a total value of 4 and weight 2

```

Due to the additional constraint, selection 2 is the correct answer. However, the classical 01 knapsack doesn't ensure this. So my question is, does there exist a variant of 01 knapsack which handles this? If not how do I tackle this additional constraint.

So far, I have the following two approaches which can possibly work:

* Calculate the density of the objects and then perform knapsack using density as the value. This approach however is suited to fractional knapsack where any arbitrary amount of an item can be taken. In this case, the item, if taken, must be taken in its entirety.
* Sort the items with respect to weights before running knapsack on them.

# Answer
> 4 votes
Sure. It's easy to take any algorithm to solve the ordinary knapsack problem, and apply it to your problem. In the ordinary knapsack problem, we specify an upper bound on the weight. Once we find the maximum value achievable with that weight, next we'll try to see if we can reduce its weight further. Do this by solving a new version of the knapsack problem, the same as the original, except the maximum weight has been reduced. See how far you can reduce the maximum weight while still achieving the same value. You can use binary search for that.

---
Tags: knapsack-problems
---


title: How are Qubits useful?

text:
# Question
Title: How are Qubits useful?
I'm aware that a qubit can exist in an infinite number of states and that when measured it collapses into one state, with the probability of each state being directly affected by it's latitude.

My question is: Why is this in any way useful? Surely you can't use a unit of information meaningfully when you don't know what it will be..?

Surely, not knowing what a quantum bit is going to be is detrimental to computing? I'm evidently missing something since we know that quantum computing works, but **why?**

# Answer
So you can't find out everything about the value of a qubit. That doesn't mean you know nothing about it. And, sure, quantum computing probably would be more powerful if you could find out everything about the value. But, again, the fact that you can't do everything doesn't mean that you can't do *anything*.

In particular, you know that the measured value of a qubit drawn from a probability distribution constructed by some quantum algorithm. The algorithm will, presumably, construct a distribution that's quite tightly concentrated about the true answer. And you can always repeat the computation to get multiple samples.
> 4 votes

---
Tags: computation-models, quantum-computing
---


# Question
Title: Complexity of membership testing for finite-regular languages
A language $L \subseteq \Sigma^\*$ is *finite-regular* if there exists $C$ such that for all $n$, $L \cap \Sigma^n$ is accepted by some DFA with at most $C$ final states.

Given a finite-regular language $A\_L$, am I guaranteed that there exists a polynomial-time algorithm $A\_L$ that recognizes $L$? In other words, I want an algorithm such that on input $x$ it returns true or false according to whether $x \in L$ or not, and the running time is polynomial in the length of $x$. Is this guaranteed?

Note that the number of states of the complete DFA accepting such $L$ may be $O(|\Sigma|^n)$ so any trivial algorithm actually constructing the full DFA would not be polynomial time. However the number of accepting final states is $O(1)$, which leads me to believe there is some shortcut available here.

Thanks to Yuval Filmus for formalizing this language class, and explaining its closure properties.

# Answer
> 4 votes
Finite-regular languages need not even be decidable. Indeed, if $L$ is *any* language such that $|L \cap \Sigma^n| \leq C$ for some $C$ independent of $n$, then $L$ is finite-regular (you can show this by considering the case $C=1$). In particular, the language $\\{ 1^n : \text{ the $n$th Turing machine halts on the empty input} \\}$ is finite-regular but not decidable.

---
Tags: time-complexity, regular-languages, finite-automata
---


# Question
Title: Complexity for merging 3 sorted arrays using this specific algorithtm
During an interview I was asked to calculate the big theta complexity for the following algorithm that receives 3 sorted arrays of variable size and returns a new array which has the elements of the original 3 arrays.

The algorithm is pretty basic: we set indexes at the beginning of each array and use such indexes for accessing the elements, in that fashion we find the minimum element for the 3 arrays (at the position given by the indexes) and then we insert the element into the resulting array and we increase such index. We repeat until we are done processing every element.

My answer was that the complexity was linear because we are processing n elements and we are doing a constant number of comparisions for finding the minimum element out of the 3 arrays (at the given index position). Yet, I was told that the complexity is not linear but it is higher than nlogn.

I have a few ideas but could someone explain the actual complexity of this algorithm for me?

Thanks for your time.

# Answer
Assuming that you're using some random-access model of computation (i.e., not an ordinary Turing machine) and that comparisons can be done in constant time, the algorithm you describe is linear. Each element of the final array is produced by comparing at most three elements of the original arrays, so each element of the output is produced in constant time.

Perhaps you misunderstood the question and they were actually asking about something else? Perhaps they mis-stated their question and they were trying to ask about the complexity of three-way mergesort (sorting an array by splitting into three parts, recursively sorting the parts, then merging them)? Perhaps they were just wrong.
> 5 votes

# Answer
What you are describing is merging $K$ sorted arrays, each array of length $N$. In this case, from the algorithm you describe you are making $K$ comparisons and there is a total of $N \cdot K$ elements, your complexity is $O(N \cdot K^2)$. If $K=N$ then it is $O(N^3)$.
> 0 votes

---
Tags: complexity-theory, runtime-analysis
---


title: Trie sorting based on word frequency

text:
# Question
Title: Trie sorting based on word frequency
Given a trie with word occurrences (frequency), how can we sort the words( both ascending and descending) on the basis of their frequency?

# Answer
As the comments say, the basic trie will not help with this task. So I'll propose a special trie for this task. It is the same in every way to normal trie *except* the "end-of-word" (EOW) nodes (Note that these are not necessarily leaf nodes as words may overlap, e.g. "the" and "theory").

Forget the trie for a moment and imagine all words of frequency 1 in a linked list. Now imagine we have multiple linked lists for each frequency. Now we have $k$ linked lists if there are $k$ distinct frequencies. We can chain these links together, in order of frequency, to create a linked list of linked lists. You could imagine something like this:

We will try to add this same idea into the EOW nodes in the trie without messing up the trie structure. It will be similar, but we will also need every EOW node to point to the sentinel node of their respective frequency list. We will have the following properties in the EOW nodes:

* `head` \- head (or sentinel) of this frequency list.
* `next` \- next EOW node in this frequency list.
* `prev` \- previous EOW node in this frequency list.
* `frequency` \- frequency of the word that ends at this EOW node.

The sentinel node will also have a `next_head` and `prev_head` field to go to the next and previous frequency list. Similarly the empty root of our trie will act as a sentinel to the first frequency list (i.e. `root.next_head` is `frequency_list_1.head`). It will look something like this:

Now we just need to modify the insertion procedure a little bit to accommodate these changes. Specifically the changes will occur when we reach the EOW node. I had started writing the changes out in pseudocode but it became a bit cumbersome. So there are probably easier ways to do this. The idea still is the same. Insertions should only increase by $O(1)$ operations because you'll never have to move a node more than one frequency list at a time, and if you have the necessary pointers this is fine. From there it's as simple as iterating over the list of lists of EOW nodes.

---

### Analysis:

Let the words be a set $S$ of $n$ words and $k$ unique words (apologies for reusing $k$, this is different than the first $k$ we define).

Then we have that the insertion time for **all** words will be $O(sum\\{|S\_i|\\})$. Or if we say $m$ is the length of the longest word, then it is $O(m \cdot n)$. Then after insertions getting the frequencies in order is $O(k)$ and $O(n)$ for the simple traversal.
> 6 votes

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


# Question
Title: What kind of pattern recognition algorithm would Facebook use to detect suicidal users?
Facebook announced that it would employ a machine learning "reporting process using pattern recognition in posts previously reported for suicide" (https://newsroom.fb.com/news/2017/03/building-a-safer-community-with-new-suicide-prevention-tools/).

**Could anyone explain in more detail how this pattern recognition algorithm might work in their reporting system? Is it possible to say what kind of classification algorithm are they most likely using? Something similar to a spam filtering algorithm?**

Here's the section I quoted from:

*"Based on feedback from experts, we are testing a streamlined reporting process using pattern recognition in posts previously reported for suicide. This artificial intelligence approach will make the option to report a post about 'suicide or self injury' more prominent for potentially concerning posts like these. We’re also testing pattern recognition to identify posts as very likely to include thoughts of suicide. Our Community Operations team will review these posts and, if appropriate, provide resources to the person who posted the content, even if someone on Facebook has not reported it yet"*

# Answer
I would take march average to calculate several indicators from posts of the same user including but not limited to:
\- emotional-tagged words from posts (using available dictionary for this purpose) \- sudden changes in the writting style
\- response times to messages
\- relationship changes
\- job changes

Also tagged messages reported by users, if it abides with policy also filtering concerns from private messages (reading them is probably illegal, but feeding machine learning scripts, maybe would be ok). For the supervised learning, the morbid idea is to feed learning algorithm the posts of people who made attempts.

To feed any data it should be preprocessed (to get rid of noise - texts that have no indicating value), possibly with included data about gender, age, education. Since it may not be properly filled in, maybe some additional scavenging and recognition of profile images (to determine age fir example) may be needed.

From reading the link it looks like scheme to allow flagging concerns, also the group of experts is reviewing the reports, so it is for sure mixture of unsupervised, supervised and experts learning system, scrapping every possible data.

To answer the main question, it depends on data acquired, resources available (for example how many review hours from experts they are willing to afford). The gathered data (and assumed certainty) shapes the used algorithms. The other problem is that there are no good enough tests to tell apart depressed or suicidal people apart based only on social media or written tests, so my bet is there are at least several algorithms formed into polling system, quite like ICD-11 or DSM-V diagnostic manuals, poll-based operationslisation of state to detect disorders. But the sentiment analysis gives roughly 20% of good results when used for opinions, for emotion detection it vastly degrades, so this approach would not be considered as is for safety reasons. The Stanford NLP unit works hard on higher level understanding of text, with sentiment analysis demo available. It works poorly for short texts, peaking at moderately long ones. It may be incorporated into longitudal working (time based consecutive tests), where afaik it could yield 25% for negative mind state of user.

Your idea of spam filtering may work in this context, where filter detects anomalies of behaviour or predefined patterns comming from tagged messages, but it must yield many false positives (due to weak patterns available).

The natural choice would be RNN, as Martin wrote, to account for dynamic temporal behaviour, if any other NN is used, such feature would be simply emulated, to match temporal behaviour of suicide plans. Estimating risk factors and including personal data (some auxiliary tests are required to asses personality traits, hopefuly these are quite accurate and work even in transparent setting, when someone is evaluated from behaviour), there should exist several time scale factors independently at least for every main personality type. The main disadvantage here is accuracy of profile data, for example five years inaccuracy in the age field filled by user matters. If someone for some reasons fills birthday date wrongly, the learning system cannot depend on valuable data what user does that day and whom meets. This may seem as tangential, but users privacy is important here, if someone feels insecure, the important data is lost, otherwise inferrence is inaccurate.

TLDR;
The algorithms used is not arbitrary chosen, it does not matter which one is performant or accurate for some tasks, it is data dependend choice, so it is hard to pick. Another factor is assesment, which is far from ideal. We can conclude that there are non-standard algorithms created solely for this task (perhaps including several known ones), but the heavy lifting is still done by people, as the machine learning works as screening test, flagging for review.

The fresh and interesting article about Predicting Risk of Suicide Attempts Over Time Through Machine Learning claims 80-90% accuracy, but is not applicable here, because it uses medical records to work.
> 1 votes

# Answer
While I can't give a definite answer (I don't work for Facebook), I have a couple of ideas what to look for.

First of all, the area is called (Natural Language Processing) and while you could phrase it as a binary classification problem, I rather think they will apply *sentiment-analysis*. This might also be relevant to advertisement (you rather want ads next to positive posts)

The question What is the Best and easiest way to create a Classifer for Sentiment Analysis was closed as to broad, so the same might apply here.

I think the best systems today use RNNs (recurrent neural networks) and learn pretty much from the raw text (see How does a recurrent connection in a neural network work?).

Simpler algorithms use stemming, tf-idf features and apply a classifier to it (could be a neural network, a random forest or a SVM).
> 0 votes

---
Tags: algorithms, machine-learning, artificial-intelligence, classification, pattern-recognition
---


# Question
Title: What is the branching factor for nondeterministic games?
Given a nondeterministic game how could one know the branching factor of it? Is it the number of all possible outcomes?

I have an example game in which you have some cards. The goal is to get rid of all of them. At the start of the game you get 7 random cards. There is a draw pile from which you take cards if you can't (or don't want to) play a card. You can't see the cards in that pile and they are in random order. The amount of card types in the simple version is equal to 52. If I understand correctly that means that the branching factor is at least 52 for every move plus 52 times the number of cards of the player (player's don't know other's cards). Is my thinking correct? It seems to be too big (416 at the start of the game (52 + 52\*7) from the perspective of another player and 59 (52 + 7) from the player's own perspective, when Go has "only" 250) but I'm not expert in this.

# Answer
The branching factor depends on exactly how you model the game. A standard way to model games that have some randomness is to imagine adding another player (the "dealer") whose only purpose is to make a random choice.

So if your game involves only one player Alice, we'll add another player Declan (the dealer). Alice and Declan alternate turns. During her turn, Alice can either play one of her cards or choose to draw from the pile. Thus, if Alice has $n$ cards, she has $n+1$ actions she can choose from. During Declan's turn, if Alice previously chose to draw, Declan selects one of the remaining cards and adds it to Alice's hand; otherwise he does nothing. Thus, if there are $m$ cards remaining in the pile, Declan has either $m$ actions he can choose from, or only one.

With this model, the maximum branching factor is 53 (assuming Alice can have up to 52 cards in her hand).
> 2 votes

---
Tags: trees, search-trees
---


# Question
Title: Is deciding whether or not a graph is bipartite in $L$?
Let's consider the problem:

> Prove that decision whether a graph is bipartite is in $LOGSPACE$.

I am convinced that I should use Reingold's theorem. I know that I test whether graph contains an odd-length cycle.

For a given graph $G = (V,E)$ I can define the graph $$G' = (V', E') \\ V' = \\{ v^1, v^2 | v \in V \\} \\ E' = \\{(u^1, w^2), (u^2, w^1) | (u,w) \in E\\}$$

And now, the vertex $v$ resides in odd-length cycle iff there is a path between $v^1$ and $v^2$.

But, how can I construct $G'$ using $LOG$ memory?

# Answer
Your construction shows that checking whether an undirected graph is bipartite is logspace reducible to PATH (deciding whether there exists a path between two vertices in an undirected graph).

Recall that if $A$ is logspace reducible to $B$ and $B\in L$, then $A\in L$. To decide $A$ in logspace, you don't actually compute the reduction (as its output can be of polynomial length), but compute a single bit of the reduction whenever it is requested. More concretely, suppose $f$ is a logspace reduction from $A$ to $B$. To decide $A$, given input $x$, execute the logspace machine for $B$ and keep a counter $i$ for the location on its input tape. Whenever $B$ wants to read a symbol from its input, compute the $i$'th bit of $f(x)$, which requires only logarithmic space (as $f$ is a logspace reduction from $A$ to $B$).

This show that you don't actually need to construct $G'$ entirely. You only need to compute a given bit of its adjacency matrix in logarithmic space.
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: What is the correct FSA representation of the following string sequence?
Based on this article, i am trying to imagine how i would construct an FSA based index for the following string sequence:

1. ABCDEF
2. ABDDDF
3. ABDDEFGHI

These are the representations that i found:  There are problems with each:

The first introduces a new key in the automata that really isn't in the set (ABCDEFGHI)

The second one is the closest to my heart but it is more trie-like, so it can be inefficient at a large scale.

The third saves a lot of final states therefore saves some space. However, state 9 has multiple "F" transitions which i think is illegal.

So the big question is: Which one of the above is correct? If none of them, please share what is the correct!

Thank you

# Answer
> 1 votes
I think none of your finite automata accepts the third string `ABDDEFGHI`.The following is what I think a correct finite automaton for accepting all three strings

In case where your language has the third string `ABDDDFGHI`.The first is wrong since it accepts another string.The third also seems incorrect since there are multiple labels of same letter exiting from one node.Your second automaton is correct but you may want something like this

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


title: Cross Edge and Back Edge when doing BFS

text:
# Question
Title: Cross Edge and Back Edge when doing BFS
I was asking to prove that

> For any directed graph, when we perform BFS, for each cross edge $(u,v)$, there is some time when both vertices $u$ and $v$ appear in the queue. (In other words, we have a queue like this: $Q = \langle v\_1,v\_2,..u,..,v,..v\_k \rangle$.)

However, when I draw some graph; I've encountered this example

If we perform BFS starts from $a$, then what is the edge of $(f,c)$? clearly, if what I was about to prove is correct, $f$ and $c$ will never appear in the queue at same time during the whole execution of BFS. So $(f,c)$ is not cross edge. Then what edge is this ? It can't be back edge; since $c.parent$ is $a$, and $f.parent$ is $e$. they aren't tree edge, nor forward edge.

So what I am asked to prove is not correct?

So I guess that the statement only holds for undirected graph?

# Answer
> 3 votes
Your statement for directed graphs is not true. Your graph in the OP is a counterexample. However, for undirected graphs it is true since if $(a,b)$ is a cross edge then the depth-difference between the vertices is at most 1, i.e. $depth(a) = depth(b)$ or $depth(a)+1 = depth(b)$. Using this fact, which is proved below, you can prove your statement.

Assume that at some point you have the following queue configuration: $$v\_1, v\_2,\dots, v\_k,a,\dots, u\_1,\dots u\_m \text{ (leftmost leaves first)}$$ where $v\_i$s and $a$ have the depth $d$ and $u\_i$s have the depth greater than $d$. Since $(a,b)$ is a cross edge, $a$ and $b$ belong to different ancestral trees, i.e., one of the $v\_i$s is an ancestor of $b$ i.e, $b$ must be discovered before we reach $a$. If their depth values are equal then $b$ has already been reached (discovered) and so they must be at the same time in the queue. Otherwise, their depth values differ by 1 and so $b$'s ancestor (parent) must be one of the $v\_i$, say $v'$. This $v'$ is popped and extended before we reach $a$ and since $b$ is a descendant of $v'$, $b$ is pushed into the queue before $a$ is removed.

Thus in both cases $a$ and $b$ appear in the queue for some time during the execution of BFS.

---

**Claim:** In a breadth-first search of an undirected graph for each cross edge $(a,b)$ $$0 \leq depth(b)-depth(a) \leq 1$$ **Proof**: Assume that $depth(b)-depth(a) \> 1$. Then $depth(b)$ is at least $depth(a) + 2$. But $(a,b) \in E$ (a cross-edge) and hence $depth(b) = depth(a)+1$, a contradiction (see the following figure).

---
Tags: graphs
---


# Question
Title: Prove correctness of iterative LCM algorithm
I have been trying to prove the following algorithm, without success.

Here is the C-Style pseudocode:

```
//j,k >= 0
int get_lcm(int j, int k){
    int c = j;
    int d = k;
    while(c != d){
        if(c < d){
            c += j;
        } else {
            d += k;
        }
    }
    return c;
}

```

I tried to find the loop invariant, which ended up being something like: $$ \begin{aligned} &c\le\text{LCM}(j,k) \wedge d\le\text{LCM}(j,k) \wedge c=aj \wedge d =bk\\ &(a,b \in N) \end{aligned} $$ I'm not sure how to proceed from here. I understand intuitively why the algorithm works, but I'm having trouble putting out an actual formal proof of it.

I need to come up with an invariant such that $c=d=LCM(j,k)$ when $c=d$. I'm having trouble showing how $c, d \le LCM(j,k)$ after one iteration.

Can anybody please help me? Thank you for your time.

# Answer
> 1 votes
Assume j, k \> 0.

You have your loop invariant. Every iteration, one of c or d gets larger. They cannot forever stay ≤ LCM (i, j), therefore the loop must finish.

Because c and d are multiples of i, j, they cannot change directly from being \< LCM (i, j) to \> LCM (i, j), instead there must be a step for each of c and d where it is equal.

If both are = LCM (i, j) then c = d and the algorithm exits. If one is = LCM (i, j) then the other one is smaller and gets increased.

# Answer
> 0 votes
I don't know how to write it down mathematically but may be I can do good with words to give you an idea.

You should ask yourself the question

**What's the smallest possible LCM of `j` and `k`?**

**Ans-** When the LCM is either `j` or `k`(When one divides the other without remainder).

**So now what's happening in the loop**

**1**. `c` is a multiple of `j` (since it is initialized with the value of `j` and increments by `j` whenever `c` is smaller than `d`).

**2**. Similarly `d` is a multiple of `k`.

**Now let's come to the point**

If `j` is the LCM then As long as `j` is greater than `k` , `d` will continue to increase unless `d` becomes equal to `m*k` where `m` is a factor of `j`.

If `k` is the LCM then As long as `k` is greater than `j` , `c` will continue to increase unless `c` becomes equal to `n*j` where `n` is a factor of `k`.

**Mathematically, LCM can be defined as**

***LCM(j,k)=j*n=k*m*** where `n` and `m` are the times `j` and `k` are added to themselves

**So if an LCM exists then in the loop**

`c`(the iterative multiple of `j`) must become `j*n` before becoming `j*(n+1)`.

Similarly `d`(the iterative multiple of `k`) must become `k*m` before becoming `k*(m+1)`. which is the same as saying that

**c == d** will be true at some point.

---
Tags: algorithm-analysis, correctness-proof, loops, loop-invariants
---


# Question
Title: Convolutional Neural Networks - Where should I start from?
I will soon be starting a part-time job within a start-up and I've been assigned to a project where I'll have to build a CNN that recognizes and counts people in various kinds of videos.

My CEO knows I have no training or experience in Computer Vision and he suggested that I should spend all my working hours in the first month on understanding the necessary concepts behind CNNs and then proceed with the implementation for the next two months.

I know that mathematics are a huge part of understanding the necessary concepts. I'm a CS 3rd year undergrad and my relevant studies in math are comprised of the following:

---

* Calculus $I - IV$
* Linear algebra and differential equations (didn't study partial differential equations)
* Complex analysis

---

I've managed to pass these courses with maximum scores. Since mathematics is a very dear interest of mine, I spent a lot of time on actually understanding each and every concept I've studied so far.

So, my questions is, are there any textbooks on CNN(preferably free) you could recommend, given my experience and goal?

Also, since my mathematical training may not be enough, I would also appreciate insights (or textbooks) on what should I learn, or improve while studying the concepts behind CNNs.

# Answer
> 1 votes
I know this is a link only answer, but the question is a reference request.

Neural Networks and Deep Learning is a free online book. The book will teach you about:

* Neural networks, a beautiful biologically-inspired programming paradigm which enables a computer to learn from observational data
* Deep learning, a powerful set of techniques for learning in neural networks

---
Tags: reference-request, neural-networks
---


# Question
Title: Are genetic algorithms an effective way to train neural networks?
It seems to me that genetic algorithms would be an ideal way to train neural networks so that they come to have the right weights, since they are especially good at escaping local minima, and converging on a global optimum. However, from my rudimentary knowledge of neural nets so far, I haven't come across this method in any tutorial video. Are there inherent challenges that make GA's unsuitable for this purpose? Or is there a better way to accomplish the same thing?

# Answer
> 4 votes
There have been hundreds of papers published over the years on training neural networks with GAs. Here's a starting point Neuroevolution.

The basic problem though is that stochastic gradient descent works really well in vastly less computation time.

---
Tags: artificial-intelligence, neural-networks, genetic-algorithms
---


# Question
Title: Any algorithm polynomial time with infinite space?
If I had an arbitrary amount of space at my disposal, couldn't I vectorize/parallelize any program in such a way that it would only need one step? For example, I could let my CPU have an inbuilt look-up-table for the function (x+y)/z with 3 input values instead of doing the calculation in 2 steps.
Does there exist any proof that something like that isn't possible?

# Answer
> 2 votes
If you don't allow preprocessing, then the answer is no (at least when talking about standard models of computation such as the Turing machine or a random access machine). The reason follows from the fact that (in reasonable models) writing to memory requires time, hence the amount of memory used is upper bounded by the running time.

The notion of preprocessing is captured in complexity by machines who have access to an advice, alongside with the input. For example, the class $\mathsf{P/Poly}$ consists of all problems solvable using polynomial machines, who given a length $n$ input, have access to an advice string of length $poly(n)$. Note that the advice is the same for all inputs of the same length, you can think of this advice as your preprocessing. If, as in your example, you allow too much preprocessing, then everything is solvable in a single step, which makes this situation uninteresting (and indeed, it is not realistic to imagine you have the answer ready for any possible input). In the language of Turing machines who take advice, you can say that $\mathsf{P/EXP}$ with random access to the advice is the class of all languages (your advice can include the answers for all inputs). This means that allowing the advice to be too long makes the game too easy.

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


# Question
Title: Why do TPTP Performance plots look like this?
CASC is the premier Automated Theorem Prover competition performed annually at the Conference on Automated Deduction (CADE). The 2017 event has finished on the 9th of August this year.

During this conference provers are faced with a set of problems and a time limit of 5 minutes (300 seconds) per problem. When the competition is over, the timings for each problem are taken to produce performance plots.

Here we see the results from the general first order formulas (FOF) division. 11 ATP systems participated, Vampire 4.2 was the winner in this division having solved over 450 problems from the set.

It is clear from this plot that the timings for each prover were independently sorted in increasing order and plotted over the same axes.

What is puzzling is the shape of the graph: for most provers most of the problems were really easy (solved within 50 seconds) and only a small proportion of problems were difficult yet solvable within the time limit (i.e. about 5% for Vampire 4.2 and less than 10% for Vampire 4.0, the 2016 winner). On the remaining problems (there were 500 problems altogether) the prover failed. Is there an intuitively simple explanation of why the difficulty distribution is so skewed towards "easy" problems not for one but for all provers?

# Answer
> 3 votes
I can speculate/hypothesize. Each solver has many heuristics and proof tactics. Imagine that corresponding to each heuristic is a class of instances that are easy to solve if you use that heuristic, but hard if you don't (e.g., if you don't have a heuristic for it and you fall back to the generic methods, maybe you're effectively exploring the entire exponentially large space of possible solutions to try to find one that works). An example would be 2SAT; if you use the right algorithm, it can be solved in linear time, but if you blindly search, that will take exponential time.

So, in this model, if an instance is handled by one of the prover's heuristics, it is solved very rapidly; otherwise you fall back to some generic method that may take exponential time. This would lead to a kind of "very fast or very slow" dichotomy. And the set of instances that a prover is fast on may be different for each prover, because prover uses a different set of heuristics. In other words, this hypothesis would explain the observed behavior.

I have no data and no hard evidence, so this is merely speculation. It could be entirely wrong.

---
Tags: first-order-logic, automated-theorem-proving
---


# Question
Title: How do confluently persistent data structures handle merge conflicts?
From my limited understanding fully persistent data structures allow changes to be made to previous nodes, with new nodes creating a branch rooted at the changed node, resulting in a tree of nodes and also disallowing the remerging of these branches.

```
       o o o
      /
o o o o o o o o o
  \
   o o o

```

Confluently persistent data structures on the other hand seem to allow the merging of these branches even though over time they may accumulate conflicting modifications to the contents of their given nodes.

```
o o o o o o o o o o o o
  \
   o o o o o x x x
      \     /
       o o o

```

I think I've searched the given research for an algorithm about how to potentially handle merge conflicts arising from this situation but have come up with nothing. Real world examples like git appear to punt this question to the user for manual resolution. Is this really the only option? Thanks for reading!

# Answer
> 4 votes
Typically, confluently persistent data structures are built so that they will never have a merge conflict. The details differ for each such data structure, but here are the broad outlines. Basically, you define a semantics for what you want to happen during a merge, then devise a data structure with those semantics. (The desired semantics depends on the kind of data stored in the data structure; there's no single answer.)

So what's a merge conflict? A merge conflict arises when your semantics for the merge throws up its hands and says "I don't know what to do". But normally, when we design confluently persistent data structures, we typically define merge semantics where that will never happen. In other words, the semantics are well-defined for all possible cases. Merge conflicts are only necessary when there are situations where the semantics aren't well-defined.

Why does git have merge conflicts? Because it is a general-purpose tool used to store arbitrary data with unknown meaning/semantics. Therefore, we can't know what the "right" semantics for merging is, in general. But confluently data structures are typically designed for a narrower, more specific purpose. Think, for instance, of a set; that has a well-defined semantics, and we can define a merge operator that fully specifies what the result of merging two sets should be for all possible cases. So, it's feasible to define merge semantics that are well-defined for all possible cases, when the data structure handles such a specific, well-defined kind of data. Git has to deal with a harder problem, where it might not be possible to define a useful, sensible merge operator that is defined for all possible cases.

---
Tags: persistent-data-structure
---


# Question
Title: An efficient method to compute a minimum set of sets that form the union of these sets?
Let's say we have a set of sets:

$$\mathfrak S = \lbrace S\_1, S\_2, ... , S\_n\rbrace$$

And the union of the all the sets in this set:

$$\mathfrak U = \bigcup\limits\_{i=1}^{n} S\_{i}$$

And so there is at least one minimum set of sets that is identical to this union:

$$(\mathfrak M \subseteq \mathfrak S) = \mathfrak U$$

What is the most efficient known method of computing $\mathfrak M$ ?

# Answer
In case $S\_i$ sets are finite your problem is reduced to the Set Cover problem which is NP-complete. You can also attack this problem by any approximation algorithm, e.g. Greedy algorithm, or by using Linear programming.
> 2 votes

---
Tags: algorithms, sets
---


# Question
Title: Building segment tree without adding extra elements to its size
I recently learned about segment trees as data structures, and what I learned was that we are always building segment tree with size $N$ such that $N$ is power of two. If $N$ is not power of two we can add more elements to the end of the tree.

However, I was wondering is the segment tree going to work normally if we don't add more elements to make its size power of two.

**Example**

If the size of segment tree is 8, then we have array of size 15, $15 = 2 \cdot 8-1$ In this array we keep track of the intervals, where we have the interval $\[1,8\]$ on index 1, and on index $2\cdot 1$ we keep the left child, and the right child is on index $2\cdot1+1$.

So our array looks like following:

index $1: \[1, 8\], 2: \[1, 4\], 3: \[5, 8\], 4: \[1,2\], 5:\[3, 4\],6:\[5, 6\], 7:\[7, 8\]$, $8\[1, 1\], 9:\[2, 2\], 10:\[3,3\], 11:\[4,4\], 12:\[5,5\], 13:\[6,6\], 14:\[7, 7\], 15:\[8,8\]$

Now my question is this: If we run this algorithm for dividing and building the segment tree for numbers that are not power of two (ex. 7, 11, 15).. is it going to build the segment tree normaly, because the segment tree is not going to be full balanced then.

# Answer
> 7 votes
A segment tree is not required to be *full* (which is what I believe you mean), however it will always be *complete*. That is, every level, except possibly the last, is filled.

Take a look at the structure and construction to see that it says nowhere that was must have $2^k - 1$ nodes in the tree. For example we may have $2^{k-1} \< c \< 2^{k}$ elementary intervals, making our tree non-*full*, but absolutely *complete*.

---

Example, let's say we have intervals:

$$I = \\{\[1, 5\]^A, \[2, 3\]^B, \[2, 8\]^C, \[4, 6\]^D, \[4, 10\]^E, \[5, 9\]^F, \[7, 8\]^G\\}$$

We then have the endpoints of the elementary intervals:

$$I' = \\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\\}$$

Now we construct a balanced tree with just the end points as leaves:

Next when we insert intervals to get:

This is fine. Adding in the extra elements is usually a convenience. This is mostly a convenience when using an array to implement the tree. For efficiency reasons, using an array is almost always preferable to an actual tree (`Node`) object because there is much less overhead. Arrays also make it easier/more natural to implement searching/insertion iteratively rather than recursively which decreases another factor of overhead. The sacrifice of adding at most $2x$ as many nodes is generally worth it. Asymptotically there is no difference.

---

Okay, so using an array is preferable, but why do we need $2^k - 1$ elements? If we have a full binary tree there is *almost* no edge case handling. Imagine in a recursive procedure we produced a tree like the one above. What would it look like in an array?

I'll show the two different proposals.

1. Our tree if we filled up the last layer and moved all elementary boundaries to leaves (leaves in red and the gradient shows least to greatest boundary, levels are different colored blue boundaries)

2. Our tree if we do **not** fill up the last layer and left leaves as is.

Clearly (1) should look more appealing, but it is also functionally more appealing. There is only one leaf level, so we need no conditional checking if we are at a leaf or not, we just check which iteration into the tree we are at. There are simply more checks to do per iteration and it is not worth it over filling in the final level. So you *can* do it, but I wouldn't.

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


# Question
Title: Proving this language is not context free using the pumping lemma
I am trying to prove why the below language is not context free. Note: this should be carried out by applying the pumping lemma for context free languages.

To prove something with the pumping lemma, we firstly need to choose an arbitrary m \> 0. After that we need to formulate the string (alpha below) we are going to reach a contradiction with. But how do I formulate that string? Rational thinking lead me to believe it's the following:

What do I do next?
I have no idea about the length of $w$, and therefore the above approach seems kind of useless.

Is the solution to constrain $w$ to be of length at most $m$?
But again, I wouldn't know what to do from there.

# Answer
> 1 votes
Here in the notation of the language superscript $R$ is *not* a number; you cannot choose it to be a length $m$.

Instead $R$ usually denotes the operation of "mirror image" which inverts a string: $(abbaa)^R = aabba$.

Now start rereading your notes on the Pumping Lemma.

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


# Question
Title: Solve X(n) = 2X(n-1) + 2 recurrence relation
I'm trying to solve the excersice from Knuth's "Concrete Mathematics":

```
A Double Tower of Hanoi contains 2n disks of n different sizes, two of
each size. As usual, we're required to move only one disk at a time,
without putting a larger one over a smaller one.

How many moves does it take to transfer a double tower from one peg to
another, if disks of equal size are indistinguishable from each other?

```

My solution was like this. Let $n$ be the number of disks of different sizes and $X\_n$ - number of moves. The first few solutions are:

$n = 0$ $X\_n = 0$

$n = 1$ $X\_n = 2$

$n = 2$ $X\_n = 6$

$n = 3$ $X\_n = 14$

Recurrence is $X\_n = 2X\_{n-1} + 2$

We can add $2$ to both sides:

$X\_n+2 = 2X\_{n-1} + 4$

let $Y\_n = X\_n + 2$, then

$Y\_n = 2Y\_{n-1}$

$Y\_n = 2^n$

$X\_n = 2^n - 2$

The problem is that the correct solution is $2^{n+1} - 2$, but I cannot find an error in my approach.

# Answer
> 2 votes
Your $Y\_0$ is probably wrong. $Y\_0$ must be equal to $X\_0+2=0+2=2$. Then $Y\_n=2^{n+1}$ and hence $X\_n=2^{n+1}-2$. Please double check.

---
Tags: recurrence-relation
---


# Question
Title: Are there any proofs that BQP is not in P?
**Are there any proofs that BQP is not in P?** In laymen's terms, I am asking if there is any formal proof separating the complexity class that quantum computers are presently assumed to solve efficiently from the complexity class that non-quantum computers are presently known to solve efficiently.

Obviously I'm not talking here about black box/oracle proofs that show they are nonequivalent *if we have access to some theoretical oracle*. Just talking about regular, normal equivalence.

# Answer
This is a famous open problem, so you won't find a proof anywhere at this time. We don't even know how to prove that $\mathsf{P\neq PSPACE}$, so finer separation of complexity classes such as $\mathsf{P\neq BQP}$ is also not known. Note that $\mathsf{BQP\subseteq PSPACE}$ is not trivial, you can find a proof in Quantum complexity theory, by Bernstein & Vazirani.

It is suspected that they are different, with the ability of quantum computers to factor integers in polynomial time being a strong witness.
> 3 votes

---
Tags: complexity-theory, quantum-computing
---


# Question
Title: Choose N pairs of (job, time slot) with a constraint on the number of different jobs
I am making a solver to choose the best assignment to a set of people for an event, given their availability (chosen in a set $T$ of time slots), jobs preferences (among $J$ possible jobs) and some of other predefined constraints. We refer to a particular pair of *(job, time slot)* as a "shift".

I'm not optimizing the entire workforce at once but instead I assign one person at a time.\* Here's an overview of how I modeled the sub-problem:

* Enumerate the set $S$ of all possible shifts ($|S| = |J|\times|T| = 90$ in my case)
* Use an objective function related to the number of people already assigned to each shift (and the need for that shift)
* Find solution $x \in \\{0,1\\}^{|S|}$ that associates to each element of $S$ a value in $\\{0, 1\\}$

The constraints are the following:

* Each person can be assigned up to N shifts (depending on their preference)
* Up to 2 shifts during the same day
* No consecutive shifts except when the job remains the same
* **Each person can do only up to two different jobs during the entire event**

I managed to encode all the constraints as a linear program except the last one. Any idea on how that could be done ? If that is not possible at all (which I suspect), what tool can I use to solve this problem ?

---

* I know that is sub-optimal, but finding a better algorithm will probably be the subject of another question ;)

# Answer
The last constraint is also no problem. You already have variables $x\_{j,t}$, that say if the person works the $j$th job on the time slot $t$. Now you can introduce new binary variables $y\_j$, that represent, if the person works at the job $j$ or not. Then you can model the constraint by:

$$\sum\_{j \in J} y\_j \le 2$$

The only part left is how you connect the information from the $x\_{j,t}$ with $y\_j$. But that is also not hard. If any of the $x\_{j,t}$ is $1$, then you can force $y\_j$ to also be $1$ with the constraints

$$y\_j \ge x\_{j,t}\qquad\forall t \in T, \forall j \in J$$

and force $y\_j$ to $0$ if all $x\_{j,t}$ are $0$. This can be done with:

$$y\_j \le \sum\_{t \in T} x\_{j,t}\qquad\forall j \in J$$
> 2 votes

---
Tags: optimization, linear-programming, integer-programming
---


# Question
Title: NP-complete language as a result of xoring two PTIME languages
> We define xor operation on languages $L,M\subseteq \\{0,1\\}^\*$:
> $$L\oplus M = \\{u\oplus v :|u|=|v|, u\in L, v\in M\\}$$ $\oplus$ is defined as xor on postions, for example: $001\oplus 100=101$ Show that there exist languages $L,M\in PTIME$ such that $L\oplus M\in NP complete$

It is hard to me. I have been thinking a lot about it. My intuition is:

Write the problem as equations system and reduce 3-SAT to it. But, I am not sure if it is ok and, if yes, how to solve it.

# Answer
> 2 votes
This seems like a rather difficult question. Here is one approach.

Every 3CNF on $n$ variables can be encoded as a binary string of length $8n^3$ (how?). Consider the following two languages: $$ \begin{align\*} L\_1 &= \bigcup\_{n=1}^\infty \\{ xy0^{8n^3} : |x|=n, |y|=8n^3, \text{$x$ is an assignment satisfying the 3CNF $y$} \\}, \\ L\_2 &= \bigcup\_{n=1}^\infty \\{ x0^{8n^3}y : |x|=n, |y|=8n^3, \text{$x$ is an assignment satisfying the 3CNF $y$} \\}. \end{align\*} $$ These two languages are clearly in P, and so their XOR is clearly in NP. However, $$ (L\_1 \oplus L\_2) \cap \bigcup\_{n=1}^\infty \\{0^ny^2 : |y|=8n^3\\} = \bigcup\_{n=1}^\infty \\{0^n y^2 : |y|=8n^3, y \text{ is satisfiable}\\}, $$ showing that $L\_1 \oplus L\_2$ is NP-complete.

# Answer
> 1 votes
I have other idea, I am not sure if it is correct:
Let $k$ will be number of clauses and $n=5$ number of variables. I reduce $3-$SAT problem, for each clause $c\_i=(x\_1, x\_3, \neg x\_5)$ I create language $$L\_i= \\{1\\{0,1\\}\\{0,1\\}\\{0,1\\}\\{0,1\\},\\{0,1\\}\\{0,1\\}1\\{0,1\\}\\{0,1\\}, \\{0,1\\}\\{0,1\\}\\{0,1\\}\\{0,1\\}0 \\}$$
So $L\_i$ contains patterns which satisfy $c\_i$. Of course $L\_i\in P$.
Let $$L=L\_1\cdot ...\cdot L\_k$$, $$M=\\{(\\{0,1\\}^n)^k\\}$$
Hence, $M$ contains all possible assigments reapeted $k$ times. Now, we can check if $0^{kn}$ belongs to $L\oplus M$ in order to check if given $3CNF$ formula is satisfable. The meaning is that $0^{kn}\in M$ does mean that each clause agree with some assigment (agreeing corresponds to satisfability)

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


# Question
Title: Lower bound on space of DFS keeping the running time linear
$\mathsf{DFS(G, u) \text{}}$, $G = (V,E)$

**Input** : A Directed graph $G$ and a source vertex $u$.

**Find** : Is $v$ reachable from vertex $u$ for all $v \in V$ ?

**Model of computation** : Word RAM , one can represent a vector $A\[1,\cdots ,n\]$ of elements from a finite alphabet $\Sigma$ using $n \lg |\Sigma| + O(\lg^2 n)$ bits, such that any element of vector can be read or written in constant time.

$\mathsf{DFS \text{}}$ (Depth first search) takes $O(m + n)$ time and $O(n\log n)$ bits of space . Other known results for DFS is $O((m + n ) \log n)$ time and space $O(n)$ bits ( see this paper) (please note that DFS in this paper have defined as two phase process 1) Forward phase 2) Backtack phase )

It is a open question that $\mathsf{DFS \text{}}$ can be done in $O(m + n)$ time and $O(n)$ bits of space. (see this paper)

How to prove the lower bound that for $\mathsf{DFS \text{}}$ if we want to keep the runtime $O(m + n)$, we cannot do better than $O(n)$ in terms of space ?

Thanks in advance.

# Answer
> 5 votes
The questions as stated seems to be beyond reach. Without the time constraint, a superlogarithmic space lower bound on your question would imply that $\mathsf{L} \neq \mathsf{NL}$, a famous conjecture in complexity theory.

What you are looking for is known as a *time-space tradeoff*, and these are not known for the RAM model, though similar results are known for restricted models such as the cell-probe model and comparison-based algorithms with memory (modeled as branching programs).

Time-space tradeoffs for reachability have been studied under the JAG model and its variants, which is a pebbling-based model. The best known time-space tradeoff, due to Edmonds and Poon, implies that polynomial time requires space roughly $\Omega(n/2^{O(\sqrt{\log n}})$, and this has been achieved by Barnes et al. in their paper A sublinear space, polynomial time algorithm for directed $s$-$t$ reachability. (The work of Edmonds and Poon is cited by Barnes et al.)

---
Tags: algorithms, complexity-theory, lower-bounds
---


title: Chomsky or Greibach Normal Form?

text:
# Question
Title: Chomsky or Greibach Normal Form?
I tried to solve this exercise:

*Discuss the normal forms (CNF or GNF) of a grammar with productions:*

$S\rightarrow BC | CB$

$B\rightarrow cB | c$

$C\rightarrow cC | \epsilon$

*Same request with the following grammar:*

$S\rightarrow BC | CB$

$B\rightarrow cB | c$

$C\rightarrow cC | c$

---

I applied the rules to convert a grammar into its normal form and I think that both are CNFs.

For the first grammar:

$S\rightarrow BC | CB|C'B|c$

$B\rightarrow C'B | c$

$C\rightarrow C'C | c$

$C'\rightarrow c$

For the second grammar:

$S\rightarrow BC | CB|TB|c$

$B\rightarrow TB | c$

$C\rightarrow TC | c$

$T\rightarrow c$

Is that correct?

# Answer
> 2 votes
A context-free grammar is in Chomsky normal form if all productions are of the form $A \to BC$ (where $B,C$ are not the starting symbol), $A \to a$, or $S \to \epsilon$, where $S$ is the starting symbol. A context-free grammar is in Greibach normal form if all productions are of the form $A \to a\alpha$, where $\alpha$ consists only of non-terminals (but not the starting symbol), or $S \to \epsilon$, where $S$ is the starting symbol.

Every context-free grammar has an equivalent context-free grammar in Chomsky normal form, and another one in Greibach normal form; there could be several equivalent context-free grammars in either normal form.

When you applied the rules to convert your grammars into normal form, you got Chomsky normal form *because the rules were designed for converting a given context-free grammar to Chomsky normal form*. You could follow other rules and get Greibach normal form.

---
Tags: context-free, formal-grammars, normal-forms
---


# Question
Title: Can the "divide" step in a merge sort be avoided?
So merge sort is a divide and conquer algorithm. While I was looking at the above diagram, I was thinking if it was possible to basically bypass all the divide steps.

If you iterated over the original array while jumping by two, you could get the elements at at index i and i+1 and put them into their own sorted arrays. Once you have all these sub-arrays (\[7,14\], \[3,12\], \[9,11\] and \[2,6\] as shown in the diagram), you could simply proceed with the normal merge routine to get a sorted array.

Is iterating through the array and immediately generating the required sub-arrays less efficient than performing the divide steps in their entirety?

# Answer
The confusion arises from difference between the *conceptual* description of the algorithm, and its *implementation*.

Logically merge sort is described as splitting up the array into smaller arrays, and then merging them back together. However, "splitting the array" doesn't imply "creating an entirely new array in memory", or anything like that - it could be implemented in code as

```
/*
 * Note: array is now split into  [0..n) and [n..N)
 */

```

i.e. no actual work takes place, and the "splitting" is purely conceptual. So what you suggest certainly does work, but logically you're still "splitting" the arrays - you just don't need any work from the computer to do so :-)
> 29 votes

# Answer
I guess what you mean is the bottom-up implementation. In the bottom up implementation you start from single cell elements an move upward by merging elements into larger sorted lists/arrays. Just reverse the arrows in your figure above starting from the middle array, i.e., one-element arrays.

Also, you may want to optimize the merge sort by dividing arrays until they reach some constant size, after which you simply sort them using for example insertion sort.

Otherwise, sorting without splitting array is not possible. In fact the gist of the Merge sort is dividing and sorting subarrays, i.e., divide-and-conquer.
> 11 votes

---
Tags: algorithms, sorting, efficiency, mergesort
---


# Question
Title: Definition of space complexity when algorithm cycles.
I'm reading side by side my class notes and Papadimitrious' Computational Complexity book. At this point they are talking about space complexity. They give rules for computing space employed in an algorithm that runs on a multi-tape Turing machine:

1. We count the cells used.
2. If we don't write in the input, this cells don't count.
3. If the output cells are written from left to right, they don't count.

The final requirement is expressed differently in Papadimitrious' and my notes. In the books it is written:

> The cursor of the input string does not wander off into the blank symbols after the end of the input. It is a useful technical requirement, but not necessary.

In my notes:

> In an algorithm where space is counted, there can exist computations that never end, but one can always transform the algorithm into another that doesn't cycle.

So how does one measure the space complexity of an algorithm that may cycle forever? Are this statement equivalent to each other?

# Answer
> 1 votes
> So how does one measure the space complexity of an algorithm that may cycle forever?

When we say that some language $L$ belongs to some complexity class it is assumed that a TM (algorithm) **decides** $x \in L$ in finite space and time amount. In other words, the TM/algorithm terminates, i.e. it may not cycle forever. However, an algorithm that loops forever may use finite space, but it still cannot decide.

But I don't understand the following statement

> In an algorithm where space is counted, there can exist computations that never end, but one can always transform the algorithm into another that doesn't cycle.

---
Tags: turing-machines, space-complexity
---


# Question
Title: Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?
Input: amount of variables (with minimum of $10$ since otherwise problem is unsolvable).

Output: unsatisfiable formula.

Restrictions:

1. Every clause contains exactly 3 variables.
2. Every clause differs by at least one variable. For example, a pair of clauses $(x\lor y\lor z)\land(x\lor \overline y\lor\overline z)$ is forbidden.
3. Every variable must be involved.
4. Removing any clause makes the formula satisfiable.

No set of clauses is given as input. Is this problem in $\mathsf{FP}$ or is it $\mathsf{NP}$-hard?

# Answer
> 2 votes
The smallest formula with $n=10$ can be written as follows:

$(x\_1\rightarrow(x\_2\rightarrow x\_3))\land(x\_1\rightarrow(x\_3\rightarrow x\_4))\land(x\_1\rightarrow(x\_4\rightarrow\overline{x\_2}))\land$ $(x\_1\rightarrow(\overline{x\_2}\rightarrow x\_5))\land(x\_1\rightarrow(x\_5\rightarrow x\_6))\land(x\_1\rightarrow(x\_6\rightarrow x\_2))\land$ $(\overline{x\_1}\rightarrow(x\_2\rightarrow x\_7))\land(\overline{x\_1}\rightarrow(x\_7\rightarrow x\_8))\land(\overline{x\_1}\rightarrow(x\_8\rightarrow\overline{x\_2}))\land$ $(\overline{x\_1}\rightarrow(\overline{x\_2}\rightarrow x\_9))\land(\overline{x\_1}\rightarrow(x\_9\rightarrow x\_{10}))\land(\overline{x\_1}\rightarrow(x\_{10}\rightarrow x\_2))$

It satisfies all of the restrictions.

As you can see, it is just two unsatisfiable 2-SAT formulas one of which is implied by $x\_1$ and another by $\overline{x\_1}$. We can add arbitrary amount of vertices to any of these implication chains, so, generating such formula for any $n\ge10$ can be done in linear time.

---
Tags: np-hard, satisfiability, boolean-algebra, 3-sat
---


title: Reduction and decidability

text:
# Question
Title: Reduction and decidability
Consider the following language: $$ L = \\{ \langle M \rangle \ |\ M \text { accepts } w \text { whenever it accepts } w^R \\}$$

I am trying to understand the following proof that this language $L$ is undecidable.

The proof proceeds by contradiction, by reducing to $L$ the language $A\_{TM}=\\{\langle M,w \rangle\mid M\text{ accepts }w\\}$ known to be undecidable. It goes as follows:

Suppose that $L$ is decidable, then there's a TM $M\_L$, that decides $L$

Thus we can build $M\_{ATM}$ to decide $A\_{TM}$ as follows:

1. Let $\langle M, w \rangle$ be an input for $M\_{ATM}$.
2. Construct a machine, $M\_1$ which on input $x$: Simulate $M$ on $w$; if $M$ rejects $w$, $reject$. If $M$ accepts $w$, $accept$ if $x=01$, $reject$ otherwise.
3. Simulate $M\_L$ on input $\langle M\_1 \rangle$.
4. $accept$ if $M\_L$ rejects. $reject$ otherwise.

Since $A\_{TM}$ is not decidable, we have a contradiction, which implies that $L$ cannot be decidable.

However there is a point of the proof I do not understand.

**My question is:** What happens if $M$ gets into a loop on some $w$?

# Answer
> 3 votes
In many problems like this, it's often a bad idea to base your construction on both acceptance and rejection. Try rewriting your $M\_1$ in this form

```
M1(x) =
   simulate M on w
   if M accepts w
      if x = 01
         accept

```

Now the important thing is that

1. If $M$ accepts $w$ (i.e., if $\langle M, w\rangle\in A\_{TM}$) then $L(M\_1)=\\{01\\}$.
2. If $M$ fails to accept $w$, *either by rejecting or by running forever*, then $M\_1$ will accept nothing, so $L(M\_1)=\varnothing$

Now if $L$ were decidable with decider $M\_L$, then you can use the decider and $M\_1$ to build a decider, $M\_A$, for $A\_{TM}$ as you suggested:

```
MA(<M>, w) =
   Construct M1 as above
   if ML accepts <M1>
      reject
   else if ML rejects <M1>
      accept

```

Now we have

1. If $M$ accepts $w$, then $L(M\_1)=\\{01\\}$ so $M\_L$ will reject $M\_1$ and hence $M\_A$ will accept $\langle M, w\rangle$.
2. If $M$ doesn't accept $w$, then $L(M\_1)=\varnothing$ so $M\_L$ will accept $M\_1$ and hence $M\_A$ will reject $\langle M, w\rangle$.

In short, $M\_A$ is indeed a decider for $A\_{TM}$, an undecidable language, meaning that $L$ must not be decidable.

# Answer
> 2 votes
In this reduction of $A\_{TM}=\\{\langle M,w \rangle\mid M\text{ accepts }w\\}$ to $L$, what matters in the construction of the Turing machine $M\_1$ is that the language accepted by $M\_1$ is $\\{01\\}$ iff $M$ accepts $w$, and is $\emptyset$ otherwise.

Whether $M$ does not halt on input $w$, or halts rejecting it, does not make any difference. In both cases, the language accepted by $M\_1$ is $\emptyset$, thus satisfyiing the definition for $L$. Hence $M\_L$ will accept $\langle M\_1 \rangle$, so that $M\_{ATM}$ will reject.

# Answer
> 1 votes
You are trying to prove that $L$ is undecidable by showing $A\_{tm}\le L$.

For this reduction to be valid, you need to convert each input $(\langle M \rangle, w)$ of $A\_{tm}$ into an input $\langle M\_1 \rangle$ (using your notations) for $L$ so that $$ (\langle M \rangle, w) \in A\_{tm} \quad\text{ iff }\quad \langle M\_1 \rangle \in L$$

Equivalently, such a reduction shows that if you can decide $L$ you will be able to decide $A\_{tm}$: simply you convert the input of $A\_{tm}$ to an equivalent input of $L$ and run $M\_L$ on it.

So the question that hides in your post, is how to convert the inputs. Let's see what happens in each case:

1. **case I**: $(\langle M \rangle, w) \in A\_{tm}$.
In this case $M\_1$ will just run $M$ on $w$ (which ends in an accepting state, and specifically, always halts), and then only accepts $x=01$. Therefore $M\_1$ is not in $L$.
2. **case II**: $(\langle M \rangle, w) \notin A\_{tm}$.
As you mention, there are 2 cases here: wither $M$ rejects $w$ or it never halts. In both cases, $M\_1$ never accept a single word: either it rejects *everything*, or it never halts (and then also no input is ever accepted). Therefore $M\_1$ is in $L$ (vacuously satisfying the requirement).

So this goes the opposite way from the "iff" statement I wrote above, but that's fine because the final decision of your $M\_{ATM}$ is the *opposite* of the decision of $M\_L$ on $M\_1$, which fixes this negaiton. So everything works fine, and the proof is valid. Makes sense?

# Answer
> 1 votes
Wrong solution ( based on the comment below )

> L={⟨M⟩ | M accepts w whenever it accepts $w^R$}. Proof by contradiction. Assume that L is decidable and let $R$ be a decider for it. We will construct decider $S$ for $A\_{tm}$, using $R$ as a subrouting. Note that $A\_{tm}$ = {`<M,w> | M is a TM and M accepts
>  w`}.
>
> ```
> S = on input <M,w>
> constructs M_w = on input x
> if x!=010 reject
> else run M on w
>  if M accepts w => accept
>  else reject
> Run R on M_w
> if R accepts => accept
> if R rejects => reject
>
> ```
>
> Note: if $M$ accepts $w$ then $L(M\_w)$ = {010} , $R$ ran on $M\_w$ will accept, therefore $S$ will accept. if $M$ rejects or loops on $w$ then $L(M\_w)$ = empty set , $R$ ran on $M\_w$ will reject, therefore $S$ will reject. We have built a decider for $A\_{tm}$, since we know that $A\_{tm} $ is undecidable our assumption was wrong =\> L is undecidable.

Edited Solution\>\>\>

L={⟨M⟩ | M accepts w whenever it accepts $w^R$}. Proof by contradiction. Assume that L is decidable and let $R$ be a decider for it. We will construct decider $S$ for $A\_{tm}$, using $R$ as a subrouting. Note that $A\_{tm}$ = {`<M,w>` | M is a TM and M accepts w\`}.

```
S = on input <M,w>
constructs M_w = on input x
run M on w
 if M accepts w => reject
 else  => accept
Run R on M_w
if R accepts => accept
if R rejects => reject

```

Note: if $M$ accepts $w$ then $M\_w$ will reject on all input $L(M\_w)$ = empty set, $R$ ran on $M\_w$ will accept, therefore $S$ will accept. if $M$ rejects or loops on $w$ then $L(M\_w)$ = {$\Sigma^\*$} , $R$ ran on $M\_w$ will reject , therefore $S$ will reject. We have built a decider for $A\_{tm}$, since we know that $A\_{tm} $ is undecidable our assumption was wrong =\> L is undecidable.

---
Tags: formal-languages, turing-machines, reductions, proof-techniques, undecidability
---


title: Is the language A decidable?

text:
# Question
Title: Is the language A decidable?
Is the language $A$ decidable ? Please help me get the proof right !!

$A = \\{ \langle M \rangle | M \text{ is } TM \text{ such that } L(M) \neq \Sigma^\* \\}$

My proof is by contradiction. Assume $A$ is decidable and let $R$ be decider for it. I will construct decider $S$ for $A\_{tm}$, using $R$ as a subroutine.

```
S = on input <M,w>
constructs M_w = on input x
 if x!=w accept
 else run M on w
  if M accepts => accept
  else => reject
run R on M_w
 if R accepts => reject
 if R rejects => accept

```

Note : If $M$ accepts $w$ then $L(M\_w) = \Sigma^\*$ , then $R$ ran on $M\_w$ will reject it, and $S$ will accept. If $M$ rejects or loops on $w$, $L(M\_w) \neq \Sigma^\*$, then $R$ ran on $M\_w$ will accept, and $S$ will reject. Therefore, we created a decider for $A\_{tm}$, but we know that $A\_{tm}$ is undecidable, our assumption was wrong =\> $A$ is undecidable .

# Answer
I don't understand how you call $R$ from $S$. The following is a possible solution.

Let's reduce $A\_{TM}$ (halting problem) to $\overline{A} = \\{ \langle M \rangle | M \text{ is } TM \text{ such that } L(M) = \Sigma^\* \\}$ instead of $A$, since decidability of $\overline{A}$ would imply decidability of $A$.

First note that $M\_\emptyset (\text{ TM accepting nothing )} \notin$ $\overline{A}$ and it is clearly that $\overline{A}$ is not empty since a TM machine simply accepting any string is in $\overline{A}$, so let's choose $M\_1$ from the set $\overline{A}$ and let $L\_1$ be the language recognizable by $M\_1$.

For any $\langle M, w \rangle$ construct a new TM $M'$

```
  M'(x)
   Simulate M on w
   If M accepts w then run M_1 on x
   If M_1 accepts x then ACCEPT

```

Now let's show the reduction:
$\langle M,w \rangle \in A\_{TM} \Rightarrow M \text{ accepts } w \Rightarrow M'$ accepts $x$ exactly when $M\_1$ accepts $x \Rightarrow L(M') = L\_1$ which implies $\langle M\_1 \rangle \in \overline{A}$. So we have obtained

$$\langle M,w \rangle \in A\_{TM} \Rightarrow \langle M' \rangle \in \overline{A}$$

Similarly, $\langle M,w \rangle \notin A\_{TM} \Rightarrow M \text{ does not accepts } w \Rightarrow M' \text{ accepts no string } \Rightarrow L(M') = \emptyset $ which implies $\langle M' \rangle \notin \overline{A}$. So we have obtained $$\langle M,w \rangle \notin A\_{TM} \Rightarrow \langle M' \rangle \notin \overline{A}$$

Now if $\overline{A}$ were decidable then on any input $\langle M, w \rangle$ we could construct $M'$ as above and decide if $M$ halts on $w$ by checking $\langle M' \rangle \in \overline{A}$.

Finally, the general case of the proof above is known as the Rice's theorem, which you could apply directly to prove that $A$ is not decidable.
> 0 votes

---
Tags: turing-machines, undecidability
---


# Question
Title: Logarithmic reduction to another LOGSPACE problem
For words of the same length $u = u\_1..u\_n, v = v\_1..v\_n$ over an alphabet $A$ let $$u \circ v = u\_1v\_1...u\_nv\_n$$

Prove that if $L$ over $A \times A$ in in LOGSPACE then $$L' = \\{uv : u \circ v \in L\\}$$ is also in LOGSPACE

My solution: We try to log-reduce $L'$ to $L$. So, I mean when a machine $M\_L$ tries to read an input then reducing function $f$ gives another input.

Let $I$ be an input tape, word $w = uv = u\_1..u\_nv\_1..v\_n, |w| = 2n$ and $w$ starts at 0th cell.

Now, we define $f$: $$ f(i) = \left\\{\begin{array}{lr} I\[i/2\] & \text{for } i \ even \\ I\[i/2+n\] & \text{for } i \ odd \end{array}\right\] $$

My doubts:

1. Is it ok?
2. I used in $f$ division. Is is possible in $LOGSPACE$?

# Answer
> 1 votes
You are asking two questions. I will only answer the one about division. Division can be done in logspace, as shown in this answer, which cites the relevant literature.

However, in your case you are interested in *division by 2*, which is easier than general division. I bet you can show yourself that numbers can be divided by 2 in logspace (assuming that they're represented in binary). This operation is known as *right shift*.

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


# Question
Title: Does there exist any work on creating a Real Number/Probability Theory Framework in COQ?
COQ is an interactive theorem prover that uses the calculus of inductive constructions, i.e. it relies heavily on inductive types. Using those, discrete structures like natural numbers, rational numbers, graphs, grammars, semantics etc. are very concisely represented.

However, since I grew to like the proof assistant, I was wondering whether there are libraries for uncountable structures, like real numbers, complex numbers, probability bounds and such. I am of course aware that one cannot define these structures inductively (at least not as far as I know), but they can be defined axiomatically, using for instance the axiomatic approach.

Is there any work that provides basic properties, or even probabilistic bounds like Chernoff bound or union bound as a library?

# Answer
The standard library of Coq has a section about real numbers. These are the classical real numbers, using the Dedekind completion. There are also results about complex numbers, I suppose there are several libraries, I happen to know this one. Note that there is also a lot of results for *constructive* real and complex numbers, C-CoRN is the reference.

Side note: you *could* also define (computable) real numbers inductively with some of the constructive axiomatics, for example using rational numbers from the Cauchy sequences or some constructive version of the least-upper-bound property. I am not sure how much inductive that this.

I know there are *some* people working on probabilities with Coq. Unfortunately I am not sure how advanced their works are. My guess is that there is likely no such specific result about Chernoff bound or union bound. (But it's just a guess)
> 7 votes

# Answer
Check this out! http://coq.io/opam/coq-markov.8.5.0.html. A library for Markov's inequality built on mathematical probability theory.
> 3 votes

---
Tags: probability-theory, coq, real-numbers, uncountability
---