# Question
Title: Parallelization of an iterative function application
### What I have

An iterative process based on the application of a very simple function to represent a rate, with total dependence among any iteration and its predecessor (one input parameter for (n)th iteration is the output parameter from the (n-1)th iteration). Specifically,

$\qquad f(x, y, z) = x + \frac{y - x}{z + 1}$

with $x$ the modeled rate (typical value between 0 and 1), $y$ the contribution of every new record to the learning about the rate (typical value 0 or 1) and $z$ some kind of convergence/learning speed parameter (typical value any integer between 30 and 900). While $y$ and $z$ are constant, $x$ would be the result of the previous calculation.

### What I want

Some kind of manipulation of the function that allows some level of independence among sequential iterations, thus allowing parallelization.

What I know (or believe to) so far:

There is extensive published literature on parallel iterative methods, but most of them are about classical methods like Map-Reduce for Machine Learning on Multicore by Chu et al.

But I'm failing to recognize which of them I could "use" to help me with my simple function.

Can someone help me pointing literature on the basics of function transformation aiming towards parallelization? Any thoughts on that matter will be very helpful.

# Answer
> 4 votes
A good starting point is the Wikipedia article on Prefix Sums. A particularly good source is Guy Blelloch's article about Prefix Sums.

The idea is this: *if* you have an associative operator (e.g., "+"), you can turn a long dependent chain of those operators into a tree that is more balanced.

For the example you gave, $f(x,y,z) = x + (y-x)/(z+1)$ we can actually generalize to an entire class of problems. $$ \begin{array}{rcl} x\_{i+1} & = & x\_i + (y\_{i+1}-x\_i)/(z\_{i+1}+1) \\ & = & \frac{y\_{i+1}}{z\_{i+1}+1} + \frac{x\_i (z\_{i+1}+1) - x\_i}{z\_{i+1}+1} \\ & = & \frac{y\_{i+1}}{z\_{i+1}+1} + \frac{z\_{i+1}}{z\_{i+1}+1} x\_i \\ & = & a\_{i+1} + b\_{i+1} x\_i\mathrm{,} \end{array} $$ where the $a\_i$ and $b\_i$ can be calculated completely in parallel. So the calculation looks like:

Ok. So let's look at a few iterations starting at $x\_i$ through $x\_{i+3}$: $$ \begin{array}{rcl} x\_{i+2} & = & a\_{i+2} + b\_{i+2} x\_{i+1} \\ & = & a\_{i+2} + b\_{i+2} (a\_{i+1} + b\_{i+1} x\_i) \\ & = & (a\_{i+2} + a\_{i+1} b\_{i+2}) + b\_{i+2}b\_{i+1} x\_i \\ x\_{i+3} & = & a\_{i+3} + b\_{i+3} x\_{i+2} \\ & = & a\_{i+3} + b\_{i+3} (a\_{i+2} + a\_{i+1} b\_{i+2} + b\_{i+2}b\_{i+1}x\_i)\\ & = & (a\_{i+3} + a\_{i+2}b\_{i+3} + a\_{i+1}b\_{i+3}b\_{i+2}) + b\_{i+3}b\_{i+2}b\_{i+1}x\_i\\ & = & A\_{i+1,i+3} + B\_{i+1,i+3}x\_i \end{array} $$

and so on. The interesting thing is that we can calculate $x\_{i+k}$ as $A\_{i+1,i+k} + B\_{i+1,i+k}x\_i,$ where large chunks of computation can be summed up independently in the $A\_{i+k}$ and the $B\_{i+k},$ *without knowing* $x\_{i+1}, \cdots, x\_{i+k-1}.$

Now let's chunk up the work of calculating the $x\_i$'s. Here's what it might look like if we divided the calculation up into 4 equal parts and put each part on a different thread:

So each thread works completely independently to calculate the $A\_i$ and $B\_i$. Then we have a final (sequential) phase where we calculate $x\_{n/4}, x\_{2n/4}, x\_{3n/4},$ and $x\_n$.

As Guy Blelloch's article shows, you can actually calculate all the partial sums with one last step, if you need them.

---
Tags: reference-request, parallel-computing
---


title: Regular language proving

text:
# Question
Title: Regular language proving
Question:The set of all first names given to children born in New Zealand in 1996

I think this language is regular because every element in the set can be a accept state

How can I prove if the language is regular?

# Answer
> 3 votes
Every finite language is regular. The easiest way to prove it is to build the regular expression $w\_1+w\_2+\dots+w\_n$ where $\\{w\_1,\dots,w\_n\\}$ is you finite language.

You can also build an automaton as you said. May be build a separate one for each word and the do a finite union is the easiest.

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


# Question
Title: Given an n-state TM, can we construct an m-state TM (m>n) to determine if it halts?
BB(n) is roughly the maximum number of new states an n-state TM can run into without halting. So for a particular n, if we know BB(n), then we can find out if an arbitrary n-state TM halts by running it for BB(n) steps.

So given some n-state TM, can we construct an m-state TM, where m\>n, to calculate BB(n) and thus decides if it halts?

Now some might say that this is equivalent to solving the halting problem, but I don't think so. Because given an arbitrary TM, we don't in fact know how many states it has. And if we don't know n, we certainly can't find m.

If the answer is in the negative, then how is it that we can in fact find out the values of BB(n) for small n? What's the connection between incomputability and unknowability?

# Answer
For a **particular** $n$, there are at most $2^{O(n)}$ different TMs with $n$ states, and we can have a list for all of them: 1 is the TM halts, and 0 otherwise. A TM that has this "list" in its memory can decide the problem you give in your question. Not only this language is decidable - it is even regular!

The "halting problem" states though, that there is no TM that works for **all** possible $n$'s.
> 3 votes

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


title: construct a TM from a PDA

text:
# Question
Title: construct a TM from a PDA
Given a PDA $P=(Q,\sum,\delta,q\_0,F)$ construct formally a TM that accepts $L(P)$.

My idea is to construct a Turing machine with 2 tapes, one for the input and the other for the stack. Also to add $q\_a$ for accept and $q\_r$ for reject and to send to $q\_a$ if the TM stops on states in $F$ and send to $q\_r$ otherwise.

But I am having a trouble to define new the transition function for the TM: $\delta\_M$.

# Answer
> 1 votes
Your idea is correct (or at least one way of doing it), though it may be "easier" to add a third tape, where you just write the current PDA state. Your transition function just needs to simulate the PDA. The alphabet for the input tape is just the PDA's input alphabet plus the blank, the alphabet for the stack tape is the stack alphabet plus the blank symbol. You read a symbol on the input tape, the PDA state and the current symbol on the stack, move the input head right and maybe write a symbol on the stack tape and stay put, write a symbol and move right, or erase a symbol and move left. The state tape head just stays put and writes the new state on the tape. If you read a blank on the input tape, and the current PDA state is accepting, move to the TM's accept state, if you otherwise read a blank on the input tape, then move to the TM's reject state.

Given a PDA transition $\delta\_{PDA}(q\_{i}, \sigma, \tau) = (q\_{j}, \rho) $ (so moving from state $q\_{i}$ to $q\_{j}$, with $\sigma$ in the input, popping $\tau$ and pushing $\rho$), the TM transition looks something like $\delta\_{TM}(q\_{p}, \sigma, \tau, q\_{i}) = (q\_{p}, (\sigma, R), (\rho, S), (q\_{j},S))$ - the notation here is somewhat abused, mostly to group each tapes actions together in order. Transitions that have one or more $\varepsilon$/$\lambda$ in them complicate things a little, the input tape head would not move on an $\varepsilon$, the stack tape head might move left or right, depending on whether it was a pop or push that had the $\varepsilon$.

This gives you a TM with a single state that does all the real work, and the accept and reject states.

---
Tags: machine-learning, turing-machines, machine-models
---


# Question
Title: Is there a mistake in the expression for clean behavior in Pnueli's article from 81'?
I am reading an article called The temporal semantics of concurrent programs .

On page $9$, there is a small section (numbered as $2$) called "clean behavior".

I think that there is a problem with this part, what does Pnueli meant by "Let $\lambda\_i$ be the leagality condition for **the** statement departing from $m^i$" ?

I have marked the word "the" in bold since, as I see it, there can be more than one edge departing from $m^i$, an example can be seen on page $11$, at the beginning of part $5$.

Did I missunderstood something , or is there actually a mistake in the article by not addressing the fact that there can be more than one statement that can be exectuded after $m^i$, and that this expression for clean behavior need to be corrected accordingly ?

# Answer
It would seem that in (1) (still page 9) he refers to a sequential program, so there is no concurrency. I think this assumption holds for the rest of the articles. So the "the" is ok there.
> 2 votes

---
Tags: concurrency, linear-temporal-logic
---


# Question
Title: Circuit size for "at least n inputs are true"
Say you have $m$ boolean inputs, and you are given a threshold $n$. You need to construct a boolean circuit that evaluates to true if at least $n$ of the inputs true. You may use AND, OR, NOT, or XOR gates (restricted to fan-in two, with arbitrary fan-out). Asymptotically how small can you make this circuit?

Any reasonably tight upper bound would be appreciated. I keep on thinking of ways to recursively construct such a circuit but I can't find anything good. Also, any results for any other reasonable basis of allowed gates would also be useful.

# Answer
> 8 votes
From S. Chaudhuri, J. Radhakrishnan. Deterministic Restrictions in Circuit Complexity:

**Theorem 6.1**: A circuit computing $T\_k^n$ with $k \leq n^{1/3}$ has $\Omega(k^2(\ln n)/\ln k)$ gates

Where $T\_k^n$ is the boolean function that has the value 1 iff at least $k$ of its inputs have the value 1 (*threshold function*).

# Answer
> 4 votes
We can get some sort of upper bound from some complexity inclusions.

$TC^{0}$ is the class of polynomially sized, constant depth boolean circuits where we also have a $MAJORITY$ gate of unbounded fan-in, so there's a size $1$ $TC^{0}$ circuit that computes the function you want (one $MAJ$ gate with all the inputs going to it).

$NC^{1}$ is the class of boolean circuits of polynomial size and $O(\log n)$ depth (but here we only have the normal gates). It is known that $TC^{0} \subseteq NC^{1}$, so at worst, you can compute $MAJ$ with a poly-size $O(\log n)$ depth circuit.

I suspect that as you only need $MAJ$, we can do better, but I haven't managed to get a good reference for this quite yet. Vollmer's "Introduction to Circuit Complexity" should have the reduction, but I don't have a copy available. It should also be a uniform reduction too (i.e. for an input of size $n$ we can efficiently produce the appropriate circuit).

This question on cstheory.SE might also have something useful to you in it, but it's pretty technical.

# Answer
> 0 votes
with $T\_k^n$ a standard threshhold function defined as in Vors answer, $T\_k^n$ is a symmetric function. thm 2.11.1 in Savage\[1\] gives a $O(n)$ size circuit.

\[1\] Models of Computation, John E Savage

---
Tags: complexity-theory, circuits
---


