# Question
Title: What is the difference between language hierarchy and Grammar hierarchy for LL and LR?
Till now I have believed that a LL language is a language generated by a LL grammar. Same goes for LR.

Now I know some of the hierarchies such as $LL(1)\subset LR(1)$. I used to think that the hierarchy is valid for language as well as grammar i,e if a grammar is LL1 then it must be LR(1); If a language is LL(1) then it must be LR(1).

Language theoretic comparison of LL and LR grammars

In the above link there is mention about two type of hierarchy. One for grammar, another for language. The two hierarchies are different at some points.

For e,g for grammar hierarchy $LALR(1)\subset LR(1)$ but for language hierarchy $LALR(1)=LR(1)$. I accept the grammar hierarchy. But the language hierarchy confuses me. Basically this hierarchy says that LALR(1) language set is equal to LR(1) language set.

How could this be true?

There are some grammars which are LR(1) but not LALR(1). So the language produced by these grammars should be LR(1) but not LALR(1) thus violating the language hierarchy.

I must be making some kind of mistake. please someone point that out?

# Answer
A language is in a class if there exist a grammar of that class which generates the language. Stating that for languages $LALR(1)=LR(1)$, means that when you have a $LR(1)$ grammar you can build a $LALR(1)$ grammar for the same language. The grammar may be more complex than the $LR(1)$ grammar (for instance, it may use equivalent but different non-terminals to provide the finer distinction of contexts that $LR(1)$ gives for free).
> 2 votes

# Answer
The notation $LR(1)$ denotes the set of languages that can be accepted by a LR(1) parser. So when you see something like $LALR(1)=LR(1)$, that is fundamentally about languages. It is incorrect to write "$LALR(1) \subset LR(1)$ for the grammar hierarchy"; that is meaningless. You haven't defined what you mean by a "grammar hierarchy", so we're forced to guess what that might mean. That's a non-standard concept -- we usually focus on the language hierarchy.

I don't know what the correct relationship between $LALR(1)$ and $LR(1)$ is, but here's how it could be true (if it is true): every LALR(1) grammar is a LR(1) grammar, but not every LR(1) grammar is a LALR(1) grammar; yet perhaps every LR(1) grammar can be rewritten into an equivalent LALR(1) grammar (one that accepts the same language). That would be consistent with (a natural interpretation) of what you wrote.

Keep in mind that there might be multiple grammars that accept the same language.
> 1 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: How to convert 2 or gates (x1 V x2 V x3) to NAND
**How can I convert a clause of size 3 that is made of 2 OR gates**

example:

```
(x1 OR x2 OR x3 )

```

**to one or more clauses of size 4 made only of NAND gates and not gates?** So without parentheses inside the clauses.

examples:

```
(x1 NAND x2 NAND x3 NAND x4)
(not x1 NAND x2 NAND not x3 NAND not x4) AND (x1 NAND x2 NAND x3 NAND x4)

```

additional notes: The original question asked is to prove that 4-SATCNF (A CNF expression that can be satisfied, with clauses of size 4 and with NAND gates between the 4 terms.) is NP-Complete by showing the polynomial reduction of 3-SAT \<=p 4-SATCNF. I'm stuck at the part where I need to find a function for the reduction. I suppose the function should be something around the form showed above, if not can somebody helped me find the good function?

Thank You

Articles that I consulted so far:

3-Sat to 4-sat polynomial conversion: https://www.csie.ntu.edu.tw/~lyuu/complexity/2012/20121106s.pdf

NAND Conversion: https://en.wikipedia.org/wiki/NAND\_logic

# Answer
> 0 votes
(x1 or x2 or x3) = (not x1 NAND not x2 NAND True NAND not x3)

# Answer
> 0 votes
We start with

```
NAND (a, b) := NOT (a AND b) = (NOT a) or (NOT b)
a = NOT NOT a
NOT a = NOT NOT NOT a.

a OR b or c =
a OR (b OR c) =
(NOT NOT a) OR (NOT NOT (b OR c)) =
NAND (NOT a, NOT (b OR c)) =
NAND (NOT a, NOT ((NOT NOT b) OR (NOT NOT c))) =
NAND (NOT a, NOT (NOT (NOT b AND NOT c))) =
NAND (NOT a, NOT (NAND (NOT b, NOT c))).

```

---
Tags: np-complete, logic
---


# Question
Title: Relationship between Independent Set and Vertex Cover
Directly from Wikipedia, a set of vertices $X \subseteq V(G)$ of a graph $G$ is independent if and only if its complement $V(G) \setminus X$ is a vertex cover.

Does this imply that the complement of the independent set problem is the vertex cover problem?

# Answer
> 11 votes
Well, strictly speaking it's not the complement; co-VC is co-NP-complete whereas Independent Set is NP-complete. If they were the same, we would know that co-NP was equal to NP, which we do not, and indeed most people believe they are not.

But an easy way of seeing that they are not the same if to consider $(K\_4, 2)$, the complete graph on four vertices) which is neither a yes-instance of Vertex Cover nor of Independent Set. Similarly, the instance $(K\_2,1)$ is a yes-instance for both.

However, they are related in the following way. A set of vertices $C \subseteq V(G)$ of a graph $G$ is a vertex cover if and only if $V(G) \setminus C$ is an independent set. This is easy to see; for every endpoint of an edge, at least one vertex must be in $C$ for $C$ to be a vertex cover, hence not both endpoints of an edge are in $V(G) \setminus C$, so $V(G) \setminus C$ is an independent set. This holds both directions.

So $(G,k)$ is a yes instance for Vertex Cover (a minimization problem) if and only if $(G,n-k)$ is a yes instance for Independent Set (a maximization problem).

# Answer
> -3 votes
You may check out this link:

http://www.hananayad.com/teaching/syde423/IndependentSet.pdf

According to this one, both are equally hard (NP-complete), however, optimization version of each problem is NP-hard.

---
Tags: graphs, np-complete
---


# Question
Title: What property of cons allows elimination of tail recursion modulo cons?
I'm familiar with the idea of *basic* tail recursion elimination, where functions that return the direct result of a call to themselves can be rewritten as iterative loops.

```
foo(...):
    # ...
    return foo(...)

```

I also understand that, as a special case, the function can still be rewritten if the recursive call is wrapped in a call to `cons`.

```
foo(...):
    # ...
    return (..., foo(...))

```

What property of `cons` allows this? What functions other than `cons` can wrap a recursive tail call without destroying our ability to rewrite it iteratively?

GCC (but not Clang) is able to optimize this example of "tail recursion modulo *multiplication,*" but it's unclear what mechanism allows it to discover this or how it makes its transformations.

```
pow(x, n):
    if n == 0: return 1
    else if n == 1: return x
    else: return x * pow(x, n-1)

```

# Answer
While GCC likely uses ad-hoc rules, you can derive them in the following way. I'll use `pow` to illustrate since you're `foo` is so vaguely defined. Also, `foo` might best be understood as an instance of last-call optimization with respect to single-assignment variables as the language Oz has and as discussed in Concepts, Techniques, and Models of Computer Programming. The benefit of using single-assignment variables is it allows remaining within a declarative programming paradigm. Essentially, you can have each field of the struct `foo` returns represented by single-assignment variables that are then passed to `foo` as additional arguments. `foo` then becomes a tail-recursive `void` returning function. No particular cleverness is needed for this.

Returning to `pow`, first, transform into continuation passing style. `pow` becomes:

```
pow(x, n):
    return pow2(x, n, x => x)

pow2(x, n, k):
    if n == 0: return k(1)
    else if n == 1: return k(x)
    else: return pow2(x, n-1, y => k(x*y))

```

All calls are tail calls now. However, the control stack has been moved into the captured environments in the closures representing the continuations.

Next, defunctionalize the continuations. Since there is only one recursive call, the resulting data structure representing the defunctionalized continuations is a list. We get:

```
pow(x, n):
    return pow2(x, n, Nil)

pow2(x, n, k):
    if n == 0: return applyPow(k, 1)
    else if n == 1: return applyPow(k, x)
    else: return pow2(x, n-1, Cons(x, k))

applyPow(k, acc):
    match k with:
        case Nil: return acc
        case Cons(x, k):
            return applyPow(k, x*acc)

```

What `applyPow(k, acc)` does is take a list, i.e. free monoid, like `k=Cons(x, Cons(x, Cons(x, Nil)))` and make it into `x*(x*(x*acc))`. But since `*` is associative and generally forms a monoid with unit `1`, we can reassociate this into `((x*x)*x)*acc`, and, for simplicity, tack a `1` on to start, producing `(((1*x)*x)*x)*acc`. The key thing is that we can actually partially compute the result even before we have `acc`. That means instead of passing `k` around as a list which is essentially some incomplete "syntax" that we'll "interpret" at the end, we can "interpret" it as we go. The upshot is that we can replace `Nil` with the unit of the monoid, `1` in this case, and `Cons` with the operation of the monoid, `*`, and now `k` represents the "running product". `applyPow(k, acc)` then becomes just `k*acc` which we can inline back into `pow2` and simplify producing:

```
pow(x, n):
    return pow2(x, n, 1)

pow2(x, n, k):
    if n == 0: return k
    else if n == 1: return k*x
    else: return pow2(x, n-1, k*x)

```

A tail-recursive, accumulator-passing style version of the original `pow`.

Of course, I'm not saying GCC does all this reasoning at compile-time. I don't know what logic GCC uses. My point is simply having done this reasoning once, it's relatively easy to recognize the pattern and immediately translate the original source code into this final form. However, the CPS transform and defunctionalization transform are completely general and mechanical. From there fusion, deforestation, or supercompilation techniques could be used to attempt to eliminate the reified continuations. The speculative transformations could be thrown away if it is not possible to eliminate all the allocation of the reified continuations. I suspect, though, that that would be too expensive to do all the time, in full generality, hence more ad-hoc approaches.

If you want to get ridiculous, you can check out the paper Recycling Continuations which also uses CPS and representations of continuations as data, but does something similar to but different to tail-recursion-modulo-cons. This describes how you might produce pointer-reversing algorithms by transformation.

This pattern of CPS transforming and defunctionalizing is a quite powerful tool for understanding, and is used to good effect in a series of papers I list here.
> 15 votes

# Answer
I’m going to beat around the bush for a while, but there is a point.

### Semigroups

The answer is, *the associative property of the binary reduction operation*.

