# Question
Title: How to use structural induction to prove law on lists
I want to prove that the following equation holds using structural induction on (finite) lists

```
subs (map f xs) = map (map f) (subs xs)

where subs [] = [[]]                                          (subs.1)
      subs (x:xs) = subs (xs) ++ map (x:) (subs xs)           (subs.2)

      map f [] = []                                           (map.1)
      map f (x:xs) = f x : map f xs                           (map.2)

```

`:` is the cons operator and `++` the join operator on lists.

I'm using structural induction on `xs`, the base step for `[]` is easy to prove but I hit a wall when trying to solve the inductive step for `(x:xs)`

```
subs (map f) (x:xs)                                             (map.2)
subs (f x : map f xs)                                           (subs.2)
subs (map f xs) ++ map ((f x):) (subs (map f xs))               (hyp)
(map (map f) (subs xs)) ++ map ((f x):) (map (map f)(subs xs))

```

From here I couldn't find a way to proceed so I moved to the right-hand side of the equation and I kind of found a way to find a "proof" but something tells me that it's bogus

```
map (map f) (subs (x:xs))                     (subs.2)
map (map f) (subs xs ++ map (x:) (subs xs))   (generalise term)
map (map f) ys                                (hyp)
subs (map f ys)                               ???
subs (map f (y:ys))
□

```

My reasoning here is: `(x:xs)` is a list with at least length 1, it should be legal to generalise `subs xs ++ map (x:) (subs xs)` as either `(y:ys)` or `ys` (because `(x:xs)` is not empty) so I chose the latter first to be able to use the induction hypothesis and after that I rewritten `ys` as `(y:ys)` to establish the case.

Does this make any sense at all? If not, could anybody show me the right approach to tackle this proof?

# Answer
You'll want a helper lemma to make this endeavor more digestible.

---

## Notations for `map` and `subs`:

I'm going to condense the `map` notation a bit so that we can express it as the binary operator $f \diamond l = \mathrm{map} ~ f ~ l$. Similarly, we will express the `subs` as a unary operation $\lfloor\\!\\!\lfloor l \rfloor\\!\\!\rfloor = \mathrm{subs} ~ l$.

This might seem terse at the moment, but it's useful to visually capture a "commutativity" property we will illustrate in a moment that sits at the core of the proof of this extensional equation.

### Reformulation of the problem:

We want to show that $$ \lfloor\\!\\!\lfloor f \diamond l \rfloor\\!\\!\rfloor = (f \diamond) \diamond \lfloor\\!\\!\lfloor l \rfloor\\!\\!\rfloor $$

which basically states that if we try to hoist the $f$ outside of the brackets, then we have to turn it into a map.

Now, if we follow your original blueprint, your inductive hypothesis establishes that $$ \lfloor\\!\\!\lfloor f \diamond x ::l \rfloor\\!\\!\rfloor = (f \diamond) \diamond \lfloor\\!\\!\lfloor l \rfloor\\!\\!\rfloor +\\!\\!\\!+ ~(f ~x ::) \diamond ((f \diamond) \diamond \lfloor\\!\\!\lfloor l \rfloor\\!\\!\rfloor) $$

In order for this proof to proceed, you need to tame the term on the righthand side of the concatenation. But what would you want it to look like?

Well, recall that maps distribute into concatenations: $$ (f \diamond l\_1) +\\!\\!\\!+ ~(f \diamond l\_2) = f \diamond (l\_1 +\\!\\!\\!+~ l\_2) $$

which suggests that we might be able to get our equation into an amenable form if we can rewrite the second term so that it is of the form $(f \diamond) \diamond \cdot$.

Here's where our helper lemma comes in to save the day:

**Lemma ("Commutativity")**:You have to use finger quotes when you read the name of this lemma out loud. $$ (f ~x ::) \diamond ((f \diamond) \diamond l) = (f \diamond) \diamond ((x ::) \diamond l) $$ *Proof:* Structural induction on $l$. This is actually a pretty easy proof, so I'll leave it to the reader™. However, the core of this proof is essentially showing that \begin{align\*} (f~x ::) \diamond ((f \diamond) \diamond a :: \[...\]) &= (f~x ::) \diamond ((f \diamond a) :: \underbrace{((f \diamond) \diamond \[...\])}\_{\text{induction hypothesis}}) \\ &= \underbrace{(f~x :: f \diamond a)}\_{\text{map distributivity}} :: (f~x ::) \diamond((f \diamond) \diamond \[...\])) \\ &= (f \diamond (x :: a)) :: (f~x ::) \diamond((f \diamond) \diamond \[...\])) \\ & \text{discharge the induction hypothesis} \\ &= (f \diamond (x :: a)) :: (f \diamond) \diamond ((x ::) \diamond \[...\]) \\ & \text{distributivity} \\ &= (f \diamond) \diamond ((x :: a) :: ((x ::) \diamond \[...\])) \\ & \text{distributivity} \\ &= (f \diamond) \diamond ((x ::) \diamond (a :: \[...\])) \end{align\*} which concludes the proof of the lemma. $\square$

### Finishing your inductive proof:

Once we have this gem, we can continue your structural induction proof.

\begin{align\*} \lfloor\\!\\!\lfloor f \diamond x ::l \rfloor\\!\\!\rfloor &= (f \diamond) \diamond \lfloor\\!\\!\lfloor l \rfloor\\!\\!\rfloor +\\!\\!\\!+ ~(f ~x ::) \diamond ((f \diamond) \diamond \lfloor\\!\\!\lfloor l \rfloor\\!\\!\rfloor) \\ & \text{by the lemma} \\ &= (f \diamond) \diamond \lfloor\\!\\!\lfloor l \rfloor\\!\\!\rfloor +\\!\\!\\!+ ~(f\diamond) \diamond ((x ::) \diamond \lfloor\\!\\!\lfloor l \rfloor\\!\\!\rfloor) \\ & \text{by distributivity of map} \\ &= (f \diamond) \diamond (\lfloor\\!\\!\lfloor l \rfloor\\!\\!\rfloor +\\!\\!\\!+ ~ (x::) \diamond \lfloor\\!\\!\lfloor l \rfloor\\!\\!\rfloor) \\ & \text{by the definiton of } \lfloor\\!\\!\lfloor x :: l \rfloor\\!\\!\rfloor \\ &= (f \diamond) \diamond \lfloor\\!\\!\lfloor x :: l \rfloor\\!\\!\rfloor \end{align\*}

which satisfies your goal.

---

The equational acrobatics we've just performed seems a bit excessive, which is why I'm willing to bet that there's some elegant fusion law, recursion scheme, or some other representation (probably some categorical law given the nature of the problem) that nicely unwraps this proof. Unfortunately, AFAIK, I'm not aware of more elegant approaches. While this is a valid proof, it's somewhat unsatisfying. It is as much of a proof of this theorem as my performances of Taylor Swift is considered entertainment: it is technically correct, just not in the way that I intend it to be.
> 4 votes

---
Tags: proof-techniques, induction, software-verification, lists
---


title: Lower bound for $k$-sorting an array

text:
# Question
Title: Lower bound for $k$-sorting an array
This is exercise 2 of the lecture note by Jeff Erickson on decision tree lower bounds.

> We say that an array $A\[1 \ldots n\]$ is $k$-sorted if it can be divided into $k$ blocks, each of size $n/k$ (we assume that $n/k$ is an integer), such that the elements in each block are larger than the elements in earlier blocks and smaller than elements in later blocks. The elements within each block need not be sorted.
>
> (a) Describe an algorithm that $k$-sorts an arbitrary array in $O(n \log k)$ time.
> (b) Prove that any comparison-based $k$-sorting algorithm requires $\Omega(n \log k)$ comparisons in the worst case.
> (c) Describe an algorithm that completely sorts an already $k$-sorted array in $O(n \log(n/k))$ time.
> (d) Prove that any comparison-based algorithm to completely sort a $k$-sorted array requires $\Omega(n \log(n/k))$ comparisons in the worst case.

---

The first problem can be solved by modifying the quicksort algorithm. However, I am stuck with the second problem which asks for a lower bound. My attempt is to use the decision tree technique. I think the number of leaves of the decision tree is at least $((\frac{n}{k})!)^{k}$. Therefore, the height of the decision tree must be $$ H \ge \log ((\frac{n}{k})!)^{k} = k \log (\frac{n}{k})! = \Omega(k \frac{n}{k} \log \frac{n}{k}) = \Omega(n \log \frac{n}{k}),$$ which is not the desired result $\Omega(n \log k)$.

What is wrong with my argument? And how to establish the lower bound $\Omega(n \log k)$?

# Answer
From the result of $k$-sorting an array you can tell which elements of the original array were the $n/k$ smallest, the $n/k$ largest, and which belong to each of the other $k-2$ blocks of $n/k$ elements in between. In particular, there are at least $\binom{n}{n/k,\ldots,n/k}$ different leaves, which works out to $\frac{n!}{(n/k)!^k} = \exp \Theta(n\log k)$. This gives you the correct lower bound.

What you calculated is the number of different ways to completely sorted a $k$-sorted permutation. Therefore your lower bound is for sorting a $k$-sorted permutation, and for this task your lower bound is tight: a $k$-sorted permutation can be sorted in $O(n\log (n/k))$.
> 3 votes

---
Tags: algorithms, sorting, lower-bounds
---


title: Explaining regular expressions

text:
# Question
Title: Explaining regular expressions
folks. My question is about explaining the each step of regular expressions. The task is to find the regular expression that **contains 101 as a substring**. I already know that the regular expression for this is

$$ (0 + 1)^\*101(0 + 1)^\*. $$

The question is that how we should show each step for explaining the regular expressions.

# Answer
> 1 votes
You have to show two things:

1. Every word in the language of your regular expression contains 101 as a substring.
2. Every word containing 101 as a substring belongs to the language of your regular expression.

You can prove both of these using the definition of the language of a regular expression. It is a bit tiring but otherwise requires little creativity.

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


# Question
Title: Intuition why $ L= \{\langle M \rangle| \ L(M)=\Sigma ^* \}\notin RE $
I know how to prove it by reduction, but I couldn't find an explanation why it is true.

$\langle M \rangle$ represents the encoding of a turing machine $M$.

# Answer
The class RE contains all languages $L$ which can be expressed in the form $$ x \in L \Longleftrightarrow \exists y \\, P(x,y), $$ for some computable predicate $P$.

Your language can be expressed in the following way: $$ \langle M \rangle \in L \Leftrightarrow \forall x \exists t \\, \text{"$M$ halts on $x$ after $t$ steps"} $$ The quoted predicate is computable. This puts your language in $\Pi\_2$, a level on the arithmetical hierarchy. There seems to be no natural way to come up with a simpler expression (less quantifiers), and this is why, intuitively, the language is not r.e. This kind of intuition usually works – write down an expression for your language in the most natural way, and this usually puts it in the correct level of the arithmetical hierarchy.

Your language is in fact $\Pi\_2$-complete – every language in $\Pi\_2$ can be reduced to it. Indeed, suppose that $$ x \in L' \Longleftrightarrow \forall y \exists z \\, P(x,y,z), $$ where $P$ is computable. Given $x$, you can construct a Turing machine which on input $y$, goes over all $z$ in parallel, determines the value of each $P(x,y,z)$, and if it ever finds a value of $z$ such that $P(x,y,z)$ is true, it halts. This construction gives a reduction from $L'$ to your language.

Since your language is $\Pi\_2$-complete, we know that it is not in $\Sigma\_1$ (another name for RE), since the arithmetical hierarchy is strict. This means that there is no way to describe the language using fewer quantifiers (or using $\exists\forall$ rather than $\forall\exists$).

Your language is usually known as TOT, the language of all total Turing machines.
> 2 votes

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


# Question
Title: Is the language $L=\{a^nb^m \mid n>2^m\}$ context-free?
I cannot go on with this exercise:

> Determine whether $L = \\{a^nb^m \mid n \> 2^m \\}$ is context-free.

Let's suppose that $L$ is context-free. According to the pumping lemma, there exists $N \> 0$ such that every $z \in L$ of size at least $N$ has a decomposition $z = uvwxy$ such that

1. $|vwx| \leq N$.
2. $|vx| \geq 1$.
3. For all $i \geq 0$, $z\_i = uv^iwx^iy$ is in $L$.

Let's use $z= a^{2^N+1}b^N$.

Then $|z| = 2{^N+1} +N \> N$ and $v= a^h$ and $x= b^k$ with $1 \leq h+k \leq N$.

So $z\_i = a^{2^N+1}a^{h(i-1)} b^{N-k}b^{k(i-1)}$.

So if there exists $i \> 0$ such that $2^N+1+h(i-1) \leq 2^{N+(i-1)k}$, then $z\_i \notin L$.

How can I go on to show that $L$ is not context-free?

# Answer
According to Parikh's theorem, if your language were context-free, then the set S = $\\{(n,m) : n \> 2^m\\}$ would be semi-linear. Every linear subset of $S$ has a constant second coordinate, as we show below. Therefore you need an infinite number of linear sets to cover $S$, showing that it is not semi-linear.

It remains to show that every linear subset of $S$ has constant second coordinate. Indeed, consider any linear subset of $S$. By definition, such a subset is of the form $u\_0 + \mathbb{N} u\_1 + \cdots + \mathbb{N} u\_r$. By assumption there exists some $i \> 0$ such that $u\_i = (a,b)$, where $b \neq 0$. Let $u\_0 = (n',m')$. It is not hard to check that for some $t$, $n' + at \leq 2^{m' + tb}$, since the left-hand side grows linearly, whereas the right-hand side grows exponentially. This contradicts the fact that the subset is a subset of $S$.
> 3 votes

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


# Question
Title: Are there decidable problems that are reducible to undecidable problems?
I've seen a question asking if $A \le\_m B$, then if $A$ is decidable, $B$ is also decidable. My initial intuition is that this is not the case, and that there are decidable problems that are reducible to undecidable problems. While I am not sure if this is completely correct, or even how to prove this if it is correct, I am thinking a decidable problem could be reduced to a recognizable, undecidable problem because a polynomial time verifier would work on a decidable problem. Is this a correct idea?

# Answer
Any decidable problem can be reduced to the halting problem. Take a machine $M$ that decides some language $L$. Now produce a new Turing machine $M'$ that behaves identically to $M$ except that, if $M$ rejects, $M'$ loops forever. Now, $M'$ halts on input $x$ if, and only if, $x\in L$.

More generally, every decidable problem can be reduced to *every* undecidable problem. Let $Z$ be some undecidable language. We know that $Z\neq\emptyset$ and $Z\neq\Sigma^\*$, since both of those languages are trivially decidable. Therefore, there are strings $z^+\in Z$ and $z^-\notin Z$. Now take any decidable language $L$. Since $L$ is decidable, the function $$ f(x) = \begin{cases}z^+&\text{if }x\in L\\z^-&\text{if }x\notin L\end{cases}$$ is computable, and it is a reduction from $L$ to $Z$.

> I am thinking a decidable problem could be reduced to a recognizable, undecidable problem because a polynomial time verifier would work on a decidable problem. Is this a correct idea?

I think you're confusing the set of recognizable languages with **NP**. A recognizable language has a computable verifier but the verifier doesn't necessarily run in polynomial time (and the time hierarchy theorem says that there are languages whose verifiers can't run in polynomial time). It's true that every decidable problem has a computable verifier (because being able to decide the problem essentially means that you can verify a given answer by just computing the correct answer and comparing) but that doesn't give you a *reduction*. Rather, it proves that every decidable language is itself recognizable.
> 4 votes

---
Tags: reductions, undecidability
---


# Question
Title: Why the language of unary primes isn't regular
I have some difficulties proving that the language of unary primes ($L=\\{1^p\mid p\text{ is prime}\\}$) is not regular using the pumping lemma. Any suggestions?

# Answer
> 3 votes
This is one of the more difficult common applications of the pumping lemma, so I'll give you an outline to get you started.

Suppose $L$ is regular and let $k$ be the pumping length. Let $p$ be a big enough prime* so $1^p\in L$, and write $a=1^r1^s1^t$, with $r+s\leq k$ and $s\geq 1$, so $t=p-r-s$. You need to find some $n$ such that $1^r(1^s)^n1^t\notin L$, i.e., such that $r+ns+t$ is not prime, which you can show by writing it as a product of two factors, both strictly bigger than $1$.

* You'll certainly need $p\>k$ to apply the pumping lemma, but you might need it to be bigger still, to guarantee that the factors are bigger than $1$.

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


# Question
Title: Having problem understanding the formal definition of NP
So I'm having a tad bit of a problem deciphering the formal definition of NP. In my text book (Algorithm Design, Tardos et al) it says that a problem $X$ belongs to $NP$ iff;

* there exists a "certificate" string $t$ such that $|t| \le p(|s|)$ for a polynomial function $p$ and an input string $s$.
* there exists an *efficient certifier* $B$ that takes $s$ and $t$ as inputs and has polynomial time complexity.

I'm having a hard time understanding this problem in a more practical sense. Say for example I had to verify a solution for a Graph Coloring problem. Then I would take the graph $G = (V, E)$ and the number of allowed colours $K$ as input (the problem instance) aswell as the proposed solution (Let's call it $S$) that consists of the coloring of the graph $G$. In this example, what would be $s$ and what would be $t$?

# Answer
> 8 votes
For Graph colouring problem

**Input** : A graph $G(V,E)$ and $k$.

**Decide** : Is $G$ $k$-colourable?

**Certificate** : A map $\phi : V \mapsto C $, where $C = \\{R,B,Y,\cdots ,P\\}$ is the set of colours and $|C| = k$.

For example for any $v \in V$, $\phi(v) = Y$ means $v$ has assigned color $Y$.

**Example**: let complete graph $K\_4 (\\{v\_1,v\_2,v\_3,v\_2\\},E)$ is input graph and $k=4$ i.e. is it 4-colorable? A possible certificate in this case is $\\{v\_1(R),v\_2(B),v\_3(Y),v\_4(P)\\}$,($v\_1(R)$ means vertex $v\_1$ has color $R$), which is polynomial in input size.

Now you can see that the size of $|\phi| \le p(|G|)$, where $|G|$ is a input graph size. As you have given a map $\phi$, now you can verify in polynomial time whether colouring is valid or not.

# Answer
> 3 votes
Following the notation of the definition that you provide

* $s$ is the graph input $G=(V,E)$ and the number $K$ of the allowed colors *encoded* represented in some form of appropriate encoding
* $t$ is the proposed solution to the original problem for the input $s$. A coloring for that graph.

Therefore a verifier is an efficient algorithm that will take as inputs $s$ and $t$ and will decide in reasonable amount of time if $s\in X$, that is, if the suggested coloring is permitted by the problem statement.

---
Tags: np, decision-problem, p-vs-np
---


# Question
Title: Finding missing range in multidimensional domain
Let's suppose that I have a monodimensional numeric domain and a list of ranges in this domain defined as

```
class Range {
    int lowerBound;
    int upperBound;
}

```

then it's trivial to check if the union of the `List<Range>` is covering the entire domain. However in case of a bidimensional domain I have a `List<Pair<Range>>` and I'm no longer able to figure out if my rectangles (bidimensional ranges) are covering the entire area.

For example suppose that I have these ranges:

```
pair{ range{0, 7}, range{0, 5} },
pair{ range{7, 10}, range{0, 7} },
pair{ range{0, 5}, range{5, 10} },
pair{ range{5, 10}, range{7, 10} }

```

covering the domain as shown below.

How can I know that part of the domain isn't covered? (gray area in the picture). In other words is there an algorithm or a data-structure allowing to find if there exists at least one point in that domain that is not included in any of the rectangles? Is this solution also extensible to the n-dimensional case?

# Answer
This problem is known in computational geometry as Klee's measure problem.

The solution to this problem in 2D case is based on an approach known as Sweep Line Algorithm and is know as *Bentley's algorithm*.

Conceptually, it is as easy as sweeping the plane by a vertical line from left to right. An intersection of a vertical line with a set of rectangles is a set of one-dimensional ranges. That way, a two-dimensional problem is reduced to $O(N)$ one-dimensional problems.

Here is an overview:

1. Represent each rectangle as a pair of vertical ranges. One range on the left-hand side of it and one range on the right-hand side of it.
2. Sort vertical ranges by their $x$ coordinate. That should take $O(N \log N)$ time.
3. Scan the resulting $2N$ vertical ranges in increasing order of $x$ coordinate while maintaining a set of active ranges. When encountering a left-hand side of the rectangle the corresponding range is added to the set, crossing a right-hand side removes the corresponding range.
4. As you finish processing updates to the set at the given $x$ coordinate verify that the current set of active ranges covers your $y$ range completely.

An efficient implementation of this algorithm maintains a set of ranges in a data structure that supports $O(\log N)$ update and query operations. It can be implemented by building a *Segment Tree* for all different $y$ coordinates and maintaining a total covered range in that segment tree.

It gives an overall $O(N \log N)$ complexity for a 2D algorithm.

This algorithm can be generalized to higher dimensions with $O(N^{d - 1} \log N)$ complexity. However, there are better algorithms for $d \> 3$. You can find references in the Wikipedia article for Klee's measure problem.
> 2 votes

# Answer
If they are not overlapping you could calculate the area of the rectangles and check to see if the sum is less than the area of the domain.

Since they can overlap the only thing I can think of is to convert it to monodimensional view. In your example you have 11 points in each row so you could transform it to something like this:

```
pair{ range{0, 7}, range{0, 5} } ->
    range{0, 7},
    range{11, 18},
    range{22, 29},
    ...
    range{55, 62},
pair{ range{7, 10}, range{0, 7} } ->
    range{7, 10},
    range{18, 21},
    range{29, 32},
    ...
pair{ range{0, 5}, range{5, 10} }, ->
    ...
pair{ range{5, 10}, range{7, 10} } ->
    ...

```

Obviously not the most efficient approach but should work.
> 0 votes

---
Tags: graphs
---


# Question
Title: Finding the dichotomy that maximizes information gain for a classifier?
Suppose that $\Omega$ is a finite probability space,with measure $P$ (we can take $P$ uniform). Let $C \in \\{\pm 1 \\}$ be a random variable on $\Omega$, the classifier. Let

$$H(C) = H(C, \Omega, P) = \sum\_{i \in \pm 1} P(C = i) \log P(C = i)$$

be the entropy of $C$.

For a random variable $Y$ on $\Omega$ and $r \in \mathbb{R}$, define the level set $\\{Y = r\\} = V\_r$, and define

$$H(C | Y) = \Sigma\_{r \in \mathbb{R}} P(Y = r) H(C|\_{V\_r}, V\_r, P\_{V\_r})$$

where $P\_{V\_r}(B) = P(B \cap V\_r) / P(V\_r)$ is a measure on $V\_r$. $H(C|\_{V\_r}, V\_r, P\_{V\_r})$ is the entropy of the random variable restricted to the the subset $V\_r$, with the conditional probability measure.

As in a decision tree classifier, I want to determine the subset $A \subset \Omega$ that maximizes $H(C) - H(C|1\_A)$. That is, I want to maximize the information gain. What is the "best" algorithm for doing so? What is the complexity of this question? Are there good probabilistic algorithms ?

Some computation allows one to reformulate this as finding the subset $A$ that maximizes

$$\sum\_e \sum\_{i = \pm 1} P(C^i \cap A^e) \log(P(C^i \cap A^e)) + \sum\_e P(A^e) \log P(A^e),$$