# Question
Title: Proving that $\text{PCP}(O(\log n),1)\subseteq \mathsf{P}$
I'm studying the PCP theorem.

While it is easy to prove that $\mathsf{P}=\text{PCP}(O(\log n),0)$ , proving that $\text{PCP}(O(\log n),1)\subseteq \mathsf{P}$ i.e. PCP that uses $O(\log n)$ random bits and read 1 bit of the proof is less obvious, what I tried to do is to take some proof $\pi$ of length $n^{O(1)}$ (because effectively the message sent by the prover is bounded by $2^{r(n)}q(n)=2^{O(\log n)}=n^{O(1)}$) then try all the coin tosses each time the verifier read some bit of the message so if the proof is not correct we flip the bit in the proof!

# Answer
By the basic equivalence of PCPs and MaxCSP problems, there exists a conjunction $C$ of polynomially many boolean literals, s.t.

> $\exists \text{ proof } \pi$ which makes the verifier $V$ accept with probability $\geq p$ $\Leftrightarrow$ $\exists$ an assignment that satisfies at least a $p$ fraction of the literals in $C$.

So you just need to show that the following problem is polytime solvable: given a conjunction $C$ of boolean literals, what is the largest number of literals that can be simultaneously satisfied. That's a very easy problem.

The idea here is that a PCP with query complexity $q$ corresponds to some MaxCSP problem with arity $q$. If the PCP has completeness $c$ and soundness $s$, then the language accepted by the PCP is reducible to a promise version of an arrity $q$ MaxCSP problem where in a 'no' instance at most an $s$ fraction of the constraints can be satisfied, and in a 'yes' instance at least a $c$ fraction of the constraints can be satisfied. These reductions are standard, look up any reference on PCPs.
> 5 votes

# Answer
The PCP theorem states that $\mathrm{NP}=\mathrm{PCP}\[O(\log n),O(1)\]$. So showing that $\mathrm{PCP}\[O(\log n), O(1)\] \subseteq \mathrm{P}$ should be pretty difficult...
> 3 votes

---
Tags: complexity-theory, randomness
---


# Question
Title: Algorithm to determine whether two regexes are equivalent
Given two arbitrary regular expressions, is there an "efficient" algorithm to determine whether they match the same set of strings?

More generally, can we compute the size of the intersection of the two match sets?

What algorithms are there to do this, and what complexity class do they live in?

If we disallow the Kleene star, does that alter the picture at all?

# Answer
Hendrik Jan gives a good answer for complexity class, but not an algorithm itself.

The simplest algorithm to do this that I know of is to convert the regular expression to a DFA. There are known techniques for converting a regular expression to an NFA, and an NFA to a DFA.

Once you have two DFAs, testing for equivalence is efficient and decidable, since the minimal form of a DFA is unique up to isomorphism.

However, constructing these DFAs from NFAs could take lots of time, and produce extremely large DFAS, exponentially large in the worst case.
> 15 votes

# Answer
Equivalence of regular expressions is known to be PSPACE-complete, which is rather bad. The paper "Complexity of Decision Problems for Simple Regular Expressions" lists several subclasses of regular expressions with their respective complexities. (link)
> 14 votes

---
Tags: algorithms, regular-expressions
---


title: Normal form Lambda calculus expression

text:
# Question
Title: Normal form Lambda calculus expression
I need a little help with a lambda calculus reduction to normal form: $$(\lambda xxxx.xx)(\lambda x.xx)(\lambda x.x)y((\lambda x.x)x)$$ It should be solved like this: $$xx(\lambda x.x)y((\lambda x.x)x)$$ and then: $$xx(\lambda x.x)y(x)$$

This is the result of any of the lambda calculators that you can find online.

My question is: why can't I go on with reductions and make also $(\lambda x.x)y$ so the resulting expression would be $xxy(x)$?

Can you give me a complete answer, with theory of lambda calculus rules/proofs?

I really want to understand this exercise, any help would be appreciated.

# Answer
> 2 votes
As pointed out in the comments, the first term seems broken - too many $x$es.

The key is that function application *is not associative* (both in the lambda calculus and outside it). In particular, $a(bc)$ is different from $(ab)c$. In the first term, we apply $b$ to $c$ and then $a$ to the result. In the second term, we apply $a$ to $b$ and then apply the result on $c$.

In your case $xx(\lambda x.x)yx$ is parenthesised as $(((xx)(\lambda x.x))y)x$, because function application associates to the left. This means that there is no redex there, it can't be reduced further.

Your mistake was in that you added parentheses like $xx((\lambda x.x)y)x$, which is a completely different term.

---
Tags: lambda-calculus, normal-forms
---


# Question
Title: $\mathsf{RegExpEq_*} \in \mathsf{coNPC}$ but why isn't in $\mathsf{P}$
Hello for a homework I have to show that deciding whether a regex over $\Sigma = \\{0,1\\}$ descibes $\Sigma^\*$ is $\mathsf{coNP}$ complete (this is irrelevant for the question though).

The thing which irrs me is that I think this problem is in $\mathsf{P}$.

Here is my argumentation:

Let $R$ be a regex, then we have $$L(R) = \\{0,1\\}^\* \Leftrightarrow \overline{L(R)} = \varnothing$$

Given $R$ we can consruct an NFA with $\epsilon$ moves for $L(R)$ in poly. time; eliminating the $\epsilon$ moves (again poly. time: $O(|Q| \cdot |\delta| \cdot |\Sigma|)$) we obtain an NFA $M$.

By toggling the accepting states of $M$ we can construct an NFA which accepts $\overline {L(R)}$, whose emptiness we can check with a BFS (again in poly. time).

$\leadsto \mathsf{RegExpEq\_{\*}} \in \mathsf{P}$

Where does my argumentation shatter? If both my argumentation and the question is correct, then $\mathsf{P} = \mathsf{coNP}$ which seems highly doubtful.

# Answer
> 7 votes
*By toggling the accepting states of $M$ we can construct an NFA which accepts $\overline{L(R)}$*.

Well, that's not true. You won't get $\overline{L(R)}$. That would have happened if $M$ was a DFA, rather than a NFA. So you have to first convert $M$ to $M'$ which is a DFA, but then you would have to spend an exponential time there.

---
Tags: complexity-theory, formal-languages
---


# Question
Title: Assuming NP $\neq$ P, are there NPI languages only P languages reduce to?
let $L\_c$ be the class of all languages that have a polynomial reduction to some language L, for example if $L=SAT$ then $SAT\_c=NP$.

Assuming know that $NP\neq P$ we know that there exist languages that are not NP-hard and not in P, i.e. those in NPI. My question is there a language L in NPI such that $L\_c \setminus \\{L\\}=P$?

# Answer
> 4 votes
I don't think such a language $L$ can exist, because it suffices to slightly modify it to get a language $L'\in L\_c$ and not in $P$. For instance let $u$ be a word of minimal length which is not in $L$, and take $L'=L\cup\\{u\\}$. It is clear that $L'$ polynomially reduces to $L$: check if the input word is $u$, and if it's not use your oracle for $L$. Since $u$ is of constant size, this algorithm runs in polynomial time. So $L'\in L\_c$. But you also have the inverse reduction: $L$ polynomially reduces to $L'$. This implies that $L'\notin P$, because otherwise $L$ would also be in $P$.

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Infinite languages and undecidable languages
I'm having a problem with proving the following statement:

For every infinite language $L$, does there exists an infinite language $L' \subseteq L$ such that $L'$ is not decidable?