That’s pretty abstract, but multiplication is a good example. If *x*, *y* and *z* are some natural numbers (or integers, or rational numbers, or real numbers, or complex numbers, or *N*×*N* matrices, or any of a whole bunch more things), then *x*×*y* is the same kind of number as both *x* and *y*. We started with two numbers, so it’s a binary operation, and got one, so we reduced the count of numbers we had by one, making this a reduction operation. And (*x*×*y**z* is always the same as *x*×(*y*×*z*), which is the associative property.

(If you already know all this, you can skip to the next section.)

A few more things you often see in computer science that work the same way:

* adding any of those kinds of numbers instead of multiplying
* concatenating strings (`"a"+"b"+"c"` is `"abc"` whether you start with `"ab"+"c"` or `"a"+"bc"`)
* Splicing two lists together. `[a]++[b]++[c]` is similarly `[a,b,c]` either from back to front or front to back.
* `cons` on a head and tail, if you think of the head as a singleton list. That’s just concatenating two lists.
* taking the union or the intersection of sets
* Boolean and, Boolean or
* bitwise `&`, `|` and `^`
* composition of functions: (*f**g*)∘*h* *x* = *f*∘(*g**h*) *x* = *f*(*g*(*h*(*x*)))
* maximum and minimum
* addition modulo *p*

Some things that don’t:

* subtraction, because 1-(1-2) ≠ (1-1)-2
* *x**y* = tan(*x*+*y*), because tan(π/4 + π/4) is undefined
* multiplication over the negative numbers, because -1 × -1 is not a negative number
* division of integers, which has all three problems!
* logical not, because it has only one operand, not two
* `int print2(int x, int y) { return printf( "%d %d\n", x, y ); }`, as `print2( print2(x,y), z );` and `print2( x, print2(y,z) );` have different output.

It’s a useful enough concept that we named it. A set with an operation that has these properties is a *semigroup*. So, the real numbers under multiplication are a semigroup. And your question turns out to be one of the ways this kind of abstraction becomes useful in the real world. **Semigroup operations can all be optimized the way you’re asking about.**

### Try This At Home

As far as I know, this technique was first described in 1974, in Daniel Friedman and David Wise’s paper, “Folding Stylized Recursions into Iterations”, although they assumed a few more properties than it turns out they needed to.

Haskell is a great language to illustrate this in, because it has the `Semigroup` typeclass in its standard library. It calls the operation of a generic `Semigroup` the operator `<>`. Since lists and strings are instances of `Semigroup`, their instances define `<>` as the concatenation operator `++`, for example. And with the right import, `[a] <> [b]` is an alias for `[a] ++ [b]`, which is `[a,b]`.

But, what about numbers? We just saw that numeric types are semigroups under *either* addition *or* multiplication! So which one gets to be `<>` for a `Double`? Well, either one! Haskell defines the types `Product Double`, `where (<>) = (*)` (that is the actual definition in Haskell), and also `Sum Double`, `where (<>) = (+)`.

One wrinkle is that you used the fact that 1 is the multiplicative identity. A semigroup with an identity is called a *monoid* and is defined in the Haskell package `Data.Monoid`, which calls the generic identity element of a typeclass `mempty`. `Sum`, `Product` and list each has an identity element (0, 1 and `[]`, respectively), so they are instances of `Monoid` as well as `Semigroup`. (Not to be confused with a *monad*, so just forget I even brought those up.)

That’s enough information to translate your algorithm into a Haskell function using monoids:

```
module StylizedRec (pow) where

import Data.Monoid as DM

pow :: Monoid a => a -> Word -> a
{- Applies the monoidal operation of the type of x, whatever that is, by
 - itself n times.  This is already in Haskell as Data.Monoid.mtimes, but
 - let’s write it out as an example.
 -}
pow _ 0 = mempty -- Special case: Return the nullary product.
pow x 1 = x      -- The base case.
pow x n = x <> (pow x (n-1)) -- The recursive case.

```

Importantly, note that this is tail recursion modulo semigroup: every case is either a value, a tail-recursive call, or the semigroup product of both. Also, this example happened to use `mempty` for one of the cases, but if we hadn’t needed that, we could have done it with the more general typeclass `Semigroup`.

Let’s load this program up in GHCI and see how it works:

```
*StylizedRec> getProduct $ pow 2 4
16
*StylizedRec> getProduct $ pow 7 2
49

```

Remember how we declared `pow` for a generic `Monoid`, whose type we called `a`? We gave GHCI enough information to deduce that the type `a` here is `Product Integer`, which is an `instance` of `Monoid` whose `<>` operation is integer multiplication. So `pow 2 4` expands recursively to `2<>2<>2<>2`, which is `2*2*2*2` or `16`. So far, so good.

But our function uses only generic monoid operations. Previously, I said that there is another instance of `Monoid` called `Sum`, whose `<>` operation is `+`. Can we try that?

```
*StylizedRec> getSum $ pow 2 4
8
*StylizedRec> getSum $ pow 7 2
14

```

The same expansion now gives us `2+2+2+2` instead of `2*2*2*2`. Multiplication is to addition as exponentiation is to multiplication!

But I gave one other example of a Haskell monoid: lists, whose operation is concatenation.

```
*StylizedRec> pow [2] 4
[2,2,2,2]
*StylizedRec> pow [7] 2
[7,7]

```

Writing `[2]` tells the compiler that this is a list, `<>` on lists is `++`, so `[2]++[2]++[2]++[2]` is `[2,2,2,2]`.

### Finally, an Algorithm (Two, in Fact)

By simply replacing `x` with `[x]`, you convert the generic algorithm that uses recursion modulo a semigroup into one that creates a list. Which list? *The list of elements the algorithm applies `<>` to.* Because we used only semigroup operations that lists have too, the resulting list will be isomorphic to the original computation. And since the original operation was associative, we can equally well evaluate the elements from back to front or from front to back.

If your algorithm ever reaches a base case and terminates, the list will be non-empty. Since the terminal case returned something, that will be the final element of the list, so it will have at least one element.

How do you apply a binary reduction operation to every element of a list in order? That’s right, a fold. So you can substitute `[x]` for `x`, get a list of elements to reduce by `<>`, and then either right-fold or left-fold the list:

```
*StylizedRec> getProduct $ foldr1 (<>) $ pow [Product 2] 4
16
*StylizedRec> import Data.List
*StylizedRec Data.List> getProduct $ foldl1' (<>) $ pow [Product 2] 4
16

```

The version with `foldr1` actually exists in the standard library, as `sconcat` for `Semigroup` and `mconcat` for `Monoid`. It does a lazy right fold on the list. That is, it expands `[Product 2,Product 2,Product 2,Product 2]` to `2<>(2<>(2<>(2)))`.

This is not efficient in this case because you can’t do anything with the individual terms until you generate all of them. (At one point I had a discussion here about when to use right folds and when to use strict left folds, but it went too far afield.)

The version with `foldl1'` is a strictly-evaluated left fold. That is to say, a tail-recursive function with a strict accumulator. This evaluates to `(((2)<>2)<>2)<>2`, calculated immediately and not later when it’s needed. (At least, there are no delays within the fold itself: the list being folded is generated here by another function that might contain lazy evaluation.) So, the fold calculates `(4<>2)<>2`, then immediately calculates`8<>2`, then `16`. This is why we needed the operation to be associative: we just changed the grouping of the parentheses!

**The strict left fold is the equivalent of what GCC is doing.** The leftmost number in the previous example is the accumulator, in this case a running product. At each step, it’s multiplied by the next number in the list. Another way to express it that is: you iterate over the values to be multiplied, keeping the running product in an accumulator, and on each iteration, you multiply the accumulator by the next value. That is, it’s a `while` loop in disguise.

It can sometimes be made just as efficient. The compiler might be able to optimize away the list data structure in memory. In theory, it has enough information at compile time to figure out it should do so here: `[x]` is a singleton, so `[x]<>xs` is the same as `cons x xs`. Each iteration of the function might be able to re-use the same stack frame and update the parameters in place.

Either a right fold or a strict left fold could be more appropriate, in a particular case, so know which one you want. There are also some things only a right fold can do (such as generate interactive output without waiting for all the input, and operate on an infinite list). Here, though, we’re reducing a sequence of operations to a simple value, so a strict left fold is what we want.

So, as you can see, it is possible to automatically optimize tail-recursion modulo any semigroup (one example of which is any of the usual numeric types under multiplication) to either a lazy right fold or a strict left fold, in one line of Haskell.

### Generalizing Further

The two arguments of the binary operation don’t have to be the same type, so long as the initial value is the same type as your result. (You can of course always flip the arguments to match the order of the kind of fold you’re doing, left or right.) So you might repeatedly add patches to a file to get an updated file, or starting with an initial value of 1.0, divide by integers to accumulate a floating-point result. Or prepend elements to the empty list to get a list.

Another type of generalization is to apply the folds not to lists but to other `Foldable` data structures. Often, an immutable linear linked list is not the data structure you want for a given algorithm. One issue I did not get into above is that it’s a lot more efficient to add elements to the front of a list than to the back, and when the operation is not commutative, applying `x` on the left and the right of the operation aren’t the same. So you would need to use another structure, such as a pair of lists or binary tree, to represent an algorithm that could apply `x` on the right of `<>` as well as to the left.

Also note that the associative property allows you to regroup the operations in other useful ways, such as divide-and-conquer:

```
times :: Monoid a => a -> Word -> a
times _ 0 = mempty
times x 1 = x
times x n | even n    = y <> y
          | otherwise = x <> y <> y
  where y = times x (n `quot` 2)

```

Or automatic parallelism, where each thread reduces a subrange to a value that is then combined with the others.
> 9 votes

---
Tags: compilers, recursion, program-optimization, tail-recursion
---


title: Efficient point grouping algorithm

text:
# Question
Title: Efficient point grouping algorithm
I'm trying to find a good solution to the following problem: Given a set of 3d real number coordinates inside a cube, I want to group them into containers. The containers should contain all elements that are in predefined distance to at least one of the other elements. Should two elements be closer than a predefined distance, they are to end in the same container. **Note:** Two elements that are further apart may end in the same container e.g. if they are both close to a different element

The most straight forward solution I can think of is to go through all points, and compare them with all other points that haven't been visited before to find out if they are in proximity, but it seems rather inefficient.

I tried to find a solution online, but (maybe because I'm missing the correct keywords) can't find any. I stumbled upon k-d-trees and similar concepts but as far as I understood they don't help much here. Are there good algorithms out there that can take care of this or does anybody have a suggestion on what I could do?

Below is a (badly hand drawn) illustration of a possible 2d case with reference distance d marked in blue and the two groups I want to end up with in red. Thanks in advance for any help.

**Edit:** as pointed out in the comments, this problem can be thought of as finding connected components of a graph. The graph nodes are the points from the data set and two nodes are adjacent if their distance is smaller than the reference value. The problem I see is that establishing the edges seems to be O(n^2), because I don't see a way that doesn't require me to do pairwise checks on all points of the set, is that correct?

# Answer
> 2 votes
There is an efficient algorithm whose running time is nearly linear in most cases.

Suppose you the distance threshold is $d$, i.e., you want two elements at distance $\le d$ to be in the same group.

Then you can divide up space into cubes of side length $2d$, and store each element in the cube it is contained in. The cubes can be stored in a hash table for efficient lookup. For instance, given a point at coordinates $(x,y,z)$, it is associated with the cube whose lower-left corner is at coordinates $(\lfloor x/2d \rfloor, \lfloor y/2d \rfloor, \lfloor z/2d \rfloor \rfloor)$; you can hash those coordinates and store the point in the corresponding bucket of the hashtable.

Now, if two points are at distance $\le d$ apart, then they must be in adjacent cubes. So, you can find all points that need to be put into the same group by looking at pairs of adjacent cubes. In particular, the algorithm becomes:

* For each cube $C$:
    + For each cube $C'$ that is adjacent to $C$:
    + For each point $P$ in $C$ and each point $P'$ in $C'$:
        - If the distance between $P,P'$ is at most $d$, merge them into the same group.

You can keep track of the groups using a Union-Find data structure. With this approach, the running time will be $O(n \alpha(n))$, assuming that each cube has at most a constant number of points in it (which will typically be the case for most arrangements of points). Here we've used the fact that each cube is adjacent to only 26 other cubes, so each point $P$ only needs to be compared to a constant number of other points.

# Answer
> 4 votes
## **My Solutions**

I will try to elaborate on what solutions I found, their implementations and those implementation's running time. As I don't have any real computer science background, please point out any mistakes/unclarities you find.

First: The problem, in general terms, is to partition a set of points from $A \subset \mathbb{R}^d$ into groups such that every point in them is $\epsilon$-reachable from every other point in the group. Reachable,for $x\_1, x\_n \in A$, means there is a sequence of points $x\_1,\dots,x\_n \in A$ s.t. $d(x\_i,x\_{i+1})\<\epsilon$. In other terms: If two points are closer than $\epsilon$ to each other, the algorithm must assign them to the same group/cluster.

---

**DBSCAN**: DBSCAN is a super general algorithm. I will use $B\_{\epsilon}(x)$ for the $d$-dimensional sphere around $x$ with respect to some arbitrary metric $d(\cdot,\cdot)$. DBSCAN finds clusters by defining:

* $x \in A$ is a core point, if at least $N$ other points of $A$ lie in $B\_{\epsilon}(x)$
* $x \in A$ is directly reachable from $y \in A$ if both are core points and $d(x,y)\<\epsilon$
* $x \in A$ is reachable from $y \in A$ if there exists a sequence $x\_1 =x, \dots, x\_n =y \in A$ s.t. $x\_{i+1}$ is reachable from $x\_i$
* non reachable points are outliers

Now, as you might see, for $N=2$ (if you include every point itself when counting) and $d(\cdot, \cdot)$ the usual euclidean metric this defines exactly the problem I stated above. DBSCAN clusters together core-points deterministically, but also adds non-core points to clusters. So if $x \in A$ is reachable from core point $y$, it might end up in the same cluster without being a core point itself. I say might, because non-core points may be reachable from different clusters. The assignation is then determined by the order in which the algorithm runs through the clusters. This ambiguity however resolves with $N=2$, as then every point that is reachable from another is automatically a core point, that is reachability as stated above is then a symmetric relation. Clusters are then unambiguous. In case of an indexing structure that does neighborhood querys in $O(logn)$, the runtime complexity is apparently $O(n \\; logn)$, but don't take my word for it.

I used scikit-learn's implementation of DBSCAN (http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html). I failed to find out what runtime complexity this implementation has, but the docs state memory complexity of $O(n.d)$.

---

**Intersection graph:** As it has been proposed in a different answer: One can also think of the problem as a graph-theoretical one. The graphs vertices are represented by the points in $A$, with two vertices being adjacent iff their points are in $\epsilon$-distance of each other. On this graph the problem translates to finding the connected components. The paper of *Bentley, Jon L.; Stanat, Donald F.; Williams, E. Hollins, Jr. (1977), "The complexity of finding fixed-radius near neighbors", Information Processing Letters, 6 (6): 209–212* provides an algorithm for constructing this graph that runs in linear time and is essentially identical to the one proposed by @D.W.. Finding the connected components can also be done in linear time, e.g. by breadth- or depth-first algortihms.

---

**Python Code:** For the Code, I mainly used the DBSCAN implementation of scikit-learn, networkx for graphs and finding connected components (it is open source but I couldnt find any reference on the runtime complexity) and scipy.spatial's cKDTree implementation (which I *do not* understand in detail).

```
from sklearn.cluster import DBSCAN
from sklearn.datasets.samples_generator import make_blobs
import networkx as nx
import scipy.spatial as sp

def cluster(data, epsilon,N): #DBSCAN, euclidean distance
    db     = DBSCAN(eps=epsilon, min_samples=N).fit(data)
    labels = db.labels_ #labels of the found clusters
    n_clusters = len(set(labels)) - (1 if -1 in labels else 0) #number of clusters
    clusters   = [data[labels == i] for i in range(n_clusters)] #list of clusters
    return clusters, n_clusters

```

Is my minimal implementation of the previously described goal. The method returns clusters and their size. For the graph method, I wrote a little class. The class describes a graph whose vertices are the indices of the corresponding points in $A$ as list. Using the cKDTree's data structure, finding pairs of reachable points is lightning fast. You can then slice out the elements via the indices.

```
class IGraph:
    def __init__(self, nodelst=[], radius = 1):
        self.igraph = nx.Graph()
        self.radii  = radius
        self.nodelst = nodelst #nodelst is array of coordinate tuples, graph contains indices as nodes
        self.__make_edges__()

    def __make_edges__(self):
        self.igraph.add_edges_from( sp.cKDTree(self.nodelst).query_pairs(r=self.radii) )

    def get_conn_comp(self):
        ind = [list(x) for x in nx.connected_components(self.igraph) if len(x)>1]
        return [self.nodelst[indlist] for indlist in ind]

def graph_cluster(data, epsilon):
    graph = IGraph(nodelst = data, radius = epsilon)
    clusters = graph.get_conn_comp()
    return clusters, len(clusters)

```

I also did a little benchmark, but it is in no way representative. I create a cluster with:

```
centers = [[1, 1,1], [-1, -1,1], [1, -1,1]]
X,_ = make_blobs(n_samples=N, centers=centers, cluster_std=0.4,
                            random_state=0)

```

For different N, the methods compare differently, on my machine for example:

* $N = 20000$: "cluster": 293.711 ms, "graph\_cluster": 422.089 ms
* $N = 7000$: "cluster": 87.455 ms, "graph\_cluster": 95.322 ms
* $N = 700$: "cluster": 3.764 ms, "graph\_cluster": 1.689 ms

For small datasets, and this specific clustering, the graph solution wins. But apparently the DBSCAN shows better scaling behavior. I haven't looked at different dimensions of the data, but that may also be interesting. Also: the results are exactly the same for both algortihms. **Additional Note**: The graph solution scales heavily with $\epsilon$, which is 0.1 in my code. Larger values make it far worse! In other words: If you have small clusters, the graph solution outperforms DBSCAN by ages, for large clusters it is the other way around (apparently).

# Answer
> 1 votes
You can build the graph according to the following rules:

1) nodes corresponds to points

2) two nodes are connected if and only if the distance between points is less than $d$