provided we let $A^e$ mean $A$ or $A^c$, and $C^i = \\{C = i\\}$.

# Answer
> 2 votes
As in the discussion, there are too many "features" for this to be in interesting question. In particular, letting $A = C^{-1}(1)$, the set of positive examples, then $H(C|A) = H(C|C) = 0$ so information gain is $H(C)$, which is maximal.

This is obvious in retrospect, in order to decrease the entropy maximally, make $C$ deterministic on $A$ and $A^c$.

For decision trees, the point is that we have a limited collection of features, specifically excluding C, to split our data set around.

---
Tags: optimization, machine-learning, probability-theory, information-theory, entropy
---


# Question
Title: Algorithm for choosing unique options with least overall cost
# Problem And Question

I am looking for pointers for an efficient algorithm for the following problem.

It is hard to explain without some data so first I will provide some example data:

```
Destination 1:
   Source 1: Cost 26
   Source 2: Cost 32
   Source 3: Cost 98
   Create New Source: Cost 100
Destination 2:
   Source 1: Cost 12
   Source 2: Cost 99
   Source 3: Cost 51
   Create New Source: Cost 88
Destination 3:
   Source 1: Cost 55
   Source 2: Cost 31
   Source 3: Cost 76
   Create New Source: Cost 99

```

I need to choose one of the sources for each destination, so that each source (excluding 'create new source', which can be used as many times as required) is used **zero or one times**, and the **overall cost is low**.

I do not need (although it would be nice) an algorithm that produces the absolute lowest cost, because I imagine this would require brute forcing. Instead, I just need an algorithm that is rather more efficient than blindly using source $n$ for destination $n$.

# Example Output And Constraints

The above data was actually chosen completely at random, but the following general rules apply to the data:

* It will be very likely that, excluding the 'Create new source' option, the amount of sources will be equal to the amount of destinations.
* It will be very likely that the cheapest option for destination $n$ will be to use source $n$.
* It will be very likely that the cost of creating a new source will be one of highest costing options.
* The example data above uses 3 sources, therefore there are $(3+1)^{3}=64$ total options, and as such, the solution is brute-forcible. At the time of writing, I am actually currently working with 33 sources and counting, there the brute forcing the $(33+1)^{33}=3.45... × 10^{50}$ options is not feasible.

For the above data, the following costs are generated:

```
/---------------+---------------+---------------+------------+--------\
| Destination 1 | Destination 2 | Destination 3 | Total Cost | Valid? |
+---------------+---------------+---------------+------------+--------+
| Source 1 (26) | Source 1 (12) | Source 2 (31) |         69 |  FALSE |
| Source 2 (32) | Source 1 (12) | Source 2 (31) |         75 |  FALSE |
| Source 1 (26) | Source 1 (12) | Source 1 (51) |         93 |  FALSE |
| Source 2 (32) | Source 1 (12) | Source 1 (55) |         99 |  FALSE |
| Source 1 (26) | Source 3 (51) | Source 2 (31) |        108 |  TRUE  |
\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/

```

Therefore

* Destination 1 should use Source 1.
* Destination 2 should use Source 3.
* Destination 3 should use Source 2.
* *In actual fact, blindly using source $n$ for destination $n$ with this data actually has a cost of 201, almost double the best choice, and is ranked 15th of the 24 valid solutions.*

# Background To The Problem

I am working with a series of playlists, which when combined form one master playlist. Each playlist consists of a title in the format of (Master Playlist - Part $n$) and a list of items. These playlists are stored on a server.

The program I have written locally calculates the new state the master playlist needs to be in, splits it up with rules that are beyond the context of this question, and then starts making API calls to update the state of the playlists on the server accordingly.

The operations that can be done are

* Create a new empty playlist, giving it a name in the process.
* Delete an unwanted playlist, and any items inside.
* Add an item to an existing playlist.
* Remove an item from an existing playlist.
* Re-order an item to a new position in the playlist it is already in.
* Rename a playlist.

In the programs current form, for each local playlist part $n$, it will fetch the server state of playlist part $n$, work out whether it is cheaper to delete+recreate or add+remove, and then proceed accordingly.

This is not efficient because, using the above example, it may be much cheaper for local playlist part 2, to take the server playlist part 3, rename it, and modify it, and for local playlist part 3 to do the same for server playlist part 2.

As I already need to fetch all the playlist parts from the server, I am easily able to calculate the amount of API operations it would take to get each of the server playlists into the state required for each of the local playlists. This results in a cost table like at the top of this question, and leads on to the actual problem above.

# Footnote

*Sorry if question is too subjective, or if I should have posted this on a different stack exchange site, or if I've gone into a bit too much detail. I'm worried I may have done all three.*

# Answer
> 4 votes
This is an instance of the assignment problem. There are polynomial-time algorithms, e.g., the Hungarian algorithm. See also .

The one twist in your problem statement is the "create new source". We can model this in the assignment problem by adding $N$ extra sources, one per destination. The $i$th extra source is connected (only) to the $i$th destination. Thus, "creating" a source for destination $i$ is equivalent to connecting it to the $i$th extra source. In other words, instead of treating it as cost 100 to create a new source for destination 1, just eagerly create a new source for destination 1, and treat it as costing 100 if destination 1 uses that source (and no other destination is allowed to use that source; i.e., the cost is $\infty$ for all other destinations).

# Answer
> 3 votes
Without the creation of additional source, your problem seem very close to an assignment problem. Namely, let $n$ be your number of destination and sources, $x\_{ij}$ a $\\{0,1\\}$ variable that is one if Destination $i$ is assigned to source $j$, and $C(i,j)$ the cost of affecting source $j$ to destination $i$. Then you want to solve $$Min\_{x\_{ij}} \sum C(i,j) x\_{ij} $$ under the constraints $$\sum\_{j=1}^n x\_{ij}=1$$ $$\sum\_{i=1}^n x\_{ij}=1$$ $$x\_{ij} \in \\{0,1\\}$$ which can be solved efficiently in Polynomial time by the so-called Hungarian algorithm. The two constraints ensure that one source go to one and only one destination.

---
Tags: algorithms, optimization, time-complexity
---


# Question
Title: Using landmark points on the face for face recognition
I am currently working in area of computer vision for my master's thesis and am trying to use distances between landmark points on the face for recognition.

My question is this: What landmark points should I use for measuring distances between landmarks? And, since distance is dependent on scale, what ratios of distances should I take?

# Answer
> 0 votes
I propose reading this answer in stackoverflow for "how to apply face keypoint to face recognition?"

But specifically for this question for using landmark point you should first normalize some criteria in all face. for example you can resize all faces into the same eye distance, so all of them will have the same eye distance and then choose some landmark points and calculate their distance as a feature. But I highly recommend that landmark distances are NOT a good feature due to their variable position when face pose changes. Another approach can be using them for face normalization for other types of feature extraction.

---
Tags: machine-learning, image-processing, computer-vision, facial-recognition
---


# Question
Title: Any problem solved by a finite automaton is in P
After my Theory of Computation class today this question popped in my mind: If a problem can be solved by a finite automaton, this problem belongs to P.

I think its true, since automata recognize very simple languages, therefore all these languages would have polynomial algorithms to solve them. Thus, is it true that any problem solved by a finite automaton is in P?

# Answer
Yes, it is true. In terms of complexity classes, $$ \text{REG} \subseteq \text{P}, $$ where $\text{REG}$ is the class of regular languages (i.e., problems that can be solved by a finite automaton). More specifically, $$ \text{REG} \subseteq \text{DTIME}(n), \tag{\*} $$ and $\text{DTIME}(n)$ is a strict subset of $\text{P}$ by the time hierarchy theorem.

The proof of (\*) is as follows: for any problem in $\text{REG}$, there is a DFA which solves it. Convert that DFA to a Turing machine with the same states and transition function, which always moves to the right until it sees a blank, and then accepts or rejects. This Turing machine always halts in time exactly $n$.

---

It's also worth mentioning that $$ \text{REG} = \text{DSPACE}(0) = \text{DSPACE}(k)$$ for any fixed constant $k$.
> 16 votes

# Answer
Yes, this is true. For every such problem there is a DFA that decides the language, and checking if a word is accepted by a DFA can easily be done in time linear in the length of the word.
> 8 votes

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


# Question
Title: Overfitting in Machine Learning Algorithms
I am new in the ML. I know that overfitting is memorizing the data while training. Like in Neural Network, if we make lots of layers and lots of hidden nodes, we can memorize all the data, but it can be bad because train data would not cover the whole space.

Like this, is there any way to overfit in SVM and Logistic Regression? Since they are linear algorithms, they cannot be something curvy, I guess, so I am guessing the answer would be no. But I am not sure.

Any help is appreciated.

# Answer
> 2 votes
Yes, they can overfit too. Overfitting is especially a risk when the number of features is much larger than the number of samples in the training set.

# Answer
> 1 votes
As D.W. points out, in principle every machine learning algorithm can overfit a finite data sample provided you give it enough flexibility and degrees of freedom, e.g., by adding layers or additional features.

However, different methods will be more or less prone to overfitting, and their tendency to overfit is typically studied by theoretical notions such as Rademacher complexity or the Vapnik-Chervonenkis dimension, that roughly speaking characterizes the maximal number of points that an algorithm can perfectly fit for sure.

---
Tags: machine-learning, neural-networks, svm
---


title: Rice–Shapiro theorem example

text:
# Question
Title: Rice–Shapiro theorem example
Rice-Shapiro theorem is:

> Let $Γ$ be a set of computable functions such that the set $R\_Γ$ is recursively enumerable. We have $f ∈ Γ$ if and only if there exists a finite function $θ ∈ Γ$ such that $θ ⊆ f$.

If $Γ$ is singleton set, for example $Γ = \lbrace ϕ\_{10}\rbrace$ then $R\_Γ = \lbrace 10 \rbrace$ and is recursively enumerable, but $Γ$ does not satisfy:

$f ∈ Γ$ if and only if there exists a finite function $θ ∈ Γ$ such that $θ ⊆ f$.

Where I have made a mistake?

# Answer
The flaw is that $R\_\Gamma$ includes not just the natural number $10$, but any natural number which gives rise to the same partial recursive function. It will be infinite, and not recursively enumerable.

In general, for any partial recursive function $f$ you can think of, there will be many Godel numbers which describe it. In other words, many partial recursive function *descriptions* result in the same actual *function*. If you are more familiar with Turing machines, there will always be many different Turing machines which compute the same abstract function or language.

**In summary:** $\Gamma$ is any set of functions. However, $R\_\Gamma$ is the set of natural numbers which *encode* that function. In your case, for $\Gamma = \\{\phi\_{10}\\}$, $R\_\Gamma$ is the set of natural numbers which encode the same function as $10$, and this set is not recursively enumerable.
> 1 votes

---
Tags: computability
---


# Question
Title: Local type argument synthesis when type variable does not appear in arguments
I am implementing the techniques described in the classic Local Type Inference paper. Specifically, I am implementing the type argument synthesis algorithm from section 3.

My algorithm seems to mostly work, but it doesn’t seem to produce reasonable results when a quantified type variable appears in the *result* of a function, but not in its arguments. For context, I’ve reproduced the $\text{App-InfAlg}$ rule here:

$$ \dfrac{\begin{align}\tt\Gamma \vdash f \in All(\overline{X}) \overline{T} \rightarrow R \qquad &\tt \Gamma \vdash \overline{e} \in \overline{S} \qquad \lvert\overline{X}\rvert \> 0\\ \tt\emptyset \vdash\_\overline{X}\overline{S} \<: \overline{T} \Rightarrow \overline{C}&\qquad\tt \sigma \in \bigwedge \overline{C} \Downarrow R \end{align}} {\tt\Gamma \vdash f(\overline{e}) \in \sigma R \Rightarrow f\[\sigma \overline{X}\](\overline{e})} (\text{App-InfAlg}) $$