# Answer
> 7 votes
The set $\\{L' : L' \subseteq L\\}$ is an uncountable set of languages, and since there is only countably many decidable languages, it has to contain an undecidable language. (You can get a concrete $L'$ by a diagonal argument.)

# Answer
> 4 votes
Since $L'$ is totally free, you can always define it directly as something undecidable.

For example ordering the words of $L$ with lexicographic order and ordering turing machines (in any order you like) you can define $L'$ as: $L'=\\{w\_i|w\_i\text{ ith word in $L$ and $M\_i$ stop on }\epsilon\\}$.

If $L'$ is decidable then termination with empty tape of Turing machine is decidable. Contradiction.

Hence $L'\subseteq L$ and $L'$ is undecidable.

**Note I assumed $L$ decidable. If $L$ is already undecidable then take $L'=L$.**

---
Tags: undecidability
---


# Question
Title: Why is the size of the search space 2057 in the 8-queen puzzle?
In the 8-queen puzzle, to reduce the search space, we can use an incremental approach. We put the first queen in the first column, then the 2nd queen in the 2nd column etc., avoiding the slots that are already being occupied.

According to Peter Norvig's book, there are only 2057 possible sequences. Where does that number come from?

# Answer
According to Peter Norvig in 2007, it comes from "... writing a program and counting the states."

For the $n$-queens problem, it is not too hard to show that $(n!)^{(1/3)}$ is a lower bound on the size of state space. This can be calculated by considering the maximum number of squares in each column that might be threatened by queens from previous columns. For $n=8$, this evaluates to $34.29$.
> 2 votes

---
Tags: combinatorics, artificial-intelligence
---


# Question
Title: Using Little's law to find the average N of customers
I'm trying to understand Little's law and can't seem to get past this scenario:

Let's say people arrive at the register at 12 per hour. It takes 10 minutes (1/6 of an hour) to service each one of them. The law says that the long-term average number of customers is 12 * 1/6 = 2. After the first hour, my assumption is that there will be 6 customers not serviced. Then after the second hour, there will be 6 more. Why is the long-term average `2` and not the `storeCapacity`?

Is my usage of the law wrong because I'm not talking about a stable system?

# Answer
> 1 votes
Your intuition was right. As you hinted, Little's law only applies to a stable system. This is not a stable system. The arrival rate exceeds the rate at which customers can be serviced. Therefore, the number of customers waiting in line will grow without bound, getting increasingly larger as time increases. That means this is not a stable system.

You can only apply Little's law to stable systems. Since this isn't a stable system, Little's law doesn't apply.

---
Tags: concurrency
---


title: Information of a stream of bits

text:
# Question
Title: Information of a stream of bits
Here is my problem. I have to compute the amount of information that is possible to encode in a string of bits. This string of bits represent a stream. Let us call such stream as $X\_1,X\_2,X\_3,...,X\_n$. Important: this succession of Random variable is not a Markov Process, but a process with memory!! I suppose that the right measure would be based on the information entropy of the collection of random variables: $H(X\_1,X\_2,X\_3,...,X\_n)=\sum\_i H(X\_i|X\_{i-1},...,X\_1)$

Am I right?

However I have more doubts:

* If $n \to \infty$ then a better measure would be the entropy rate, isn't it?.
* What is meaning of $H(X\_n)$, i.e. the entropy of only the last random variable?
* In term of information theory, what is the meaning of $H(X\_1, X\_n)$ or $H(X\_1| X\_n)$ ?

A point is that I can compute both $H(X\_1, X\_n)$ and $H(X\_1| X\_n)$ for my process, but the computation of $H(X\_1,X\_2,X\_3,...,X\_n)$ remains very hard, as the process is non markovian.

Thanks!

# Answer
Yes, for a concrete value of $n$, $H(X\_1,\dots,X\_n)$ would be a good measure.

If $n \to \infty$ and you happen to know that the limit $\lim\_{n\to \infty} H(X\_1,\dots,X\_n)/n$ exists, then yes, the entropy rate would be a good measure.

I don't understand what your other questions are asking. What is the meaning of $H(X\_n)$? It is the entropy of $X\_n$. Giving any more concrete answer will depend upon the specific process that is used to generate $X\_n$. Unless there is something specific about your situation, it is unlikely that there is any natural meaning to assign to $H(X\_1,X\_n)$ or $H(X\_1|X\_n)$.
> 1 votes

---
Tags: information-theory, coding-theory
---


# Question
Title: Find the weight of the lightest path from u to v
Find the weight of the lightest path from u to v the goes through node a or/and b.

Do you have a suggestion on how it can be done?

# Answer
> 2 votes
Suppose we have a graph $G = (V,E)$ and the source $s$ and target $t$ vertices.

There is a variation of the shortest path problem in which one wants to find a simple path from $s$ to $t$ provided that this path visits a subset of the vertices $P \subseteq V$ and it is has minimum cost. Some call it the *$(s - P - t)$-shortest path*. When we have $P = V$, this problem becomes the *Hamiltonian Path Problem*, thus telling us that it is $\mathcal{NP}$-hard in general.

Here are some references:
http://epubs.siam.org/doi/abs/10.1137/1015031
http://or.journal.informs.org/content/14/5/909.short

As jmite commented, the difference between AND and OR in your question is quite important. In the scope of this problem I cited, asking the OR version would imply solving the problem for $P\_1 = \\{a\\}$, then for $P\_2 = \\{b\\}$ and outputting the minimum of the two as the answer. The AND version would be the one using $P\_3 = \\{a,b\\}$, which could be a completely different solution.

I don't actually know if there is some polynomial algorithm for this problem when the number of "mandatory" vertices is constant, but I do have a simple way to get a somewhat good lower bound on the solution value.

For the OR version:

1. calculate the SP from $s$ to $a$ and then from $a$ to $t$
2. calculate the SP from $s$ to $b$ and then from $b$ to $t$
3. output the minimum from the two as a LB

For the AND version:

1. calculate the SP from $s$ to $a$, then from $a$ to $b$ and finally from $b$ to $t$
2. calculate the SP from $s$ to $b$, then from $b$ to $a$ and finally from $a$ to $t$
3. output the minimum from the two as a LB

These bounds might not be tight because the subpaths may overlap and not compose a simple path. If I'm not mistaken, they output the actual solution for DAGs.

Also, notice that if either $a$ or $b$ are leaves ($d(a) = 1$ or $d(b) = 1$), then these bounds may be invalid, but the algorithms could easily be fixed.

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


# Question
Title: Preventing oversell, allocation of limited resources with overlapping properties
I am trying to solve problem of preventing oversell of limited resources.

Consider resources (people) who are described by set of properties where each property belongs to different category (example properties from four categories: male, age 25-30, 2 children, interested in games).

Buyers want to allocate access to resources. Buyers can specify subset of categories and one property from each category (example: allocate 1000 males, age 25-30 or allocate 100 females, age 25-30, interested in music).

In my real life example I have 6m+ possible set of properties (profiles) where for each set of properties I know how many profiles exists.

My initial approach was to build a graph like one below:

and then traverse using edge weights, for instance validating if demand for 100 females, age2 can be satisfied:

1. check if size(female, age2) \< 100
2. for each parent:
    1. check if size(parent) \< 100 and go to 2.
3. for each child:
    1. check if size(child) \< 100 * weight(edge(node, child)) go to 1.

(above algorithm is simplified as does not prevent visiting same node multiple times)

It all works fine when graph is small, however when number of nodes and edges (dependencies) between nodes (profile universe groups) grows it does not scale very well.

Consider example:

* large graph, 6m nodes, 20m+ edges
* buyer wants to allocate 1000 males (and there are only males and females in gender category)

algorithm would start with top-level 'male' node which probably has 10m+ outgoing edges and 10m+ checks would be required (and probably each of those 10m outgoing edges has incoming edges which need to be checked as well).

I was trying to find different approach but failed. I was trying to google out existing solutions but seems like I am unable to even name problem properly. Any reference to what is this problem similar to would be good for me as a starting point.

Thanks for comments/help.

Two more graphs to present exponential growth of the graph: 3 categories

4 categories

**Update**

Regarding size, assuming 8 categories of properties where each category has: 2, 6, 6, 6, 6, 8, 1140, 150 values respectively then estimated number of profiles: 2\*6^4\*8\*1140\*150 ~= 3.5 * 10^9. Number of nodes in graph: at least 7 * 10^9, number of edges in graph: at least 140 * 10^9.

**Update #2**

Formula for number of nodes is:

$\sum\_{i\<n}\prod\_{k\<i \atop j\_1, j\_2, ..., j\_k \< n} s\_{j\_{1}} ... s\_{j\_{n}}$

where $n$ is number of categories and $s\_x$ is size of category $x$.

So in my example there would be 11'169'108'657 nodes.

**Update #3**

As per @Raphael advice - I have reduced number of nodes and now formula is:

$\sum\_{i\<n-M}\prod\_{k\<i \atop j\_1, j\_2, ..., j\_k \< n} s\_{j\_{1}} ... s\_{j\_{n}}$

where $M\<n$ and assumed that distribution of resources across smallest slices of universe is equal. At the same time removed lot of edges from graph.

Example of sub-graph size reduction:

# Answer
> 1 votes
So the data structure holding pointers for every possible combination of classifiers is huge. Sure, but why build it at all? Don't overengineer this!

Just store the profiles in a database and do one (linear time) filtering sweep for each query, i.e. select/count on demand. For a few millions of records, that should require no further preprocessing.

If the number of requests is large and/or you need *really* small response times, you can think about caching, or creating equivalence classes along some popular classifiers, or along classifiers with few large classes. Then, the linear sweep has to be done only on small lists.

For example, you can divide your database along gender and age (assuming these are included in most customer queries)

$\qquad \\{m, w, o\\} \times \\{0..5, 10..15, \dots, 95..100\\}$

where the values obviously depend on your data. Then, each query will require only few of these small lists, and can even parallelise if you store the individual chunks separately.

---
Tags: algorithms, databases, counting
---


# Question
Title: When to use SAT vs Constraint Satisfaction?
If I have a hard problem, one standard approach is to express it as a SAT instance and try running a SAT solver on it. Another standard approach is to express it as a constraint satisfaction problem, and try using a CSP solver. The two feel somehow vaguely similar in what sorts of problems can be naturally expressed in their input format.

Are there any guidelines or rules of thumb for how to recognize, for a given problem, which approach is more likely to yield good results? Is there any guidance anyone can offer about which sorts of problems can be handled better by SAT solvers than by CSP solvers, or vice versa?

(Obviously, there are some easy problems that can be solved by both approaches. There are also some hard problems that can't be usefully solved by either approach. Let's set those aside. The case where guidance is most helpful are problems where either SAT solvers perform better than CSP solvers, or where CSP solvers perform better than SAT solvers. How do I recognize when a SAT solver is likely to be a better fit than a CSP solver, or when a CSP solver is likely to be a better fit than a SAT solver -- i.e., which approach to try first?)

# Answer
I think this is a very good question. You could also ask: when to use a SMT solver? I have a feeling it might be hard to determine before modeling the problem and actually running the CSP/SAT/SMT solvers and finding out. It is well known that even different solvers perform very differently on the same instances! My intuition also comes from the fact that there are potentially many ways of modeling a problem. Furthermore, there are many ways of doing search and inference, depending on what type of constraints is used (if the formalism in question allows different types).

Take for example the standard Sudoku puzzle. For the standard $8 \times 8$ puzzle, a modern SAT/CSP solver will solve any such puzzle in an instant. However, I would rather use a CSP solver because it is *easier* to express my intention. The mentioned puzzle needs $9+9+9=27$ alldiff constraints, and I'm done. There's actually quite a bit of research in the context of CSP solvers trying to solve Sudoku instances of different size. As far as I remember, they don't do any comparisons between SAT, but rather try to determine what kind of inference works the best, or what kind of Sudoku puzzles are hard. I don't know if for say $32 \times 32$ Sudoku puzzles, SAT solvers would be faster than CSP solvers.

Different formalisms are able to capture domain specific information and exploiting it better and in different ways. For a bit more on this, see the answer and the comments here.
> 8 votes

---
Tags: heuristics, sat-solvers, constraint-programming
---


# Question
Title: Complexity of an algorithm for bounding a region in 2D
First I apologize if the title is unclear, but I didn't find anything better.

I'm solving a differential equation that has two parameters , here denoted by points of a plane.These parameters are real numbers. For some points of the plane (or, equivalently, for some parameters of the differential equation) , the solution of the equation satisfies some condition and we denote such points of the plane with 1. This points make a simply-connected region in the plane, and I know that this region lies somewhere in $0\<x\<1.6, -.7\<y\<.3$ rectangle. My goal is to find this region.Remember that this region is on the real plane.($\mathbf R^2$)

**My main question is this:** I already know these two things about the wanted region:

1. The set of points on the plane that satisfy the conditions (the wanted region) , form a simply-connected region
2. This region lies somewhere in $0\<x\<1.6, -.7\<y\<.3$ rectangle

for example it may be something like this:

I want to use this two facts to find the region with less computations; i.e. instead of checking the condition on all points on the rectangle, actually , on a very high-resolution grid (this the first approach below), use an algorithm (below : Variant 2) that more quickly converges to **the boundary** (and so determines the region without inspecting all points).

(If you know a better approach ,I'll be happy to hear)

### Variant 1 (the naive approach, noted above)

Divide each axis to identical steps (of length $\Delta$ ) and check the condition on each node to find the region.$\Delta$ must be as small as possible to find the region with an acceptable accuracy ($\Delta0.001$ suffices for my purpose) . (in the picture : nodes = intersections). This method needs a huge number of check operations , but can be used to find all kinds of regions; I mean if I didn't know that the wanted region is connected or it had sharp edges, etc. ,this method was the only way.

### Variant 2

(It may be a famous method, but I haven't seen it before)

Because the region will be simply connected, it suffices to find its boundary .We use a **recursive** approach. We start from a grid (like the first step, but with much larger distance between nodes, say, $100\Delta$) and check the condition on this grid.For the next step, I assume the interval between two adjacent 1s is 1 everywhere and between two adjacent 0s is 0 everywhere. *If two adjacent nodes gave different results (1 on one them and 0 on the other) , I put a point between them and check the condition on that point (red points in the picture) check this point. If it was 1, I put a new point between this point and the adjacent 0 and check that point; and if it was 0, I put a new point between this zero and adjacent 1 and check that point*. I continue till I arrive at a distance of $\Delta$ between points.So I've found the boundary. (This method is like bisection method for finding the roots of a function)

In the picture, the first iteration is shown.Black and yellow points are the points of the initial grid (that are distributed on the whole rectangle) and red points are those that are added after checking the initial grid nodes. Black points are points that are determined to satisfy the condition (are 1) and so are certainly inside the region. Yellow points are those that did not satisfy the condition and so are outside, and red points are those added in the 2nd iteration , between adjacent nodes with different results (between a 1 and a 0) ,according to the above paragraph.

So , using this method I've found the region with the same accuracy as in the first method, and saved a lot of time too.

I want to know *how much this method is faster.* A qualitative answer that shows if it is better to implement this method , suffices. My problem is so computational intensive that I can't use the first approach.

# Answer
> 1 votes
This question is not well-posed. You haven't told us what form you want the answer in, nor what you know about the region. In the fully general case, this problem is not solvable in any finite amount of time: there are uncountably many possible regions, so you can't even describe all of them in finite space.

Perhaps what you want is an approximation to the region (or to its perimeter). If so, you need to figure out how you want it to be described, and what approximation metric you are using.

A plausible approach is to find a bounding box, then sweep a vertical line from left to right. If your region is convex, then given the vertical line $x=1$ (say), you can find all points on that line that lie within your region by using binary search (twice): the result will be that all points $(x,y)$ satisfying $x=1$, $f(1)\le y \le g(1)$ are in the region, for some values $f(1),g(1)$. Now if you know that all of the points in your region lies satisfy $1 \le x \le 5$, you can iterate over values of $x$, from $1$ to $5$ by steps $\epsilon$, and find the values of $f(x)$ and $g(x)$ for each such $x$. This gives you about $8/\epsilon$ points on the perimeter of the region. Now, you could interpolate along these points somehow to get a plausible approximation to the shape of the region.

Whether this is good enough will depend upon your particular application and what you are trying to accomplish. Since you haven't told us that, we can't evaluate whether this is an adequate solution for your needs. (That, incidentally, is why the question is not well-posed.)

# Answer
> 1 votes
This answer addresses the edited question (which is a bit different now).

If you want to know which of those two methods is faster on your problem instances, the best strategy is going to be to implement them both and try them both on your problem instances. No one here is going to be able to tell you the answer. Complexity-theoretic worst-case asymptotic running time analysis is not likely to be the best tool here to tell you how much better the second one is in practice. Instead, try some experiments and see how much faster it actually is!

Keep in mind it is possible that the second method might fail to find all of the region, depending upon how sharply curved (and how concave) the perimeter is. The first method could also fail, too, if the region is unpleasant enough. For instance, if the region has a very thin and long peninsula jutting out, and if that peninsula does not intersect any of your grid point, you will not detect the peninsula. That might be acceptable, given that your method is only intended as an approximation -- or it might not arise in practice, for the specific differential equations you are using -- but in principle, it could happen. Any worst-case complexity-theoretic analysis is going to have to assume that it does happen.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, computational-geometry
---


# Question
Title: Prove that if a problem L can be decided in polynomial time, then L ≤p L' for any other problem L'
So we know that there exists a Turing Machine $M$ and a polynomial $T$ such that:

* $M$ halts on all inputs within at most $T(|x|)$ steps
* If $x$ is in $L$ then $M$ accepts $x$
* If $x$ is not in $L$ then $M$ rejects $x$

We need to show that for any other problem $L'$, there exists a polynomial time computable function $f$ such that for all $x$, $f(x)$ is in $L'$ if and only if $x$ is in $L$.

I imagine the answer is simple but I'm stumped.

# Answer
> 2 votes
We show a karp reduction from $L$ to any other language $L'$, as long as $L'\notin\\{\Sigma^\*,\emptyset\\}$.

The reduction proceeds as follows. Since $L'$ is non-trivial, there exists $x,y$ such that $x\in L'$ and $y\notin L'$. Given input $w$, the reduction runs $M$ on $w$ (which takes polynomial time). Then, if $w\in L$ the reduction outputs $x$, and if $w\notin L$ it outputs $y$.

Proving correctness is trivial.

As @dkuper states, this is simply not true if we allow $L'$ to be trivial. However, it is a common mistake to ignore these end-cases in exercises (which I assume this is).

---
Tags: complexity-theory, reductions, decision-problem, polynomial-time
---


# Question
Title: How approximate are "approximate" nearest neighbor (ANN) search algorithms?
Starting to use nanoflann to do some point cloud nearest neighbor searching and it got me thinking about just how "approximate" ANN methods are.

If I have a (more or less) randomly distributed point cloud what is the likelihood that I get the exact nearest neighbor given a target point within the clouds bounding box? I know that it is dataset dependent... but does anyone have a good numerical study somewhere that shows trends?

# Answer
> 2 votes
nanoflann is a library for building KD-trees. For the best bin first (BBF) approximate nearest neighbor algorithm (which is based on KD-trees), the authors report the following performance results:

> In 12 dimensions, for example, BBF recovers the closest neighbor 94% of the time (versus 59% for restricted search) while on average examining only 200 of the 100,000 leaf nodes. For this same case, the “exact” search has to examine over 2400 leaves. \[Even\] when the method does not discover the exact nearest neighbor, it does not fail by much. Even up to dimension 20, the average distance of recovered neighbors is only 2% greater than the true NN distances.

However, that paper does not contain a formal analysis of the error bounds in this particular $\varepsilon$-approximation.

---
Tags: algorithms, algorithm-analysis, search-algorithms, approximation, heuristics
---


# Question
Title: Nondeterministic finite state machine without any initial state possible
Is it theoretically possible to have a nondeterministic finite state machine without any initial state or does it need at least one initial state?

# Answer
> 5 votes
In my favourite definition a finite state automaton is specified as 5-tuple $(Q,\Sigma,\delta,q\_0,F)$, where $Q$ is the finite set of states, $\Sigma$ is a (finite, nonempty) alphabet, $q\_0\in Q$ the initial state, $F\subseteq Q$ the set of final states, and $\delta\subseteq Q\times\Sigma\times Q$ the set of transitions. In that definition we would have exactly one initial state.

It is however very well possible that, for reasons of symmetry, one specifies a set $I\subseteq Q$ of initial states. There you can have one, several, of no initial state.

Short answer: consult the book, lecture notes, or scientific paper you are using. They set the rules for the game. Not us, not wikipedia.

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


title: Is np-complete an equivalence class?

text:
# Question
Title: Is np-complete an equivalence class?
So, there are multiple possible definitions of "np-complete", two of which being:

1. A decision problem $L$ is np-complete if and only if: $L \in \text{NP}$ and $\forall L' \in \text{NP}: L' \preceq\_{p} L$
2. A decision problem $L$ is np-complete if and only if: $L \in \text{NP}$ and there exists a np-complete problem $L \in \text{NP}$ such that: $L' \preceq\_{p} L$

My question is, why are those two definitions equivalent, or put differently, (why) is np-complete an equivalence class?

If it is an equivalence class I can understand equivalence of the above two definitions, but I fail to see why this is the case, since the (one-to-many) poly-time reduction $\preceq\_{p}$ is not symmetric... :-/

# Answer
The second definition isn't valid, since it's self-referential. Given the first definition, the second statement is an easy theorem that follows from the first definition.

Indeed, suppose we define NP-completeness using the first definition. Let's see that the second definition is true.

$\Longrightarrow$ If $L$ is NP-complete then for all $L'$ in NP, $L'$ reduces to $L$. In particular, SAT reduces to $L$. Since SAT is NP-complete by Cook's theorem, there exists an NP-complete problem $L'$ (namely SAT) that reduces to $L$.

$\Longleftarrow$ Suppose $L$ is in NP and some NP-complete problem $L'$ reduces to $L$. We will show that *every* problem $M$ in NP reduces to $L$, and so $L$ is NP-complete. Given a problem $M$ in NP, since $L'$ is NP-complete, $M$ reduces to $L'$. Since $L'$ reduces to $L$, $M$ also reduces to $L$, and we're done.

The proof used two properties: (1) there exists some NP-complete problem, (2) reducibility is transitive: if $A$ reduces to $B$ and $B$ reduces to $C$ then $A$ reduces to $C$.

Finally, any two NP-complete problems reduce to each other (via the definition), and in this sense they form an equivalence class of the reduction relation.
> 6 votes

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


# Question
Title: What is the difference between Transitive Closure and Join?
In database theory, there is a notion of transitive closure over relations. I am wondering if join operator over relations is also a special case of transitive closure?

# Answer
No, it is not. Transitive closure is the closure of composition on binary relations; composition can be expressed as a rename (to make join operate on the right attributes), followed by a join, followed by a project to remove the common attributes.

So *composition* can be expressed in terms of join, but (as Erwin Smout says) its *transitive closure* can *not*, and join (or composition) cannot be expressed in terms of transitive closure, either.
> 3 votes

# Answer
Imprecisely, Join is a bit like relational composition. Transitive closure is relational composition repeated 0 or more times.
> 2 votes

# Answer
Transitive closure of relations wasn't even part of Codd's algebra, while join indeed was, eurhm, sort of.

Transitive closure necessarily involves recursion, which takes its logical equivalent outside the realm of first-order predicate logic. That's why Codd's algebra was eventually demonstrated "expressively incomplete", why recursive querying was added so belatedly in the SQL standard, and why many courses even to this very day completely overlook the issue.

Join has none of that. Plus, transitive closure, eurhm, well, all versions I am personally aware of, operates on one single relation specifically. Join is not so constrained. Hence, there are joins that are not expressible as transitive closures, and join cannot possibly be a "special case" of TC.
> 2 votes

---
Tags: database-theory, databases
---


# Question
Title: Efficient algorithms for finding a region in $\mathbf R^2$
This question is an extension of a previous question I've asked.

Consider the rectangle $a\<x\<b , c\<y\<d$ in the $\mathbf R^2$ plane. Each point in this rectangle can be of kind #1 or #2 (We have to check each point to know its kind).

Assume that somehow we know that the points of kind 1 (and so the points of kind 2) form a connected region (i.e. , 1s and 2s are not scattered in the plane arbitrarily). Given the condition of being of kind 1 or 2, The goal is to find the region occupied by 1s (a *search* problem). Consider somehow we know the following attributes of the region occupied by 1s: (one at a time)

1. The region occupied by 1s forms a convex set (so it is 1-connected too).

2.The region occupied by 1s forms a simply connected region , but not necessarily convex.

The simplest algorithm for finding the region of 1s is to simply start from bottom of the rectangle and sweep it and check all of the points in the rectangle to determine their kind and this way find the region.This is not an efficient algorithm, because we can use the known fact of convexity (or simply-connectivity) of the region of 1s to find it more easily without inspecting all of the points.

What more efficient algorithms are there to find the region , as fast as possible? (with an acceptable accuracy, which is about 0.001 in my work). The regions may have sharp edges. But their detection is limited to the mentioned accuracy too. (It is clear that finding the boundary of the region suffices)

Please don't forget that the problem is *to find an unknown set of points*, not *bound a known set of points*. i.e., **it's a search problem , not a convex hull finding problem.**

**(also, speed is very important for me)**

**EDIT1:**

After some suggestions (in the comments) I should say that I think we can take advantage of simply-connectivity of the region to write an algorithm that tries to find the boundary of the region instead of checking more points to find the region directly.

# Answer
> 2 votes
Here's an idea that might be quick in practice. Judging from the OP's comments, this is idea is implementable.

The idea is that we start scanning from a corner and approach the center of the rectangle. Once the scan finds a vertex $v$ with label $1$, it halts. Start a DFS from $v$. Keep a stack $F$ that represents the frontier into which you can expand the search. A vertex is put into the stack if and only if it has at least one neighbor whose label is $0$. The idea is to complete a cycle, while staying on the boundary.

The figure above is a rough representation of the initial region of the green vertices labeled $1$. Say we start scanning from the upper right corner. The vertex $29$ is the one we hit, and the one from which we start a DFS.

The DFS was started from the purple vertex $29$. In the figure, $F$ would contain $9$ and $28$, because they are the only neighbors we can visit next that have at least one neighbor with the label $0$. The cycle is completed when we come back to $29$ or when the frontier meets.

---
Tags: algorithms, computational-geometry, search-problem
---


title: Decomposition of a relation to 3NF

text:
# Question
Title: Decomposition of a relation to 3NF
Given a relation $R(A, B, C, D, E, F)$, with the following functional dependencies: $\\{A \rightarrow BC, CD \rightarrow E, B \rightarrow D, E \rightarrow A\\}$.

The objective is to decompose $R$ into 3NF relations.

So far, I have determined that the following candidate keys are present in the given relation: $AF$, $EF$, $CDF$ and $BCF$.

Since every attribute is present as a part of some candidate key, for every $X \rightarrow A$, $A$ will be part of some candidate key, and so R itself should be in 3NF.

Since the question explicitly, however, states that it is not in 3NF, I have got a little confused. Where am I going wrong? Is there something that I have not understood?

# Answer
The original definition of 3NF was "flawed". Relvars such as yours could perfectly be in 3NF and still have undesirable redundancy.

And the flaw was exactly in cases when there was more than one candidate key.

Which was the very reason why BCNF was introduced, as a "fix" to the "flaw" that was discovered in \[the definition of\] 3NF.

The thing is, in cases of \>1 candidate key, we wouldn't even want designs such as yours to even satisfy 2NF. Both 2NF and 3NF can be violated only by nonprime attributes. That is the flaw in their definition. When the "fix" was applied to 3NF, superseding it with BCNF, the fix itself was flawed because actually what should have happened was to supersede the definition of 2NF with one that didn't limit itself to "nonprime" attributes".
> 2 votes

# Answer
As I am detouched from the subject for a long gap I have taken help from Wikipedia. A relational schema is in 3NF if for all of its FD X-\>A atleast one of the following holds 1) X contains A 2) X is a superkey 3) A-X is a prime attribute