Then you either look for connected components in the graph (classical and very fast, use DFS) or apply another graph clustering/partitioning algorithm. If splitting into two groups MIN-CUT is a reasonable choice.

---
Tags: algorithms, efficiency
---


# Question
Title: $\#P$ closure under binomial coefficients?
It is quite straightforward to understand $\\#P$ closure under addition and multiplication since there are canonical $NTM$ constructions.

Is there illustrative non-trivial example to understand $NTM$ construction for closure under binomial coefficients?

# Answer
Let me take a guess: you mean an operation of the form $f(x) \mapsto \binom{f(x)}{d}$, where $d$ is a constant. Let's assume also that $f(x)$ is the number of $y$ such that $\phi(x,y)$. Then $\binom{f(x)}{d}$ is the number of $d$-tuples $y\_1,\ldots,y\_d$ such that $y\_1 \< \cdots \< y\_d$ and $\phi(x,y\_1) \land \cdots \land \phi(x,y\_d)$.
> 1 votes

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


# Question
Title: Good reference for average-case runtime analysis of QuickSort
I'm a beginner in programming with little knowledge about the technicalities. I'm assigned to do a "reading project" on the average case analysis of quicksort. I mean I have to present it in class. Now, I need a good source from which I can read it and find the materials which I can include in my presentation. As for my existing knowledge on algorithms, one can assume that I almost know nothing except for "just codes" and nothing at all about their analysis. Any book or materials having rigorous proofs will also do. Any help will be greatly appreciated!

# Answer
> 1 votes
Given your stats background, you will find the "indicator variable" analysis easier than the solution via recurrence equations. It is based on computing the probability that two elements of given ranks are compared to each other.

The idea is described on the wikipedia page and in more detail in Section 7.4 of Cormen et al. Introduction to Algorithms 3rd edition.

---
Tags: algorithm-analysis, reference-request, runtime-analysis, quicksort, average-case
---


title: Can Atm language be reduced?

text:
# Question
Title: Can Atm language be reduced?
I'm familiar with reductions to the language $A\_{\mathrm{TM}}=\\{\langle M,w\rangle | M \text{ accepts } w \\}$, for example $A\_{\mathrm{TM}}\le H\_{\mathrm{TM}}$. Are there examples for reductions from $A\_{\mathrm{TM}}$. By that I mean, a reduction such as: $B\le A\_{\mathrm{TM}}$ (many to one reduction).

# Answer
> 2 votes
I'm fairly certain this has been asked before, but I couldn't find it, so here goes:

We can reduce every problem in RE to $A\_{TM}$ as follows. Let $L$ be a language in RE, and let $M$ be a TM such that $L(M)=L$.

The reduction then proceeds as follows: given input $x$, the reduction outputs $\langle M,x \rangle$.

It then trivially holds that $x\in L$ iff $M$ accepts $x$, iff $\langle M,x \rangle\in A\_{TM}$.

---
Tags: complexity-theory, turing-machines, reductions
---


# Question
Title: How might neural networks use a symbolic A.I approach?
I’m fairly new to this area so my understanding is pretty basic. Am I correct in saying that symbolic a.i would take data and use logic to search through and find the right answer. An example is a doctor machine. We feed the machine a ton of medical textbooks and it answers questions by looking up the answers from those textbooks. and The non symbolic approach is feeding raw information into the AI so that it can analyze and construct its own implicit knowledge about how to answer ?

But what I can’t understand is these approaches look completely different, so what similarities might it share ?

# Answer
Yes, the symbolic AI operates on symbols, but your idea surpasses what it really can do. It was mainly used for the expert system and the input was in the form of symbols, not just any data.

To feed the textbooks into the AI would require Natural Language Processing at higher level than currently is achievable. The symbolic AI concept was created about seventy years ago, so it cannot operate as you imagine.

On the other hand feeding appropriate data into network to give prediction could be used, but here inherent problem is with lack of full medical knowledge to make it work.

If the goal is to check textbooks and return relevant information then the task is simpler, here dictionary based search would do the trick.

No, the raw data is being fed to NN to solve some optimization / classification / estimation problem based on provided data (unsupervised or supervised learning on the training set).

It doesn't create implicit knowledge, think about it more in the terms of regression or approximation. Currently it is not fully known what exactly is the state of the *knowledge* of trained network, we are not sure what it has learned.

If you compare the expert system and trained classifier, they do not have similarities. The expert system deduce based on given data, requests missing info, input is symbolic and extensible. For *raw data* approaches the network is not extensible in this sense, it requires new training samples and possibly new architecture if the task differs from the initial goal.
> 1 votes

# Answer
I haven't studied ai formally, but I can tell you that the two things you are comparing are actually examples of not simbolic ai, both of them. That is a medical textbook is actually considered "raw data" as you said. An example of simbolic ai would be a software that gets as input illneses symptoms from the doctor in a particular format that the machine can understand and then uses logical rules of inference to try to find the best diagnostic from the patient.

A no simbolic ai algorithm could be a neural network that looks at pictures of cats and other things and eventually learns to find cats in pictures that it hasn't seen before

As it happens with most things in AI, these definitions are not set in stone and there is lots of overlap between the two things
> 0 votes

# Answer
Symbolic AI covers a lot of different methods, including logic reasoning, but not limited to. The "doctor machine" you refer too has actually been tried in the 1980's, in the form of expert systems: broadly, a very large if-then-else tree. Problem is: it is very expensive (as in: time consuming) to turn expert knowledge into a program (you cannot feed medical textbooks, you have to extract knowledge from the expert). Symbolic AI is still around today, but not so popular as it was in the early decades of AI.

Sub-symbolic AI, which includes artificial neural networks, takes a different approach by training what is essentially a blackbox (e.g. a big mess of artificial neurons connected together). On the one hand, you may gain the ability to feed a lot of raw information to your learning blackbox. On the other hand, you may also loose the ability to explain what has been learned.