The most important piece here is the $\tt\emptyset \vdash\_\overline{X}\overline{S} \<: \overline{T} \Rightarrow \overline{C}$ premise, which invokes the constraint generation algorithm. Importantly, though, it *only* generates constraints using $\tt\overline{S}$ and $\tt\overline{T}$, which correspond to the argument types (that is, the types to the left of the arrow). This is problematic for types like this, which include type variables that only appear in the result:

$$ \tt All(X, Y)(X) \rightarrow Y $$

Or, even more simply:

$$ \tt All(X)() \rightarrow X $$

In this case, my implementation happily infers the type of the above two functions to be $\tt Y$ and $\tt X$, respectively, which are clearly not valid types, since they are type variables that have escaped their scope!

My guess is that my implementation is wrong, and the algorithm accounts for this case. In that situation, I would expect the algorithm to either reject the applications or infer $\tt Bot$ as the result type. However, I don’t see how this could possibly be accounted for, since the algorithmic inference rule only uses $\tt R$ for the purposes of turning the constraints $\overline{C}$ into the substitution set $\sigma$.

How does the algorithm handle this situation?

# Answer
> 4 votes
As a prelude, there is some terminological confusion in your question. The issue is about a type variable occurring in a result *type* of a function. This is fairly minor. A more serious one is when you say "my implementation happily infers the types of the above two functions to be ...". What functions? Functions are terms like (in this case) $\tt fun(x:T)e$ but the rule you quote is actually about function application, i.e. it applies to terms like $\tt f(e)$. Either way, the two things you present are types not terms. What you seem to want to say is: given a function $\mathtt{f}\in\tt All(X)()\to X$, the expression $\tt f()$ seems to have the inferred type $\tt X$.

$\tt \sigma \in \bigwedge \overline{C} \Downarrow R$ implies that $\sigma$ is a map for all the variables in $\tt R$ or else it wouldn't even make sense. Maybe it doesn't make sense, but we see that in the rule you listed the constraint generation step produces a $\mathtt{\bar X}/V$ constraint and the substitution algorithm will thus produce a $\mathtt{\bar X}/V$ substitution which, by definition, has a mapping for each type variable in $\tt \bar X$. I assume your confusion is that you look at the minimal substitution generating algorithm $\sigma\_{C\tt R}$ at the bottom of page 11, note that in your second case, for example, the constraint generation step produces an empty set of constraints and thus the "for each constraint" iterates over an empty set producing a substitution with no mappings which presumably would act as the identity. However, this would violate the definition of an $\mathtt{\bar X}/V$ substitution. The detail here is the definition of the empty constraint set. At the beginning of section 3.3 on page 9 it states:

> The empty $\mathtt{\bar X}/V$ constraint set, written $\emptyset$, contains the trivial constraint $\tt Bot \<: X\_\mathit{i} \<: Top$ for each variable $\mathtt{X}\_i$.

Since the result type is covariant (in a top-level context), we'll get $\tt Bot$ in those cases. In particular, given that $\mathtt{f}\in\tt All(X)()\to X$, the expression $\tt f()$ will have the inferred type $\tt Bot$. The produced substitution $\sigma\_{\emptyset\tt R}$ will map $\tt X$ to $\tt Bot$.

---
Tags: type-theory, type-checking, typing, type-inference
---


# Question
Title: Why can there be no reductions from NP-complete problems to P problems under P ≠ NP
Under the assumption that $P \ne NP$, why is it impossible to reduce a problem that is known to be NP-complete to a problem that is known to be of polynomial time complexity? What kind of fundamental theorems would this contradict if it was possible?

# Answer
> 4 votes
It would contradict the assumption that **P$\\,\neq\\,$NP**. You could solve the **NP**-complete problem in polynomial time by reducing it to a problem in **P** and solving that.

# Answer
> 2 votes
*This answer was a response to the original version of the question, which has now been edited to ask something different.*

Contrary to your premise, it is possible. If $\text{P} \ne \text{NP}$, then *any* language in $\text{P}$ reduces to an $\text{NP}$-complete problem, but is not $\text{NP}$-complete itself.

In fact we don't need the $\text{P} \ne \text{NP}$ assumption. $\varnothing$ is not $\text{NP}$-complete but reduces easily to $\text{3-SAT}$.

Additional note: it is generally believed that NP-intermediate problems exist (this is equivalent to $\text{P} \ne \text{NP}$). These problems are not in $\text{P}$ and not $\text{NP}$-complete, but they reduce to $\text{NP}$-complete problems.

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


# Question
Title: Semidecidability/Decidability for strings seperated by a non alphabet symbol
I am trying to prove the following:

Let $\Sigma $ be an alphabet not containing the symbol "$;$", and suppose that $L \subseteq \Sigma^\*$; $\Sigma^\*$ is recursively enumerable. If this is the case language $L' = \\{x \in \Sigma^\*: x; y \in L \ for \ some \ y \in \Sigma^\*\\}$ is recursively enumerable.

which left me a little bit confused. Since $";"$ is not in the alphabet $\Sigma$ should I seperate $x$ and $y$ and show that check for $x \in \Sigma^\*$ and $y \in \Sigma^\*$ is recursively enumerable?

Also, will this statement be the case if we checked for being recursive instead, that is if $L$ was recursive, is $L'$ necessarily recursive as well? And is the proof of this the same with the recursively enumerable case?

Any help will be appreciated.

# Answer
> 1 votes
First, a few things that may or may not help:

* **Def**: A language $L\subseteq \Sigma ^\*$ is Recursive (R) if there is some algorithm that, when given $u\in \Sigma^\*$, will return $1$ iff $u\in L$ and $0$ iff $u\not\in L$.
* **Def**: A language $L\subseteq \Sigma ^\*$ is Recursively enumerable (RE) if there is some algorithm that, when given $u\in \Sigma^\*$, will return $1$ iff $u\in L$. (If $u\not\in L$, ir may return $0$ **or loop forever**)
* **Prop**: A language $L$ is RE iff there is some algorithm that enumerates $L$. One way to formalize "$\mathcal A$ enumerates $L$" would be to say that the algorithm $\mathcal A$ takes an integer $n\in \mathbb N$ and returns some $\mathcal A(n)\in L$ for each $n$, and that for any $u\in L$ there is at least one $n$ so that $\mathcal A(n)=u$ (i.e. if you look at the algorithm as a function $\mathcal A:\mathbb N \to L$, it is surjective).
* **Remark**: Even though the notins of R and RE seem to depend on the alphabet, they do not. If you have an algorithm $\mathcal A$ that takes a word $u\in \Sigma$ as input, you create the one that takes $u\in \Sigma'^\*$ by returning $0$ if $u\not\in \Sigma$ (which is decidable) and then running $\mathcal A$. And in the other direction, you can just reuse the same algorithm.

---

Now, take some alphabet $\Sigma$ so that $;\not\in\Sigma$ and let $\Sigma':=\Sigma\sqcup \\{;\\}$.

To show that your $L'$ is indeed RE, just take the algorithm $\mathcal A$ that proves that $L$ is RE. When given $x\in \Sigma^\*$, you want to know if there is some $y\in \Sigma^\*$ so that $x;y\in L$. The problem with simply trying for each $y\in \Sigma^\*$ is that your first call to $\mathcal A$ may never terminate and you'll have looped on a possibly positive instance. What you want to do instead is this: for $n$ from $0$ to $+\infty $, for each word $y\in \Sigma^\*$ of size $|y|\le n$, run $\mathcal A$ on $y$ for $n$ steps (or seconds) and if it returns $1$, return $1$. So you're trying bigger a bigger $y$ while giving more and more time to $\mathcal A$ to finish. If there is some $y$ so that $x;y\in L$, then you'll eventually try for this $y$ and give $\mathcal A$ enough time to tell you it's the corect $y$. And if it answers yes, then clearly, there is some $y$ so that $x;y\in L$. So we just proved that $L'$ is RE.

Using the property I gave above, there is another simpler proof. You suppose that you can enumerate $L$ and want to enumerate $L'$. Well clearly, you just have to enumerate $L'$ and drop the $;$ and whatever is after it.

If you suppose that $L$ is R then $L'$ may not be R. Recall that the halting problem $HALT=\\{\langle M,w\rangle|M\text{ halts on input }w\\}$ is undecidable (i.e. $HALT\not\in R$). Let $BHALT:=\\{\langle M,w\rangle;n|M\text{ halts on input }w\text{ in at most }n\text{ steps}\\}$. Clearly $BHALT\in R$: you can just simulate $M$ on $w$ for $n$ steps and then check if the last state is final. But if you take $L=BHALT\in R$, then $L'=HALT\not \in R$.

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