For your problem any of the FD's are not being satisfied on point 1. For your problem we have not found any FD such that X is a superkey. Your superkey is AF,EF,CDF etc.. and A-X is giving you the empty set for all of FD's

So none of the conditions are satisfied. So it is not in 3NF
> 0 votes

---
Tags: database-theory
---


# Question
Title: Does the 'difference' operation add expressiveness to a query language that already includes 'join'?
The set difference operator (e.g., `EXCEPT` in some SQL variants) is one of the many fundamental operators of relational algebra. However, there are some databases that do not support the set difference operator directly, but which support `LEFT JOIN` (a kind of outer join), and in practice this can be used instead of a set difference operation to achieve the same effect.

Does this mean that the expressive power of a query language is the same even without the set difference operator, so long as the `LEFT JOIN` operator is maintained? How would one prove this fact?

# Answer
> 14 votes
In relational algebra, we shall first provide an informal definition of left (outer) join, and proceed to prove that it, renaming, selection, join and projection can construct difference, as well as that difference, selection and union can be used to construct left (outer) join. Actually, we'll end up doing it in the reverse order: we'll show how to construct left joins using differences, and then we'll show how to construct differences using left joins.

Let $R$ and $S$ have schemata $(R', T)$ and $(T, S')$, respectively, where $R'$ and $S'$ are the sets of attributes in one schema but not the other, and $T$ is the set of common attributes.