For example: a neural network can be trained to associate a description of symptoms with diagnosis (this is supervised learning with labelled data) and be efficient at playing doctor, but it will be very difficult to understand how it produces a specific diagnosis. In the same line of thought: Deepmind's Alpha Go or Alpha Zero can beat the best human player, but both Deepmind's programmers and the greatest masters struggle to understand how.
> 0 votes

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


# Question
Title: How can i design this function using only NAND and XOR gates?
I have this initial function \begin{split}(\overline{A}+\overline{B})(\overline{D}+\overline{C})+AB\overline{(\overline{C}+\overline{D})}\end{split} Which i reduced to \begin{split}{\overline{AB}\*\overline{CD}}+ABCD \end{split} The first part is easy to do with NAND but the OR ABCD part i have no ideia how to do...I suspect thats where the XOR comes in and i maybe shouldn't have reduced so much the function.

# Answer
I have assumed that only 2 input NAND gates are available.

For $\overline {AB}\*\overline {CD}$

Take A and B as input and feed them to a NAND gate. U will get $\overline {AB}$. Similarly u can get $\overline {CD}$.

Now feed $\overline {AB}$ and $\overline {CD}$ as input to another NAND gate . U will get AB + CD using demorgan law.

For ABCD take $\overline {AB}$ and complement it using a NAND gate to get AB. Take $\overline {CD}$ and complement it to get CD. Now feed AB and CD to NAND gate. You will get $\overline {ABCD}$.

Now feed (AB+CD) and (ABCD)' to NAND gate. U will get $\overline{(AB+CD)\overline{(ABCD})}$.Apply demorgan law. U have ur answer.

The trick is to express the function as a sum of products which u already have. Now derive the complement of each product term. When all product terms have been derived then feed then to a NAND gate. This final NAND gate will complement the already complemented product terms and add them thus giving the desired answer.
> 1 votes

---
Tags: boolean-algebra
---


title: Camera position w.r.t. basketball court

text:
# Question
Title: Camera position w.r.t. basketball court
I am new in Computer Vision. Suppose you have 8 points (players in a basketball court) in a 2D image (png photo), that is we know the pixel coordinates of each. I would like to compute camera position w.r.t. the field. We have the actual dimensions of the field. Also, I can write the equations of two or three transversal lines in the field that are parallels lines from top view. With this data can we find a position vector of the camera w.r.t. the field ?

> Any idea on where to read about this ?

# Answer
> 3 votes
You said you could see lines, so I assume you could see their intersections. If you could assume to have at least 4 fixed points of the court which are always visible (corners might be a good choice), this problem is similar to the 3D pose estimation problem, since you are essentially looking for a pose (position and orientation) of a known 3D object in a 2D image.

You might find it useful to read about POSIT, an iterative algorithm published in 1992 and there is also this algorithm from 1999. Both algorithm solve the 3D pose estimation problem.

---
Tags: computer-vision
---


# Question
Title: Applying Johnson's algorithm on undirected graph with negative edge weights
Currently we are discussing applying Johnson's algorithm on undirected graph with negative edge weights. And the graph may contains cycles, but **the sum of weights of any cycle is guaranteed to be non-negative**.

If we consider the undirected graph as bi-directed, then any negative-weight undirected edge will create a negative cycle in the bi-directed graph, and violate the prerequisite of Johnson's algorithm.

Is there any altered version of Johnson's algorithm can handle such scenario?

-- update 2017/12/30 --

Sorry, I forget to mention an additional constraint for the path: the path should be simple, which means one edge could only be travel for once.

# Answer
> 2 votes
# Shortest simple paths

Finding the length of the shortest simple path is NP-hard, so there is no efficient algorithm.

# Shortest paths (not necessarily simple)

The original version of the question didn't include the requirement that the path be simple. Below I include my answer to that version of the question, for posterity:

Decompose the graph into connected components. Solve the problem separately for each connected component.

If there is an edge with negative weight in the component, then for all pairs of vertices $u,v$ in the component, the distance from $u$ to $v$ is $-\infty$. So, you can output $d(u,v)=-\infty$ for all pairs $u,v$ in the component. You don't even need to run Johnson's algorithm.

(Why is that answer correct? Well, suppose the edge $(a,b)$ has negative weight. Then consider a path $u \leadsto a \to b \to a \to \cdots \to b \leadsto v$. Such a path can have arbitrarily small length, by traversing the cycle $a \to b \to a$ sufficiently many times.)

If there is no edge in the component with negative weight, you can use Johnson's algorithm to compute the distance between each pair of vertices in the component. Johnson's algorithm on this component will work fine, since this component has no negative-weight edges.

Finally, the distance between any two vertices that are in different components is $+\infty$, since there is no path between them.

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


title: Remove elements that appear m times

text:
# Question
Title: Remove elements that appear m times
I need to come up with an algorithm that iterates through an array and if any element appears m times, then the array needs to be modified so that it only appears min(2, m) times. For example, if A = \[2, 2, 2, 3, 4, 4, 5, 5, 5\] and m = 3, A = \[2, 2, 3, 4, 4, 5, 5\]. It is easy to do with extra space or nonlinear time but I want to know how to do it in O(n) time and space. The array is already sorted.

It is apparently a variant of the "remove all duplicates of a sorted array" problem, but the O(n) algo for that works because it finds all distinct elements and inserts them one by one. In the problem above, you can't do that because you need to check how many times the particular element occurred.

I've tried the following algorithm:

```
def variant2(arr, m):
    vacant = 1
    for i in range(1, len(arr)):
        if not arr[i] == arr[vacant - 1]:
            if i - vacant + 1 == m:
                vacant += min(2, m) - 1
                arr[vacant] = arr[i]
                vacant += 1

    temp = arr[:vacant][:]
    return temp

```

but this doesn't work as the overwriting of the "vacant" index will cause an element that wasn't duplicated before to be duplicated. For example, A = \[2, 2, 2, 3, 4, ...\] with m = 3 will become A = \[2, 2, 3, 3, 4....\].

# Answer
I don't really understand your problem, so here is how you can solve a similar problem: instead of removing duplicated, we want each element to appear at most twice. In other words, if an element appears in a run of length $\ell$, we replace it with a run of length $\min(\ell,2)$. Suppose that the array is $A\_1,\ldots,A\_n$.

1. Assign $\mathrm{curr} \gets A\_1$. This variable will store the value being repeated in the current run.
2. Assign $\ell \gets 1$. This is the length of the current run.
3. Assign $\nu \gets 1$. This is the length of the "new" array.
4. Loop over the values $2 \leq i \leq n$:
    * If $A\_i = \mathrm{curr}$, increase $\ell$ by 1.
    * If $A\_i \neq \mathrm{curr}$, let $\mathrm{curr} \gets A\_i$, and set $\ell \gets 1$.
    * If $\ell \leq 2$, insert the new element: increase $\nu$ by 1, and assign $A\_\nu \gets \mathrm{curr}$.
5. Return $A\_1,\ldots,A\_\nu$.

You can prove by induction that $\nu \leq i$, and so information is erased only after it is read.

A more challenging task is: "If an element appears in a run of length $\ell \geq m$, replace it with a run of length $2$". In other words, we replace a run of length $\ell$ with a run of length $2$ whenever $\ell \geq m$ (assuming $m \geq 2$). We can accomplish this using a similar strategy:

1. Assign $\mathrm{curr} \gets A\_1$. This variable will store the value being repeated in the current run.
2. Assign $\ell \gets 1$. This is the length of the current run.
3. Assign $\nu \gets 1$. This is the length of the "new" array.
4. Loop over the values $2 \leq i \leq n$:
    * If $A\_i = \mathrm{curr}$, increase $\ell$ by 1.
    * If $A\_i \neq \mathrm{curr}$, let $\mathrm{curr} \gets A\_i$, and set $\ell \gets 1$.
    * If $\ell \< m$, insert the new element: increase $\nu$ by 1, and assign $A\_\nu \gets \mathrm{curr}$.
    * If $\ell = m$, remove $m-2$ occurrences of $\mathrm{curr}$: decrease $\nu$ by $m-2$.
5. Return $A\_1,\ldots,A\_\nu$.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Polynomial time problems with provably high degree time complexity?
For any integer $k$, does there exist a decision problem in $\textbf P$ that can be proven to require $\Omega(n^k)$ steps?

# Answer
> 2 votes
The time hierarchy theorem, proved by diagonalization, shows that for every reasonable function $f$ there exists a problem solvable in $O(f(n))$ but not in $o(f(n)/\log f(n))$. One such problem is, given a Turing machine and in input $x$, to determine whether the machine halts in $x$ within $f(|x|)$ steps. In your case, you can choose $f(n) = n^k \log n$ to obtain a problem solvable in $O(n^k \log n)$ but not in $o(n^k)$.

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


# Question
Title: Why the Goemans-Williamson's MAX-CUT algorithm relax the variables to vectors of $n-$dimension on unit sphere?
Why not to some constant like 3 or 4 dimension? I suspect that it is because Cholesky Decompostion will work only for $n \times n$ matrix $B$ where $B^TB = P$ where $P$ is a semidefinite matrix. Is it true? Or there is something else?

# Answer
The MAX-CUT algorithm relies on semidefinite programming, a convex optimization problem which can be solved in polynomial time. What you solve directly is the semidefinite program

$$ \begin{align\*} & \max \sum\_{ij} w\_{ij} \frac{1-a\_{ij}}{2} \\ s.t. \quad& (a\_{ij})\_{i,j=1}^n \text{ is positive semidefinite} \\ & a\_{ii} = 1 \text{ for all $i$} \end{align\*} $$

Given a solution for this program, you can extract the vectors using Cholesky decomposition.

The problem you are interested in is different:

$$ \begin{align\*} & \max \sum\_{ij} w\_{ij} \frac{1-\langle v\_i, v\_j \rangle}{2} \\ s.t. \quad& v\_i \in \mathbb{R}^d \\ & \\|v\_i\\|^2 = 1 \end{align\*} $$

When $d = 1$, this is just MAX-CUT. When $d$ is constant, optimizing over $\\{v\_i \in \mathbb{R}^d : \\|v\_i\\| = 1 \\}$ is likely NP-hard. When $d = n$, this can be solved using the semidefinite program described above. This is why we allow the dimension to be unbounded.

If you could force the dimension to be small, then you could improve the approximation ratio of the algorithm, see for example Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT by Avidor and Zwick. Assuming the unique games conjecture, however, the approximation guarantee of the Goemans–Williamson algorithm is tight. This shows that even in the particular case of MAX-CUT, it is likely that finding a low-dimensional solution cannot be done efficiently.
> 5 votes

---
Tags: algorithms, approximation, max-cut
---


