# Question
Title: Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL?
Is the language $L=\\{a^nb^n\\} \cup \\{aa\*\\}$ DCFL OR CFL? The author says $L$ is CFL, but I am able to generate a Deterministic PDA for the corresponding language. I am naive in this subject and hence I am not sure whether its DCFL or CFL.

Can you provide an explanation that shows $L$ is either DCFL or CFL?

i dont know how to use math,i searched for the solution but didn't got any,my DPDA is shown in picture below.

# Answer
> 3 votes
Your PDA isn't deterministic, as it has moves for $q\_0, \epsilon, a$ and $q\_0, b, a$.

# Answer
> 0 votes
Of course $\\{ a^nb^n \mid n\ge 1\\}$ is a DCFL. Adding $a^\*$ to a DPDA for that language is straigthforward: as long as we did only read $a$'s that state we are in is final, after we read a $b$ the states are as in the original DPDA.

In this way we can show that the family DCFL is closed under union with regular languages. The construction simulates the original DPDA with a (deterministic) finite state automaton in parallel, using a product construction.

But there is a caveat. The original DPDA is deterministic, but it might end some of its computatuins in an infinite $\varepsilon$-loop. This will infinitely interrupt the simulation of the parallel finite automaton. Hence we need the requirement that the DPDA we start with has no such $\varepsilon$-loops. That is non-trivial, but as a normal-form it has been obtained in the construction for closure under complement for DCFL.

---
Tags: formal-grammars, parsers
---


# Question
Title: Clarification of Generalizing and Overfitting
To get to clarification of "generalizing" and "overfitting" I first must state the following: We have a robot, it makes guesses, and the way we know what guesses to keep is by if the received sensory input matches pre-installed senses that keep it alive/producing. The analog to my terms are training/test data and guessing and "?", correct? So now, it ends up saving better actions to pick up food, then a fork, if the actions are in their teen-age stage then they generalize and can pick up both food and a fork whereas if they are overfit then it only picks up a fork with too much precision. Is that what generalizing and overfit mean?

# Answer
No not exactly.

To be precise:

Generalisation means the ability of a machine-learning algorithm/device to match / process data it **has not seen before (but are in the domain of the problem)**, correctly.

Overfitting, is that state of learning where the algorithm is very tightly bound to the data it has seen (trained, tested) that **it cannot generalise well to data not seen before (but are in the domain of the problem)**.

So in this sense these are inter-related.

If you can clarify how the above relate to your use-case i can expand the answer.
> 2 votes

# Answer
No, not really.

## Generalization

Generalization means the ability to generalize from the training data to new situations you've never seen before. For example, suppose the robot has the following past experience:

* On Monday, it saw a plate of food and a cup of water on the table; it picked up a fork, and got a positive reward.
* On Tuesday, it saw a plate of food and a newspaper on the table; it picked up a fork, and got a positive reward.
* On Wednesday, it saw a newspaper and a bill on the table; it picked up a fork, and got no reward.
* On Thursday, it saw a bill and a plate of food on the table; it picked up a fork, and got a positive reward.

A machine learning algorithm might learn the rule "If you saw a plate of food on the table, pick up the fork." If it does, then (intuitively) we'd say it has generalized well.

For instance, suppose on Friday it sees a plate of food and a mosquito on the table, and based on the rule it has learned, it picks up the food. That would count as an example of generalization, because it has figured out what to do in a situation it hasn't seen before.

## Overfitting

Overfitting means a failure to generalize from the training data: it means the machine learning algorithm has learned something overly specific, that is overly specific to the training data, often to the point of finding spurious "patterns" that don't apply to future data. This typically causes future predictions to be wrong.

For example, suppose the robot has the following past experience:

* On Monday, it saw a plate of food on the table, it saw that the digital clock on the wall was showing 7:57, and it saw out the window that the weather was cloudy; it picked up a fork, and got a positive reward.
* On Tuesday, it saw a plate of food on the table, the clock showing 8:01, and sunny weather out the window; it picked up a fork, and got a positive reward.
* On Wednesday, it saw a newspaper on the table, the clock showing 7:49, and rain out the window; it picked up a fork, and got no reward.
* On Thursday, it saw a plate of food on the table, the clock showing 5:42, and the weather was overcast; it picked up a fork, and got a positive reward.

Now suppose that the machine learning algorithm learns the rule "If you see a plate of food on the table and either it's sunny or you see the digit 5 somewhere on the clock's display, then pick up the fork". That would be a case of overfitting: it has learned a spurious, overly specific pattern, one that is too closely based on the points in the training set. In real life, the weather and the digits showing on the digital clock should be irrelevant to the decision of whether to pick up a fork.
> 0 votes

---
Tags: machine-learning
---


title: Classifier optimization

text:
# Question
Title: Classifier optimization
Suppose we have a set E of entities. Each entity is described by a set P of binary properties (i.e. each element e of E has a defined true/false value for each element p of P).

|P| \>\> |E|

We now want to select a subset of fixed size (e.g., 10) of P that will enable us distinguish the elements in E as accurately as possible.

In extensions of this basic scenario, the properties could assume numeric values.

Has this problem been studied? Under what name?

A practical example: there is a set of 100 bacterial species that are characterized for the presence or absence of 1000 genes. We now want to select a subset of 10 genes that, upon typing of a novel sample, will tell us which bacterial species that sample represents.

# Answer
> 1 votes
If you need the optimal answer, the best solution I know is exhaustive search: try all ${|P| \choose 10}$ different subsets, and see which is best. The running time of this will be $O(|P|^{10})$, though, which is probably too high to be feasible.

Given this, you will probably need to accept solutions that are heuristics or not guaranteed to give an absolutely optimal answer.

One standard approach is to use a greedy algorithm: you iteratively build up a set of properties, one by one. At each step, if your set is currently $S$, you choose the property $p$ that makes $S \cup \\{p\\}$ as accurate as possible, and then add $p$ to $S$. To turn this into a full algorithm, you need to decide how you want to measure/evaluate each candidate $S \cup \\{p\\}$.

For comparison, you can look also at the ID3 algorithm. Rather than trying to pick a set of size 10, it tries to pick a decision tree of depth 10, so it's not solving exactly the same problem: but it is similar. The metric used at each step to evaluate the candidates is the information gain; you could do the same, but for a set rather than a tree.

In the machine learning literature, there is a lot of work on feature selection: given a large number of possible features, the goal is to pick a subset of the features that makes the classifier as accurate as possible. You could explore that literature and see if any of those methods are effective in your domain.

---
Tags: optimization
---


title: Need help understanding a decider

text:
# Question
Title: Need help understanding a decider
currently working through slides and I've noticed this which I believe to be an error.

Shouldn't the two DFA's be swapped around, so that the one that reaches the accept state is with L(M)=nothing is the accept state? If not could you explain why?

# Answer
> 2 votes
What these slides are describing is an algorithm (Turing Machine), which looks at a DFA and asks "does this DFA accept the empty language?"

So the diagrams in the slides are correct. If there is no path to an accepting state, then the answer is "yes, this DFA accepts the empty language," and our algorithm should output "true."

You would reverse the diagrams if you were writing an algorithm which was "test whether there exists some string that the given DFA accepts".

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


# Question
Title: Data structure to store sphere points (latitude,longitude) and retrieve all points within a distance
I have a set of thousands~millions of points on a sphere's surface, each with latitude, longitude.
I want to quickly get all points within a distance `d` of a particular sphere point `latC, lonC`.

* The points are mostly concentrated at places where humans go often.
* Some points have the exact same latitude and longitude.
* `d` is orders of magnitude smaller than the Earth's radius `r`, so using arc instead of distance is totally OK
* Getting a few extra points is OK (even a rectangle area instead of a circle area is better than nothing). Missing points is not OK
* No persistence needed.

What data structure would give these points quickly consistently, even if the set is large?

What I tried:

* Simple list: Checking all points is too slow.
* Quadtree on latitude, longitude: Does not find points around the poles.

# Answer
Geographic information systems use spherical triangular quadtrees to solve this problem. They are analogous to a quadtree, but defined over a sphere using triangular patches.

There are different variants with different bells and whistles, but you can refer to Quaternary Triangular Meshes (Dutton. "Encoding and Handling Geospatial Data with Hierarchical Triangular Meshes"), Sphere Quadtrees (Fekete. "Rendering and managing spherical data with sphere quadtree") and HTMs (Kunszt. "The Hierarchical Triangular Mesh") as approaches you can extrapolate from.

The basic idea is that you partition the sphere into coarse triangular patches, then subdivide those patches into smaller triangular patches recursively as needed. You can then perform basic queries like you would on a quadtree.

See Chen. "An Algorithm for the Generation of Voronoi Diagrams on the Sphere Based on QTM" for a survey of different techniques, and related problems.
> 4 votes

# Answer
Represent the points in *cartesian* coordinates (in 3D), and use square of distance (as it is cheaper to compute).
> 3 votes

# Answer
Use multiple quadtrees. Generate one quadtree based on lat-long. This has trouble at the poles (because the poles are "singularities", so pick a second lat-long-like coordinate system, but rotated 90 degrees, so the singularities are at two opposite points on the equator. Build a second quadtree based on that coordinate system. Now given any query, you can pick one of the two quadtrees and look it up in that quadtree: pick the quadtree that makes the query point as far away from the quadtree's singularities as possible.
> 2 votes

---
Tags: data-structures, sets
---


# Question
Title: Result of ANDing & ORing functions expressed as CDNF & CCNF
I came across following fact:

> If we AND two functions expressed as CDNF (Canonical Disjunctive Normal Form), then the result contains sum of commont minterms.

For example consider two functions $f\_1$ and $f\_2$ on three variables $A,B$ and $C$ expressed in CDNF. Then they will have eight minterms: $m\_0$ to $m\_7$.

If

$f\_1 = \sum ({m\_1,m\_2,m\_3}) = m\_1+m\_2+m\_3$ and

$f\_1 = \sum ({m\_2,m\_3,m\_4})=m\_2+m\_3+m\_4$

then,

$f\_1.f\_2=m\_2+m\_3$ as $m\_2$ and $m\_3$ are common in both $f\_1$ and $f\_2$.

However now I am thinking about what will be the result of

1. $f\_1+f\_2$

If we consider $F\_1$ and $F\_2$ on three variables $A,B$ and $C$ expressed in CCNF (Canonical Conjuctive Normal Form) as follows:

$F\_1 = \prod ({M\_1,M\_2,M\_3}) = M\_1.M\_2.M\_3$ and

$F\_1 = \prod ({M\_2,M\_3,M\_4}) = M\_2.M\_3.M\_4$

then what will be the result of
2. $F\_1.F\_2$
3. $F\_1+F\_2$

After some thinking, I came up with following:

1. $f\_1+f\_2$ will be

> union of minterms in both functions, that is sum of all minterms with the common minterm appearing only once.

Thus, $f\_1+f\_2 = m\_1+m\_2+m\_3+m\_4$
2. $F\_1.F\_2$ will also be

> union of the maxterms in both functions. That is the product of all maxterms with the common maxterms appearing only once.

Thus, $F\_1.F\_2=M\_1.M\_2.M\_3.M\_4$
3. I found it very tricky to think about $F\_1+F\_2$. In the end I felt it should be

> AND of OR of two different maxterms with no OR of same and common maxterms.

$\therefore F\_1+F\_2= (M\_1+M\_2)(M\_1+M\_3)(M\_1+M\_4)(M\_2+M\_3)(M\_2+M\_4)(M\_3+M\_4)$ So $(M\_2+M\_2)$ and $(M\_3+M\_3)$ will not be there.

as $f\_1.f\_2$ was

> OR of AND of two same and common minterms with no AND of different minterms.

So above $f\_1.f\_2$ was actually $m\_2.m\_2+m\_3.m\_3$. This because AND of different terms will be $0 (false)$ and $0+a=a$

However, if I am correct with $(M\_2+M\_2)$ and $(M\_3+M\_3)$ being not part of $F\_1+F\_2$, I don't understand why that would be. If I think as dual of "AND of different terms will be $0 (false)$ and $0+a=a$", it would be "OR of same terms will be $1 (true)$ and $1.a=a$". But I dont get **how OR of same terms will be 1?**

I am just trying to find some pattern here and didnt found this explained anywhere.

Q. Am I correct with these three guessings?

Q. If yes then I will like to know about above bold-faced question: how OR of same terms will be 1?

# Answer
There is no need to guess. Try to prove your guesses. If $f$ is the disjunction of minterms $\\{m\_i : i \in I\\}$ and $g$ is the disjunction of minterms $\\{m\_j : j \in J\\}$ then it is definitely the case that $f + g$ is the disjunction of $\\{m\_k : k \in I \cup J\\}$, but not all $m\_k$ are necessarily minterms. For example, $x + xy = x$.

Regarding $F+G$, try to use de Morgan's rules twice to reduce it to the case of $fg$, which is identical other than the operators involved. In Boolean algebra addition and multiplication are dual (via de Morgan's rules), so anything you can with CNFs you can also do with DNFs.
> 1 votes