Let $w = (\epsilon, \epsilon, ..., \epsilon)$ be the null tuple for schema $S'$. That is, it is the tuple consisting of all null values for each attribute of $S'$. Then, we define left outer join as follows: `R LEFT JOIN S` is the set of all tuples $(r, t, s)$ belonging to schema $(R', T, S')$ where...

1. $(r, t)$ is a tuple in $R$;
2. (a) $(t, s)$ is a tuple of $S$ or (b) $s = w$;
3. If $(r, t, s)$ is in the set for $s \neq w$, then $(r, t, w)$ is not in the set.

Example: $R$'s schema is $(A\_{1}, A\_{2}, A\_{3})$, $S$'s schema is $(A\_{2}, A\_{3}, A\_{4})$, and we have that $R = \\{(1, 2, 3), (4, 5, 6)\\}$ and $S = \\{(2, 3, 4), (2, 3, 6)\\}$. By (1) and (2) we get the intermediate result $\\{(1, 2, 3, 4),(1, 2, 3, 6), (1, 2, 3, \epsilon),(4, 5, 6, \epsilon)\\}$. By (3) we must remove $(1, 2, 3, \epsilon)$, since we have (for instance) $(1, 2, 3, 4)$ and $s = 4 \neq \epsilon = w$. We are thus left with $\\{(1, 2, 3, 4), (1, 2, 3, 6), (4, 5, 6, \epsilon)\\}$, the expected result for a left join.

Theorem: `R LEFT JOIN S` is equivalent to `(R EQUIJOIN S) UNION ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)`.

Proof: `(R EQUIJOIN S)` gives us everything required by (1) and (2a). We claim that `((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)` gives us everything of the form `(r, t, w)` required by (2b) and (3).

To see this, first notice that `(((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R)` is the set of all tuples in $R$ for which there is no corresponding tuple in $S$. To see that, it suffices to note that by projecting the common attributes out of $R$ and $S$ (the attribute set $T$) and taking the difference, one is left with all and only those tuples (with schema $T$) which are represented in $R$ but not $S$. By the `EQUIJOIN` with $R$, we recover all and only those tuples in $R$ which have values for attributes in $T$ which are present in $R$ but not in $S$; namely, precisely the set of tuples we have so far claimed.