# Question
Title: Can LP for matroid polytopes be solved using the greedy algorithm?
For general linear programming (LP), i.e. optimization of a linear objective over a general polyhedron, to the best of my knowledge/recollection one can use the simplex algorithm (or hypothetically, although it's not done often in practice, the ellipsoid algorithm).

Matroids are well known for the property that the greedy algorithm is optimal if and only if it is performed for a weight function defined on the bases of a matroid. (Or something similar.)

**Question:** In special cases where we can somehow create a correspondence between vertices of a polytope and bases of a matroid, does the greedy algorithm provide a solution for LP?

The answer to this seems like it might be yes based on the paper *The Bergman Complex of a Matroid and Phylogenetic Trees* by Federico Ardila and Caroline J. Klivans. However, the exposition does not confirm or deny this suspicion explicitly, and without an explicit statement either way, combined with the fact I am not 100% certain I understand the definitions, I am still unsure if it is true or not. Below I quote the portion with the relevant definitions and hint:

> Let $M$ be a matroid of rank $r$ on the ground set $\[n\] = \\{1,2,...,n\\}$, and let $\omega \in \mathbb{R}^n$. Regard $\omega$ as a weight function on $M$, so that the weight of a basis $B=\\{b\_1,...,b\_r\\}$ of $M$ is given by $$\omega\_B =\omega\_{b\_1} + \omega\_{b\_2} +\cdots+\omega\_{b\_r} \\,.$$ Let $M\_{\omega}$ be the collection of bases of $M$ having minimum $\omega$-weight... we can understand $M\_{\omega}$ in terms of the **matroid polytope**. \[emphasis mine\] We will use the following characterization of matroid polytopes, due to Gelfand and Serganova:
>
> **Theorem.** \[6, Theorem 1.11.1\] Let $S$ be a collection of $r$-subsets of $\[n\]$. Let $P\_S$ be the polytope in $\mathbb{R}^n$ with vertex set $\\{e\_{b\_1} +\cdots+e\_{b\_r} |\\{b\_1,\dots,b\_r\\} \in S\\}$, where $e\_i$ is the $i$-th unit vector. Then $S$ is the collection of bases of a matroid if and only if every edge of $P\_S$ is a translate of the vector $e\_i − e\_j$ for some $i, j \in \[n\]$.
>
> Let $P\_M$ be the matroid polytope of $M$. We can now think of $\omega$ as a linear functional in $\mathbb{R}^n$. **The bases in** $M\_{\omega}$ **correspond to the vertices of** $P\_M$ **which minimize the linear functional $\omega$.** \[emphasis mine\] Their convex hull is $P\_{M\_{\omega}}$, the face of $P\_M$ where $\omega$ is minimized. It follows that the edges of $P\_{M\_{\omega}}$, being edges of $P\_M$ also, are parallel to vectors of the form $e\_i − e\_j$. Therefore $M\_{\omega}$ is the collection of bases of a matroid.

# Answer
You can associate with each matroid two polytopes in $\mathbb{R}^n$, where $n$ is the size of the universe over which the matroid is defined:

* The *matroid polytope* is the convex hull of the characteristic vectors of all independent sets.
* The *base polytope* is the convex hull of the characteristic vectors of all bases (maximal independent sets).

The maximum of a linear function over a polytope is always attained (not necessarily uniquely) at a vertex. Therefore maximizing a linear function over a base polytope is like maximizing it over the collection of bases, for which the greedy algorithm can be used. The same goes for the matroid polytope, with the necessary changes.
> 2 votes

---
Tags: linear-programming, greedy-algorithms, matroids
---


title: Compute growth of function

text:
# Question
Title: Compute growth of function
Suppose that $p\>0$ and $n\>0$ is a natural number. How do I prove that

$$ \sum\_{k=1}^n k^p = 1^p + 2^p + \dots +n^p \sim \frac{1}{p+1}n^{p+1}=\Theta(n^{p+1})$$

for $n \rightarrow \infty$?

# Answer
You can show this by estimating the sum using an integral: on the one hand, $$ \sum\_{k=1}^n k^p = \int\_1^{n+1} \lfloor x \rfloor^p \\, dx \leq \int\_1^{n+1} x^p \\, dx = \left. \frac{x^{p+1}}{p+1} \right|\_1^{n+1} = \\\frac{(n+1)^{p+1}-1}{p+1} = \frac{n^{p+1}}{p+1} + O(n^p). $$ On the other hand, $$ \sum\_{k=1}^n k^p = \int\_0^n \lceil x \rceil^p \\, dx \geq \int\_0^n x^p \\, dx = \left. \frac{x^{p+1}}{p+1} \right|\_0^n = \frac{n^{p+1}}{p+1}. $$ You can also calculate the sum explicitly, using Faulhaber's formula.
> 2 votes

# Answer
$$\sum\_{k=1}^{n}k^p\<\sum\_{k=1}^{n}\color{red}n^p=n\times n^p=n^{p+1}$$
> 2 votes

---
Tags: mathematical-foundations
---


# Question
Title: Are all relational schemas with partial dependencies not in 3NF?
From Database Management Systems, by Raghu Ramakrishnan, Johannes Gehrk

> Let `R` be a relation schema, `F` be the set of functional dependencies (FDs) given to hold over `R` , `X` be a subset of the attributes of `R`, and `A` be an attribute of `R`. `R` is in third normal form if, for every FD `X -> A` in `F`, one of the following statements is true:
>
> * `A` $\in$ `X`; that is, it is a trivial FD, or
> * `X` is a superkey, or
> * `A` is part of some key for `R`.
>
> Suppose that a dependency `X -> A` causes a violation of 3NF. There are two cases:
>
> * `X` is a proper subset of some key `K`. Such a dependency is called **a partial dependency**.
> * `X` is not a proper subset of any key. Such a dependency is called **a transitive dependency**, because it means we have a chain of dependencies `K->X-> A`.

1. Am I correct that "Figure 19.7 Case 1" and "Figure 19.8 Case 1" are not 3NF, while "Figure 19.8 Case 2" is 3NF?
2. Why is there no either "Figure 19.7 Case 2: A in KEY" or "Figure 19.7 Case 2: A in KEY1" where "KEY1" is different from "KEY"? Does that case exist?

Am I correct that

* If that case can exist, it will be 3NF.
    * If that case can't exist, all relational schemas with partial dependencies are not in 3NF?

Thanks.

# Answer
Premise: The figures depict functional dependencies, not relation schemas. It is improper to say that a functional dependency is or not in any normal form. So, I suppose that you are asking if the functional dependencies violate or not a normal form.

You say:

> Suppose that a dependency X -\> A causes a violation of 3NF. There are two cases:
>
> • X is a proper subset of some key K. Such a dependency is called a **partial dependency**.
>
> • X is not a proper subset of any key. Such a dependency is called a **transitive dependency**, because it means we have a chain of dependencies K-\>X-\> A.

You have given one correct definition of 3NF a few lines above, and according to this definition the two cases are true **only** if A is not a prime attribute (that is, is not part of a key), otherwise the dependency *does* not violate the 3NF.

So the answer to the question which is title of your post: “Are all relational schemas with partial dependencies not in 3NF?” is **NO**.

> Am I correct that "Figure 19.7 Case 1" and "Figure 19.8 Case 1" are not 3NF, while "Figure 19.8 Case 2" is 3NF?

Yes, if you mean that in these cases the dependencies do not violate the 3NF.

> Why is there no either "Figure 19.7 Case 2: A in KEY" or "Figure 19.7 Case 2: A in KEY1" where "KEY1" is different from "KEY"? Does that case exist?

Yes, both cases could exists: in general in a relation scheme there can be multiple candidate keys (and possibly with empty intersection).

> Am I correct that
>
> If that case can exist, it will be 3NF.
>
> If that case can't exist, all relational schemas with partial dependencies are not in 3NF?

Since both cases can exists, the relevant dependencies do not violate the 3NF, while it is incorrect the assertion that “all relational schemas with partial dependencies are not in 3NF” (if a partial dependency determines a prime attribute, than it does not violate the 3NF).
> 1 votes

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


# Question
Title: Reinforcement Learning: An Introduction, A Gambler's Problem, Exercise 4.7 Solution
Currently reading a recent draft of Reinforcement Learning: An Introduction by Sutton and Barto. Really good book!

I was a bit confused by exercise 4.7 in chapter 4, section 4, page 93, (see attached photo) where it asks you to intuit about the form of the graph and the policy that converged. I do not understand why this policy is as it is, and was wondering if anyone has any insight into the problem or answers for this exercise in the book.

I have so far look extensively around Google for answer booklets or any work on the problem to no avail. I could not resolve why s=50 would be a bound with a high a=50 when surely any similar policy could be applied to s=51 with a=49? Any help is much appreciated, many thanks!

# Answer
> 3 votes
The question, as written, certainly suggests that it's a "good policy" to bet a=50 for s=50 , while not "betting it all" with a=49 for s=51. However, in an e-mail discussion surrounding this (here), Daniel Loeb asks a similar question and notes, "in particular, the simple policy of always making the largest allowed bet is optimal", which would suggest that betting 49 at s=51 would be fine. Andy Barto replies and seems to endorse this conclusion.

Perhaps, if we forget that by construction you can't bet a=51 when s=51, then you could interpret "betting it all" to be betting a=51 when s=51, which is clearly sub-optimal, because your goal is only to reach 100, not to exceed it, and there's no reason to risk complete ruin (loss of the entire stake). So in that sense, it makes sense to "bet it all" when s=50 but obviously not when s\>50. But this is just speculation.

# Answer
> 1 votes
The best policy, known as *bold play* and figured out by Dubbins and Savage, is to always gamble as much as possible (but not more than is necessary to reach the goal). See for example an exposition by Kyle Siegrist, How to gamble if you must.

---
Tags: dynamic-programming, reinforcement-learning
---


# Question
Title: Time complexity of arithmetic operations
I want to calculate the time complexity of the listed algorithms, please correct if I'm doing something wrong: The question is, do some operations like multiplying, dividing, or plus really affect on time complexity ?

```
// Time complexity is O(log n)
    void calculate(n: Int) {

        while (k < n) {
            k *= 2 //or k *= k
        }
    }

// Time complexity is O(n)
void calculate(n: Int) {

    while (k < n) {
        k += 1000
    }
}

//Time complexity is O(log n)
void calculate(n: Int) {

    k = n

    while (k > 1) {
        k /= 4
    }
}

```

# Answer
> 6 votes
Your question is excellent! Unfortunately, my answer might disappoint you: the complexity of arithmetic operations depends on the computation model; to some extent, it's up to you to decide how much does it cost to add or multiply two numbers. Usually when analyzing algorithms, we assume the *unit cost RAM* model, in which arithmetic operations on two "reasonably sized" integers takes time $O(1)$. Here "reasonably sized" means of length $A\log n$, or equivalently, of absolute value at most $n^A$ (here $n$ is the size of the input). The constant $A\>0$ should be fixed per algorithm. Its exact value doesn't matter, since we can simulate arithmetic operations on operands of size $m^2$ using $O(1)$ arithmetic operations on operands of size $m$.

In some cases, we have to do arithmetic on large integers. This happens in cryptography, for example. When adding or multiplying large numbers, operations no longer take $O(1)$ even in the unit cost RAM. For example, adding $m$-bit integers takes time $\Theta(m)$, and the best known algorithm for multiplication runs in $\tilde{O}(m\log m)$ (the tilde hides smaller multiplicative factors).

In most elementary algorithms, large integers do not show up, so you can just assume that arithmetic operations on variables take constant time. This is intended to be the case in all your examples.

---
Tags: time-complexity
---


# Question
Title: Is the complement of every non Turing recognizable language a Turing recognizable language?
One thing I understand is that the complement of every Turing recognizable(but not decidable) language is non Turing recognizable.

What about the complement of non Turing recognizable language? Is the complement of every non r.e a recognizable language.

I don't know how to approach this problem.

But one idea I had was this:

If the complement of every non r.e were a r.e language then there would be a bijection from r.e to non r.e. This bijection maps a r.e to a non r.e . The set of r.e languages is countable(even though infinite). If a bijection exists then non r.e would also be countable. But the union of r.e and non r.e is uncountable. This means one of them must be uncountable. So the original supposition must be wrong.

I am new to coutability and such things. So it may be possible that the idea is compeletely wrong.

Anyhow can someone provide an approach to this problem.

# Answer
Your proof is fine. There are also explicit languages which are neither r.e. nor co-r.e., for example the language of all total Turing machines (Turing machines halting on every input).

In fact, the language of all total Turing machines is $\Pi\_2$-complete, which means, in a sense, that there is no better way to "solve" it than to run all on inputs and see whether the given machine halts on each of them (of course, you can't do this with a Turing machine, but perhaps with a more powerful device...). Take a look at the arithmetical hierarchy for more on this.
> 2 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: FA for w when length of w is even or divisible by 3
I want to construct a FA for the language

$\\{w \in \\{a,b\\} | $length of w is either even or divisible by 3$\\}$.

I've been playing around with some FAs, but I can't seem to create one that does the job. I can easily create one that accepts words with even length, and also one that accepts words with lengths divisible by 3, but I am unable to combine these.

This is my attempt:

# Answer
You're very close, you need to add one more node,and to add another final state for $q\_0$ because that the length of empty string equal to zero which is even. try this:

I made some tests:

Hope this help.
> 0 votes

# Answer
A simpler solution is to use a DFA with 6 states which count the number of letters seen so far, modulo 6. This is a DFA with 6 states $q\_0,\ldots,q\_5$, and transition function $\delta(q\_i,\sigma) = q\_{i+1 \bmod{6}}$. The accepting states are $\\{q\_0,q\_2,q\_3,q\_4\\}$, since a number is even or divisible by 3 iff its residue modulo 6 is one of 0,2,3,4.

Using Myhill–Nerode theory, you can easily show that this is the minimal DFA for the language. Using an NFA with multiple initial states, you can improve this to 5 states: have two starting states $q\_0^{(2)},q\_0^{(3)}$ which also double as accepting states, states $q\_1^{(2)},q\_1^{(3)},q\_2^{(3)}$, and transitions $\delta(q\_i^{(m)},\sigma) = \\{q^{(m)}\_{i+1 \bmod{m}}\\}$. This is likely the minimal number of states for this type of NFA.
> 3 votes

---
Tags: finite-automata
---


# Question
Title: Figuring out whether LL(1) grammar has an $\varepsilon$-free variant
This question arose out of a concrete problem I had, which was to find an $\varepsilon$-free variant of the following LL(1) grammar $G\_0$ that I developed for a Lisp-like language $L$ (I found a monotone LR(0) variant):

$$ \begin{array} \\ P & \rightarrow & (EP \\ & | & \varepsilon \\ E & \rightarrow &iE \\ & | &sE \\ & | &nE \\ & | &(EE \\ & | &) \end{array} $$ where the start symbol is $P$. With this grammar, the leftmost derivation of $\omega = (i()sn)(inn)$ is $$ \begin{array} \\ P & \Rightarrow\_L (EP \\ & \Rightarrow\_L (iEP \\ & \Rightarrow\_L (i(EEP \\ & \Rightarrow\_L (i()EP \\ & \Rightarrow\_L (i()sEP \\ & \Rightarrow\_L (i()snEP \\ & \Rightarrow\_L (i()sn)P \\ & \Rightarrow\_L (i()sn)(EP \\ & \Rightarrow\_L (i()sn)(iEP \\ & \Rightarrow\_L (i()sn)(inEP \\ & \Rightarrow\_L (i()sn)(innEP \\ & \Rightarrow\_L (i()sn)(inn)P \\ & \Rightarrow\_L (i()sn)(inn) \end{array} $$ My problem is that the parser generated by this grammar accepts the empty string, and I would like to exclude that.
So I am looking for an $\varepsilon$-free LL(1) grammar $G\_1$ that generates $L-\\{\varepsilon\\}$. I have tried several times without success, leading me to doubt whether $L-\\{\varepsilon\\}$ is simple deterministic.

# Answer
> 0 votes
The solution is to simply start in a slightly different starting state before starting the main recursion:

$$ \begin{array} \\ S & \rightarrow & (EP\\ P & \rightarrow & (EP \\ & | & \varepsilon \\ E & \rightarrow &iE \\ & | &sE \\ & | &nE \\ & | &(EE \\ & | &) \end{array} $$

---
Tags: formal-grammars
---


# Question
Title: Find minimum set of vertices that are reachable from all other vertices
I have a DAG and I wish to find the minimal set of vertices that have a path to all other vertices.

My solution was to simply find all the vertices that their incoming degree is 0. However, if there are two vertices in the DAG that have an indegree of 0 and that point to a common vertex then one of the two vertices is surplus.

Any help appreciated.

# Answer
Your algorithm is correct, provided that the following is a formal definition of your problem:

> Given a DAG $D = (V, A)$, find a minimum set $C \subseteq V$ such that for every vertex $v \in V$, either $v \in C$ or there exists a vertex $c \in C$ such that $v$ is reachable from $c$.

Let's call a vertex with indegree 0 a *source* and any vertex set that satisfies the reachability part a *cover*.

Claim. The optimal solution is $C = \\{v \in V \mid v \text{ is a source}\\}$.

Claim 1. $C$ is a solution. Trivial since $D$ is a DAG.

Claim 2. Every vertex $c \in C$ is in every cover. Since it has indegree 0 it cannot be reached by any other vertex.
> 2 votes

---
Tags: graphs, dag
---


# Question
Title: Why are these states equivalent on this translation table
Full disclosure: I am trying to understand an answer from the Stanford Automata MOOC.

Why are states F and G equivalent here, such that they would get merged in a minimization process? They both differ on their transitions on 0, so I thought they were distinguishable?

```
    0   1
->A E   D
*B  A   C
C   G   B
D   E   A
*E  H   C
F   C   B
G   F   E
H   B   H

```

# Answer
```
The two states F and G on similar inputs leads to a final state.
     w(F)+0*1 = w(final-state);
     w(G)+0*1 = w(final-state);
Here, w(X) is the string that leads to the state X, and
      + is concatenation operator.

```

Due to the above proposition, it is clear that the two states behave in the same manner and the system's functionality will be unaffected because of merging of these states.
> 3 votes

# Answer
When you say equivalent you need to keep in mind to look if there is no word in length k that separates them.

Moreover you you can see that for a word in length 1 :

$If w\_1 = 1 $ then F and G enter accepting states B and E

$If w\_1 = 0$ then F and G enters a non accepting state C And F

There for they are equivalent for word in length $k=1$

For minimization check this reference: https://www.tutorialspoint.com/automata\_theory/dfa\_minimization.htm
> 0 votes

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


# Question
Title: What is an extremely basic asymmetric cipher that I can present at the pub?
I'm trying to explain the basics of Bitcoin to my parents.

One of the core components of bitcoin, is signing transactions to make sure your identity can't be impersonated, and thus the need to explain a simplified asymmetric cipher.

What's an extremely simple asymmetric cipher I can use as an example?

How can this simplified cipher be used for signing?

# Answer
> 28 votes
If you want to present public key cryptography to your parents or friends, then I suggest you follow some guidelines. First, don't talk about specific functions, nobody cares about SHAxxx, keep your talk conceptual. The problem solved by public key cryptography is allowing two parties who never met before to securely exchange information in a public channel. Do not confuse this with other applications that are achieved by public key encryption, such as digital signatures or authentication.

An illuminating simple illustration of this that I have seen is the following. Suppose that two parties have a bucket and a number of colors, and they want to agree on a specific secret compound. They are allowed to send each other a bucket with a certain compound, but anything sent is exposed to an evil adversary. The underline assumption is that mixing colors is easy, but decomposing a mixture to its ingredients is hard. This assumption (which is easily connected to the formal side of things) allows you to achieve their goal. Pick a public color $P$, and allow both parties to pick a secret color, let us denote them by $S\_1,S\_2$. The first party then sends a bucket of a mixture of $P,S\_1$. Similarly, the second party sends a bucket containing a mixture of $P,S\_2$. Finally, each side adds his private color to the mixture he received, and now both parties have a mixture of $P,S\_1,S\_2$, which (by our assumption) remains secret from any eavesdroppers. A formal version of this is the Diffie-Hellman key exchange protocol, which relies on the hardness of discrete log.

Now, my understanding of the bitcoin protocol is limited, but when talking to your parents about it, I see no reason to go into cryptography. Most of the popular explanations I have seen unnecessarily delve into implementation details, and start talking about finding a preimage of a hash such that the result would have $x$ number of zeros, loosing sight of the actual problem. As before, I suggest to keep the talk conceptual. What problem is the bitcoin trying to solve, and why isn't this trivial? To my understanding, the bitcoin solves the problem of maintaining a distributed ledger, specifically avoiding the double spending problem. The motivation is to avoid having a central authority, and this can be achieved by allowing each participant to approve a transaction (instead of giving this authority to the bank). To avoid adversarial participants approving their own invalid transactions, the concept of proof of work is introduced. POW uses the hash as a black box, so you can avoid mentioning specific candidates.

# Answer
> 15 votes
A common metaphor I hear used is manufacturing a bunch of padlocks, keeping all the keys, and sending out open padlocks to anyone who wants one. Then anyone with such a padlock can send you secret messages by putting them in a box and then using one of your padlocks to lock it before sending it to you. No-one but you has the keys, so even the sender can't unlock the box after it's locked – in particular, the postal service can't snoop on your message at all. They might even have a padlock from you too, but that doesn't help them unlock the box.

(I provide this example to answer your question as stated, without any particular opinion on whether it's actually useful for the bitcoin explanation.)

# Answer
> 7 votes
The problem with explaining asymmetric cyphers (and the reason why most pop explanations actually fail to explain anything) is that they are entwined with the idea that there exist problems that are (supposedly) intractable, which is one of the ideas behind computational complexity.

Once you get that point across, an asymmetric cypher is "just" a function that is easy to compute but thought to be hard to invert. You could even make your own, see the Diffie-Hellman key exchange original implementation as a reference.

# Answer
> 4 votes
I don't think there is an easily demonstrable asymmetric encryption system. Instead, describe *what* it does, not *how* it does it. In fact, I've had to do this recently, to describe how PGP works. For BitCoin, concentrate on the second part, signing messages.

> I can create two related numbers. One is called the *private key*, the other the *public key*. I keep the first secret, and tell everyone the second. Anyone who wants to send me a message takes my public key, and encrypts their message with it. Once that is done, no one can decrypt the message, not even the sender. When I receive the message, I can decrypt it with my private key.
>
> Or, I can encrypt a message with my private key, and send both the encrypted and non-encrypted message to a second person. If they have my public key, then they can decrypt the encrypted part of the message, and it will be the same as the non-encrypted part. This shows that I was the person who encrypted the message.

If they ask how the keys are generated, then say

> I think of two very large prime numbers, and then transform them through a mathematical function. It spits out the private and public keys.

This is of course, glossing over the fact the asymmetrical encryption normally doesn't work on the message itself, instead on a session key (for encryption), or on a hash (signature verification). It also ignores the very important requirement that you *must* keep your private key private - anyone with access it to can pretend to be you.

---
Tags: cryptography
---


# Question
Title: Finding lower bounds for data structures with non-standard interfaces
Consider the problem of designing a data structure that provides the interface functions $\rm{pop}, \rm{push}, \rm{findmin}$, all running in constant time. This problem may be solved by (e.g.) having the $\rm{push}$ method compute the new minimum as well, and place it on the stack together with the pushed element.

Is there any systematic approach to determining lower bounds (of time and space complexity) for data structures exposing a given set of interfaces? E.g. $\rm{push,pop,sort, insertAtIndex}$? Can you provide links to relevant literature?

# Answer
> 4 votes
Data structure lower bounds is a full-fledged area in theory of computation. The main model of computation on which the lower bounds are proved is the cell probe model, which counts the number of memory accesses, but for which computation is free. For an overview of how things stood in 2008, you can take a look at Mihai Pătraşcu's thesis. Tragically, Pătraşcu died from brain cancer in 2012 at the age of 29.

---
Tags: complexity-theory, data-structures
---


# Question
Title: Are time complexity of followng codes equivalent?
Implemented is done in C++.

Supposing we have defined a class `T` with no restrictions and three functions `cond`, `next` and `f` returning `bool`, `void` and anything respectively, are

```
for(T k = T(); cond(); next())
    f();

```

and

```
{
T k = T();

while(cond()) {
    f();
    next();
}
}

```

So, I would like know that time complexity of the following algorithms are same?

# Answer
> 0 votes
I'm not familiar with `C++` but it looks like that both codes are equivalent, `for` loop and `while` loop has the same power.

In your examples, in both cases you first you initial the variable `k`, and the loop doesn't stop as `coud()` condition holds, inside the loop there is a call to `f();` method, and finally to `next();`.

# Answer
> 0 votes
As your code stands, yes they are algorithmically the same in that both have a starting state, a condition, and an incrementing step.

The difference between the two would be if the code within the body of the `for` and the `while` had a `continue` statement. With a `for` the `continue` statement would cause the `next()` to be executed before the condition is checked since the `next()` is part of the `for` and not part of the body of the `for`.

However with the `while` a `continue` statement that is before the `next()` would cause execution to jump to the end of the `while` body which would bypass the `next()`. This would result in `next()` not be called with a possible infinite loop. This is because the `next()` is within the body of the `while`.

---
Tags: algorithms
---


# Question
Title: If $f(n)=\Omega(g(n))$ and $h(n)=\theta (g(n))$ then does this implies $f(n).g(n)=\Omega(g(n).h(n))$?
If $f(n)=\Omega(g(n))$ and $h(n)=\theta (g(n))$ then does this implies $f(n).g(n)=\Omega(g(n).h(n))$

I saw a proof where they have proved If $f(n)=O(g(n))$ and $h(n)=\theta (g(n))$ then this implies $f(n).g(n)=O(g(n).h(n))$.

So I thought may this should also hold. I have taken some examples and the formula holds on all of them. However I can't be sure. There can be a contradicting case.

# Answer
> -1 votes
I have got the answer. It's easy.

Since $f(n)= \Omega g(n)$

$cg(n)\le f(n)$

Multiplying both sides by h(n)

$cg(n).h(n)\<=f(n).h(n)$

$f(n).g(n)=\Omega(g(n).h(n))$

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


# Question
Title: Is there a concept for an algorithm computing a function by first finding another algorithm?
If I understand it correctly, an algorithm that computes the value of a real function $f$ has computational complexity $O(g(n))$ if the following holds: When we compute $f$ to precision $\delta$ requires on the order of $g(n)$ steps.

However, what if we have an algorithm that first "finds a more efficient algorithm to compute $f$", and then computes $f$?

> In other words, what if we have an algorithm $A$ that does the following:
>
> 1. Find an efficient algorithm $B$ for computing $f$.
> 2. use $B$ to compute $f$.

In that case, we can no longer speak of the computational time it would take to compute $f(5)$ for example, because it fully depends on whether Algorithm $A$ has already found algorithm $B$. In other words, the computing time required to compute $f(5)$ if $5$ is the first comoputed number is far greater than the computational time required to compute $f(5)$ after $f(3)$ is already computed.

My question is, **is there a concept/theory about this kind of algorithm that first finds another algorithm before computing a function?** Specifically I am wondering about analysis of the computational complexity of such algorithms.

# Answer
> 18 votes
There is a well-known algorithm, Levin's universal search algorithm, whose mode of operation is identical. Consider for example the problem of finding a satisfying assignment for a formula which is guaranteed to be satisfiable. Levin's universal search runs all potential algorithms in parallel, and if any algorithm outputs a satisfying assignment, stops and outputs this assignment. If the optimal algorithm for the problem runs in time $f(n)$, then Levin's algorithm runs in time $O(f(n))$ (with a possibly huge constant) if implemented correctly.

While Levin's algorithm is impractical (due to the huge constants involved), it is very interesting theoretically. See the Scholarpedia article for more on universal search.

# Answer
> 10 votes
Suppose we have a function `f` which takes an argument `x` of type `A`, and outputs another function which takes an argument `y` of type `B` and returns a result of type `C`. In your words, `f` takes an argument `x` and returns an "algorithm" which takes inputs of type `B` and outputs results of type `C`.

The function `f` has the type

```
A → (B → C)

```

Indeed, it takes `x : A` and returns a function of type `B → C`. But such an `f` is equivalent to a function `g : A × B → C` which takes *both* `x` and `y` at once and gives you the final result. Indeed, there is an isomorphism between the types

```
A → (B → C)

```

and

```
A × B → C

```

because we can define `g` in terms of `f` as

```
g(x, y) := f(x)(y)

```

and we can define `f` in terms of `g` as

```
f(x) := (y ↦ g(x,y))

```

The operation of passing from `g` to `f` is called currying and functional programmers use it all the time. In computability theory the idea of taking one input and outputing a function (algorithm) is emboddied in the s-m-n theorem.

The answer to your question is "yes, people do this all the time". But there is also a moral: an algorithm which finds an algorithm is still just an algorithm.

---
Tags: complexity-theory
---


# Question
Title: Explanation of the Gelfond Lifschitz reduct
Can someone explain with a hands on example how the Gelfond Lifschitz reduct works in order to check stable model semantics?

# edit

a simple example here - at least as far as I understand the thing. So far grounding is clear to me - but the the application of the reduct is not. My goal in the end is to check stable model semantics of a program `P` and a supplied model `M`

Let `i`, `j` be constant symbols and `X`, `Y` be variables. Consider

```
d(X,Y,Z) :- a(X), b(Y), c(Z).
c(X) :- a(X), not b(X).
a(i).
b(j).

```

Decide using the Gelfond-Lifschitz reduct whether the interpretation `I = {a(i), b(j), c(i), d(i, j, i)}` is a stable model of `P`. Then the grounding looks like:

```
a(i).
b(j).
c(i):- a(i), not b(i).
c(j):- a(j), not b(j).
d(i,i,i) :- a(i), b(i), c(i).
d(i,i,j) :- a(i), b(i), c(j).
d(i,j,j) :- a(i), b(j), c(j).
d(j,j,j) :- a(j), b(j), c(j).
d(j,j,i) :- a(j), b(j), c(i).
d(j,i,i) :- a(j), b(i), c(i).
d(j,i,j) :- a(j), b(i), c(j).
d(i,j,i) :- a(i), b(j), c(i).

```

Now I start to apply the reduct. To me only the simple bits are clear:

```
P = {a(i), b(i), ... unclear part}

```

What is lacking & unclear to me: \- removal of default negations \- removal of not applicable formulas

# Answer
> 1 votes
Due to `b(j).`, `c(j):- a(j), not b(j).` is not applicable and needs to be removed. As all negated literals are deleted, `c(i):- a(i), not b(i).` is converted to `c(i):- a(i).`
Therefore, as `I = {a(i), b(j), c(i), d(i, j, i)}` is minimal representation of the remaining `P`, it is also stable.

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


title: Why doesn't this put $BPP$ in $NP$?

text:
# Question
Title: Why doesn't this put $BPP$ in $NP$?
From Sipser Gacs we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists t\_1,\dots,t\_{|r|}\forall r\in\\{0,1\\}^{|r|}\vee\_{i\in\\{1,\dots,|r|\\}}M(x,r\oplus t\_i)=1.$$

From Adleman we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists r\in\\{0,1\\}^{|r|}M(x,r)=1.$$

> 1. Why is this just $BPP\subseteq P/Poly$ (looks like a derandomization to $BPP\subseteq NP$)? If Adleman's theorem just puts $BPP\subseteq P/Poly$ (because we need to find $r$) then why cannot I argue for similar reasons Sipser Gacs only puts $BPP\subseteq coNP/Poly$ (because we need to find $t\_1,\dots,t\_{|r|}$)?
> 2. What should Adleman's theorem have looked like if it indeed showed $BPP\subseteq NP$ and what should Sipser Gacs' theorem have looked like if it indeed showed $BPP\subseteq coNP/poly$?

# Answer
Adleman's theorem states that you can amplify the success probability of $M$ so that there will be a single choice for the random string $r$ that works for all $x$: $$ \exists r \forall x : x \in L(M) \Leftrightarrow M(x,r) = 1. $$ (Here $x$ goes over all inputs of length $n$, and $r$ goes over all possible random strings that $M$ requires for inputs of length $n$.)

Unfortunately, it's not clear how to find $r$, and even worse, if I give you $r$, it's not clear how to verify that it satisfies the property stated above. This is why we have to supply it as advice.

The Sipser–Gács theorem similarly states a different property from what you list. It states that if $M$ is a BPP machine then $$ \forall x \bigl(x \in L(M) \Longleftrightarrow \exists t\_1,\ldots,t\_{|r|} \forall r : M(x,r \oplus t\_1) = 1 \lor \cdots \lor M(x,r \oplus t\_{|r|}) = 1 \bigr). $$ Here the strings $t\_i$ could depend on the input $x$. This is why you get $\Sigma\_2^P$ or $\Pi\_2^P$ rather than $\mathsf{NP}/\mathsf{poly}$ or $\mathsf{coNP}/\mathsf{poly}$.

---

Summarizing, you have to be careful with quantifiers when stating a theorem. Changing the order of the quantifiers could drastically change the meaning.
> 4 votes

---
Tags: complexity-theory, logic, complexity-classes, randomized-algorithms, randomness
---


# Question
Title: Proving that a class of languages is a subset of RE for Rice Theorem
> Consider language $L = \\{\<M\> |L(M) \subseteq L(0(0\cup1)^\*) \\}$ where $\<M\>$ is a valid encoding of a turing machine.

I know that the language is applicable for Rice Theorem. Now, I understand that in this case the language group in $RE$ is:

$C = \\{L\subseteq \Sigma^\*|L\subseteq L(0(0\cup1)^\*)\\}$

However, I'm not sure how to prove that each of these languages is in the $RE$ class. Note That an alphabet wasn't given in the exercise so I guess that there can be other letters. I thought at first it had something to do with the languages being subests of a regular language, but then again $\Sigma^\*$ is a regular language and all other languages are its subsets.

# Answer
You missed a tiny detail when defining $C$: all those languages are RE *by assumption*; no other language can be an $L(M)$!

Let us again look at the language you want to say something about:

$\qquad L = \\{ \langle M \rangle \mid M \text{ is a TM}, L(M) \subseteq L\bigl(\\, 0(0\cup1)^\* \\,\bigr) \\}$.

We see that $L \subseteq \Sigma^\*$ for some alphabet $\Sigma$ that depends on the TM encoding $\langle \\\_ \rangle$.

Now recall the statement of Rice's theorem: the index set

$\qquad \Phi(X) = \\{ \langle M \rangle \mid M \text{ is a TM}, L(M) \in X \\}$

of a language class $X$ is undecidable if $\emptyset \subsetneq X \subsetneq \mathrm{RE}$.

Now, it is obvious (read: very easy to prove -- your exercise) that $L = \Phi(C)$ with

$\qquad C = \\{ Y \in \mathrm{RE} \mid Y \subseteq L\bigl( 0(0+1)^\* \bigr) \\}$;

the requirement $\emptyset \subsetneq C \subsetneq \mathrm{RE}$ is likewise trivial.

We don't get to "just say" anything; we have to prove all three conditions -- $L = \Phi(C)$, $\emptyset \subsetneq C$, and $C \subsetneq \mathrm{RE}$ -- but it so happens that all three proofs are very easy here since $L$ has been defined in a very suitable way. For other languages, the proofs can be more intricate (or impossible; then Rice's theorem does not apply).

---

Side note: If we consider

$\qquad C' = \\{ Y \in \Sigma^\* \mid Y \subseteq L\bigl( 0(0+1)^\* \bigr) \\}$

then we also get $\Phi(C') = L$! While there are non-RE $X$ in $C'$ (a simple if non-constructive argument is that there are uncountably many such $X$), $\Phi$ "ignores" them. However, $C'$ does not fulfill the conditions of Rice's theorem so we can not use it.
> 2 votes

---
Tags: turing-machines, computability, rice-theorem
---


# Question
Title: Is there a way to efficiently parse this grammar?
Consider the following context-free grammar:

> $T \to (\*) \mid (T\*) \mid (\*T) \mid (T\*T)$

This effectively forms a notation for binary trees: A binary tree is a $\*$, with optional children on either side, all surrounded by $()$. This is clearly unambiguous, because you can distinguish between the presence and absence of a tree, and you can determine where a tree begins and ends.

Now consider the same grammar, except that it does not distinguish between opening and closing parenthesis:

> $T \to aba \mid aTba \mid abTa \mid aTbTa$

Here, we have replaced both $($ and $)$ with $a$ (and $\*$ with $b$).

After trying several examples, I believe that this grammar is unambiguous. For example, the string $aaabababaabaababaa$ parses as $(a(a(aba)b(aba)a)b(a(aba)ba)a)$.

However, I don't see an efficient way to parse it. The general idea I had was to go as follows:

* The string must start and end with $a$.
* If the second character from the start is $b$, recursively parse the part after it, all the way to the second character from the end.
* If the second character from the end is $b$, recursively parse the part before it, all the way to the second character from the start.
* If the second character from both the start *and* end is $b$, we have a malformed expression.
* If both characters from the start and end are $a$, then... what?

Here it seems that we would have to create a choice point and use a backtracking method to find it. However, this method would have exponential runtime for many pathological inputs, such as $aababababababababababaa$.

Is this grammar unambiguous? If so, is there a way to parse this grammar that avoids pathological exponential runtime for most inputs?

# Answer
> 4 votes
The grammar is ambiguous: (I used `|` for `a` and `*` for `b` because I find it easier to read.)

```
||*|*||*|*||
((*(*))*(*))
((*)*((*)*))

```

However, you can use an Earley grammar to find all possible parses in worst-case cubic time. (As long as you are satisfied with a graph representation of "all possible parses" since the maximum number of parses of a string of a given size is exponential.)

---

I found this example by using a bison GLR grammar and iterating over inputs until I found one which produced an ambiguity. Out of laziness, I produced the list of inputs by generating all strings consisting of $n$ `|` and $n$ `*|` where the first element is `|`. Most of these inputs are syntax errors, but for small $n$ it doesn't matter.

Here's a simpler approach, using Python to generate valid inputs:

```
def gen(s, n):
  """Generate left-most derivations of 's' with maximum length 'n'"""
  if n > 0:
    i = s.find('T')
    if i == -1:
      yield s
    else:
      yield from gen(s[:i]+'|*|'+s[i+1:], n)
      yield from gen(s[:i]+'|T*|'+s[i+1:], n-1)
      yield from gen(s[:i]+'|*T|'+s[i+1:], n-1)
      yield from gen(s[:i]+'|T*T|'+s[i+1:], n-2)

```

If this function generates the same string twice, that string is ambiguous since it has two left-most derivations.

---
Tags: algorithms, context-free, parsers
---


# Question
Title: Not getting the clear picture of Goto actions , reduce and shift actions in SLR Parsing
I am going through the following lecture notes on LR parsing :

https://www3.nd.edu/~dthain/courses/cse40243/fall2016/chapter4b.pdf

For the following grammar :

The following LR automation has been done :

and the following is the LR parsing table drawn for it :

In the table I can see that the alphabets "R" ,"G" and "S" denote the action being taken and the number following them is the index number of the state to which the transition is taking place .

Now , what I am unclear about is what exactly is a "goto"action ? I can see that goto actions , "G1" , "G8" , "G3", "G6" are occurring only in response to non- terminals "'E" and "T" . And all of them have two rules by using which we can reduce the expression to the start symbol.

But I am unable to draw any further patterns to interpolate what exactly is a "Goto action " .

Nevertheless , when at state 4 an input of "(" results in shift but how does an input of ")" or "+" result in reduction , which I ,with certain degree of confidence, guess to be , the action of replacing few symbols with the left hand side of certain production .

So , how exactly to make sense of this table ? What exactly is a GOto and am I right about "reduction"?

# Answer
> 0 votes
Remember that a stack entry is a state and a symbol. (In fact, the symbols are not really important for the parser, but they will prove useful later on when you encounter semantic values.)

A reduction action consists of popping the right hand side of a production from the top of the stack and pushing the left hand side. (The number in the reduction action is the number of the production, so you know what the left- and right-hand sides are.)

When the right hand side is popped off the stack, a new state is revealed (at the top of the stack). The Goto action which corresponds to that state and the left-hand side non-terminal tells you which state to push along with the non-terminal.

The parser's actions are illustrated in the chart at the end of section 4.8 of your text, which I reproduce below. However, the reduction and subsequent goto action are combined in the chart:

```

Stack         Symbols       Input             Action
0                           id ( id + id) $   shift 4
0 4           id            ( id + id ) $     shift 5
0 4 5         id (          id + id ) $       shift 4
0 4 5 4       id ( id       + id ) $          reduce T → id
0 4 5 8       id ( T        + id ) $          reduce E → T
0 4 5 6       id ( E        + id ) $          shift 2
0 4 5 6 2     id ( E +      id ) $            shift 4
0 4 5 6 2 4   id ( E + id   ) $               reduce T → id
**0 4 5 6 2 3   id ( E + T    ) $               reduce E → E + T**
0 4 5 6       id ( E        ) $               shift 7
0 4 5 6 7     id ( E )      $                 reduce T → id ( E )
0 8           T             $                 reduce E → T
0 1           E             $                 accept

```

Let's look at what the parser does at the highlighted line in the above chart. We can see that the parser is in state 3 (which is the state at the top of the stack) and is about to perform a reduction. The right-hand side of the production to be reduced has three symbols – `E + T` – which we can also see at the top of the stack (in the Symbols column). So the first thing the parser does is pop the right-hand side of the production:

```
**0 4 5 6 2 3   id ( E + T    ) $               pop E + T**
```

Now, the parser is in state 5 and needs to do something with the `E` which was just reduced (that is, the left-hand non-terminal in the reduced production).

```
**0 4 5         id (          ) $               push E**
```

We consult the parser action chart, looking for the action for an `E` corresponding to state 5. That action is `G6`, meaning that the parser pushes state 6 onto the stack with the symbol `E`, giving us the next line:

```
**0 4 5 6       id ( E        ) $               shift 7**
```

Aside from the fact that it's a non-terminal rather than a terminal being pushed onto the stack, there is no difference between a shift and a goto action. Of course, the goto action does not consume the lookahead symbol, so that symbol is then used in the new state (resulting, in this case, in a shift action).

---
Tags: compilers, parsers
---


# Question
Title: Probability of hash collision in the case of two parallel hashes
I understand how to calculate the probability of a hash collision.

I am designing a DB and have a potential case where a record could have the inherited hash of its parent plus its own hash, meaning I could potentially query two hashes to determine probable record matches.

If I have 1 billion records, a 64-bit hash will have $\sim 1:32.5$ collisions. If I have two by 64-bit hashes, how many effective bits will I have?

65-bits seems pessimistic, 128-bits seems optimistic. $\sim 32.5^2$ results in a fraction over 69 bits hash resolution.

How do I calculate this?

**ILLUSTRATION**

*Parent Table*

parent id, $\\{$ field $1$, field $2$, ... field $n \\}\implies$ parent hash

*Child Table*

child id, parent id, parent hash, $\\{$ field $1$, field $2$, ... field $n \\}\implies$ child hash

As illustrated, the child table has both `parent hash` and `child hash`. Two by 64-bit hashes.

# Answer
You can think of concatenating the two hash values and treating the result as a single hash. Then you have $n$ records, each of which has a single hash. The probability of a collision among $n$ hashes is roughly $n^2/2^{b+1}$, if the hash outputs a $b$-bit value. In your case if each of the two individual hashes is 64 bits long, after concatenation you have a 128-bit hash for the record, so $b=128$.

How did I obtain the formula $n^2/2^{b+1}$? It's an application of the birthday paradox, with $n$ people born on a planet that has $2^b$ days in the year (instead of 365 days). Or, if you prefer an intuitive argument: think of all ways to pick a pair of $b$-bit hashes. There are about $n^2/2$ pairs of hashes. For each one, there's a $1/2^b$ probability that those pair of hashes are equal (that they collide). So the total probability that at least one of these collide is about $n^2/2$ times $1/2^b$. This is a crude estimate that isn't totally accurate, but it turns out to be a reasonable approximation as long as $n^2/2$ is fairly small compared to $2^b$.
> 1 votes

# Answer
The distribution of hash collision lengths is binomial, but for a large enough problem, it's easier to use a Poisson distribution.

Suppose you are inserting $m$ pigeons into $n$ pigeonholes. Denote the load factor $\lambda = \frac{m}{n}$. Then for large enough $n$, the expected proportion of pigeonholes which receive $k$ pigeons is roughly:

$$\textit{Poiss}(\lambda; k) = \frac{e^{-\lambda} \lambda^k} {k!}$$

The expected number of pigeons which get their own pigeonhole is:

$$n \\, \textit{Poiss}(\lambda; 1) = m e^{-\frac{m}{n}}$$

And so the expected number of pigeons who have to share a pigeonhole is:

$$m (1 - e^{-\frac{m}{n}})$$

Plugging in your numbers, for $m = 10^9$ and $n = 2^{64}$, you would expect roughly $0.05$ items to be involved in a collision. For $m = 10^9$ and $n = 2^{128}$, the expected number of items to be involved in a collision is $3 \times 10^{-21}$.

One useful rule of thumb comes from the observation that there is a 50% chance of one or more collisions when $m (1 - e^{-\frac{m}{n}}) = 1$. (Remember, you need two items for an actual collision, so setting the expected number of items involved to 1 gives you half a collision.)

Using the approximation $e^{-x} \approx 1 - x$, we find $m \approx \sqrt{n}$. So if you have $n$ possible hash values, you have a 50% probability of one or more collisions after hashing $\sqrt{n}$ items.

This estimate is reasonably accurate for $n\>10$ or so. In your case, there are $2^{64}$ possible hash values, so there will be a 50% probability of one or more collisions after inserting around $2^{32}$ items.
> 1 votes

---
Tags: hash, hashing
---