# Question
Title: Decision problems vs "real" problems that aren't yes-or-no
I read in many places that some problems are difficult to approximate (it is **NP-hard** to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. Also for each desired approximation factor, there are many answers that are correct and many that are wrong, and this changes with the desired approximation factor!

So how can one say that this problem is NP-hard?

*(inspired by the second bullet in How hard is counting the number of simple paths between two nodes in a directed graph?)*

# Answer
> 31 votes
As you said, there is no decision to make, so new complexity classes and new types of reductions are needed to arrive at a suitable definition of *NP-hardness* for *optimization-problems*.

One way of doing this is to have two new classes **NPO** and **PO** that contain *optimizations problems* and they mimic of course the classes **NP** and **P** for decision problems. New reductions are needed as well. Then we can recreate a version of *NP-hardness* for optimization problems along the lines that was successful for decision problems. But first we have to agree what an *optimization-problem* is.

Definition: Let $O=(X,L,f,opt)$ be an *optimization-problem*. $X$ is the set of *inputs* or *instances* suitable encoded as strings. $L$ is a function that maps each instance $x\in X$ onto a set of strings, the *feasible solutions* of instance $x$. It is a set because there are many solutions to an optimization-problem. Thus we haven an *objective function* $f$ that tells us for every pair $(x, y)$ $y\in L(x)$ of instance and solution its *cost* or *value*. $opt$ tells us whether we are maximizing or minimizing.

This allows us to define what an *optimal solution* is: Let $y\_{opt}\in L(x)$ be the *optimal solution* of an instance $x\in X$ of an optimization-problem $O=(X,L,f,opt)$ with $$f(x,y\_{opt})=opt\\{f(x,y')\mid y'\in L(x)\\}.$$ The optimal solution is often denoted by $y^\*$.

Now we can define the class **NPO**: Let $NPO$ be the set of all optimization-problems $O=(X,L,f,opt)$ with:

1. $X\in P$
2. There is a polynomial $p$ with $|y|\le p(|x|)$ for all instances $x\in X$ and all feasible solutions $y\in L(x)$. Furthermore there is an deterministic algorithm that decides in polynomial time whether $y\in L(x)$.
3. $f$ can be evaluated in polynomial time.

The intuition behind it is:

1. We can verify efficiently if $x$ is actually a valid instance of our optimization problem.
2. The size of the feasible solutions is bounded polynomially in the size of the inputs, And we can verify efficiently if $y\in L(x)$ is a fesible solution of the instance $x$.
3. The value of a solution $y\in L(x)$ can be determined efficiently.

This mirrors how $NP$ is defined, now for **PO**: Let $PO$ be the set of all problems from $NPO$ that can be solved by an deterministic algorithm in polynomial time.

Now we are able to define what we want to call an *approximation-algorithm*: An *approximation-algorithm* of an optimization-problem $O=(X,L,f,opt)$ is an algorithm that computes a feasible solution $y\in L(x)$ for an instance $x\in X$.

Note: That we don’t ask for an *optimal* solution we only what to have a *feasible* one.

Now we have two types of errors: The *absolute error* of a feasible solution $y\in L(x)$ of an instance $x\in X$ of the optimization-problem $O=(X,L,f,opt)$ is $|f(x,y)-f(x,y^\*)|$.

We call the absolute error of an approximation-algorithm $A$ for the optimization-problem $O$ bounded by $k$ if the algorithm $A$ computes for every instance $x\in X$ a feasible solution with an absolute error bounded by $k$.

Example: According to the Theorem of Vizing the *chromatic index* of a graph (the number of colours in the edge coloring with the fewest number of colors used) is either $\Delta$ or $\Delta+1$, where $\Delta$ is the maximal node degree. From the proof of the theorem an approximation-algorithm can be devised that computes an edge coloring with $\Delta+1$ colours. Accordingly we have an approximation-algorithm for the $\mathsf{Minimum-EdgeColoring}$-Problem where the absolute error is bounded by $1$.

This example is an exception, small absolute errors are rare, thus we define the *relative error* $\epsilon\_A(x)$ of the approximation-algorithm $A$ on instance $x$ of the optimization-problem $O=(X,L,f,opt)$ with $f(x,y)\>0$ for all $x\in X$ and $y\in L(x)$ to be

$$\epsilon\_A(x):=\begin{cases}0&f(x,A(x))=f(x,y^\*)\\\frac{|f(x,A(x))-f(x,y^\*)|}{\max\\{f(x,A(x)),f(x,y^\*)\\}}&f(x,A(x))\ne f(x,y^\*)\end{cases}$$

where $A(x)=y\in L(x)$ is the feasible solution computed by the approximation-algorithm $A$.

We can now define approximation-algorithm $A$ for the optimization-problem $O=(X,L,f,opt)$ to be a *$\delta$-approximation-algorithm* for $O$ if the relative error $\epsilon\_A(x)$ is bounded by $\delta\ge 0$ for every instance $x\in X$, thus $$\epsilon\_A(x)\le \delta\qquad \forall x\in X.$$

The choice of $\max\\{f(x,A(x)),f(x,y^\*)\\}$ in the denominator of the definition of the relative error was selected to make the definition symmetric for maximizing and minimizing. The value of the relative error $\epsilon\_A(x)\in\[0,1\]$. In case of a maximizing problem the value of the solution is never less than $(1-\epsilon\_A(x))\cdot f(x,y^\*)$ and never larger than $1/(1-\epsilon\_A(x))\cdot f(x,y^\*)$ for a minimizing problem.

Now we can call an optimization-problem $\delta$-approximable if there is a $\delta$-approximation-algorithm $A$ for $O$ that runs in polynomial time.

We do not want to look at the error for every instance $x$, we look only at the worst-case. Thus we define $\epsilon\_A(n)$, the *maximal relativ error* of the approximation-algorithm $A$ for the optimization-problem $O$ to be $$\epsilon\_A(n)=\sup\\{\epsilon\_A(x)\mid |x|\le n\\}.$$

Where $|x|$ should be *the size* of the instance.

Example: A maximal matching in a graph can be transformed in to a minimal node cover $C$ by adding all incident nodes from the matching to the vertex cover. Thus $1/2\cdot |C|$ edges are covered. As each vertex cover including the optimal one must have one of the nodes of each covered edge, otherwise it could be improved, we have $1/2\cdot |C|\cdot f(x,y^\*)$. It follows that $$\frac{|C|-f(x,y^\*)}{|C|}\le\frac{1}{2}$$ Thus the greedy algorithm for a maximal matching is a $1/2$-approximatio-algorithm for $\mathsf{Minimal-VertexCover}$. Hence $\mathsf{Minimal-VertexCover}$ is $1/2$-approximable.

Unfortunately the relative error is not always the best notion of quality for an approximation as the following example demonstrates:

Example: A simple greedy-algorithm can approximate $\mathsf{Minimum-SetCover}$. An analysis shows that $$\frac{|C|}{|C^\*|}\le H\_n\le 1+\ln(n)$$ and thus $\mathsf{Minimum-SetCover}$ would be $\frac{\ln(n)}{1+\ln(n)}$-approximable.

If the relative error is close to $1$ the following definition is advantageous.

Let $O=(X,L,f,opt)$ be an optimization-problem with $f(x, y)\>0$ for all $x\in X$ and $y\in L(x)$ and $A$ an approximation-algorithm for $O$. The *approximation-ratio* $r\_A(x)$ of feasible solution $A(x)=y\in L(x)$ of the instance $x\in X$ is $$r\_A(x)=\begin{cases}1&f(x,A(x))=f(x,y^\*)\\\max\left\\{ \frac{f(x,A(x))}{f(x, y^\*)},\frac{f(x, y^\*)}{f(x, A(x))}\right\\}&f(x,A(x))\ne f(x,y^\*)\end{cases}$$

As before we call an approximation-algorithm $A$ an $r$-approximation-algorithm for the optimization-problem $O$ if the approximation-ratio $r\_A(x)$ is bounded by $r\ge1$ for every input $x\in X$. $$r\_A(x)\le r$$ And yet again if we have an $r$-approximation-algorithm $A$ for the optimization-problem $O$ then $O$ is called *$r$-approximable*. Again we only care about to the worst-case and define the *maximal approximation-ratio* $r\_A(n)$ to be $$r\_A(n)=\sup\\{r\_A(x)\mid |x|\le n\\}.$$ Accordingly the approximation-ratio is larger than $1$ for suboptimal solutions. Thus better solutions have smaller ratios. For $\mathsf{Minimum-SetCover}$ we can now write that it is $(1+\ln(n))$-approximable. And in case of $\mathsf{Minimum-VertexCover}$ we know from the previous example that it is $2$-approximable. Between relative error and approximation-ratio we have simple relations: $$r\_A(x)=\frac{1}{1-\epsilon\_A(x)}\qquad \epsilon\_A(x)=1-\frac{1}{r\_A(x)}.$$

For small deviations from the optimum $\epsilon\<1/2$ and $r\<2$ the relative error is advantageous over the approximation-ratio, that shows its strengths for large deviations $\epsilon\ge 1/2$ and $r\ge 2$.

The two versions of $\alpha$-approximable don’t overlap as one version has always $\alpha\le 1$ and the other $\alpha\ge 1$. The case $\alpha=1$ is not problematic as this is only reached by algorithms that produce an exact solution and consequentially need not be treated as approximation-algorithms.

Another class appears often **APX**. It is define as the set of all optimization-problems $O$ from $NPO$ that haven an $r$-approximation-algorithm with $r\ge1$ that runs in polynomial time.

We are almost through. We would like to copy the successful ideas of *reductions* and *completness* from complexity theory. The observation is that many NP-hard decision variants of optimization-problems are reducible to each other while their optimization variants have different properties regarding their approximability. This is due to the polynomialtime-Karp-reduction used in NP-completness reductions, which does not preserve the objective function. And even if the objective functions is preserved the polynomialtime-Karp-reduction may change the quality of the solution.

What we need is a stronger version of the reduction, which not only maps instances from optimization-problem $O\_1$ to instances of $O\_2$, but also good solutions from $O\_2$ back to good solutions from $O\_1$.

Hence we define the *approximation-preserving-reduction* for two optimization-problems $O\_1=(X\_1,L\_1,f\_1,opt\_1)$ and $O\_2=(X\_2,L\_2,f\_2,opt\_2)$ from $NPO$. We call $O\_1$ $AP$-reducible to $O\_2$, written as $O\_1\le\_{AP} O\_2$, if there are two functions $g$ and $h$ and a constant $c$ with:

1. $g(x\_1, r)\in X\_2$ for all $x\_1\in X\_1$ and rational $r\>1$
2. $L\_2(g(x, r\_1))\ne\emptyset$ if $L\_1(x\_1)\ne\emptyset$ for all $x\_1\in X\_1$ and rational $r\>1$
3. $h(x\_1, y\_2, r)\in L\_1(x\_1)$ for all $x\_1\in X\_1$ and rational $r\>1$ and for all $y\_2\in L\_2(g(x\_1,r))$
4. For fixed $r$ both functions $g$ and $h$ can be computed by two algorithms in polynomial time in the length of their inputs.
5. We have $$f\_2(g(x\_1,r),y\_2)\le r \Rightarrow f\_1(x\_1,h(x\_1,y\_2,r))\le 1+c\cdot(r-1) $$ for all $x\_1\in X\_1$ and rational $r\>1$ and for all $y\_2\in L\_2(g(x\_1,r))$

In this definition $g$ and $h$ depend on the quality of the solution $r$. Thus for different qualities the functions can differ. This generality is not always needed and we just work with $g(x\_1)$ and $h(x\_1, y\_2)$.

Now that we have a notion of a reduction for optimization-problems we finally can transfer many things we know from complexity theory. For example if we know that $O\_2\in APX$ and we show that $O\_1\le\_{AP} O\_2$ it follows that $O\_1\in APX$ too.

Finally we can define what we mean by $\mathcal{C}$-hard and $\mathcal{C}$-complete for optimization-problems:

Let $O$ be an optimization-problem from $NPO$ and $\mathcal{C}$ a class of optimization-problems from $NPO$ then $O$ is called *$\mathcal{C}$-hard* with respect to $\le\_{AP}$ if for all $O'\in\mathcal{C}$ $O'\le\_{AP} O$ holds.

Thus once more we have a notion of a *hardest* problem in the class. Not surprising a *$\mathcal{C}$-hard* problem is called $\mathcal{C}$-complete with respect to $\le\_{AP}$ if it is an element of $\mathcal{C}$.

Thus we can now talk about $NPO$-completness and $APX$-completness etc. And of course we are now asked to exhibit a first $NPO$-complete problem that takes over the role of $\mathsf{SAT}$. It comes almost naturally, that $\mathsf{Weighted-Satisfiability}$ can be shown to be $NPO$-complete. With the help of the PCP-Theorem one can even show that $\mathsf{Maximum-3SAT}$ is $APX$-complete.

# Answer
> 21 votes
Usually what's shown is the NP-hardness of a "Gap" version of the problem. For example, suppose that you want to show that it's hard to approximate SET COVER to within a factor of 2.

You define the following "promise" instance of SET COVER that we'll call 2-GAP-SET-COVER:

Fix some number $\ell$. 2-GAP-SET-COVER consists of all instances of set cover where the size of the optimal set cover is either:

* at most $\ell$
* at least $2\ell$

Suppose we show that the problem of deciding which of the two cases a problem falls into is NP-complete. Then we've shown that approximating SET COVER to within a factor of 2 is NP-hard, because we could use such an algorithm to distinguish these two cases.

# Answer
> 4 votes
The two existing answers are very informative but I don't think either of them really answers the question, which is, "How can a problem that isn't even a decision problem be NP-hard, when NP is a class of decision problems?"

The answer is to remember what NP-hard means. A problem $L$ is NP-hard under some kind of reductions if every problem in NP can be reduced to $L$. (And $L$ is NP-complete if it's NP-hard and in NP.) Informally, NP-hard means "If I could solve this problem, I could solve everything in NP", even if the problem you're talking about isn't in NP. NP-hardness does not require membership of NP, but it does need the right notion of reduction.

Some examples.

1. Any NEXPTIME-complete problem $L$ is NP-hard under polynomial-time many-one reductions. Any problem in NP is in NEXPTIME so is reducible to $L$ by definition. By the time hierarchy theorem, $L$ cannot be in NP, so $L$ is not NP-complete.
2. #SAT is the problem of computing the number of satisfying assignments to CNF formulas. It is clearly not in NP because, as you observe, NP is a class of decision problems and #SAT is not one of those. However, #SAT is NP-hard under polynomial-time Turing reductions because we can reduce SAT to it. Given a SAT instance, we ask how many satisfying assignments there are: if there is at least one, we say "satisfiable"; otherwise, "unsatisfiable".
3. Let APPROXSAT be the problem of computing a number which is within a factor of ten of the number of satisfying assignments to a CNF formula $\varphi$. Just to be annoying, let's say you're allowed to round down so, if $\varphi$ has, say, three satisfying assignments, the algorithm is allowed to think "0.3" and round that down to zero. This is NP-hard under polynomial-time Turing reductions because we can still reduce SAT to it. Given a CNF formula $\varphi$, ask for the number of satisfying assignments to $\varphi'=\varphi \wedge (Z\_1\vee \dots \vee Z\_{10})$, where the $Z\_i$ are new variables. $\varphi'$ is satisfiable if, and only if, $\varphi$ is, but $\varphi'$ is guaranteed to have more than 1,000 satisfying assignments, if it has any. So, $\varphi$ is satisfiable if, and only if, the APPROXSAT algorithm says that $\varphi'$ has at least 100 satisfying assignments.

---
Tags: complexity-theory, time-complexity, np-hard, approximation
---


title: Interest in Artificial Intelligence

text:
# Question
Title: Interest in Artificial Intelligence
(If I am posting this in the wrong StackExchange site, then please direct me to the correct one)

Okay, so some small background first: I am currently third-years student in Computer Science on the university.

I have big interest in Artificial Intelligence and I was wondering if I could practice it somewhere, for example a challenge versus other people that gets updated/executed every set time period (possibly per week).

Example of a challenge that I do like:

* Assume that there is an infrastructure set by the organisator to run a poker game via poker bots. I would like to code such a poker bot that would challenge other people, by using AI via a statistical approach, but also via doing fake moves, remembering what the other players have done so far.

It could even be fun to add in real players and see who wins in the end.

Example of a challenge I do not like:

* Given a partially filled in Sudoku puzzle, make an algorithm that solves the puzzle.

Why don't I like the Sudoku? Well, I would rather challenge other players or have an interactive way of using AI. I don't even think that an algorithm like this involves any AI. However when asked to do this exercise as part of my study, I didn't mind it, because it was still an interesting programming problem.

Has anyone else been in the same boat? Or is someone being in the same boat currently?

Please share any thoughts, I definately would like to practice around with this, but for example doing the poker bot thing just by myself would be somewhat... dull.

Regards.

edit: Forgot to add, but for a challenge or anything I would prefer Java, as I am used to doing that. But any raw format (so just sending data to a channel and receiving data from a channel would also do)

# Answer
> 2 votes
Background first, too: I am currently third-years student in Information and Computing Science at a Chinese university.

I think most of your problems can be solved by common algorithms. For example, Sudoku game, can be solved by searching, or DLX(Dancing links and X algorithm) if you wanna improve the performance.

I think you can do some exercises to improve your basic skills. Some online judge services are suggested, such as Codeforces, SPOJ, poj.org, etc. There's an interesting game on a contest few days before. codeforces-\>contest-\>346-\>problem-\>A

Some of AI algorithms are based on searching. To improve the performance, we have some optimizing skills such like evaluation function(e.g. A\* algorithm) or randomization(e.g. GA or Simulated annealing). Another part is base on learning, responses of a quest are according to large amount of data(e.g. ANN, and some algorithms for classifying).

Huge amount of code cannot be avoided. And some Lisp symbolic programming languages are good at such things. You can learn it if you're interested.

So just enjoy playing with what you make!

---
Tags: artificial-intelligence
---


# Question
Title: Solving recurrences using substitution method
I already have a solution for this problem but it's just not making sense to me.

Here is the problem (It's from Introduction to Algorithms by CLRS found in CH.4):

> Show $T(n) = 2T(\lfloor n/2 \rfloor +17)+n$ is $O(n \log n)$

This is what I have so far:

So Assume $T(k) \leq cn\lg n$, for $k\<n$.

$\qquad \begin{align\*} T(n) &= 2T(\lfloor n/2 \rfloor +17)+n \\ &\leq 2c(\lfloor n/2 \rfloor +17)\lg(\lfloor n/2 \rfloor + 17) +n \\ &\leq 2c(n/2 + 17) \lg (n/2 + 17) + n \\ &= c(n + 34) \lg((n+34)/2)+ n \end{align\*}$

And this is where I stop understanding what is going on. Looking at the solution to this problem tells me:

> Note that $(n + 34)/2 \leq (3n)/4$ for $n \geq 68$ so that $\lg((n + 34)/2) \leq \lg((3n)/4) = \lg(n) + \lg(3/4)$ for $n \geq 68$.

But it fails to tell me why/how we know that $(n+34)/2 \leq 3n/4$ for $n \geq 68$. Where did this number come from and how would I arrive at this if I did not know the solution beforehand?

# Answer
The complexity in your proof is that you have addition in you logarithm, and you need that complexity to go away. So lets get rid of that 34, by just making $n \ge 34$, so now

$$\log\left( \frac{n + 34}{2} \right) \le \log\left( \frac{n + n}{2} \right) = \log(n).$$

I am not sure why the book chose 68, but really its the same argument. If $n \ge 68$, then $n/2 \ge 34$. Thus

$$\log\left( \frac{n + 34}{2} \right) \le \log\left( \frac{n + n/2}{2} \right) = \log\left( \frac{2n + n}{4} \right) = \log\left(\frac{3n}{4}\right) = \log(n) + \log(3/4).$$
> 6 votes

# Answer
Let $n\>34$ be an integer. We consider the sequence $u\_0=n,u\_{k+1}=floor(u\_k/2)+17$. There is $p$ s.t. $u\_p=34$ and we stop the process. Thus, if we know $T(34)$, then we use a back-tracking to obtain $T(n)$. The number of step is in $O(log(n))$. Inded the value $\delta=17$ is not important. In this case $\log\_2(n)\<p\<\log\_2(n)+1$. If $\delta=1000$, then let $q$ s.t. $u\_q=2000$. Again $\log\_2(n)\<q\<\log\_2(n)+1$.

EDIT: Now the back-tracking: $T(u\_{k-1})=2T(u\_k)+u\_{k-1}$. $T(n)=T(u\_0)$ is in the form $a\_nT(34)+b\_n$ with $a\_n=O(n)$. Let $v\_p=0, v\_{k-1}=2v\_k+u\_{k-1}$ ; then $b\_n=v\_0$. It remains to show that $b\_n=O(n\log(n))$.

EDIT: At each step, $u\_{k-1}\approx 2u\_k$. Then one has approximately $v\_p=0,v\_{p-1}=2.0+2=2^1.1,v\_{p-2}=2.2+4=2^2.2,v\_{p-3}=2.8+8=2^3.3,v\_{p-4}=2.24+16=2^4.4,v\_{p-5}=2.64+32=2^5.5$ and, in general $v\_{p-k}=2^k.k$. Finally $b\_n\approx 2^p.p\approx n\log\_2(n)$. In fact, we can prove $T(n)=\Theta(nlog(n))$.

EDIT: Hi Harrison, your (or that of your book !) reasoning by recurrence does not work because you obtain only $T(n)\leq cn\log(n)+n+o(n)$ instead of $T(n)\leq c(n+1)\log(n+1)=cn\log(n)+c\log(n)+o(\log(n))$.
> 0 votes

---
Tags: asymptotics, proof-techniques, recurrence-relation
---


# Question
Title: Ordering a list of lists subject to constraints
I have encountered a surprisingly challenging problem arranging a matrix-like (List of Lists) of values subject to the following constraints (or deciding it is not possible):

A matrix of m randomly generated rows with up to n distinct values (no repeats within the row) arrange the matrix such that the following holds (if possible):

1) The matrix must be "lower triangular"; the rows must be ordered in ascending lengths so the only "gaps" are in the top right corner

2) If a value appears in more than one row it must be in the same column (i.e. rearranging the order of values in a row is allowed).

Example 1 - which has a solution

A B
C E D
C A B

becomes (as one solution)

A B
E D C
A B C

since A, B and C all appear in columns 1, 2 and 3, respectively.

Example 2 - which has no solution

A B C
A B D
C B D

has no solution since the constraints require the third row to have the C and D in the third column which is not possible.

In my attempts to solve this naively (e.g. by sorting shortest rows to longest and then trying to order the rows from "most in common" to least and then simple reordering within the row) there are always scenarios that it thinks aren't solvable but are. In other words backtracking/exhaustive search appears to be required, which is OK but I haven't yet struck onto a nice concise (ideally functional) algorithm for this.

# Answer
> 2 votes
This problem is an instance of the list coloring problem. The list coloring problem is a variant of the graph color problem, where additionally have constraints that provide for each vertex a list of allowable colors that can be used for that vertex.

Here's the relationship. Let $V$ denote the set of distinct values that appear in any row. In Example 1, $V=\\{A,B,C,D,E\\}$; in Example 2, $V=\\{A,B,C,D\\}$. Form an undirected graph $G$ where $V$ is the vertex set (so each value is a vertex). Add an edge $(u,v)$ between two values if there is some row where those two vertices appear together.

Now suppose we want to arrange these in a matrix with $c$ columns (i.e., $c$ is the length of the longest row). We'll imagine having $c$ colors, numbered from $1$ to $c$, where color $i$ corresponds to the $i$th column. If the value $v$ is colored $i$, we take this to mean that every appearance of value $v$ should appear in column $i$.

Now from each row that is less than $c$ values long, we obtain some constraints. In particular, if we have a row that is $\ell$ values long, then each value in that row needs to be colored with a color in the set $\\{1,2,\dots,\ell\\}$ (to ensure the lower-triangular requirement). These are the lists that make this a list coloring problem.

Now any solution to the list coloring problem yields a solution to your problem: the colors tell you what column to put each value into, which tells you how to permute each of your rows to form a valid solution. Therefore, you can use any algorithm for the list coloring problem to solve your problem.

# Answer
> 1 votes
To solve this problem in practice, here's the first thing I would try:

* Try using a SAT solver.

As long as your problem instance isn't too large, I suspect that a SAT solver will be very effective at solving this problem.

Here is how you use a SAT solver. Introduce boolean variables $x\_{v,j}$ (where $v$ ranges over values, and $j$ ranges over columns). If your original matrix has $n$ distinct values and the longest row has $c$ columns, you'll have $cn$ boolean variables ($v$ ranges over $n$ distinct values, and $j$ ranges from $1$ to $c$). The intended meaning of $x\_{v,j}$ is that value $v$ appears only in column $j$.

Now add boolean constraints as follows:

* If the value $v$ appears somewhere in the input, then it needs to appear in some row. This gives us the constraint $x\_{v,1} \lor x\_{v,2} \lor \dots \lor x\_{v,c}$ for each value $v$.
* If the value $v$ appears in a row of length $\ell$, then the value $v$ must appear in one of the first $\ell$ columns. Consequently, for each $v$ we get the constraint $x\_{v,1} \lor x\_{v,2} \lor \dots \lor x\_{v,\ell}$, where $\ell$ is the length of the shortest row containing the value $v$. (This actually subsumes the constraint in the previous bullet, so that one can be omitted.)
* The value $v$ appears in at most one column. This gives us the constraint $\neg x\_{v,j} \lor \neg x\_{v,k}$ for each value $v$ and each pair $j,k$ of columns (where $1 \le j \< k \le c$).
* If there is some row that contains both the value $u$ and the value $v$, then both $u$ and $v$ cannot be placed into the same column. Consequently, we get the constraint $\neg x\_{u,j} \land \neg x\_{v,j}$ for each $j=1,2,\dots,c$ and each pair of values $u,v$ that appear together in the same row.

Then let the SAT solver crank away. Give it a try -- I think it might just work on the problems you have in practice.

To learn more about using SAT solvers to solve graph coloring problems, see, e.g., this nifty video.

# Answer
> 1 votes
I needed a solution in a functional language (XQuery) so I implemented this first in Scala due to its expressiveness and I post the code below. It uses a brute-force, breadth first style search for solutions. I'm only interested in a single solution (if one exists) so the algorithm throws away the extra solutions.

```
def order[T](listOfLists: List[List[T]]): List[List[T]] = {

def isConsistent(list: List[T], listOfLists: List[List[T]]) = {
  def isSafe(list1: List[T], list2: List[T]) =
    (for (i <- list1.indices; j <- list2.indices) yield
      if (list1(i) == list2(j)) i == j else true
      ).forall(_ == true)

  (for (row <- listOfLists) yield isSafe(list, row)).forall(_ == true)
}

def solve(fixed: List[List[T]], remaining: List[List[T]]): List[List[T]] =
  if (remaining.isEmpty)
    fixed        // Solution found so return it
  else
    (for {
      permutation <- remaining.head.permutations.toList
      if isConsistent(permutation, fixed)
      ordered = solve(permutation :: fixed, remaining.tail)
      if !ordered.isEmpty
    } yield ordered) match {
      case solution1 :: otherSolutions =>       // There are one or more solutions so just return one
        solution1

      case Nil =>   // There are no solutions
        Nil
    }

// Ensure each list has unique items (i.e. no dups within the list)
  require (listOfLists.forall(list => list == list.distinct))

  /*
   * The only optimisations applied to an otherwise full walk through all solutions is to sort the list of list so that the lengths
   * of the lists are increasing in length and then starting the ordering with the first row fixed i.e. there is one degree of freedom
   * in selecting the first row; by having the shortest row first and fixing it we both guarantee that we aren't disabling a solution from being
   * found (i.e. by violating the "lower triangular" requirement) and can also avoid searching through the permutations of the first row since
   * these would just result in additional (essentially duplicate except for ordering differences) solutions.
   */
    //solve(Nil, listOfLists).reverse           // This is the unoptimised version
    val sorted = listOfLists.sortWith((a, b) => a.length < b.length)
    solve(List(sorted.head), sorted.tail).reverse
}

```

---
Tags: algorithms, np-complete, recursion
---


# Question
Title: Complexity of a recursive bignum multiplication algorithm
We have started learning about analysis of recursive algorithms and I got the gist of it. However there are some questions, like the one I'm going to post, that confuse me a little.

### The exercise

> Consider the problem of multiplying two big integers, i.e. integers represented by a large number of bits that cannot be handled directly by the ALU of a single CPU. This type of multiplication has applications in data security where big integers are used in encryption schemes. The elementary-school algorithm for multiplying two n-bit integers has a complexity of . To improve this complexity, let x and y be the two n-bit integers, and use the following algorithm
>
> ```
> Recursive-Multiply(x,y)
>   Write  x = x1 * 2^(n/2)+x0  //x1 and x0 are high order and low order n/2 bits
>        y = y1 * 2^(n/2)+y0//y1 and y0  are high order and low order n/2 bits
>   Compute x1+x0  and y1+y0
>   p = Recursive-Multiply (x1+x0,y1+y0)
>   x1y1 = Recursive-Multiply (x1,y1)
>   x0y0 = Recursive-Multiply (x0,y0)
>   Return  x1y1*2^n + (p-x1y1-x0y0)*2^(n/2)+x0y0
>
> ```
>
> (a) Explain how the above algorithm works and provides the correct answer.
>
> (b) Write a recurrence relation for the number of basic operations for the above algorithm.
>
> (c) Solve the recurrence relation and show that its complexity is $O(n^{\lg 3})$

### My conjecture

1. Since the method is being called three times, the complexity is going to be $3C(n/2) + n/2$.

### My questions

1. What do they mean by hi-lo order bits?
2. How can I use a recurrence relation on this if I don't know how each recursion works?

# Answer
The idea is to divide each $n$-bit integer into two halves of $n/2$ bits. For example, $10100010$ would be divided into $1010$ and $0010$. Naively, we would need to multiply four such halves, but in fact there is a way to do with only three. (This is similar to matrix multiplication algorithms such as Strassen's.) The algorithm described by the exercise is known as Karatsuba multiplication.

Regarding your other question, once you have reduced the computation of running time to a recurrence relation, you no longer need to understand anything more about the recursion in order to compute the running time - this is the main point of this abstraction.
> 3 votes

---
Tags: algorithms, time-complexity, recursion
---


# Question
Title: proving the error bound for a hypothesis
Given a hypothesis $h:X\rightarrow Y$ ($h$ is returned by an Empirical Risk Minimization (ERM) strategy with realizable case i.e. $h$ is consistent with the sample examples) over $X=\[0,1\]\subseteq R$ where $Y=\\{0,1\\}$ and $D$ is the uniform distribution over $X$. How can I prove that for the accuracy parameter $0\leq\epsilon\leq 1$ we might get $err\_D(h)\>\epsilon$? where $err\_D(h)$ is the true error of $h$ in the distribution $D$.

**This is a homework** and all I can do is using probabilities (as its shown in the course slides and other sources) to give some bounds on the error (i.e. $P(err\_D(h)\> \epsilon)\leq k(1-\epsilon)^m$) where $k$ is the number of *bad* hypotheses $|H\_B|$ s.t. ($\bar{h}\in H\_B | err\_D(\bar{h})\>\epsilon)$ and $m$ is the sample size.

MY question is: is there any other way (beside using probabilities) to prove this? It just seems odd to me when the question asks for a prove and the answer is about probability bound. I am new to the field of learning theory and this might seems like a silly question but I am really trying to understand the intuition behind using probabilities.

# Answer
Consider a case where the actual label is $1$ for all $x\in \[0,1\]$. Suppose $H$ consists of two classifiers: one that realizes this (i.e. $\forall x\in \[0,1\], h(x)=1$), and one that is almost entirely wrong: $g(x)=0$ except for some finite set of numbers $S$.

If the sample is exactly $S$, then both classifiers have the same error on the sample set (0), so you may choose $g$. However, you'll get that $err\_D(g)=1\>\epsilon$.

As mentioned in the comments, this doesn't really prove anything useful, since the probability that the sample will be exactly $S$ is $0$.
> 5 votes

---
Tags: machine-learning, learning-theory
---


title: Intro to Martin-Löf type theory

text:
# Question
Title: Intro to Martin-Löf type theory
What would be the best introduction to Per Martin-Löfs ideas about type theory? I've looked at some lectures from the Oregon PL summer school, but I'm still sort of puzzled by the following question:

*What is a type?*

I know what a set is, since you can define them by the usual ZF axioms and they have a very intuitive concrete model; just think of a basket filled with stuff. However, I've yet to see a reasonable definition of a type and I was wondering if there is some source that would distill this idea for dummy.

# Answer
> 32 votes
A type is a property of computations. It's what you write on the right-hand side of a colon.

Let me elaborate on that. Note that the terminology isn't completely standard: some articles or books may use different words for certain concepts.

A **term** is an element of an abstract syntax that is intended to represent computation. Intuitively, it's a parse tree. Formally, it's a finite tree where the nodes belong to some alphabet. An untyped **calculus** defines a syntax for terms. For example, the (untyped) lambda calculus contains terms (written $M$, $N$, etc.) built from three types of nodes:

* variables, of arity 0 (a denumerable collection thereof), written $x$, $y$, etc.;
* application of a variable, of arity 1 (a denumerable collection thereof, with a bijection to variables), written $\lambda x. M$, etc.;
* application, of arity 2, written $M \\, N$.

A term is a syntactic construction. A semantics relates terms to computations. There are many types of semantics, the most common being operational (describing how terms can be transformed into other terms) or denotational (describing terms by a transformation into another space, usually built from set theory).

A **type** is a property of terms. A **type system** for an untyped calculus describes which terms have which types. Mathematically, at the core, a type system is a relation between terms and types. More accurately, a type system is a family of such relations, indexed by **contexts** — typically, a context provides at least types for variables (i.e. a context is a partial function from variables to types), such that a term may only have a type in contexts that provide a type for all its free variables. What kind of mathematical object a type is depends on the type system.

Some type systems are described with types as sets, using notions of set theory such as intersection, union and comprehension. This has the advantage of resting upon familiar mathematical foundations. A limitation of this approach is that it doesn't allow reasoning about equivalent types.

Many type systems describe types themselves as terms in a calculus of types. Depending on the type system, these may be the same terms or different terms. I'll use the phrase **base term** to refer to a term of the calculus that describes computation. For example, the simply typed lambda calculus uses the following calculus of types (written $\tau$, etc.):

* base types, of arity 0 (a finite or denumerable collection thereof), written $A$, $B$, etc.;
* function, of arity 2, written $\tau\_0 \rightarrow \tau\_1$.

The relation between terms and types that defines the simply typed lambda calculus is usually defined by **typing rules**. Typing rules are not the only way to define a type system, but they are common. They work well for compositional type systems, i.e. type systems where the type(s) of a term is built from the types of subterms. Typing rules define a type system inductively: each typing rule is an axiom that states that for any instantiation of the formulas above the horizontal rule, the formula below the rule is also true. See How to read typing rules? for more details. Does there exist a Turing complete typed lambda calculus? may also be of interest.

For the simply typed lambda calculus, the **typing judgement** $\Gamma \vdash M : \tau$ means that $M$ has the type $\tau$ in the context $\Gamma$. I've omitted the formal definition of contexts. $$ \dfrac{x:\tau \in \Gamma}{\Gamma \vdash x : \tau}(\Gamma) \qquad \dfrac{\Gamma, x:\tau\_0 \vdash M : \tau\_1}{\Gamma \vdash \lambda x.M : \tau\_0 \rightarrow \tau\_1}(\mathord{\rightarrow}I) \qquad \dfrac{\Gamma \vdash M : \tau\_0 \rightarrow \tau\_1 \quad \Gamma \vdash N : \tau\_0}{\Gamma \vdash M\\,N : \tau\_1}(\mathord{\rightarrow}E) $$

For example, if $A$ and $B$ are based types, then $\lambda x. \lambda y. x\\,y$ has the type $(A \rightarrow B) \rightarrow A \rightarrow B$ in any context (from bottom to top, apply $(\mathord{\rightarrow}I)$ twice, then $(\mathord{\rightarrow}E)$, and finally $(\Gamma)$ on each branch).

It is possible to interpret the types of the simply typed lambda calculus as sets. This amounts to giving a denotational semantics for the types. A good denotational semantics for the base terms would assign to each base term a member of the denotation of all of its types.

Intuitionistic type theory (also known as Martin-Löf type theory) is more complex that simply typed lambda calculus, as it has many more elements in the calculus of types (and also adds a few constants to the base terms). But the core principles are the same. An important feature of Martin-Löf type theory is that types can contain base terms (they are dependent types): the universe of base terms and the universe of types are the same, though they can be distinguished by simple syntactic rules (usually known as sorting, i.e. assigning sorts to terms, in rewriting theory).

There are type systems that go further and completely mix types and base terms, so that there is no distinction between the two. Such type systems are said to be **higher-order**. In such calculi, types have types — a type can appear on the left-hand side of the $:$. The calculus of construction is the paradigm of higher-order dependent types. The lambda cube (also known as Barendregt cube) classifies type systems in terms of whether they allow terms to depend on types (polymorphism — some base terms contain types as subterms), types to depend on terms (dependent types), or types to depend on types (type operators — the calculus of types has a notion of computation).

Most type systems have been given set-theoretical semantics, to tie them with the usual foundations of mathematics. How are programming languages and foundations of mathematics related? and What is the difference between the semantic and syntactic views of function types? may be of interest here. There has also been work on using type theory as a foundation of mathematics — set theory is the historic foundation, but it is not the only possible choice. Homotopy type theory is an important milestone in this direction: it describes the semantics of intentional intuitionistic type theory in terms of homotopy theory and constructs set theory in this framework.

I recommend Benjamin Pierce's books *Types and Programming Languages* and *Advances Topics in Types and Programming Languages*. They are accessible to any undergraduate with no prerequisite other than basic familiarity with formal mathematical reasoning. TAPL describes many type systems; dependent types are the subject of chapter 2 of ATTAPL.

# Answer
> 19 votes
Maybe a better question for somebody coming from set theory and grappling with how set theory and Martin-Löf type theory differ, is to reflect on what sets are. Your intuitions about set theory and the foundations of mathematics will be infected with unquestioned set-theoretic assumptions that you take for granted. Alas Martin-Löf type theory does not share these assumptions.

Contrary to conventional understanding, set theory is a theory of **two** relations: **equality** and **set membership**, not just set membership. And these two relations are built in substantially distinct phases.

1. We build up first-order logic as a theory of equality of arbitrary things (not just sets). First-order logic uses an **informal** notion of proof. The concept proof is not itself expressible formally in first-order logic alone.
2. Then we build up set-theory on top of first-order logic as a theory of sets and set membership.
3. Set membership and equality are then related by the axiom of extensionality which says that two sets are equal exactly when they have the same members.
4. Finally, the informal concept of proof from (1) gets an ex-post rationalisation as certain sets (proof trees).

It is important thing to realise is that the notion of **proof** is thus a **second-class citizen** in set theory.

This set-up works fine for conventional small/medium sized mathematics, but as we are now tackling large-scale proofs, such as the classification of all finite simple groups, or the verification of non-trivial computer programs, it falls apart, because it does not lead itself to easy mechanisation.

Martin-Löf type theory is different: it builds up the notion of proof and that of type (which, roughly, is to Martin-Löf type theory what sets are to set theory) in one-fell swoop. This means **proofs** are **first-class citizens** of the theory. While a set is given by it's members, set theory omits to specify formally what counts as a proof that something is a set member. In contrast a type is given by its proofs of inhabitation. So you understand a type $T$ exactly when you understand what counts as a proof of $T$.

What are these proofs that inhabit types? Simplifying a bit (and omitting identity types), they are functional programs, more precisely terms in the $\lambda$-calculus that are typable. This is known as the Curry-Howard correspondence. It gives a beautiful new and less ad-hoc foundation of constructive mathematics. It doesn't work quite so well for classical mathematics tough.

# Answer
> 11 votes
I'm not aware of easy pathways into Martin-Löf type theory. I guess the following could serve as introductions.

However, if you are puzzled by the question "what is a type", I suggest to get into much simpler type-theories first. Any typed programming language will do, but e.g. Ocaml, F# and Haskell would be especially useful. Simplifying a bit, one could say that Martin-Löf type theory extends the types behind the aforementioned languages in two ways:

1. With dependent types. You find them in tamer form in various programming languages.
2. With identity types. This is the main innovation of Martin-Löf's over previous dependent type theories.

The key idea behind dependent types is simple: types can be parameterised by programs. This is not possible (simplifying a bit) in more conventional typing systems such as those mentioned above. While simple, the consequences are profound: dependent types lift the Curry-Howard correspondence to first-order constructive logic. Identity types are a bit unusual. If/when you are comfortable with a language like Haskell, you could learn Agda, which is basically Haskell with Martin-Löf type theory. I feel that Agda is much easier to learn for a programmer than reading the books mentioned above.

---
Tags: logic, type-theory
---


# Question
Title: Clear, complete, proof that a language is Turing Compete?
I have seen web sites that purport to "prove" that HTML5+CSS is Turing Complete.

I have seen web sites that purport to "prove" that SQL is Turing Complete.

I have seen a bunch of web sites that purport to "explain" what it means to be Turing Complete.

Enough!

Where can I find a book (written by an expert in computability theory) or a peer-reviewed article (in a reputable journal) that shows a proof of, "This language XYZ is capable of describing a computational machine which has the same computational power as a Turing Machine"?

# Answer
> 12 votes
Every language that can implement two counters $C\_1, C\_2$ (i.e. two registers that can store two arbitrarily large integers) and a program made with a labeled sequence of these two elementary instructions is Turing complete:

* ADD $1$ to counter $C\_i$, GOTO instruction $I\_j$
* SUBTRACT $1$ from counter $C\_i$ if $C\_i \> 0$ and GOTO instruction $I\_j$; otherwise (if $C\_i = 0$) GOTO instruction $I\_k$

The result is proved in:

Marvin L. Minsky, "Recursive Unsolvability of Post's Problem of Tag and other Topics in the Theory of Turing Machines" (1961)

Don't forget that a computational model (in your case a *programming language + a device that executes programs written in that language*) can be considered Turing complete only if it supports access to an unbounded amount of memory (i.e. space) or can store (in some form) arbitrarily large integers. A programming language implementation on a real computer is equivalent to a Linear Bounded Automaton.

You can also find a lot of references on the Wikipedia pages on RAM model and RASP model.

Finally a nice book focused on the equivalence of different models of computation is:

"Models of Computation: An Introduction to Computability Theory", by Maribel Fernandez

# Answer
> 3 votes
The two most widely used text books on computability and complexity theory are:

> Michael Sipser: *Introduction to the Theory of Computation*, 2/e, Cengage, 2005.
>
> John E Hopcroft; Jeffrey D Ullman: *Introduction to Automata Theory, Languages and, Computation*, Addison-Wesley, 1979.

There is also a beautiful philosophy monograph for lay-people that works through the technical details of computability theory without the formal proofs.

> Douglas Hoftstadter: *Gödel, Escher, Bach*, Basic Books, 1979.

Finally, the best introduction to computability may be a puzzle book by a famous logician:

> Raymond Smullyan: *The Lady or the Tiger and Other Logic Puzzles*, Penguin, 1983. (Now in an inexpensive Dover edition, 2009.)

(He starts with a bunch of puzzles based on the Liar's paradox, and then works you through the construction of a self-referential statement in the guise of a Sherlock Holmes-style puzzle about a mysterious locked box.)

---
Tags: computability, turing-machines, automata, turing-completeness, church-turing-thesis
---


# Question
Title: How to encode date as input in neural network?
I am using neural networks to predict a time series. The question I'm facing now is how do I encode date/time/serial no. of each input set as an input to the neural network?

Should I use 1 of C encoding (used for encoding categories) as described here?

Or Should I just feed it the time (in milliseconds since 1-1-1970)?

Or is feeding it the time unnecessary as long as I feed it the rest of the data chronologically?

# Answer
Neural Networks are not magic. If you treat them like they are and just throw data at them without thinking you're going to have a very bad time.

You need to stop and ask youself "Is milliseconds since 1970 actually going to be predictive of the event I'm interested in?" The answer you should arrive at immediately is no. Why? For every instance you actually care about (events in the future, the past already happened) the time variable will take on a value that is greater than any value the time variable will take in your training data. Such a variable is very unlikely to help. Even worse it is likely to cause overfitting (a serious problem for powerful non-linear models like neural networks) if you aren't careful.

Now what might make sense is a variable like week of the year or month that could help you model seasonal or annual effects. I've done some work in agricultural disease prediction where Julian day ended up being a very important variable. Based on this experience, I suspect you'd be better off encoding this type of variable as a categorical variable rather than ordinal, your experience may very. Notice that month or week of the year are repeatable events that one is likely to see many times in your training data and it is possible to explain why such a variable could impact a financial outcome. Contrast this with milliseconds since 1970 which is just a monotonically increasing value.

Lastly, from your statement "Or is feeding it the time unnecessary as long as I feed it the rest of the data chronologically?" it sounds like you might not have a very good grasp of how neural networks work. With a standard feedforward neural network the order you feed the network your data is going to have no impact on the predictions. Order may impact training if you're using stochastic or mini-batch gradient descent, but this is only an artifact of the iterative (as opposed to batch) training method. If you want to model temporal dependence with a neural network you'll need to use something like a sliding window or a recurrent neural network.
> 19 votes

# Answer
you state in comments you're working on financial time series prediction. whether to include time or not in inputs is somewhat domain-dependent. in general its relevant if you have some kind of "cyclic" time component in your data. for example, maybe there is some weekly effect in your data if it is running over weeks, or some intraday effect if it spans a single day. then if you have many cycles, include an input that reflects the position in the cycle, eg from $\[-1,1\]$ or $\[0,1\]$ or say $sin(t)$.

if you find that theres a consistent trend eg either increasing or decreasing over time say $f(t)$ its more appropriate to extract that from the inputs prior to feeding the inputs via what is called "detrending". in other words you subtract the formula $f(t)$ for that underlying trend and predict the trend plus difference $d\_t = f\_t + g\_t$ but the NN focuses only on the difference $g\_t$, not the trend $f\_t$.
> 2 votes

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


# Question
Title: Proving a Language is Irregular using Myhill-Nerode
I'm trying to prove that the language: \begin{equation\*} L = \\{ w \in \\{ 0, 1 \\}^\* : w \text{ contains more 0's than 1's} \\} \end{equation\*} is irregular using the Myhill-Nerode theorem. I've been through all the basic examples in the book, and thought I understood them, but I'm having trouble with this one.

So far, I've been thinking about letting $ x\_i = 1^i 0^i $ and $x\_j = 1^{j+1} 0^{j-1}$, then if I let $ w\_{ij} = 0$, only $x\_iw\_{ij} \in L$. That seems to be sufficient, but it seems weak compared to some of the other examples.

Am I on the right track here? I would really appreciate any hints/suggestions.

# Answer
You can observe that $L$ is accepted by this infinite DFA $\mathcal{A}$$\mathcal{A}$" /\>
<sub>(source: jep at www.irif.fr/)</sub>

This might help you to separate the words $0^i$, as suggested by Yuval Filmus.

By the way, this will also prove that $\mathcal{A}$ is the minimal DFA of $L$.

**Update**. Just in case, a brief description: set of states $\mathbf{N}$, initial state $0$, final states $\mathbf{N} \setminus \\{0\\}$, transitions $n \xrightarrow{0} n + 1$ and $n+1 \xrightarrow{1} n$ for all $n \in \mathbf{N}$.
> 1 votes

# Answer
You need to come up with an infinite number of pairwise inequivalent strings. Try $x\_i = 0^i$ for *all* $i \geq 0$.
> 2 votes

# Answer
You need to show that there are infinitely many equivalence classes. For that you should find an infinite number of strings, such that no pair of them is equivalent. Right now you have an infinite number of inequivalent pairs, which is a much weaker statement.

Complete a chain of strings. Say, first you had $1^i0^i$ and $1^{j+1}0^{j-1}$. See what could go next to keep all strings inequivalent. See what pattern emerges. There is plenty of solutions.
> 2 votes

---
Tags: formal-languages
---


# Question
Title: a jigsaw problem: recreating a subgraph from a limited number of fragments on an original graph
Suppose I have a set of small subgraphs $A=\\{G\_i\\}$ of an original directed acyclic graph $G$, typically $|G\_i| \ll |G|$, which together span the original graph

$$ G= \bigcup\_i G\_i $$ My question is if I take a arbitrary subset of these graphs $A′ \subset A$, and a single subgraph from this graph, $ a \in A′$, is there a simple way (or known algorithm) of reassembling the subgraph $G′ \subset G$ given by that portion of the union of $A′$ connected to $a$?

In words, this is rather like a jigsaw problem where $A$ is the total collection of pieces that originally came in the box, $A′$ is the subset left after half of them got lost and $a \in A′$ the random selected piece you put down the start the puzzle off. The question is then what is the largest connected graph (connected subset of pieces $x \in A'$) that you can lay down all on the board.

The actual application arises where each subgraph $G\_i$ of A represents a rule and (e.g. $x \wedge y \Rightarrow z$) and the objective is to find the largest rule implied transitively from an initial seed rule $a \in A′$ and the remaining rules contained in thinned out subset $A′ \subset A$.

I suspect I maybe able to do something by brute force here but would be most interested in knowing if there is any area or known application of this problem elsewhere. I think similar things are possible in declarative language such as Prolog but I suspect that Prolog can actually do any more. Any good up-to-date reference on declarative programming languages would also be very useful.

I originally posted a version of this question on the Computational Science site but was advised that this forum could be better.

# Answer
One unclear point about the question is the meaning of "connected". If we interpret it as weakly connected, then the orientation of the DAG is no longer important, and we could have worked with an undirected graphs in the first place. We should also not interpret it as strongly connected, since a DAG has no strongly connected subsets.

So we are probably interested in the subgraph reachable from a node in $a$. I looks like we can just work with the set of edges contained the graphs from $A'$. But then we end up with a problem which belongs to both 2-SAT and HORNSAT, and the unit-propagation algorithm for HORNSAT will solve it in linear time. As the problems also belongs to 2-SAT, we know that it is not P-complete.
> 1 votes

---
Tags: graphs
---


# Question
Title: Algorithm for splitting array into subarrays with sums close to the target value
I have an array of positive integers, $A = (a\_1, a\_2, ..., a\_n)$. Let $s(A)$ denote the sum of elements of array $A$. I also have an integer $t$, such that $1 \< t \le s(A)$.

I want to split the array $A$ into $m$ contiguous subarrays $(A\_1, ..., A\_m)$, for which I'll get a minimum of function $f$, defined as

$$ f(A\_1, ..., A\_m) = \sum\_{1 \le i \le m}{(s(A\_i) - t)^2}. $$

Please note that I'm talking specifically about arrays, so the order of elements does matter.

Here is a simple example.

Let $t = 13$ and $$ A = (1, 6, 7, 10, 3, 2, 10). $$ With the following subarrays $$ A\_1 = (1, 6, 7)\\ A\_2 = (10, 3) \\ A\_3 = (2, 10) \\ $$ the value of $f(A\_1, A\_2, A\_3) = (14-13)^2 + (13 - 13)^2 + (12 - 13)^2 = 2$.

I don't need an exact solution. Good heuristic would be sufficient.

# Answer
You can solve it exactly using dynamic programming, though that might be too slow or might require too much memory. Calculate an array $B(\ell,k)$, which is the minimal error obtained by dividing $a\_1,\ldots,a\_k$ into $\ell$ parts. This can be implemented in time and space $O(mn)$ by calculating (in advance) the running sums $\sum\_{i \leq t} a\_i$.
> 5 votes

---
Tags: algorithms, dynamic-programming
---


title: Iterative merge sort

text:
# Question
Title: Iterative merge sort
I was asked to perform merge sort by iterative method. I solved it as follows: I first stored each of the elements of the array given in another array say $A$. Then I sent entries of $A$ two by two for merging(was given that the function for merging is known and it merged two arrays at a time). This function returned the merged array which I stored in another array $B$. After I was done with all the elements of $A$ I deleted $A$ and copied each of the entries of $B$ in $A$.I allocated memories for $A$ and $B$ dynamically. I repeated this for $log(n)$ times and each time I halved the size of $A$ and $B$. Is my algorithm correct??

# Answer
> 1 votes
1. I suggest you try to run your algorithm on a few small arrays and see if it works.
2. Merge sort can be implemented in-place, and the same is true in your case.
3. Consider the recursive version of merge sort. Apart from calling itself recursively, the only other operation is *merge*. See if you can make a sequential list of all calls made to *merge* (with their parameters).

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


# Question
Title: How to prove substring is a partial order
u is defined to be a substring of a string v if v = xuy for some string x and y. Either or both possibly empty.

How to you prove that a substring relation on any set of strings is a partial order?

# Answer
Hint: show that if $u$ is a substring of $v$ and $v$ is a substring of $w$ then $u$ is a substring of $w$.
> 2 votes

---
Tags: partial-order
---


title: trouble with bijection definition

text:
# Question
Title: trouble with bijection definition
I have a bijection problem that I cannot get my head around. It goes like this:

let f: A -\> B and g: B -\> C be functions such that g o f is a bijection. Prove that f must be one-to-one and that g must be onto. And also an example showing that it is possible for neither f nor g to be a bijection.

This is the problem. I do not even know where to begin. Any help is appreciated.

# Answer
Hints: First part: Suppose that $f$ is not one-to-one. That implies that $f(x) = f(y)$ for some $x \neq y$. Can $g \circ f$ be a bijection? Similar idea for the other half. Second part: We know that $f$ must be one-to-one and $g$ must be onto. So if $f$ and $g$ are not bijections, then $f$ must *not* be onto and $g$ must *not* be one-to-one. See how these two conditions mesh together.
> 2 votes

---
Tags: proof-techniques, discrete-mathematics, correctness-proof, partial-order
---


# Question
Title: Maintaining an efficient ordering where you can insert elements "in between" any two other elements in the ordering?
Imagine I have an ordering on a bunch of elements like so:

Where an arrow $X \leftarrow Y$ means $X \< Y$. It is also transitive: $\left(X \< Y\right) \wedge \left(Y \< Z\right) \implies \left(X \< Z\right)$.

In order efficiently answer queries like $A \stackrel {?}{\<} D$, some sort of labeling or data structure is required. For example, you could number the nodes from left to right, and thus you can simply do integer comparison to answer the query: $A \stackrel {?}{\<} D \implies 1 \< 4 \implies T$. It would look something like this:

Where the number is the ordering, and the letter is just a name.

But what if you needed to insert elements "in between" two other elements in the ordering, like so:

How can you maintain such an ordering? With simple numbering, you run into the problem that there are no integers "in between" $2,3$ to use.

# Answer
This is known as the "order maintenance" problem. There is a relatively simple solution using $O(1)$ amortized time for both queries and inserts. Now, by "relatively simple", I mean that you have to understand some building blocks, but that once you get those, the rest isn't hard to see.

http://courses.csail.mit.edu/6.851/spring12/lectures/L08.html

The basic idea is a two-level data structure. The top level is like the AVL tree solution by Realz Slaw, but

* The nodes are directly labeled with bit strings of length $O(\lg n)$ with an order that matches their order in the tree. Comparison thus takes constant time
* A tree with fewer rotations than an AVL tree is used, like a scapegoat tree or a weight-balanced tree, so relabellings happen less frequently.

The bottom level is the leaves of the tree. That level uses the same length of labels, $O(\lg n)$, but holds only $O(\lg n)$ items in each leaf in a simple linked list. This gives you enough extra bits to relabel aggressively.

Leaves get too big or too small every $O(\lg n)$ inserts, inducing a change in the top level, which takes $O(\lg n)$ amortized time ($\Omega(n)$ worst-case time). Amortized, this is only $O(1)$.

Much more complex structures exist for performing updates in $O(1)$ worst-case time.
> 9 votes

# Answer
Instead of simple numbering, you could spread the numbers out over a large (constant sized) range, such as integer minimum and maximums of a CPU integer. Then you can keep putting numbers "in between" by averaging the two surrounding numbers. If the numbers become too crowded (for example you end up with two adjacent integers and there is no number in between), you can do a one-time renumbering of the entire ordering, redistributing the numbers evenly across the range.

Of course, you can run into the limitation that all the numbers within the range of the large constant are used. Firstly, this is not a usually an issue, since the integer-size on a machine is large enough so that if you had more elements it likely wouldn't fit into memory anyway. But if it is an issue, you can simply renumber them with a larger integer-range.

If the input order is not pathological, this method might amortize the renumberings.

### Answering queries

A simple integer comparison can answer the query $\left(X \stackrel{?}{\<}Y\right)$.

Query time would be very quick ( $\mathcal{O}\left(1\right)$ ) if using machine integers, as it is a simple integer comparison. Using a larger range would require larger integers, and comparison would take $\mathcal{O}\left(\log{|integer|}\right)$.

### Insertion

Firstly, you would maintain the linked list of the ordering, demonstrated in the question. Insertion here, given the nodes to place the new element in between, would be $\mathcal{O}\left(1\right)$.

Labeling the new element would usually be quick $\mathcal{O}\left(1\right)$ because you would calculate the new numeber easily by averaging the surrounding numbers. Occasionally you might run out of numbers "in between", which would trigger the $\mathcal{O}\left(n\right)$ time renumbering procedure.

### Avoiding renumbering

You can use floats instead of integers, so when you get two "adjacent" integers, they *can* be averaged. Thus you can avoid renumbering when faced with two integer floats: just split them in half. However, eventually the floating point type will run out of accuracy, and two "adacent" floats will not be able to be averaged (the average of the surrounding numbers will probably be equal to one of the surrounding numbers).

You can similarly use a "decimal place" integer, where you maintain two integers for an element; one for the number and one for the decimal. This way, you can avoid renumbering. However, the decimal integer will eventually overflow.

Using a list of integers or bits for each label can entirely avoid the renumbering; this is basically equivalent to using decimal numbers with unlimited length. Comparison would be done lexicographically, and the comparison times will increase to the length of the lists involved. However, this can unbalance the labeling; some labels might require only one integer (no decimal), others might have a list of long length (long decimals). This is a problem, and renumbering can help here too, by redistributing the numbering (here lists of numbers) evenly over a chosen range (range here possibly meaning length of lists) so that after such a renumbering, the lists are all the same length.

---

This method actually is actually used in this algorithm (implementation,relevant data structure); in the course of the algorithm, an arbitrary ordering must be kept and the author uses integers and renumbering to accomplish this.

---

Trying to stick to numbers makes your key space somewhat limited. One could use variable length strings instead, using comparison logic "a" \< "ab" \< "b". Still two problems remain to be solved A. Keys could become arbitrarily long B. Long keys comparison could become costly
> 7 votes

# Answer
You can maintain a key-less AVL tree or similar.

It would work as follows: The tree maintains an ordering on the nodes just as an AVL tree normally does, but instead of the key determining where the node "should" lie, there are no keys, and you must explicitly insert the nodes "after" another node (or in other words "in between" two nodes), where "after" means it comes after it in in-order traversal of the tree. The tree will thus maintain the ordering for you naturally, and it would also balance out, due to the AVL's built in rotations. This will keep everything evenly distributed automatically.

## Insertion

In addition to regular insertion into the list, as demonstrated in the question, you would maintain a separate AVL tree. Insertion to the list itself is $\mathcal{O}\left(1\right)$, as you have the "before" and "after" nodes.

Insertion time into the tree is $\mathcal{O}\left(\log {n}\right)$, the same as insertion to an AVL tree. Insertion involves having a reference to the node you want to insert after, and you simply insert the new node into the left of the leftmost node of the right child; this location is "next" in the ordering of the tree (it is next in the in-order traversal). Then do the typical AVL rotations to rebalance the tree. You can do a similar operation for "insert before"; this is helpful when you need to insert something into the beginning of the list, and there is no node "before" node.

## Answering queries

To answer queries of $\left(X \stackrel{?}{\<}Y\right)$, you simply find all the ancestors of $X$ and $Y$ in the tree, and you analyze the location of where in the tree the ancestors diverge; the one that diverges to the "left" is the lesser of the two.

This procedure takes $\mathcal{O}\left(\log{n}\right)$ time climbing the tree to the root and obtaining the ancestor lists. While it is true that this seems slower than integer comparison, the truth is, it is the same; only that integer comparison on a CPU is bounded by a large constant to make it $\mathcal{O}\left(1\right)$; if you overflow this constant, you have to maintain multiple integers ( $\mathcal{O}\left(\log{n}\right)$ integers actually ) and do the same $\mathcal{O}\left(\log{n}\right)$ comparisons. Alternatively, you can "bound" the tree height by a constant amount, and "cheat" the same way the machine does with integers: now queries will seem $\mathcal{O}\left(1\right)$.

## Insertion operation demonstration

To demonstrate, you can insert some elements with their ordering from the list in the question:

### Step 1

Start with $D$

List:

Tree:

### Step 2

Insert $C$, $\emptyset \< C \< D$.

List:

Tree:

Note, you explicitly put $C$ "before" $D$, not because the letter C is before D, but because $C \< D$ in the list.

### Step 3

Insert $A$, $\emptyset \< A \< C$.

List:

Tree:

AVL Rotation:

### Step 4

Insert $B$, $A \< B \< C$.

List:

Tree:

No rotations necessary.

### Step 5

Insert $E$, $D \< E \< \emptyset$

List:

Tree:

### Step 6

Insert $F$, $B \< F \< C$

We just put it right "after" $B$ in the tree, in this case by simply attaching it to $B$'s right; thus $F$ is now right after $B$ in the in-order traversal of the tree.

List:

Tree:

AVL rotation:

## Comparison operation demonstration

### $A \stackrel{?}{\<} F$

```
ancestors(A) = [C,B]
ancestors(F) = [C,B]
last_common_ancestor = B
B.left = A
B.right = F
... A < F #left is less than right

```

### $D \stackrel{?}{\<} F$

```
ancestors(D) = [C]
ancestors(F) = [C,B]
last_common_ancestor = C
C.left = D
C.right = B #next ancestor for F is to the right
... D < F #left is less than right

```

### $B \stackrel{?}{\<} A$

```
ancestors(B) = [C]
ancestors(A) = [B,C]
last_common_ancestor = B
B.left = A
... A < B #left is always less than parent

```

---

## Graph sources
> 3 votes

---
Tags: data-structures, graphs, linked-lists, partial-order, order-theory
---


title: Abduction in ASP

text:
# Question
Title: Abduction in ASP
Well, forgive my ignorance about the matter as I have been playing with ASP for the last couple of days.

Consider this simple example

```
p.
s :- p.

```

And the corresponding output generated after running the program in clingo:

```
$ ./clingo.exe  ex.lp --number=0
Answer: 1
p s
SATISFIABLE

Models      : 1
...

```

Where possible models are generated having `p true` and the formula `p -> s`.

But if I want to ask some query that requires abductive reasoning in order to generate some answers; in other words, I need to know the possible solutions to the fact `s true`. So the "supposed" example should be like the following:

```
s.
s :- p.

```

But unfortunately the answer does not contain `p` as expected.

```
$ ./clingo.exe  ex.lp --number=0
% warning: p/0 is never defined
Answer: 1
s
SATISFIABLE

Models      : 1
...

```

Could that be done in any way in ASP?

# Answer
I found out that this could not be done natively in ASP (or at least in the solvers that I am using). So the abduction theory needs to be modeled with the problem in order to derive expected results.

This is an example that demonstrates how it can be done. I haven't had the time to thoroughly test its efficiency but it works for some basic examples.

Source: http://www.dbai.tuwien.ac.at/proj/arvis/#usage

```
% abduction.lp

%%%%%%%%%%%%% Preprocessing %%%%%%%%%%

% Remove tautological clauses
taut(C) :- pos(C,X), neg(C,X).
preprocessed_clause(C) :- clause(C), not taut(C).

% which variable is in which clause
var_in_clause(C,X) :- preprocessed_clause(C), pos(C,X).
var_in_clause(C,X) :- preprocessed_clause(C), neg(C,X).

%%%%%%%%%%%%% Guess a Candidate Solution %%%%%%%%%%

% S, a subset of hypotheses  is a solution iff (1) and (2) hold
solution(S) :- hypothesis(S), not nosolution(S).
nosolution(S) :- hypothesis(S), not solution(S).

%%%%%%%%%%%%% (1) background theory is consistent with S %%%%%%%%%%

% guess an assignment for all variables
true_consistency(X) :- variable(X), not false_consistency(X).
false_consistency(X) :- variable(X), not true_consistency(X).

%% Solution must be true
true_consistency(S) :- solution(S).

%% Check for each clause in T whether it is satisfied
sat(C) :- preprocessed_clause(C), pos(C,V), true_consistency(V).
sat(C) :- preprocessed_clause(C), neg(C,V), false_consistency(V).

%% In case a clause is not satisfied, remove AS
notsat :- preprocessed_clause(C), not sat(C).
:- notsat.

%%%%%%%%%%%%%% (2) background theory and solution entail the manifestation%%%%%%%%%%

%% Find assignment, which is a counter-example to entailment
true_entail(X) | false_entail(X) :- variable(X).

% ordering over variables in preprocessed clauses
lowerThan(C,X,Y) :- var_in_clause(C,X), var_in_clause(C,Y), X<Y.
not_successor(C,X,Z) :- lowerThan(C,X,Y), lowerThan(C,Y,Z).
successor(C,X,Y) :- lowerThan(C,X,Y), not not_successor(C,X,Y).
not_infimum(C,X) :- lowerThan(C,Y,X).
not_supremum(C,X) :- lowerThan(C,X,Y).
infimum(C,X) :- not not_infimum(C,X), var_in_clause(C,X).
supremum(C,X) :- not not_supremum(C,X), var_in_clause(C,X).

% check if unsat
unsatupto(C,V) :- infimum(C,V), pos(C,V), false_entail(V).
unsatupto(C,V) :- infimum(C,V), neg(C,V), true_entail(V).
unsatupto(C,V) :- unsatupto(C,PreV), successor(C,PreV,V), pos(C,V), false_entail(V).
unsatupto(C,V) :- unsatupto(C,PreV), successor(C,PreV,V), neg(C,V), true_entail(V).

unsat(C) :- unsatupto(C,V), supremum(C,V).
unsat :- unsat(C).

% make sure that variables in manifestations and solution get the right truth value
false_entail(X) :- manifestation(X).
true_entail(X) :- solution(X).

% saturation
true_entail(X) :- variable(X), unsat.
false_entail(X) :- variable(X), unsat.

:- not unsat.

#show solution/1.
%#show manifestation/1.
%#show hypothesis/1.
%#show variable/1.

```

And the example provided in this post's question:

```
% a_ex2.lp

% Variables V
variable("s";"p").

% Theory T over V
clause(1).
pos(1,"s").
neg(1,"p").

hypothesis("p").

manifestation("s").

```

Output:

```
$ ./gringo.exe abduction.lp a_ex2.lp | ./claspD.exe --number 0
claspD version 1.1. Reading...done
Answer: 1
solution("p")

Models      : 1
Time        : 0.002  (Parsing: 0.001)

```
> 1 votes

---
Tags: logic, logic-programming, answer-set-programming
---


# Question
Title: Finding both the longest and shortest path in a convex polygon
Let $S$ be a convex polygon on $n$ points. Given two points $A$ and $B$, where $A$ is left of $S$, and $B$ is right of $S$, what's an algorithm to find the shortest path from $A$ to $B$, that avoids the interior of $S$? What about the longest path?

# Answer
The shortest path will be made out of straight lines connecting A, B and the vertices of S.

The most simple solution is to check a bunch of paths, starting with path AB; then AXB and AYB where X and Y are the topmost and bottommost points of S; then extending to the left or right neighbors of X and Y, if some intersections happen.

A smarter solution would be to find the points P, minimizing and maximizing the angle between $\vec {AP}$ and $\vec {AB}$. Those will be the points where your path enters and leaves S.

The longest path is, obviously, infinite.
> 1 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, computational-geometry
---


title: On approximations and reductions

text:
# Question
Title: On approximations and reductions
This may be a naive question but I am a bit clueless. I was under the opinion that given two NP complete problems, $P1$ and $P2$, if $P2 \in APX$ and $P1 \notin APX$, then we cannot have a direct reduction $P2\leq P1$ but we can have a reduction $P1\leq P2$.

In this paper on page 165 http://www.lancaster.ac.uk/staff/letchfoa/articles/cut-projection.pdf, there is a reduction $MAXCUT \leq STABLESET$. That is, given an instance of *STABLESET*, I can find an instance of *MAXCUT*. Why cant I use the approximate solution for *MAXCUT* to find an approximate solution to *STABLESET*?

# Answer
> 6 votes
In short, a reduction need not preserve approximations. For more details, see my answer on cstheory to a similar question.

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


title: NFA and DFA storage cost

text:
# Question
Title: NFA and DFA storage cost
In some paper I read,

> A theoretical worst case study shows that a single regular expression of length $n$ can be expressed as an NFA with $O(n)$ states. When the NFA is converted into a DFA, it may generate O($\Sigma^n$) states. The processing complexity for each character in the inpuyt it $O(1)$ in a DFA, but is $O(n^2)$ for an NFA when all $n$ states are active at the same time.

Please explain how NFA has at its maximum just $n$ states and its equivalent DFA has at most $O(\Sigma^n)$ states?

# Answer
> 5 votes
Consider the construction of an NFA from a regular expression $r$. The construction is by induction over the generating sequence of $r$. If you examine the different operations (union, Kleene star, and concatenation), you will see that each operation increases the size of the NFA by a linear blowup.

For example, an NFA for $r\_1\cup r\_2$ is obtained by nondeterministically starting in an NFA for $r\_1$ or an NFA for $r\_2$, so the size of the NFA is (by induction) at most $|r\_1|+|r\_2|$.

Now, determinizing an NFA with $k$ states may involve a blowup of up to $2^k$ states. However, the NFA you obtained from the construction has $k=O(n)$ states, so the blowup is $2^{O(n)}$. The paper you read shows that the $O(n)$ factor is in fact $n\cdot O(\log|\Sigma|)$, thus making the total size $O(|\Sigma|^n)$.

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


# Question
Title: What areas in EE overlap closely with CS
I am doing bachelors in Electronics & Communication Engg.. But most of my work happened to be in Web development.. I am thinking to do my bachelor thesis which very closely overlaps with my recent work.

Are there any specific areas in CS, EE (may be Computer Networking in broad terms) that I can take up?

# Answer
One very close overlap is of course Computer Architecture.

Another close overlap (which incidentally happens to be my speciality) is EDA (CAD for VLSI designers). EDA requires development of fairly sophisticated parallel algorithms for things such as routing, RC extraction, optical proximity correction, etc., as well as understanding of the underlying VLSI physics.

Other subjects include telecommunication and signal processing, as pointed out in Subhayan's comment.
> 4 votes

---
Tags: computer-networks, research
---


# Question
Title: Printing The Longest Path from Root to Leaf in Binary Tree
I am stumped as to how to print the longest path from the root of a binary tree to a leaf, essentially traversing the height of the tree. I've got the following for finding the height of a binary tree:

```
if (root == null) {
    return -1;
}

return 1 + (Math.max(heightOfTree(root.leftNode), heightOfTree(root.rightNode)));

```

This easily finds the height of the tree but doesn't lend itself to actually figuring out which nodes should be printed out. I could go about finding the nodes's value that is at the leaf, and then do a find for that particular node, but that seems inefficient.

```
        A
      B   C
    D  E F  G
             H

```

For example, the height of this binary tree is 3, and I would ideally like to know the path to take, in this case it would be A, C, G, H. I know that I most likely need to keep an array for the path, but I just can't seem to find a solution that isn't terribly inefficient.

# Answer
> 1 votes
Though I don't believe this is the most efficient solution to the problem, it definitely works and I figured I would share it here and see if anyone had any feedback.

```
private static void printMain(BTNode node, String[] path, int arrayCounter) {
    if (node == null) {
        return;
    }

    path[arrayCounter++] = node.data;

    if (node.leftNode == null && node.rightNode == null) {
        printArray(path);
    }
    else {
        printMain(node.leftNode, path, arrayCounter);
        printMain(node.rightNode, path, arrayCounter);
    }
}

```

This print function adds each node's value to an array until it reaches a node that has a left and right child that is null. This means it has reached the end and the array now has a path from the root node to *a* leaf node. It's not necessarily the longest path though. Here in the printArray function, it checks to see if the last element of the array is null.

Since the array is initialized to only be as large as the height found in the algorithm in my original question, if the last element is null this is not the longest path. If it is we print.

```
private static void printArray(String[] path) {
    if (path[max] != null) {
        for (String node : path) {
            System.out.print(node + ", ");
        }
        System.out.print("\n");
    }
}

```

The added benefit of this approach is that it will print each and every path that is the longest. Meaning if there were 3 nodes that are of height 3, each of the 3 would be printed as opposed to just the one. I still think it could be done more efficiently but this is certainly one solution.

# Answer
> 0 votes
Hint: Suppose we know that there is a longest path going through child X. If we ask X for a longest path from X to a leaf, would it help us to find a longest path from us to a leaf?

(This solution uses $O(1)$ memory, apart from the stack, if you don't care about printing the path backwards.)

# Answer
> 0 votes
A very simple solution is to augment the data structure so each node has a pointer to its parent. When you find the deepest leaf, then just follow parent pointers to the root to retrieve the path you want.

---
Tags: binary-trees, recursion
---


title: Type inference of pair (product) types

text:
# Question
Title: Type inference of pair (product) types
I am looking into Hindler-Milney type system and I am trying to add support for the pair type. In Pierces book, he introduces special language constructs for creation of pairs and getting their elements.

What I am interested in is the following. What if I don't introduce new constructs, yet use special functions with this signatures:

$$pair: \alpha \rightarrow \beta \rightarrow \alpha \times \beta $$

$$proj1: \alpha \times \beta \rightarrow \alpha$$

$$proj2: \alpha \times \beta \rightarrow \beta $$

If I use Wand's algorithm for type inference, after collecting all equations between type expressions and solving it a bit, I get the following equation for $((pair\\; 2\\;) 4): \tau$:

$$\alpha \rightarrow \beta \rightarrow \alpha \times \beta = Int \rightarrow Int \rightarrow \tau$$

It seems to me that the unification algorithm should infer at the end that $\tau = Int \times Int$. Is this true?

Do I really need a special construct for pairs? Is there something conceptually wrong with this? Probably their is, so it would be great if someone could point me out.

Note that I would also prefer using special constructs as that way looks cleaner and easier to program with; this question is just for my complete understanding of the subject.

# Answer
You can use things like **pair**, **proj** ... as constants only. That works very well conceptually. Nevertheless, there are reasons why programming languages tend to use special syntactic forms for the like of products:

* Readability, e.g. **( M, N )** reads more natural than **pair M N** to some.
* For efficient reductions. It is possible to code the reductions for pairs up in pure$\lambda$-calculus, but that's usually not as efficient.
* Finally, you'd need a polymorphic typing system for this to work.

As an aside, the formalisation of logics in interactive proof assistants like Isabelle is based on a similar idea, called logical frameworks.
> 1 votes

---
Tags: type-theory, type-inference, unification
---


# Question
Title: Determine whether two languages are context free
(1) $L\_1 = \\{a^ib^{i+j}c^j|i,j\geq 0\\} $

(2) $L\_2 = \\{xy | x,y \in \\{0,1\\}^\*, x \neq y, |x| = |y| \\}$

I doubt that $L\_1$ is CFL. I've been trying to go with the string $s$ = $a^pb^{2p}c^p$. Thus, we can write $s$ as $uvxyz$. Now I'm trying to show $uv^2xy^2z$ is not in $L\_1$.

I really have no idea how to approach (2). And if it is context free, how in the world would you draw a pda?

# Answer
> 3 votes
For the first one, $$L\_1 = \\{a^i,b^{i+j}c^j \mid i,j \geq 0 \\} $$

Here's an rough idea of the algorithm:

* read off the all '$a$'s and push $a$ into the stack
* upon seeing a '$b$', pop the '$a$'s till the stack is empty
* then again as long as reading '$b$'s keep pushing $b$ into the stack
* on seeing a $c$, start popping the stack until empty.

For the second one,

Please see my answer here, The other answer is equally good (perhaps even better and simpler) than mine.

# Answer
> 1 votes
$L\_1$ is context-free. It is fairly easy to write a grammar for it: $$ \begin{align} S &\to A C \\ A &\to \epsilon \\ A &\to a A b \\ C &\to \epsilon \\ C &\to b C c \\ \end{align} $$

Intuitively, $L\_1$ needs to remember the number of $a$'s, then when a matching number of $b$'s have been found it needs to remember the excess, and compensate by $c$'s. This is within the capabilities of a pushdown automaton (push a token per excess $a$, pop one when a $b$ comes, then start pushing $b$'s when the stack is empty and pop them when $c$'s come).

$L\_2$ is also context-free, but this is more difficult to see. Try reasoning by induction and deducing a grammar, but be warned that it isn't straightforward. Start with the idea that either $x$ and $y$ start with the same letter, in which case the rest of the words must be different, or $x$ and $y$ start with the same letter, in which case the rest of the words can be arbitrary. This is not enough, because you can't keep track of the fact that you're decomposing into words of equal length. So you need to do more to ensure that you aren't including words of the form $x x$ that you happened to break down in the wrong place. See Show that { xy ∣ |x| = |y|, x ≠ y } is context-free for a solution.

# Answer
> 0 votes
Another simple way to see that (1) is a context-free is to observe that both $L'\_1=\\{a^ib^i\mid i\ge 0\\}$ and $L''\_1 = \\{b^jc^j \mid j\ge 0\\}$ are context-free, and $L\_1$ is simply $L'\_1\cdot L''\_1$, the concatenation of $L'\_1$ and $L''\_1$. And we know that the set of context-free languages is closed under concatenation.

---
Tags: context-free, pushdown-automata
---


# Question
Title: Showing that CLIQUE can be verified in polynomial time
The CLIQUE problem -- problem of finding the maximum clique in a graph -- is NP-complete. That is, CLIQUE is

1. in NP and
2. there is an NP complete problem, 3-SAT for one, that reduces to CLIQUE in polynomial time.

Part 2. above is fine -- all over in every resource and very well explained. For Part 1., from what I know, we need to have the following: Given a specific solution instance, we need to show that it can be verified, in polynomial time, that that solution is an answer to this problem. So for instance, given a specific graph and a subgraph of it, we should be able to check whether that subgraph is a clique of maximum size in that graph.

The resources I've read so far are phrasing this Part 1. here as "easy, straightforward, etc" or "it can be shown in $O(n^2)$ time that the given subgraph is a clique/not". However, the verification here is not just whether it's a clique, but also is whether it is a maximum clique in the graph. How can this be decided in polynomial time?

What am I missing here?

# Answer
What you're missing is the difference between decision problems and optimization problems. "Finding the maximum clique" is an optimization problem. The corresponding decision problem is "Does there exist a clique of size $\ge k$?". The latter problem is in NP. NP is a class of decision problems, so it doesn't make sense to ask whether an optimization problem is in NP; that's only meaningful for decision problems. Any textbook or standard resource on NP should explain the difference between decision problems vs. optimization problems in more depth.
> 4 votes

---
Tags: complexity-theory, decision-problem, np
---


# Question
Title: Does a Universal Turing Machine have more computational power than a non-universal one?
I'm a bit confused about these concepts. As far as I understand, something is Turing complete when it can simulate a Turing machine. And there is this thing called a Universal Turing machine which is universal because it can simulate a Turing machine. Which to me, implies there are Turing machines that are not universal and cannot simulate a Turing machine. Does this mean non-universal Turing machines are not Turing complete?

Could anyone clarify this concepts for me?

# Answer
In short yes, a non-universal Turing Machine is not Turing-complete.

The key part is that a computational model is Turing-complete if it can simulate ***any*** Turing Machine (or using the transitivity of the simulations, if it can simulate a ***Universal*** Turing Machine).

As you note, many Turing Machines are not Universal, they compute something, but they can't simulate any computation that any Turing Machine could do.

A possibly intuitive practical way of thinking about this is that Turing Machines are normally equivalent to programs - they take a particular type of input and compute some output. Universal Turing Machines are equivalent to programming languages or computers - you can build/run any program/Turing Machine on them. Of course I'm using "equivalent" very loosely here.
> 9 votes

# Answer
This is a response to the following comment by Juan Luis Soldi but was too long to put in a comment.

> Let me see if I get it. A Turing Machine is a Turing complete machine because it can run programs that can compute anything. Theses programs can be either Turing Complete (like running Visual Studio on Windows) or not (like running Paint). A Universal Turing Machine is a Turing Machine loaded with a Turing complete program. Right?

The Visual Studio / Paint analogy isn't a million miles from the truth but it contain a couple of problems that ought to be discussed.

First, in my opinion it's best not to think of Turing machines as being "loaded with a program", because that leads to confusion. A Turing machine computes a single function, kind of like those cheap little games machines that, say, only play Tetris. Remember that, historically, Turing machines predate the stored program computer by about fifteen years. The definition of the machine includes the transition function, which is fixed: the machine and the program are the same thing and, if you want to change the program, you have to change the hardware.

A universal Turing machine is a Turing machine whose input is a description of a Turing machine and its input. The universal Turing machine simulates the machine described in its input. (As such, it's a bit more like an interpreter than a compiler.) So, if a universal Turing machine $U$ has as input a description of a machine $M$ and its input $x$, its output will be whatever $M$ outputs when it's given input $x$. If $M$ doesn't halt when given input $x$, then $U$ will not halt when given a description of $M$ and $x$.

Now, Turing completeness is a property of models of computation. A model of computation is Turing-complete if defines exactly the same class of functions as Turing machines. So Turing machines are Turing-complete by definition. The lambda-calculus is Turing complete because every lambda-calculus term can be translated into a Turing machine and every Turing machine can be translated into a lambda-calculus term.

Strictly speaking, a universal Turing machine (UTM) is not Turing-complete. This is because it only computes one function: if its input describes a Turing machine $M$ and $M$'s input, the UTM tells you what that machine would have done. Why isn't this Turing-complete? Well, there's a Turing machine $T$ that accepts all inputs of even length and rejects all inputs of odd length and no UTM can do that. The UTM can simulate $T$ but the UTM itself isn't accepting exactly the even-length inputs. Rather, it's accepting all inputs that start with the description of $T$, followed by an even-length input for $T$.
> 5 votes

---
Tags: turing-completeness
---


# Question
Title: What is Harrison hashing, its applications in web search engines?
What is Harrison hashing and what are its applications in web searching? Can some one give me some relevant information?

**Update:**

I found it here , and is a part of M.Tech syllabus of a friend of mine. I need to explain him this concept and then see how it can be applied in web applications. Many thanks for spending your precious time.

# Answer
I think you are looking for Implementation of the Substring Test by Hashing by Malcolm C. Harrison. It describes a fast implementation, which determines if one string contains a specified substring. This technique is appropriate in searching of large static text files.

Also you can find in String Searching Algorithms By Graham A. Stephen.
> 4 votes

# Answer
Harrison hashing is a rapid technique for determining if a given substring COULD POSSIBLY be contained in a larger string. The first step is to create SIGNATURES of all the strings in the file to be searched using the hashing algorithm. These signatures are then stored along with the actual file. Typically the file being dealt with consists of individual text lines, because the search technique will only work within a single line. Then using the same hashing algorithm one constructs the signature of the substring being searched for. One then applies a simple Boolean test to determine if the substring is possibly contained in the string. If the answer is affirmative then one must examine the actual string and substring to see if there is indeed a match. But if the answer is negative it is impossible for the substring to be contained in the string and that particular string in the file does not have to be examined further.

The signatures are constructed by examining all pairs of consecutive characters in the string. Thus for the string "abcdef" the pairs would be "ab","bc","cd","de","ef". Depending on the nature of the data and the computer being used, one picks a bit size for the signature, perhaps 32 or 64 bits, but different sizes are possible. Next you have to develop a hash function that will map any pair of characters into one of the bits in the signature. A simple hash function would be to multiply the values of the characters together, divide by the bit size of the signature, and use the remainder. In practice some tweaking is necessary to get a good distribution of the bits set across all of the character pairs. You then calculate the hash for each of the character pairs and set the corresponding bit in the signature. When different pairs hash to the same bit the bit stays set, that is you keep ORing in the bit to set in the signature. You build a table of all of the signatures for all lines in the original source file.

To search for a substring you calculate the signature of the substring itself. If the substring is contained in the string then ALL OF THE SET BITS IN THE SIGNATURE OF THE SUBSTRING MUST BE SET IN THE SIGNATURE OF THE STRING. This should be self evident, for if the substring contained a pair of characters which hashed to say 17, but bit 17 wasn't set in the signature of the string, then clearly that pair of characters could not be in the string, because if it were that bit would have been set.

If the signature is contained in a single computer word then all that is necessary to determine if all the bits of the substring are in the string is to exclusive or (XOR) the signatures of the string and the substring, and then and (AND) that result with the signature of the substring. If the result is non zero, then there exists at least one pair of characters in the substring that is not in the string, and hence the substring cannot be contained in the string. Since only two logical operations are required to totally test any string in the file the program can operate very quickly. In practice the Harrison hashing test will eliminate most of the file from consideration and the program will only have to perform the full substring search on a very small portion of the file.

I explained the algorithm using pairs of characters, but another variant is to use three consecutive characters.

Professor Harrison was one of my teachers at the Courant Institute of Mathematical Sciences and I have used this algorithm in a number of text editing programs. It is a truly brilliant observation.
> 3 votes

---
Tags: algorithms, strings, search-algorithms, hash
---


title: Number of Independent Sets in a tree

text:
# Question
Title: Number of Independent Sets in a tree
(I've been stuck on this homework assignment for far too long)

I need to find the number of independent sets in a tree.

For example, say the set of nodes in a tree is {A, B, C, D, E}. B and C are children of A and D, E are children of B. This tree has 14 independent sets.

I assume that the algorithm will be recursive and I think that I should make each level of a tree into a linked list, so B-\>C and D-\>E, but more than that I'm stumped.

Would grealy appreciate help.

# Answer
> 3 votes
Hint: Compute recursively the number of independent sets (a) containing the root, (b) not containing the root.

---
Tags: algorithms, trees
---


# Question
Title: Recursive equation for complexity: T(n) = log(n) * T(log(n)) + n
For analyzing the running time of an algorithm , I'm stuck with this recursive equation : $$ T(n) = \log(n) \cdot T(\log n) + n $$ Obviously this can't be handled with the use of the Master Theorem, so I was wondering if anybody has any ideas for solving this recursive equation.

I'm pretty sure that it should be solved with a change in the parameters, like considering $n$ to be $2^m$, but I couldn't manage to find any good fix.

# Answer
> 5 votes
I suppose you are looking for an asymptotic bound. Notice that the recursion depth is $\log^\* n$, that is how often do I have to apply the logarithm recursively to get below 2. Also, the function is increasing. Using these two facts, you can plug in the recursion once and then you see that you have at most $\log^\*$ summands, each of them at most $\log^2 n$ and then the additional $n$. This sum is dominated by $n$.

$$ \begin{align} T(n)&=\log(n) T(\log n)+n=\log n \log\log n \\;T(\log\log n)+\log^2(n)+n \\ &\le \log^\*n\log^2n+n=O(n) \end{align} $$

Clearly $T(n)\ge n$ and thus $T(n)=\Theta(n)$.

---
Tags: asymptotics, runtime-analysis, recursion, master-theorem
---