Next, notice that the schema of `(((PROJECT_T R) DIFFERENCE (PROJECT_T S))` is the same as that of $R$ (namely, $(R', T)$), while the schema of $w$ is $S'$. The `JOIN` operation is therefore a Cartesian product, we we get all tuples of the form $(r, t, w)$ where there is no $(t, s)$ in $S$ corresponding to $(r, t)$ in $R$.

To see that this is precisely the set of tuples we needed to add to `R EQUIJOIN S` in order to construct `R LEFT JOIN S`, consider the following: by construction, (3) is satisfied, since `R EQUIJOIN S` cannot contain $(r, t, s)$ if `((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)` contains $(r, t, w)$ (if it did, then the second part's containing $(r, t, w)$ would be a contradiction); if we were to add another $(r, t, w)$ not in `((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)`, then there would be a $(t, s)$ in $S$ corresponding to $(r, t)$ in $R$, and by the definition of `EQUIJOIN`, $(r, t, s)$ would also be in `R LEFT JOIN S`, a contradiction of (3). This completes the proof.

Now we show that left join can be used to construct difference:

Theorem: `R DIFFERENCE S` is equivalent to `PROJECT_T(SELECT_{t'=w}(R LEFT JOIN (SELECT_{s=s'}(((S JOIN RENAME_{T->T'}(S)))))))`

Proof: Notice that here, $R'$ and $S'$ are empty, since all attributes are shared for `DIFFERENCE` to make sense. First, we create a new relation from $S$ by duplicating the attribute set in $S$ (handled by `RENAME` and `JOIN`) so that it consists of tuples $(t, t')$ on attribute set $(T, T')$ where $t = t'$ (handled by the `SELECT`). The left join leaves us with tuples of the form $(t, t')$ where $t=t'$ or $t'=w$. Now, to get rid of entries which do also appear in $S$, we must keep only the tuples of the form $(t, w)$, which is handled by the outermost `SELECT`. The last `PROJECT` gets rid of the temporary attribute set $T'$ and leaves us with the difference in terms of the original schema.

Example: Let $R = \\{(1, 2), (3, 4), (5, 6)\\}$ and $S = \\{(3, 4), (5, 6), (7, 8)\\}$. We first get $S$ with the `RENAME`d attribute set $T'$: $\\{(3, 4), (5, 6), (7, 8)\\}$. The `JOIN` operation gives us the Cartesian product with all nine possible pairings; this set is not written here for reasons of formatting. The `SELECT` then pares this down to $\\{(3, 4, 3, 4), (5, 6, 5, 6), (7, 8, 7, 8)\\}$. The `LEFT JOIN` with $R$ gives $\\{(1, 2, \epsilon, \epsilon), (3, 4, 3, 4), (5, 6, 5, 6)\\}$. The `SELECT` gives $\\{(1, 2, \epsilon, \epsilon)\\}$. The `PROJECT` gives $\\{(1, 2)\\}$, the desired answer.

# Answer
> 0 votes
LEFT JOIN as implemented by SQL, does not produce relations as its result (because some attributes of the result will not have a value).

Ergo, LEFT JOIN as implemented by SQL, is not a direct counterpart of any relational algebra operator.

Ergo, The **relational** difference operator cannot be expressed in terms of LEFT JOIN (because LEFT JOIN cannot possibly be part of the relational algebra, this being because LEFT JOIN produces something that is not a relation, thus violating closure of the algebra).

Any set of primitive operators of a **relational** algebra **that satisfies closure** that I know of, always includes either relational difference or else relational semidifference.

---
Tags: database-theory, relational-algebra, finite-model-theory
---


# Question
Title: Is it impossible to truly emulate a system if its actual clock speed is the same?
As I understand emulation a rule of the thumb says that a computer must be around a order of magnitude more powerful to emulate another system without resorting to tricks. This is because for every clock cycle of the system to be emulated, the host machine must process that cycle in the correct time and also process its own cycles.

A Xbox 360 uses a `3.2GHz PowerPC Tri-Core Xenon` processor, would this mean that emulating the console on a 3GHz PC CPU would be impossible, even if the host CPU was more powerful but not faster for clock cycles?

To give a more straightforward example. A i7 that runs at the same clock speed as a Pentium 4 will not be able to emulate the Pentium 4, even though the i7 is many times more powerful.

In addition, does this mean that to emulate the Xbox 360, The host computer must run at a speed of between 9GHz and 3.2GHz to be able to truly emulate a Xbox 360?

If this is the case, surely there must be a way around this limitation? If we had a host computer with 10x3GHz CPU's could this system use parallelzation to somehow emulate a 3 core 3.2GHz system.

Also the emulate should run at the speed that the user expected of the emulated system, I know if you slowed down the Xbox 360 on the emulator by a few times then it would be easier, I want to know if we can emulate a system at the speed it was meant to run.

If this is not possible does that mean that for emulation, clock speed is king? And there is no way around this? Even if your host machine had a thousand CPU's running at 2GHz it could never ever emulate a Xbox 360 at its native speed?

By the way I am sure this is in the domain of computer science. I am not sure exactly what it comes under but the simulation of a system within a system and inherent limitations is certainly applicable to computer science.

What about this: could a 4 core 3GHz i7 CPU emulate in proper time a 3.8GHz single core Pentium 4?

# Answer
> 9 votes
That very much depends on how well the instruction set of the CPU to be emulated maps to the instruction set of the emulating CPU. Certainly, clock speed is not the deciding factor. It might very well be that a slower (clock wise) CPU A can emulate a faster CPU B.

This can be both because of more powerful instructions (e.g. SSE instructions that allow doing the same operation to multiple values at once), or improvements in instruction level parallelism (e.g. more adders, multipliers etc. so that more instructions can be executed simultaniously, smarter recognition of independent instructions). There are also strong contributions from larger caches and smarter branch prediction. All these factors (and probably many more that I don't know about) can be improved to increase the average number of instructions executed without changing the clock speed. Since clock-speed increases stalled some years ago, this kind of improvement has been a major contributor to performance increases in CPUs.

Of course it also strongly depends on the skill of the person writing the emulator. There will always be some overhead involved in translating the instructions for CPU B to instructions that work on A. The larger the difference between the two CPUs, the larger the overhead.

---
Tags: simulation
---


# Question
Title: Is there an algorithm to find the best strategy for a game?
Let,

* `game` be the state of a 2-player, turn based game
* `actions game player -> [move]` be a function that gets the state of a game and returns all valid moves, where a move if a function `move game -> game` that updates the state of the game
* `state game -> state` returns wether a game is `incomplete`, `won by player1` or `won by player 2`

Countless games such as chess and tic-tac toe can be described this ways. Is there an algorithm that, given such description, returns the optimal strategy, where `strategy` takes the game state as input and returns the optimal move for that turn?

# Answer
> 4 votes
Your notion of "strategy" is very ill defined. Exactly what kind of object do you want this algorithm to return? Do you want it to return another algorithm?

There is an algorithm which takes a current board state and returns the optimal move. It's called Mini-Max, you can read about it here. It basically is a depth-first search for a move that doesn't allow for a losing situation. It's called minimax because it alternates for one player minimizing the benefit for player 1 (i.e. player 2) and the other player maximizing the benefit for player 1 (i.e. player 1).

There are techniques, such as Alpha-Beta pruning, which make Minimax faster, however, it is still painfully slow. For Tic-Tac-Toe, it works. For chess, a complete run is completely infeasible. In practice, instead of doing a full search, the search is done to a specific level, and then heuristics are used to evaluate which game states are the most favorable.

So, technically, an algorithm which always returned minimax would fulfill your requirement for a strategy: you could give it a game state and it would output the possible move. However, this is far beyond the capabilities that computers will ever have: expanding the full minimax tree would probably take more memory than there are atoms in the universe.

# Answer
> 3 votes
If we consider finite deterministic games, then there is always an algorithm that calculates if one of the two players have a winning strategy or one of the two players can force a draw (just make a full search on the game space) ... the problem (as noted by jmite) is that it requires too much time and space :-)

But if we consider games that are "unlimited" (in some way), then there are two-person win-lose games (rather artificial) with decidable rules but no computable winning strategies.

A classical example is the following: given a computable function $f: \mathbb{N}^{m} \to \\{A,B\\}$, the two players alternately choose a natural number $x\_i$ (player A begins). The games ends after $m$ turns (suppose that $x\_1, x\_2, ..., x\_{m}$ are the picked numbers); the winner is player $A$ if and only if $f(x\_1, x\_2, ..., x\_{m}) = A$. For this game, given $m$ and $f$, there is no algorithm that can tell you if A (or B) has a winning strategy. Rabin \[Rab57\] proposed a similar simple *three moves game* (m = 3) for which player B has a winning strategy, but it is not computable.

A still open problem (as far as I know it is still open :-) is a chess game played on an infinite board:

> Given a finite set of chess pieces and their position on an infinite bidimensional $\mathbb{Z} \times \mathbb{Z}$ board, is there a winning strategy for white?

For other references see: J. P. Jones, Some undecidable determined game

(I'm not an expert, and I would like to know if there are more natural undecidable games)

\[Rab57\] Michael O. Rabin, Effective computability of winning strategies, Contributions to the theory of games, vol. 3, Annals of Mathematics Studies, no. 39, Princeton University Press, Princeton, N. J., 1957, pp. 147-157.

# Answer
> 1 votes
If you are referring to a generalization of games, you should have a look at General Game Playing.

As an alternative to traditional, search-based methods such as minimax/alpha-beta, there is also a simulation-based method called monte carlo tree search..

---
Tags: algorithms, artificial-intelligence
---


# Question
Title: Multiplying intervals in Two's complement
I want to perform some interval-operations, and for addition, subtraction, and logic-/shift-operators, that works very well.

The only problem I have is the multiplication.

An interval $\[a, b\]$ denotes all two's complement numbers $x$ with the property $a \leq x \leq b$.

An interval-operation means that if i have a binary operation $\circ$ and two intervals $\[a, b\]$ and $\[c, d\]$, then $\[a, b\] \circ \[c, d\] = \[e, f\]$ means that for for an arbitrary $x \in \[a, b\]$ and $y \in \[c, d\]$: $$x \circ y \in \[e, f\].$$

But additionally, I want to have the most precise or a very precise interval.

"The most precise" means that there are the values $w,x \in \[a, b\]$ and $y,z \in \[c, d\]$ for which holds that $w \circ y = e$ and $x \circ z = f$

An example of an interval-operation:

* $A = \[7,14\]$
* $B = \[-6, 77\]$
* $A + B = \[1, 91\]$

It's correct, because there is no value outside of $\[1, 91\]$ that can be reached, when adding numbers out of $A$ and $B$.

Also it's precise, because $7+(-6) = 1$ and $14+77 = 91$

It seems impossible to find an efficient algorithm that handles all the overflows correctly and finds the precise (or at least a good) interval.

Is there a good algorithm?

# Answer
If $0 \leq a,b,c,d$ then $\[a,b\] \[c,d\] = \[ac,bd\]$. The trouble begins when numbers can be negative. If $a,b\<0$ then $\[a,0\]\[b,0\]=\[0,ab\]$. If $a\<0\<b$ then $\[a,0\]\[0,b\] = \[ab,0\]$. And so on. To consider intervals straddling $0$, partition them into their positive and negative parts.

Summarizing, I wouldn't say that it is "impossible" to find an algorithm for multiplying intervals, only that you have to consider numerous cases. Good luck.
> 1 votes

---
Tags: binary-arithmetic, arithmetic, intervals
---


# Question
Title: Paper with proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ is not Deterministic Context Free?
These lecture slides sketch a proof that $L=\\{ a^n b^n \mid n \geq 0 \\} \cup \\{ a^n b^{2n} \mid n \geq 0 \\}$ cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give no references as to where the proof comes from.

I was wondering, does anybody know of an academic paper or textbook that gives a full proof? I'd love to be able to cite it, but I haven't been able to find one.

# Answer
> 6 votes
The result is proved in Ginsburg and Greibach, *Deterministic context free languages*, Inform. Control 9(6), 620–648, 1966, Theorem 4.1 on page 24 (643). However, the proof looks somewhat different.

---
Tags: formal-languages, reference-request, automata, pushdown-automata, nondeterminism
---


title: Is constant a variable or subtype?

text:
# Question
Title: Is constant a variable or subtype?
I think of type as a range of values that the variable can take whereas the rest is known constant or does not matter. Variables (instances or objects), which share common properties, are considered to belong to the same type/kind/class. That is, the type properties are constant across the type. The type is actually a common property of a class of objects (variables). The variables have a variable part, which may change, making them flipping from one subtype to the other. However, the same applies to subtypes: subtypes also share a common constant property.

I may describe a class by a circle in Vienn Diagramm. Its subspheres would be types or variables. I think that the variable means that it has some fixed part, its type, and variable part, which make it variable and not constant. The constants or values would be an elementary point in the diagramm.

For instance, integer is a subtype of real. Integer variable means that it can take concrete values within the range of the integer area. Similarly, boolean variables, taking only values 0 and 1, are subtype of integer. But, what is a constant 1? Is it a real or integer or boolean variable or it is a specific type, instances of which have a common property: they have a value of 1? Is it a known treatment?

My interest stems from the practice: how can I save memory fixing the common part of variables in a language processing framework?

# Answer
This seems very confused. Probably you should state which programming language you are referring to as some of these concepts may have different definitions depending on the language or formalism. Much is arbitrary (possibly not always too consistent). For example, you do not necessarily have booleans as a subtype of integers.

One important issue is to distinguish syntax (what you write to talk about entities) from semantics (the actual entities you wish to talk about). In a simple world, a type may be understood as a set of values that the language can manipulate through specific representations. A constant is a representation of a specific value. In many languages, a constant is a name that is given to a specific value in a given context. A variable is a place holder for a value, that may change. Now this is to be interpreted a bit differently depending on the type of programming langusge, notably imperative of functional (there are other kinds).

Things get more complicated when you start aggregating values in various ways, because some language will let you consider aggregates where some components may change.

You should probably go back to a textbook on programming languages.

**P.S.** I agree that considering types as sets of values is too simplistic. But I am trying here to make as simple an answer as I can. This is precisely why considering `boolean` as a subtype of `integer` may not always be a good idea, or may not be as simple as it may seem.
> 2 votes

---
Tags: type-theory, type-inference, inductive-datatypes
---


# Question
Title: Do subqueries add expressive power to SQL queries?
Does SQL need subqueries?

Imagine a sufficiently generalized implementation of the structured query language for relation databases. Since the structure of the canonical SQL `SELECT` statement is actually pretty important for this to make sense, I don't appeal directly to relational algebra, but you could frame this in those terms by making appropriate restrictions on the form of expressions.

An SQL `SELECT` query generally consists of a projection (the `SELECT` part) some number of `JOIN` operations (the `JOIN` part), some number of `SELECTION` operations (in SQL, the `WHERE` clauses), and then set-wise operations (`UNION`, `EXCEPT`, `INTERSECT`, etc.), followed by another SQL `SELECT` query.

Tables being joined can be the computed results of expressions; in other words, we can have a statement such as:

```
SELECT t1.name, t2.address
  FROM table1 AS t1
  JOIN (SELECT id, address
          FROM table2 AS t3
         WHERE t3.id = t1.id) AS t2
 WHERE t1.salary > 50,000;

```

We will refer to the use of a computed table as part of an SQL query as a subquery. In the example above, the second (indented) `SELECT` is a subquery.

Can all SQL queries be written in such a way as to not use subqueries? The example above can:

```
SELECT t1.name, t2.address
  FROM table1 AS t1
  JOIN table2 AS t2
    ON t1.id = t2.id
 WHERE t1.salary > 50,000;

```

This example is somewhat spurious, or trivial, but one can imagine instances where considerably more effort might be required to recover an equivalent expression. In other words, is it the case that for every SQL query $q$ with subqueries, there exists a query $q'$ without subqueries such that $q$ and $q'$ are guaranteed to produce the same results for the same underlying tables? Let us limit SQL queries to the following form:

```
SELECT <attribute>,
      ...,
      <attribute>
 FROM <a table, not a subquery>
 JOIN <a table, not a subquery>
  ...
 JOIN <a table, not a subquery>
WHERE <condition>
  AND <condition>
  ...
  AND <condition>

UNION
 -or-
EXCEPT
 -or-
<similar>

SELECT ...

```

And so on. I think left and right outer joins don't add much, but if I am mistaken, please feel free to point that out... in any event, they are fair game as well. As far as set operations go, I guess any of them are fine... union, difference, symmetric difference, intersection, etc... anything that is helpful. Are there any known forms to which all SQL queries can be reduced? Do any of these eliminate subqueries? Or are there some instances where no equivalent, subquery-free query exists? References are appreciated... or a demonstration (by proof) that they are or aren't required would be fantastic. Thanks, and sorry if this is a celebrated (or trivial) result of which I am painfully ignorant.

# Answer
> 9 votes
There is some terminology confusion; the query block within parenthesis

```
SELECT t1.name, t2.address
  FROM table1
  JOIN (SELECT id, address
          FROM table2 AS t3
         WHERE t3.id = t1.id)

```

is called *inner view*. A *subquery* is query block within either WHERE or SELECT clause, e.g.

```
select deptno from dept
where 3 < (select count(1) from emp
           where dept.deptno=emp.deptno)

```

In either case, inner view or subquery can be unnested into "flat" project-restrict-join. Correlated subquery with aggregation unnests into inner views with grouping, which then unnests into flat query.

```
select deptno from dept d
    where 3 < (select avg(sal) from emp e
               where d.deptno=e.deptno)

select d.deptno from dept d, (
    select deptno from emp e
    group by deptno
    having avg(sal) > 3
) where d.deptno=e.deptno

select d.deptno from dept d, emp e
where d.deptno=e.deptno
group by d.deptno
having avg(sal) > 3

```

As for algebraic rules for query optimization, relational algebra is known to be axiomatized into Relational Lattice which simplifies query transformations as demonstrated here and there.

# Answer
> 16 votes
To translate your statement into the relational algebra, I think it asks:

> Can we rewrite $\sigma\_A(A)\bowtie \sigma\_B(B)$ as $\sigma\_A(\sigma\_B(A\bowtie B))$?

(Where $\sigma$ is select and $\bowtie$ is join.)

The answer is "Yes," and it's a standard query optimization. To be honest, I'm not sure how to prove this in a non-question-begging manner - it's just a property of selection and join. You can argue inductively to add however many layers of nested queries you want.

Additionally, you might ask:

> Can every sequence of joins be written as $A\bowtie B\bowtie C\bowtie\dots$ \[As opposed to, say, $(A\bowtie B)\bowtie(C\bowtie D)$\]?

Again the answer is yes, because join is associative. Similar statements can be made about projection as well.

One notable type of "subquery" which I think cannot be "flattened out" is `with`. One way to see this is to note that if you have a `with` statement then you can have a recursive function, which cannot be written without using subqueries.

So to sum up: in the specific case you mentioned, no, SQL does not need subqueries, and you can prove it inductively. In general though, there are features which require subqueries.

# Answer
> 1 votes
"Do subqueries add expressive power to SQL queries?"

They did, at least before the introduction of EXCEPT in the SQL language.

Prior to the introduction of EXCEPT, there was no way what so ever to express a relational difference or semidifference in SQL without resorting to subqueries.

These days, all of the "typical" primitive operators of "the" relational algebra can be expressed without subqueries :

NATURAL JOIN can be done through NATURAL JOIN, or JOIN ON
UNION can be done through UNION
MINUS can be done through EXCEPT
PROJECT/RENAME/EXTEND can be done throug SELECT
RESTRICT can be done through WHERE
relational literals can be done through VALUES
transitive closures can be done through recursive WITH

---
Tags: database-theory, relational-algebra
---


# Question
Title: "At least one" clause in Relational Algebra
I'm fairly new to the syntax of relational algebra, and I'm having a hard time understanding how I could set a "at least one" clause.

Example: I have:

* a table with books (listing the title, year published and ID),
* a table with authors (listing their name and ID),
* a table which lists what author wrote what book (through a tuple of the IDs mentioned before).

How could I, in relational algebra, get "All the authors that have published at least one book per year between 2008 and 2010"?

I have figured this so far. At step "b", the Natural join is used since both tables have PublicationID in common. Thus, the resulting table is |PublicationID|AuthorID|Year|. So I'm simply missing the step "c", where I don't understand how to gather a sub-set of the authors that published at least one book per year between 2008 and 2010.

$ a \leftarrow \pi\_{PublicationID,Year} (Publication)$

$ b \leftarrow a \bowtie AuthorPublication $

$ c \leftarrow \sigma\_{something} $

# Answer
A first hint toward a solution is to think about "what's the result of a *natural* join between $Author$, $Publication$ and $AuthorPublication$?" The answer is "the universal relation" $R(BookID,AuthorID,Title,Year,Name)$ describing who wrote a book and when. Note that a book without any author or an author without any book written won't appear in $R$. So an author in $R$ as written at least one book. The following query gives the authors who wrote at least a book in year 2008: $$ \pi\_{Name}(Author \Join AuthorPublication \Join \sigma\_{(2008 = year)}(Publication))$$

For the final answer, compute the intersection of this query with its variants: $$ \pi\_{Name}(Author \Join AuthorPublication \Join \sigma\_{(2008 = year)}(Publication)) \cap \pi\_{Name}(Author \Join AuthorPublication \Join \sigma\_{(2009 = year)}(Publication)) \cap \pi\_{Name}(Author \Join AuthorPublication \Join \sigma\_{(2010 = year)}(Publication))$$

You may provide other equivalent answers with outer $Author \Join$.
> 1 votes

# Answer
**This is an answer by the OP, which is removed from the question.**

*A friend gave me a tip and a possible solution appeared:*

For Author(Name,AuthorID) | Publication(Title,Year,BookID) | AuthorPublication(BookID,AuthorID)

$ RenamedAP = \alpha\_{(AuthorID:linkAuthorID, PublicationID:linkPubID)} (AuthorPublication) $

$Mix \leftarrow RenamedAP \times Author \times Publication $

$Mix2 \leftarrow \sigma\_{(AuthorID=linkAuthorID \wedge PublicationID = linkPubID)} (Mix) $

$ Y2008 \leftarrow \sigma\_{(Year=2008)} (Mix2)$

$ Y2009 \leftarrow \sigma\_{(Year=2009)} (Mix2)$

$Y2010 \leftarrow \sigma\_{(Year=2010)} (Mix2) $

$ Subresult \leftarrow Y2008 \cap Y2009 \cap Y2010 $

$ Result \leftarrow \pi\_{Name} (Subresult) $ \
> 0 votes

---
Tags: database-theory, databases, relational-algebra
---


title: Can a perceptron forget?

text:
# Question
Title: Can a perceptron forget?
I would like to build an online web-based machine learning system, where users can continuously add classified samples, and have the model updated online. I would like to use a perceptron or a similar online-learning algorithm.

But, users may make mistakes and insert irrelevant examples. In that case, I would like to have the option to delete a specific example, without re-training the perceptron on the entire set of examples (which may be very large).

Is this possible?

# Answer
As I understand the process, altering a perceptron without retraining is impossible. The weight adjustments are not only relative to that specific example but also relative to the other training examples that have gone before. Identifying the incorrectly classified instance and removing it from the test set before retraining the model would seem to be the most effective way of correcting the weights.

I think it's worth pointing out that in comparison to other machine learning algorithms, perceptrons are relatively resistent to noise and incorrectly classified instances in the training set. If you're encountering a large number of misclassified instances, it would seem more prudent to have better validation at the point you ingest the data prior to training than to come up with some way to correct for misclassified instances after the perceptron has been trained. If that's not possible and you're able to identify the incorrectly classified instances as such, then removing them and retraining would seem the only way to effectively remove the impact of the misclassified instances.
> 6 votes

---
Tags: machine-learning, online-algorithms
---


# Question
Title: Elegant approach to finding largest $n$ such that $n\lg(n) \leq 10^6$
I'm studying CLRS, and solving problems listed after each chapter. I'm curious about problem 1-1. That is right after Chapter 1.

The question is, what is the best way to find the largest integer $n$ such that $n \lg(n) \leq 10^6$.

The simplest but the longest one is substitution. Are there some elegant ways to solve this?

Some explanations: $n$ is what I should calculate - total quantity of input elements, $10^6$ - time in microseconds - total algorithm running time. I should figure out $n\_{\text{max}}$.

# Answer
We just solve $x \log x = 10^6$ and round down. This sort of equation typically does not have a closed form solution (so what, closed form solutions are so 18th century, we've got computers now), so we just feed this into a computer and we get $n \approx 87847.5$, so the answer is 87847.

You did ask for the most elegant approach, you know, and that would be to use the right tool.

Now, you could also wonder how you would compute this by hand if you found yourself in the middle of a jungle. You could use the iteration method (is this what you called substitution?). Write the equation in the form of a fixed point: $$x = \frac{10^6}{\log x}$$ Start with any initial guess for $x$ and keep applying the right-hand side. With some luck, you converge. You find a python in the jungle and make it compute:

```
>>> import math
>>> x = 42
>>> for i in range(20):
...    print x
...    x = 1000000.0/math.log(x)
...
42
267546.386419
80018.8957423
88573.8173924
87784.0460781
87853.1196966
87847.0493964
87847.5826391
87847.5357949
87847.5399101
87847.5395486
87847.5395803
87847.5395775
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778

```

That was kind of slow. A better method would be Newton's method. We are looking for the root of $f(x) = x \log x - 10^6$. The derivative is $f'(x) = 1 + \log x$ so the Newton's method step is $$x\_{n+1} = x\_n - \frac{f(x\_n)}{f'(x\_n)} = x\_n - \frac{x\_n \log x\_n - 10^6}{1 + \log x\_n}.$$ So now we get:

```
>>> x = 42
>>> for i in range(10):
...     print (x)
...     x = x - (x * math.log(x) - 1000000.0)/(1 + math.log(x))
...
42
211083.102152
91333.5177989
87852.9643949
87847.5395913
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778

```

Much better.
> 7 votes

# Answer
This to me looks like a case for good old-fashined binary search.

Notice that $n\log n$ is strictly increasing as $n$ increases. So if you try an $m$ and find that $m\log m \leq 10^6$, then you know $n \geq m$. Likewise, if $m \log m \> 10^6$, then $n \< m$.

You can do this to keep cutting your search space in half. Your starting lower bound is $0$, and your starting upper bound is $10^6$, since $10^6 \cdot \log (10^6) \> 10^6$.

You try $m$ as $start +\frac{start-end}{2}$ each time. If $m\log m \leq 10^6$, then your lower bound is $m$, and if it is greater, your upper bound changes to $m$. You repeat until you have narrowed it down to a single solution, remembering that your lower bound is an inclusive lower bound.

This runs in $O(\log k)$ time for an interval of width $k$, so for $k = 10^6$, it should run decently fast.
> 3 votes

# Answer
Practically speaking, if $n\log n = x$, then $n \approx x/\log x$. This won't give you the optimal $n$, but for large $x$ it's a pretty good approximation since $$ \frac{x}{\log x} \log \frac{x}{\log x} = \frac{x}{\log x} (\log x - \log\log x) = x \left(1 - \frac{\log\log x}{\log x}\right).$$
> 2 votes

# Answer
In the edition I have, $\lg n$ means $\log\_2 n$, so I suspect the authors had in mind something like the following:

Since $10^6 \lesssim 2^{20} = 16.2^{16}$, one needs $n$ to be a little bit less than $65536$, and is somewhat larger than $32768$. A quick binary search then yields $n\_\text{max} = 62746$. This can be calculated quickly even with just the simple calculator app that comes with most operating systems, by computing $n \log n/\log 2$ for a few values of $n$.

(This is essentially the same answer given by Michael C. Grant at \[math.se\], where the version of the question also confirms that $\lg n = \log\_2 n$ is intended.)
> 2 votes

---
Tags: algorithms
---


# Question
Title: Exponential reduction vs Polynomial Reduction
I'm having trouble understanding reduction. Lets say you have a decision problem A that is NP-Complete. Also, another problem B the can be reduced from A.

What can you say about B if:

1) The reduction is done in polynomial time
2) The reduction is done in exponential time

I know that if A is reduced to B means that if we knew how to solve B, then solving A would be easy. But I don't understand what 1 & 2 signify.

Would it be right to say that for 1)
B is in the same Class as A