# Question
Title: What's the input to the decoder in a sequence to sequence autoencoder?
What's the input to the decoder part of a sequence to sequence autoencoder? I've seen certain examples of such an autoencoder (using LSTM's more often than not) but am still unclear.

* For example, here in this often-cited paper by Dai & Le ('Semi Supervised Sequence Learning'), we have the following diagram:

What's the input to the decoder portion of the autoencoder here? In this example it's 'W-X-Y-Z.' But in general, is it the same as the input to the encoder? Or is it using the output from the previous timestep/LSTM cell as input?
* Similarly, in another popular paper by Srivastava et. al ('Unsupervised Learning of Video Representations using LSTMs'), they have the following diagram:

It seems they're using the reversed input from the encoder as input here. However, there's a section as follows:

> The decoder can be of two kinds – conditional or unconditioned. A conditional decoder receives the last generated output frame as input, i.e., the dotted input in Fig. 2 is present. An unconditioned decoder does not receive that input.

In the unconditioned decoder, what input does the decoder receive?

# Answer
> 7 votes
I was wondering the same and just stumbled across a nice tutorial by Quoc V. Le. The following explanation deals with the conditional case since this seems to be the common case. My explanation is based on and the image is taken from chapter 5 *Sequence output prediction with Recurrent Neural Networks*.

### Background

We only regard a decoder with a *single* cell RNN which has:

* **W** input to hidden weights
* **U** hidden to hidden weights (ignore that first weight is different here)
* **V** hidden to label weight

$$ f(x) = Vh\_T \\ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ h\_t = \sigma ( U h\_{t-1} + W x\_t ) ~~~ \text{for} ~ t = T, \dots, 1 \\ ~~~~~~~~~~ h\_0 = \sigma ( W x\_0 ) $$

Since we are doing sequence prediction, we are not only interested in the last output of the RNN but rather the output at every timestep. Therefore the conditional decoder is designed to predict each label based on the previous ones, mathematically it splits the conditional probability in the following way:

$$ p(y|x) = \prod\_{i=1}^n p(y\_{i} | y\_{i-1}, \dots, y\_{1}, x) $$

Like often done in machine learning, you can transform the probability to a score/energy/whatever which consists of a more convenient summation:

$$ \log p(y|x) = \sum\_{i=1}^n \log p(y\_{i} | y\_{i-1}, \dots, y\_{1}, x) $$

The maximization of that score over our data is the objective. That can be equivalently formulated by the minimization of $ - \sum\_{(x,y) \in D} \log p(y|x) $ where $D$ is our training set.

To complete this thought: When this probability is approximated we are actually interested in the argument $\theta\_{min}$ of the minimization of $ - \sum\_{(x,y) \in D} \log f(y|x,\theta) $ where $f(y|x,\theta)$ is our function approximator, e.g. a RNN, and $\theta$ the vector containing all weights $U$, $W$ and $V$.

### During Training

During training we have the ground truth at hand so we can feed the decoder (see image) with the respective previous label at each timestep. At the first timestep we use the output of the encoder. Easy peasy.

### During Inference

Here we obviously do not have the ground truth so instead we use the output of the previous timestep. This however poses another problem, since to find the sequence of maximum probability, we would have to compute every possible sequence and its probability according to probability function defined above.

Now, apparently one "greedy" approach is, to just ignore the above probability model and take the argmax's of each timestep.

Another more faithful approach is *Beam Search* which just heuristically looks at a subset of probable sequences and picks the one with maximum probability of them.

Things to note:

* Inference is stopped, when the End-Of-Sequence symbol (`<EOS>`) is returned (greedy: when a timestep's argmax is `<EOS>`, beam search: the currently regarded sequence leads to `<EOS>`)
* Both inference methods do not gurantee retrieving the sequence with maximum probability
* The output of $f(x,\theta)$ needs to be a probability distribution at each timestep, so the final activation of the RNN is usually a softmax $f(x) = softmax(Vh\_T)$

### Unconditioned Case

I'd say based on the above explanation and the paper you referenced, that the unconditioned case does only get input at the first timestep of the decoder and then just "works with" the propagation of the hidden states. So the second equation of the RNN equations changes to $h\_t = \sigma ( U h\_{t-1} )$.

Then the outputs at each step would not be conditioned on the previous timestep's output, but rather be *unconditioned*. This way the modelled probability would become

$$ p(y|x) = \prod\_{i=1}^n p(y\_{i} | x) $$

and the greedy inference strategy would become valid.

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: How to prove that $n^2$ is not $o(n^2+10^{10}n)$?
I need to prove that $n^2$ is not $o(n^2+10^{10}n)$. I thought of the limit test: $$ \lim\_{n \to \infty} \frac{n^2}{n^2+10^{10}n} = 1 \Rightarrow n^2 = \Theta(n^2+10^{10}n) $$

However I'm not sure if the result of the test rules out the possibility of $o(n^2+10^{10}n)$.

# Answer
One definition $f(n)=o(g(n))$ is that $\lim\_{n\to\infty} f(n)/g(n)=0$. If this is the definition you're using, then showing that the limit is $1$ already shows that $f(n)\neq o(g(n))$.

The other definition is that, for every $c\>0$, there is an $n\_0$ such that $f(n)\leq cg(n)$ for all $n\geq n\_0$. The fact that $\lim\_{n\to\infty} f(n)/g(n)=1$ means that, for all $\varepsilon\>0$, there is some $n\_0$ such that $f(n)/g(n)\>1-\varepsilon$ for all $n\geq n\_0$ (this is part of the definition of "limit"). So, for all $\varepsilon\>0$, we have $f(n)\>(1-\varepsilon)g(n)$ for all large enough $n$. This means that, in particular, we do *not* have $f(n)\leq cg(n)$ for $c=1-\epsilon$, so $f(n)\neq o(g(n))$ by the alternative definition.
> 6 votes

# Answer
Without any limits: $(n^2 + 10^{10}n) / 2 ≤ n^2 ≤ n^2 + 10^{10}n$ whenever $n ≥ 10^{10}$. So for c \< 1/2, we don't have $n^2 \< c(n^2 + 10^{10}n)$ for all large n. Actually, not for any large n.

And $f(n) = \Theta (g(n))$ does indeed rule out that $f(n) = o (g(n))$, but is not a necessary condition.
> 1 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: What Turing's proof of Halting Problem really proves?
This is something that has bugged me for a while, so I hope you can help me.

Suppose:

* $A'$ is the set of all programs,
* $halt?$ is the halting problem solver,
* $D$ is the program that is constructed in the proof to show HP is undecidable

Obviously $halt? \in A'$ and $D \in A'$.

$A' - halt? = A$ is the set of all programs except $halt?$ and all programs that uses $halt?$ e.g $D \notin A$.

So it seems to me that what Turing's proof shows is that HP is undecidable for the set $A'$. It does not show that it's undecidable for the set $A$.

It also seems that every valid program that ever written is in $A$

Did I misunderstand something? If not is there any $halt?$ program to decide $A$ or $A$ is also undecidable?

# Edit

I think, I didn't say correctly what I meant. and I know that I misused the $X - y$ notation but I hoped you get what I mean.

Suppose:

* $A'$ is the set of all programs,
* $halt?$ is the halting problem solver that may produce the wrong answer
* $D$ is the program that is constructed in the proof of HP and instead use my version of $halt?$
* $A = A' - \text{{D}}$
* $The\ Halt?$ is the original halt? program in the proof of HP

by the same arguments of proof of HP we can prove that $halt?$ give the wrong answer for $D$. so we proved that $halt?$ surely not working correctly for at least one program $D$

we now know that $The\ Halt?$ program doesn't exist so $D$ program doesn't compile. so let's exclude it from the set of all possible program

now the question is this: Is the set $A$ is decidable?

My understanding is that The HP proof does not say anything about A.

# Answer
> 5 votes
The following was written before the extensive edit to the question, but the edit doesn't really change anything. The point remains that the proof shows that no program decides the halting problem, so it shows that the set "$A'$ minus some programs that don't exist" is just $A'\setminus\emptyset=A'$.

> Obviously $halt?\in A'$ and $D\in A'$.

That's not obvious. Indeed, the point of the proof is that it's not even true. Turing proves that $halt?\notin A'$ – there is no Turing machine (program) that decides the halting problem.

> $A' - halt? = A$ is the set of all programs except $halt?$ and all programs that uses $halt?$ e.g $D \notin A$.

If $X$ and $Y$ are sets, then $X-Y = \\{e\mid e\in X\text{ but }e\notin Y\\}$. Where $y$ is an element, people sometimes write $X-y$ as shorthand for $X-\\{y\\}$.

Let us assume, for a moment, that $halt?$ is a program. Then $A'-halt?$ would be the set of all programs except for $halt?$. In particular, if $halt?$ were a program, then $D$ would be a program and, contrary to your claim, $D$ would be in $A'-halt?$. As it is, neither $halt?$ nor $D$ is a program, so $A'=A$.

> If not is there any $halt?$ program to decide $A$ or $A$ is also undecidable?

$A$ is just the set of all programs. It is decidable, just like the set of all Java programs is decidable. Do you mean to ask if *the halting problem for $A$* is decidable? If so, it is the very thing that Turing has proven to be undecidable, since $A=A'$.

# Answer
> 2 votes
There's a few pieces here.

First, your proof regarding $A$ is correct: it is possible to construct a set of programs for which $halt?$ can correctly determine whether they halt or not. That has never been the issue. Everyone knows that there are programs for which we can determine whether they will halt.

> It also seems that every valid program that ever written is in $A$

This one is trickier. Your claim sounds like it should be obvious, but without having named $halt?$ it's not really reasonable to determine whether any program does not contain this unspecified $halt?$.

In fact, one real issue you run into is that real computers are not actually Turing machines because they lack the mythical "infinite tape" that is required for a Turing machine. Real computers are finite automata. And it is easy to prove whether a finite automata terminates or loops in finite time (the proof is trivial, in fact). By that logic, we can comfortably say that we have never written a program that is not decidable.

Even here, though, there's some value in realizing that it could be "hard" to determine if a program halts or not. Consider this one, in pseudocode:

```
loop over every permutation of a 160 byte string
    calculate the SHA-1 hash of this string
    if the hash is equal to 0000000000000: terminate

```

Determining whether this program terminates could potentially require more energy than exists in our galaxy! That's pretty darn close to undecidable! In fact, it is not currently known whether there is a 160 byte string which hashes via SHA-1 to be all 0s. It is theorized that it should be likely to be true, but that's as far as our mathematicians have gotten!

So the real world practicality of decidability is still there. The interesting part about decidability in the Turing complete land is that, even given access to some infinite resources, there are *still* some undecidable problems.

# Answer
> 1 votes
The halting program, $halt?$, does not exist, and neither does $D$. In reality, then, your $A'$ and your $A$ are identical. The halting problem cannot be solved for either of them.

However, on second thought, your question is not completely bogus -- if I think about what you really meant to say. In the proof that the halting problem is undecidable, instead of assuming that $halt?$ exists and deriving a contradiction, you can think of it as taking *any* program $H$, and showing that $H$ does not solve the halting problem. Specifically, imagine $H$ solves the halting problem for many inputs, but perhaps it doesn't work on every input (either it returns the wrong answer, or maybe it doesn't halt at all). Then what does the proof tell us about $H$?

First, the proof constructs $D$, which on input $x$ runs $H$ on $(x,x)$; then, if $H$ says it halts $D$ runs forever and if $H$ says not, $D$ halts. Then we consider $D$ on input $D$. IF $H$ can deduce the correct behavior of $D$ on input $D$, then we get a contradiction: if $D$ halts, $D$ actually runs forever, and if $D$ doesn't halt, $D$ actually halts. That is, IF $H$ answers correctly on input $(D,D)$, we get a contradiction.

Therefore, **we have shown that $H$ cannot decide the answer correctly on input $(D,D)$. But this doesn't mean that there can't be a smaller set of programs on which $H$ correctly decides the answer.** Indeed, many practical algorithms exist for deciding whether *some* programs halt (usually simple ones).

> by the same arguments of proof of HP we can prove that $halt?$ give the wrong answer for $D$. so we proved that $halt?$ surely not working correctly for at least one program $D$

Yes, exactly -- we proved $H$ doesn't work for $D$ on input $D$, but maybe $H$ works for other programs.

> we now know that $The\ Halt?$ program doesn't exist so $D$ program doesn't compile. so let's exclude it from the set of all possible program

Be careful how you word things -- you can't exclude a program that doesn't exist. But, I'm thinking what you *meant* to say is, rather than excluding the non-existent program $halt?$, exclude the program $H$ which only *sometimes* solves the halting problem. Then, sure -- you can absolutely do that.

> now the question is this: Is the set $A$ is decidable?
>
> My understanding is that The HP proof does not say anything about A.

You are right that we haven't proved that the halting problem on $A$ is not decidable!

However: **no, $A$ is not decidable.** For starters, there are an infinite number of programs that behave exactly like $D$, but aren't equal to $D$ (for instance, they have a bunch of extra lines of code that do nothing). You'd have to exclude those as well -- *even writing down a list of programs equivalent to $D$ is not a decidable problem, not something you can do easily.*

Computer scientists have tried very hard to find a subclass of programs for which the halting problem is decidable, and many such classes exist -- for example, the class of loop-free programs. But it is not enough **just** to exclude $D$ and $H$. In fact, you will likely have to exclude *most* programs. You will never succeed in solving the halting problem just by disallowing some specific small number of programs.

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


# Question
Title: Round robin tournament scheduling using divide and conquer
I want to scheduling $n$ teams using divide and conquer method for $n \in \mathbb{N}$.My approach is that if $n$ is even divide it to to group $\frac{n}{2}$ and $\frac{n}{2}$ but if $n$ is odd, add auxiliary team and scheduling $n+1$ team at the end we remove the last team and in table every match between $n+1$ team and others will mark as rest. but for some $n$ like 6 there will be a little problem. we should first schedule table for 3 team, 3 is odd so we should schedule for 4. for scheduling 4 teams we need schedule for 2 team and that's the base case so we have:

\begin{array}{c|ccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} \\ \hline 1 & 2 & & \\ 2 & 1 & & \\ 3 & 4 & & \\ 4 & 3 & & \end{array}

now we should conquer the result. upper side of table didn't play with down site of table so we should schedule their matches, and remove team 4. then we have

\begin{array}{c|ccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} \\ \hline 1 & 2 & 3 & - \\ 2 & 1 & - & 3 \\ 3 & - & 1 & 2\\ \end{array}

now we have table for 3 teams it's time to schedule 6 teams so we create table like this

\begin{array}{c|cccccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\ \hline 1 & 2 & 3 & - & & & \\ 2 & 1 & - & 3 & & & \\ 3 & - & 1 & 2 & & & \\ 4 & 5 & 6 & - & & & \\ 5 & 4 & - & 6 & & & \\ 6 & - & 4 & 5\\ \end{array}

for conquer step we should schedule match for upper side of table with down side so then

\begin{array}{c|cccccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\ \hline 1 & 2 & 3 & - & 4 & 5 & 6\\ 2 & 1 & - & 3 & 5 & 6 & 4 \\ 3 & - & 1 & 2 & 6 & 4 & 5 \\ 4 & 5 & 6 & - &1 &2 &3 \\ 5 & 4 & - & 6 &2 & 3& 1\\ 6 & - & 4 & 5 & 3 & 1 & 2\\ \end{array}

but it's not best answer and we can reschedule rest matches such that tournament end in 5 days for $n = 6$. how can I modify conquer step?

# Answer
I think this method will fix conquer step. for example for 6 teams we have this table when we divide it to 2 piece

\begin{array}{c|cccccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\ \hline 1 & 2 & 3 & - & & & \\ 2 & 1 & - & 3 & & & \\ 3 & - & 1 & 2 & & & \\ 4 & 5 & 6 & - & & & \\ 5 & 4 & - & 6 & & & \\ 6 & - & 4 & 5\\ \end{array}

first we should replace rested games with new matches, we now that the only answer for Day 3 of team 1 is 4 so we put 4 in table and so on then we have \begin{array}{c|cccccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\ \hline 1 & 2 & 3 & 4 & & & \\ 2 & 1 & 5 & 3 & & & \\ 3 & 6 & 1 & 2 & & & \\ 4 & 5 & 6 & 1 & & & \\ 5 & 4 & 2 & 6 & & & \\ 6 & 3 & 4 & 5\\ \end{array}

then we will create array like this $\[4,5,6\]$ cause we put the numbers with this order, then we remove first element and add it to end of list, then we write this numbers for Day 4 and it will so we have this

\begin{array}{c|cccccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\ \hline 1 & 2 & 3 & 4 & 5 & & \\ 2 & 1 & 5 & 3 & 6 & & \\ 3 & 6 & 1 & 2 & 4 & & \\ 4 & 5 & 6 & 1 & 3 & & \\ 5 & 4 & 2 & 6 & 1 & & \\ 6 & 3 & 4 & 5 & 2 & & \\ \end{array}

and do it again, we should do this $\frac{n-2}{2}$ times when $\frac{n}{2}$ is odd and $\frac{n}{2}$ times when $\frac{n}{2}$ is even. so the final table will be like this \begin{array}{c|cccccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\ \hline 1 & 2 & 3 & 4 & 5 & 6 & \\ 2 & 1 & 5 & 3 & 6 & 4 & \\ 3 & 6 & 1 & 2 & 4 & 5 & \\ 4 & 5 & 6 & 1 & 3 & 3& \\ 5 & 4 & 2 & 6 & 1 & 2& \\ 6 & 3 & 4 & 5 & 2 & 1 & \\ \end{array}

it should be a valid table because divide part are correct and adding matches to rest parts are also correct the conquer part has no repeated match with games in day 1 to $\frac{n}{2}$ because the right side of table are matches between the upper side of table with down side of table and the only matches that may case repeated match is matches that we add to rest matches. we use list and shifting it circular so it will guarantee that we don't have any repeated match.

I check this method for $n \< 2000$ and it was correct.
> 1 votes

# Answer
The recursive approach is not necessarily the simplest one here. There is a simple direct construction I am quoting from here. Suppose first that you are trying to schedule $n$ teams, where $n$ is odd. In total there are $n(n-1)/2$ matches to schedule, and in each round at most $(n-1)/2$ matches can take place, so there should be $n$ rounds in total. All computations below are modulo $n$. In round $r$, team $x$ plays against team $r-x$, except for team $r/2$, which stays out. Here is an example for $n=5$:

* Round 0: 1–4, 2–3, 0 sits out
* Round 1: 0–1, 2–4, 3 sits out
* Round 2: 0–2, 3–4, 1 sits out
* Round 3: 0–3, 1–2, 4 sits out
* Round 4: 0–4, 1–3, 2 sits out

It's easy to prove the correctness of this schedule. Indeed, teams $x$ and $y$ meet in round $x+y$ and in no other round.

If $n$ is even then there are $n(n-1)/2$ matches to schedule, and each round at most $n/2$ can take place, so there should be $n-1$ rounds. Indeed, we take the schedule for $n-1$, and pair up the team sitting out with the extra team. For example, for $n=6$:

* Round 0: 1–4, 2–3, 0–5
* Round 1: 0–1, 2–4, 3–5
* Round 2: 0–2, 3–4, 1–5
* Round 3: 0–3, 1–2, 4–5
* Round 4: 0–4, 1–3, 2–5

It's again not hard to prove the correctness of the schedule. If $x,y \neq n-1$ then they meet in round $x+y$, while $x$ and $n-1$ meet in round $2x$ (where all computations are modulo $n-1$).
> 1 votes

# Answer
For example we have 8 teams: 1 2 3 4 5 6 7 8 Divide they onto 2 groups and let play each team one group with each team another group:

day 1: 1 2 3 4 5 6 7 8 day 2: 1 2 3 4 6 7 8 5 day3: 1 2 3 4 7 8 5 6 day 4: 1 2 3 4 8 5 6 7

All teams one group just had games with all teams another group. But teams inside one group didn't have game between each other.

Repeat that algorithm recursively for every group

day 5: 1 2 5 6 3 4 7 8 day 6: 1 2 5 6 4 3 8 7

Once again divide every group

day 7: 1 3 5 7 2 4 6 8

Perfect solution : Recursion algorithm here
> 0 votes

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


# Question
Title: Existence of suitable pseudo-random number generators to derandomize BPP to P
I am struggling to understand how the known oracle, and conditional derandomization results connecting $BPP$ and $P$, relate to each other.

My understanding is that if there is a suitably strong pseduo-random number generator that only uses $O(\log n)$ seed bits, then we can derandomize $BPP$ to $P$ by simulating $BPP$ machines in polynomial time using the random number generator and looping over every possible seed. If I understand correctly, the "suitably strong" details were made explicit with Impagliazzo-Wigderson's conditional result that unless $E$ has sub-exponential circuits, $P=BPP$ by way of simulating $BPP$ machines with a pseudo-random number generator.

However, it is known that there is an oracle to which $P^A \ne BPP^A$.

While I understand that this does not imply $P \ne BPP$, cannot we at least say that this means that $P$ cannot simulate $BPP$ machines? Because if $P$ could just simulate $BPP$ machines directly, then it could also access the oracle $A$ in exactly the same way as $BPP$, and it would not be possible to get an oracle separation.

So putting this all together, why can't we say that Impagliazzo-Wigderson's result actually proves $E$ has sub-exponential circuits?

Or alternatively worded, doesn't the oracle separation prove no "suitably strong" pseduo-random number generator exists that would allow derandomizing $BPP$ by just simulating it in polynomial time?

It's possible I'm missing something subtle, but I have a feeling I'm actually just way off the mark. So please help me understand what is going on here.

# Answer
$P^A\neq BPP^A$ implies the inexistence of strong enough PRG's in the relativized world, not necessarily in the usual (non black box) model.

Remember that when defining a PRG, you require it to fool some adversary with bounded resources, e.g. polynomial size circuits, or probabilistic poly time Turing machines. The NW generator fools circuits of bounded size $S$ (which depends on the hardness of the problem you started your construction with), but this does not mean it can fool circuits (or Turing machines) with access to the oracle $A$.

As an example, for any PRG $G$ which fools poly time probabilistic Turing machines, let $\mathcal{O}\_G$ be the oracle which tells you whether some string $s$ is a possible outcome of $G$. $G$ can no longer fool poly size Turing machines with oracle $\mathcal{O}\_G$.
> 3 votes

---
Tags: complexity-theory, randomized-algorithms, pseudo-random-generators, oracle-machines
---


title: Sorting in a probabilistic order

text:
# Question
Title: Sorting in a probabilistic order
Given a list of real numbers $p\_1, \dots, p\_n$, I am looking for a most efficient algorithm to sort this list in a "probabilistic ascending order", meaning that $p\_i \< p\_j$ implies that it is likely for $i$ to be placed before $j$, but not certain. In principle, every permutation is a possible output, but the less sorted the permutation is, the less likely it is to occur.

The best solution I could come up with is to modify selection sort. Instead of selecting the minimal element in every step, you select a random element with probability proportional to $\frac{1}{p\_i}$. This has quadratic complexity of course, so I was wondering if there are better alternatives.

# Answer
> 5 votes
One of the popular models for biased permutations is the Mallows model, dating to a paper of Mallows from 1957. Lu and Boutilier, quoting Doignon et al., give the following recipe for sampling a permutation according to the Mallows distribution, given a parameter $0 \< \phi \leq 1$:

1. Start with the permutation 1.
2. Insert 2 into position 1 with probability $\frac{\phi-\phi^2}{1-\phi^2}$, and into position 2 with probability $\frac{1-\phi}{1-\phi^2}$.
3. Insert 3 into positions 1,2,3 with probabilities $\frac{\phi^2-\phi^3}{1-\phi^3},\frac{\phi-\phi^2}{1-\phi^3},\frac{1-\phi}{1-\phi^3}$, respectively.
4. Insert $4,\ldots,n$ in an analogous manner.

When inserting $x$ into position $i$, what you do is shift positions $i,\ldots,x-1$ one step forward, and insert $x$ in the resulting empty spot.

The probability to obtain a permutation $\pi$ is proportional to $\phi$ raised to the number of inversions in $\pi$ (the Kendall $\tau$ distance between $\pi$ and the identity permutation).

Another popular model is the PlackettLuce model from 1959. There are other models, for example Tallis–Dansie.

# Answer
> -1 votes
The expected running time of quicksort with random pivot is actually $O(n\log n)$.

One can show that you cannot achieve better expected runtime, by any randomized algorithm that correctly sorts any list of $n$ elements. This is shown by Yao's principle, which states that the worst case expected running time of any randomized algorithm, is no better than the expected running time of the best deterministic algorithm for any input distribution.

This gives you the power to, instead of considering coin tossing algorithms, fix some input distribution, and ask what is the best expected running time of any deterministic algorithm relative to that distribution (i.e. it relates randomize complexity to distributional complexity).

Now, since we can fix any distribution, you can look at the uniform distribution over all possible inputs, and ask what is the best expected running time a **deterministic** algorithm achieves, relative to the uniform distribution. A lower bound proof in this setting is closer in spirit to the regular lower bound proof for deterministic sorting that you know, you can find it in the following lecture notes.

The idea is similar, you consider a comparison based sorting algorithm as a binary tree, where each node is a query of the form $x\<y$, and each leaf in the tree represents a different permutation. The number of comparisons required to sort some input $a\_1,...,a\_n$ is given by the height of the leaf corresponding to the sorted permutation $a\_{i\_1},...,a\_{i\_n}$. Since the number of leaves is $n!$, you know the depth is $\Omega(n\log n)$. The difference in the distributional case is that you need to bound the average leaf height of a binary tree with $n!$ leaves (not the depth). Now, proceed to show that the average leaf height is minimized by a balanced binary tree, in which the average leaf height is $\Omega(\log n!)$. To see why you can focus on balanced trees, show that if the tree is unbalanced somewhere, you can "fix it", and this operation only decreases average leaf height.

I only dealt with algorithms that correctly sort all inputs, but using Yao's principle for Monte-Carlo algoirthms, you can extend this to your case.

---
Tags: sorting, probability-theory
---


# Question
Title: Finite State Automaton Transition Diagram
I got an alphabet E={x,y,z}. And i want to create a finite state automaton that accepts strings consisting of at least two x's, followed by at most three y's followed by any number of z's. And i want to draw a transition diagram for this.

And i am new to this concept, So far i got here. And i know i am wrong so if someone can help me out would be great. Thanks

# Answer
> at most three y's means that you can either have none 'y', or 1 'y' , or 2 'y' so you should also accept such strings
> 0 votes

---
Tags: finite-automata, finite-model-theory
---


# Question
Title: Integer linear programming formulation of formula in DNF
I have multiple sets, e.g.,

$$\\{1, 2\\}, \\{2, 3, 4\\}, \\{1, 4\\}$$

Each variable $1, 2, 3, 4$ is binary. I need to represent the following condition without additional variables

$$(1 \land 2) \lor (2 \land 3 \land 4) \lor (1 \land 4)$$

Basically, I need to enforce that either $1$ and $2$ are 1s, or $2$ and $3$ and $4$ are ones, or $1$ and $4$ are 1s, but not all of them. Constants can be added as needed, as well as equalities, inequalities, etc. How can I do that?

# Answer
> 3 votes
You are looking for a four-dimensional convex polytope that contains all of the points $(x\_1,x\_2,x\_3,x\_4)$ that satisfy your condition, and but not any point $(x\_1,x\_2,x\_3,x\_4)$ that doesn't satisfy your condition. (That's because any system of linear inequalities forms a convex polytope.)

It's not quite clear to me from your question about what your condition is, so I'll try answering your question with both plausible interpretations I see.

## Interpretation #1:

In the first possible interpretation, the boolean formula is $(x\_1 \land x\_2) \lor (x\_2 \land x\_3 \land x\_4) \lor (x\_1 \land x\_4)$. This means the polytope needs to contain all of the following seven points:

$$(0,1,1,1), (1,0,0,1), (1,0,1,1), (1,1,0,0), (1,1,0,1), (1,1,1,0), (1,1,1,1)$$

and not any of the other nine points where the formula is false.

There are various ways to check whether there exists such a polytope. One way is to enumerate all possible inequalities $c\_1 x\_1 + c\_2 x\_2 + c\_3 x\_3 + c\_4 x\_4 + c\_5 \ge 0$ and look for combinations $(c\_1,\dots,c\_5)$ such that this inequality is true for all of the seven points listed above. Then, we check whether a system of constraints obtained by using all of those inequalities has the desired property (in particular, each of the other nine points violates at least one of these inequalities). You can then minimize the set of constructed inequalities, to remove redundancies.

Here is one such system of constraints that works:

$$\begin{align\*} x\_2+x\_4-1 &\ge 0\\ x\_1+x\_3-1&\ge 0\\ x\_1+x\_2-x\_3+x\_4-1 &\ge 0 \end{align\*}$$

Another way to have obtained this system of constraints would be to convert the DNF formula you listed to CNF, and then translate each "OR" constraint into a single inequality using the techniques from Express boolean logic operations in zero-one integer linear programming (ILP). The formula $(x\_1 \land x\_2) \lor (x\_2 \land x\_3 \land x\_4) \lor (x\_1 \land x\_4)$ is equivalent to $(x\_1 \lor x\_2) \land (x\_1 \lor x\_3) \land (x\_1 \lor x\_4) \land (x\_2 \lor x\_4)$. That then yields the following system of constraints, which also works:

$$\begin{align\*} x\_1+x\_2-1 &\ge 0\\ x\_1+x\_3-1 &\ge 0\\ x\_1+x\_4-1 &\ge 0\\ x\_2+x\_4-1 &\ge 0 \end{align\*}$$

## Interpretation #2:

In the second plausible interpretation, you want the boolean formula

$$(x\_1 \land x\_2 \land \neg x\_3 \land \neg x\_4) \lor (\neg x\_1 \land x\_2 \land x\_3 \land x\_4) \lor (x\_1 \land \neg x\_2 \land \neg x\_3 \land x\_4).$$

Thus, you want the polytope to contain only the three points

$$(1,1,0,0),(0,1,1,1),(1,0,0,1).$$

We can apply the same methods to get a system of inequalities for this formula. Here is one solution that works:

$$\begin{align\*} -x\_1-x\_3+1 &\ge 0\\ -x\_2+x\_3-x\_4+1 &\ge 0\\ x\_2+x\_4-1 &\ge 0\\ x\_1+x\_3-1 &\ge 0\\ x\_1+x\_2-x\_3+x\_4-1 &\ge 0 \end{align\*}$$

# Answer
> 2 votes
I will use a = 1, b = 2, etc...

If a is set then c must be false and EITHER b or d must be true:

```
10a + c <= 10
10a + b + d <= 11
10a - b - d <= 9

```

Finally, if a is not set then the rest must be true:

```
10 - 10a - b - c - d <= 7

```

# Answer
> 1 votes
To complement the 2nd part of D.W.'s answer, we would like to find an $\mathcal H$-polytope (defined by the intersection of closed half-spaces) whose intersection with $\\{0,1\\}^4$ is

$$\\{ (1,1,0,0),(0,1,1,1),(1,0,0,1) \\}$$

Let

$$\Phi := \left(x\_{1} \wedge x\_{2} \wedge \neg x\_{3} \wedge \neg x\_{4}\right) \vee \left(\neg x\_{1} \wedge x\_{2} \wedge x\_{3} \wedge x\_{4} \right) \vee \left(x\_{1} \wedge \neg x\_{2} \wedge \neg x\_{3} \wedge x\_{4}\right)$$

Using SymPy,

```
>>> from sympy import *
>>> x1, x2, x3, x4 = symbols('x1 x2 x3 x4')
>>> Phi = (x1 & x2 & Not(x3) & Not(x4)) | (Not(x1) & x2 & x3 & x4) | (x1 & Not(x2) & Not(x3) & x4)

```

Converting to the CNF,

```
>>> to_cnf(Phi,simplify=true)
And(Or(x1, x2), Or(x1, x3), Or(x1, x4), Or(x2, x4), Or(x2, Not(x3)), Or(x4, Not(x3)), Or(Not(x1), Not(x3)), Or(x3, Not(x2), Not(x4)))

```

Hence,

$$\Phi \equiv \left(x\_{1} \vee x\_{2}\right) \wedge \left(x\_{1} \vee x\_{3}\right) \wedge \left(x\_{1} \vee x\_{4}\right) \wedge \left(x\_{2} \vee x\_{4}\right) \wedge \left(x\_{2} \vee \neg x\_{3}\right) \wedge \left(x\_{4} \vee \neg x\_{3}\right) \wedge \left(\neg x\_{1} \vee \neg x\_{3}\right) \wedge \left(x\_{3} \vee \neg x\_{2} \vee \neg x\_{4}\right)$$

Note that $\neg x\_i$ and $x\_i \vee x\_j$ can be translated into binary integer programming as $1 - x\_i$ and $x\_i + x\_j \geq 1$, respectively. Thus, an $\mathcal H$-polytope with the desired property is defined as follows

$$\begin{bmatrix} 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & -1 & 0\\ 0 & 0 & -1 & 1\\ -1 & 0 & -1 & 0\\ 0 & -1 & 1 & -1\end{bmatrix} \begin{bmatrix} x\_1\\ x\_2\\ x\_3\\ x\_4\end{bmatrix} \geq \begin{bmatrix} 1\\ 1\\ 1\\ 1\\ 0\\ 0\\ -1\\ -1\end{bmatrix}$$

Verifying in Haskell:

```
λ> filter (\(x1,x2,x3,x4)->(x1 + x2 >= 1 && x1 + x3 >= 1 && x1 + x4 >= 1 && x2 + x4 >= 1 && x2 - x3 >= 0 && -x3 + x4 >= 0 && -x1 - x3 >= -1 && -x2 + x3 - x4 >= -1)) [ (x1,x2,x3,x4) | x1 <- [0,1], x2 <- [0,1], x3 <- [0,1], x4 <- [0,1] ]
[(0,1,1,1),(1,0,0,1),(1,1,0,0)]

```

It seems to be correct. However, note that D.W.'s polytope is more economical, as it only uses $5$ half-spaces, whereas my polytope uses $8$ half-spaces. Verifying D.W.'s polytope:

```
λ> filter (\(x1,x2,x3,x4)->(-x1 - x3 >= -1 && -x2 + x3 - x4 >= -1 && x2 + x4 >= 1 && x1 + x3 >= 1 && x1 + x2 - x3 + x4 >= 1)) [ (x1,x2,x3,x4) | x1 <- [0,1], x2 <- [0,1], x3 <- [0,1], x4 <- [0,1] ]
[(0,1,1,1),(1,0,0,1),(1,1,0,0)]

```

---
Tags: linear-programming, integer-programming, modelling, encoding-scheme
---


# Question
Title: Matching two people. One has 7% in common with the other. The other has 70% in common. What's a fair match score?
I am exploring some ideas around dating site matching, and I can do with some ideas as to which is the better solution

Senario: We have a boy and girl, the boy has completed his profile/bio thoroughly while the girl hasn't or maybe she just doesn't like a lot of things, so this is what the data looks like

```
Boy likes:                  Girl likes:
---------                   -----------
Painting                    Painting
Movies                      Movies
Long walks                  Long walks
Harry Potter                Harry Potter
Dogs                        Dogs
Pizza                       Pizza
Computer Science            Computer Science
Mercedes                    Ford
Traveling                   Daisies
Diving                      Psycology
...

Total things
---------------------------------------
100                         10

```

They share 7 things in common. To the girl the boy is a 70% match which is great But to the boy the girl is only a 7% match

Maybe the girl would have more in common if she had more in her list of likes so maybe giving their match a 7/100 is a match missed and maybe that's all she likes and 7/100 is the best they'll ever match but even then, it still might be a good match because maybe the boy over filled his list of things he likes while the girl chose carefully what she really likes.

I am looking for ideas for an algorithm that would give the best match score to order them in lists with other people/matches who might have small percentage in matches because their lists of things they like are 1000s of entries long for example

**Edit:** I will not be matching strings, each of strings in the table above will have a unique ID in an RDBMS database. A table will be used to link users and topics

# Answer
> 4 votes
It seems you're looking for a symmetric set similarity measure. (Symmetric since, as you point out, $A$ should match $B$ as much as $B$ matches $A$. Set similarity since each person's preference is defined by a set of objects.)

A number of these are used in the CS literature. Probably the most common is Jaccard similarity, defined by $|A\cap B|/|A\cup B|$. In your example, $A$ and $B$ have 7 elements in common, and there are 103 elements between them, leading to a similarity of $7/103$. A similar metric is Braun-Blanquet similarity, $|A\cap B|/\max\\{|A|,|B|\\}$; in your example this gives $7/100$. With these as starting points you may be able to find further metrics that capture what you want better. For example, here's a list I found while writing this.

What's notable about these metrics is that they don't take each person's dislikes into account---the similarity is defined only by what's on their list, not what's not on it. (So you may think it makes a better match if two people don't like fish.) Incorporating this would require a universe of elements (so any element in the universe not on the list is considered a dislike). In this case you can use the classic Hamming Distance. You have other options as well, like Euclidean distance or even the Sørensen-Dice similarity.

One benefit of using one of the above, well-known similarity measures is that you can use known algorithms to compute nearest neighbors quickly.

# Answer
> 2 votes
If you want to weight then cosine\_similarity is an option. What this does is weight items that are not common in the population higher. Not sure how but I would base uniqueness on the two populations separately. Some very common among women but uncommon among men should still have high weighting. You could have the people rank their list and use that as the weighting.

You need to be careful that checking a small number of items or a large number of items does not produce more matches as people will cheat the system and check a lot or a few.

I think it should be symmetric. The match from A to B should equal the match from B to A.

Not weighted you take the number of matches and divide by a number. The question is what number to use to for the denominator.

* Simple average (x+y)/2
* Geometric mean sqrt(xy)
* Hamonic mean 2xy/(x+y)

---
Tags: algorithms, matching, modelling
---


# Question
Title: How to prove that algorithm returns the value which appears more than $n/2$ times in the array?
Given the following algorithm (pseudocode):

```
alg1(A[1,..,n])
    i <- 1
    candidate <- NULL
    count <- 0
    while(i <= n)
        if(count = 0)
            candidate <- A[i]
            count <- count + 1
        else if(candidate = A[i])
            count <- count + 1
        else
            count <- count - 1
        i <- i + 1
    return candidate

```

I need to prove that if a value appears more than $n \over 2$ times (let the value be named $M$) in the array then it will be returned.

$\mathbf{EDIT:}$ here's my 2 attempt. First we assume that the array $A$ contains at least 3 elements (if less then the proof is trivial). The element which appears more than $n/2$ times is $M$ else it's $M'$. Let a two-element combination of $MM'$ or $M'M$ be called $C$. Every time we traverse a $C$ the `count` decreases by one.

CASE 1: If the pattern is strictly alternating combinations of type $C$ then the first and the last element must be $M$ (otherwise $M$ will not appear more than $n/2$ times) and this means that after the last iteration the `candidate` is $M$.

CASE 2: We can see that after any number of adjacent $C$'s the counter will be $0$ and the `candidate` will be either $M$ or $M'$. It is given that more than $n/2$ elements of $M$ do exist in the array, so the number of $C$ combinations must be supplemented by at least $1$ occurrence of $k$ adjacent elements of $M$ either before $C$'s or after $C$'s. If it's after, then the next candidate is $M$ and it will continue to be so as long as we keep traversing $k$ elements of adjacent $M$'s. If it's before than the `count` will be at least $1$ before it proceeds to iterate through $C$'s and essentially it'll behave just like CASE 1.

I'm still aware that the proof is not perfect but I feel like it's an improvement. Suggestions/advice is very welcome.

# Answer
Let us prove the following claim by induction:

> Suppose that the first $i$ symbols contain $j$ copies of $\sigma$, and let $\delta = j-(i-j) = 2j-i$. After the $i$th iteration of the loop:
>
> (a) If $\delta \> 0$ then $candidate=\sigma$ and $count \geq \delta$.
>
> (b) If $\delta \leq 0$ then either $candidate=\sigma$ or $count \leq -\delta$.

This certainly holds for $i = 0$. Given that it holds for $i$, we now show it holds for $i':=i+1$ as well. Let $j,j'$ be the number of copies of $\delta$ in the first $i,i'$ symbols (respectively), and let $\delta=2j-i$, $\delta'=2j'-i'$. Define $candidate,candidate'$ and $count,count'$ as the values of these variables after $i,i'$ iterations (respectively). There are several cases to consider.

Case 1: the $i'$th symbol is $\sigma$.

Case 1a: $\delta \> 0$. The induction hypothesis states that $candidate = \sigma$ and $count \geq \delta$. Therefore $candidate' = \sigma$ and $count' = count+1 \geq \delta+1 = \delta'$.

Case 1b: $\delta = 0$, $candidate = \sigma$. This is the same as Case 1a.

Case 1c: $\delta = 0$ and $candidate \neq \sigma$. The induction hypothesis states that $count = 0$. Therefore $candidate' = \sigma$ and $count' = 1 = \delta'$.

Case 1d: $\delta \< 0$ and $candidate = \sigma$. This is the same as Case 1a.

Case 1e: $\delta \< 0$ and $candidate \neq \sigma$. The induction hypotehsis states that $count \leq -\delta$. Therefore either $candidate' = \sigma$, or $count' = count-1 \leq -(\delta+1) = -\delta'$.

Case 2: the $i'$th symbol is $\tau \neq \sigma$.

Case 2a: $\delta \> 0$. The induction hypothesis states that $candidate = \sigma$ and $count \geq \delta$. Therefore $candidate' = \sigma$ and $count' = count-1 \geq \delta-1 = \delta'$.

Case 2b: $\delta = 0$ and $candidate = \sigma$. If $count = 0$ then $count' = 1 = -\delta'$. Otherwise, $candidate' = \sigma$.

Case 2c: $\delta = 0$ and $candidate \neq \sigma$. The induction hypothesis states that $count = 0$, and so $count' = 1 = -\delta'$.

Case 2d: $\delta \< 0$ and $candidate = \sigma$. This is the same as Case 2b (with $1 \leq -\delta'$ in the first case).

Case 2e: $\delta \< 0$ and $candidate \neq \sigma$. If $candidate = \tau$ then $count' = count + 1 \leq -(\delta-1) = -\delta'$. If $candidate \neq \tau$ then $count' = 1 \leq -\delta'$.

---

Given the claim, we see that if $\sigma$ appears more than $n/2$ times, then when $i=n$ we have $\delta \> 2(n/2)-n \> 0$, and so $candidate = \sigma$.
> 1 votes

# Answer
*Note:* In my opinion, although the answer given by @Sunny Wang is slightly hard to follow, it is in the right direction. Maybe the author would like to come back and improve his/her answer. Therefore, I will only give some high-level hints here.

Playing with some examples, you will find that the program amounts to keeping eliminating (by decreasing the counter, of course) a pair of *distinct* elements. Therefore, *if* a value appears more than $\frac{n}{2}$ times, it (and only it; this is also important) survives and will be returned.
> 1 votes

# Answer
I'd like to try to use **contradiction** to prove your algorithm.

The algorithm can be described with a **stack model**. The procedure is equal to the operation of pushing and popping elements while scanning an array. As for each element scanned, if the stack is empty or the element is equal to the element at the top of the stack, push it; or pop an element. Since we initialize the stack with the array's first element and we push one element as soon as the stack is empty, our popping one element operation in each loop will remain the stack operations legal.

For the elements in the stack meantime are equal, the value which appears more than $\frac{n}{2}$ times must be returned. We can prove it by **contradiction**. Assume the value is not returned, any element of this value will lead to another element of a different value be popped. But it is impossible. We do not have so many elements. So the assumption is not correct. In this way, we prove that the algorithm is correct.
> 0 votes

# Answer
Proof by induction:

If $n=1$, the algorithm returns `A[1]`, which is correct.

if $n\>1$, and $M$ appears $t$ times in `A`, then either:

* it appears $t$ times in `A[1],...,A[n-1]` and `A[n]!=M`, in which case the nth iteration of the while loop takes `candidate=M` and `count`$=t-(n-1-t)=2t-n+1$, but $t\>n/2$ implies $2t-n+1\>0$ therefore `count>0` and `alg1` returns $M$.
* it appears $t-1$ times in `A[1],...,A[n-1]` and `A[n]=M`, in which case, in the nth iteration of the while loop, either `candidate=M` and `alg1` returns `M`, or `candidate!=M` and `count=0` and `alg1` returns `A[n]` which is $M$.
> 0 votes

---
Tags: correctness-proof
---


# Question
Title: Understanding how to decide whether a language for a DFA is decidable
So from what I understand, if a language is recognisable then using a TM it can be accepted and halted or rejected or halted, however a language that is decidable can be accepted and always halts on rejection?

Given the language $A\_{\mathrm{DFA}} = \\{\langle A \rangle\mid A \text{ is a DFA and } L(A) = \\{0, 1\\}^∗\\}$ , I want to determine if it is decidable.

What I have come up with so far is that it is a recognisable language, I don't believe it can be rejected, only accepted and halted due to the fact once the read head comes across a blank it can just accept it. Is this the way I should be thinking? Am I correct in thinking it is not decidable or is this not a valid way to argue the point?

What should my process of thinking be when I am trying to prove it by contradiction if it is not decidable?

Thanks in advance for any tips!

# Answer
Let me rephrase the question:

> Is there an algorithm that, given a DFA, decides whether its language is $\\{0,1\\}^\*$?

Such algorithms do exist, hence the corresponding set is decidable.

I'm not sure what your instructor means by "high level description of a Turing machine", but what they should have meant is "describe an algorithm that solves the problem". Hopefully you already know how to do that.
> 1 votes

---
Tags: turing-machines, finite-automata, undecidability, proof-techniques
---


# Question
Title: How does recursion work in void method java
```
class test{
  public static void main(String args[]){
  int n = 5;
  mystery(n);
}

  public static void mystery(int n)
{

  if(n == 0 || n==1)
  {
   return;
  }
  mystery(n-2);
  System.out.println(n);
  mystery(n-1);
  }
}

```

This a very simple void method code.

I want to know what happen during the recursion and why is the output is like that??

the output to the console is:

3

2

5

2

4

3

2

# Answer
Consider the following binary tree `mystery-tree(5)`

```
         5
        / \
       /   \
      /     \
     4       3
    / \     /
   /   \   /
  3     2 2
 /
2

```

Clearly `mystery-tree(5)` is defined by:

```
mystery-tree(1) = null
mystery-tree(2) = null
mystery-tree(n) = Node n mystery-tree(n - 1) mystery-tree(n - 2)

```

Clearly the output you showed is just the reversed in-order traversal of this tree, i.e. `mystery(n) = for i in reversed(in-order(mystery-tree(n))) { println(n) }`.
> 1 votes

---
Tags: recursion, java
---


title: Approximate Similarity Search

text:
# Question
Title: Approximate Similarity Search
I am implementing an approximate similarity search using multi-index hashing. I have a set (T) of millions of strings (of same length) and I have a query string(P) (or set of strings) that needs to find similar strings former set. My implementation is the following (assuming length is 64 and similarity is defined as hamming distance less than 15)

> 1. Divide each string in T into 16 parts and store each part in a hash table where key is the hash value and value is a vector containing the indices of strings. Ex \< 198675, {2, 7, 8, 456}\> \[I have 16 such hash tables for each portion of the string\]
> 2. For a query string P, divide it into 16 parts and for each part collect the set of indices(if present) from each hash table and then take the union of all. That becomes a small search space.
> 3. Calculate the hamming distance between the query and the resulting set of strings.

I have implemented in C++ and it's working fine, but I am still wondering how could I make it more faster. Any suggestions would be appreciated.

# Answer
Your method is reasonable. There are other possibilities as well.

## Randomized algorithm: locality-sensitive hashing

Here is a randomized algorithm that finds all matches with high probability (probability $1-\epsilon$ where $\epsilon$ is exponentially small, but not zero). It will probably be more efficient.

Build 100 tables. Each table is constructed as follows: Randomly pick a subset of 8 positions (out of the 64 possible positions). Now a string is hashed by keeping only the 8 characters from those 8 positions, and the string is stored in the hashtable keyed on that hash. For instance, if the positions associated with a particular table are $i\_1,i\_2,\dots,i\_8$, then the string $S$ is hashed by hashing $S\[i\_1\],S\[i\_2\],\dots,S\[i\_8\]$ and using that hash value as the key to store $S$ in the table. Each table has a different and randomly generated subset of positions.

Store each of the millions strings in all 100 tables. When you get a query string $Q$, look it up in each of the 100 tables to find all possible matches, take the union of those possible matches, and calculate the Hamming distance between $Q$ and each possible match.

This is very similar to your method, but each "part" is longer (8 characters instead of 4 characters), so there will probably be many fewer "false matches" from the hashtable.

There is no guarantee that this approach will find all valid matches, but most likely it will. The probability that a valid match is not found is

$$(1-(49/64)^8)^{100} \approx 0.0000035,$$

so missing a match is unlikely. You can tune the probability of a missed match by adjusting the number of tables, and you can adjust the parameters ($8,100$) to find the setting that gives you the best possible performance.

This is effectively a form of locality-sensitive hashing (LSH). There may be other schemes worth investigating. You could also look at MinHash.

## Trie

Another approach is to store the dictionary of millions of strings in a trie data structure. Given a query string $Q$, you can start traversing the trie, doing a recursive breadth-first search to explore all paths that are at distance at most 15 from $Q$. For many paths, you'll be able to immediately terminate the search.
> 0 votes

---
Tags: strings, hashing, searching
---