---
Tags: logic, boolean-algebra
---


# Question
Title: Regular Expression representing the following language
I am having trouble understanding how to write a regular expression for the set of words that contain at least two *b*'s and at least two *a*'s, where the alphabet is {a,b}.

I understand that set of words that contain at least two *b*'s is: **\[1\]** `(a+b)*b(a+b)*b(a+b)*` and the set of words that contain at least two *a*'s is: **\[2\]** `(a+b)*a(a+b)*a(a+b)*`. In addition, I understand that the set of words that contain at least one *a* and at least one *b* is: **\[3\]** `(a+b)*(ab+ba)(a+b)*` (or at least *I think* that is correct).

I know the easy solution would be to use an intersection between **\[1\]** and **\[2\]**; however, I would like to understand how to accomplish this without using an intersection.

I know I would need to have `(a+b)*` at the beginning and at the end to say that any string made up of *a*'s and *b*'s can be at the beginning and at the end. But I am having trouble understanding the logic between those two points.

Just looking for some direction as I do not know where to go from there.

# Answer
You have written (a+b)*(ab+ba)(a+b)*

This contains atleast 1 a & at least 1 b. So what are ab & ba ? ab & ba are permutations of string you can form with at least one a & at least one b ! As you are asking for hint, You can write something like (a+b)\* (All Permutations of aabb ) (a+b)\*

Hope this helps.

There are just 6 permutations (4!/2!2!) of aabb here, so it wont be hard to calcualate them ! .
> -1 votes

# Answer
Random junk is $(a \mid b)^\*$, then (at least) two $b$ is $(a \mid b)^\* b (a \mid b)^\* b (a \mid b)^\*$. ($b$s separated by junk). Two $a$, two $b$ is one of $aabb$, $abab$, $abba$, $baba$, $bbaa$, $baab$ (this checks, there must be $\binom{4}{2} = 6$ of them). Fill out with junk:

$$(a \mid b)^\* a (a \mid b)^\* a (a \mid b)^\* b (a \mid b)^\* b (a \mid b)^\* \mid \dotsb$$

(fill out all the 6 alternatives above with $(a \mid b)^\*$ between fixed symbols, alternate between them).

Yes, very ugly, but easy to see it does the job.
> 2 votes

---
Tags: finite-automata, regular-expressions
---


# Question
Title: What is the difference between user-level threads and kernel-level threads?
After reading several sources I'm still confused about user- and kernel-level threads.

In particular:

> Threads can exist at both the user level and the kernel level

What is the difference between the user level and kernel level?

# Answer
One of the roles of a multitasking operating system kernel is scheduling: determining which thread of execution to execute when. So such a kernel has some notion of thread or process. A thread is a sequential piece of code that is executing, and has its own stack and sometimes other data. In an operating system context, people usually use *process* to mean a thread that has its own memory space, and *thread* to mean a thread that shares its memory space with other threads. A process can have one or more threads.

Some operating systems, for example older unix systems, only provide processes: every thread that the kernel manages has its own memory space. Other operating systems, for example most modern unix systems, allow processes to contain multiple threads of execution: they provide a kernel-level notion of threads.

It's also possible for a process to manage its own threading. In cooperative multithreading, the code of each thread contains instructions to switch to another thread. In preemptive multithreading, the process requests periodic asynchronous notifications from the kernel, and reacts to these notifications by switching to a different thread. This way, multithreading is implemented with no kernel cooperation, at the user level, in a library.

A system can offer both kernel-level and user-level threads; this is known as hybrid threading.

User- and kernel-level threads each have their benefits and downsides. Switching between user-level threads is often faster, because it doesn't require resetting memory protections to switch to the in-kernel scheduler and again to switch back to the process. This mostly matters for massively concurrent systems that use a large number of very short-lived threads, such as some high-level languages (Erlang in particular) and their green threads. User-level threads require less kernel support, which can make the kernel simpler. Kernel-level threads allow a thread to run while another thread in the same process is blocked in a system call; processes with user-level threads must take care not to make blocking system calls, as these block all the threads of the process. Kernel-level threads can run simultaneously on multiprocessor machines, which purely user-level threads cannot achieve.
> 30 votes