And for 2)
That B \> then NP-Complete?

# Answer
> 2 votes
In fact, depending on the class you want to reduce to, you need to be careful about the reduction you are doing.

For instance to preserve the class $P$, you need to do $LOGSPACE$-reductions. For the class $NP$, you need $P$-reductions.

I'm also afraid that you reverse the reductions: to show that a problem $B$ is in $NP$, you need to reduce it (polynomially) to a problem $A$ in $NP$. Meaning that if you to how to solve $A$ in $NP$, then you can solve $B$ by reducing it to $A$.

So to sum up, if $B\leq\_P A$ and $A\in NP$, then $B\in NP$. Indeed the NP algorithm is clear: perform your reduction (polynomial time) and then solve the instance of $A$ you reduced to (in $NP$).

However, if the reduction is exponential, then we cannot say anything about $B$, except that it is in $EXPTIME^{NP}$, i.e. you can solve it in exponential time with an $NP$ oracle. It is in fact the same that just saying $B\in EXPTIME$, since the NP oracle does not add power.

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


# Question
Title: Hanoi tower with forbidden direct move from source to destination
I want to know what is algorithm and time complexity of Hanoi tower with forbidden direct move from source to destination (*it means you cannot move disk from source to destination directly and you instead of that should first move disk from source to middle and then from middle to destination*) and other rules as normal problem?

I didn't find any article about it.

# Answer
> 2 votes
**Notation**
Let's denote least number of moves needed to move $n$ disks from column $i$ to column $j$ with $T\_{ij}$. Let $A$ be the source and $C$ be the destination column.

**Recurrence relations**
We can say the followings about each $T$: \begin{equation} T\_{AC}(n)=T\_{AC}(n-1)+1+T\_{CA}(n)+1+T\_{AC}(n-1) \end{equation} To move $n$ disks from source to destination, we first have to move the top $n-1$ disks to column $C$ and then move the last one to Column $B$, Then return the $n-1$ disks to $A$ so as to free up destination column, then move the biggest disk to $C$ and once again move the $n-1$ disks to $C$. It's easy to see that this is the optimal set of operations. This equation can be written as: \begin{equation} T\_{AC}(n)=2T\_{AC}(n-1)+2+T\_{CA}(n-1) \end{equation}

For other $T$s we have a different situation: \begin{equation} T\_{CA}(n)=T\_{CB}(n-1)+1+T\_{BA}(n-1)\\ T\_{CB}(n)=T\_{CA}(n-1)+1+T\_{AB}(n-1)\\ T\_{BA}(n)=T\_{BC}(n-1)+1+T\_{CA}(n-1)\\ T\_{AB}(n)=T\_{AC}(n-1)+1+T\_{CB}(n-1)\\ T\_{BC}(n)=T\_{BA}(n-1)+1+T\_{AC}(n-1) \end{equation}

**Solving the system of recurrence relations**
Let's start with $T\_{AB}$ or $T\_{BC}$ . We already know: \begin{equation} T\_{AB}(n)=T\_{AC}(n-1)+1+T\_{CB}(n-1) \end{equation} We try to rewrite $T\_{CB}$'s equation by replacing $T\_{AB}$ from the above equation. \begin{align} T\_{CB}(n)&=T\_{CA}(n-1)+1+(T\_{AC}(n-2)+1+T\_{CB}(n-2))\\ &=T\_{CA}(n-1)+T\_{AC}(n-2)+T\_{CB}(n-2)+2 \end{align} \begin{equation} T\_{CB}(n)-T\_{CB}(n-2)=T\_{CA}(n-1)+T\_{AC}(n-2)+2 \end{equation}

By the same method we get: \begin{equation} T\_{BA}(n)=T\_{CA}(n-1)+T\_{AC}(n-2)+T\_{BA}(n-2)+2 \end{equation}

It can immediately be seen that $T\_{BA}(n)=T\_{CB}(n)$. Then we rewrite $T\_{CA}$ as: \begin{equation} T\_{CA}(n)=2T\_{CB}(n-1)+1 \Rightarrow \end{equation} \begin{align} T\_{CA}(n)-T\_{CA}(n-2)&=2(T\_{CB}(n-1)-T\_{CB}(n-3))\\ &=2(T\_{CA}(n-2)+T\_{AC}(n-3)+2)\\ &=2T\_{CA}(n-2)+2T\_{AC}(n-3)+4 \end{align}

Now let's go back to the main relation, to $T\_{AC}$: \begin{equation} T\_{AC}(n)=2T\_{AC}(n-1)+2+T\_{AC}(n-1) \Rightarrow\\ \end{equation} \begin{align} &T\_{AC}(n)-3T\_{AC}(n-2)\\ =&2(T\_{AC}(n-1)-3T\_{AC}(n-3))+(T\_{CA}(n-1)-3T\_{CA}(n-3))=\\ =&2(T\_{AC}(n-1)-3T\_{AC}(n-3))+(2T\_{AC}(n-4)+4)\\ =&2T\_{AC}(n-1)-6T\_{AC}(n-3)+2T\_{AC}(n-4)+4 \Rightarrow \end{align} \begin{equation} T\_{AC}(n)=2T\_{AC}(n-1)+3T\_{AC}(n-2)-6T\_{AC}(n-3)+2T\_{AC}(n-4)+4 \end{equation}

There! We have reduced the system of recurrence relations to a single relation, involving only the target series. Ok, the rest is easy from here on. I leave it as an exercise to the reader! $\ddot\smile$

---
Tags: algorithms, recurrence-relation, board-games
---


# Question
Title: Is $L = \{a^jb^ia^{j-i}\mid i,j \ge 0\ , j > i\}$ context-free?
I'm exercising for an upcoming exam and I find this exercise:

> Say whether or not the language $$L = \\{a^jb^ia^{j-i}\mid i,j \ge 0\ , j \> i\\}$$ is a context-free language. Justify your answer.

I have already tried (using the pumping lemma for CFL) with two different words: $$w1 = \ a^pb^{p-1}a$$ $$w2 = \ a^{2p}b^pa^p$$

but I'm stuck when the case is that $vwx$ (considering $uvwxy = w$) take letters from both the first group of $\bf{a}$ and the group of $\bf{b}$.
Have I chosen a wrong format for the word or am I simple missing some trivial condition?

# Answer
> 3 votes
The following grammar shows the contextfreeness $L$:

* $G = (N,T,P,S)$
* $N = \\{A, B, S\\}$
* $T = \\{a, b\\}$
* $S = \\{S\\}$
* $P = \\{S \rightarrow aAa, A \rightarrow aAa, A \rightarrow B, B \rightarrow aBb, B \rightarrow \lambda\\}$

$L(G) = L$

# Answer
> 4 votes
You are trying the wrong way. It is context-free.

(added.) The structure of the language (to guide the grammar construction) is better seen by setting $k = j-i$, so $j=k+i$. Then the language becomes $\\{ a^ka^ib^ia^k \mid i\ge 0, k\>0 \\}$.

# Answer
> 2 votes
**Hint:** You can first insert all of the $a$ in stack and then for each $b$ POP one $a$ from stack, then, for each $a$ POP one $a$ from stack.

**Because:** $i + (j-i)=j$

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


title: k-path problem - P, NP or NPC?

text:
# Question
Title: k-path problem - P, NP or NPC?
I need to determine which complexity class this problem belongs to:

> Given a graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of length $k$ exist between thesee two vertices?

How can I approach this problem to solve it?

# Answer
> 1 votes
If the path has to be simple reduce the HamiltonPath problem to this to show that's NP-complete, otherwise (not necessarily simple paths) take the $k$-th power of the adjacency matrix, whose entry corresponding to $u$ and $v$ not only contains whether there is such a path, but also the number of such paths.

# Answer
> 0 votes
it is a member of NP because you can design certificate for this problem , when the path you want to find is not necessarily simple you can solve it in polynomial time , if it is simple then this problem is NP complete problem .... if you want more then you can try by yourself to search or to make proof of your own ...

# Answer
> 0 votes
Hint: Given a vertex $v$, can you enumerate all vertices for which there is a path of length 1 from $v$? Then all vertices with for which there is a path of length 2 from $v$, etc.? How long does each step take in terms of $|V|$ and $|E|$?

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


# Question
Title: van Emde Boas tree: why store max recursively?
In both CLRS (third edition) and Erik Demaine's lecture, the van Emde Boas tree is defined to store `max` but not `min` recursively. Why store max recursively?

If it is *not* stored recursively, insert(*V*, *x*) can take advantage of the special case where a cluster or summary contains one element (`min = max`), although I think the advantage gained from this is insignificant. Keith Schwarz implements it this way in his Archive of Interesting Code. So why do CLRS and Erik not make use of this optimization in the algorithm? Is it actually a mistake?

# Answer
> 1 votes
take a look here he explains what you are saying , the theory does not guarantee the algorithm performance so what you pointed at to be weird is not but it is equivalent both cases and give the same $O(\log \log (u) )$ but it may differ in performance as you said .

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