# Answer
Think of kernel level threads as "*virtual processors*" and user level threads as simply *threads* (Let's call them as such for now). Now, for a thread to be executed, it has get assigned on to a processor right? So, each thread gets assigned to a virtual processor so that it can be executed.

Here are facts

* Creating a new virtual processor is a bit costly. (The kernel has to create an entry in Thread Control Block, assign stack etc.)
* Creating a thread is pretty simple compared to creating a new virtual processor. An application developer can create threads using Thread Libraries provided by the programming languages and are managed in *User Space*. And different languages implement *multithreading* in different ways.

## Models

* If threads are mapped onto a single virtual processor, then one must be careful not to make a blocking system call in any of the threads, because other threads can no more run concurrently.
* This limitation can be overcome if a few more virtual processors can be created. Now, threads can run concurrently (in parallel if multiple real processors are present). A thread will not effect other threads which are mapped on other virtual processors.
* In the latter model, either one or many threads can be mapped onto a virtual processors.
* The above models are named Many to One, One to One and Many to Many respectively.

Referenes: Operating system concepts by Galvin et al. Topic: Threads -\> Multithreading Models
> 5 votes

---
Tags: operating-systems, terminology, concurrency, os-kernel
---


# Question
Title: Why $A \cap B = \widehat{\widehat{A}\cup \widehat{B}}$ does not holds for the class of Recursively Enumerable Languages?
> "*The class of Recursively Enumerable Languages is closed under Union, and Intersection but they are not closed under Complement.*"

I know why they are not closed under Complement & why they are closed under Union & Intersection but for other classes of languages we use a reasoning for closures based on the De'Morgan Law:

> $A \cap B = \widehat{\widehat{A}\cup \widehat{B}}$

That is,
*If some language class is closed under any two of the three operations namely, Union, Intersection & Complement then it must be closed under the third.*
So what's wrong with the class of Recursively Enumerable Languages?
are not they sets?
Or am I using implication incorrectly?

# Answer
The claim "If some language class is closed under any two of the three operations namely, Union, Intersection & Complement then it must be closed under the third." is not accurate. I'm not sure where you got it from, but it's not correct.

Recursively enumerable languages are closed under union and intersection. However, they're not closed under complement. And, there's no way to express complement using just union and intersection. So, the fact that they're closed under union and intersection does not imply that they're closed under complete. There's no paradox/contradiction here.
> 7 votes

---
Tags: closure-properties
---


# Question
Title: Does precedence matter in constructing parse trees of arithmetic expressions for postfix notation?
Table 4 in Problem Solving with Algorithms and Data Structures's chapter on Infix, Prefix and Postfix Expressions gives the following examples:

```
Infix Expression: A + B * C + D
Prefix Expression: + + A * B C D
Postfix Expression: A B C * + D +

```

Why is prefix not:

```
+ A + * B C D

```

To show my reason for this question, I'll use lowercase characters combined to represent a completed operation (e.g. `+ A B` becomes `ab`). Here's my thinking:

```
+ A + * B C D
+ A + bc D
+ A bcd
abcd

```

Here's my thinking applied to the answer supplied by the text:

```
+ + A * B C D
+ + A bc D
+ abc D
abcd

```

They both work?

I'm making the same mistake with

```
Infix Expression: A + B + C + D
Prefix Expression: + + + A B C D
Postfix Expression: A B + C + D +

```

I write postfix as:

```
A B C D + + +

```

...which is wrong (but I don't know why).

# Answer
What you're missing is the associativity of operators. All operators you mention in your examples are *binary*. An expression of the form $A + B + C + D$ is interpreted by the parser as $(((A+B)+C)+D)$. When converting such a fully parenthesized expression into prefix form, we apply the rule $(\alpha + \beta) \to +\alpha\beta$. Denote this transformation by $T$. Then $$ T\[(((A+B)+C)+D)\] = +T\[((A+B)+C)\]D = ++T\[(A+B)\]CD = +++ABCD. $$ In a completely analogous way, the operator $S$ converting into postfix makes the transformation $S\[(\alpha+\beta)\] = \alpha\beta+$: $$ S\[(((A+B)+C)+D)\] = S\[((A+B)+C)\]D+ = S\[(A+B)\]C+D+ = AB+C+D+. $$

The operator $+$ is associative, but imagine what happens with an operator like $-$. The expression $A-B-C$ is interpreted as $((A-B)-C)$, and its prefix and postfix forms are $--ABC$ and $AB-C-$, respectively. *Any other conversion would result in an arithmetically inequivalent expression.* That's why associativity matters.

Most operators associate to the left, just like $+$. Exponentiation traditionally associates to the right.

On top of this, we also have operator precedence, which leads to the parsing of $A+B\*C+D$ as $((A+(B\*C))+D)$. If you apply the transformations $T$ and $S$ you will get the expressions given in the book.
> 2 votes

# Answer
Yes in this case they both happen to equal the same value however yours is technically wrong. Your forgetting the final rule of order of operations which is left-to-right.

> A + B * C + D

(mult. first)

> A + \*bc + D

(left addition second)

> +a \*bc + D

(finally convert the last addition)

> ++a\*bcd

What you posted `+ A + * B C D` corresponds instead to A + (B\*C + D)
> 2 votes

# Answer
Ever heard of Tree traversals? I suggest you not to bang your head playing with expressions. Just construct a parse tree and perform

* In order traversal for infix notation - `L A R`
* Pre order traversal for prefix notation - `A L R`
* Post order traversal for postfix notation - `L R A`

where `L` = left child, `R` = Right child and `A` = parent. (See also Depth First Traversals)

The concept has something to do with removing *ambiguity* while deriving the parse tree. The expression `A + B + C + D` could have multiple parse trees, two of which are presented below.

```
  +                 +
 / \               / \
A   +             +   D
   / \           / \
  B   +         +   C
     / \       / \
    C   D     A   B

```

Left side tree's postorder ( `L R A` ) traversal gives your answer i.e. `A B C D + + +`, but the right tree's gives `A B + C + D +` and *luckily* both are correct. Why? Since all the three operators have same ***precedence*** and ***associativity*** doesn't matter for addition operator `+`. What if, the expression is `A + B * C - D`? Which is correct? This `A B C D - * +` or this `A B C * + D -`? So, you need to consider the *precedence* and *associativity* of the operators while constructing parse trees to generate *unambiguous* parse trees.

## Rules:

* For right associative operators (of same precedence) right recursive trees are generated, i.e. the tree grows towards right (left tree above fig) and right most operator is evaluated first.
* For left associative operators (of same precedence) left recursive trees are generated, i.e. the tree grows towards left (right tree above fig) and left most operator is evaluated first.
* The level of the operator with higher precedence must be lower in the tree than the level of the operator with lower precedence i.e. an operator with higher precedence is evaluated first and result is passed to the parent (in tree).

For the expression `A + B * C`,

```
  +              *
 / \            / \
A   *          +   C
   / \        / \
  B   C      A   B

```

left tree is correct, as the level of `*` is lower and right tree is wrong.

In order to reflect normal usage, **addition**, subtraction, multiplication, and division operators are usually **left**-associative while an exponentiation operator (if present) is right-associative. Source

See also Operator-precedence parser and Shunting Yard Algo by Dijkstra and an example considering precedence. Also, the precedence and associativity of operators in C++.

See also More examples of Infix, Postfix and Prefix conversions, making of parse tree (jump to the end of the page).
> 1 votes

---
Tags: formal-languages, parsers, syntax
---


title: Encryption on a compressed file

text:
# Question
Title: Encryption on a compressed file
Can I do encryption on a compressed file and again decompress the file after decryption to get the original data?

# Answer
> 3 votes
> Can i do encryption on a compressed file and again decompress the file after decryption to get the original data?

If the compression and decompression algorithms are lossless then yes.

If you are wondering about it, an example of a lossy compression system is the JPEG encoding process. The lost data is generally visually insignificant, but enables much better compression ratios. However strictly speaking an image encoded with JPEG will not produce *exactly* the same image after decompression.

Compression systems like zip, gzip and bzip use lossless compression.

Also note that compression is normally applied before encryption because encryption produces data that is essentially impossible to compress.

---
Tags: data-compression, encryption
---


# Question
Title: Search a preprocessed text with online queries
We're given a fixed text, and we are presented with a series of online queries of patterns. For each query, the goal is to answer if the pattern exists in the text. Each pattern is a string, and we want to know if it appears as a substring of the text. The text can be preprocessed.

What's the optimal way to solve this?

# Answer
> 4 votes
By building a suffix trie.

If you wish to preprocess the search query, then there is this algorithm by Boyer–Moore, whose complexity is believed to be linear after applying Galil Rule (details in the same page).

Other than that, if you can preprocess the whole text before hand and construct a Suffix Trie, then you can achieve many things. But the main limitation is it requires a lot of space.

See Suffix Trees and the lecture from MIT (Complete List)

See also Popular String searching algorithms.

---
Tags: optimization, strings, online-algorithms
---


# Question
Title: Showing that $\mathscr{L}$ is not context-free-grammar language
> Let $"t"$ and $"s"$ be a words we will say that two words are "completly different" if for all $1\leqslant i\leqslant |t|$ the $i$ letter in $t$ diffrent from the $i$ letter in $s$.
>
> Prove that the language $\mathcal{L}=\\{ts|t,s\in \\{0,1\\}^\*,|t|=|s|,t,s \text{ completly different} \\}$ is not a free-context-language

*Attempt :*

Applaying the pumping lemma for free-contex-language:

Suppose that $\mathcal L$ is regular so exists a word '$z=uxvyw$' with length of at least $n$ such that:

$(1)\\,\\,\\,|xvy|\leqslant n$

$(2)\\,\\,\\,|xy|\geqslant 1$

$(3)\\,\\,\\,ux^ivy^iw \in \mathcal L\\,\\,\\,\\,\\,\\,\\,\\,\\,i\geqslant 0$

Now, let's choose the word $\color{blue}{z=0^n1^n}$ it is obvious that $|z|\geqslant n$ so we can use $(1)-(3)$

$z=0^{\alpha}0^{\beta}0^{\gamma}0^{\lambda}1^n$

So $\alpha+\beta+\gamma+\lambda=n$

I am stuck here.

---

> EDIT: After using @Renato's answer:

Consider $z=0^p1^p0^p1^p0^p1^p\in \mathcal{L}$ since $|z|\>p$, there are $u,v,w,x,y$ such that $z=uvwxy,|vwx|\leqslant p, |vx|\>0$ and $uv^iwx^iy\in \mathcal{L}$

$vwx$ must straddle the midpoint of $z$ there are fore possibilities:

* $vwx$ is in $0^p$ part.
* $vwx$ is in $1^p$ part.
* $vwx$ is in $1^p0^p$ part.
* $vwx$ is in $0^p1^p$ part.

Thus, it is not of the form that we want

For $i=2$ $z\notin \mathcal{L}$

# Answer
You are wrong because you can pump in the middle of the word. A guy has commited the same mistake as you yesterday. Check this answer: https://cs.stackexchange.com/a/51613/31129
> 2 votes

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


# Question
Title: what is the k-line-connected graph definition
What is the definition for k-line-connectedness of the graph ? I am in doubt whether it differs from usual k-vertex (edge) connectedness. I've encountered it in the paper titled "Np-complete problems on a 3-connected cubic planar graph and their applications" where it comes without definition. Unfortunately for me I couldn't get the definition from the context given in its authors' proofs.

# Answer
Judging from the proof of Lemma 1 in the paper, *3-line-connected* is the same as *3-edge-connected*; *line* is probably a translation from Japanese.
> 3 votes

---
Tags: complexity-theory, graphs
---


# Question
Title: Pumping Lemma for $L = \left \{ a^{c}\mid \text{c is a composite number} \right \}$
$L = \left \\{ a^{c}\mid \text{c is a composite number} \right \\}$
I feel that this is not a context-free language as checking this constraint requires divisibility checking, but I am facing a hard time in proving that $L$ is not a Context Free Language using Pumping Lemma.
Could please anybody please give me a hint?

# Answer
> 8 votes
Let $p$ be the pumping length, and choose a prime $q \> p$. The word $a^{q^2}$ is in $L$, and so it can be written as $a^{q^2} = uvwxy$ so that $|vwx| \leq p$, $|vx| \geq 1$, and $uv^iwx^iy \in L$ for all $i \geq 0$. If $|vx| = \ell$ then $1 \leq \ell \leq p$, and for all $i \geq 0$, $q^2 + (i-1)\ell$ is composite. Since $\ell \leq p$ and $q$ is prime, $(q^2,\ell) = 1$, and so Dirichlet's theorem about primes in arithmetic progressions shows that for infinitely many $i \geq 0$, $q^2 + (i-1)\ell$ is prime. We have reached a contradiction.

An easier argument uses Parikh's theorem, which states that a unary language (a subset of $a^\*$) is context-free iff it is regular. In particular, it is enough to show that $L$ isn't regular. Since the complement of a regular language is regular, it's enough to show that $\overline{L} = \\{ a^k : k \text{ is prime}\\}$ is not regular. It is easier to use the pumping lemma for this language. Given a pumping length $p$, choose a prime $q \> p$. As before, there must exist $\ell \leq p$ so that $q + (i-1)p$ is prime for all $i \geq 0$. However, for $i = q+1$ we get $q + (i-1)p = q + qp = q(p+1)$, which isn't prime.

---
Tags: pumping-lemma
---


title: How to convert PDA to CFG

text:
# Question
Title: How to convert PDA to CFG
I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG?

For example: to write CFG for the automata

**My attempt:**

$S=A\_{03}$ because $q\_{\color{blue}0}$ is the initial state and $q\_{\color{blue}3}$ is the final state.

There are $4$ states so we will have $4^2$ variables:

$$A\_{00},A\_{01},A\_{02},A\_{03},\\ A\_{10},A\_{11},A\_{12},A\_{13},\\ A\_{20},A\_{21},A\_{22},A\_{23},\\ A\_{30},A\_{31},A\_{32},A\_{33}$$

for each state $q\_{i}$ of the automata $A\_{ii}\to\varepsilon$

$$A\_{00}\to \varepsilon\\ A\_{11}\to \varepsilon\\ A\_{22}\to \varepsilon\\ A\_{33}\to \varepsilon\\\$$

For each triplet of states $q\_i,q\_j,q\_k$, we add the rule $A\_{ij}\to A\_{ik}A\_{jk}$, this gives us $4^3=64$ rules:

$$A\_{00}\to A\_{00}A\_{00}|A\_{01}A\_{10}|A\_{02}A\_{20}|A\_{03}A\_{30}\\ A\_{01}\to A\_{00}A\_{01}|A\_{01}A\_{11}|A\_{02}A\_{21}|A\_{03}A\_{31}\\ A\_{02}\to A\_{00}A\_{02}|A\_{01}A\_{12}|A\_{02}A\_{22}|A\_{03}A\_{32}\\ \vdots\\ A\_{33}\to A\_{30}A\_{03}|A\_{31}A\_{13}|A\_{32}A\_{23}|A\_{33}A\_{33}\\\$$

I am stuck here.

# Answer
There is a standard construction to do this, discussed in all formal languages/automata courses. It results in gigantic grammars, often with lots of useless productions and nonterminals.

**Added, as requested by Nehorai:**

Take a PDA $M = (Q, \Sigma, \Gamma, \delta, q\_0, Z\_0, \varnothing)$ that accepts $L = \mathcal{N}(M)$ by empty stack (if you have a PDA accepting by final state, first convert to empty stack). We define a CFG that accepts $L$. The nonterminals are symbols of the form $\[p, A, q\]$ with $p, q \in Q$, $A \in \Gamma$, and a start symbol $S$. The idea is that if $\[p, A, q\] \Rightarrow^\* \sigma$, then if $M$ starts in state $p$ with $A$ on its stack, after consuming $\sigma$ it might be in state $q$ and the stack is shorter by one symbol for the first time. Consider an $A$ on the (eventually empty) stack as commitment to get rid of it.

If there is a move $(p, A\_1 A\_2 \dots A\_n) \in \delta(q, x, A)$ with $x = \epsilon$ or $x \in \Sigma$, this adds productions:

$\begin{align} \[q, A, q\_n\] \rightarrow x \[p A\_1 q\_1\] \[q\_1 A\_2 q\_2\] \dots \[q\_{n - 1} A\_n q\_n\] \end{align}$

I.e., we consume $x$ from the input (generate it in the grammar), going to state $p$, from which we now are committed to get rid of $A\_1 \dots A\_N$. We don't know what states $q\_1, \dotsc, q\_n$ are involved, we just know that after consuming e.g. $A\_i$ we will be in some state $q\_i$, from which we have to consume $A\_{i + 1}$. So we will have to consider *all* possible collections of states for them.

In the special case $(p, \epsilon) \in \delta(q, x, A)$, the above simplifies to:

$\begin{align} \[q, A, p\] \rightarrow x \end{align}$

If $x = \epsilon$, the above formally doesn't give a context free grammar, but with the standard construction $\epsilon$ productions can be eliminated.

To start the ball rolling, the stack initially contains just $Z\_0$, we are in state $q\_0$, and end up in any state:

$\begin{align} S \rightarrow \[q\_0, Z\_0, q\] \end{align}$

for any state $q \in Q$.

This should convince you the above construction is correct. It is *far* from a proof...
> 7 votes

# Answer
In your example you can easily read from the automaton what its language is.

The standard construction to convert a PDA into a CFG is usually called the triplet construction. In that construction the triplet $\[p,A,q\]$ represents a computation from state $p$ to state $q$ with symbol $A$ on top of the stack that (eventually) is popped.

But in your first attempt I see you are using a different technique. Presumably you should have a look in the book of Sipser? The variable $A\_{ij}$ will generate the strings read on a computation from state $q\_i$ to state $q\_j$ beginning and ending with the empty stack. (Which is not technically allowed in many other texts.) This construction combines a push of some stack symbol $Y$ with a pop of the same $Y$ elsewehere in the computation. So with the instructions $(q\_i,a,q\_k,\text{push}Y)$ and $(q\_\ell,b,q\_j,\text{pop}Y)$ the computation from $q\_i$ to $q\_j$ is started by reading $a$ pushing $Y$ and continuing from next state $q\_k$ we persue the computation until in state $q\_\ell$ we pop that same $Y$ read $b$ and move to state $q\_j$. This is summarized by the context-free rule $A\_{ij}\to a A\_{k\ell} b$.

Try this construction, but pick up a copy of your book or lecture notes on the way.
> 2 votes

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


title: This opertion gives overflow and carry?

text:
# Question
Title: This opertion gives overflow and carry?
Take this example in 2's complement representation with 8 bits.

1111 1110 + 1111 1110 ( -2 + -2 = -4 ) Calculation:

```
  1111 1110
 +1111 1110
 -----------
1|1111 1100 = -4 in 2's complement

```

This operation gives overflow and carry at the same time?

# Answer
> 0 votes
In this case you have no overflow, summing up two negative numbers giving negative number there is no overflow flag.
Carry flag is there, but since you have signed numbers, it does not matter.

But the ALU does not know whether it was signed, so flags it anyway.

It might occur at once: -70 + -100 10111010
+10011100
101010110

Result is carried and overflowed - it changed sign while both operands were not, and does not fit to 8bit representation.

---
Tags: arithmetic
---


# Question
Title: Distribute numbers 1,N on a grid as evenly as possible
I'm working on a complex engineering problem that I've essentially reduced to this problem:

I have a set of natural numbers $1,N$ and a grid (square or hexagonal) of exactly $N$ cells. I have to map each number to each cell so that the distribution (in a geometric sense) is *as flat as possible*. I'm still working on the definition of *flat*, but so far

1. The average of the numbers of a cell and its nearest neighbours must be as close to $N/2$ as possible, for every cell.
2. The average of the *distance* between a cell and each neighbour must be as large as possible.

If a cell has a number $n$ and its neighbour $m$ the distance between these neighbours is $min(|n-m|,N-|n-m|)$. It's essentially cyclical.

If $.$ represents a small number and # a large number I'm looking chessboard-like configurations like

```
.#.#.#.#
#.#.#.#.
.#.#.#.#

```

I need to find the best configuration (or a very good one) without using brute force.

Can you point me to some good algorithms that may be useful for this problem? I could only get above-average results on my own.

In my problem $N\approx~500$ and there is no runtime constraint.

# Answer
Simulated Annealing might work well for this problem.

The idea is to introduce a "temperature" component to your heuristic function to avoid getting stuck at local optima. Temperature corresponds to how willing the heuristic function is to accept an inferior arrangement. With simulated annealing, temperature starts off high and decreases until an optimal solution is found.

Here is solution to the Travelling Salesman Problem using simulated annealing

You can tinker with the starting temperature and its rate of change to try and find an optimal arrangement.
> 1 votes

---
Tags: algorithms, optimization, sorting
---


title: Random quadtrees

text:
# Question
Title: Random quadtrees
I have $N$ uniformly distributed 2D points and I want to find out how many points lie in some small rectangular region. However, the number of points can be arbitrarily large (e.g., $N=10^8$), so I don't want to explicitly generate points and insert them in some spatial data structure. I am not interested in the actual locations of points, just the number of them in some region. The search region is not known in advance, and I can perform queries in many different regions.

One solution is to use a quadtree and for every region query you traverse the tree and generate the number of points inside a node using multinomial distribution with probabilities 1/4 each.

For example, at the top level of the tree (level 1), there are N points. After one subdivision, nodes have $N\_1$, $N\_2$, $N\_3$ and $N\_4$ points that were distributed with multinomial distribution. The number of points in four children nodes must sum to the number of points in the parent node: $N = N\_1 + N\_2 + N\_3 + N\_4$. We continue traversal to some arbitrary depth level until we account for all quadtree nodes that overlapped the query region. This approach works, but the performance bottleneck is repeated generation of the number of particles in each node being traversed.

Question: Is there a way to compute the number of points in a region using purely probabilistic approach?

If there is a consistent enumeration of nodes in a quadtree, is there an algorithm that allows me to make a query "how many points lie in a quadtree node X at level L?" without explicit generation of the tree or hierarchical traversal described above?

# Answer
Yes, there are efficient solutions. Compute the area of the small rectangular region, and divide by the area of the entire region where the points are uniformly distributed. That is the probability that a single point falls within the small region; call this probability $p$. Now $pN$ (the product of $p$ and $N$) is the expected number of points within the small region.

More precisely, the number of points within the small region follows a Binomial$(N,p)$ distribution, so you can simulate a draw from that distribution with standard techniques. For instance, you can use the normal approximation (or, in some cases, the Poisson approximation) to very efficiently simulate drawing from this distribution.
> 1 votes

---
Tags: data-structures, probability-theory, probabilistic-algorithms
---


title: Graph Isomorphism variant

text:
# Question
Title: Graph Isomorphism variant
**Question:** Given 2 undirected graphs $G\_1$, $G\_2$, the problem whether exists a subgraph H1 of G1 which is isomorphic to a subgraph $H\_2$ of $G\_2$. What is the lowest complexity class for this problem: a. PSPACE b. NPC c. NP d. P

**Thoughts** We were thinking of this to be in NP because we can get a certificate of such two subgraphs and check the in polynomial time. But - we cannot determine whether this is complete or not. Is the only way to determine that is by trying to find a reduction to an NPC problem? Is there a specific way to prove that a language is NOT NPC but in NP?

# Answer
Showing that a problem has a polynomial time algorithm is strong evidence it's not $NP$-complete, but unless you plan to prove $P\not =NP$ the only languages you're going to prove are not $NP$-complete are the empty language and $\Sigma^\*$.

If you are interested in showing $NP$-completeness you may find our reference answer useful but I'd suggest looking at your problem definition carefully, thinking about what it means, and perhaps trying a few examples.
> 3 votes

# Answer
You haven't explained what you mean by *subgraph*. Here are a few possibilities:

* A subgraph of $G$ is a graph on the same vertex set but with possibly fewer edges. In that case, consider what happens when $H\_1,H\_2$ are the empty graphs.
* A subgraph of $G$ is a graph induced on a subset of the vertex set of $G$. In that case, consider what happens when $H\_1,H\_2$ are the graphs on one vertex.
* A subgraph of $G$ can be obtained by deleting both vertices and edges. This case left to you.
> 3 votes

---
Tags: time-complexity, complexity-classes
---


title: 'Stones' game complexity

text:
# Question
Title: 'Stones' game complexity
I'm trying to find complexity class of finding winning strategy for first player in following game:

Intance of 'Stones' game is:

* finite set $X$
* relation $R \subseteq X^3$
* set $Y \subseteq X$ and node $f \in X$

At the beggining we place stone in every element of $Y$. Every player in his turn can move stone from $x$ to $z$ iff. $\exists y.R(x, y, z) \wedge y\ has\ stone\ placed\ in\ it$. Player who places stone in $f$ wins.

I think it's $PSPACE-complete$, but I was trying to proove this for some time, and I run out of ideas.

I won't lie, it's homework assignment for my complexity class. Any help will be highly appreciated.

# Answer
> 5 votes
The game is actually an instance of two-persons Pebble game, as @HendrikJan pointed out, and as such is proven to be $EXPTIME-complete$. The following is a summary based on a proof by Kasai, Adachi and Iwata in SICOMP 8 (4).

For starters, it's pretty obvious that the game is in $EXPTIME$ - we can simply check all the possible games and see if there is winning strategy. To proove it's $EXPTIME-hard$ is a little bit more challenging.

First we need to know the notion of Alternating Turing machines (or ATMs for short). We will further tighten the definition to get so-called **standard ATM**:

We say an ATM $M$ is **standard** if

1. $M$ has only one work tape with the head initialized to the first cell of the tape,
2. if a configuration $C$ of $M$ is existential (universal), then every configuration $C’ \in Next\_M(C)$ is universal (existential),
3. the initial state is existential and the accepting state is universal, and
4. $Next\_M(C) = \emptyset$ if and only if $C$ is an accepting configuration.

Where $Next\_M(C)$ deontes set of possible configurations after one move starting from configuration $C$

Now there come two important lemmas proven by Chandra, Kozen and Stockmayer in Journal of the ACM 28(1):

---

**Lemma 1**

For every $S(n) \geq log (n)$, if $L \in ASPACE(S(n))$, then $L$ is accepted by a **standard** ATM within space $S(n)$.

---

**Lemma 2**

$EXPTIME = APSPACE$

---

Having those two in mind, we now see that, given a standard ATM $M = (Q, \Sigma, \Gamma, \delta, b, q\_1, q\_a, U)$ such that only $p(n)$ cells are available on the work tape for some polynomial $p$ in $n$, and a word $w = w\_1 w\_2 ... w\_n$, we need to construct, in logarythmic space, an instance of pebbles game $G$ such, that $w$ is accepted by $M$ iff. first player has winning strategy in $G$.

In order to do that we will need

1. set of fields $X$ consisting of

* fields representing the state of working tape ($\\{1..p(n)\\} \times \Gamma$)
    * fields representing current state of machine and it's heads ($Q \times \\{1..n\\} \times \\{1..p(n)\\}$)
    * fields representing work tape transitions ($Q \times \\{1..n\\} \times \\{1..p(n)\\} \times \Gamma^2)$
    * three additional fields $s\_1, s\_2, t$ to ensure that correct player wins the game
2. Set $R$ of rules that translates $\delta$ into our game:

* For each element of $Q \times \\{1..n\\} \times \\{1..p(n)\\}$ if $\delta (q, w\_i, a)$ contains $(q', a', (d', d'')), a \neq a'$ then this transition can be encoded with the following rules:
        + $(\[q, i, l\], \[l, a\], \[q, i, l, a, a'\])$
        + $(\[l, a\], \[q, i, l, a, a'\], \[l, a'\])$
        + $(\[q, i, l, a, a'\], \[l, a'\], \[q, i+d', l+d''\])$
    * For each element of $Q \times \\{1..n\\} \times \\{1..p(n)\\}$ if $\delta (q, w\_i, a)$ contains $(q', a, (d', d''))$ we need just one rule:
        + $(\[q, i, l\], \[l, a\], \[q, i+d', l+d''\])$
    * Finally we need to have "game finishers" rules:
        + for each $i$ and $l$ there should be rule $(\[q\_a, i, l\], s\_1, s\_2)$
        + we also add rule $(s\_2, s\_1, t)$
3. And to start the game properly we need the set $S = \\{\[q\_1,1,1\],s\_1\\} \cup \\{\[l,b\] | 1 \leq l \leq p(n)\\}$, which denotes that we're in initiall state, both heads are at the beggining of the tapes, and the working tape is empty.

From this, the proof of the fact that $w$ is accepted by $M$ iff. first player has a winning strategy in $G$ should be pretty straightforward.

---
Tags: complexity-theory, space-complexity, complexity-classes, game-theory
---


# Question
Title: Minimal class of grammar required to run program
In computability we have the hierarchy of grammars "https://en.wikipedia.org/wiki/Chomsky\_hierarchy". In this hierarchy we have many classes of grammar. This hierarchy has Turing machines at the top, and weaker machines lower. Machines are able to "recognize" languages within their class, and they are able to "decide" the halt-ability of weaker languages. "http://www.radford.edu/~nokie/classes/420/Chap3-Langs.html". Doing such tasks has different complexity classes based on the class of what is being acted on.

Here is my question: What is the process of determining the minimal class of machine required to recognize, and then decide, on a language. Also what is the cost of this function in relation to the class of machine?

I know that one way is to construct a grammar for a weak machine, see if it accepts, and then if you cant find one work your way up the hierarchy.

I certainly hope there is a solution to this problem besides just brute forcing potentially forever? Thanks!

# Answer
Determining whether a context-free grammar generates a regular language is undecidable (this is exercise 9.107 in Singh's *Elements of computation theory*; the reduction is from the Post correspondence problem). So if you are OK with a language being given to you as a context-free grammar, then even determining whether a language is regular or context-free but not regular is undecidable.
> 2 votes

---
Tags: complexity-theory, computability, turing-machines, formal-grammars
---


# Question
Title: How does a computer solve matrices of higher order?
To compute the determinant of a $n \times n$ matrix using the cofactor expansion requires roughly $n!$ operations ($n! = 1 \times 2 \times 3 \times \ldots \times n)$. Consider a $25 \times 25$ matrix. This would require $25!$ operations or roughly operations. Suppose you have a super computer that can do $1$ trillion operations per second. This calculation would require $500,000$ years!! How do you find the determinant of $25 \times 25$ matrix then?

# Answer
> 6 votes
There are other algorithms that can be used to calculate the determinant. The simplest ones find a triangular matrix similar to the given matrix. Since similar matrices have the same determinant, this reduces the general determinant question to triangular matrices, for which the computation is trivial (multiply the elements on the diagonal). This algorithm takes $O(n^3)$ practically (using LU decomposition), or $O(n^\omega)$ theoretically, where $\omega$ is the exponent of matrix multiplication.

From a theoretical perspective there are other non-trivial methods for computing the determinant, described on cstheory.

---
Tags: algorithms
---


# Question
Title: How to query and update ranges of arrays?
I have an array of size $N$ $(N \leq 10^5)$. I need to perform two types of operations on the array.

1. Decrease elements in range $\[L,R\]$ by $X$.
2. Count the number of negative elements in range $\[L,R\]$.

There are $10^5$ queries. All I can think about is using a segment tree with lazy propagation, but I believe there would be a better method. The segment tree method will probably time out because in case of alternate update/count queries, this will be close to linear.

# Answer
> 5 votes
Break the array up into $O(\sqrt{n})$ contiguous groups, each of size $O(\sqrt{n})$. With each group, store:

* A balanced binary search tree (BBST) containing the values of the elements in the array as keys and a pointer to their location in the group as a value.
* A modifier, $\delta$, indicating some offset that all of the elements have from $0$. For instance, if the elements are stored as $1,2,3$, but actually have the values $-11,-10,-9$, $\delta$ should be $-12$. The idea of $\delta$ is that decreasing the value of all of the elements in a group takes $O(1)$ time.
* The array elements themselves in array order

To decrease the elements in a range $\[R,L\]$ where $R$ and $L$ are in the same group, just walk the array and update the BBST for each element. This takes $O(\sqrt{n} \lg n)$ time.

To decrease the elements in an entire group at once, update $\delta$. This takes $O(1)$ time.

Every range contains $O(\sqrt{n})$ groups at most, and at most two of them are *not* wholly contained in the range - the end groups. Thus, to decrease a range $\[R,L\]$ takes $O(\sqrt{n} \lg n)$ total time

To count in a group, find the number of elements in the binary tree less than $-\delta$. This takes $O(\lg n)$ time in a BBST where the nodes are annotated by the sizes of their subtree.

To count in a part of a group, iterate over the array values in that part of the group and count how many are less than $-\delta$. This takes $O(\sqrt{n})$ time.

Again, every range contains $O(\sqrt{n})$ groups at most, and at most two of them are *not* wholly contained in the range - the end groups. Thus, to count a range $\[R,L\]$ takes $O(\sqrt{n} \lg n)$ total time

# Answer
> 0 votes
This can be done in **O(n lg n) easily** with following reduction:
You just want to know *how many negatives* are there,
**Idea : Just look at negative numbers as ones and non-negatives as zero**,
Then you have a array of ones and zeros that you want its range sum query, then use Fenwick(BIT) tree or Segment tree to calculate the result.
For **updates to be in O(lg n)**, you have to use normal update routines in Fenwick/Segment tree that works in O(lg n) but you should not insert the real value given to you instead you can replace the given value with one if it is negative and with zero if it is non-negative.

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


# Question
Title: Grammar of regular languages vs. context free languages
Let $L$ be some language. What could you say about $L$'s grammar if it is a regular language, that couldn't be said if it was a context free language?

For example, in case $L$ is regular, could you say that there exists a context-free grammar $S$ such that every derivation rule of $S$ is of the form:

$$V \rightarrow \sigma\_1 \sigma\_2 \cdots \sigma\_k V\_1V\_2 \cdots V\_m$$

In other words, the prefix of the rule contains only symbols of $\Sigma$ and the postfix contains only variables of $V$.

# Answer
> 11 votes
If the language is regular, then it can be defined using rules of the form $A \to \sigma B$ and $A\to \varepsilon$ by just simulating a finite state automaton. Here the nonterminals $A,B$ represent states of the automaton, and a production of the first type corresponds to a transition from $p$ to $q$ with label $\sigma$. The latter type of productions is for a final state $A$. Thus, when we use this construction the number of variables equals the number of states. As we know this number cannot be bounded.

Grammars of this type are called *right-linear*. Nowadays they are sometimes called regular grammars (but I am not fond of this as I would prefer regular to distinguish the expressions of that name).

If you do not like $\varepsilon$-production then we can take productions $A\to \sigma$ for transitions leading into a final state. But in this way we cannot produce the empty string.

Every context-free language can be generated by rules of the form $A \to \sigma B\_1\cdots B\_m$. This is called *Greibach normal form*. In general we can restrict to $m\le 2$ for this normal form. Restricting to $m\le 1$ will (of course) give only regular languages.

Greibach normal form is special as in each derivation step a letter is produced.

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


title: Synchronizing speech and text

text:
# Question
Title: Synchronizing speech and text
I have a text and a narration of the exact same text. What is the best way to synchronize them together? By synchronizing I mean, finding out for example the location of each word in the audio. For example if the sentence is "I took a cab" I want for markers on the accompanying audio which indicate start of each word.

Obviously any speech-to-text algorithm can be applied here, but given the fact that we've already know the text, I wonder if there's an algorithm for this simplified problem which works either much faster, or gives much better performance. Or if there is a general algorithm that can be tuned for this specific problem.

# Answer
> 1 votes
Papers on algorithms:

Implementations:

---
Tags: speech-recognition
---


title: Why is overfitting bad?

text:
# Question
Title: Why is overfitting bad?
I've studied this lots, and they say overfitting the actions in machine learning is bad, yet our neurons do become very strong and find the best actions/senses that we go by or avoid, plus can be de-incremented/incremented from bad/good by bad or good triggers, meaning the actions will level and it ends up with the best(right), super strong confident actions. How does this fail? It uses positive and negative sense triggers to de/re-increment the actions say from 44pos. to 22neg.

# Answer
The best explanation I've heard is this:

When you're doing machine learning, you assume you're trying to learn from data that follows some probabilistic distribution.

This means that in any data set, because of randomness, there will be some *noise*: data will randomly vary.

When you overfit, you end up learning from your noise, and including it in your model.

Then, when the time comes to make predictions from other data, your accuracy goes down: the noise made its way into your model, but it was specific to your training data, so it hurts the accuracy of your model. Your model doesn't generalize: it is too specific to the data set you happened to choose to train.
> 47 votes

# Answer
**ELI5 Version**

*This is basically how I explained it to my 6 year old.*

Once there was a girl named Mel (*"Get it? ML?" "Dad, you're lame."*). And every day Mel played with a different friend, and every day she played it was a sunny, wonderful day.

Mel played with Jordan on Monday, Lily on Tuesday, Mimi on Wednesday, Olive on Thursday .. and then on Friday Mel played with Brianna, and it rained. It was a terrible thunderstorm!

More days, more friends! Mel played with Kwan on Saturday, Grayson on Sunday, Asa on Monday ... and then on Tuesday Mel played with Brooke and it rained again, even worse than before!

Now Mel's mom made all the playdates, so that night during dinner she starts telling Mel all about the new playdates she has lined up. "Luis on Wednesday, Ryan on Thursday, Jemini on Friday, Bianca on Saturday -"

Mel frowned.

Mel's mom asked, "What's the matter, Mel, don't you like Bianca?"

Mel replied, "Oh, sure, she's great, but every time I play with a friend whose name starts with B, it rains!"

---

*What's wrong with Mel's answer?*

Well, it might not rain on Saturday.

*Well, I don't know, I mean, Brianna came and it rained, Brooke came and it rained ...*

Yeah, I know, **but rain doesn't depend on your friends.**
> 41 votes

# Answer
Overfitting implies that your learner won't generalize well. For example, consider a standard supervised learning scenario in which you try to divide points into two classes. Suppose that you are given $N$ training points. You can fit a polynomial of degree $N$ that outputs 1 on training points of the first class and -1 on training points of the second class. But this polynomial would probably be useless in classifying new points. This is an example of overfitting and why it's bad.
> 14 votes

# Answer
Roughly speaking, over-fitting typically occurs when the ratio

is too high.

Think of over-fitting as a situation where your model learn the training data by heart instead of learning the big pictures which prevent it from being able to generalized to the test data: this happens when the model is too complex with respect to the size of the training data, that is to say when the size of the training data is to small in comparison with the model complexity.

Examples:

* if your data is in two dimensions, you have 10000 points in the training set and the model is a line, you are likely to *under*-fit.
* if your data is in two dimensions, you have 10 points in the training set and the model is 100-degree polynomial, you are likely to *over*-fit.

From a theoretical standpoint, the amount of data you need to properly train your model is a crucial yet far-to-be-answered question in machine learning. One such approach to answer this question is the VC dimension. Another is the bias-variance tradeoff.

From an empirical standpoint, people typically plot the training error and the test error on the same plot and make sure that they don't reduce the training error at the expense of the test error:

I would advise to watch Coursera' Machine Learning course, section "10: Advice for applying Machine Learning".
> 9 votes

# Answer
I think we should consider two situations:

**Finite training**

There is a finite amount of data we use to train our model. After that we want to use the model.

In this case, if you overfit, you will not make a model of the phenomenon that yielded the data, but you will make a model of your data set. If your data set is not perfect - I have trouble imagining a perfect data set - your model will not work well in many or some situations, depending on the quality of the data you used to train on. So overfitting will lead to specialization on your data set, when you want generalization to model the underlying the phenomenon.

**Continuous learning**

Our model will receive new data all the time and keep learning. Possibly there is an initial period of increased elasticity to get an acceptable starting point.

This second case is more similar to how the human brain is trained. When a human is very young new examples of what you want to learn have a more pronounced influence than when you are older.

In this case overfitting provides a slightly different but similar problem: systems that fall under this case are often systems that are expected to perform a function while learning. Consider how a human is not just sitting somewhere while new data is presented to it to learn from. A human is interacting with and surviving in the world all the time.

You could argue that because the data keeps coming, the end result will work out fine, but in this time span what has been learned needs to be used! Overfitting will provide the same short time effects as in case 1, giving your model worse performance. But you are dependent on the performance of your model to function!

Look at at this way, if you overfit you might recognize that predator that is trying to eat you sometime in the future after many more examples, but when the predator eats you that is moot.
> 4 votes

# Answer
Let's say you want teach the computer to determine between good and bad products and give it the following dataset to learn:

0 means the product is faulty, 1 means it is OK. As you can see, there is a strong correlation between the X and Y axis. If the measured value is below or equal 50 it very likely (~98%) that the product is faulty and above it is very likley (~98%) it is OK. 52 and 74 are outliers (either measured wrong or not measured factors playing a role; also known as noise). The measured value might be thickness, temperature, hardness or something else and it's unit is not important in this example So the generic algorithm would be

```
if(I<=50)
    return faulty;
else
    return OK;

```

It would have a chance of 2% of misclassifying.

An overfitting algorithm would be:

```
if(I<50)
    return faulty;
else if(I==52)
    return faulty;
else if(I==74)
    return faulty;
else
    return OK;

```

So the overfitting algorithm would misclassify all products measuring 52 or 74 as faulty allthough there is a high chance that they are OK when given new datasets/used in production. It would have a chance of 3,92% of misclassifying. To an external observer this misclassification would be strange but explainable knowing the original dataset which was overfitted.

For the original dataset the overfitted algorithm is the best, for new datasets the generic (not overfitted) algorithm is most likely the best. The last sentence describes in basic the meaning of overfitting.
> 3 votes

# Answer
In my college AI course our instructor gave an example in a similar vein to Kyle Hale's:

> A girl and her mother are out walking in the jungle together, when suddenly a tiger leaps out of the brush and devours her mother. The next day she is walking through the jungle with her father, and again the tiger jumps out of the brush. Her father yells at her to run, but she replies "Oh, it's ok dad, tigers only eat mothers."

But on the other hand:

> A girl and her mother are out walking in the jungle together, when suddenly a tiger leaps out of the brush and devours her mother. The next day her father finds her cowering in her room and asks her why she isn't out playing with her friends. She replies "No! If I go outside a tiger will most certainly eat me!"

Both overfitting and underfitting can be bad, but I would say that it depends upon the context of the problem you are trying to solve which one worries you more.
> 2 votes

# Answer
One that I have actually encountered is something like this. First, I measure something where I expect the input to output ratio to be roughly linear. Here's my raw data:

```
Input   Expected Result
1.045   0.268333453
2.095   0.435332226
3.14    0.671001483
4.19    0.870664399
5.235   1.073669373
6.285   1.305996464
7.33    1.476337174
8.38    1.741328368
9.425   1.879004941
10.47   2.040661489

```

And here that is a graph:

Definitely appears to fit my expectation of linear data. Should be pretty straightforward to deduce the equation, right? So you let your program analyze this data for a bit, and finally it reports that it found the equation that hits all of these data points, with like 99.99% accuracy! Awesome! And that equation is... 9sin(x)+x/5. Which looks like this:

Well, the equation definitely predicts the input data with nearly perfect accuracy, but since it is so overfitted to the input data, it's pretty much useless for doing anything else.
> 2 votes

# Answer
Take a look at this article, it explains overfitting and underfitting fairly well.

http://scikit-learn.org/stable/auto\_examples/model\_selection/plot\_underfitting\_overfitting.html

The article examines an example of signal data from a cosine function. The overfitting model predicts the signal to be slightly more complicated function (that is also based on a cosine function). However, the overfitted model concludes this based not on generalization but on memorization of noise in the signal data.
> 1 votes

# Answer
With no experience in machine learning and judging from @jmite's answer here is a visualization of what I think he means:

Assume the individual bars in the graph above are your data, for which your trying to figure out the general trends to apply to larger sets of data. Your goal is to find the curved line. If you overfit - instead of the curved line shown, you connect the top of every individual bar together, and then apply that to your data set - and get a weird in-accurate spiky response as the noise (variations from the expected) gets exaggerated into your real-practice data sets.

Hope I've helped somewhat...
> 1 votes

# Answer
Overfitting in real life:

White person sees news story of black person committing crime. White person sees another news story of black person committing a crime. White person sees a third news story of black person committing a crime. White person sees news story about white person wearing red shirt, affluent parents, and a history of mental illness commit a crime. White person concludes that all black people commit crime, and only white people wearing red shirts, affluent parents, and a history of mental illness commit crime.

If you want to understand why this kind of overfitting is "bad", just replace "black" above with some attribute that more or less uniquely defines you.
> 0 votes

# Answer
Any data you test will have properties you want it to learn, and some properties that are irrelevant that you DON'T want it to learn.

John is age 11
Jack is age 19
Kate is age 31
Lana is age 39

Proper fitting: The ages are approximately linear, passing through ~age 20
Overfit: Two humans cannot be 10 years apart (property of noise in the data)
Underfit: 1/4 of all humans are 19 (stereotyping)
> 0 votes

---
Tags: machine-learning, statistics
---


title: 2 SAT variants complexity class

text:
# Question
Title: 2 SAT variants complexity class
**Question:** Which of the following languages are in P? which in NP? other classes?

a. EXACTLY-2-CNF (every clause in the formula has 2 differenet literelas)- does there exist a satisfying assignment s.t. at most k variables are TRUE.

b. same language but this time in each clause one literal is negated and the other isn't.

c. SAT-2-NAE - every clause has exactly 2 literals, is there an NAE satisfying assignment to the formula

d. mono-SAT-2-NAE - every clause as exactly 2 literals, none of them negated and it has a satisfying assignment

**Thoughts:** We tried a lot of reductions from 2SAT and other problems and cannot really determine most of the questions. We'd like to know what is the effect of the "monotone" property on the satisfiability such formulae... We'd also like some hints on how to reduce to these problems.

# Answer
> 3 votes
b. is completely trivial - just set each variable to FALSE.
d. trivially reduces to c.    c. reduces to d. as follows:
For each double-negative clause, remove the negatives.  Replace each
single-negative clause with 2 clauses, each of which has one of the original clause's variables
and a new variable that's shared with the other of the 2 new clauses but otherwise unused.

That works because:
for 2-variable clauses, NAE is just ≠
for boolean variables,    x  NAE  not y    simplifies to  x = y
for boolean variables, \[there exists a y such that    x ≠ y  and  y ≠ z \]  if and only if  x = z

By    variables \<-\> vertices  and  clauses \<-\> edges  ,    c. is equivalent to bipartiteness.
Bipartiteness is logspace-complete.  (Thus, c. and d. are logspace-complete.)
By throwing in k extra variables to handle "at most" vs. "exactly", a. is in W\[P\].
By    vertices -\> variables  and  edges -\> clauses  ,    vertex cover reduces to  a. .
(Thus, for unrestricted k, a. is NP-complete.)  However, a. is fixed-parameter tractable.

Proof:
By replacing each clause with k+1 copies of itself and then \[for each variable, putting in a
clause whose literals are both the negation of that variable\], a. reduces to Almost 2-SAT.
By part 2.1 of that paper, that paper handles the case of clauses whose 2 literals are the same.
Theorem 7 of that paper explicitly covers "possible repeated occurrences of clauses".

I have no clue regarding possible kernalizability of a. or
$\big\[$the space requirements of algorithms for a. whose runtimes aren't  max$\hspace{-0.03 in}\big(\hspace{-0.04 in}$n(k),$\hspace{.02 in}$2(n)$\hspace{-0.03 in}\big)\big\]$.

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


title: Inverting radial distortion

text:
# Question
Title: Inverting radial distortion
I'm trying to understand the math behind correcting a radial distortion (caused by a lens), but I'm failing to have it explained in simple terms.

I found several examples that proceed this way: a starting point $P = (x, y)$ is given and it is transformed to another point $P'=(x', y')$ with the following equations

$$\begin{align\*} x' &= x \cdot (1-a \cdot \\|P\\|) \\ y' &= y \cdot (1-b \cdot \\|P\\|)\\,. \end{align\*} $$

This causes radial distortion, depending on the constants $a$ and $b$. Here $\\|P\\|$ is the euclidean norm of the vector from the origin to the point P, i.e. $\\|P\\|=\sqrt{x^2 + y^2}$.

How can I invert these equations? In other words, given $x',y'$, I want to get back $x,y$.

# Answer
> 1 votes
I'm not sure inverting these equations will help you gain any understanding. Consider for example the simple case in which $a = b$. In that case, $$ x'^2 + y'^2 = (x^2 + y^2) (1- a\\|P\\|)^2 = \\|P\\|^2(1-a\\|P\\|)^2, $$ and taking square roots, $$ \sqrt{x'^2+y'^2} = \\|P\\|\\,\big|1-a\\|P\\|\big|. $$ You know the left-hand side. The right-hand side is either $\\|P\\|(1-a\\|P\\|)$ or $\\|P\\|(a\\|P\\|-1)$ (though I'm not sure the latter is physically possible in your case), and in each case you get a quadratic for $\\|P\\|$. You get at most four solutions for $\\|P\\|$, and for each positive one you can substitute back, calculate $x,y$, and check that the equations are satisfied.

The case $a \neq b$ looks more complicated, but perhaps can be solved explicitly using a bit of creative algebra. Failing that, there are numerical method that can invert these equations.

---
Tags: discrete-mathematics, image-processing, computer-vision
---


# Question
Title: Explanation of the knowledge representation hypothesis (Brian Smith)
In 1982 Brian Smith proposed his Knowledge Representation Hypothesis:

> Any mechanically embodied intelligent process will be comprised of structural ingredients that
>
> * we as external observers naturally take to represent a propositional account of the knowledge that the overall process exhibits, and
> * independent of such external semantic attribution, play a formal but causal and essential role in engendering the behavior that manifests that knowledge.

Can someone simplify this statement or add some explanations to it?

In particular I don't understand what is meant by "propositional account" and "formal but causal role".

Thanks!

# Answer
> 4 votes
This is a philosophical statement which uses sophisticated language per convention. Here is another version (according to this page):

> Any process capable of reasoning intelligently about the world must consist in part of a field of structures, of a roughly linguistic sort, which in some fashion represent whatever knowledge and beliefs the process may be said to possess.

You can visit the page I linked from some critique of both statements. For another critique, here is an example taken from these lecture notes. Consider the following two procedures for translating the colors red and blue into French:

```
function translate1(color):
  if color is "red" return "rouge"
  if color is "blue" return "bleu"

function translate2(color):
  dictionary = [ "red" -> "rouge", "blue" -> "bleu" ]
  return dictionary[color]

```

According to the lecture notes, only the second function `translate2` conforms to the hypothesis.

---

Now for some positive example. Consider an automated translation service such as Google translate. As a vast simplification, Google has a dictionary that it uses to translate words from (say) English to French. This dictionary is a "propositional account" of the knowledge of the process. Here by "propositional account", Smith means a set of logical statements, for example:

> The translation of *red* is *rouge*.
>
> The translation of *blue* is *bleu*.

(Technically, he means first-order logic, so you would put these statements in concise logical form, or as Prolog statements.)

The translation program uses its dictionary in its efforts. Thus the dictionary plays a "causal ... role" in the "behavior" of the system. That is, since *rouge* is the counterpart of *red*, if you give the program *red* it outputs *rouge*. We don't claim any 'real' intelligence for the program, so this role is only "formal", and moreover our understanding of the dictionary as a list of matching words in two different languages is only an "external semantic attribution" that is irrelevant for explaining the behavior of the program. After all, the program doesn't really 'speak' English or French, it only gives the impression of being able to.

---

Let me try to put the hypothesis in simpler words:

> Programs use databases that represent knowledge.

(See Surely you're joking, Mr Feynman!, page 281.)

Now we can come up with many more examples. JPEG compression programs use knowledge about the human visual system in the form of the quantization matrix, which explains which Fourier coefficients are more important for image representation. Recommendation systems use a database of products that can be recommended, and another database that keeps track of what other users liked. OCR systems use implicit representations of symbols (letters, digits, and punctuation) in the form of a machine learning recognizer for them.

Does modern machine learning conform to the hypothesis? Considering the last example, optical character recognition, the "catalog of characters" isn't stored as such, but only implicitly as (say) a set of weights in some neural network. This is certainly not a "field of structures, of a roughly linguistic sort", as per the other version of the hypothesis.

Modern artificial intelligence has largely moved away from the naive and romantic view of classical artificial intelligence, as exemplified by the KR hypothesis. Instead, now we often use statistical methods of machine learning which are much more successful in practice but much less satisfying from a human perspective.

Are knowledge representation techniques used in the real world? This is a question left for the experts to answer.

---
Tags: artificial-intelligence
---


# Question
Title: Given a λ-term, can I decide which machine model I need to express it?
I am having a hard time figuring out the specific relationship, of various things in computability. So we have a hierarchy of machines, with a (real life) upper bound of Turing machines, moving on down to things like deterministic finite automata. We also have a hierarchy of grammars that the machines can implement. These grammars range from recursively enumerable down to things like regular grammars. By implement I mean be configured in such a way that they either accept a string or declare it not part of the language.

The lambda calculus has a grammar. This grammar can be expressed on a low class of machine. The lambda calculus itself though is Turing complete. Clearly the syntax of the lambda calculus has no relationship to the power classification.

While the full lambda calculus is Turing complete you can restrict it in certain ways so that the syntax is the same, but the calculus becomes no longer Turing complete. This is talked about in the Turner paper:

"https://uf-ias-2012.wikispaces.com/file/view/turner.pdf/401400700/turner.pdf".

You could restrict it more, and make it an even weaker machine, until nothing can be expressed. As the version of lambda calculus you are programming in becomes weaker, and weaker, fewer grammars could be implemented.

Noting that the syntax is the same: Given a string representing a lambda expression X. Depending on the content of X only certain classes of restricted lambda calculus (to un-restricted) may be able to execute it. If the expression X requires a Turing machine to implement then a machine restricted to a weaker lambda calculus would not be able to express it.

Is it possible to determine what class of machine is required to express a given lambda expression? Turner in his paper clearly shows that you can restrict the lambda calculus to not require a Turing machine. But just given the expression, can you determine the class of machine?

# Answer
Paraphrasing, this seems to be your question:

> Given an unrestricted λ-term, can I determine what kind of automaton/machine model I need to express it?

Such properties are inherently undecidable (usually). Starting with a Turing-complete formalism, Rice's theorem immediately tells you that what you are asking is impossible.

The set of TMs/λ-terms corresponding to any non-empty, non-Turing-complete machine model forms a non-trivial index set and is thus is never decidable.

Of course, if you restrict yourself to a less than Turing-complete base set of terms, Rice's theorem does no longer apply. This is still a tough question to ask, though, even at lower levels of the hierarchy. For instance, it is undecidable if an NPDA accepts a DCFL, if a context-free grammar describes a regular language, or even if a context-free grammar is equivalent to a fixed regular grammar.
> 2 votes

---
Tags: computability, turing-machines, lambda-calculus, turing-completeness
---


# Question
Title: Maximum bipartite matching with extra reward for covering certain sets
Consider the following variation of Bipartite Maximum Matching. As usual, we have a bipartite graph $G$. In addition, there is an additional collection of sets $S\_1,S\_2,\dots,S\_k$, with each set $S\_{i}$ being defined as a collection of nodes from the right side of the graph $G$ as well as a weight.

Suppose that in a matching all nodes which $S\_{i}$ describes are matched. Then an extra bonus of weight($S\_{i}$) is gained.

Given a certain matching, define as $Y$ the set of all indexes $i$ such that $S\_{i}$ is fully covered by the matching (i.e all its nodes are matched). Then the profit of this matching is

$$\text{# edges} + \sum\_{a \in Y} \text{weight}(S\_{a}),$$

where $\text{# edges}$ is the number of edges in the matching.

The problem is, of course, to find the matching which maximizes the above quantity.

I instantly thought of the following exponential time algorithm. The algorithm works as follows:

```
For i in [0,2^k -1]:
    Define X= a subset containing all S_{j} such that  j-bit in i is 1.
    Try to find a maximum matching  only for the nodes which are defined by the elements of X
    If it is a maximum matching(I.e all elements in the right side are matched)
       Add all the other nodes not already present and continue the augmenting path algorihtm
Pick the maximum for all i

```

As I remember from my algorithm class, in the augmenting path algorithm, once a node in the left side has been assigned to the matching it never leaves it. Hence, the algorithm tries to make sure that in each iteration certain sets will be satisfied. Essentially, it is brute force. Therefore, optimality is proven easily. Unless of course my assumption is wrong.

The running time is $O(2^{k}\text{poly}(V,E))$ which is fine for my needs as $k$ is only 7.

But I am wondering whether there exists a polynomial algorithm for this or if the problem is NP-hard. Its clearly in NP but I have not had much success proving NP-completeness.

# Answer
> 4 votes
Let Y131P be "your problem with \[weights all equal to 1\] and
\[left-side degrees bounded above by 3\] and \[right-side degrees all equal to 1\]".
I will show hardness of Y131P.
Wikipedia gives two local gadget reductions from 3-SAT to 1-in-at-most-3-SAT.
The longer one induces a locally-computable bijection between
satisfying assignments whose inverse is also locally-computable.
The following is a linear reduction from 1-in-at-most-3-SAT to Y131P:

There is a left-side node for each variable and for each clause.    Each literal corresponds
to a set of  ( 1 + number\_of\_occurences\_of\_that\_literal\_in\_the\_input )  right-side nodes,
one of which is labeled with the literal LIT and the others of which are labeled  $\langle$LIT,C$\rangle$  for the
constraints C in which they appear.    Each right-side node labeled with a literal is adjacent
to the left-side node labeled with that literal's variable, and each right-side node labeled
with a pair  $\langle$LIT,C$\rangle$  is adjacent to the left-side node that corresponds to the constraint C.

(A satisfying assignment induces a matching which uses every left-side node and number\_of\_variables sets, so its value is    # left-side edges  +  number of variables    .
Since the graph is bipartite, no matching can have more edges than the number of left-side nodes.
Due to the left-side variables, sets for complementary literals can't simultaneously be chosen.  Thus, no matchings have value greater than    # left-side edges  +  number of variables  ,
and since the constraints are Exactly-1, there is an efficiently-computable bijection
\[between \[matchings whose value is that sum\] and satisfying assignments\]
whose inverse is also efficiently computable.)
In particular, Y131P is FNP-hard.

By \[that reduction being linear\] and the sparsification lemma, one gets that a
strong version of ETH would imply that Y131P takes takes 2(|E|) time to decide.
Since Y131P can be efficiently padded without changing k (just throw in
isolated edges between new vertices), the same strengthened ETH assumption
would imply that Y131P algorithms' runtime's dependency on k must be 2(k).

The rest of this answer's results apply even when the weights are
given in unary and are equal to each other (but not necessarily to 1).

As I'll use the phrase, "threshold constraints" specify \[a multi-set of literals\] and
\[a positive integer (the "threshold") that's at most the constraint's "size"\], where its "size"
is the sum of the multiplicities of the literals in the multi-set.  The constraint is satisfied
if and only if the sum of the multiplicities of the true literals is at least the threshold.
The following is a reduction from \[satisfying a list of threshold constraints\] to
your problem such that \[the number of sets is twice the number of variables\] and
\[the degree of the left-side nodes are at most  max ( 2 , size\_of\_largest\_constraint ) \]
and the degree of each right-side node is at most
max  (  1  ,  \[the maximum, taken over the constraints, of size minus threshold\]  )    :

Each variable corresponds to one left-side node and each constraint corresponds
to  ( size\_of\_the\_constraint - the\_constraint's\_threshold )  left-side nodes.
Each literal corresponds to a set of
( 1 + number\_of\_occurences\_of\_its\_complement\_in\_the\_input )
right-side nodes, one of which is labeled with the literal LIT and the others of which
are labeled  $\langle$LIT,C$\rangle$  for each occurrence of LIT's complement in a constraint C.
For each constraint C, for each literal LIT whose *complement* is in C, the node labeled
$\langle$LIT,C$\rangle$  is adjacent to \[the left-side nodes that correspond to C\] and nothing else.
For each variable v, \[the 2 right-side nodes labeled with v's literals\] are
adjacent to \[the left-side node that corresponds to v\] and nothing else.
The weights are equal to each other and greater than the number of variables plus
\[the sum, taken over the variables, of the maximum, taken over the variable's
positive and negative literal, of the number of occurrences of that literal in the input\].

(Due the the left-side variables, one can't choose both a variable and its negation.
Due to the number of nodes corresponding to a given constraint, one can't
choose too many literals in that constraint to be false, but can do anything else.
The weights are equal and large-enough to dominate over the other part of the matchings' values.
Thus, there's a many-one correspondence between \[solutions to the outputted instance of your problem\] and \[solutions to the input problem\], although the output problem can easily have
more than one solution even when the constraint satisfaction problem has a unique solution.)
Since threshold constraints can implement clauses by letting the thresholds be 1,
it follows that if $\big\[$there is a real number c such that  c \< 1/2  and there are arbitrarily-large
integers d such that for all integers b, there is an algorithm for \[$\hspace{.02 in}$your problem with \[$\hspace{.02 in}$left-side nodes
having degree d$\hspace{.02 in}$\] and \[right-side nodes having degree d-1\] and  |E| \< b$\cdot \hspace{-0.02 in}$k \]  whose runtime is
not eventually bounded below by  2$\hspace{.02 in}$c$\hspace{.02 in}\cdot \hspace{-0.02 in}$k $\big\]$   then the corresponding strengthing of SETH is false.

For the same reason, high-power compression of the graph and/or the sets
would yield compression of \[threshold-constraint\]-SAT, and I'm
not aware of any feasibility results regarding such compression.
(Reminder:  Threshold constraints can implement clauses by letting the thresholds be 1.)

However, that does not say anything about compressing *the weights*, and independently:

Weighted set packing reduces to maximum-weight independent set with number of vertices equal to the number of sets (adjacent if and only if intersect).  Maximum-weight independent set reduces to your problem (incidence graph).  When the right-side nodes each have degree at most 1, your problem reduces to weighted set packing with the number of sets equal to the number of vertices.
(Remove sets with degree-zero nodes, remove sets with a pair of nodes adjacent to the same node, then replace each set with the set of left-side nodes adjacent to an element of the set
and weight those sets by the original sets' weight plus number of non-removed elements.)
Thus, when the right-side nodes each have degree at most 1, your problem can be
*somewhat* kernelized.  (That "somewhat kernelization" doesn't simplify the weights.)

---
Tags: algorithms, graphs, bipartite-matching, computational-complexity
---


# Question
Title: No Naive Set Theoretic Models of Polymorphic Lambda Calculus?
In Philip Wadler's paper on Theorems for Free he states in Section 2 on Parametricity that

> there are no naive set-theoretic models of polymorphic lambda calculus

In the naive set-theoretic model types are sets and functions are set-theoretic functions which seems reasonable. So why does he say there are no naive set-theoretic models of polymorphic lambda calculus?

# Answer
The standard reference you are looking for is indeed Reynold's *Polymorphism is not Set Theoretic*. While it is quite obvious that you cannot form, e.g. the product $\Pi\_{S\in\mathrm{Set}}S$ over all sets using the usual set theoretic product, it's a legitimate, and non-trivial question whether there is some weaker notion of product that would work, while preserving the usual binary product $\times$ and function space $\rightarrow$.

This turns out to not be possible either, since on one hand, it is rather easy to build a type $\bf 2$ such that the interpretation has at least 2 elements, and show that the interpretation of $T=\Pi\_X(X\rightarrow {\bf 2})\rightarrow{\bf 2}$ is isomorphic to $(T\rightarrow {\bf 2})\rightarrow {\bf 2}$, which is not possible for the usual interpretation of $\rightarrow$ by the usual cantor paradox. In this sense it is somewhat similar to the proof for the untyped calculus.

Note that a further paper, by Andrew Pitts, *Polymorphism is Set Theoretic, Constructively*, overturns this conclusion somewhat by showing that the above contradiction is only possible to construct in **classical** set theory, and that there are several constructive theories of sets in which polymorphism *can* be interpreted with the usual interpretations of functions spaces and products. Most notably these "large products" exists in the Effective Topos, the most comprehensive of introductions being given by Phoa.
> 14 votes

---
Tags: functional-programming
---


# Question
Title: An obvious approach to NP = coNP, is there a counterexample?
Let's try to solve "co3SAT" with an NTM in polynomial time. It seems we need, more or less, to guess a proof that the formula is unsatisfiable i.e. derive a contradiction.

We've got a formula in conjunctive normal form, a big AND of OR clauses, each clause with 3 literals. Let's suppose we adopt the following strategy: at each stage, we expand two of of the clauses using the distributive law (AND distributes over OR), and simplify the result whenever possible. In the end, if the formula is unsatisfiable, we should get "false" from this procedure.

Is a lower bound known for this procedure (i.e. is it known whether this necessarily uses exponential time, given that we can use the non-determinism to select the optimal order in which the clauses are expanded)?

I read a little a bit about lower bounds for resolution techniques using the pigeonhole principle, but at first glance this seems like a different problem.

# Answer
> 4 votes
It is not known whether NP=coNP or NP≠coNP, but the latter is strongly suspected. It is not even known whether P≠NP implies NP≠coNP.

It is known that NP≠coNP implies P≠NP, and this approach for proving P≠NP is known as "Cook's program".

---

Now to your particular proof system. As far as I understand, your proof system maintains a collection of DNFs, which are initially the clauses of the original CNF (so they are trivial DNFs in the sense that all terms have width 1). At each step, you take two DNFs and combine them to a new DNF.

This system is similar to "depth-2 Frege", which is the following system. You start with "axioms" which are the clauses of the original CNF that you are trying to refute. The proof consists of a sequence of "lines" (propositions), each one either an axiom or following from previous lines via one or more derivation rules. In addition, all the lines are constrained to be formulas of depth 2 (CNFs or DNFs). The exact choice of derivation rules doesn't matter - fix any finite set of derivation rules of your choice.

It seems that one can simulate your proof system using depth-2 Frege in such a way that the number of lines in the Frege proof is comparable to the size of your proof. To know for sure, one needs to examine the exact simplification rules that you use, and show how to simulate them using depth-2 Frege. I believe that this should work out.

The pigeonhole principle is hard not only for Resolution, but also for bounded depth Frege. In particular, refuting the pigeonhole principle using depth-2 Frege takes $2^{n^{\Omega(1)}}$ lines, where $n$ can be taken as the size of the formula. See for example Fu and Urquhart.

---
Tags: complexity-theory, np, co-np
---


title: What are GPU arrays?

text:
# Question
Title: What are GPU arrays?
I came across the Python library libgpuarray and was reading about it but could not really understand what a GPU array is and why do we need it? What is the difference between a normal array and GPU array?

Please excuse the noobness of the question.

# Answer
> 4 votes
Libgpuarray is package (like in proxy or wrapper) around cuda and opencl ndarray - meaning that computation is done on device side (GPU side) as opposed to host side (CPU).
This is described in documentation, and also defined what were the goals of this particular library.

It makes sense to talk about "faster" in terms of GPU if we are having a lot of data, which can be solved on different threads or vectorised (SIMT - new to Flynn taxonomy due to massive parallel but limited computation).

Strictly sequential algorithms benefit nothing, CPU has higher power for them, because GPU cores are slower.
It is not like it is fancy to compute on GPU disregarding problem statement.

On GPU you have smaller and constrainef memory, you have to take bandwidth (sending data from host to device, computation time and sending results from device to host) ti know whether there is speed up or slow down effect on your program.

# Answer
> 0 votes
Most probably, a GPU array is an array which is stored and processed on the GPU. Operations on the GPU are faster than those on the CPU, which is why you'd want to use such an array.

---
Tags: arrays
---


# Question
Title: Prove an arithmetic property of a partial recursive function
I have this program written in haskell :

I have to prove that: $(\forall a \in \mathbb{N})\[!D\_V \[h\](a) \Rightarrow log\_2 (D\_V\[h\](a) )\equiv 2 (mod$ $ 10) \]$.

The predicate $P\_2$ for the $g$ function is obvious : $P\_2(f,g) \equiv (\forall x,y \in \mathbb{N})\[!g(x,y) \Rightarrow g(x,y)\backsimeq xy\]$.

But the predicate for the function $f$ which would give me authomaticaly the one for $h$ I have no idea what it should be.

Any ideas and help in solving this problem is welcomed :)

Notations:

* $D\_V\[h\]$: denotational semantics with passing by value of the function $f$.
* $!F(x)$ means that $F$ is defined at point $x$.
* $F(x) \backsimeq V$ means has the value $V$ at the point $x$ or is undefined.

# Answer
The function $f$ computes the recurrence relation $$ f(x) = \begin{cases} 4 & x \leq 1, \\ f(x-1)^2 f(x-2)^4 & x \> 1. \end{cases} $$ Taking $\ell = \log\_2 \circ f$, we get $$ \ell(x) = \begin{cases} 2 & x \leq 1, \\ 2\ell(x-1) + 4\ell(x-2) & x \> 1. \end{cases} $$ Now, modulo 10 we have $$ 2 \cdot 2 + 4 \cdot 2 = 12 \equiv 2 \pmod{10}. $$ An easy proof by induction then shows that $\ell(x) \equiv 2 \pmod{10}$ for all $x$.
> 2 votes

---
Tags: programming-languages, denotational-semantics
---


# Question
Title: Algorithm to find the shortest walk with k leaf nodes on a tree
Let's say I have a general tree. What algorithm can I use to find a shortest walk that starts at the root, passes through exactly $k$ different leaves, and ends at the root? Passing through a node/edge more than once is allowed.

For example, consider this graph:

For $k = 1$, the shortest walk would have the node *4*. For $k = 2$, the leaf nodes would be *4* and *12*. For $k = 3$, the leaves would be *4*, *16* and *17*.

What I actually need is the length of the shortest walk (if this simplifies anything).

I could not find an algorithm for this, but maybe I searched with the wrong terms.

# Answer
This can be solved by a fairly standard dynamic programming algorithm. For a given node $v$, let $C(v,k)$ be the minimum length of a (closed) walk through the subtree rooted at $v$ passing through exactly $k$ leaf nodes ($C(v,k)=\infty$ if there is no such walk).

If a node $v$ has children $c\_1,\ldots c\_m$, then $C(v,k) = min\_{k=a\_1 + \ldots + a\_m} \Sigma\_{\\{i:a\_i\not = 0\\}} 2 + C(c\_i, a\_i)$ (i.e. taking the minimum over all ways to split up $k$ over the children of the node).

With some modification, this can be made to run in $O(n^3)$.
> 4 votes

---
Tags: graphs, trees, shortest-path
---